[LiveDebugValues] Speed up removeEntryValue, NFC

[vsk]

Summary

Instead of iterating over all VarLoc IDs in removeEntryValue(), just
iterate over the interval reserved for entry value VarLocs. This changes
the iteration order, hence the test update -- otherwise this is NFC.

This appears to give an ~8.5x wall time speed-up for LiveDebugValues when
compiling sqlite3.c 3.30.1 with a Release clang (on my machine):

        ---User Time---   --System Time--   --User+System--   ---Wall Time--- --- Name ---
Before: 2.5402 ( 18.8%)   0.0050 (  0.4%)   2.5452 ( 17.3%)   2.5452 ( 17.3%) Live DEBUG_VALUE analysis
 After: 0.2364 (  2.1%)   0.0034 (  0.3%)   0.2399 (  2.0%)   0.2398 (  2.0%) Live DEBUG_VALUE analysis

The change in removeEntryValue() is the only one that appears to affect
wall time, but for consistency (and to resolve a pending TODO), I made
the analogous changes for iterating over SpillLocKind VarLocs.

[vsk]

I've generalize the patch a bit:

• Assign a reserved location for SpillLocKind VarLocs.
• Share the reserved location between all EntryValue*Kind VarLocs.
• Get rid of for (uint64_t ID : OpenRanges.getVarLocs()). We should always iterate over a subset of open VarLocs.

[vsk]

Simplify the diff.

[djtodoro]

Great!

llvm/lib/CodeGen/LiveDebugValues.cpp

929

I'm not sure we want to remove this line. The backup locations are EntryValueBackupKind and EntryValueCopyBackupKind only; the EntryValueKind is real location created from one of these two.

[nikic]

Hm, for some reason I'm not seeing any instruction count differences with this patch (or at least the latest version), in either -O0 -g or -O3 -g configuration.

[jmorse]

The implementation here looks good, and should lead to some kind of speedup. I'll leave approving to @djtodoro as he knows the entry value mechanisms better.

llvm/unittests/ADT/CoalescingBitVectorTest.cpp

506

IMHO, we should also test a Start >= End case, as that's a condition in half_open_range.

[aprantl]

llvm/include/llvm/ADT/CoalescingBitVector.h

363

It's weird that this empty range violates the assertion on line 360, but I think that is okay.

Is *StartIt >= End even possible, given the assertion?

llvm/lib/CodeGen/LiveDebugValues.cpp

148

what does the k stand for?

1385

if (VL.Loc.SpillLocation != *Loc)
  // Comment explains why no pair is inserted...
  continue;
