Vendor import of llvm trunk r302418:vendor/llvm/llvm-trunk-r302418

https://llvm.org/svn/llvm-project/llvm/trunk@302418

1 files changed, 30 insertions, 3 deletions

diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 5aa101591e6e..e835f1516225 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -217,7 +217,7 @@ public:
     unsigned BitPos = Prev % BITWORD_SIZE;
     BitWord Copy = Bits[WordPos];
     // Mask off previous bits.
-    Copy &= ~0UL << BitPos;
+    Copy &= maskTrailingZeros<BitWord>(BitPos);
 
     if (Copy != 0)
       return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
@@ -229,7 +229,7 @@ public:
     return -1;
   }
 
-  /// find_next_unset - Returns the index of the next usnet bit following the
+  /// find_next_unset - Returns the index of the next unset bit following the
   /// "Prev" bit.  Returns -1 if all remaining bits are set.
   int find_next_unset(unsigned Prev) const {
     ++Prev;
@@ -253,7 +253,34 @@ public:
     return -1;
   }
 
-  /// clear - Clear all bits.
+  /// find_prev - Returns the index of the first set bit that precedes the
+  /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
+  int find_prev(unsigned PriorTo) {
+    if (PriorTo == 0)
+      return -1;
+
+    --PriorTo;
+
+    unsigned WordPos = PriorTo / BITWORD_SIZE;
+    unsigned BitPos = PriorTo % BITWORD_SIZE;
+    BitWord Copy = Bits[WordPos];
+    // Mask off next bits.
+    Copy &= maskTrailingOnes<BitWord>(BitPos + 1);
+
+    if (Copy != 0)
+      return (WordPos + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
+
+    // Check previous words.
+    for (unsigned i = 1; i <= WordPos; ++i) {
+      unsigned Index = WordPos - i;
+      if (Bits[Index] == 0)
+        continue;
+      return (Index + 1) * BITWORD_SIZE - countLeadingZeros(Bits[Index]) - 1;
+    }
+    return -1;
+  }
+
+  /// clear - Removes all bits from the bitvector. Does not change capacity.
   void clear() {
     Size = 0;
   }