Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h =================================================================== --- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h +++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h @@ -784,6 +784,17 @@ /// Used as the result type for the variable value dataflow problem. using LiveInsT = SmallVector, 8>; + /// Mapping from lexical scopes to a DILocation in that scope. + using ScopeToDILocT = DenseMap; + + /// Mapping from lexical scopes to variables in that scope. + using ScopeToVarsT = DenseMap>; + + /// 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>; + private: MachineDominatorTree *DomTree; const TargetRegisterInfo *TRI; @@ -821,7 +832,7 @@ /// Blocks which are artificial, i.e. blocks which exclusively contain /// instructions without DebugLocs, or with line 0 locations. - SmallPtrSet ArtificialBlocks; + SmallPtrSet ArtificialBlocks; // Mapping of blocks to and from their RPOT order. DenseMap OrderToBB; @@ -993,6 +1004,19 @@ SmallPtrSet &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 cope, 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 &Output, + const SmallPtrSetImpl &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 @@ -1043,6 +1067,12 @@ 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 + /// the AllVarsNumbering order. + bool emitTransfers(DenseMap &AllVarsNumbering); + /// Boilerplate computation of some initial sets, artifical blocks and /// RPOT block ordering. void initialSetup(MachineFunction &MF); Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp =================================================================== --- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -2430,8 +2430,71 @@ } } -void InstrRefBasedLDV::buildVLocValueMap(const DILocation *DILoc, - const SmallSet &VarsWeCareAbout, +void InstrRefBasedLDV::getBlocksForScope( + const DILocation *DILoc, + SmallPtrSetImpl &BlocksToExplore, + const SmallPtrSetImpl &AssignBlocks) { + // Get the set of "normal" in-lexical-scope blocks. + LS.getMachineBasicBlocks(DILoc, 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()); + + // Storage for artificial blocks we intend to add to BlocksToExplore. + DenseSet ToAdd; + + // 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) { + // Depth-first-search state: each node is a block and which successor + // we're currently exploring. + SmallVector, + 8> + DFS; + + // Find any artificial successors not already tracked. + for (auto *succ : MBB->successors()) { + if (BlocksToExplore.count(succ)) + continue; + if (!ArtificialBlocks.count(succ)) + continue; + ToAdd.insert(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({*CurSucc, (*CurSucc)->succ_begin()}); + continue; + } + + ++CurSucc; + } + }; + + BlocksToExplore.insert(ToAdd.begin(), ToAdd.end()); +} + +void InstrRefBasedLDV::buildVLocValueMap( + const DILocation *DILoc, const SmallSet &VarsWeCareAbout, SmallPtrSetImpl &AssignBlocks, LiveInsT &Output, ValueIDNum **MOutLocs, ValueIDNum **MInLocs, SmallVectorImpl &AllTheVLocs) { @@ -2455,74 +2518,7 @@ return BBToOrder[A] < BBToOrder[B]; }; - 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 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. - DenseSet 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, - 8> - DFS; - - // 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())); - } - - // 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; - } - - ++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()); + getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks); // Single block scope: not interesting! No propagation at all. Note that // this could probably go above ArtificialBlocks without damage, but @@ -2812,39 +2808,7 @@ } } - // 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> 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) { @@ -2889,6 +2853,45 @@ #endif } +bool InstrRefBasedLDV::emitTransfers( + DenseMap &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> 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, @@ -2995,14 +2998,14 @@ DenseMap AllVarsNumbering; // Map from one LexicalScope to all the variables in that scope. - DenseMap> ScopeToVars; + ScopeToVarsT ScopeToVars; - // Map from One lexical scope to all blocks in that scope. - DenseMap> - 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 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. @@ -3022,7 +3025,7 @@ 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; } @@ -3046,7 +3049,7 @@ // 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); }