PR26055: [WIP] Speed up LiveDebugValues::transferRegisterDef()

[aprantl]

Summary

This is a work-in-progress that I wanted to throw it out there to solicit opinions.

This patch builds upon http://reviews.llvm.org/D20178 + http://reviews.llvm.org/D20636 and improves LiveDebugValues::transferRegisterDef() by adding a BitVector tracking the registers holding DebugVariables.
Note that even though we can efficiently calculate the set of clobbered registers, we are still iterating over all OpenRanges to find which VarLocs are associated with these registers.

This has no dramatic impact on the overall runtime. In my large ASAN benchmark we get a 500ms improvement on LiveDebugValues::runOnMachineFunction() out of ~7s total. However, all benchmarks are now dominated by the subsequent run of DbgValueHistoryCalculator, which takes ~55s in the same benchmark.

[aprantl]

Rebased on trunk.

[aprantl]

This makes the code harder to read and does not improve performance significantly. Abandoning for now.

lib/CodeGen/LiveDebugValues.cpp

bool operator<(const VarLoc &Other) const {
       return Var < Other.Var;
     }
   };
 
   typedef UniqueVector<VarLoc> VarLocMap;
   typedef SparseBitVector<> VarLocSet;
   typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
 
-  /// This holds the working set of open ranges. For fast access, this
-  /// is done both as a set of VarLocIDs, and a map of DebugVariable
-  /// to recent VarLocID. Note that a DBG_VALUE ends all previous open
-  /// ranges for the same variable.
+  /// This holds the working set of open ranges. The canonical list is
+  /// implemented as a set of VarLocIDs. Redundant data structures
+  /// exist for optimization purposes:
+  ///
+  /// - For fast access in transferDebugValue() a map from
+  ///   DebugVariable to recent VarLocID is stored.  Note that a
+  ///   DBG_VALUE ends all previous open ranges for the same variable.
+  ///
+  /// - For fast access in transferRegisterDef, a bitvector of
+  ///   registers holding DebugVariables is stored.
   struct VarLocList {
     VarLocSet VarLocs;
     SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
+    BitVector Regs;
+    VarLocList(unsigned NumRegs) : Regs(NumRegs) {}
     void clear() {
       VarLocs.clear();
       Vars.clear();
+      Regs.reset();
     }
   };
 
   void transferDebugValue(const MachineInstr &MI, VarLocList &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges,
                            const VarLocMap &VarLocIDs);
   bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
   auto OR = OpenRanges.Vars.find(V);
   if (OR != OpenRanges.Vars.end()) {
     unsigned ID = OR->second;
     OpenRanges.Vars.erase(OR);
     OpenRanges.VarLocs.reset(ID);
   }
   // Add the VarLoc to OpenRanges from this DBG_VALUE.
   // TODO: Currently handles DBG_VALUE which has only reg as location.
-  if (isDbgValueDescribedByReg(MI)) {
+  if (unsigned RegNo = isDbgValueDescribedByReg(MI)) {
     VarLoc VL(MI);
     unsigned ID = VarLocIDs.insert(VL);
     OpenRanges.VarLocs.set(ID);
     OpenRanges.Vars.insert({VL.Var, ID});
+    for (MCRegAliasIterator RAI(RegNo, TRI, true); RAI.isValid(); ++RAI)
+      OpenRanges.Regs.set(*RAI);
   }
 }
 
 /// A definition of a register may mark the end of a range.
 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
                                           VarLocList &OpenRanges,
                                           const VarLocMap &VarLocIDs) {
   MachineFunction *MF = MI.getParent()->getParent();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
-  SparseBitVector<> KillSet;
+  BitVector ClobberedRegs(TRI->getNumRegs());
   for (const MachineOperand &MO : MI.operands()) {
     if (MO.isReg() && MO.isDef() && MO.getReg() &&
         TRI->isPhysicalRegister(MO.getReg())) {
       // Remove ranges of all aliased registers.
-      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
-        for (unsigned ID : OpenRanges.VarLocs)
-          if (VarLocIDs[ID].isDescribedByReg() == *RAI)
-            KillSet.set(ID);
+      ClobberedRegs.set(MO.getReg());
     } 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.VarLocs) {
-        unsigned Reg = VarLocIDs[ID].isDescribedByReg();
-        if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
-          KillSet.set(ID);
-      }
-    }
+      BitVector Mask(TRI->getNumRegs());
+      Mask.setBitsNotInMask(MO.getRegMask());
+      Mask.reset(SP);
+      ClobberedRegs |= Mask;
+
+  // Remove ranges of all clobbered registers.
+  VarLocSet KillSet;
+  ClobberedRegs &= OpenRanges.Regs;
+  if (ClobberedRegs.any())
+    for (unsigned ID : OpenRanges.VarLocs)
+      if (unsigned RegNo = VarLocIDs[ID].isDescribedByReg())
+        for (MCRegAliasIterator RAI(RegNo, TRI, true); RAI.isValid(); ++RAI)
+          if (ClobberedRegs[*RAI]) {
+            OpenRanges.Regs.reset(*RAI);
+            OpenRanges.Vars.erase(VarLocIDs[ID].Var);
+            KillSet.set(ID);
           }
   OpenRanges.VarLocs.intersectWithComplement(KillSet);
-  for (unsigned ID : KillSet)
-    OpenRanges.Vars.erase(VarLocIDs[ID].Var);
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
                                              VarLocList &OpenRanges,
                                              VarLocInMBB &OutLocs,
                                              const VarLocMap &VarLocIDs) {
   bool Changed = false;
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
 
   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.
-  VarLocList OpenRanges; // Ranges that are open until end of bb.
+  VarLocList OpenRanges(TRI->getNumRegs()); // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;   // Ranges that exist beyond bb.
   VarLocInMBB InLocs;    // Ranges that are incoming after joining.
 
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist;