1 use crate::liveness::{LiveNode, Variable};
5 pub(super) struct RWU {
6 pub(super) reader: bool,
7 pub(super) writer: bool,
11 /// Conceptually, this is like a `Vec<Vec<RWU>>`. But the number of
12 /// RWU`s can get very large, so it uses a more compact representation.
13 pub(super) struct RWUTable {
14 /// Total number of live nodes.
16 /// Total number of variables.
19 /// A compressed representation of `RWU`s.
21 /// Each word represents 2 different `RWU`s packed together. Each packed RWU
22 /// is stored in 4 bits: a reader bit, a writer bit, a used bit and a
25 /// The data for each live node is contiguous and starts at a word boundary,
26 /// so there might be an unused space left.
28 /// Number of words per each live node.
29 live_node_words: usize,
33 const RWU_READER: u8 = 0b0001;
34 const RWU_WRITER: u8 = 0b0010;
35 const RWU_USED: u8 = 0b0100;
36 const RWU_MASK: u8 = 0b1111;
38 /// Size of packed RWU in bits.
39 const RWU_BITS: usize = 4;
40 /// Size of a word in bits.
41 const WORD_BITS: usize = std::mem::size_of::<u8>() * 8;
42 /// Number of packed RWUs that fit into a single word.
43 const WORD_RWU_COUNT: usize = Self::WORD_BITS / Self::RWU_BITS;
45 pub(super) fn new(live_nodes: usize, vars: usize) -> RWUTable {
46 let live_node_words = (vars + Self::WORD_RWU_COUNT - 1) / Self::WORD_RWU_COUNT;
47 Self { live_nodes, vars, live_node_words, words: vec![0u8; live_node_words * live_nodes] }
50 fn word_and_shift(&self, ln: LiveNode, var: Variable) -> (usize, u32) {
51 assert!(ln.index() < self.live_nodes);
52 assert!(var.index() < self.vars);
54 let var = var.index();
55 let word = var / Self::WORD_RWU_COUNT;
56 let shift = Self::RWU_BITS * (var % Self::WORD_RWU_COUNT);
57 (ln.index() * self.live_node_words + word, shift as u32)
60 fn pick2_rows_mut(&mut self, a: LiveNode, b: LiveNode) -> (&mut [u8], &mut [u8]) {
61 assert!(a.index() < self.live_nodes);
62 assert!(b.index() < self.live_nodes);
65 let a_start = a.index() * self.live_node_words;
66 let b_start = b.index() * self.live_node_words;
69 let ptr = self.words.as_mut_ptr();
71 std::slice::from_raw_parts_mut(ptr.add(a_start), self.live_node_words),
72 std::slice::from_raw_parts_mut(ptr.add(b_start), self.live_node_words),
77 pub(super) fn copy(&mut self, dst: LiveNode, src: LiveNode) {
82 let (dst_row, src_row) = self.pick2_rows_mut(dst, src);
83 dst_row.copy_from_slice(src_row);
86 /// Sets `dst` to the union of `dst` and `src`, returns true if `dst` was
88 pub(super) fn union(&mut self, dst: LiveNode, src: LiveNode) -> bool {
93 let mut changed = false;
94 let (dst_row, src_row) = self.pick2_rows_mut(dst, src);
95 for (dst_word, src_word) in iter::zip(dst_row, &*src_row) {
97 let new = *dst_word | src_word;
99 changed |= old != new;
104 pub(super) fn get_reader(&self, ln: LiveNode, var: Variable) -> bool {
105 let (word, shift) = self.word_and_shift(ln, var);
106 (self.words[word] >> shift) & Self::RWU_READER != 0
109 pub(super) fn get_writer(&self, ln: LiveNode, var: Variable) -> bool {
110 let (word, shift) = self.word_and_shift(ln, var);
111 (self.words[word] >> shift) & Self::RWU_WRITER != 0
114 pub(super) fn get_used(&self, ln: LiveNode, var: Variable) -> bool {
115 let (word, shift) = self.word_and_shift(ln, var);
116 (self.words[word] >> shift) & Self::RWU_USED != 0
119 pub(super) fn get(&self, ln: LiveNode, var: Variable) -> RWU {
120 let (word, shift) = self.word_and_shift(ln, var);
121 let rwu_packed = self.words[word] >> shift;
123 reader: rwu_packed & Self::RWU_READER != 0,
124 writer: rwu_packed & Self::RWU_WRITER != 0,
125 used: rwu_packed & Self::RWU_USED != 0,
129 pub(super) fn set(&mut self, ln: LiveNode, var: Variable, rwu: RWU) {
132 packed |= Self::RWU_READER;
135 packed |= Self::RWU_WRITER;
138 packed |= Self::RWU_USED;
141 let (word, shift) = self.word_and_shift(ln, var);
142 let word = &mut self.words[word];
143 *word = (*word & !(Self::RWU_MASK << shift)) | (packed << shift)