Index: include/llvm/ADT/BitVector.h =================================================================== --- include/llvm/ADT/BitVector.h +++ include/llvm/ADT/BitVector.h @@ -14,6 +14,7 @@ #ifndef LLVM_ADT_BITVECTOR_H #define LLVM_ADT_BITVECTOR_H +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/MathExtras.h" #include #include @@ -25,6 +26,50 @@ namespace llvm { +/// ForwardIterator for the bits that are set. +/// Iterators get invalidated when resize / reserve is called. +template class const_set_bits_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_set_bits_iterator_impl(const BitVectorT &Parent, int Current) + : Parent(Parent), Current(Current) {} + explicit const_set_bits_iterator_impl(const BitVectorT &Parent) + : const_set_bits_iterator_impl(Parent, Parent.find_first()) {} + const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default; + + const_set_bits_iterator_impl operator++(int) { + auto Prev = *this; + advance(); + return Prev; + } + + const_set_bits_iterator_impl &operator++() { + advance(); + return *this; + } + + unsigned operator*() const { return Current; } + + bool operator==(const const_set_bits_iterator_impl &Other) const { + assert(&Parent == &Other.Parent && + "Comparing iterators from different BitVectors"); + return Current == Other.Current; + } + + bool operator!=(const const_set_bits_iterator_impl &Other) const { + assert(&Parent == &Other.Parent && + "Comparing iterators from different BitVectors"); + return Current != Other.Current; + } +}; + class BitVector { typedef unsigned long BitWord; @@ -73,6 +118,18 @@ } }; + typedef const_set_bits_iterator_impl const_set_bits_iterator; + typedef const_set_bits_iterator set_iterator; + + const_set_bits_iterator set_bits_begin() const { + return const_set_bits_iterator(*this); + } + const_set_bits_iterator set_bits_end() const { + return const_set_bits_iterator(*this, -1); + } + iterator_range set_bits() const { + return make_range(set_bits_begin(), set_bits_end()); + } /// BitVector default ctor - Creates an empty bitvector. BitVector() : Size(0), Capacity(0) { Index: include/llvm/ADT/SmallBitVector.h =================================================================== --- include/llvm/ADT/SmallBitVector.h +++ include/llvm/ADT/SmallBitVector.h @@ -136,6 +136,19 @@ } public: + typedef const_set_bits_iterator_impl const_set_bits_iterator; + typedef const_set_bits_iterator set_iterator; + + const_set_bits_iterator set_bits_begin() const { + return const_set_bits_iterator(*this); + } + const_set_bits_iterator set_bits_end() const { + return const_set_bits_iterator(*this, -1); + } + iterator_range set_bits() const { + return make_range(set_bits_begin(), set_bits_end()); + } + /// Creates an empty bitvector. SmallBitVector() : X(1) {} Index: lib/Analysis/DependenceAnalysis.cpp =================================================================== --- lib/Analysis/DependenceAnalysis.cpp +++ lib/Analysis/DependenceAnalysis.cpp @@ -2984,7 +2984,7 @@ SmallVectorImpl &Constraints, bool &Consistent) { bool Result = false; - for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) { + for (unsigned LI : Loops.set_bits()) { DEBUG(dbgs() << "\t Constraint[" << LI << "] is"); DEBUG(Constraints[LI].dump(dbgs())); if (Constraints[LI].isDistance()) @@ -3266,7 +3266,7 @@ // 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 (unsigned VI : BV.set_bits()) { dbgs() << VI; if (BV.find_next(VI) >= 0) dbgs() << ' '; @@ -3506,7 +3506,7 @@ NewConstraint.setAny(SE); // test separable subscripts - for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) { + for (unsigned SI : Separable.set_bits()) { DEBUG(dbgs() << "testing subscript " << SI); switch (Pair[SI].Classification) { case Subscript::ZIV: @@ -3545,14 +3545,14 @@ SmallVector 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 (unsigned SI : Coupled.set_bits()) { DEBUG(dbgs() << "testing subscript group " << SI << " { "); SmallBitVector Group(Pair[SI].Group); SmallBitVector Sivs(Pairs); SmallBitVector Mivs(Pairs); SmallBitVector ConstrainedLevels(MaxLevels + 1); SmallVector PairsInGroup; - for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) { + for (unsigned SJ : Group.set_bits()) { DEBUG(dbgs() << SJ << " "); if (Pair[SJ].Classification == Subscript::SIV) Sivs.set(SJ); @@ -3564,7 +3564,7 @@ DEBUG(dbgs() << "}\n"); while (Sivs.any()) { bool Changed = false; - for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) { + for (unsigned SJ : Sivs.set_bits()) { DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n"); // SJ is an SIV subscript that's part of the current coupled group unsigned Level; @@ -3588,7 +3588,7 @@ DEBUG(dbgs() << " propagating\n"); DEBUG(dbgs() << "\tMivs = "); DEBUG(dumpSmallBitVector(Mivs)); - for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { + for (unsigned SJ : Mivs.set_bits()) { // 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, @@ -3622,7 +3622,7 @@ } // test & propagate remaining RDIVs - for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { + for (unsigned SJ : Mivs.set_bits()) { if (Pair[SJ].Classification == Subscript::RDIV) { DEBUG(dbgs() << "RDIV test\n"); if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) @@ -3635,7 +3635,7 @@ // 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 (unsigned SJ : Mivs.set_bits()) { if (Pair[SJ].Classification == Subscript::MIV) { DEBUG(dbgs() << "MIV test\n"); if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result)) @@ -3647,8 +3647,7 @@ // update Result.DV from constraint vector DEBUG(dbgs() << " updating\n"); - for (int SJ = ConstrainedLevels.find_first(); SJ >= 0; - SJ = ConstrainedLevels.find_next(SJ)) { + for (unsigned SJ : ConstrainedLevels.set_bits()) { if (SJ > (int)CommonLevels) break; updateDirection(Result.DV[SJ - 1], Constraints[SJ]); @@ -3859,7 +3858,7 @@ NewConstraint.setAny(SE); // test separable subscripts - for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) { + for (unsigned SI : Separable.set_bits()) { switch (Pair[SI].Classification) { case Subscript::SIV: { unsigned Level; @@ -3886,12 +3885,12 @@ SmallVector 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 (unsigned SI : Coupled.set_bits()) { 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 (unsigned SJ : Group.set_bits()) { if (Pair[SJ].Classification == Subscript::SIV) Sivs.set(SJ); else @@ -3899,7 +3898,7 @@ } while (Sivs.any()) { bool Changed = false; - for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) { + for (unsigned SJ : Sivs.set_bits()) { // SJ is an SIV subscript that's part of the current coupled group unsigned Level; const SCEV *SplitIter = nullptr; @@ -3914,7 +3913,7 @@ } if (Changed) { // propagate, possibly creating new SIVs and ZIVs - for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) { + for (unsigned SJ : Mivs.set_bits()) { // 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)) { Index: lib/CodeGen/AggressiveAntiDepBreaker.cpp =================================================================== --- lib/CodeGen/AggressiveAntiDepBreaker.cpp +++ lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -128,8 +128,7 @@ } DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); - DEBUG(for (int r = CriticalPathSet.find_first(); r != -1; - r = CriticalPathSet.find_next(r)) + DEBUG(for (unsigned r : CriticalPathSet.set_bits()) dbgs() << " " << TRI->getName(r)); DEBUG(dbgs() << '\n'); } @@ -571,7 +570,7 @@ DEBUG({ dbgs() << " ::"; - for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) + for (unsigned r : BV.set_bits()) dbgs() << " " << TRI->getName(r); dbgs() << "\n"; }); Index: lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp =================================================================== --- lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp +++ lib/CodeGen/AsmPrinter/DbgValueHistoryCalculator.cpp @@ -209,8 +209,7 @@ } 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 (unsigned I : ChangingRegs.set_bits()) { // Don't consider SP to be clobbered by register masks. if (unsigned(I) != SP && TRI->isPhysicalRegister(I) && MO.clobbersPhysReg(I)) { Index: lib/CodeGen/MachineVerifier.cpp =================================================================== --- lib/CodeGen/MachineVerifier.cpp +++ lib/CodeGen/MachineVerifier.cpp @@ -758,7 +758,7 @@ const MachineFrameInfo &MFI = MF->getFrameInfo(); BitVector PR = MFI.getPristineRegs(*MF); - for (int I = PR.find_first(); I>0; I = PR.find_next(I)) { + for (unsigned I : PR.set_bits()) { for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true); SubRegs.isValid(); ++SubRegs) regsLive.insert(*SubRegs); Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -285,8 +285,7 @@ // Set B[i] = C for every live bundle where B[i] was NoCand. unsigned getBundles(SmallVectorImpl &B, unsigned C) { unsigned Count = 0; - for (int i = LiveBundles.find_first(); i >= 0; - i = LiveBundles.find_next(i)) + for (unsigned i : LiveBundles.set_bits()) if (B[i] == NoCand) { B[i] = C; Count++; @@ -1162,9 +1161,8 @@ } DEBUG({ - for (int i = Cand.LiveBundles.find_first(); i>=0; - i = Cand.LiveBundles.find_next(i)) - dbgs() << " EB#" << i; + for (int i : Cand.LiveBundles.set_bits()) + dbgs() << " EB#" << i; dbgs() << ".\n"; }); return true; @@ -1482,8 +1480,7 @@ 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.set_bits()) dbgs() << " EB#" << i; dbgs() << ".\n"; }); Index: lib/CodeGen/SpillPlacement.cpp =================================================================== --- lib/CodeGen/SpillPlacement.cpp +++ lib/CodeGen/SpillPlacement.cpp @@ -310,7 +310,7 @@ bool SpillPlacement::scanActiveBundles() { RecentPositive.clear(); - for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) { + for (unsigned n : ActiveNodes->set_bits()) { 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. @@ -365,7 +365,7 @@ // Write preferences back to ActiveNodes. bool Perfect = true; - for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) + for (unsigned n : ActiveNodes->set_bits()) if (!nodes[n].preferReg()) { ActiveNodes->reset(n); Perfect = false; Index: lib/CodeGen/StackColoring.cpp =================================================================== --- lib/CodeGen/StackColoring.cpp +++ lib/CodeGen/StackColoring.cpp @@ -703,12 +703,10 @@ // 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 (unsigned pos : MBBLiveness.LiveIn.set_bits()) { Starts[pos] = Indexes->getMBBStartIdx(&MBB); } - for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1; - pos = MBBLiveness.LiveOut.find_next(pos)) { + for (unsigned pos : MBBLiveness.LiveOut.set_bits()) { Finishes[pos] = Indexes->getMBBEndIdx(&MBB); } Index: lib/CodeGen/TargetLoweringBase.cpp =================================================================== --- lib/CodeGen/TargetLoweringBase.cpp +++ lib/CodeGen/TargetLoweringBase.cpp @@ -1296,7 +1296,7 @@ // 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 (unsigned i : SuperRegRC.set_bits()) { const TargetRegisterClass *SuperRC = TRI->getRegClass(i); // We want the largest possible spill size. if (SuperRC->getSize() <= BestRC->getSize()) Index: lib/CodeGen/TargetRegisterInfo.cpp =================================================================== --- lib/CodeGen/TargetRegisterInfo.cpp +++ lib/CodeGen/TargetRegisterInfo.cpp @@ -50,8 +50,7 @@ ArrayRef 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 (unsigned Reg : RegisterSet.set_bits()) { if (Checked[Reg]) continue; for (MCSuperRegIterator SR(Reg, this); SR.isValid(); ++SR) { Index: lib/Target/AArch64/AArch64FrameLowering.cpp =================================================================== --- lib/Target/AArch64/AArch64FrameLowering.cpp +++ lib/Target/AArch64/AArch64FrameLowering.cpp @@ -1158,8 +1158,7 @@ } DEBUG(dbgs() << "*** determineCalleeSaves\nUsed CSRs:"; - for (int Reg = SavedRegs.find_first(); Reg != -1; - Reg = SavedRegs.find_next(Reg)) + for (unsigned Reg : SavedRegs.set_bits()) dbgs() << ' ' << PrintReg(Reg, RegInfo); dbgs() << "\n";); Index: lib/Target/ARM/Thumb1FrameLowering.cpp =================================================================== --- lib/Target/ARM/Thumb1FrameLowering.cpp +++ lib/Target/ARM/Thumb1FrameLowering.cpp @@ -572,8 +572,7 @@ 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 (unsigned Register : GPRsNoLRSP.set_bits()) { if (!UsedRegs.contains(Register)) { // Remember the first pop-friendly register and exit. if (PopFriendly.test(Register)) { Index: lib/Target/Mips/MipsDelaySlotFiller.cpp =================================================================== --- lib/Target/Mips/MipsDelaySlotFiller.cpp +++ lib/Target/Mips/MipsDelaySlotFiller.cpp @@ -386,7 +386,7 @@ 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 (unsigned R : AllocSet.set_bits()) for (MCRegAliasIterator AI(R, &TRI, false); AI.isValid(); ++AI) AllocSet.set(*AI); Index: lib/Target/WebAssembly/WebAssemblyRegColoring.cpp =================================================================== --- lib/Target/WebAssembly/WebAssemblyRegColoring.cpp +++ lib/Target/WebAssembly/WebAssemblyRegColoring.cpp @@ -140,8 +140,7 @@ // 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 (unsigned C : UsedColors.bits_set()) { if (MRI->getRegClass(SortedIntervals[C]->reg) != RC) continue; for (LiveInterval *OtherLI : Assignments[C]) Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -3907,8 +3907,7 @@ // 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 (unsigned LUIdx : UsedByIndices.set_bits()) // 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)); Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -2491,8 +2491,7 @@ // 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 (unsigned InstrNum : TouchedInstructions.set_bits()) { // This instruction was found to be dead. We don't bother looking // at it again. Index: unittests/ADT/BitVectorTest.cpp =================================================================== --- unittests/ADT/BitVectorTest.cpp +++ unittests/ADT/BitVectorTest.cpp @@ -501,5 +501,34 @@ testEmpty(E); } +TYPED_TEST(BitVectorTest, Iterators) { + TypeParam Filled(10, true); + EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); + unsigned Counter = 0; + for (unsigned Bit : Filled.set_bits()) + EXPECT_EQ(Bit, Counter++); + + TypeParam Empty; + EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); + for (unsigned Bit : Empty.set_bits()) { + (void)Bit; + EXPECT_TRUE(false); + } + + TypeParam ToFill(100, false); + ToFill.set(0); + EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); + EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); + EXPECT_EQ(*ToFill.set_bits_begin(), 0U); + ToFill.reset(0); + EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); + + const unsigned List[] = {1, 10, 25, 99}; + for (unsigned Num : List) + ToFill.set(Num); + unsigned i = 0; + for (unsigned Bit : ToFill.set_bits()) + EXPECT_EQ(List[i++], Bit); +} } #endif