regalloc2 0.15.1

Backtracking register allocator inspired from IonMonkey
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use core::fmt;

use crate::ion::data_structures::VRegIndex;
use crate::VReg;
use alloc::vec;
use alloc::vec::Vec;

#[derive(Clone)]
struct VRegNode {
    next: VRegIndex,
    prev: VRegIndex,
    vreg: VReg,
}

// Using a doubly linked list here for fast insertion,
// removal and iteration.
pub struct VRegSet {
    items: Vec<VRegNode>,
    head: VRegIndex,
}

impl VRegSet {
    pub fn with_capacity(num_vregs: usize) -> Self {
        Self {
            items: vec![
                VRegNode {
                    prev: VRegIndex::new(num_vregs),
                    next: VRegIndex::new(num_vregs),
                    vreg: VReg::invalid()
                };
                num_vregs + 1
            ],
            head: VRegIndex::new(num_vregs),
        }
    }

    pub fn insert(&mut self, vreg: VReg) {
        debug_assert_eq!(self.items[vreg.vreg()].vreg, VReg::invalid());
        let old_head_next = self.items[self.head.index()].next;
        self.items[vreg.vreg()] = VRegNode {
            next: old_head_next,
            prev: self.head,
            vreg,
        };
        self.items[self.head.index()].next = VRegIndex::new(vreg.vreg());
        self.items[old_head_next.index()].prev = VRegIndex::new(vreg.vreg());
    }

    pub fn remove(&mut self, vreg_num: usize) {
        let prev = self.items[vreg_num].prev;
        let next = self.items[vreg_num].next;
        self.items[prev.index()].next = next;
        self.items[next.index()].prev = prev;
        self.items[vreg_num].vreg = VReg::invalid();
    }

    pub fn is_empty(&self) -> bool {
        self.items[self.head.index()].next == self.head
    }

    pub fn iter(&self) -> VRegSetIter<'_> {
        VRegSetIter {
            curr_item: self.items[self.head.index()].next,
            head: self.head,
            items: &self.items,
        }
    }
}

pub struct VRegSetIter<'a> {
    curr_item: VRegIndex,
    head: VRegIndex,
    items: &'a [VRegNode],
}

impl<'a> Iterator for VRegSetIter<'a> {
    type Item = VReg;

    fn next(&mut self) -> Option<Self::Item> {
        if self.curr_item != self.head {
            let item = self.items[self.curr_item.index()].clone();
            self.curr_item = item.next;
            Some(item.vreg)
        } else {
            None
        }
    }
}

impl fmt::Debug for VRegSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{{ ")?;
        for vreg in self.iter() {
            write!(f, "{vreg} ")?;
        }
        write!(f, "}}")
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::RegClass;
    use RegClass::*;
    const VREG: fn(usize, RegClass) -> VReg = VReg::new;

    #[test]
    fn operations() {
        let mut set = VRegSet::with_capacity(3090);
        assert!(set.is_empty());
        set.insert(VREG(10, Int));
        set.insert(VREG(2000, Int));
        set.insert(VREG(11, Vector));
        set.insert(VREG(199, Float));
        set.insert(VREG(23, Int));
        let mut iter = set.iter();
        assert_eq!(iter.next(), Some(VREG(23, Int)));
        assert_eq!(iter.next(), Some(VREG(199, Float)));
        assert_eq!(iter.next(), Some(VREG(11, Vector)));
        assert_eq!(iter.next(), Some(VREG(2000, Int)));
        assert_eq!(iter.next(), Some(VREG(10, Int)));

        set.remove(23);
        set.remove(11);
        set.insert(VREG(73, Vector));
        let mut iter = set.iter();
        assert_eq!(iter.next(), Some(VREG(73, Vector)));
        assert_eq!(iter.next(), Some(VREG(199, Float)));
        assert_eq!(iter.next(), Some(VREG(2000, Int)));
        assert_eq!(iter.next(), Some(VREG(10, Int)));
        assert!(!set.is_empty());
    }

    #[test]
    fn empty() {
        let mut set = VRegSet::with_capacity(2000);
        assert!(set.is_empty());
        set.insert(VREG(100, Int));
        assert!(!set.is_empty());
        set.remove(100);
        assert!(set.is_empty());
    }
}