BitVector: add iterators for bits that are set

[thegameg]

Summary

Add iterators to iterate on the bits of the bit vector that are set. This is useful when BitVector is used as a set<unsigned>, which usually is a set of basic block numbers or a set of registers.

D30808 would be a user of this.

This would allow us to transform:

for (int Elt = Vector.find_first(); Elt >= 0; Elt = Vector.find_next(Elt)) {
  // Stuff
}

into

for (int Elt : Vector.bits_set()) {
  // Stuff
}

[MatzeB]

Thanks for working on this. I missed this feature myself a couple of times.

We generally do not commit unused code, so before commit this we have to wait until one of the shrink-wrapping patches is accepted. Or you go around llvm and try to find a few find_next() users that can be replaced with a range based for.

include/llvm/ADT/BitVector.h

123–124

You should probably pull this out of the class, as it doesn't use any private methods and is used not just by BitVector but also by SmallBitVector.

125

Does this ever make sense to be nullptr? I'd recommend using a reference.

131

I'd recommend an explicit modifier here.

135–138

This can be private.

151

We have size_type BitVector::size() or BitVector::set(unsigned Idx). We seem to be a bit inconsistent regarding size_type vs. unsigned but the majority of functions appear to be using unsigned for bit indexes so this should be the return type here.

152

Is it necessary to make this accessible? Having access to the parent bitvector seems like an implementation detail to me that could stay private.

155–162

This could be more consistent: const_bits_set_iterator, bit_set_begin() and bit_set().

158–159

http://llvm.org/docs/CodingStandards.html#do-not-use-braced-initializer-lists-to-call-a-constructor recommends against calling constructors with curly braces.

679–693

Isn't it possible to move those into the iterator class?

unittests/ADT/BitVectorTest.cpp

514

How about EXPECT_TRUE(false); to make it more obvious?

526–533

Maybe construct an array {1,10,99,25} that you verify against during the iteration to make sure we do indeed return the right numbers?

[MatzeB]

Adding a few reviewers who often have comments on ADT changes.

[thegameg]

Thanks Matthias for the review.

[thegameg]

Fixl typo in unit tests.

[MatzeB]

include/llvm/ADT/SmallBitVector.h

139–144

This is still inconsistent bits_set vs. bit_set.

[thegameg]

Updated some passes to use this.

[thegameg]

Better name for the iterator range.
Fix typo.

[MatzeB]

This is looking pretty good, but I'd expect the range based for loops to use the same type as operator() of operator*(), i.e. `for (unsigned Bit : Empty.set_bits()) {}.

[thegameg]

int -> unsigned.

[MatzeB]

LGTM

