[LiveDebugValues] Encode register location within VarLoc IDs [3/3]

[vsk]

Summary

This is part 3 of a 3-part series to address a compile-time explosion
issue in LiveDebugValues.

---

Start encoding register locations within VarLoc IDs, and take advantage
of this encoding to speed up transferRegisterDef.

There is no fundamental algorithmic change: this patch simply swaps out
SparseBitVector in favor of CoalescingBitVector. That changes iteration
order (hence the test updates), but otherwise this patch is NFCI.

The only interesting change is in transferRegisterDef. Instead of doing:

KillSet = {}
for (ID : OpenRanges.getVarLocs())
  if (DeadRegs.count(ID))
    KillSet.add(ID)

We now do:

KillSet = {}
for (Reg : DeadRegs)
  for (ID : intervalsReservedForReg(Reg, OpenRanges.getVarLocs()))
    KillSet.add(ID)

By not visiting each open location every time we visit an instruction,
this eliminates some potentially quadratic behavior. The new
implementation basically does a constant amount of work per instruction
because the interval map lookups are very fast.

For a file in WebKit, this brings the time spent in LiveDebugValues down
from ~2.5 minutes to 4 seconds, reducing compile time spent in that pass
from 28% of the total to just over 1%.

Before:

2.49 min   27.8%	0 s	LiveDebugValues::process
2.41 min   27.0%	5.40 s	LiveDebugValues::transferRegisterDef
1.51 min   16.9%	1.51 min LiveDebugValues::VarLoc::isDescribedByReg() const
32.73 s    6.1%		8.70 s	 llvm::SparseBitVector<128u>::SparseBitVectorIterator::operator++()

After:

4.53 s	1.1%	0 s	LiveDebugValues::process
3.00 s	0.7%	107.00 ms		LiveDebugValues::transferRegisterCopy
892.00 ms	0.2%	406.00 ms	LiveDebugValues::transferSpillOrRestoreInst
404.00 ms	0.1%	32.00 ms	LiveDebugValues::transferRegisterDef
110.00 ms	0.0%	2.00 ms		  LiveDebugValues::getUsedRegs
57.00 ms	0.0%	1.00 ms		  std::__1::vector<>::push_back
40.00 ms	0.0%	1.00 ms		  llvm::CoalescingBitVector<>::find(unsigned long long)

FWIW, I tried the same approach using SparseBitVector, but got bad
results. To do that, I had to extend SparseBitVector to support 64-bit
indices and expose its lower bound operation. The problem with this is
that the performance is very hard to predict: SparseBitVector's lower
bound operation falls back to O(n) linear scans in a std::list if you're
not /very/ careful about managing iteration order. When I profiled this
the performance looked worse than the baseline.

You can see the full CoalescingBitVector-based implementation here:

https://github.com/vedantk/llvm-project/commits/try-coalescing

You can see the full SparseBitVector-based implementation here:

https://github.com/vedantk/llvm-project/commits/try-sparsebitvec-find

Depends on D74984 and D74985.

[vsk]

Back out changes accidentally introduced in a rebase.

[vsk]

Avoid a std::vector allocation in getUsedRegs and shorten the patch summary.

[aprantl]

Those numbers are really impressive.

llvm/lib/CodeGen/LiveDebugValues.cpp

453–459

Comment: Index into what? Or perhaps even typedef a LocIndex type?

1527

This also *looks* nicer :-)

[vsk]

Add doxygen comments to VarLocMap.

[nikic]

While bisecting compile-time regressions, I hit on this change as a larger -O0 -g regression. It's 2% geomean on CTMark, with the largest regression being 4% on sqlite3. Might be worth a look.

[vsk]

In D74986#2057531, @nikic wrote:

While bisecting compile-time regressions, I hit on this change as a larger -O0 -g regression. It's 2% geomean on CTMark, with the largest regression being 4% on sqlite3. Might be worth a look.

@nikic We actually saw a similar result on our CTMark bot, but the regression was fixed by D76465 + D76467. Were you able to measure any improvement after those changes (or, put another way, does reverting D74986 + D76465 + D76467 fix the issue)?

