[LiveDebugValues] Cache LexicalScopes::getMachineBasicBlocks, NFCI

[vsk]

Summary

Cache the results from getMachineBasicBlocks in LexicalScopes to speed
up UserValueScopes::dominates queries. This replaces the caching done
in UserValueScopes. Compared to the old caching method, this reduces
memory traffic when a VarLoc is copied (e.g. when a VarLocMap grows),
and enables caching across basic blocks.

When compiling sqlite 3.5.7 (CTMark version), this patch reduces the
number of calls to getMachineBasicBlocks from 10,207 to 1,093. I also
measured a small compile-time reduction (~ 0.1% of total wall time, on
average, on my machine).

As a drive-by, I made the DebugLoc in UserValueScopes a const reference
to cut down on MetadataTracking traffic.

[Orlando]

This makes sense to me.

If you're going to subclass and are paying for the callback indirection in LexicalScopes now anyway, would it not make sense to make getMachineBasicBlocks virtual instead of using a callback? Seems like it could be simpler that way but I don't know if one way is better than the other, I'm just curious.

[vsk]

In D80957#2068276, @Orlando wrote:

This makes sense to me.

If you're going to subclass and are paying for the callback indirection in LexicalScopes now anyway, would it not make sense to make getMachineBasicBlocks virtual instead of using a callback? Seems like it could be simpler that way but I don't know if one way is better than the other, I'm just curious.

I think that could work, but I'm not sure it'd be cleaner, since there'd still be a need for some override of dominates() to pass a cached set into getMachineBasicBlocks.

Maybe a simpler approach would be to sink the cache into the LexicalScopes instance? I'll take a stab at this.

[vsk]

Move the caching into LexicalScopes.

[vsk]

Simplify further by deleting the UserValueScopes class, as it no longer holds on to anything interesting.

[Orlando]

llvm/lib/CodeGen/LexicalScopes.cpp

328

I'm not familiar with the extent of the usage of LexicalScopes throughout llvm, so I wonder if there's ever a case where we don't want the caching behaviour. i.e. is it conceivable that the result of dominates should change for the same inputs between calls?

Given this unfamiliarity I probably shouldn't be the one to give the final LGTM on this.

[vsk]

llvm/lib/CodeGen/LexicalScopes.cpp

328

LexicalScopes is used by LiveDebugValues and the debug info generators (it's referenced by DebugHandlerBase). A LexicalScopes instance can't be used to describe a changing MachineFunction, so the result of dominates can't change for the same inputs between calls. Also, the dominates method is currently only used by LiveDebugValues, where the caching seems to be useful.

[Orlando]

llvm/lib/CodeGen/LexicalScopes.cpp

328

That makes sense, thanks!

[jmorse]

LGTM

llvm/include/llvm/CodeGen/LexicalScopes.h

public:
   }
 
   /// getMachineBasicBlocks - Populate given set using machine basic blocks
   /// which have machine instructions that belong to lexical scope identified by
   /// DebugLoc.
   void getMachineBasicBlocks(const DILocation *DL,
                              SmallPtrSetImpl<const MachineBasicBlock *> &MBBs);
 
