[DebugInfo][InstrRef][NFC] Refactor code portions into own functions, name some useful types

[jmorse]

Summary

This patch shuffles some functions around before another patch that uses them, so this is primarily a refactor. In particular:

• Move the determination of "which blocks are in scope" to its own function -- this is sometimes trickier than it sounds, and we're going to end up doing it twice. In the process, the "InScopeBlocks" collection is deleted, nothing actually read it, I believe it's a hangover from VarLocBasedLDV.
• Split transfer emission (i.e., installing DBG_VALUEs into blocks) into its own function.
• Give type names to a variety of useful collections that are going to be used in several places shortly.
• Rename a misleading name, "ScopeToBlocks" to "ScopeToAssignBlocks". Because it stores a collection of blocks where assignments happen, not the set of blocks for a scope.

[Orlando]

The clang-format bot isn't happy and I have one nit inline, otherwise LGTM.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

1002–1005

Is there a way that you could reword this to make it slightly clearer what your chosen definition of "in scope" is?

[jmorse]

Revise comment for getBlocksInScope -- remove angst and uncertainty, refer to a PR for talking about the edge cases.

[Orlando]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

1003

This new comment is much clearer, thanks.
nit: cope -> scope

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

public:
 
   /// Type for a live-in value: the predecessor block, and its value.
   using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;
 
   /// Vector (per block) of a collection (inner smallvector) of live-ins.
   /// Used as the result type for the variable value dataflow problem.
   using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;
 
+  /// Mapping from lexical scopes to a DILocation in that scope.
+  using ScopeToDILocT = DenseMap<const LexicalScope *, const DILocation *>;
+
+  /// Mapping from lexical scopes to variables in that scope.
+  using ScopeToVarsT = DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>>;
+
+  /// Mapping from lexical scopes to blocks where variables in that scope are
+  /// assigned. Such blocks aren't necessarily "in" the lexical scope, it's
+  /// just a block where an assignment happens.
+  using ScopeToAssignBlocksT = DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>;
+
 private:
   MachineDominatorTree *DomTree;
   const TargetRegisterInfo *TRI;
   const MachineRegisterInfo *MRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   const MachineFrameInfo *MFI;
   BitVector CalleeSavedRegs;
private:
 
   /// Tracker for transfers, listens to DBG_VALUEs and transfers of values
   /// between locations during stepping, creates new DBG_VALUEs when values move
   /// location.
   TransferTracker *TTracker = nullptr;
 
   /// Blocks which are artificial, i.e. blocks which exclusively contain
   /// instructions without DebugLocs, or with line 0 locations.
-  SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
+  SmallPtrSet<MachineBasicBlock *, 16> ArtificialBlocks;
 
   // Mapping of blocks to and from their RPOT order.
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<const MachineBasicBlock *, unsigned int> BBToOrder;
   DenseMap<unsigned, unsigned> BBNumToRPO;
 
   /// Pair of MachineInstr, and its 1-based offset into the containing block.
   using InstAndNum = std::pair<const MachineInstr *, unsigned>;
private:
   /// from \p InLocs, and assigning the newly computed live ins back into
   /// \p InLocs. \returns two bools -- the first indicates whether a change
   /// was made, the second whether a lattice downgrade occurred. If the latter
   /// is true, revisiting this block is necessary.
   bool mlocJoin(MachineBasicBlock &MBB,
                 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
                 ValueIDNum **OutLocs, ValueIDNum *InLocs);
 
+  /// Produce a set of blocks that are in the current lexical scope. This means
+  /// those blocks that contain instructions "in" the scope, blocks where
+  /// assignments to variables in scope occur, and artificial blocks that are
+  /// successors to any of the earlier blocks. See https://llvm.org/PR48091 for
+  /// more commentry on what "in scope" means.
+  /// \p DILoc A location in the scope that we're fetching blocks for.
+  /// \p Output Set to put in-scope-blocks into.
+  /// \p AssignBlocks Blocks known to contain assignments of variables in scope.
+  void
+  getBlocksForScope(const DILocation *DILoc,
+                    SmallPtrSetImpl<const MachineBasicBlock *> &Output,
+                    const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks);
+
   /// Solve the variable value dataflow problem, for a single lexical scope.
   /// Uses the algorithm from the file comment to resolve control flow joins
   /// using PHI placement and value propagation. Reads the locations of machine
   /// values from the \p MInLocs and \p MOutLocs arrays (see buildMLocValueMap)
   /// and reads the variable values transfer function from \p AllTheVlocs.
   /// Live-in and Live-out variable values are stored locally, with the live-ins
   /// permanently stored to \p Output once a fixedpoint is reached.
   /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
