PR26055: Speed up LiveDebugValues::transferDebugValue()

[aprantl]

Summary

This patch builds upon http://reviews.llvm.org/D20178 and speeds up LiveDebugValues::transferDebugValue() by adding an index that maps each DebugVariable to its open VarLoc.

The transferDebugValue() function needs to close all open ranges for a given DebugVariable. Iterating over the set bits of OpenRanges is prohibitively slow in practice. I experimented with using the sorted map of VarLocs in the UniqueVector to iterate only over the range of VarLocs with a given DebugVariable, but the binary search turned out to be even more expensive than just iterating over the set bits in OpenRanges.
Instead, this patch exploits the fact that there can only be one open location for each DebugVariable and redundantly stores this location in a DenseMap.

Benchmarks:
bench1: The ASAN -O3 example I've been testing with.
bench2: The bitcode from PR26055 at -O0.

Baseline (D20178):
bench1: user 2m43.600s
bench2: user 1m0.948s

This patch:
bench1: user 1m6.725s
bench2: user 0m21.452s

[dblaikie]

Given this is a time/space tradeoff, it might be worth having the space
numbers as well just to demonstrate that it's a good tradeoff?

[aprantl]

In D20636#440225, @dblaikie wrote:

Given this is a time/space tradeoff, it might be worth having the space
numbers as well just to demonstrate that it's a good tradeoff?

This adds one DenseMap entry (16 bytes index + 4 bytes payload) per local (inlined) variable in a single function. In my large benchmark with the >4000 DBG_VALUEs this was below the noise threshold. Peak memory usage seems to fluctuate by ~ 4MB on repeat runs on my machine.

[• dberlin]

lib/CodeGen/LiveDebugValues.cpp

294

Would you mind simply abstracting this into a openrange class (or something), so that the code to maintain the set/hash happens under the covers and this is just insert/find/erase?

(If this is really difficult or something, feel free to explain why and we can punt :P)

[aprantl]

Address review comments: Add an OpenRangesSet class that hides the dual nature of VarLocList behind a set-like interface.

[• dberlin]

Looks good to me. Thanks so much for working on this.

[aprantl]

Thanks! Landed as r270923.

lib/CodeGen/LiveDebugValues.cpp

 }
 
 class LiveDebugValues : public MachineFunctionPass {
 
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
 
+  /// Based on std::pair so it can be used as an index into a DenseMap.
   typedef std::pair<const DILocalVariable *, const DILocation *>
-      InlinedVariable;
-
+      DebugVariableBase;
   /// A potentially inlined instance of a variable.
-  struct DebugVariable {
-    const DILocalVariable *Var;
-    const DILocation *InlinedAt;
+  struct DebugVariable : public DebugVariableBase {
+    DebugVariable(const DILocalVariable *Var, const DILocation *InlinedAt)
+        : DebugVariableBase(Var, InlinedAt) {}
 
-    DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt)
-        : Var(_var), InlinedAt(_inlinedAt) {}
+    const DILocalVariable *getVar() const { return this->first; };
+    const DILocation *getInlinedAt() const { return this->second; };
 
     bool operator<(const DebugVariable &DV) const {
-      if (Var == DV.Var)
-        return InlinedAt < DV.InlinedAt;
-      return Var < DV.Var;
-    }
-
-    bool operator==(const DebugVariable &DV) const {
-      return (Var == DV.Var) && (InlinedAt == DV.InlinedAt);
+      if (getVar() == DV.getVar())
+        return getInlinedAt() < DV.getInlinedAt();
+      return getVar() < DV.getVar();
     }
   };
 
   /// A pair of debug variable and value location.
   struct VarLoc {
     const DebugVariable Var;
     const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE.
 
struct VarLoc {
     }
 
     void dump() const { MI.dump(); }
 
     bool operator==(const VarLoc &Other) const {
       return Var == Other.Var && Loc.Hash == Other.Loc.Hash;
     }
 
+    /// This operator guarantees that VarLocs are sorted by Variable first.
     bool operator<(const VarLoc &Other) const {
       if (Var == Other.Var)
         return Loc.Hash < Other.Loc.Hash;
       return Var < Other.Var;
     }
   };
 
   typedef UniqueVector<VarLoc> VarLocMap;
-  typedef SparseBitVector<> VarLocList;
   typedef SparseBitVector<> VarLocSet;
   typedef SmallDenseMap<const MachineBasicBlock *, VarLocSet> VarLocInMBB;
 
-  void transferDebugValue(const MachineInstr &MI, VarLocList &OpenRanges,
+  /// This holds the working set of currently 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.
+  class OpenRangesSet {
+    VarLocSet VarLocs;
+    SmallDenseMap<DebugVariableBase, unsigned, 8> Vars;
+
+  public:
+    const VarLocSet &getVarLocs() const { return VarLocs; }
+
+    /// Terminate all open ranges for Var by removing it from the set.
+    void erase(DebugVariable Var) {
+      auto It = Vars.find(Var);
+      if (It != Vars.end()) {
+        unsigned ID = It->second;
+        VarLocs.reset(ID);
+        Vars.erase(It);
+      }
+    }
+
+    /// Terminate all open ranges listed in \c KillSet by removing
+    /// them from the set.
+    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) {
+      VarLocs.intersectWithComplement(KillSet);
+      for (unsigned ID : KillSet)
+        Vars.erase(VarLocIDs[ID].Var);
+    }
+
+    /// Insert a new range into the set.
+    void insert(unsigned VarLocID, DebugVariableBase Var) {
+      VarLocs.set(VarLocID);
+      Vars.insert({Var, VarLocID});
+    }
+
+    /// Empty the set.
+    void clear() {
+      VarLocs.clear();
+      Vars.clear();
+    }
+
+    /// Return whether the set is empty or not.
+    bool empty() const {
+      assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent");
+      return VarLocs.empty();
+    }
+  };
+
+  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                           VarLocMap &VarLocIDs);
-  void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges,
+  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
                            const VarLocMap &VarLocIDs);