[nikic]

In D74986#2057820, @vsk wrote:

In D74986#2057531, @nikic wrote:

While bisecting compile-time regressions, I hit on this change as a larger -O0 -g regression. It's 2% geomean on CTMark, with the largest regression being 4% on sqlite3. Might be worth a look.

@nikic We actually saw a similar result on our CTMark bot, but the regression was fixed by D76465 + D76467. Were you able to measure any improvement after those changes (or, put another way, does reverting D74986 + D76465 + D76467 fix the issue)?

Thanks for the references! When I revert these patches in reverse order, I see (for the instructions retired metric) the original regression for sqlite at +4.4%, the CoalescingBitVector optimization as a -1.1% improvement, and the collectIDsForRegs() optimization as a -0.5% improvement. So these two changes seem to recover a sizable part of the regression (about a 35%), but not the entirety. As such, there might still be some optimization potential here. (Results for reference -- these are reverts, so inverted.)

[vsk]

In D74986#2058583, @nikic wrote:

In D74986#2057820, @vsk wrote:

In D74986#2057531, @nikic wrote:

While bisecting compile-time regressions, I hit on this change as a larger -O0 -g regression. It's 2% geomean on CTMark, with the largest regression being 4% on sqlite3. Might be worth a look.

@nikic We actually saw a similar result on our CTMark bot, but the regression was fixed by D76465 + D76467. Were you able to measure any improvement after those changes (or, put another way, does reverting D74986 + D76465 + D76467 fix the issue)?

Thanks for the references! When I revert these patches in reverse order, I see (for the instructions retired metric) the original regression for sqlite at +4.4%, the CoalescingBitVector optimization as a -1.1% improvement, and the collectIDsForRegs() optimization as a -0.5% improvement. So these two changes seem to recover a sizable part of the regression (about a 35%), but not the entirety. As such, there might still be some optimization potential here. (Results for reference -- these are reverts, so inverted.)

Interesting; I missed this because I only looked at averaged wall times while investigating. Thanks for sharing this data (the tracker is awesome). Would you mind adding reverts of D74985 + D74633 to nikic/perf/live-debug-values so we can get a complete picture? Those are two NFC preparatory changes for the main data structure change (this patch). I suspect D74633 in particular gave a large speedup: it's possible that this patch causes a slowdown relative to D74633 on small inputs. That could tell us which direction to go. There a number of compile-time optimizations that are possible with CoalescingBitVector, but if we're slower on small inputs after reverting D74633, maybe we should rethink the data structure instead.

[vsk]

@nikic D80684 might help with this as well.