include/llvm/ADT/BitVector.h

 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the BitVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_BITVECTOR_H
 #define LLVM_ADT_BITVECTOR_H
 
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <utility>
 
 namespace llvm {
 
+/// ForwardIterator for the bits that are set.
+/// Iterators get invalidated when resize / reserve is called.
+template <typename BitVectorT> class const_bit_set_iterator_impl {
+  const BitVectorT &Parent;
+  int Current = 0;
+
+  void advance() {
+    assert(Current != -1 && "Trying to advance past end.");
+    Current = Parent.find_next(Current);
+  }
+
+public:
+  const_bit_set_iterator_impl(const BitVectorT &Parent, int Current)
+      : Parent(Parent), Current(Current) {}
+  explicit const_bit_set_iterator_impl(const BitVectorT &Parent)
+      : const_bit_set_iterator_impl(Parent, Parent.find_first()) {}
+  const_bit_set_iterator_impl(const const_bit_set_iterator_impl &) = default;
+
+  const_bit_set_iterator_impl operator++(int) {
+    auto Prev = *this;
+    advance();
+    return Prev;
+  }
+
+  const_bit_set_iterator_impl &operator++() {
+    advance();
+    return *this;
+  }
+
+  unsigned operator*() const { return Current; }
+
+  bool operator==(const const_bit_set_iterator_impl &Other) const {
+    assert(&Parent == &Other.Parent &&
+           "Comparing iterators from different BitVectors");
+    return Current == Other.Current;
+  }
+
+  bool operator!=(const const_bit_set_iterator_impl &Other) const {
+    assert(&Parent == &Other.Parent &&
+           "Comparing iterators from different BitVectors");
+    return Current != Other.Current;
+  }
+};
+
 class BitVector {
   typedef unsigned long BitWord;
 
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
reference& operator=(bool t) {
       return *this;
     }
 
     operator bool() const {
       return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
     }
   };
 
+  typedef const_bit_set_iterator_impl<BitVector> const_bit_set_iterator;
+  typedef const_bit_set_iterator set_iterator;
+
+  const_bit_set_iterator bit_set_begin() const {
+    return const_bit_set_iterator(*this);
+  }
+  const_bit_set_iterator bit_set_end() const {
+    return const_bit_set_iterator(*this, -1);
+  }
+  iterator_range<const_bit_set_iterator> bit_set() const {
+    return make_range(bit_set_begin(), bit_set_end());
+  }
 
   /// BitVector default ctor - Creates an empty bitvector.
   BitVector() : Size(0), Capacity(0) {
     Bits = nullptr;
   }
 
   /// BitVector ctor - Creates a bitvector of specified number of bits. All
   /// bits are initialized to the specified value.
   explicit BitVector(unsigned s, bool t = false) : Size(s) {
     Capacity = NumBitWords(s);
     Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
     init_words(Bits, Capacity, t);
     if (t)
       clear_unused_bits();
   }
 
   /// BitVector copy ctor.
   BitVector(const BitVector &RHS) : Size(RHS.size()) {
     if (Size == 0) {
       Bits = nullptr;
       Capacity = 0;
       return;
     }
 
     Capacity = NumBitWords(RHS.size());
     Bits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
     std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
   }
 
   BitVector(BitVector &&RHS)
     : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) {
     RHS.Bits = nullptr;
     RHS.Size = RHS.Capacity = 0;
   }
 
   ~BitVector() {
     std::free(Bits);
   }
public:
   /// Return the size (in bytes) of the bit vector.
   size_t getMemorySize() const { return Capacity * sizeof(BitWord); }
 };
 
 static inline size_t capacity_in_bytes(const BitVector &X) {
   return X.getMemorySize();
 }
 
 } // end namespace llvm
 
 namespace std {
   /// Implement std::swap in terms of BitVector swap.
   inline void
   swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
     LHS.swap(RHS);
   }
 } // end namespace std
 
 #endif // LLVM_ADT_BITVECTOR_H

include/llvm/ADT/SmallBitVector.h

private:
   }
 
   void setSmallBits(uintptr_t NewBits) {
     setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
                     (getSmallSize() << SmallNumDataBits));
   }
 
 public:
