rustc_passes/liveness/
rwu_table.rs

Help
1use std::iter;
2
3use crate::liveness::{LiveNode, Variable};
4
5#[derive(Clone, Copy)]
6pub(super) struct RWU {
7    pub(super) reader: bool,
8    pub(super) writer: bool,
9    pub(super) used: bool,
10}
11
12/// Conceptually, this is like a `Vec<Vec<RWU>>`. But the number of
13/// RWU's can get very large, so it uses a more compact representation.
14pub(super) struct RWUTable {
15    /// Total number of live nodes.
16    live_nodes: usize,
17    /// Total number of variables.
18    vars: usize,
19
20    /// A compressed representation of `RWU`s.
21    ///
22    /// Each word represents 2 different `RWU`s packed together. Each packed RWU
23    /// is stored in 4 bits: a reader bit, a writer bit, a used bit and a
24    /// padding bit.
25    ///
26    /// The data for each live node is contiguous and starts at a word boundary,
27    /// so there might be an unused space left.
28    words: Vec<u8>,
29    /// Number of words per each live node.
30    live_node_words: usize,
31}
32
33impl RWUTable {
34    const RWU_READER: u8 = 0b0001;
35    const RWU_WRITER: u8 = 0b0010;
36    const RWU_USED: u8 = 0b0100;
37    const RWU_MASK: u8 = 0b1111;
38
39    /// Size of packed RWU in bits.
40    const RWU_BITS: usize = 4;
41    /// Size of a word in bits.
42    const WORD_BITS: usize = std::mem::size_of::<u8>() * 8;
43    /// Number of packed RWUs that fit into a single word.
44    const WORD_RWU_COUNT: usize = Self::WORD_BITS / Self::RWU_BITS;
45
46    pub(super) fn new(live_nodes: usize, vars: usize) -> RWUTable {
47        let live_node_words = (vars + Self::WORD_RWU_COUNT - 1) / Self::WORD_RWU_COUNT;
48        Self { live_nodes, vars, live_node_words, words: vec![0u8; live_node_words * live_nodes] }
49    }
50
51    fn word_and_shift(&self, ln: LiveNode, var: Variable) -> (usize, u32) {
52        assert!(ln.index() < self.live_nodes);
53        assert!(var.index() < self.vars);
54
55        let var = var.index();
56        let word = var / Self::WORD_RWU_COUNT;
57        let shift = Self::RWU_BITS * (var % Self::WORD_RWU_COUNT);
58        (ln.index() * self.live_node_words + word, shift as u32)
59    }
60
61    fn pick2_rows_mut(&mut self, a: LiveNode, b: LiveNode) -> (&mut [u8], &mut [u8]) {
62        assert!(a.index() < self.live_nodes);
63        assert!(b.index() < self.live_nodes);
64        assert!(a != b);
65
66        let a_start = a.index() * self.live_node_words;
67        let b_start = b.index() * self.live_node_words;
68
69        unsafe {
70            let ptr = self.words.as_mut_ptr();
71            (
72                std::slice::from_raw_parts_mut(ptr.add(a_start), self.live_node_words),
73                std::slice::from_raw_parts_mut(ptr.add(b_start), self.live_node_words),
74            )
75        }
76    }
77
78    pub(super) fn copy(&mut self, dst: LiveNode, src: LiveNode) {
79        if dst == src {
80            return;
81        }
82
83        let (dst_row, src_row) = self.pick2_rows_mut(dst, src);
84        dst_row.copy_from_slice(src_row);
85    }
86
87    /// Sets `dst` to the union of `dst` and `src`, returns true if `dst` was
88    /// changed.
89    pub(super) fn union(&mut self, dst: LiveNode, src: LiveNode) -> bool {
90        if dst == src {
91            return false;
92        }
93
94        let mut changed = false;
95        let (dst_row, src_row) = self.pick2_rows_mut(dst, src);
96        for (dst_word, src_word) in iter::zip(dst_row, &*src_row) {
97            let old = *dst_word;
98            let new = *dst_word | src_word;
99            *dst_word = new;
100            changed |= old != new;
101        }
102        changed
103    }
104
105    pub(super) fn get_reader(&self, ln: LiveNode, var: Variable) -> bool {
106        let (word, shift) = self.word_and_shift(ln, var);
107        (self.words[word] >> shift) & Self::RWU_READER != 0
108    }
109
110    pub(super) fn get_writer(&self, ln: LiveNode, var: Variable) -> bool {
111        let (word, shift) = self.word_and_shift(ln, var);
112        (self.words[word] >> shift) & Self::RWU_WRITER != 0
113    }
114
115    pub(super) fn get_used(&self, ln: LiveNode, var: Variable) -> bool {
116        let (word, shift) = self.word_and_shift(ln, var);
117        (self.words[word] >> shift) & Self::RWU_USED != 0
118    }
119
120    pub(super) fn get(&self, ln: LiveNode, var: Variable) -> RWU {
121        let (word, shift) = self.word_and_shift(ln, var);
122        let rwu_packed = self.words[word] >> shift;
123        RWU {
124            reader: rwu_packed & Self::RWU_READER != 0,
125            writer: rwu_packed & Self::RWU_WRITER != 0,
126            used: rwu_packed & Self::RWU_USED != 0,
127        }
128    }
129
130    pub(super) fn set(&mut self, ln: LiveNode, var: Variable, rwu: RWU) {
131        let mut packed = 0;
132        if rwu.reader {
133            packed |= Self::RWU_READER;
134        }
135        if rwu.writer {
136            packed |= Self::RWU_WRITER;
137        }
138        if rwu.used {
139            packed |= Self::RWU_USED;
140        }
141
142        let (word, shift) = self.word_and_shift(ln, var);
143        let word = &mut self.words[word];
144        *word = (*word & !(Self::RWU_MASK << shift)) | (packed << shift)
145    }
146}
rustc_passes/liveness/rwu_table.rs

rustc_passes/liveness/
rwu_table.rs
