wave_compiler/regalloc/
live_range.rs

1// Copyright 2026 Ojima Abraham
2// SPDX-License-Identifier: Apache-2.0
3
4//! Live range computation for virtual registers.
5//!
6//! Computes the program points where each virtual register is live,
7//! represented as intervals over instruction indices in the flat LIR.
8
9use std::collections::{HashMap, HashSet};
10
11use crate::lir::instruction::LirInst;
12use crate::lir::operand::VReg;
13
14/// A live range interval [start, end) for a virtual register.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct LiveRange {
17    /// First instruction index where the value is defined.
18    pub start: usize,
19    /// Last instruction index where the value is used (inclusive).
20    pub end: usize,
21}
22
23impl LiveRange {
24    /// Returns true if this live range overlaps with another.
25    #[must_use]
26    pub fn overlaps(&self, other: &Self) -> bool {
27        self.start <= other.end && other.start <= self.end
28    }
29
30    /// Returns the length of this live range.
31    #[must_use]
32    pub fn length(&self) -> usize {
33        if self.end >= self.start {
34            self.end - self.start + 1
35        } else {
36            0
37        }
38    }
39}
40
41/// Compute live ranges for all virtual registers in a LIR instruction sequence.
42#[must_use]
43pub fn compute_live_ranges(instructions: &[LirInst]) -> HashMap<VReg, LiveRange> {
44    let mut ranges: HashMap<VReg, LiveRange> = HashMap::new();
45
46    for (idx, inst) in instructions.iter().enumerate() {
47        if let Some(dest) = inst.dest_vreg() {
48            ranges
49                .entry(dest)
50                .and_modify(|r| {
51                    if idx < r.start {
52                        r.start = idx;
53                    }
54                    if idx > r.end {
55                        r.end = idx;
56                    }
57                })
58                .or_insert(LiveRange {
59                    start: idx,
60                    end: idx,
61                });
62        }
63
64        for src in inst.src_vregs() {
65            ranges
66                .entry(src)
67                .and_modify(|r| {
68                    if idx < r.start {
69                        r.start = idx;
70                    }
71                    if idx > r.end {
72                        r.end = idx;
73                    }
74                })
75                .or_insert(LiveRange {
76                    start: idx,
77                    end: idx,
78                });
79        }
80    }
81
82    ranges
83}
84
85/// Collect all virtual registers used in the instruction sequence.
86#[must_use]
87pub fn collect_vregs(instructions: &[LirInst]) -> HashSet<VReg> {
88    let mut vregs = HashSet::new();
89    for inst in instructions {
90        if let Some(dest) = inst.dest_vreg() {
91            vregs.insert(dest);
92        }
93        for src in inst.src_vregs() {
94            vregs.insert(src);
95        }
96    }
97    vregs
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn test_live_range_overlap() {
106        let a = LiveRange { start: 0, end: 5 };
107        let b = LiveRange { start: 3, end: 8 };
108        let c = LiveRange { start: 6, end: 10 };
109        assert!(a.overlaps(&b));
110        assert!(!a.overlaps(&c));
111        assert!(b.overlaps(&c));
112    }
113
114    #[test]
115    fn test_compute_live_ranges() {
116        let insts = vec![
117            LirInst::MovImm {
118                dest: VReg(0),
119                value: 1,
120            },
121            LirInst::MovImm {
122                dest: VReg(1),
123                value: 2,
124            },
125            LirInst::Iadd {
126                dest: VReg(2),
127                src1: VReg(0),
128                src2: VReg(1),
129            },
130            LirInst::Halt,
131        ];
132
133        let ranges = compute_live_ranges(&insts);
134        assert_eq!(ranges[&VReg(0)], LiveRange { start: 0, end: 2 });
135        assert_eq!(ranges[&VReg(1)], LiveRange { start: 1, end: 2 });
136        assert_eq!(ranges[&VReg(2)], LiveRange { start: 2, end: 2 });
137    }
138
139    #[test]
140    fn test_collect_vregs() {
141        let insts = vec![
142            LirInst::Iadd {
143                dest: VReg(2),
144                src1: VReg(0),
145                src2: VReg(1),
146            },
147            LirInst::Halt,
148        ];
149        let vregs = collect_vregs(&insts);
150        assert_eq!(vregs.len(), 3);
151        assert!(vregs.contains(&VReg(0)));
152        assert!(vregs.contains(&VReg(1)));
153        assert!(vregs.contains(&VReg(2)));
154    }
155}
wave_compiler/regalloc/live_range.rs

wave_compiler/regalloc/
live_range.rs