+  typedef const_bit_set_iterator_impl<SmallBitVector> const_bit_set_iterator;
+  typedef const_bit_set_iterator set_iterator;
+
+  const_bit_set_iterator bit_set_begin() const {
+    return const_bit_set_iterator(*this);
+  }
+  const_bit_set_iterator bit_set_end() const {
+    return const_bit_set_iterator(*this, -1);
+  }
+  iterator_range<const_bit_set_iterator> bit_set() const {
+    return make_range(bit_set_begin(), bit_set_end());
+  }
+
   /// Creates an empty bitvector.
   SmallBitVector() : X(1) {}
 
   /// Creates a bitvector of specified number of bits. All bits are initialized
   /// to the specified value.
   explicit SmallBitVector(unsigned s, bool t = false) {
     if (s <= SmallNumDataBits)
       switchToSmall(t ? ~uintptr_t(0) : 0, s);

lib/Analysis/DependenceAnalysis.cpp

 //            Practical Dependence Testing
 //            Goff, Kennedy, Tseng
 //            PLDI 1991
 bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
                                SmallBitVector &Loops,
                                SmallVectorImpl<Constraint> &Constraints,
                                bool &Consistent) {
   bool Result = false;
-  for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) {
+  for (int LI : Loops.bit_set()) {
     DEBUG(dbgs() << "\t    Constraint[" << LI << "] is");
     DEBUG(Constraints[LI].dump(dbgs()));
     if (Constraints[LI].isDistance())
       Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
     else if (Constraints[LI].isLine())
       Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
     else if (Constraints[LI].isPoint())
       Result |= propagatePoint(Src, Dst, Constraints[LI]);

 }
 
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
 // For debugging purposes, dump a small bit vector to dbgs().
 static void dumpSmallBitVector(SmallBitVector &BV) {
   dbgs() << "{";
-  for (int VI = BV.find_first(); VI >= 0; VI = BV.find_next(VI)) {
+  for (int VI : BV.bit_set()) {
     dbgs() << VI;
     if (BV.find_next(VI) >= 0)
       dbgs() << ' ';
   }
   dbgs() << "}\n";
 }
 #endif
 
DependenceInfo::depends(Instruction *Src, Instruction *Dst,
   DEBUG(dumpSmallBitVector(Separable));
   DEBUG(dbgs() << "    Coupled = ");
   DEBUG(dumpSmallBitVector(Coupled));
 
   Constraint NewConstraint;
   NewConstraint.setAny(SE);
 
   // test separable subscripts
-  for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) {
+  for (int SI : Separable.bit_set()) {
     DEBUG(dbgs() << "testing subscript " << SI);
     switch (Pair[SI].Classification) {
     case Subscript::ZIV:
       DEBUG(dbgs() << ", ZIV\n");
       if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
         return nullptr;
       break;
     case Subscript::SIV: {
DependenceInfo::depends(Instruction *Src, Instruction *Dst,
 
   if (Coupled.count()) {
     // test coupled subscript groups
     DEBUG(dbgs() << "starting on coupled subscripts\n");
     DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n");
     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
     for (unsigned II = 0; II <= MaxLevels; ++II)
       Constraints[II].setAny(SE);
-    for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) {
+    for (int SI : Coupled.bit_set()) {
       DEBUG(dbgs() << "testing subscript group " << SI << " { ");
       SmallBitVector Group(Pair[SI].Group);
       SmallBitVector Sivs(Pairs);
       SmallBitVector Mivs(Pairs);
       SmallBitVector ConstrainedLevels(MaxLevels + 1);
       SmallVector<Subscript *, 4> PairsInGroup;
-      for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) {
+      for (int SJ : Group.bit_set()) {
         DEBUG(dbgs() << SJ << " ");
         if (Pair[SJ].Classification == Subscript::SIV)
           Sivs.set(SJ);
         else
           Mivs.set(SJ);
         PairsInGroup.push_back(&Pair[SJ]);
       }
       unifySubscriptType(PairsInGroup);
       DEBUG(dbgs() << "}\n");
       while (Sivs.any()) {
         bool Changed = false;
-        for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
+        for (int SJ : Sivs.bit_set()) {
           DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
           // SJ is an SIV subscript that's part of the current coupled group
           unsigned Level;
           const SCEV *SplitIter = nullptr;
           DEBUG(dbgs() << "SIV\n");
           if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
                       SplitIter))
             return nullptr;
           ConstrainedLevels.set(Level);
           if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
             if (Constraints[Level].isEmpty()) {
               ++DeltaIndependence;
               return nullptr;
             }
             Changed = true;
           }
           Sivs.reset(SJ);
         }
         if (Changed) {
           // propagate, possibly creating new SIVs and ZIVs
           DEBUG(dbgs() << "    propagating\n");
           DEBUG(dbgs() << "\tMivs = ");
           DEBUG(dumpSmallBitVector(Mivs));
-          for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
+          for (int SJ : Mivs.bit_set()) {
             // SJ is an MIV subscript that's part of the current coupled group
             DEBUG(dbgs() << "\tSJ = " << SJ << "\n");
             if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
                           Constraints, Result.Consistent)) {
               DEBUG(dbgs() << "\t    Changed\n");
               ++DeltaPropagations;
               Pair[SJ].Classification =
                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
for (int SI : Coupled.bit_set()) {
                 llvm_unreachable("bad subscript classification");
               }
             }
           }
         }
       }
 
       // test & propagate remaining RDIVs
-      for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
+      for (int SJ : Mivs.bit_set()) {
         if (Pair[SJ].Classification == Subscript::RDIV) {
           DEBUG(dbgs() << "RDIV test\n");
           if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
             return nullptr;
           // I don't yet understand how to propagate RDIV results
           Mivs.reset(SJ);
         }
       }
 
       // test remaining MIVs
       // This code is temporary.
       // Better to somehow test all remaining subscripts simultaneously.
-      for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
+      for (int SJ : Mivs.bit_set()) {
         if (Pair[SJ].Classification == Subscript::MIV) {
           DEBUG(dbgs() << "MIV test\n");
           if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
             return nullptr;
         }
         else
           llvm_unreachable("expected only MIV subscripts at this point");
       }
 
       // update Result.DV from constraint vector
       DEBUG(dbgs() << "    updating\n");
-      for (int SJ = ConstrainedLevels.find_first(); SJ >= 0;
-           SJ = ConstrainedLevels.find_next(SJ)) {
+      for (int SJ : ConstrainedLevels.bit_set()) {
         if (SJ > (int)CommonLevels)
           break;
         updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
         if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
           return nullptr;
       }
     }
   }
else {
       }
     }
   }
 
   Constraint NewConstraint;
   NewConstraint.setAny(SE);
 
   // test separable subscripts
-  for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) {
+  for (int SI : Separable.bit_set()) {
     switch (Pair[SI].Classification) {
     case Subscript::SIV: {
       unsigned Level;
       const SCEV *SplitIter = nullptr;
       (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
                      Result, NewConstraint, SplitIter);
       if (Level == SplitLevel) {
         assert(SplitIter != nullptr);
for (int SI : Separable.bit_set()) {
     }
   }
 
   if (Coupled.count()) {
     // test coupled subscript groups
     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
     for (unsigned II = 0; II <= MaxLevels; ++II)
       Constraints[II].setAny(SE);
-    for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) {
+    for (int SI : Coupled.bit_set()) {
       SmallBitVector Group(Pair[SI].Group);
       SmallBitVector Sivs(Pairs);
       SmallBitVector Mivs(Pairs);
       SmallBitVector ConstrainedLevels(MaxLevels + 1);
-      for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) {
+      for (int SJ : Group.bit_set()) {
         if (Pair[SJ].Classification == Subscript::SIV)
           Sivs.set(SJ);
         else
           Mivs.set(SJ);
       }
       while (Sivs.any()) {
         bool Changed = false;
-        for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
+        for (int SJ : Sivs.bit_set()) {
           // SJ is an SIV subscript that's part of the current coupled group
           unsigned Level;
           const SCEV *SplitIter = nullptr;
           (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
                          Result, NewConstraint, SplitIter);
           if (Level == SplitLevel && SplitIter)
             return SplitIter;
           ConstrainedLevels.set(Level);
           if (intersectConstraints(&Constraints[Level], &NewConstraint))
             Changed = true;
           Sivs.reset(SJ);
         }
         if (Changed) {
           // propagate, possibly creating new SIVs and ZIVs
-          for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
+          for (int SJ : Mivs.bit_set()) {
             // SJ is an MIV subscript that's part of the current coupled group
             if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
                           Pair[SJ].Loops, Constraints, Result.Consistent)) {
               Pair[SJ].Classification =
                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
                              Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
                              Pair[SJ].Loops);
               switch (Pair[SJ].Classification) {

lib/CodeGen/AggressiveAntiDepBreaker.cpp

for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) {
     BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]);
     if (CriticalPathSet.none())
       CriticalPathSet = CPSet;
     else
       CriticalPathSet |= CPSet;
    }
 
   DEBUG(dbgs() << "AntiDep Critical-Path Registers:");
-  DEBUG(for (int r = CriticalPathSet.find_first(); r != -1;
-             r = CriticalPathSet.find_next(r))
+  DEBUG(for (int r : CriticalPathSet.bit_set())
           dbgs() << " " << TRI->getName(r));
   DEBUG(dbgs() << '\n');
 }
 
 AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() {
   delete State;
 }
 
if (RegRefs.count(Reg) > 0) {
       DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":");
 
       BitVector &BV = RenameRegisterMap[Reg];
       assert(BV.empty());
       BV = GetRenameRegisters(Reg);
 
       DEBUG({
         dbgs() << " ::";
-        for (int r = BV.find_first(); r != -1; r = BV.find_next(r))
+        for (int r : BV.bit_set())
           dbgs() << " " << TRI->getName(r);
         dbgs() << "\n";
       });
     }
   }
 
   // All group registers should be a subreg of SuperReg.
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {

lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp

for (const auto &MI : MBB) {
               for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid();
                    ++AI)
                 if (ChangingRegs.test(*AI))
                   clobberRegisterUses(RegVars, *AI, Result, MI);
             }
           } else if (MO.isRegMask()) {
             // If this is a register mask operand, clobber all debug values in
             // non-CSRs.
-            for (int I = ChangingRegs.find_first(); I != -1;
-                 I = ChangingRegs.find_next(I)) {
+            for (int I : ChangingRegs.bit_set()) {
               // Don't consider SP to be clobbered by register masks.
               if (unsigned(I) != SP && TRI->isPhysicalRegister(I) &&
                   MO.clobbersPhysReg(I)) {
                 clobberRegisterUses(RegVars, I, Result, MI);
               }
             }
           }
         }

lib/CodeGen/MachineVerifier.cpp

for (const auto &LI : MBB->liveins()) {
            SubRegs.isValid(); ++SubRegs)
         regsLive.insert(*SubRegs);
     }
   }
   regsLiveInButUnused = regsLive;
 
   const MachineFrameInfo &MFI = MF->getFrameInfo();
   BitVector PR = MFI.getPristineRegs(*MF);