LLVM_DEBUG(dbgs() << "Restoring Register " ...

[vsk]

In D80684#2059689, @nikic wrote:

Hm, for some reason I'm not seeing any instruction count differences with this patch (or at least the latest version), in either -O0 -g or -O3 -g configuration.

@nikic I can reproduce the problem using wall time alone. I did 5 CTMark runs at {-O0 -g, -O3 -g} x {prepatch, postpatch} (20 runs total, at -j1, no other stabilization), but found no significant geomean compile time change prepatch vs. postpatch. However, I do see a large speedup when compiling a separate copy of sqlite3.

It looks like CTMark ships the sqlite3 3.5.7 amalgamation (85 KLOC, generated in 2008), whereas I've been testing with the 3.30.1 amalgamation (225 KLOC, generated in 2019).

So, I think this change is worthwhile, but maybe it's not sufficient.

llvm/include/llvm/ADT/CoalescingBitVector.h

363

Thanks for the careful review here. I've added simplified test cases that show why the *StartIt >= End check is necessary, and why we have to return an empty range in that case.

The situation is: say you have the bitvector {1}, and you ask for the half-open range [0, 1). Keep in mind that find(X) returns a lower bound (the first bit set at, or after, X). So *find(Start) = *find(0) = 1, which means *StartIt == End. Since we want a half-open range, we don't want to include 1 in it, hence the empty range.

Similarly, if you have the bitvector {5} and you ask for the half-open range [3, 4), *find(Start) = *find(3) = 5, which means *StartIt > End and we want to return the empty range again.

llvm/lib/CodeGen/LiveDebugValues.cpp

148

"Constant" -- it's somewhat idiomatic in that it's used a fair amount in llvm, but not consistently. I'm not attached to this. Happy to go with your preferred spelling.

929

It looks like VL.getEntryValueCopyBackupReg() returns undef when VL.Kind isn't the right kind. So it seems safe to remove the VL.isEntryBackupLoc() check?

llvm/unittests/ADT/CoalescingBitVectorTest.cpp

506

Ah, are you referring to the same case Adrian described? If so, I've just added a test to cover that.

[vsk]

Address review feedback.

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues.cpp

509

Should we make a different kEntryValBackupLocation (and something like getBackupEntryValuesVarLocs())?

The backup locations (EntryValueBackupKind and EntryValueCopyBackupKind) are invisible/backup/secondary up to the point we lost the primary location of a variable; and then we turn the backup location into entry value location (EntryValueKind) which is (further on) used as primary location.

929

Oh, I see. It is safe! Thanks.
Eventually, if we get rid of the [1] we won't need this part at all. The EntryValueCopyBackupKind was used to indicate the variable's value was not changed with the new DBG_VALUE (for the same variable), but it was moved around due to the code from [1].

[1] https://github.com/llvm/llvm-project/blob/446082b99f0bd9786d24edd3cd598dc4e5f64371/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp#L590

990

Based on my previous comments, I think we need only getBackupEntryValuesVarLocs() here.

1430

Here we would need only getBackupEntryValuesVarLocs().

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

493

Side-note: does this get more readable if we introduce a typedef for uint32_t here, such a VarLocIndex?

1385

did this get marked as done by accident?

[vsk]

llvm/lib/CodeGen/LiveDebugValues.cpp

493

That may look a little too similar to "LocIndex". Wdyt of LocIndex::uint32_location_t and LocIndex::uint32_index_t?

509

Good point, this should now be fixed.

929

I see, thanks for the pointer (cc @tbosch, this is related to the discussion from D80819).

1385

Sorry about that, somehow I missed that you were asking to convert this to an early exit. Should be fixed soon.

[vsk]

Address review feedback.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

493

sure!

[djtodoro]

LGTM, thanks!

llvm/include/llvm/ADT/CoalescingBitVector.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_COALESCINGBITVECTOR_H
 #define LLVM_ADT_COALESCINGBITVECTOR_H
 
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <algorithm>
 #include <initializer_list>
 
 namespace llvm {
 
const_iterator find(IndexT Index) const {
     auto UnderlyingIt = Intervals.find(Index);
     if (UnderlyingIt == Intervals.end())
       return end();
     auto It = const_iterator(UnderlyingIt);
     It.advanceTo(Index);
     return It;
   }
 
+  /// Return a range iterator which iterates over all of the set bits in the
+  /// half-open range [Start, End).
+  iterator_range<const_iterator> half_open_range(IndexT Start,
+                                                 IndexT End) const {
+    assert(Start < End && "Not a valid range");
+    auto StartIt = find(Start);
+    if (StartIt == end() || *StartIt >= End)
+      return {end(), end()};
+    auto EndIt = StartIt;
+    EndIt.advanceToLowerBound(End);
+    return {StartIt, EndIt};
+  }
+
   void print(raw_ostream &OS) const {
     OS << "{";
     for (auto It = Intervals.begin(), End = Intervals.end(); It != End;
          ++It) {
       OS << "[" << It.start();
       if (It.start() != It.stop())
         OS << ", " << It.stop();
       OS << "]";

llvm/lib/CodeGen/LiveDebugValues.cpp

 /// A type-checked pair of {Register Location (or 0), Index}, used to index
 /// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
 /// for insertion into a \ref VarLocSet, and efficiently converted back. The
 /// type-checker helps ensure that the conversions aren't lossy.
 ///
 /// Why encode a location /into/ the VarLocMap index? This makes it possible
 /// to find the open VarLocs killed by a register def very quickly. This is a
 /// performance-critical operation for LiveDebugValues.
-///
-/// TODO: Consider adding reserved intervals for kinds of VarLocs other than
-/// RegisterKind, like SpillLocKind or EntryValueKind, to optimize iteration
-/// over open locations.
 struct LocIndex {
   uint32_t Location; // Physical registers live in the range [1;2^30) (see
                      // \ref MCRegister), so we have plenty of range left here
                      // to encode non-register locations.
   uint32_t Index;
 
+  /// The first location greater than 0 that is not reserved for VarLocs of
+  /// kind RegisterKind.
+  static constexpr uint32_t kFirstInvalidRegLocation = 1 << 30;
+
+  /// A special location reserved for VarLocs of kind SpillLocKind.
+  static constexpr uint32_t kSpillLocation = kFirstInvalidRegLocation;
+
+  /// A special location reserved for VarLocs of kind EntryValueBackupKind and
+  /// EntryValueCopyBackupKind.
+  static constexpr uint32_t kEntryValueBackupLocation =
+      kFirstInvalidRegLocation + 1;
+
   LocIndex(uint32_t Location, uint32_t Index)
       : Location(Location), Index(Index) {}
 
   uint64_t getAsRawInteger() const {
     return (static_cast<uint64_t>(Location) << 32) | Index;
   }
 
   template<typename IntT> static LocIndex fromRawInteger(IntT ID) {
     static_assert(std::is_unsigned<IntT>::value &&
                       sizeof(ID) == sizeof(uint64_t),
                   "Cannot convert raw integer to LocIndex");
     return {static_cast<uint32_t>(ID >> 32), static_cast<uint32_t>(ID)};
   }
 
   /// Get the start of the interval reserved for VarLocs of kind RegisterKind
   /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1.
   static uint64_t rawIndexForReg(uint32_t Reg) {
     return LocIndex(Reg, 0).getAsRawInteger();
   }
+
+  /// Return a range covering all set indices in the interval reserved for
+  /// \p Location in \p Set.
+  static auto indexRangeForLocation(const VarLocSet &Set, uint32_t Location) {
+    uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
+    uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
+    return Set.half_open_range(Start, End);
+  }
 };
 
 class LiveDebugValues : public MachineFunctionPass {
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   BitVector CalleeSavedRegs;
struct VarLoc {
     // The location at which a spilled variable resides. It consists of a
     // register and an offset.
     struct SpillLoc {
       unsigned SpillBase;
       int SpillOffset;
       bool operator==(const SpillLoc &Other) const {
         return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
       }
+      bool operator!=(const SpillLoc &Other) const {
+        return !(*this == Other);
+      }
     };
 
     /// Identity of the variable at this location.
     const DebugVariable Var;
 
     /// The expression applied to this location.
     const DIExpression *Expr;
 
#endif
 
   /// VarLocMap is used for two things:
   /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to
   ///    virtually insert a VarLoc into a VarLocSet.
   /// 2) Given a LocIndex, look up the unique associated VarLoc.
   class VarLocMap {
     /// Map a VarLoc to an index within the vector reserved for its location
     /// within Loc2Vars.
     std::map<VarLoc, uint32_t> Var2Index;
 
     /// Map a location to a vector which holds VarLocs which live in that
     /// location.
     SmallDenseMap<uint32_t, std::vector<VarLoc>> Loc2Vars;
 
+    /// Determine the 32-bit location reserved for \p VL, based on its kind.
+    static uint32_t getLocationForVar(const VarLoc &VL) {
+      switch (VL.Kind) {
+      case VarLoc::RegisterKind:
+        assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) &&
+               "Physreg out of range?");
+        return VL.Loc.RegNo;
+      case VarLoc::SpillLocKind:
+        return LocIndex::kSpillLocation;
+      case VarLoc::EntryValueBackupKind:
+      case VarLoc::EntryValueCopyBackupKind:
+        return LocIndex::kEntryValueBackupLocation;
+      default:
+        return 0;
+      }
+    }
+
   public:
     /// Retrieve a unique LocIndex for \p VL.
     LocIndex insert(const VarLoc &VL) {
-      uint32_t Location = VL.isDescribedByReg();
+      uint32_t Location = getLocationForVar(VL);
       uint32_t &Index = Var2Index[VL];
       if (!Index) {
         auto &Vars = Loc2Vars[Location];
         Vars.push_back(VL);
         Index = Vars.size();
       }
       return {Location, Index - 1};
     }
public:
 
     /// Return whether the set is empty or not.
     bool empty() const {
       assert(Vars.empty() == EntryValuesBackupVars.empty() &&
              Vars.empty() == VarLocs.empty() &&
              "open ranges are inconsistent");
       return VarLocs.empty();
     }
+
+    /// Get an empty range of VarLoc IDs.
+    auto getEmptyVarLocRange() const {
+      return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(),
+                                                       getVarLocs().end());
+    }
+
+    /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg.
+    auto getRegisterVarLocs(Register Reg) const {
+      return LocIndex::indexRangeForLocation(getVarLocs(), Reg);
+    }
+
+    /// Get all set IDs for VarLocs of kind SpillLocKind.
+    auto getSpillVarLocs() const {
+      return LocIndex::indexRangeForLocation(getVarLocs(),
+                                             LocIndex::kSpillLocation);
+    }
+
+    /// Get all set IDs for VarLocs of kind EntryValueBackupKind or
+    /// EntryValueCopyBackupKind.
+    auto getEntryValueBackupVarLocs() const {
+      return LocIndex::indexRangeForLocation(
+          getVarLocs(), LocIndex::kEntryValueBackupLocation);
+    }
   };
 
   /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind
   /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs
   /// into \p Collected.
   void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs,
                          const VarLocSet &CollectFrom) const;
 
void LiveDebugValues::collectIDsForRegs(VarLocSet &Collected,
   }
 }
 
 void LiveDebugValues::getUsedRegs(const VarLocSet &CollectFrom,
                                   SmallVectorImpl<uint32_t> &UsedRegs) const {
   // All register-based VarLocs are assigned indices greater than or equal to
   // FirstRegIndex.
   uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1);
-  for (auto It = CollectFrom.find(FirstRegIndex), End = CollectFrom.end();
+  uint64_t FirstInvalidIndex =
+      LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
+  for (auto It = CollectFrom.find(FirstRegIndex),
+            End = CollectFrom.find(FirstInvalidIndex);
        It != End;) {
     // We found a VarLoc ID for a VarLoc that lives in a register. Figure out
     // which register and add it to UsedRegs.
     uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location;
     assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) &&
            "Duplicate used reg");
     UsedRegs.push_back(FoundReg);
 
if (I != MI.getParent()->rend()) {
     SrcRegOp = DestSrc->Source;
     DestRegOp = DestSrc->Destination;
     if (Reg != DestRegOp->getReg())
       return true;
     TrySalvageEntryValue = true;
   }
 
   if (TrySalvageEntryValue) {
-    for (uint64_t ID : OpenRanges.getVarLocs()) {
+    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
       const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
-      if (!VL.isEntryBackupLoc())
-        continue;
-
       if (VL.getEntryValueCopyBackupReg() == Reg &&
           VL.MI.getOperand(0).getReg() == SrcRegOp->getReg())
         return false;
     }
   }
 
   return true;
 }