private:
   /// 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);
 
   bool ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree,
                     TargetPassConfig *TPC, unsigned InputBBLimit,
                     unsigned InputDbgValLimit) override;
 

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

if (!Disagree) {
     DbgValue VPHI(MBB.getNumber(), FirstVal.Properties, DbgValue::VPHI);
     Changed = LiveIn != VPHI;
     if (Changed)
       LiveIn = VPHI;
     return Changed;
   }
 }
 
-void InstrRefBasedLDV::buildVLocValueMap(const DILocation *DILoc,
-    const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
-    SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
-    ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
-    SmallVectorImpl<VLocTracker> &AllTheVLocs) {
-  // This method is much like buildMLocValueMap: but focuses on a single
-  // LexicalScope at a time. Pick out a set of blocks and variables that are
-  // to have their value assignments solved, then run our dataflow algorithm
-  // until a fixedpoint is reached.
-  std::priority_queue<unsigned int, std::vector<unsigned int>,
-                      std::greater<unsigned int>>
-      Worklist, Pending;
-  SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
-
-  // The set of blocks we'll be examining.
-  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
-
-  // The order in which to examine them (RPO).
-  SmallVector<MachineBasicBlock *, 8> BlockOrders;
-
-  // RPO ordering function.
-  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
-    return BBToOrder[A] < BBToOrder[B];
-  };
-
+void InstrRefBasedLDV::getBlocksForScope(
+    const DILocation *DILoc,
+    SmallPtrSetImpl<const MachineBasicBlock *> &BlocksToExplore,
+    const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks) {
+  // Get the set of "normal" in-lexical-scope blocks.
   LS.getMachineBasicBlocks(DILoc, BlocksToExplore);
 
-  // A separate container to distinguish "blocks we're exploring" versus
-  // "blocks that are potentially in scope. See comment at start of vlocJoin.
-  SmallPtrSet<const MachineBasicBlock *, 8> InScopeBlocks = BlocksToExplore;
-
   // VarLoc LiveDebugValues tracks variable locations that are defined in
   // blocks not in scope. This is something we could legitimately ignore, but
   // lets allow it for now for the sake of coverage.
   BlocksToExplore.insert(AssignBlocks.begin(), AssignBlocks.end());
 
-  // We also need to propagate variable values through any artificial blocks
-  // that immediately follow blocks in scope.
+  // Storage for artificial blocks we intend to add to BlocksToExplore.
   DenseSet<const MachineBasicBlock *> ToAdd;
 
-  // Helper lambda: For a given block in scope, perform a depth first search
-  // of all the artificial successors, adding them to the ToAdd collection.
-  auto AccumulateArtificialBlocks =
-      [this, &ToAdd, &BlocksToExplore,
-       &InScopeBlocks](const MachineBasicBlock *MBB) {
-        // Depth-first-search state: each node is a block and which successor
-        // we're currently exploring.
-        SmallVector<std::pair<const MachineBasicBlock *,
-                              MachineBasicBlock::const_succ_iterator>,
-                    8>
-            DFS;
+  // To avoid needlessly dropping large volumes of variable locations, propagate
+  // variables through aritifical blocks, i.e. those that don't have any
+  // instructions in scope at all. To accurately replicate VarLoc
+  // LiveDebugValues, this means exploring all artificial successors too.
+  // Perform a depth-first-search to enumerate those blocks.
+  for (auto *MBB : BlocksToExplore) {
 
-        // Find any artificial successors not already tracked.
-        for (auto *succ : MBB->successors()) {
-          if (BlocksToExplore.count(succ) || InScopeBlocks.count(succ))
-            continue;
-          if (!ArtificialBlocks.count(succ))
-            continue;
-          ToAdd.insert(succ);
-          DFS.push_back(std::make_pair(succ, succ->succ_begin()));
-        }
+      if (BlocksToExplore.count(succ))
+      DFS.push_back({succ, succ->succ_begin()});
 
-        // Search all those blocks, depth first.
-        while (!DFS.empty()) {
-          const MachineBasicBlock *CurBB = DFS.back().first;
-          MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;
-          // Walk back if we've explored this blocks successors to the end.
-          if (CurSucc == CurBB->succ_end()) {
-            DFS.pop_back();
-            continue;
-          }
 
-          // If the current successor is artificial and unexplored, descend into
-          // it.
-          if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
-            ToAdd.insert(*CurSucc);
-            DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin()));
-            continue;
-          }
+        DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});
 
