1 files changed, 287 insertions, 89 deletions

diff --git a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
index 0eb6100230bd..6af5f07d801a 100644
--- a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
+++ b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
@@ -148,6 +148,20 @@ static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
                                    cl::desc("Act like old LiveDebugValues did"),
                                    cl::init(false));
 
+// Limit for the maximum number of stack slots we should track, past which we
+// will ignore any spills. InstrRefBasedLDV gathers detailed information on all
+// stack slots which leads to high memory consumption, and in some scenarios
+// (such as asan with very many locals) the working set of the function can be
+// very large, causing many spills. In these scenarios, it is very unlikely that
+// the developer has hundreds of variables live at the same time that they're
+// carefully thinking about -- instead, they probably autogenerated the code.
+// When this happens, gracefully stop tracking excess spill slots, rather than
+// consuming all the developer's memory.
+static cl::opt<unsigned>
+    StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,
+                         cl::desc("livedebugvalues-stack-ws-limit"),
+                         cl::init(250));
+
 /// Tracker for converting machine value locations and variable values into
 /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
 /// specifying block live-in locations and transfers within blocks.
@@ -757,9 +771,15 @@ void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,
   Masks.push_back(std::make_pair(MO, InstID));
 }
 
-SpillLocationNo MLocTracker::getOrTrackSpillLoc(SpillLoc L) {
+Optional<SpillLocationNo> MLocTracker::getOrTrackSpillLoc(SpillLoc L) {
   SpillLocationNo SpillID(SpillLocs.idFor(L));
+
   if (SpillID.id() == 0) {
+    // If there is no location, and we have reached the limit of how many stack
+    // slots to track, then don't track this one.
+    if (SpillLocs.size() >= StackWorkingSetLimit)
+      return None;
+
     // Spill location is untracked: create record for this one, and all
     // subregister slots too.
     SpillID = SpillLocationNo(SpillLocs.insert(L));
@@ -898,7 +918,7 @@ bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const {
 // void InstrRefBasedLDV::printVarLocInMBB(..)
 #endif
 
-SpillLocationNo
+Optional<SpillLocationNo>
 InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
   assert(MI.hasOneMemOperand() &&
          "Spill instruction does not have exactly one memory operand?");
@@ -913,8 +933,11 @@ InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
   return MTracker->getOrTrackSpillLoc({Reg, Offset});
 }
 
-Optional<LocIdx> InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) {
-  SpillLocationNo SpillLoc =  extractSpillBaseRegAndOffset(MI);
+Optional<LocIdx>
+InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) {
+  Optional<SpillLocationNo> SpillLoc = extractSpillBaseRegAndOffset(MI);
+  if (!SpillLoc)
+    return None;
 
   // Where in the stack slot is this value defined -- i.e., what size of value
   // is this? An important question, because it could be loaded into a register
@@ -930,7 +953,7 @@ Optional<LocIdx> InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr
     // occur, but the safe action is to indicate the variable is optimised out.
     return None;
 
-  unsigned SpillID = MTracker->getSpillIDWithIdx(SpillLoc, IdxIt->second);
+  unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillLoc, IdxIt->second);
   return MTracker->getSpillMLoc(SpillID);
 }
 
@@ -1006,7 +1029,7 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
 
   // Only handle this instruction when we are building the variable value
   // transfer function.
-  if (!VTracker)
+  if (!VTracker && !TTracker)
     return false;
 
   unsigned InstNo = MI.getOperand(0).getImm();
@@ -1162,7 +1185,8 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
   // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
   // aren't immediately available).
   DbgValueProperties Properties(Expr, false);
-  VTracker->defVar(MI, Properties, NewID);
+  if (VTracker)
+    VTracker->defVar(MI, Properties, NewID);
 
   // If we're on the final pass through the function, decompose this INSTR_REF
   // into a plain DBG_VALUE.
@@ -1251,7 +1275,12 @@ bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
     Register Base;
     StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
     SpillLoc SL = {Base, Offs};
-    SpillLocationNo SpillNo = MTracker->getOrTrackSpillLoc(SL);
+    Optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(SL);
+
+    // We might be able to find a value, but have chosen not to, to avoid
+    // tracking too much stack information.
+    if (!SpillNo)
+      return true;
 
     // Problem: what value should we extract from the stack? LLVM does not
     // record what size the last store to the slot was, and it would become
@@ -1263,7 +1292,7 @@ bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
     Optional<ValueIDNum> Result = None;
     Optional<LocIdx> SpillLoc = None;
     for (unsigned CS : CandidateSizes) {
-      unsigned SpillID = MTracker->getLocID(SpillNo, {CS, 0});
+      unsigned SpillID = MTracker->getLocID(*SpillNo, {CS, 0});
       SpillLoc = MTracker->getSpillMLoc(SpillID);
       ValueIDNum Val = MTracker->readMLoc(*SpillLoc);
       // If this value was defined in it's own position, then it was probably
@@ -1280,7 +1309,7 @@ bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
     // "supposed" to be is more complex, and benefits a small number of
     // locations.
     if (!Result) {
-      unsigned SpillID = MTracker->getLocID(SpillNo, {64, 0});
+      unsigned SpillID = MTracker->getLocID(*SpillNo, {64, 0});
       SpillLoc = MTracker->getSpillMLoc(SpillID);
       Result = MTracker->readMLoc(*SpillLoc);
     }
@@ -1357,11 +1386,12 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
 
   // If this instruction writes to a spill slot, def that slot.
   if (hasFoldedStackStore(MI)) {
-    SpillLocationNo SpillNo = extractSpillBaseRegAndOffset(MI);
-    for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
-      unsigned SpillID = MTracker->getSpillIDWithIdx(SpillNo, I);
-      LocIdx L = MTracker->getSpillMLoc(SpillID);
-      MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));
+    if (Optional<SpillLocationNo> SpillNo = extractSpillBaseRegAndOffset(MI)) {
+      for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
+        unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
+        LocIdx L = MTracker->getSpillMLoc(SpillID);
+        MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));
+      }
     }
   }
 