llvm/lib/CodeGen/LiveDebugValues.cpp

 /// VarLocMap, giving each VarLoc a unique index. Rather than operate directly
 /// on machine locations, the dataflow analysis in this pass identifies
 /// locations by their index in the VarLocMap, meaning all the variable
 /// locations in a block can be described by a sparse vector of VarLocMap
 /// indexes.
 ///
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/CoalescingBitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/UniqueVector.h"
 #include "llvm/CodeGen/LexicalScopes.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
   Register Reg = Op.getReg();
 
   return Reg && Reg != SP && Reg != FP;
 }
 
 namespace {
 
 using DefinedRegsSet = SmallSet<Register, 32>;
+using VarLocSet = CoalescingBitVector<uint64_t>;
 
 /// 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;
 
   LocIndex(uint32_t Location, uint32_t Index)
       : Location(Location), Index(Index) {}
 
   uint64_t getAsRawInteger() const {
     return (static_cast<uint64_t>(Location) << 32) | Index;
   }
 
   static LocIndex fromRawInteger(uint64_t ID) {
     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();
+  }
 };
 
 class LiveDebugValues : public MachineFunctionPass {
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
+  VarLocSet::Allocator Alloc;
 
   enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
 
   /// Keeps track of lexical scopes associated with a user value's source
   /// location.
   class UserValueScopes {
     DebugLoc DL;
     LexicalScopes &LS;
#endif
 
     /// This operator guarantees that VarLocs are sorted by Variable first.
     bool operator<(const VarLoc &Other) const {
       return std::tie(Var, Kind, Loc.Hash, Expr) <
              std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
     }
   };
 
+  /// 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 {
-    UniqueVector<VarLoc> VarLocs;
+    /// 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;
 
   public:
+    /// Retrieve a unique LocIndex for \p VL.
     LocIndex insert(const VarLoc &VL) {
-      uint32_t Index = VarLocs.insert(VL);
-      return {0, Index};
+      uint32_t Location = VL.isDescribedByReg();
+      uint32_t &Index = Var2Index[VL];
+      if (!Index) {
+        auto &Vars = Loc2Vars[Location];
+        Vars.push_back(VL);
+        Index = Vars.size();
+      }
+      return {Location, Index - 1};
     }
 
-    const VarLoc &operator[](LocIndex ID) const { return VarLocs[ID.Index]; }
+    /// Retrieve the unique VarLoc associated with \p ID.
+    const VarLoc &operator[](LocIndex ID) const {
+      auto LocIt = Loc2Vars.find(ID.Location);
+      assert(LocIt != Loc2Vars.end() && "Location not tracked");
+      return LocIt->second[ID.Index];
+    }
   };
 
-  using VarLocSet = SparseBitVector<>;
   using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
   struct TransferDebugPair {
-    MachineInstr *TransferInst; /// Instruction where this transfer occurs.
-    LocIndex LocationID;        /// Location number for the transfer dest.
+    MachineInstr *TransferInst; ///< Instruction where this transfer occurs.
+    LocIndex LocationID;        ///< Location number for the transfer dest.
   };
   using TransferMap = SmallVector<TransferDebugPair, 4>;
 
   // Types for recording sets of variable fragments that overlap. For a given
   // local variable, we record all other fragments of that variable that could
   // overlap it, to reduce search time.
   using FragmentOfVar =
       std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
class OpenRangesSet {
     VarLocSet VarLocs;
     // Map the DebugVariable to recent primary location ID.
     SmallDenseMap<DebugVariable, LocIndex, 8> Vars;
     // Map the DebugVariable to recent backup location ID.
     SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars;
     OverlapMap &OverlappingFragments;
 
   public:
-    OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {}
+    OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap)
+        : VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
 
     const VarLocSet &getVarLocs() const { return VarLocs; }
 
     /// Terminate all open ranges for VL.Var by removing it from the set.
     void erase(const VarLoc &VL);
 
     /// Terminate all open ranges listed in \c KillSet by removing
     /// them from the set.
public:
     bool empty() const {
       assert(Vars.empty() == EntryValuesBackupVars.empty() &&
              Vars.empty() == VarLocs.empty() &&
              "open ranges are inconsistent");
       return VarLocs.empty();
     }
   };
 
+  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs which are located
+  /// in \p Reg, of kind RegisterKind. Insert collected IDs in \p Collected.
+  void collectIDsForReg(VarLocSet &Collected, uint32_t Reg,
+                        const VarLocSet &CollectFrom) const;
+
+  /// Get the registers which are used by VarLocs of kind RegisterKind tracked
+  /// by \p CollectFrom.
+  void getUsedRegs(const VarLocSet &CollectFrom,
+                   SmallVectorImpl<uint32_t> &UsedRegs) const;
+
+  VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
+    auto Result = Locs.try_emplace(MBB, Alloc);
+    return Result.first->second;
+  }
+
+  const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB,
+                                   const VarLocInMBB &Locs) const {
+    auto It = Locs.find(MBB);
+    assert(It != Locs.end() && "MBB not in map");
+    return It->second;
+  }
+
   /// Tests whether this instruction is a spill to a stack location.
   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
 
   /// Decide if @MI is a spill instruction and return true if it is. We use 2
   /// criteria to make this decision:
   /// - Is this instruction a store to a spill slot?
   /// - Is there a register operand that is both used and killed?
   /// TODO: Store optimization can fold spills into other stores (including
