compiler/rustc_passes/src/liveness/rwu_table.rs

   1 use crate::liveness::{LiveNode, Variable};
   2 use std::iter;
   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);
  95         for (dst_word, src_word) in iter::zip(dst_row, &*src_row) {
  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 }