-  for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
+  for (int I : PR.bit_set()) {
     for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
          SubRegs.isValid(); ++SubRegs)
       regsLive.insert(*SubRegs);
   }
 
   regsKilled.clear();
   regsDefined.clear();
 

lib/CodeGen/RegAllocGreedy.cpp

void reset(InterferenceCache &Cache, unsigned Reg) {
       Intf.setPhysReg(Cache, Reg);
       LiveBundles.clear();
       ActiveBlocks.clear();
     }
 
     // Set B[i] = C for every live bundle where B[i] was NoCand.
     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
       unsigned Count = 0;
-      for (int i = LiveBundles.find_first(); i >= 0;
-           i = LiveBundles.find_next(i))
+      for (int i : LiveBundles.bit_set())
         if (B[i] == NoCand) {
           B[i] = C;
           Count++;
         }
       return Count;
     }
   };
 
bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
   SpillPlacer->finish();
 
   if (!Cand.LiveBundles.any()) {
     DEBUG(dbgs() << ", none.\n");
     return false;
   }
 
   DEBUG({
-    for (int i = Cand.LiveBundles.find_first(); i>=0;
-         i = Cand.LiveBundles.find_next(i))
+    for (int i : Cand.LiveBundles.bit_set())
       dbgs() << " EB#" << i;
     dbgs() << ".\n";
   });
   return true;
 }
 
 /// calcSpillCost - Compute how expensive it would be to split the live range in
 /// SA around all use blocks instead of forming bundle regions.
 BlockFrequency RAGreedy::calcSpillCost() {
if (!Cand.LiveBundles.any()) {
       DEBUG(dbgs() << " no bundles.\n");
       continue;
     }
 
     Cost += calcGlobalSplitCost(Cand);
     DEBUG({
       dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost)
                                 << " with bundles";
-      for (int i = Cand.LiveBundles.find_first(); i>=0;
-           i = Cand.LiveBundles.find_next(i))
+      for (int i : Cand.LiveBundles.bit_set())
         dbgs() << " EB#" << i;
       dbgs() << ".\n";
     });
     if (Cost < BestCost) {
       BestCand = NumCands;
       BestCost = Cost;
     }
     ++NumCands;

