[DebugInfo][InstrRef] Use a depth-first search to reduce the lifetime of tracking information

[jmorse]

Summary

This patch is technically NFC, but I'm not putting NFC in the title because it shouldn't be considered a trivial change.

Over in D116821, there are some benchmarks where InstrRefBasedLDV significantly increases max-rss during LTO and the like. After thinking about it, it seems a bit stupid that we compute lots of information, store them all in huge tables, then emit them to DBG_VALUE instructions, then free the tables. We can do better: this patch solves the variable value problem in lexical scope depth-first order, allowing blocks where all contained scopes have been processed to be emitted early and the relevant information freed. This isn't going to solve the problem of instruction-referencing producing lots of variable information, but it should make the overhead on top of that stop growing linearly.

I've kept the unordered-explore code available, and it can be selected with a command line flag, to ease debugging in the future. I might figure out a way to make the unit tests use both of these modes, but haven't done that yet.

The approach is to:

• Make use of the fact LexicalScopes gives a depth-number to each lexical scope,
• Produce an "ejection map" [0] that identifies the last lexical scope to make use of a block,
• Enumerate each scope in LexicalScopes' DFS order, solving the variable value problem,
• After each scope is processed, look for any blocks that won't be used by any other scope, and "eject" them.

Where "ejecting" is translating the variable value information into DBG_VALUE instructions in the block, and freeing any machine-value or variable-value information for that block.

I haven't tested the reproducer posted in D116821 yet, but this (and stacked patches) reduces the instr-ref growth in max-rss in mafft / SPASS from 26%/35% to roughly 10% each. Digging into SPASS, the culprit is the "main" function, which LTO seems to inline a lot of stuff into. As ever, the amount of debug-info is way out of proportion to the actual code, there are some 31k non-debug instructions. After LiveDebugValues, there are ~90k DBG_VALUEs with VarLocBasedLDV, ~135k DBG_VALUEs with InstrRefBasedLDV. The ultimate fix for this is to stream variable information into the DWARF printer when needed, rather than coughing it all up at the same time and creating instructions for it.

Testing: no test added on account of this being a performance patch. I've built stage2 clang RelWithDebinfo with and without this change, and all object files are identical, except for InstrRefBasedImp.cpp.o of course.

[0] This could be called an emission instead of ejecting, but I've written emission in a lot of other places.

[dblaikie]

Minor point, but:

This patch is technically NFC, but I'm not putting NFC in the title because it shouldn't be considered a trivial change.

Generally I think it's still valuable to flag such a thing as NFC - it explains why there aren't any test changes and means someone can expect object files to be identical with/without the change (& if they aren't, that's a bug)

I've kept the unordered-explore code available, and it can be selected with a command line flag, to ease debugging in the future. I might figure out a way to make the unit tests use both of these modes, but haven't done that yet.

That worries me a bit - leaving untested code in. Like #if 0 but worse, because it is accessible, but untested. Would be good to either delete it (can be resurrected from source control) or test it...

[Orlando]

Once @dblaikie's concerns are addressed, this LGTM.

Would it be worth caching getBlocksForScope results? If I'm reading this right it looks like it's called a few times with what should be the same inputs and outputs in a few places in the pass?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

2986

Repeating offline discussion so it's noted on the review -- it looks as though it might be possible to simplify this by removing the HighestDFSIn check and moving the body of this block into the if (ChildNum < (ssize_t)Children.size()) { ... } block below.

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

2986

I went to implement this and then realised: the block you mention only runs for scopes where there are child scopes, and the "else" block only runs after child scopes are visited. I think this counter/ratchet needs to continue to exist so that scopes are always visited, and in the correct order.

[jmorse]

Strip out dead code as per recommendations.

Given that in the dead path, scopes were visited in a DenseMap order and thus it was nondeterministic, I suppose there's little value in keeping around code to visit scopes "the old way".

[Orlando]

In D118460#3284107, @Orlando wrote:

Would it be worth caching getBlocksForScope results? If I'm reading this right it looks like it's called a few times with what should be the same inputs and outputs in a few places in the pass?

wdyt about this? I'm happy for that to come as a separate patch if you agree, and it looks like @dblaikie's comments have been addressed, so LGTM if you make clang-format bot happy.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

2986

Aha, SGTM.

[jmorse]

In D118460#3290118, @Orlando wrote:

In D118460#3284107, @Orlando wrote:

Would it be worth caching getBlocksForScope results? If I'm reading this right it looks like it's called a few times with what should be the same inputs and outputs in a few places in the pass?

wdyt about this? I'm happy for that to come as a separate patch if you agree, and it looks like @dblaikie's comments have been addressed, so LGTM if you make clang-format bot happy.

IMO that should happen, but not in this patch, simply out of being conservative -- this patch should be able to make its way into llvm14-rc1, and a follow-up patch caching getBlocksForScope should be able to get into rc2 (IMHO, YMMV).

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

private:
   /// For the given block and live-outs feeding into it, try to find a
   /// machine location where all the variable values join together.
   /// \returns Value ID of a machine PHI if an appropriate one is available.
   Optional<ValueIDNum>
   pickVPHILoc(const MachineBasicBlock &MBB, const DebugVariable &Var,
               const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
               const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders);
 
-  /// Given the solutions to the two dataflow problems, machine value locations
-  /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
-  /// TransferTracker class over the function to produce live-in and transfer
-  /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
-  /// order given by AllVarsNumbering -- this could be any stable order, but
-  /// right now "order of appearence in function, when explored in RPO", so
-  /// that we can compare explictly against VarLocBasedImpl.
-  void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
-                     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
-                     DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
-                     const TargetPassConfig &TPC);
-
   /// Take collections of DBG_VALUE instructions stored in TTracker, and
   /// install them into their output blocks. Preserves a stable order of
   /// DBG_VALUEs produced (which would otherwise cause nondeterminism) through
   /// the AllVarsNumbering order.
   bool emitTransfers(DenseMap<DebugVariable, unsigned> &AllVarsNumbering);
 
   /// Boilerplate computation of some initial sets, artifical blocks and
   /// RPOT block ordering.
   void initialSetup(MachineFunction &MF);
 
+  /// Produce a map of the last lexical scope that uses a block, using the
+  /// scopes DFSOut number. Mapping is block-number to DFSOut.
+  /// \p EjectionMap Pre-allocated vector in which to install the built ma.
+  /// \p ScopeToDILocation Mapping of LexicalScopes to their DILocations.
+  /// \p AssignBlocks Map of blocks where assignments happen for a scope.
+  void makeDepthFirstEjectionMap(SmallVectorImpl<unsigned> &EjectionMap,
+                                 const ScopeToDILocT &ScopeToDILocation,
+                                 ScopeToAssignBlocksT &AssignBlocks);
+
+  /// When determining per-block variable values and emitting to DBG_VALUEs,
+  /// this function explores by lexical scope depth. Doing so means that per
+  /// block information can be fully computed before exploration finishes,
+  /// allowing us to emit it and free data structures earlier than otherwise.
+  /// It's also good for locality.
+  bool depthFirstVLocAndEmit(
+      unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,
+      const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToBlocks,
+      LiveInsT &Output, ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
+      SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,
+      DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
+      const TargetPassConfig &TPC);
+
   bool ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree,
                     TargetPassConfig *TPC, unsigned InputBBLimit,
                     unsigned InputDbgValLimit) override;
 
 public:
   /// Default construct and initialize the pass.
   InstrRefBasedLDV();
 

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

void InstrRefBasedLDV::dump_mloc_transfer(
   for (auto &P : mloc_transfer) {
     std::string foo = MTracker->LocIdxToName(P.first);
     std::string bar = MTracker->IDAsString(P.second);
     dbgs() << "Loc " << foo << " --> " << bar << "\n";
   }
 }
 #endif
 
-void InstrRefBasedLDV::emitLocations(
-    MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
-    ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
-    const TargetPassConfig &TPC) {
-  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
-  unsigned NumLocs = MTracker->getNumLocs();
-  VTracker = nullptr;
-
-  // For each block, load in the machine value locations and variable value
-  // live-ins, then step through each instruction in the block. New DBG_VALUEs
-  // to be inserted will be created along the way.
-  for (MachineBasicBlock &MBB : MF) {
-    unsigned bbnum = MBB.getNumber();
-    MTracker->reset();
-    MTracker->loadFromArray(MInLocs[bbnum], bbnum);
-    TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
-                         NumLocs);
-
-    CurBB = bbnum;
-    CurInst = 1;
-    for (auto &MI : MBB) {
-      process(MI, MOutLocs, MInLocs);
-      TTracker->checkInstForNewValues(CurInst, MI.getIterator());
-      ++CurInst;
-    }
-
-    // Our block information has now been converted into DBG_VALUEs, to be
-    // inserted below. Free the memory we allocated to track variable / register
-    // values. If we don't, we needlessy record the same info in memory twice.
-    delete[] MInLocs[bbnum];
-    delete[] MOutLocs[bbnum];
-    MInLocs[bbnum] = nullptr;
-    MOutLocs[bbnum] = nullptr;
-    SavedLiveIns[bbnum].clear();
-  }
-
-   emitTransfers(AllVarsNumbering);
-}
-
 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   // Build some useful data structures.
 
   LLVMContext &Context = MF.getFunction().getContext();
   EmptyExpr = DIExpression::get(Context, {});
 
   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
     if (const DebugLoc &DL = MI.getDebugLoc())