-          ++CurSucc;
-        }
-      };
 
-  // Search in-scope blocks and those containing a DBG_VALUE from this scope
-  // for artificial successors.
-  for (auto *MBB : BlocksToExplore)
-    AccumulateArtificialBlocks(MBB);
-  for (auto *MBB : InScopeBlocks)
-    AccumulateArtificialBlocks(MBB);
-
   BlocksToExplore.insert(ToAdd.begin(), ToAdd.end());
-  InScopeBlocks.insert(ToAdd.begin(), ToAdd.end());
+}
+
+void InstrRefBasedLDV::buildVLocValueMap(
+    const DILocation *DILoc, const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
+    SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
+    ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
+    SmallVectorImpl<VLocTracker> &AllTheVLocs) {
+  // This method is much like buildMLocValueMap: but focuses on a single
+  // LexicalScope at a time. Pick out a set of blocks and variables that are
+  // to have their value assignments solved, then run our dataflow algorithm
+  // until a fixedpoint is reached.
+  std::priority_queue<unsigned int, std::vector<unsigned int>,
+                      std::greater<unsigned int>>
+      Worklist, Pending;
+  SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
+
+  // The set of blocks we'll be examining.
+  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;
+
+  // The order in which to examine them (RPO).
+  SmallVector<MachineBasicBlock *, 8> BlockOrders;
+
+  // RPO ordering function.
+  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
+    return BBToOrder[A] < BBToOrder[B];
+  };
+
+  getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks);
 
   // Single block scope: not interesting! No propagation at all. Note that
   // this could probably go above ArtificialBlocks without damage, but
   // that then produces output differences from original-live-debug-values,
   // which propagates from a single block into many artificial ones.
   if (BlocksToExplore.size() == 1)
     return;
 
for (MachineBasicBlock &MBB : MF) {
     CurInst = 1;
     for (auto &MI : MBB) {
       process(MI, MOutLocs, MInLocs);
       TTracker->checkInstForNewValues(CurInst, MI.getIterator());
       ++CurInst;
     }
   }
 
-  // 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.
-    SmallVector<std::pair<unsigned, MachineInstr *>> Insts;
-    for (MachineInstr *MI : P.Insts) {
-      DebugVariable Var(MI->getDebugVariable(), MI->getDebugExpression(),
-                        MI->getDebugLoc()->getInlinedAt());
-      Insts.emplace_back(AllVarsNumbering.find(Var)->second, MI);
-    }
-    llvm::sort(Insts,
-               [](const auto &A, const auto &B) { return A.first < B.first; });
-
-    // Insert either before or after the designated point...
-    if (P.MBB) {
-      MachineBasicBlock &MBB = *P.MBB;
-      for (const auto &Pair : Insts)
-        MBB.insert(P.Pos, Pair.second);
-    } else {
-      // Terminators, like tail calls, can clobber things. Don't try and place
-      // transfers after them.
-      if (P.Pos->isTerminator())
-        continue;
-
-      MachineBasicBlock &MBB = *P.Pos->getParent();
-      for (const auto &Pair : Insts)
-        MBB.insertAfterBundle(P.Pos, Pair.second);
-    }
-  }
+   emitTransfers(AllVarsNumbering);
 }
 
 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   // Build some useful data structures.
 
   LLVMContext &Context = MF.getFunction().getContext();
   EmptyExpr = DIExpression::get(Context, {});
 
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
 }
 
