]>
Commit | Line | Data |
---|---|---|
fc512014 | 1 | use crate::liveness::{LiveNode, Variable}; |
cdc7bbd5 | 2 | use std::iter; |
fc512014 XL |
3 | |
4 | #[derive(Clone, Copy)] | |
5 | pub(super) struct RWU { | |
6 | pub(super) reader: bool, | |
7 | pub(super) writer: bool, | |
8 | pub(super) used: bool, | |
9 | } | |
10 | ||
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. | |
15 | live_nodes: usize, | |
16 | /// Total number of variables. | |
17 | vars: usize, | |
18 | ||
19 | /// A compressed representation of `RWU`s. | |
20 | /// | |
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 | |
23 | /// padding bit. | |
24 | /// | |
25 | /// The data for each live node is contiguous and starts at a word boundary, | |
26 | /// so there might be an unused space left. | |
27 | words: Vec<u8>, | |
28 | /// Number of words per each live node. | |
29 | live_node_words: usize, | |
30 | } | |
31 | ||
32 | impl RWUTable { | |
33 | const RWU_READER: u8 = 0b0001; | |
34 | const RWU_WRITER: u8 = 0b0010; | |
35 | const RWU_USED: u8 = 0b0100; | |
36 | const RWU_MASK: u8 = 0b1111; | |
37 | ||
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; | |
44 | ||
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] } | |
48 | } | |
49 | ||
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); | |
53 | ||
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) | |
58 | } | |
59 | ||
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); | |
63 | assert!(a != b); | |
64 | ||
65 | let a_start = a.index() * self.live_node_words; | |
66 | let b_start = b.index() * self.live_node_words; | |
67 | ||
68 | unsafe { | |
69 | let ptr = self.words.as_mut_ptr(); | |
70 | ( | |
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), | |
73 | ) | |
74 | } | |
75 | } | |
76 | ||
77 | pub(super) fn copy(&mut self, dst: LiveNode, src: LiveNode) { | |
78 | if dst == src { | |
79 | return; | |
80 | } | |
81 | ||
82 | let (dst_row, src_row) = self.pick2_rows_mut(dst, src); | |
83 | dst_row.copy_from_slice(src_row); | |
84 | } | |
85 | ||
86 | /// Sets `dst` to the union of `dst` and `src`, returns true if `dst` was | |
87 | /// changed. | |
88 | pub(super) fn union(&mut self, dst: LiveNode, src: LiveNode) -> bool { | |
89 | if dst == src { | |
90 | return false; | |
91 | } | |
92 | ||
93 | let mut changed = false; | |
94 | let (dst_row, src_row) = self.pick2_rows_mut(dst, src); | |
cdc7bbd5 | 95 | for (dst_word, src_word) in iter::zip(dst_row, &*src_row) { |
fc512014 XL |
96 | let old = *dst_word; |
97 | let new = *dst_word | src_word; | |
98 | *dst_word = new; | |
99 | changed |= old != new; | |
100 | } | |
101 | changed | |
102 | } | |
103 | ||
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 | |
107 | } | |
108 | ||
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 | |
112 | } | |
113 | ||
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 | |
117 | } | |
118 | ||
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; | |
122 | RWU { | |
123 | reader: rwu_packed & Self::RWU_READER != 0, | |
124 | writer: rwu_packed & Self::RWU_WRITER != 0, | |
125 | used: rwu_packed & Self::RWU_USED != 0, | |
126 | } | |
127 | } | |
128 | ||
129 | pub(super) fn set(&mut self, ln: LiveNode, var: Variable, rwu: RWU) { | |
130 | let mut packed = 0; | |
131 | if rwu.reader { | |
132 | packed |= Self::RWU_READER; | |
133 | } | |
134 | if rwu.writer { | |
135 | packed |= Self::RWU_WRITER; | |
136 | } | |
137 | if rwu.used { | |
138 | packed |= Self::RWU_USED; | |
139 | } | |
140 | ||
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) | |
144 | } | |
145 | } |