@@ -1398,11 +1428,12 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
 
   // Tell TTracker about any folded stack store.
   if (hasFoldedStackStore(MI)) {
-    SpillLocationNo SpillNo = extractSpillBaseRegAndOffset(MI);
-    for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
-      unsigned SpillID = MTracker->getSpillIDWithIdx(SpillNo, I);
-      LocIdx L = MTracker->getSpillMLoc(SpillID);
-      TTracker->clobberMloc(L, MI.getIterator(), true);
+    if (Optional<SpillLocationNo> SpillNo = extractSpillBaseRegAndOffset(MI)) {
+      for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
+        unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
+        LocIdx L = MTracker->getSpillMLoc(SpillID);
+        TTracker->clobberMloc(L, MI.getIterator(), true);
+      }
     }
   }
 }
@@ -1438,23 +1469,24 @@ void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
   }
 }
 
-bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
-                                          MachineFunction *MF) {
+Optional<SpillLocationNo>
+InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,
+                                     MachineFunction *MF) {
   // TODO: Handle multiple stores folded into one.
   if (!MI.hasOneMemOperand())
-    return false;
+    return None;
 
   // Reject any memory operand that's aliased -- we can't guarantee its value.
   auto MMOI = MI.memoperands_begin();
   const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
   if (PVal->isAliased(MFI))
-    return false;
+    return None;
 
   if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
-    return false; // This is not a spill instruction, since no valid size was
-                  // returned from either function.
+    return None; // This is not a spill instruction, since no valid size was
+                 // returned from either function.
 
-  return true;
+  return extractSpillBaseRegAndOffset(MI);
 }
 
 bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
@@ -1511,13 +1543,11 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
   // First, if there are any DBG_VALUEs pointing at a spill slot that is
   // written to, terminate that variable location. The value in memory
   // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.
-  if (isSpillInstruction(MI, MF)) {
-    SpillLocationNo Loc = extractSpillBaseRegAndOffset(MI);
-
+  if (Optional<SpillLocationNo> Loc = isSpillInstruction(MI, MF)) {
     // Un-set this location and clobber, so that earlier locations don't
     // continue past this store.
     for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {
-      unsigned SpillID = MTracker->getSpillIDWithIdx(Loc, SlotIdx);
+      unsigned SpillID = MTracker->getSpillIDWithIdx(*Loc, SlotIdx);
       Optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);
       if (!MLoc)
         continue;
@@ -1535,7 +1565,9 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
 
   // Try to recognise spill and restore instructions that may transfer a value.
   if (isLocationSpill(MI, MF, Reg)) {
-    SpillLocationNo Loc = extractSpillBaseRegAndOffset(MI);
+    // isLocationSpill returning true should guarantee we can extract a
+    // location.
+    SpillLocationNo Loc = *extractSpillBaseRegAndOffset(MI);
 
     auto DoTransfer = [&](Register SrcReg, unsigned SpillID) {
       auto ReadValue = MTracker->readReg(SrcReg);
@@ -1562,10 +1594,9 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
     unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});
     DoTransfer(Reg, SpillID);
   } else {
-    Optional<SpillLocationNo> OptLoc = isRestoreInstruction(MI, MF, Reg);
-    if (!OptLoc)
+    Optional<SpillLocationNo> Loc = isRestoreInstruction(MI, MF, Reg);
+    if (!Loc)
       return false;
-    SpillLocationNo Loc = *OptLoc;
 
     // Assumption: we're reading from the base of the stack slot, not some
     // offset into it. It seems very unlikely LLVM would ever generate
@@ -1592,13 +1623,13 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
 
     for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
       unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
-      unsigned SpillID = MTracker->getLocID(Loc, Subreg);
+      unsigned SpillID = MTracker->getLocID(*Loc, Subreg);
       DoTransfer(*SRI, SpillID);
     }
 
     // Directly look up this registers slot idx by size, and transfer.
     unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
-    unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});
+    unsigned SpillID = MTracker->getLocID(*Loc, {Size, 0});
     DoTransfer(Reg, SpillID);
   }
   return true;