+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.
+    SmallVector<std::pair<unsigned, MachineInstr *>> Insts;
+    for (MachineInstr *MI : P.Insts) {
+      DebugVariable Var(MI->getDebugVariable(), MI->getDebugExpression(),
+                        MI->getDebugLoc()->getInlinedAt());
+      Insts.emplace_back(AllVarsNumbering.find(Var)->second, MI);
+    }
+    llvm::sort(Insts,
+               [](const auto &A, const auto &B) { return A.first < B.first; });
+
+    // Insert either before or after the designated point...
+    if (P.MBB) {
+      MachineBasicBlock &MBB = *P.MBB;
+      for (const auto &Pair : Insts)
+        MBB.insert(P.Pos, Pair.second);
+    } else {
+      // Terminators, like tail calls, can clobber things. Don't try and place
+      // transfers after them.
+      if (P.Pos->isTerminator())
+        continue;
+
+      MachineBasicBlock &MBB = *P.Pos->getParent();
+      for (const auto &Pair : Insts)
+        MBB.insertAfterBundle(P.Pos, Pair.second);
+    }
+  }
+
+  return TTracker->Transfers.size() != 0;
+}
+
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
                                     MachineDominatorTree *DomTree,
                                     TargetPassConfig *TPC,
                                     unsigned InputBBLimit,
                                     unsigned InputDbgValLimit) {
   // No subprogram means this function contains no debuginfo.
for (auto &OrderPair : OrderToBB) {
     MTracker->reset();
   }
 
   // Number all variables in the order that they appear, to be used as a stable
   // insertion order later.
   DenseMap<DebugVariable, unsigned> AllVarsNumbering;
 
   // Map from one LexicalScope to all the variables in that scope.
-  DenseMap<const LexicalScope *, SmallSet<DebugVariable, 4>> ScopeToVars;
+  ScopeToVarsT ScopeToVars;
 
-  // Map from One lexical scope to all blocks in that scope.
-  DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>
-      ScopeToBlocks;
+  // Map from One lexical scope to all blocks where assignments happen for
+  // that scope.
+  ScopeToAssignBlocksT ScopeToAssignBlocks;
 
-  // Store a DILocation that describes a scope.
-  DenseMap<const LexicalScope *, const DILocation *> ScopeToDILocation;
+  // Store map of DILocations that describes scopes.
+  ScopeToDILocT ScopeToDILocation;
 
   // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise
   // the order is unimportant, it just has to be stable.
   unsigned VarAssignCount = 0;
   for (unsigned int I = 0; I < OrderToBB.size(); ++I) {
     auto *MBB = OrderToBB[I];
     auto *VTracker = &vlocs[MBB->getNumber()];
     // Collect each variable with a DBG_VALUE in this block.
     for (auto &idx : VTracker->Vars) {
       const auto &Var = idx.first;
       const DILocation *ScopeLoc = VTracker->Scopes[Var];
       assert(ScopeLoc != nullptr);
       auto *Scope = LS.findLexicalScope(ScopeLoc);
 
       // No insts in scope -> shouldn't have been recorded.
       assert(Scope != nullptr);
 
       AllVarsNumbering.insert(std::make_pair(Var, AllVarsNumbering.size()));
       ScopeToVars[Scope].insert(Var);
-      ScopeToBlocks[Scope].insert(VTracker->MBB);
+      ScopeToAssignBlocks[Scope].insert(VTracker->MBB);
       ScopeToDILocation[Scope] = ScopeLoc;
       ++VarAssignCount;
     }
   }
 
   bool Changed = false;
 
   // If we have an extremely large number of variable assignments and blocks,
   // bail out at this point. We've burnt some time doing analysis already,
   // however we should cut our losses.
   if ((unsigned)MaxNumBlocks > InputBBLimit &&
       VarAssignCount > InputDbgValLimit) {
     LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
                       << " has " << MaxNumBlocks << " basic blocks and "
                       << VarAssignCount
                       << " variable assignments, exceeding limits.\n");
   } 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,
-                   ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
+                   ScopeToAssignBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
                    vlocs);
     }
 
     // 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);