void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
 
   // First, if there are any DBG_VALUEs pointing at a spill slot that is
   // written to, then close the variable location. The value in memory
   // will have changed.
   VarLocSet KillSet(Alloc);
   if (isSpillInstruction(MI, MF)) {
     Loc = extractSpillBaseRegAndOffset(MI);
-    for (uint64_t ID : OpenRanges.getVarLocs()) {
+    for (uint64_t ID : OpenRanges.getSpillVarLocs()) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       const VarLoc &VL = VarLocIDs[Idx];
-      if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) {
+      assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
+      if (VL.Loc.SpillLocation == *Loc) {
         // This location is overwritten by the current instruction -- terminate
         // the open range, and insert an explicit DBG_VALUE $noreg.
         //
         // Doing this at a later stage would require re-interpreting all
         // DBG_VALUes and DIExpressions to identify whether they point at
         // memory, and then analysing all memory writes to see if they
         // overwrite that memory, which is expensive.
         //
if (isLocationSpill(MI, MF, Reg)) {
     if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
       return;
     TKind = TransferKind::TransferRestore;
     LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
                       << "\n");
   }
   // Check if the register or spill location is the location of a debug value.
-  for (uint64_t ID : OpenRanges.getVarLocs()) {
+  auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
+  if (TKind == TransferKind::TransferSpill)
+    TransferCandidates = OpenRanges.getRegisterVarLocs(Reg);
+  else if (TKind == TransferKind::TransferRestore)
+    TransferCandidates = OpenRanges.getSpillVarLocs();
+  for (uint64_t ID : TransferCandidates) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
     const VarLoc &VL = VarLocIDs[Idx];
-    if (TKind == TransferKind::TransferSpill && VL.isDescribedByReg() == Reg) {
+    if (TKind == TransferKind::TransferSpill) {
+      assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?");
       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
                         << VL.Var.getVariable()->getName() << ")\n");
-    } else if (TKind == TransferKind::TransferRestore &&
-               VL.Kind == VarLoc::SpillLocKind &&
-               VL.Loc.SpillLocation == *Loc) {
+    } else {
+      assert(TKind == TransferKind::TransferRestore &&
+             VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
+      if (VL.Loc.SpillLocation != *Loc)
+        // The spill location is not the location of a debug value.
+        continue;
       LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
                         << VL.Var.getVariable()->getName() << ")\n");
-    } else
-      continue;
+    }
     insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
                             Reg);
+    // FIXME: A comment should explain why it's correct to return early here,
+    // if that is in fact correct.
     return;
   }
 }
 
 /// If \p MI is a register copy instruction, that copies a previously tracked
 /// value from one register to another register that is callee saved, we
 /// create new DBG_VALUE instruction  described with copy destination register.
 void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
