Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h =================================================================== --- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h +++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h @@ -1073,6 +1073,30 @@ /// 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 &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 &AllTheVLocs, MachineFunction &MF, + DenseMap &AllVarsNumbering, + const TargetPassConfig &TPC); + bool ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree, TargetPassConfig *TPC, unsigned InputBBLimit, unsigned InputDbgValLimit) override; Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp =================================================================== --- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -148,6 +148,13 @@ cl::desc("Act like old LiveDebugValues did"), cl::init(false)); +// Enable the use of depth-first exploration of lexical scopes when solving +// variable locations. Reduces peak memory usage, improves locality. +static cl::opt DepthFirstSearch( + "livedebugvalues-depth-explore", cl::Hidden, + cl::desc("Depth first search when solving variable locs"), + cl::init(true)); + /// 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. @@ -2856,6 +2863,174 @@ #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 &EjectionMap, + const ScopeToDILocT &ScopeToDILocation, + ScopeToAssignBlocksT &ScopeToAssignBlocks) { + SmallPtrSet BlocksToExplore; + SmallVector, 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 &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 &AllTheVLocs, MachineFunction &MF, + DenseMap &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 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 BlocksToExplore; + SmallVector, 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 &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(*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 &AllVarsNumbering) { // Go through all the transfers recorded in the TransferTracker -- this is @@ -3051,6 +3226,13 @@ delete[] MOutLocs[Idx]; delete[] MInLocs[Idx]; } + } else if (DepthFirstSearch) { + // 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); } 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