-  bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges,
+  bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                               VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
-  bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs,
-                VarLocMap &VarLocIDs);
+  bool transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
+                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs);
 
   bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
             const VarLocMap &VarLocIDs);
 
   bool ExtendRanges(MachineFunction &MF);
 
 public:
   static char ID;
void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF,
                                        const VarLocMap &VarLocIDs,
                                        const char *msg,
                                        raw_ostream &Out) const {
   for (const MachineBasicBlock &BB : MF) {
     const auto &L = V.lookup(&BB);
     Out << "MBB: " << BB.getName() << ":\n";
     for (unsigned VLL : L) {
       const VarLoc &VL = VarLocIDs[VLL];
-      Out << " Var: " << VL.Var.Var->getName();
+      Out << " Var: " << VL.Var.getVar()->getName();
       Out << " MI: ";
       VL.dump();
       Out << "\n";
     }
   }
   Out << "\n";
 }
 
 /// End all previous ranges related to @MI and start a new range from @MI
 /// if it is a DBG_VALUE instr.
 void LiveDebugValues::transferDebugValue(const MachineInstr &MI,
-                                         VarLocList &OpenRanges,
+                                         OpenRangesSet &OpenRanges,
                                          VarLocMap &VarLocIDs) {
   if (!MI.isDebugValue())
     return;
   const DILocalVariable *Var = MI.getDebugVariable();
   const DILocation *DebugLoc = MI.getDebugLoc();
   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
          "Expected inlined-at fields to agree");
 
   // End all previous ranges of Var.
-  SparseBitVector<> KillSet;
-  for (unsigned ID : OpenRanges) {
-    auto &ORVar = VarLocIDs[ID].Var;
-    if (ORVar.Var == Var && ORVar.InlinedAt == InlinedAt)
-      KillSet.set(ID);
-  }
-  OpenRanges.intersectWithComplement(KillSet);
+  DebugVariable V(Var, InlinedAt);
+  OpenRanges.erase(V);
 
   // Add the VarLoc to OpenRanges from this DBG_VALUE.
   // TODO: Currently handles DBG_VALUE which has only reg as location.
-  if (isDbgValueDescribedByReg(MI))
-    OpenRanges.set(VarLocIDs.insert(MI));
+  if (isDbgValueDescribedByReg(MI)) {
+    VarLoc VL(MI);
+    unsigned ID = VarLocIDs.insert(VL);
+    OpenRanges.insert(ID, VL.Var);
+  }
 }
 
 /// A definition of a register may mark the end of a range.
 void LiveDebugValues::transferRegisterDef(MachineInstr &MI,
-                                          VarLocList &OpenRanges,
+                                          OpenRangesSet &OpenRanges,
                                           const VarLocMap &VarLocIDs) {
   MachineFunction *MF = MI.getParent()->getParent();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
   SparseBitVector<> KillSet;
   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)
+        for (unsigned ID : OpenRanges.getVarLocs())
           if (VarLocIDs[ID].isDescribedByReg() == *RAI)
             KillSet.set(ID);
     } 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) {
+      for (unsigned ID : OpenRanges.getVarLocs()) {
         unsigned Reg = VarLocIDs[ID].isDescribedByReg();
         if (Reg && Reg != SP && MO.clobbersPhysReg(Reg))
           KillSet.set(ID);
       }
     }
   }
-  OpenRanges.intersectWithComplement(KillSet);
+  OpenRanges.erase(KillSet, VarLocIDs);
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI,
-                                             VarLocList &OpenRanges,
+                                             OpenRangesSet &OpenRanges,
                                              VarLocInMBB &OutLocs,
                                              const VarLocMap &VarLocIDs) {
   bool Changed = false;
   const MachineBasicBlock *CurMBB = MI.getParent();
   if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back())))
     return false;
 
   if (OpenRanges.empty())
     return false;
 
-  DEBUG(for (unsigned ID
-             : OpenRanges) {
+  DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) {
           // Copy OpenRanges to OutLocs, if not already present.
-    dbgs() << "Add to OutLocs: ";
-    VarLocIDs[ID].dump();
+          dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump();
         });
   VarLocSet &VLS = OutLocs[CurMBB];
-  Changed = VLS |= OpenRanges;
+  Changed = VLS |= OpenRanges.getVarLocs();
   OpenRanges.clear();
   return Changed;
 }
 
 /// This routine creates OpenRanges and OutLocs.
-bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges,
+bool LiveDebugValues::transfer(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                VarLocInMBB &OutLocs, VarLocMap &VarLocIDs) {
   bool Changed = false;
   transferDebugValue(MI, OpenRanges, VarLocIDs);
   transferRegisterDef(MI, OpenRanges, VarLocIDs);
   Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs);
   return Changed;
 }
 
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.
+  OpenRangesSet OpenRanges; // 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;