[LiveDebugValues] Speed up collectIDsForRegs, NFC

[vsk]

Summary

Use the advanceToLowerBound operation available on CoalescingBitVector
iterators to speed up collection of variables which reside within some
set of registers.

The speedup comes from avoiding repeated top-down traversals in
IntervalMap::find. The linear scan forward from one register interval to
the next is unlikely to be as expensive as a full IntervalMap search
starting from the root.

This reduces time spent in LiveDebugValues when compiling sqlite3 by
200ms (about 0.1% - 0.2% of the total User Time).

Depends on D76466.

rdar://60046261

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

801

This looks redundant? No, the formatting in phabricator was weird. this belongs to the outer loop. I guess you could pull this into the inner loop and then get rid of the It != End &&. Not sure if that is a big improvement.

[jmorse]

LGTM

[vsk]

llvm/lib/CodeGen/LiveDebugValues.cpp

801

Yeah, this is just trying to return early if there aren't any more IDs to find. It may be at End before we enter the inner loop, so I'm not sure it's safe to sink the check from the loop condition.

llvm/lib/CodeGen/LiveDebugValues.cpp

static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
   Register FP = TRI->getFrameRegister(*MF);
   Register Reg = Op.getReg();
 
   return Reg && Reg != SP && Reg != FP;
 }
 
 namespace {
 
+// Max out the number of statically allocated elements in DefinedRegsSet, as
+// this prevents fallback to std::set::count() operations.
 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
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,
+  /// 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;
 
   /// 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) {
     std::unique_ptr<VarLocSet> &VLS = Locs[MBB];

 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,
+void LiveDebugValues::collectIDsForRegs(VarLocSet &Collected,
+                                        const DefinedRegsSet &Regs,
                                         const VarLocSet &CollectFrom) const {
+  assert(!Regs.empty() && "Nothing to collect");
+  SmallVector<uint32_t, 32> SortedRegs;
+  for (Register Reg : Regs)
+    SortedRegs.push_back(Reg);
+  array_pod_sort(SortedRegs.begin(), SortedRegs.end());
+  auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front()));
+  auto End = CollectFrom.end();
+  for (uint32_t Reg : SortedRegs) {
     // 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);
+    It.advanceToLowerBound(FirstIndexForReg);
+
     // 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)
+    for (; It != End && *It < FirstInvalidIndex; ++It)
       Collected.set(*It);
+
+    if (It == End)
+      return;
+  }
 }
 
 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);
+    It.advanceToLowerBound(NextRegIndex);
   }
 }
 
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
 
 #ifndef NDEBUG
void LiveDebugValues::transferRegisterDef(
   if (MI.isMetaInstruction())
     return;
 
   MachineFunction *MF = MI.getMF();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
 
   // 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.
-  SmallSet<uint32_t, 32> DeadRegs;
+  DefinedRegsSet DeadRegs;
   SmallVector<const uint32_t *, 4> RegMasks;
   for (const MachineOperand &MO : MI.operands()) {
     // 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.
       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()) {
       RegMasks.push_back(MO.getRegMask());
     }
   }
 
   // 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(RegMasks, [Reg](const uint32_t *RegMask) {
             return MachineOperand::clobbersPhysReg(RegMask, Reg);
           });
       if (AnyRegMaskKillsReg)
-        collectIDsForReg(KillSet, Reg, OpenRanges.getVarLocs());
+        DeadRegs.insert(Reg);
     }
   }
+
+  if (DeadRegs.empty())
+    return;
+
+  VarLocSet KillSet(Alloc);
+  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
   OpenRanges.erase(KillSet, VarLocIDs);
 
   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.ShouldEmitDebugEntryValues())
       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
   }
 }