void LiveDebugValues::transferRegisterCopy(MachineInstr &MI,
   // saved, is going to stay unclobbered longer, even if it is killed.
   if (!isCalleeSavedReg(DestReg))
     return;
 
   // Remember an entry value movement. If we encounter a new debug value of
   // a parameter describing only a moving of the value around, rather then
   // modifying it, we are still able to use the entry value if needed.
   if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) {
-    for (uint64_t ID : OpenRanges.getVarLocs()) {
+    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       const VarLoc &VL = VarLocIDs[Idx];
       if (VL.getEntryValueBackupReg() == SrcReg) {
         LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump(););
         VarLoc EntryValLocCopyBackup =
             VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg);
 
         // Stop tracking the original entry value.
         OpenRanges.erase(VL);
 
         // Start tracking the entry value copy.
         LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup);
         OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup);
         break;
       }
     }
   }
 
   if (!SrcRegOp->isKill())
     return;
 
-  for (uint64_t ID : OpenRanges.getVarLocs()) {
+  for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
-    if (VarLocIDs[Idx].isDescribedByReg() == SrcReg) {
-      insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
-                              TransferKind::TransferCopy, DestReg);
-      return;
-    }
-  }
-}
+    assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?");
+    // FIXME: A comment should explain why it's correct to return early here,
+    // if that is in fact correct.
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
                                          OpenRangesSet &OpenRanges,
                                          VarLocInMBB &OutLocs,
                                          const VarLocMap &VarLocIDs) {
   bool Changed = false;
 

llvm/test/DebugInfo/MIR/X86/entry-values-diamond-bbs.mir

 # CHECK: bb.2.if.else
 # CHECK: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression()
 # CHECK: $ebx = MOV32rr $esi
 # CHECK-NEXT: DBG_VALUE $ebx, $noreg, ![[ARG_B]], !DIExpression()
 # CHECK-NEXT: $esi = MOV32ri 1
 # CHECK-NEXT: $ebx = MOV32ri 2
 # CHECK-NEXT: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression(DW_OP_LLVM_entry_value, 1)
 # CHECK: bb.3.if.end
-# CHECK-NEXT: DBG_VALUE $edx, $noreg, ![[ARG_Q]], !DIExpression()
-# CHECK-NEXT: DBG_VALUE $ebp, $noreg, ![[ARG_C]], !DIExpression()
-# CHECK-NEXT: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression(DW_OP_LLVM_entry_value, 1)
+# CHECK-DAG: DBG_VALUE $edx, $noreg, ![[ARG_Q]], !DIExpression()
+# CHECK-DAG: DBG_VALUE $ebp, $noreg, ![[ARG_C]], !DIExpression()
+# CHECK-DAG: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression(DW_OP_LLVM_entry_value, 1)
 --- |
   ; ModuleID = 'test.c'
   source_filename = "test.c"
   target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"
 
   ; Function Attrs: noinline nounwind uwtable
   define dso_local i32 @fn2(i32 %a, i32 %b, i32 %c) local_unnamed_addr !dbg !12 {

llvm/unittests/ADT/CoalescingBitVectorTest.cpp

if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) {
     Expected.print(dbgs());
     dbgs() << "          Got: ";
     BV.print(dbgs());
     return false;
   }
   return true;
 }
 