#endif
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                   VarLocMap &VarLocIDs, TransferMap &Transfers);
   bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                         VarLocMap &VarLocIDs, const VarLoc &EntryVL);
   void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
                        VarLocMap &VarLocIDs, TransferMap &Transfers,
-                       SparseBitVector<> &KillSet);
+                       VarLocSet &KillSet);
   void recordEntryValue(const MachineInstr &MI,
                         const DefinedRegsSet &DefinedRegs,
                         OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
   void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
                             VarLocMap &VarLocIDs, TransferMap &Transfers);
   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
                            VarLocMap &VarLocIDs, TransferMap &Transfers);
   bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,

 LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
   auto It = EntryValuesBackupVars.find(Var);
   if (It != EntryValuesBackupVars.end())
     return It->second;
 
   return llvm::None;
 }
 
+void LiveDebugValues::collectIDsForReg(VarLocSet &Collected, uint32_t Reg,
+                                       const VarLocSet &CollectFrom) const {
+  // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all
+  // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg.
+  uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg);
+  uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1);
+  // Iterate through that half-open interval and collect all the set IDs.
+  for (auto It = CollectFrom.find(FirstIndexForReg), End = CollectFrom.end();
+       It != End && *It < FirstInvalidIndex; ++It)
+    Collected.set(*It);
+}
+
+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();
+       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);
+
+    // Skip to the next /set/ register. Note that this finds a lower bound, so
+    // even if there aren't any VarLocs living in `FoundReg+1`, we're still
+    // guaranteed to move on to the next register (or to end()).
+    uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1);
+    It = CollectFrom.find(NextRegIndex);
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
 void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
                                        const VarLocInMBB &V,
                                        const VarLocMap &VarLocIDs,
                                        const char *msg,
                                        raw_ostream &Out) const {
   Out << '\n' << msg << '\n';
   for (const MachineBasicBlock &BB : MF) {
-    const VarLocSet &L = V.lookup(&BB);
+    if (!V.count(&BB))
+      continue;
+    const VarLocSet &L = getVarLocsInMBB(&BB, V);
     if (L.empty())
       continue;
     Out << "MBB: " << BB.getNumber() << ":\n";
     for (uint64_t VLL : L) {
       const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
       Out << " Var: " << VL.Var.getVariable()->getName();
       Out << " MI: ";
       VL.dump(TRI, Out);
void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
   }
 }
 
 /// Turn the entry value backup locations into primary locations.
 void LiveDebugValues::emitEntryValues(MachineInstr &MI,
                                       OpenRangesSet &OpenRanges,
                                       VarLocMap &VarLocIDs,
                                       TransferMap &Transfers,
-                                      SparseBitVector<> &KillSet) {
+                                      VarLocSet &KillSet) {
   for (uint64_t ID : KillSet) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
     const VarLoc &VL = VarLocIDs[Idx];
     if (!VL.Var.getVariable()->isParameter())
       continue;
 
     auto DebugVar = VL.Var;
     Optional<LocIndex> EntryValBackupID =
void LiveDebugValues::transferRegisterDef(
   // Meta Instructions do not affect the debug liveness of any register they
   // define.
   if (MI.isMetaInstruction())
     return;
 
   MachineFunction *MF = MI.getMF();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
-  SparseBitVector<> KillSet;
+
+  // Find the regs killed by MI, and find regmasks of preserved regs.
   // Max out the number of statically allocated elements in `DeadRegs`, as this
-  // prevents fallback to std::set::count() operations. As often as possible, we
-  // want a linear scan here.
-  SmallSet<unsigned, 32> DeadRegs;
-  SmallVector<const uint32_t *, 4> DeadRegMasks;
+  // prevents fallback to std::set::count() operations.
+  SmallSet<uint32_t, 32> DeadRegs;
+  SmallVector<const uint32_t *, 4> RegMasks;
   for (const MachineOperand &MO : MI.operands()) {
-    // Determine whether the operand is a register def.  Assume that call
-    // instructions never clobber SP, because some backends (e.g., AArch64)
-    // never list SP in the regmask.
+    // Determine whether the operand is a register def.
     if (MO.isReg() && MO.isDef() && MO.getReg() &&
         Register::isPhysicalRegister(MO.getReg()) &&
         !(MI.isCall() && MO.getReg() == SP)) {
-      // Remove ranges of all aliased registers. Note: the actual removal is
-      // done after we finish visiting MachineOperands, for performance reasons.
+      // Remove ranges of all aliased registers.
       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
         // FIXME: Can we break out of this loop early if no insertion occurs?
         DeadRegs.insert(*RAI);
     } else if (MO.isRegMask()) {
-      // Remove ranges of all clobbered registers. Register masks don't usually
-      // list SP as preserved.  While the debug info may be off for an
-      // instruction or two around callee-cleanup calls, transferring the
-      // DEBUG_VALUE across the call is still a better user experience. Note:
-      // the actual removal is done after we finish visiting MachineOperands,
-      // for performance reasons.
-      DeadRegMasks.push_back(MO.getRegMask());
+      RegMasks.push_back(MO.getRegMask());
     }
   }
-  // For performance reasons, it's critical to iterate over the open var locs
-  // at most once.
-  for (uint64_t ID : OpenRanges.getVarLocs()) {
-    LocIndex Idx = LocIndex::fromRawInteger(ID);
-    unsigned Reg = VarLocIDs[Idx].isDescribedByReg();
-    if (!Reg)
-      continue;
 
-    if (DeadRegs.count(Reg)) {
-      KillSet.set(ID);
+  // Erase VarLocs which reside in one of the dead registers. For performance
+  // reasons, it's critical to not iterate over the full set of open VarLocs.
+  // Iterate over the set of dying/used regs instead.
+  VarLocSet KillSet(Alloc);
+  for (uint32_t DeadReg : DeadRegs)
+    collectIDsForReg(KillSet, DeadReg, OpenRanges.getVarLocs());
+  if (!RegMasks.empty()) {
+    SmallVector<uint32_t, 32> UsedRegs;
+    getUsedRegs(OpenRanges.getVarLocs(), UsedRegs);
+    for (uint32_t Reg : UsedRegs) {
+      // The VarLocs residing in this register are already in the kill set.
+      if (DeadRegs.count(Reg))
         continue;
-    }
 
+      // Remove ranges of all clobbered registers. Register masks don't usually
+      // list SP as preserved. Assume that call instructions never clobber SP,
+      // because some backends (e.g., AArch64) never list SP in the regmask.
+      // While the debug info may be off for an instruction or two around
+      // callee-cleanup calls, transferring the DEBUG_VALUE across the call is
+      // still a better user experience.
       if (Reg == SP)
         continue;
       bool AnyRegMaskKillsReg =
-        any_of(DeadRegMasks, [Reg](const uint32_t *RegMask) {
+          any_of(RegMasks, [Reg](const uint32_t *RegMask) {
             return MachineOperand::clobbersPhysReg(RegMask, Reg);
           });
       if (AnyRegMaskKillsReg)
-      KillSet.set(ID);
+        collectIDsForReg(KillSet, Reg, OpenRanges.getVarLocs());
+    }
   }
   OpenRanges.erase(KillSet, VarLocIDs);
 
   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.EnableDebugEntryValues)
       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
   }
void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI,
   unsigned Reg;
   Optional<VarLoc::SpillLoc> Loc;
 
   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;
+  VarLocSet KillSet(Alloc);
   if (isSpillInstruction(MI, MF)) {
     Loc = extractSpillBaseRegAndOffset(MI);
     for (uint64_t ID : OpenRanges.getVarLocs()) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       const VarLoc &VL = VarLocIDs[Idx];
       if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) {
         // This location is overwritten by the current instruction -- terminate
         // the open range, and insert an explicit DBG_VALUE $noreg.
bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB,
   bool Changed = false;
 
   LLVM_DEBUG(for (uint64_t ID
                   : OpenRanges.getVarLocs()) {
     // Copy OpenRanges to OutLocs, if not already present.
     dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
     VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI);
   });
-  VarLocSet &VLS = OutLocs[CurMBB];
+  VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
   Changed = VLS != OpenRanges.getVarLocs();
   // New OutLocs set may be different due to spill, restore or register
   // copy instruction processing.
   if (Changed)
     VLS = OpenRanges.getVarLocs();
   OpenRanges.clear();
   return Changed;
 }
bool LiveDebugValues::join(
     MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
     const VarLocMap &VarLocIDs,
     SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
     SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks,
     VarLocInMBB &PendingInLocs) {
   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
   bool Changed = false;
 
-  VarLocSet InLocsT; // Temporary incoming locations.
+  VarLocSet InLocsT(Alloc); // Temporary incoming locations.
 
   // For all predecessors of this MBB, find the set of VarLocs that
   // can be joined.
   int NumVisited = 0;
   for (auto p : MBB.predecessors()) {
     // Ignore backedges if we have not visited the predecessor yet. As the
     // predecessor hasn't yet had locations propagated into it, most locations
     // will not yet be valid, so treat them as all being uninitialized and
LLVM_DEBUG({
                  << "\n";
       }
     });
 
     NumVisited++;
   }
 
   // Filter out DBG_VALUES that are out of scope.
-  VarLocSet KillSet;
+  VarLocSet KillSet(Alloc);
   bool IsArtificial = ArtificialBlocks.count(&MBB);
   if (!IsArtificial) {
     for (uint64_t ID : InLocsT) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       if (!VarLocIDs[Idx].dominates(MBB)) {
         KillSet.set(ID);
         LLVM_DEBUG({
           auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
         });
       }
     }
   }
   InLocsT.intersectWithComplement(KillSet);
 
   // As we are processing blocks in reverse post-order we
   // should have processed at least one predecessor, unless it
   // is the entry block which has no predecessor.
   assert((NumVisited || MBB.pred_empty()) &&
          "Should have processed at least one predecessor");
 
-  VarLocSet &ILS = InLocs[&MBB];
-  VarLocSet &Pending = PendingInLocs[&MBB];
+  VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs);
+  VarLocSet &Pending = getVarLocsInMBB(&MBB, PendingInLocs);
 
   // New locations will have DBG_VALUE insts inserted at the start of the
   // block, after location propagation has finished. Record the insertions
   // that we need to perform in the Pending set.
   VarLocSet Diff = InLocsT;
   Diff.intersectWithComplement(ILS);
-  for (auto ID : Diff) {
-    Pending.set(ID);
-    ILS.set(ID);
-    ++NumInserted;
-    Changed = true;
-  }
+  Pending.set(Diff);
+  ILS.set(Diff);
+  NumInserted += Diff.count();
+  Changed |= !Diff.empty();
 
   // We may have lost locations by learning about a predecessor that either
   // loses or moves a variable. Find any locations in ILS that are not in the
   // new in-locations, and delete those.
   VarLocSet Removed = ILS;
   Removed.intersectWithComplement(InLocsT);
-  for (auto ID : Removed) {
-    Pending.reset(ID);
-    ILS.reset(ID);
-    ++NumRemoved;
-    Changed = true;
-  }
+  Pending.intersectWithComplement(Removed);
+  ILS.intersectWithComplement(Removed);
+  NumRemoved += Removed.count();
+  Changed |= !Removed.empty();
 
   return Changed;
 }
 
 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 
   bool Changed = false;
   bool OLChanged = false;
   bool MBBJoined = false;
 
   VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
   OverlapMap OverlapFragments; // Map of overlapping variable fragments.
