Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h =================================================================== --- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h +++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h @@ -1071,18 +1071,6 @@ const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, const SmallVectorImpl &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 &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 @@ -1093,6 +1081,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 @@ -2821,45 +2821,6 @@ } #endif -void InstrRefBasedLDV::emitLocations( - MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, DenseMap &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. @@ -2902,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 @@ -3098,26 +3227,12 @@ 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.