Index: llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp =================================================================== --- llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp +++ llvm/lib/CodeGen/AssignmentTrackingAnalysis.cpp @@ -4,6 +4,7 @@ #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" #include "llvm/ADT/UniqueVector.h" #include "llvm/Analysis/Interval.h" #include "llvm/BinaryFormat/Dwarf.h" @@ -28,6 +29,11 @@ using namespace llvm; #define DEBUG_TYPE "debug-ata" +STATISTIC(NumDefsScanned, "Number of dbg locs that get scanned for removal"); +STATISTIC(NumDefsRemoved, "Number of dbg locs removed"); +STATISTIC(NumWedgesScanned, "Number of dbg wedges scanned"); +STATISTIC(NumWedgesChanged, "Number of dbg wedges changed"); + static cl::opt MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), @@ -1428,6 +1434,224 @@ return InsertedAnyIntrinsics; } +/// Remove redundant definitions within sequences of consecutive location defs. +/// This is done using a backward scan to keep the last def describing a +/// specific variable/fragment. +/// +/// This implements removeRedundantDbgInstrsUsingBackwardScan from +/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with +/// FunctionVarLocsBuilder instead of with intrinsics. +static bool +removeRedundantDbgLocsUsingBackwardScan(const BasicBlock *BB, + FunctionVarLocsBuilder &FnVarLocs) { + bool Changed = false; + SmallDenseSet VariableSet; + + // Scan over the entire block, not just over the instructions mapped by + // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug + // instructions. + for (const Instruction &I : reverse(*BB)) { + if (!isa(I)) { + // Sequence of consecutive defs ended. Clear map for the next one. + VariableSet.clear(); + } + + // Get the location defs that start just before this instruction. + const auto *Locs = FnVarLocs.getWedge(&I); + if (!Locs) + continue; + + NumWedgesScanned++; + bool ChangedThisWedge = false; + // The new pruned set of defs, reversed because we're scanning backwards. + SmallVector NewDefsReversed; + + // Iterate over the existing defs in reverse. + for (auto RIt = Locs->rbegin(), REnd = Locs->rend(); RIt != REnd; ++RIt) { + NumDefsScanned++; + const DebugVariable &Key = FnVarLocs.getVariable(RIt->VariableID); + bool FirstDefOfFragment = VariableSet.insert(Key).second; + + // If the same variable fragment is described more than once it is enough + // to keep the last one (i.e. the first found in this reverse iteration). + if (FirstDefOfFragment) { + // New def found: keep it. + NewDefsReversed.push_back(*RIt); + } else { + // Redundant def found: throw it away. Since the wedge of defs is being + // rebuilt, doing nothing is the same as deleting an entry. + ChangedThisWedge = true; + NumDefsRemoved++; + } + continue; + } + + // Un-reverse the defs and replace the wedge with the pruned version. + if (ChangedThisWedge) { + std::reverse(NewDefsReversed.begin(), NewDefsReversed.end()); + FnVarLocs.setWedge(&I, std::move(NewDefsReversed)); + NumWedgesChanged++; + Changed = true; + } + } + + return Changed; +} + +/// Remove redundant location defs using a forward scan. This can remove a +/// location definition that is redundant due to indicating that a variable has +/// the same value as is already being indicated by an earlier def. +/// +/// This implements removeRedundantDbgInstrsUsingForwardScan from +/// lib/Transforms/Utils/BasicBlockUtils.cpp for locations described with +/// FunctionVarLocsBuilder instead of with intrinsics +static bool +removeRedundantDbgLocsUsingForwardScan(const BasicBlock *BB, + FunctionVarLocsBuilder &FnVarLocs) { + bool Changed = false; + DenseMap> VariableMap; + + // Scan over the entire block, not just over the instructions mapped by + // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug + // instructions. + for (const Instruction &I : *BB) { + // Get the defs that come just before this instruction. + const auto *Locs = FnVarLocs.getWedge(&I); + if (!Locs) + continue; + + NumWedgesScanned++; + bool ChangedThisWedge = false; + // The new pruned set of defs. + SmallVector NewDefs; + + // Iterate over the existing defs. + for (const VarLocInfo &Loc : *Locs) { + NumDefsScanned++; + DebugVariable Key(FnVarLocs.getVariable(Loc.VariableID).getVariable(), + NoneType(), Loc.DL.getInlinedAt()); + auto VMI = VariableMap.find(Key); + + // Update the map if we found a new value/expression describing the + // variable, or if the variable wasn't mapped already. + if (VMI == VariableMap.end() || VMI->second.first != Loc.V || + VMI->second.second != Loc.Expr) { + VariableMap[Key] = {Loc.V, Loc.Expr}; + NewDefs.push_back(Loc); + continue; + } + + // Did not insert this Loc, which is the same as removing it. + ChangedThisWedge = true; + NumDefsRemoved++; + } + + // Replace the existing wedge with the pruned version. + if (ChangedThisWedge) { + FnVarLocs.setWedge(&I, std::move(NewDefs)); + NumWedgesChanged++; + Changed = true; + } + } + + return Changed; +} + +static bool +removeUndefDbgLocsFromEntryBlock(const BasicBlock *BB, + FunctionVarLocsBuilder &FnVarLocs) { + assert(BB->isEntryBlock()); + // Do extra work to ensure that we remove semantically unimportant undefs. + // + // This is to work around the fact that SelectionDAG will hoist dbg.values + // using argument values to the top of the entry block. That can move arg + // dbg.values before undef and constant dbg.values which they previously + // followed. The easiest thing to do is to just try to feed SelectionDAG + // input it's happy with. + // + // Map of {Variable x: Fragments y} where the fragments y of variable x have + // have at least one non-undef location defined already. Don't use directly, + // instead call DefineBits and HasDefinedBits. + SmallDenseMap> + VarsWithDef; + // Specify that V (a fragment of A) has a non-undef location. + auto DefineBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) { + VarsWithDef[A].insert(V.getFragmentOrDefault()); + }; + // Return true if a non-undef location has been defined for V (a fragment of + // A). Doesn't imply that the location is currently non-undef, just that a + // non-undef location has been seen previously. + auto HasDefinedBits = [&VarsWithDef](DebugAggregate A, DebugVariable V) { + auto FragsIt = VarsWithDef.find(A); + if (FragsIt == VarsWithDef.end()) + return false; + return llvm::any_of(FragsIt->second, [V](auto Frag) { + return DIExpression::fragmentsOverlap(Frag, V.getFragmentOrDefault()); + }); + }; + + bool Changed = false; + DenseMap> VariableMap; + + // Scan over the entire block, not just over the instructions mapped by + // FnVarLocs, because wedges in FnVarLocs may only be seperated by debug + // instructions. + for (const Instruction &I : *BB) { + // Get the defs that come just before this instruction. + const auto *Locs = FnVarLocs.getWedge(&I); + if (!Locs) + continue; + + NumWedgesScanned++; + bool ChangedThisWedge = false; + // The new pruned set of defs. + SmallVector NewDefs; + + // Iterate over the existing defs. + for (const VarLocInfo &Loc : *Locs) { + NumDefsScanned++; + DebugAggregate Aggr{FnVarLocs.getVariable(Loc.VariableID).getVariable(), + Loc.DL.getInlinedAt()}; + DebugVariable Var = FnVarLocs.getVariable(Loc.VariableID); + + // Remove undef entries that are encountered before any non-undef + // intrinsics from the entry block. + if (isa(Loc.V) && !HasDefinedBits(Aggr, Var)) { + // Did not insert this Loc, which is the same as removing it. + NumDefsRemoved++; + ChangedThisWedge = true; + continue; + } + + DefineBits(Aggr, Var); + NewDefs.push_back(Loc); + } + + // Replace the existing wedge with the pruned version. + if (ChangedThisWedge) { + FnVarLocs.setWedge(&I, std::move(NewDefs)); + NumWedgesChanged++; + Changed = true; + } + } + + return Changed; +} + +static bool removeRedundantDbgLocs(const BasicBlock *BB, + FunctionVarLocsBuilder &FnVarLocs) { + bool MadeChanges = false; + MadeChanges |= removeRedundantDbgLocsUsingBackwardScan(BB, FnVarLocs); + if (BB->isEntryBlock()) + MadeChanges |= removeUndefDbgLocsFromEntryBlock(BB, FnVarLocs); + MadeChanges |= removeRedundantDbgLocsUsingForwardScan(BB, FnVarLocs); + + if (MadeChanges) + LLVM_DEBUG(dbgs() << "Removed redundant dbg locs from: " << BB->getName() + << "\n"); + return MadeChanges; +} + static DenseSet findVarsWithStackSlot(Function &Fn) { DenseSet Result; for (auto &BB : Fn) { @@ -1451,8 +1675,20 @@ // only need to perform a dataflow on the set of variables which have a stack // slot. Find those now. DenseSet VarsWithStackSlot = findVarsWithStackSlot(Fn); + + bool Changed = false; + AssignmentTrackingLowering Pass(Fn, Layout, &VarsWithStackSlot); - Pass.run(FnVarLocs); + Changed = Pass.run(FnVarLocs); + + if (Changed) { + // Remove redundant entries. As well as reducing memory consumption and + // avoiding waiting cycles later by burning some now, this has another + // important job. That is to work around some SelectionDAG quirks. See + // removeRedundantDbgLocsUsingForwardScan comments for more info on that. + for (auto &BB : Fn) + removeRedundantDbgLocs(&BB, *FnVarLocs); + } } bool AssignmentTrackingAnalysis::runOnFunction(Function &F) {