lib/CodeGen/SpillPlacement.cpp

for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
     BlockFrequency Freq = BlockFrequencies[Number];
     nodes[ib].addLink(ob, Freq);
     nodes[ob].addLink(ib, Freq);
   }
 }
 
 bool SpillPlacement::scanActiveBundles() {
   RecentPositive.clear();
-  for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
+  for (int n : ActiveNodes->bit_set()) {
     update(n);
     // A node that must spill, or a node without any links is not going to
     // change its value ever again, so exclude it from iterations.
     if (nodes[n].mustSpill())
       continue;
     if (nodes[n].preferReg())
       RecentPositive.push_back(n);
   }

 }
 
 bool
 SpillPlacement::finish() {
   assert(ActiveNodes && "Call prepare() first");
 
   // Write preferences back to ActiveNodes.
   bool Perfect = true;
-  for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
+  for (int n : ActiveNodes->bit_set())
     if (!nodes[n].preferReg()) {
       ActiveNodes->reset(n);
       Perfect = false;
     }
   ActiveNodes = nullptr;
   return Perfect;
 }

lib/CodeGen/StackColoring.cpp

for (const MachineInstr &MI : MBB) {
           if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex)
             Finishes[Slot] = ThisIndex;
         }
       }
     }
 
     // Create the interval of the blocks that we previously found to be 'alive'.
     BlockLifetimeInfo &MBBLiveness = BlockLiveness[&MBB];
