[LiveDebugValues] Visit open var locs just once in transferRegisterDef, NFC

[vsk]

Summary

For a file in WebKit, this brings the time spent in LiveDebugValues down
from 16 minutes to 2 minutes. The reduction comes from iterating the set
of open variable locations just once in transferRegisterDef. Post-patch,
the most expensive item inside of transferRegisterDef is a call to
VarLoc::isDescribedByReg, which we have to do.

Testing: I built LNT using the Os-g cmake cache with & without this
patch, then diffed the object files to verify there was no binary diff.

rdar://59446577

[vsk]

(for reference, MachineCSE takes 4 minutes on this file...)

[vsk]

• Exit early if Reg is undef.

[jmorse]

LGTM,

/me rustles around some drawers,

I've uploaded D74706 which might be relevant to your interests. We've run into similar performance problems, but caused by hoards of DBG_VALUEs rather than by many clobbered registers, and indexing VarMap by machine location gave a significant compile-time performance improvement at the expense of some memory. I can prioritise getting it landed if you think it'd be useful.

Note that it doesn't address register masks, as we don't see many of those on x86.

llvm/lib/CodeGen/LiveDebugValues.cpp

935

Could we replace "inline" with "statically allocated" or something similar? Seeing "inline" here immediately makes me think of function-inlining (which is a relevant topic in LiveDebugValues), and confused me for a bit.

[vsk]

In D74633#1878889, @jmorse wrote:

LGTM,

/me rustles around some drawers,

I've uploaded D74706 which might be relevant to your interests. We've run into similar performance problems, but caused by hoards of DBG_VALUEs rather than by many clobbered registers, and indexing VarMap by machine location gave a significant compile-time performance improvement at the expense of some memory. I can prioritise getting it landed if you think it'd be useful.

This is very interesting, thank you for sharing. I think I explored a substantially similar approach, and decided that it wouldn't really work until we make iterating over VarLocSet /much/ faster. I've left comments in D74706.

llvm/lib/CodeGen/LiveDebugValues.cpp

935

Yes, I'll fix this before committing.

llvm/lib/CodeGen/LiveDebugValues.cpp

void LiveDebugValues::transferRegisterDef(
   // define.
   if (MI.isMetaInstruction())
     return;
 
   MachineFunction *MF = MI.getMF();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
   SparseBitVector<> KillSet;
+  // 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;
   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.
     if (MO.isReg() && MO.isDef() && MO.getReg() &&
         Register::isPhysicalRegister(MO.getReg()) &&
         !(MI.isCall() && MO.getReg() == SP)) {
-      // Remove ranges of all aliased registers.
+      // Remove ranges of all aliased registers. Note: the actual removal is
+      // done after we finish visiting MachineOperands, for performance reasons.
       for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
-        for (unsigned ID : OpenRanges.getVarLocs())
-          if (VarLocIDs[ID].isDescribedByReg() == *RAI)
-            KillSet.set(ID);
+        // 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.
-      for (unsigned ID : OpenRanges.getVarLocs()) {
-        unsigned Reg = VarLocIDs[ID].isDescribedByReg();
-        if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
-          KillSet.set(ID);
-      }
-    }
+      // 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());
+    }
+  }
+  // For performance reasons, it's critical to iterate over the open var locs
+  // at most once.
+    if (!Reg)
+      continue;
+
+    if (DeadRegs.count(Reg)) {
+      continue;
+
+    if (Reg == SP)
+      continue;
+    bool AnyRegMaskKillsReg =
+        any_of(DeadRegMasks, [Reg](const uint32_t *RegMask) {
+          return MachineOperand::clobbersPhysReg(RegMask, Reg);
+        });
+    if (AnyRegMaskKillsReg)
+      KillSet.set(ID);
   }
   OpenRanges.erase(KillSet, VarLocIDs);
 
   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.EnableDebugEntryValues)
       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
   }