+bool rangesMatch(iterator_range<UBitVec::const_iterator> R,
+                 std::initializer_list<unsigned> List) {
+  return std::equal(R.begin(), R.end(), List.begin(), List.end());
+}
+
 TEST(CoalescingBitVectorTest, Set) {
   UBitVec::Allocator Alloc;
   UBitVec BV1(Alloc);
   UBitVec BV2(Alloc);
 
   BV1.set(0);
   EXPECT_TRUE(BV1.test(0));
   EXPECT_FALSE(BV1.test(1));
TEST(CoalescingBitVectorTest, AdvanceToLowerBound) {
   It.advanceToLowerBound(0);
   EXPECT_EQ(*It, 1u);
   It.advanceToLowerBound(100);
   EXPECT_TRUE(It == BV.end());
   It.advanceToLowerBound(100);
   EXPECT_TRUE(It == BV.end());
 }
 
+TEST(CoalescingBitVectorTest, HalfOpenRange) {
+  UBitVec::Allocator Alloc;
+
+  {
+    UBitVec BV(Alloc);
+    BV.set({1, 2, 3});
+
+    EXPECT_EQ(*BV.find(0), 1U); // find(Start) > Start
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2, 3}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 4), {1, 2, 3}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 3), {1, 2}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 3), {2}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 4), {2, 3}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(4, 5), {}));
+  }
+
+  {
+    UBitVec BV(Alloc);
+    BV.set({1, 2, 11, 12});
+
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 15), {1, 2, 11, 12}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 13), {1, 2, 11, 12}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 12), {1, 2, 11}));
+
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 5), {1, 2}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 5), {2}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 2), {1}));
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(13, 14), {}));
+
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 10), {2}));
+  }
+
+  {
+    UBitVec BV(Alloc);
+    BV.set({1});
+
+    EXPECT_EQ(*BV.find(0), 1U); // find(Start) == End
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 1), {}));
+  }
+
+  {
+    UBitVec BV(Alloc);
+    BV.set({5});
+
+    EXPECT_EQ(*BV.find(3), 5U); // find(Start) > End
+    EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {}));
+  }
+}
+
 TEST(CoalescingBitVectorTest, Print) {
   std::string S;
   {
     raw_string_ostream OS(S);
     UBitVec::Allocator Alloc;
     UBitVec BV(Alloc);
     BV.set({1});
     BV.print(OS);