@@ -2765,6 +2796,11 @@ void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
   auto ValueIt = VLocs.Vars.find(Var);
   const DbgValue &Value = ValueIt->second;
 
+  // If it's an explicit assignment of "undef", that means there is no location
+  // anyway, anywhere.
+  if (Value.Kind == DbgValue::Undef)
+    return;
+
   // Assign the variable value to entry to each dominated block that's in scope.
   // Skip the definition block -- it's assigned the variable value in the middle
   // of the block somewhere.
@@ -2790,35 +2826,6 @@ void InstrRefBasedLDV::dump_mloc_transfer(
 }
 #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();
-
-  // 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;
-    }
-  }
-
-   emitTransfers(AllVarsNumbering);
-}
-
 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   // Build some useful data structures.
 
@@ -2861,8 +2868,192 @@ void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
 #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()) {
+    // FIXME: this is a sticking plaster to prevent a memory leak, these
+    // pointers will be automagically freed by being unique pointers, shortly.
+    for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
+      delete[] MInLocs[I];
+      delete[] MOutLocs[I];
+    }
+    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);
+
+  // Finally, there might have been gaps in the block numbering, from dead
+  // blocks being deleted or folded. In those scenarios, we might allocate a
+  // block-table that's never ejected, meaning we have to free it at the end.
+  for (unsigned int I = 0; I < MaxNumBlocks; ++I) {
+    if (MInLocs[I]) {
+      delete[] MInLocs[I];
+      delete[] MOutLocs[I];
+    }
+  }
+
+  return emitTransfers(AllVarsNumbering);
+}
+
 bool InstrRefBasedLDV::emitTransfers(
-        DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
+    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.
@@ -3050,31 +3241,22 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
                       << " 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,
-                   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);
 
-    // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
-    Changed = TTracker->Transfers.size() != 0;
+    // Perform memory cleanup that emitLocations would do otherwise.
+    for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
+      delete[] MOutLocs[Idx];
+      delete[] MInLocs[Idx];
+    }
+  } else {
+    // 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);
   }
 
-  // Common clean-up of memory.
-  for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
-    delete[] MOutLocs[Idx];
-    delete[] MInLocs[Idx];
-  }
+  // Elements of these arrays will be deleted by emitLocations.
   delete[] MOutLocs;
   delete[] MInLocs;
 
@@ -3092,6 +3274,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   DebugPHINumToValue.clear();
   OverlapFragments.clear();
   SeenFragments.clear();
+  SeenDbgPHIs.clear();
 
   return Changed;
 }
@@ -3357,6 +3540,21 @@ Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
                                                       ValueIDNum **MLiveIns,
                                                       MachineInstr &Here,
                                                       uint64_t InstrNum) {
+  // This function will be called twice per DBG_INSTR_REF, and might end up
+  // computing lots of SSA information: memoize it.
+  auto SeenDbgPHIIt = SeenDbgPHIs.find(&Here);
+  if (SeenDbgPHIIt != SeenDbgPHIs.end())
+    return SeenDbgPHIIt->second;
+
+  Optional<ValueIDNum> Result =
+      resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);
+  SeenDbgPHIs.insert({&Here, Result});
+  return Result;
+}
+
+Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(
+    MachineFunction &MF, ValueIDNum **MLiveOuts, ValueIDNum **MLiveIns,
+    MachineInstr &Here, uint64_t InstrNum) {
   // Pick out records of DBG_PHI instructions that have been observed. If there
   // are none, then we cannot compute a value number.
   auto RangePair = std::equal_range(DebugPHINumToValue.begin(),