-    for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
-         pos = MBBLiveness.LiveIn.find_next(pos)) {
+    for (int pos : MBBLiveness.LiveIn.bit_set()) {
       Starts[pos] = Indexes->getMBBStartIdx(&MBB);
     }
-    for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1;
-         pos = MBBLiveness.LiveOut.find_next(pos)) {
+    for (int pos : MBBLiveness.LiveOut.bit_set()) {
       Finishes[pos] = Indexes->getMBBEndIdx(&MBB);
     }
 
     for (unsigned i = 0; i < NumSlots; ++i) {
       //
       // When LifetimeStartOnFirstUse is turned on, data flow analysis
       // is forward (from starts to ends), not bidirectional. A
       // consequence of this is that we can wind up in situations

lib/CodeGen/TargetLoweringBase.cpp

TargetLoweringBase::findRepresentativeClass(const TargetRegisterInfo *TRI,
 
   // Compute the set of all super-register classes.
   BitVector SuperRegRC(TRI->getNumRegClasses());
   for (SuperRegClassIterator RCI(RC, TRI); RCI.isValid(); ++RCI)
     SuperRegRC.setBitsInMask(RCI.getMask());
 
   // Find the first legal register class with the largest spill size.
   const TargetRegisterClass *BestRC = RC;
-  for (int i = SuperRegRC.find_first(); i >= 0; i = SuperRegRC.find_next(i)) {
+  for (int i : SuperRegRC.bit_set()) {
     const TargetRegisterClass *SuperRC = TRI->getRegClass(i);
     // We want the largest possible spill size.
     if (SuperRC->getSize() <= BestRC->getSize())
       continue;
     if (!isLegalRC(SuperRC))
       continue;
     BestRC = SuperRC;
   }

lib/CodeGen/TargetRegisterInfo.cpp

void TargetRegisterInfo::markSuperRegs(BitVector &RegisterSet, unsigned Reg)
   for (MCSuperRegIterator AI(Reg, this, true); AI.isValid(); ++AI)
     RegisterSet.set(*AI);
 }
 
 bool TargetRegisterInfo::checkAllSuperRegsMarked(const BitVector &RegisterSet,
     ArrayRef<MCPhysReg> Exceptions) const {
   // Check that all super registers of reserved regs are reserved as well.
   BitVector Checked(getNumRegs());
-  for (int Reg = RegisterSet.find_first(); Reg>=0;
-       Reg = RegisterSet.find_next(Reg)) {
+  for (int Reg : RegisterSet.bit_set()) {
     if (Checked[Reg])
       continue;
     for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) {
       if (!RegisterSet[*SR] && !is_contained(Exceptions, Reg)) {
         dbgs() << "Error: Super register " << PrintReg(*SR, this)
                << " of reserved register " << PrintReg(Reg, this)
                << " is not reserved.\n";
         return false;

lib/Target/AArch64/AArch64FrameLowering.cpp

if (produceCompactUnwindFrame(MF) && !SavedRegs.test(PairedReg)) {
       SavedRegs.set(PairedReg);
       if (AArch64::GPR64RegClass.contains(PairedReg) &&
           !RegInfo->isReservedReg(MF, PairedReg))
         ExtraCSSpill = true;
     }
   }
 
   DEBUG(dbgs() << "*** determineCalleeSaves\nUsed CSRs:";
-        for (int Reg = SavedRegs.find_first(); Reg != -1;
-             Reg = SavedRegs.find_next(Reg))
+        for (int Reg : SavedRegs.bit_set())
           dbgs() << ' ' << PrintReg(Reg, RegInfo);
         dbgs() << "\n";);
 
   // If any callee-saved registers are used, the frame cannot be eliminated.
   unsigned NumRegsSpilled = SavedRegs.count();
   bool CanEliminateFrame = NumRegsSpilled == 0;
 
   // FIXME: Set BigStack if any stack slot references may be out of range.

lib/Target/ARM/Thumb1FrameLowering.cpp

bool Thumb1FrameLowering::emitPopSpecialFixUp(MachineBasicBlock &MBB,
   // Rebuild the GPRs from the high registers because they are removed
   // form the GPR reg class for thumb1.
   BitVector GPRsNoLRSP =
       TRI->getAllocatableSet(MF, TRI->getRegClass(ARM::hGPRRegClassID));
   GPRsNoLRSP |= PopFriendly;
   GPRsNoLRSP.reset(ARM::LR);
   GPRsNoLRSP.reset(ARM::SP);
   GPRsNoLRSP.reset(ARM::PC);
-  for (int Register = GPRsNoLRSP.find_first(); Register != -1;
-       Register = GPRsNoLRSP.find_next(Register)) {
+  for (int Register : GPRsNoLRSP.bit_set()) {
     if (!UsedRegs.contains(Register)) {
       // Remember the first pop-friendly register and exit.
       if (PopFriendly.test(Register)) {
         PopReg = Register;
         TemporaryReg = 0;
         break;
       }
       // Otherwise, remember that the register will be available to

lib/Target/Mips/MipsDelaySlotFiller.cpp

for (MCRegAliasIterator AI(*R, &TRI, true); AI.isValid(); ++AI)
       CallerSavedRegs.reset(*AI);
 
   Defs |= CallerSavedRegs;
 }
 
 void RegDefsUses::setUnallocatableRegs(const MachineFunction &MF) {
   BitVector AllocSet = TRI.getAllocatableSet(MF);
 
-  for (int R = AllocSet.find_first(); R != -1; R = AllocSet.find_next(R))
+  for (int R : AllocSet.bit_set())
     for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI)
       AllocSet.set(*AI);
 
   AllocSet.set(Mips::ZERO);
   AllocSet.set(Mips::ZERO_64);
 
   Defs |= AllocSet.flip();
 }

lib/Target/WebAssembly/WebAssemblyRegColoring.cpp

bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
   for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) {
     LiveInterval *LI = SortedIntervals[i];
     unsigned Old = LI->reg;
     size_t Color = i;
     const TargetRegisterClass *RC = MRI->getRegClass(Old);
 
     // Check if it's possible to reuse any of the used colors.
     if (!MRI->isLiveIn(Old))
-      for (int C(UsedColors.find_first()); C != -1;
-           C = UsedColors.find_next(C)) {
+      for (int C : UsedColors) {
         if (MRI->getRegClass(SortedIntervals[C]->reg) != RC)
           continue;
         for (LiveInterval *OtherLI : Assignments[C])
           if (!OtherLI->empty() && OtherLI->overlaps(*LI))
             goto continue_outer;
         Color = C;
         break;
       continue_outer:;

lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end();
                          2)
       };
       for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) {
         ImmMapTy::const_iterator M = OtherImms[i];
         if (M == J || M == JE) continue;
 
         // Compute the difference between the two.
         int64_t Imm = (uint64_t)JImm - M->first;
-        for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1;
-             LUIdx = UsedByIndices.find_next(LUIdx))
+        for (int LUIdx : UsedByIndices.bit_set())
           // Make a memo of this use, offset, and register tuple.
           if (UniqueItems.insert(std::make_pair(LUIdx, Imm)).second)
             WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg));
       }
     }
   }
 
   Map.clear();

lib/Transforms/Scalar/NewGVN.cpp

if (FirstInstr == -1)
     return;
   BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
   while (TouchedInstructions.any()) {
     ++Iterations;
     // Walk through all the instructions in all the blocks in RPO.
     // TODO: As we hit a new block, we should push and pop equalities into a
     // table lookupOperandLeader can use, to catch things PredicateInfo
     // might miss, like edge-only equivalences.
-    for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
-         InstrNum = TouchedInstructions.find_next(InstrNum)) {
+    for (int InstrNum : TouchedInstructions.bit_set()) {
 
       // This instruction was found to be dead. We don't bother looking
       // at it again.
       if (InstrNum == 0) {
         TouchedInstructions.reset(InstrNum);
         continue;
       }
 

unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, EmptyVector) {
   E = A;
   testEmpty(E);
 
   TypeParam F;
   E.reset(A);
   testEmpty(E);
 }
 
+TYPED_TEST(BitVectorTest, Iterators) {
+  TypeParam Filled(10, true);
+  EXPECT_NE(Filled.bit_set_begin(), Filled.bit_set_end());
+  int Counter = 0;
+  for (int Bit : Filled.bit_set())
+    EXPECT_EQ(Bit, Counter++);
+
+  TypeParam Empty;
+  EXPECT_EQ(Empty.bit_set_begin(), Empty.bit_set_end());
+  for (int Bit : Empty.bit_set()) {
+    (void)Bit;
+    EXPECT_TRUE(false);
+  }
+
+  TypeParam ToFill(100, false);
+  ToFill.set(0);
+  EXPECT_NE(ToFill.bit_set_begin(), ToFill.bit_set_end());
+  EXPECT_EQ(++ToFill.bit_set_begin(), ToFill.bit_set_end());
+  EXPECT_EQ(*ToFill.bit_set_begin(), 0U);
+  ToFill.reset(0);
+  EXPECT_EQ(ToFill.bit_set_begin(), ToFill.bit_set_end());
+
+  const int List[] = {1, 10, 25, 99};
+  for (int Num : List)
+    ToFill.set(Num);
+  int i = 0;
+  for (int Bit : ToFill.bit_set())
+    EXPECT_EQ(List[i++], Bit);
+}
 }
 #endif