-  OpenRangesSet OpenRanges(OverlapFragments);
+  OpenRangesSet OpenRanges(Alloc, OverlapFragments);
                               // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
   VarLocInMBB InLocs;         // Ranges that are incoming after joining.
   TransferMap Transfers;      // DBG_VALUEs associated with transfers (such as
                               // spills, copies and restores).
   VarLocInMBB PendingInLocs;  // Ranges that are incoming after joining, but
                               // that we have deferred creating DBG_VALUE insts
                               // for immediately.
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   for (auto &MI : First_MBB) {
     collectRegDefs(MI, DefinedRegs, TRI);
       if (MI.isDebugValue())
         recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs);
   }
 
   // Initialize per-block structures and scan for fragment overlaps.
   for (auto &MBB : MF) {
-    PendingInLocs[&MBB] = VarLocSet();
+    PendingInLocs.try_emplace(&MBB, Alloc);
 
     for (auto &MI : MBB) {
       if (MI.isDebugValue())
         accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
     }
   }
 
   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
while (!Worklist.empty()) {
       MBBJoined |= Visited.insert(MBB).second;
       if (MBBJoined) {
         MBBJoined = false;
         Changed = true;
         // Now that we have started to extend ranges across BBs we need to
         // examine spill, copy and restore instructions to see whether they
         // operate with registers that correspond to user variables.
         // First load any pending inlocs.
-        OpenRanges.insertFromLocSet(PendingInLocs[MBB], VarLocIDs);
+        OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, PendingInLocs),
+                                    VarLocIDs);
         for (auto &MI : *MBB)
           process(MI, OpenRanges, VarLocIDs, Transfers);
         OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
 
         LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
                                     "OutLocs after propagating", dbgs()));
         LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
                                     "InLocs after propagating", dbgs()));

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

 # RUN: llc -debug-entry-values -run-pass=livedebugvalues -march=x86-64 -o - %s | FileCheck %s
 #
 # The test case was artificially adjusted, in order to make proper diamond basic
 # block structure relevant to the debug entry values propagation.
 #
 # CHECK: ![[ARG_B:.*]] = !DILocalVariable(name: "b"
