wave_compiler/regalloc/
interference.rs

1// Copyright 2026 Ojima Abraham
2// SPDX-License-Identifier: Apache-2.0
3
4//! Interference graph construction.
5//!
6//! Two virtual registers interfere if their live ranges overlap.
7//! The interference graph has `VReg`s as nodes and edges between
8//! interfering registers. Move-related pairs are tracked for coalescing.
9//! Parameter `VReg`s have live ranges extended to start at instruction 0
10//! since they are live from function entry.
11
12use std::collections::{HashMap, HashSet};
13
14use super::live_range::{compute_live_ranges, LiveRange};
15use crate::lir::instruction::LirInst;
16use crate::lir::operand::VReg;
17
18/// Interference graph for register allocation.
19pub struct InterferenceGraph {
20    /// Adjacency sets: for each `VReg`, the set of interfering `VReg`s.
21    pub adj: HashMap<VReg, HashSet<VReg>>,
22    /// Move pairs (dest, src) for coalescing.
23    pub moves: Vec<(VReg, VReg)>,
24    /// Live ranges for each `VReg`.
25    pub ranges: HashMap<VReg, LiveRange>,
26}
27
28impl InterferenceGraph {
29    /// Build the interference graph from LIR instructions.
30    #[must_use]
31    pub fn build(instructions: &[LirInst]) -> Self {
32        Self::build_with_params(instructions, 0)
33    }
34
35    /// Build the interference graph, extending param `VReg` live ranges to start at 0.
36    #[must_use]
37    pub fn build_with_params(instructions: &[LirInst], num_params: u32) -> Self {
38        let mut ranges = compute_live_ranges(instructions);
39
40        for i in 0..num_params {
41            let vreg = VReg(i);
42            ranges
43                .entry(vreg)
44                .and_modify(|r| r.start = 0)
45                .or_insert(LiveRange { start: 0, end: 0 });
46        }
47
48        let mut adj: HashMap<VReg, HashSet<VReg>> = HashMap::new();
49        let mut moves = Vec::new();
50
51        let vregs: Vec<VReg> = ranges.keys().copied().collect();
52
53        for &vreg in &vregs {
54            adj.entry(vreg).or_default();
55        }
56
57        for i in 0..vregs.len() {
58            for j in (i + 1)..vregs.len() {
59                let a = vregs[i];
60                let b = vregs[j];
61                if ranges[&a].overlaps(&ranges[&b]) {
62                    adj.entry(a).or_default().insert(b);
63                    adj.entry(b).or_default().insert(a);
64                }
65            }
66        }
67
68        for inst in instructions {
69            if let LirInst::MovReg { dest, src } = inst {
70                if !adj.get(dest).is_some_and(|s| s.contains(src)) {
71                    moves.push((*dest, *src));
72                }
73            }
74        }
75
76        Self { adj, moves, ranges }
77    }
78
79    /// Returns the degree (number of neighbors) of a `VReg`.
80    #[must_use]
81    pub fn degree(&self, vreg: VReg) -> usize {
82        self.adj.get(&vreg).map_or(0, HashSet::len)
83    }
84
85    /// Returns true if two `VReg`s interfere.
86    #[must_use]
87    pub fn interferes(&self, a: VReg, b: VReg) -> bool {
88        self.adj.get(&a).is_some_and(|s| s.contains(&b))
89    }
90
91    /// Returns all `VReg`s in the graph.
92    #[must_use]
93    pub fn nodes(&self) -> Vec<VReg> {
94        self.adj.keys().copied().collect()
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn test_interference_graph_simple() {
104        let insts = vec![
105            LirInst::MovImm {
106                dest: VReg(0),
107                value: 1,
108            },
109            LirInst::MovImm {
110                dest: VReg(1),
111                value: 2,
112            },
113            LirInst::Iadd {
114                dest: VReg(2),
115                src1: VReg(0),
116                src2: VReg(1),
117            },
118            LirInst::Halt,
119        ];
120
121        let ig = InterferenceGraph::build(&insts);
122        assert!(ig.interferes(VReg(0), VReg(1)));
123        assert!(ig.degree(VReg(0)) >= 1);
124    }
125
126    #[test]
127    fn test_non_overlapping_no_interference() {
128        let insts = vec![
129            LirInst::MovImm {
130                dest: VReg(0),
131                value: 1,
132            },
133            LirInst::MovImm {
134                dest: VReg(1),
135                value: 2,
136            },
137        ];
138
139        let ig = InterferenceGraph::build(&insts);
140        assert!(!ig.interferes(VReg(0), VReg(1)));
141    }
142
143    #[test]
144    fn test_move_between_interfering_not_coalescable() {
145        let insts = vec![
146            LirInst::MovImm {
147                dest: VReg(0),
148                value: 1,
149            },
150            LirInst::MovReg {
151                dest: VReg(1),
152                src: VReg(0),
153            },
154            LirInst::Halt,
155        ];
156
157        let ig = InterferenceGraph::build(&insts);
158        assert!(ig.moves.is_empty());
159    }
160
161    #[test]
162    fn test_params_interfere_with_later_temps() {
163        let insts = vec![
164            LirInst::MovImm {
165                dest: VReg(2),
166                value: 4,
167            },
168            LirInst::Iadd {
169                dest: VReg(3),
170                src1: VReg(0),
171                src2: VReg(2),
172            },
173            LirInst::Iadd {
174                dest: VReg(4),
175                src1: VReg(1),
176                src2: VReg(2),
177            },
178            LirInst::Halt,
179        ];
180
181        let ig = InterferenceGraph::build_with_params(&insts, 2);
182        assert!(ig.interferes(VReg(0), VReg(2)));
183        assert!(ig.interferes(VReg(1), VReg(2)));
184    }
185}
wave_compiler/regalloc/interference.rs

wave_compiler/regalloc/
interference.rs