for (auto It = MF.DebugValueSubstitutions.begin();
          It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
       assert(It->Src != std::next(It)->Src && "Duplicate variable location "
                                               "substitution seen");
     }
   }
 #endif
 }
 
+// Produce an "ejection map" for blocks, i.e., what's the highest-numbered
+// lexical scope it's used in. When exploring in DFS order and we pass that
+// scope, the block can be processed and any tracking information freed.
+void InstrRefBasedLDV::makeDepthFirstEjectionMap(
+    SmallVectorImpl<unsigned> &EjectionMap,
+    const ScopeToDILocT &ScopeToDILocation,
+    ScopeToAssignBlocksT &ScopeToAssignBlocks) {
+  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
+  SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;
+  auto *TopScope = LS.getCurrentFunctionScope();
+
+  // Unlike lexical scope explorers, we explore in reverse order, to find the
+  // "last" lexical scope used for each block early.
+  WorkStack.push_back({TopScope, TopScope->getChildren().size() - 1});
+
+  while (!WorkStack.empty()) {
+    auto &ScopePosition = WorkStack.back();
+    LexicalScope *WS = ScopePosition.first;
+    ssize_t ChildNum = ScopePosition.second--;
+
+    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
+    if (ChildNum >= 0) {
+      // If ChildNum is positive, there are remaining children to explore.
+      // Push the child and its children-count onto the stack.
+      auto &ChildScope = Children[ChildNum];
+      WorkStack.push_back(
+          std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));
+    } else {
+      WorkStack.pop_back();
+
+      // We've explored all children and any later blocks: examine all blocks
+      // in our scope. If they haven't yet had an ejection number set, then
+      // this scope will be the last to use that block.
+      auto DILocationIt = ScopeToDILocation.find(WS);
+      if (DILocationIt != ScopeToDILocation.end()) {
+        getBlocksForScope(DILocationIt->second, BlocksToExplore,
+                          ScopeToAssignBlocks.find(WS)->second);
+        for (auto *MBB : BlocksToExplore) {
+          unsigned BBNum = MBB->getNumber();
+          if (EjectionMap[BBNum] == 0)
+            EjectionMap[BBNum] = WS->getDFSOut();
+        }
+
+        BlocksToExplore.clear();
+      }
+    }
+  }
+}
+
+bool InstrRefBasedLDV::depthFirstVLocAndEmit(
+    unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,
+    const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,
+    LiveInsT &Output, ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
+    SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,
+    DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
+    const TargetPassConfig &TPC) {
+  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
+  unsigned NumLocs = MTracker->getNumLocs();
+  VTracker = nullptr;
+
+  // No scopes? No variable locations.
+  if (!LS.getCurrentFunctionScope())
+    return false;
+
+  // Build map from block number to the last scope that uses the block.
+  SmallVector<unsigned, 16> EjectionMap;
+  EjectionMap.resize(MaxNumBlocks, 0);
+  makeDepthFirstEjectionMap(EjectionMap, ScopeToDILocation,
+                            ScopeToAssignBlocks);
+
+  // Helper lambda for ejecting a block -- if nothing is going to use the block,
+  // we can translate the variable location information into DBG_VALUEs and then
+  // free all of InstrRefBasedLDV's data structures.
+  auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {
+    unsigned BBNum = MBB.getNumber();
+    AllTheVLocs[BBNum].clear();
+
+    // Prime the transfer-tracker, and then step through all the block
+    // instructions, installing transfers.
+    MTracker->reset();
+    MTracker->loadFromArray(MInLocs[BBNum], BBNum);
+    TTracker->loadInlocs(MBB, MInLocs[BBNum], Output[BBNum], NumLocs);
+
+    CurBB = BBNum;
+    CurInst = 1;
+    for (auto &MI : MBB) {
+      process(MI, MOutLocs, MInLocs);
+      TTracker->checkInstForNewValues(CurInst, MI.getIterator());
+      ++CurInst;
+    }
+
+    // Free machine-location tables for this block.
+    delete[] MInLocs[BBNum];
+    delete[] MOutLocs[BBNum];
+    // Make ourselves brittle to use-after-free errors.
+    MInLocs[BBNum] = nullptr;
+    MOutLocs[BBNum] = nullptr;
+    // We don't need live-in variable values for this block either.
+    Output[BBNum].clear();
+    AllTheVLocs[BBNum].clear();
+  };
+
+  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
+  SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;
+  WorkStack.push_back({LS.getCurrentFunctionScope(), 0});
+  unsigned HighestDFSIn = 0;
+
+  // Proceed to explore in depth first order.
+  while (!WorkStack.empty()) {
+    auto &ScopePosition = WorkStack.back();
+    LexicalScope *WS = ScopePosition.first;
+    ssize_t ChildNum = ScopePosition.second++;
+
+    // We obesrve scopes with children twice here, once descending in, once
+    // ascending out of the scope nest. Use HighestDFSIn as a ratchet to ensure
+    // we don't process a scope twice. Additionally, ignore scopes that don't
+    // have a DILocation -- by proxy, this means we never tracked any variable
+    // assignments in that scope.
+    auto DILocIt = ScopeToDILocation.find(WS);
+    if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
+      const DILocation *DILoc = DILocIt->second;
+      auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;
+      auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;
+
+      buildVLocValueMap(DILoc, VarsWeCareAbout, BlocksInScope, Output, MOutLocs,
+                        MInLocs, AllTheVLocs);
+    }
+
+    HighestDFSIn = std::max(HighestDFSIn, WS->getDFSIn());
+
+    // Descend into any scope nests.
+    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
+    if (ChildNum < (ssize_t)Children.size()) {
+      // There are children to explore -- push onto stack and continue.
+      auto &ChildScope = Children[ChildNum];
+      WorkStack.push_back(std::make_pair(ChildScope, 0));
+    } else {
+      WorkStack.pop_back();
+
+      // We've explored a leaf, or have explored all the children of a scope.
+      // Try to eject any blocks where this is the last scope it's relevant to.
+      auto DILocationIt = ScopeToDILocation.find(WS);
+      if (DILocationIt == ScopeToDILocation.end())
+        continue;
+
+      getBlocksForScope(DILocationIt->second, BlocksToExplore,
+                        ScopeToAssignBlocks.find(WS)->second);
+      for (auto *MBB : BlocksToExplore)
+        if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])
+          EjectBlock(const_cast<MachineBasicBlock &>(*MBB));
+
+      BlocksToExplore.clear();
+    }
+  }
+
+  // Some artificial blocks may not have been ejected, meaning they're not
+  // connected to an actual legitimate scope. This can technically happen
+  // with things like the entry block. In theory, we shouldn't need to do
+  // anything for such out-of-scope blocks, but for the sake of being similar
+  // to VarLocBasedLDV, eject these too.
+  for (auto *MBB : ArtificialBlocks)
+    if (MOutLocs[MBB->getNumber()])
+      EjectBlock(*MBB);
+
+  return emitTransfers(AllVarsNumbering);
+}
+
 bool InstrRefBasedLDV::emitTransfers(
-        DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
   // Go through all the transfers recorded in the TransferTracker -- this is
   // both the live-ins to a block, and any movements of values that happen
   // in the middle.
   for (const auto &P : TTracker->Transfers) {
     // We have to insert DBG_VALUEs in a consistent order, otherwise they
     // appear in DWARF in different orders. Use the order that they appear
     // when walking through each block / each instruction, stored in
     // AllVarsNumbering.
LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
                       << " variable assignments, exceeding limits.\n");
 
     // Perform memory cleanup that emitLocations would do otherwise.
     for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
       delete[] MOutLocs[Idx];
       delete[] MInLocs[Idx];
     }
   } else {
-    // Compute the extended ranges, iterating over scopes. There might be
-    // something to be said for ordering them by size/locality, but that's for
-    // the future. For each scope, solve the variable value problem, producing
-    // a map of variables to values in SavedLiveIns.
-    for (auto &P : ScopeToVars) {
-      buildVLocValueMap(ScopeToDILocation[P.first], P.second,
-                   ScopeToAssignBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
-                   vlocs);
-    }
-
-    // Now that we've analysed variable assignments, free any tracking data.
-    vlocs.clear();
-
-    // Using the computed value locations and variable values for each block,
-    // create the DBG_VALUE instructions representing the extended variable
-    // locations.
-    emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC);
-
-    // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
-    Changed = TTracker->Transfers.size() != 0;
+    // Optionally, solve the variable value problem and emit to blocks by using
+    // a lexical-scope-depth search. It should be functionally identical to
+    // the "else" block of this condition.
+    Changed = depthFirstVLocAndEmit(
+        MaxNumBlocks, ScopeToDILocation, ScopeToVars, ScopeToAssignBlocks,
+        SavedLiveIns, MOutLocs, MInLocs, vlocs, MF, AllVarsNumbering, *TPC);
   }
 
   // Elements of these arrays will be deleted by emitLocations.
   delete[] MOutLocs;
   delete[] MInLocs;
 
   delete MTracker;
   delete TTracker;