+# CHECK: ![[ARG_C:.*]] = !DILocalVariable(name: "c"
+# CHECK: ![[ARG_Q:.*]] = !DILocalVariable(name: "q"
 # CHECK: bb.0.entry
 # CHECK: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression()
 # CHECK: bb.1.if.then
 # 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 5
 # CHECK-NEXT: $ebx = MOV32ri 1
 # CHECK-NEXT: DBG_VALUE $esi, $noreg, ![[ARG_B]], !DIExpression(DW_OP_LLVM_entry_value, 1)
 # 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)
-#
 --- |
   ; 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/test/DebugInfo/MIR/X86/multiple-param-dbg-value-entry.mir

 # RUN: llc -debug-entry-values -run-pass=livedebugvalues -march=x86-64 -o - %s| FileCheck %s
 #
 #int global;
 #int foo(int p, int q, int r) {
 #  global = p + 1;
 #  asm __volatile("" : : : "edi", "esi", "edx");
 #  return 123;
 #}
 #
 # Verify that DW_OP_LLVM_entry_values are generated for parameters with multiple
 # DBG_VALUEs at entry block.
 # CHECK: DBG_VALUE $edi, $noreg, !{{.*}}, !DIExpression(DW_OP_LLVM_entry_value, 1), debug-location {{.*}}
-# CHECK: DBG_VALUE $edx, $noreg, !{{.*}}, !DIExpression(DW_OP_LLVM_entry_value, 1), debug-location {{.*}}
 # CHECK: DBG_VALUE $esi, $noreg, !{{.*}}, !DIExpression(DW_OP_LLVM_entry_value, 1), debug-location {{.*}}
+# CHECK: DBG_VALUE $edx, $noreg, !{{.*}}, !DIExpression(DW_OP_LLVM_entry_value, 1), debug-location {{.*}}
 
 --- |
   ; ModuleID = 'multiple-param-dbg-value-entry.ll'
   source_filename = "multiple-param-dbg-value-entry.c"
   target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
   @global = common dso_local local_unnamed_addr global i32 0, align 4, !dbg !0