Auto merge of #52335 - nnethercote:BitSlice-fixes, r=nikomatsakis

`BitSlice` fixes

`propagate_bits_into_entry_set_for` and `BitSlice::bitwise` are hot for some benchmarks under NLL. I tried and failed to speed them up. (Increasing the size of `bit_slice::Word` from `usize` to `u128` caused a slowdown, even though decreasing the size of `bitvec::Word` from `u128` to `u64` also caused a slowdown. Weird.)

Anyway, along the way I fixed up several problems in and around the `BitSlice` code.

r? @nikomatsakis

1 files changed, 11 insertions, 17 deletions

diff --git a/src/librustc_data_structures/bitslice.rs b/src/librustc_data_structures/bitslice.rs
index 2678861be06..79435aa3987 100644
--- a/src/librustc_data_structures/bitslice.rs
+++ b/src/librustc_data_structures/bitslice.rs
@@ -28,9 +28,9 @@ impl BitSlice for [Word] {
     fn clear_bit(&mut self, idx: usize) -> bool {
         let words = self;
         debug!("clear_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
+               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
         let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
-        debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
+        debug!("word={} bit_in_word={} bit_mask=0x{:x}", word, bit_in_word, bit_mask);
         let oldv = words[word];
         let newv = oldv & !bit_mask;
         words[word] = newv;
@@ -42,7 +42,7 @@ impl BitSlice for [Word] {
     fn set_bit(&mut self, idx: usize) -> bool {
         let words = self;
         debug!("set_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
+               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
         let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
         debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
         let oldv = words[word];
@@ -78,13 +78,6 @@ fn bit_lookup(bit: usize) -> BitLookup {
     BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask }
 }
 
-
-fn bit_str(bit: Word) -> String {
-    let byte = bit >> 3;
-    let lobits = 1 << (bit & 0b111);
-    format!("[{}:{}-{:02x}]", bit, byte, lobits)
-}
-
 pub fn bits_to_string(words: &[Word], bits: usize) -> String {
     let mut result = String::new();
     let mut sep = '[';
@@ -95,7 +88,7 @@ pub fn bits_to_string(words: &[Word], bits: usize) -> String {
     let mut i = 0;
     for &word in words.iter() {
         let mut v = word;
-        loop { // for each byte in `v`:
+        for _ in 0..mem::size_of::<Word>() { // for each byte in `v`:
             let remain = bits - i;
             // If less than a byte remains, then mask just that many bits.
             let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
@@ -110,14 +103,15 @@ pub fn bits_to_string(words: &[Word], bits: usize) -> String {
             i += 8;
             sep = '-';
         }
+        sep = '|';
     }
     result.push(']');
     return result
 }
 
 #[inline]
-pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
-                                   in_vec: &[usize],
+pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [Word],
+                                   in_vec: &[Word],
                                    op: &Op) -> bool {
     assert_eq!(out_vec.len(), in_vec.len());
     let mut changed = false;
@@ -132,21 +126,21 @@ pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
 
 pub trait BitwiseOperator {
     /// Applies some bit-operation pointwise to each of the bits in the two inputs.
-    fn join(&self, pred1: usize, pred2: usize) -> usize;
+    fn join(&self, pred1: Word, pred2: Word) -> Word;
 }
 
 pub struct Intersect;
 impl BitwiseOperator for Intersect {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a & b }
+    fn join(&self, a: Word, b: Word) -> Word { a & b }
 }
 pub struct Union;
 impl BitwiseOperator for Union {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a | b }
+    fn join(&self, a: Word, b: Word) -> Word { a | b }
 }
 pub struct Subtract;
 impl BitwiseOperator for Subtract {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a & !b }
+    fn join(&self, a: Word, b: Word) -> Word { a & !b }
 }