-  /// dominates - Return true if DebugLoc's lexical scope dominates at least one
-  /// machine instruction's lexical scope in a given machine basic block.
+  /// Return true if DebugLoc's lexical scope dominates at least one machine
+  /// instruction's lexical scope in a given machine basic block.
   bool dominates(const DILocation *DL, MachineBasicBlock *MBB);
 
   /// findLexicalScope - Find lexical scope, either regular or inlined, for the
   /// given DebugLoc. Return NULL if not found.
   LexicalScope *findLexicalScope(const DILocation *DL);
 
   /// getAbstractScopesList - Return a reference to list of abstract scopes.
   ArrayRef<LexicalScope *> getAbstractScopesList() const {
private:
 
   /// AbstractScopesList - Tracks abstract scopes constructed while processing
   /// a function.
   SmallVector<LexicalScope *, 4> AbstractScopesList;
 
   /// CurrentFnLexicalScope - Top level scope for the current function.
   ///
   LexicalScope *CurrentFnLexicalScope = nullptr;
+
+  /// Map a location to the set of basic blocks it dominates. This is a cache
+  /// for \ref LexicalScopes::getMachineBasicBlocks results.
+  using BlockSetT = SmallPtrSet<const MachineBasicBlock *, 4>;
+  DenseMap<const DILocation *, std::unique_ptr<BlockSetT>> DominatedBlocks;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_LEXICALSCOPES_H

llvm/lib/CodeGen/LexicalScopes.cpp

 /// reset - Reset the instance so that it's prepared for another function.
 void LexicalScopes::reset() {
   MF = nullptr;
   CurrentFnLexicalScope = nullptr;
   LexicalScopeMap.clear();
   AbstractScopeMap.clear();
   InlinedLexicalScopeMap.clear();
   AbstractScopesList.clear();
+  DominatedBlocks.clear();
 }
 
 /// initialize - Scan machine function and constuct lexical scope nest.
 void LexicalScopes::initialize(const MachineFunction &Fn) {
   reset();
   // Don't attempt any lexical scope creation for a NoDebug compile unit.
   if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
       DICompileUnit::NoDebug)
void LexicalScopes::getMachineBasicBlocks(
   SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
   for (auto &R : InsnRanges)
     for (auto CurMBBIt = R.first->getParent()->getIterator(),
               EndBBIt = std::next(R.second->getParent()->getIterator());
          CurMBBIt != EndBBIt; CurMBBIt++)
       MBBs.insert(&*CurMBBIt);
 }
 
-/// dominates - Return true if DebugLoc's lexical scope dominates at least one
-/// machine instruction's lexical scope in a given machine basic block.
 bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
   assert(MF && "Unexpected uninitialized LexicalScopes object!");
   LexicalScope *Scope = getOrCreateLexicalScope(DL);
   if (!Scope)
     return false;
 
   // Current function scope covers all basic blocks in the function.
   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
     return true;
 
   // Fetch all the blocks in DLs scope. Because the range / block list also
-  // contain any subscopes, any instruction that DL dominates can be found
-  // in the block set.
-  SmallPtrSet<const MachineBasicBlock *, 32> Set;
-  getMachineBasicBlocks(DL, Set);
-  return Set.count(MBB) != 0;
+  // contain any subscopes, any instruction that DL dominates can be found in
+  // the block set.
+  //
+  // Cache the set of fetched blocks to avoid repeatedly recomputing the set in
+  // the LiveDebugValues pass.
+  std::unique_ptr<BlockSetT> &Set = DominatedBlocks[DL];
+  if (!Set) {
+    Set = std::make_unique<BlockSetT>();
+    getMachineBasicBlocks(DL, *Set);
+  }
+  return Set->count(MBB) != 0;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
   raw_ostream &err = dbgs();
   err.indent(Indent);
   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
   const MDNode *N = Desc;
   err.indent(Indent);

llvm/lib/CodeGen/LiveDebugValues.cpp

private:
   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;
-    SmallPtrSet<const MachineBasicBlock *, 4> LBlocks;
-
-  public:
-    UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {}
-
-    /// Return true if current scope dominates at least one machine
-    /// instruction in a given machine basic block.
-    bool dominates(MachineBasicBlock *MBB) {
-      if (LBlocks.empty())
-        LS.getMachineBasicBlocks(DL, LBlocks);
-      return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB);
-    }
-  };
-
   using FragmentInfo = DIExpression::FragmentInfo;
   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
 
   /// A pair of debug variable and value location.
   struct VarLoc {
     // The location at which a spilled variable resides. It consists of a
     // register and an offset.
     struct SpillLoc {
struct VarLoc {
 
     /// The expression applied to this location.
     const DIExpression *Expr;
 
     /// DBG_VALUE to clone var/expr information from if this location
     /// is moved.
     const MachineInstr &MI;
 
-    mutable UserValueScopes UVS;
+    /// The location where the variable was defined.
+    const DebugLoc &DL;
+
     enum VarLocKind {
       InvalidKind = 0,
       RegisterKind,
       SpillLocKind,
       ImmediateKind,
       EntryValueKind,
       EntryValueBackupKind,
       EntryValueCopyBackupKind
     } Kind = InvalidKind;
 
     /// The value location. Stored separately to avoid repeatedly
     /// extracting it from MI.
     union {
       uint64_t RegNo;
       SpillLoc SpillLocation;
       uint64_t Hash;
       int64_t Immediate;
       const ConstantFP *FPImm;
       const ConstantInt *CImm;
     } Loc;
 
     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
         : Var(MI.getDebugVariable(), MI.getDebugExpression(),
               MI.getDebugLoc()->getInlinedAt()),
-          Expr(MI.getDebugExpression()), MI(MI), UVS(MI.getDebugLoc(), LS) {
+          Expr(MI.getDebugExpression()), MI(MI), DL(MI.getDebugLoc()) {
       static_assert((sizeof(Loc) == sizeof(uint64_t)),
                     "hash does not cover all members of Loc");
       assert(MI.isDebugValue() && "not a DBG_VALUE");
       assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
       if (int RegNo = isDbgValueDescribedByReg(MI)) {
         Kind = RegisterKind;
         Loc.RegNo = RegNo;
       } else if (MI.getOperand(0).isImm()) {
struct VarLoc {
     unsigned isDescribedByReg() const {
       if (Kind == RegisterKind)
         return Loc.RegNo;
       return 0;
     }
 
     /// Determine whether the lexical scope of this value's debug location
     /// dominates MBB.
-    bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); }
+    bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const {
+      return LS.dominates(DL.get(), &MBB);
+    }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     // TRI can be null.
     void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
       dbgs() << "VarLoc(";
       switch (Kind) {
       case RegisterKind:
       case EntryValueKind:
bool LiveDebugValues::join(
   }
 
   // Filter out DBG_VALUES that are out of scope.
   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)) {
+      if (!VarLocIDs[Idx].dominates(LS, MBB)) {
         KillSet.set(ID);
         LLVM_DEBUG({
           auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
           dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
         });
       }
     }
   }