diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp | 1138 |
1 files changed, 412 insertions, 726 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp index 2226c10b49a4..05e994c9eb51 100644 --- a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp +++ b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp @@ -7,23 +7,14 @@ //===----------------------------------------------------------------------===// /// /// This pass implements a data flow analysis that propagates debug location -/// information by inserting additional DBG_VALUE insts into the machine -/// instruction stream. Before running, each DBG_VALUE inst corresponds to a -/// source assignment of a variable. Afterwards, a DBG_VALUE inst specifies a -/// variable location for the current basic block (see SourceLevelDebugging.rst). +/// information by inserting additional DBG_VALUE instructions into the machine +/// instruction stream. The pass internally builds debug location liveness +/// ranges to determine the points where additional DBG_VALUEs need to be +/// inserted. /// /// This is a separate pass from DbgValueHistoryCalculator to facilitate /// testing and improve modularity. /// -/// Each variable location is represented by a VarLoc object that identifies the -/// source variable, its current machine-location, and the DBG_VALUE inst that -/// specifies the location. Each VarLoc is indexed in the (function-scope) -/// VarLocMap, giving each VarLoc a unique index. Rather than operate directly -/// on machine locations, the dataflow analysis in this pass identifies -/// locations by their index in the VarLocMap, meaning all the variable -/// locations in a block can be described by a sparse vector of VarLocMap -/// indexes. -/// //===----------------------------------------------------------------------===// #include "llvm/ADT/DenseMap.h" @@ -57,7 +48,6 @@ #include "llvm/IR/DebugLoc.h" #include "llvm/IR/Function.h" #include "llvm/IR/Module.h" -#include "llvm/InitializePasses.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" @@ -78,7 +68,6 @@ using namespace llvm; #define DEBUG_TYPE "livedebugvalues" STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); -STATISTIC(NumRemoved, "Number of DBG_VALUE instructions removed"); // If @MI is a DBG_VALUE with debug value described by a defined // register, returns the number of this register. In the other case, returns 0. @@ -90,28 +79,8 @@ static Register isDbgValueDescribedByReg(const MachineInstr &MI) { return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : Register(); } -/// If \p Op is a stack or frame register return true, otherwise return false. -/// This is used to avoid basing the debug entry values on the registers, since -/// we do not support it at the moment. -static bool isRegOtherThanSPAndFP(const MachineOperand &Op, - const MachineInstr &MI, - const TargetRegisterInfo *TRI) { - if (!Op.isReg()) - return false; - - const MachineFunction *MF = MI.getParent()->getParent(); - const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); - unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); - Register FP = TRI->getFrameRegister(*MF); - Register Reg = Op.getReg(); - - return Reg && Reg != SP && Reg != FP; -} - namespace { -using DefinedRegsSet = SmallSet<Register, 32>; - class LiveDebugValues : public MachineFunctionPass { private: const TargetRegisterInfo *TRI; @@ -144,6 +113,60 @@ private: using FragmentInfo = DIExpression::FragmentInfo; using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; + /// Storage for identifying a potentially inlined instance of a variable, + /// or a fragment thereof. + class DebugVariable { + const DILocalVariable *Variable; + OptFragmentInfo Fragment; + const DILocation *InlinedAt; + + /// Fragment that will overlap all other fragments. Used as default when + /// caller demands a fragment. + static const FragmentInfo DefaultFragment; + + public: + DebugVariable(const DILocalVariable *Var, OptFragmentInfo &&FragmentInfo, + const DILocation *InlinedAt) + : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {} + + DebugVariable(const DILocalVariable *Var, OptFragmentInfo &FragmentInfo, + const DILocation *InlinedAt) + : Variable(Var), Fragment(FragmentInfo), InlinedAt(InlinedAt) {} + + DebugVariable(const DILocalVariable *Var, const DIExpression *DIExpr, + const DILocation *InlinedAt) + : DebugVariable(Var, DIExpr->getFragmentInfo(), InlinedAt) {} + + DebugVariable(const MachineInstr &MI) + : DebugVariable(MI.getDebugVariable(), + MI.getDebugExpression()->getFragmentInfo(), + MI.getDebugLoc()->getInlinedAt()) {} + + const DILocalVariable *getVar() const { return Variable; } + const OptFragmentInfo &getFragment() const { return Fragment; } + const DILocation *getInlinedAt() const { return InlinedAt; } + + const FragmentInfo getFragmentDefault() const { + return Fragment.getValueOr(DefaultFragment); + } + + static bool isFragmentDefault(FragmentInfo &F) { + return F == DefaultFragment; + } + + bool operator==(const DebugVariable &Other) const { + return std::tie(Variable, Fragment, InlinedAt) == + std::tie(Other.Variable, Other.Fragment, Other.InlinedAt); + } + + bool operator<(const DebugVariable &Other) const { + return std::tie(Variable, Fragment, InlinedAt) < + std::tie(Other.Variable, Other.Fragment, Other.InlinedAt); + } + }; + + friend struct llvm::DenseMapInfo<DebugVariable>; + /// A pair of debug variable and value location. struct VarLoc { // The location at which a spilled variable resides. It consists of a @@ -156,25 +179,15 @@ private: } }; - /// Identity of the variable at this location. const DebugVariable Var; - - /// The expression applied to this location. - const DIExpression *Expr; - - /// DBG_VALUE to clone var/expr information from if this location - /// is moved. - const MachineInstr &MI; - + const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE. mutable UserValueScopes UVS; enum VarLocKind { InvalidKind = 0, RegisterKind, SpillLocKind, ImmediateKind, - EntryValueKind, - EntryValueBackupKind, - EntryValueCopyBackupKind + EntryValueKind } Kind = InvalidKind; /// The value location. Stored separately to avoid repeatedly @@ -188,16 +201,15 @@ private: const ConstantInt *CImm; } Loc; - VarLoc(const MachineInstr &MI, LexicalScopes &LS) - : Var(MI.getDebugVariable(), MI.getDebugExpression(), - MI.getDebugLoc()->getInlinedAt()), - Expr(MI.getDebugExpression()), MI(MI), UVS(MI.getDebugLoc(), LS) { + VarLoc(const MachineInstr &MI, LexicalScopes &LS, + VarLocKind K = InvalidKind) + : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS){ static_assert((sizeof(Loc) == sizeof(uint64_t)), "hash does not cover all members of Loc"); assert(MI.isDebugValue() && "not a DBG_VALUE"); assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); if (int RegNo = isDbgValueDescribedByReg(MI)) { - Kind = RegisterKind; + Kind = MI.isDebugEntryValue() ? EntryValueKind : RegisterKind; Loc.RegNo = RegNo; } else if (MI.getOperand(0).isImm()) { Kind = ImmediateKind; @@ -209,144 +221,23 @@ private: Kind = ImmediateKind; Loc.CImm = MI.getOperand(0).getCImm(); } - - // We create the debug entry values from the factory functions rather than - // from this ctor. - assert(Kind != EntryValueKind && !isEntryBackupLoc()); - } - - /// Take the variable and machine-location in DBG_VALUE MI, and build an - /// entry location using the given expression. - static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS, - const DIExpression *EntryExpr, unsigned Reg) { - VarLoc VL(MI, LS); - assert(VL.Kind == RegisterKind); - VL.Kind = EntryValueKind; - VL.Expr = EntryExpr; - VL.Loc.RegNo = Reg; - return VL; - } - - /// Take the variable and machine-location from the DBG_VALUE (from the - /// function entry), and build an entry value backup location. The backup - /// location will turn into the normal location if the backup is valid at - /// the time of the primary location clobbering. - static VarLoc CreateEntryBackupLoc(const MachineInstr &MI, - LexicalScopes &LS, - const DIExpression *EntryExpr) { - VarLoc VL(MI, LS); - assert(VL.Kind == RegisterKind); - VL.Kind = EntryValueBackupKind; - VL.Expr = EntryExpr; - return VL; - } - - /// Take the variable and machine-location from the DBG_VALUE (from the - /// function entry), and build a copy of an entry value backup location by - /// setting the register location to NewReg. - static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI, - LexicalScopes &LS, - const DIExpression *EntryExpr, - unsigned NewReg) { - VarLoc VL(MI, LS); - assert(VL.Kind == RegisterKind); - VL.Kind = EntryValueCopyBackupKind; - VL.Expr = EntryExpr; - VL.Loc.RegNo = NewReg; - return VL; - } - - /// Copy the register location in DBG_VALUE MI, updating the register to - /// be NewReg. - static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS, - unsigned NewReg) { - VarLoc VL(MI, LS); - assert(VL.Kind == RegisterKind); - VL.Loc.RegNo = NewReg; - return VL; - } - - /// Take the variable described by DBG_VALUE MI, and create a VarLoc - /// locating it in the specified spill location. - static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase, - int SpillOffset, LexicalScopes &LS) { - VarLoc VL(MI, LS); - assert(VL.Kind == RegisterKind); - VL.Kind = SpillLocKind; - VL.Loc.SpillLocation = {SpillBase, SpillOffset}; - return VL; + assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) && + "entry values must be register locations"); } - /// Create a DBG_VALUE representing this VarLoc in the given function. - /// Copies variable-specific information such as DILocalVariable and - /// inlining information from the original DBG_VALUE instruction, which may - /// have been several transfers ago. - MachineInstr *BuildDbgValue(MachineFunction &MF) const { - const DebugLoc &DbgLoc = MI.getDebugLoc(); - bool Indirect = MI.isIndirectDebugValue(); - const auto &IID = MI.getDesc(); - const DILocalVariable *Var = MI.getDebugVariable(); - const DIExpression *DIExpr = MI.getDebugExpression(); - - switch (Kind) { - case EntryValueKind: - // An entry value is a register location -- but with an updated - // expression. The register location of such DBG_VALUE is always the one - // from the entry DBG_VALUE, it does not matter if the entry value was - // copied in to another register due to some optimizations. - return BuildMI(MF, DbgLoc, IID, Indirect, MI.getOperand(0).getReg(), - Var, Expr); - case RegisterKind: - // Register locations are like the source DBG_VALUE, but with the - // register number from this VarLoc. - return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr); - case SpillLocKind: { - // Spills are indirect DBG_VALUEs, with a base register and offset. - // Use the original DBG_VALUEs expression to build the spilt location - // on top of. FIXME: spill locations created before this pass runs - // are not recognized, and not handled here. - auto *SpillExpr = DIExpression::prepend( - DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset); - unsigned Base = Loc.SpillLocation.SpillBase; - return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr); - } - case ImmediateKind: { - MachineOperand MO = MI.getOperand(0); - return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr); - } - case EntryValueBackupKind: - case EntryValueCopyBackupKind: - case InvalidKind: - llvm_unreachable( - "Tried to produce DBG_VALUE for invalid or backup VarLoc"); - } - llvm_unreachable("Unrecognized LiveDebugValues.VarLoc.Kind enum"); + /// The constructor for spill locations. + VarLoc(const MachineInstr &MI, unsigned SpillBase, int SpillOffset, + LexicalScopes &LS) + : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS) { + assert(MI.isDebugValue() && "not a DBG_VALUE"); + assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); + Kind = SpillLocKind; + Loc.SpillLocation = {SpillBase, SpillOffset}; } - /// Is the Loc field a constant or constant object? + // Is the Loc field a constant or constant object? bool isConstant() const { return Kind == ImmediateKind; } - /// Check if the Loc field is an entry backup location. - bool isEntryBackupLoc() const { - return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind; - } - - /// If this variable is described by a register holding the entry value, - /// return it, otherwise return 0. - unsigned getEntryValueBackupReg() const { - if (Kind == EntryValueBackupKind) - return Loc.RegNo; - return 0; - } - - /// If this variable is described by a register holding the copy of the - /// entry value, return it, otherwise return 0. - unsigned getEntryValueCopyBackupReg() const { - if (Kind == EntryValueCopyBackupKind) - return Loc.RegNo; - return 0; - } - /// If this variable is described by a register, return it, /// otherwise return 0. unsigned isDescribedByReg() const { @@ -360,59 +251,28 @@ private: bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - // TRI can be null. - void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const { - dbgs() << "VarLoc("; - switch (Kind) { - case RegisterKind: - case EntryValueKind: - case EntryValueBackupKind: - case EntryValueCopyBackupKind: - dbgs() << printReg(Loc.RegNo, TRI); - break; - case SpillLocKind: - dbgs() << printReg(Loc.SpillLocation.SpillBase, TRI); - dbgs() << "[" << Loc.SpillLocation.SpillOffset << "]"; - break; - case ImmediateKind: - dbgs() << Loc.Immediate; - break; - case InvalidKind: - llvm_unreachable("Invalid VarLoc in dump method"); - } - - dbgs() << ", \"" << Var.getVariable()->getName() << "\", " << *Expr - << ", "; - if (Var.getInlinedAt()) - dbgs() << "!" << Var.getInlinedAt()->getMetadataID() << ")\n"; - else - dbgs() << "(null))"; - - if (isEntryBackupLoc()) - dbgs() << " (backup loc)\n"; - else - dbgs() << "\n"; - } + LLVM_DUMP_METHOD void dump() const { MI.dump(); } #endif bool operator==(const VarLoc &Other) const { return Kind == Other.Kind && Var == Other.Var && - Loc.Hash == Other.Loc.Hash && Expr == Other.Expr; + Loc.Hash == Other.Loc.Hash; } /// This operator guarantees that VarLocs are sorted by Variable first. bool operator<(const VarLoc &Other) const { - return std::tie(Var, Kind, Loc.Hash, Expr) < - std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr); + return std::tie(Var, Kind, Loc.Hash) < + std::tie(Other.Var, Other.Kind, Other.Loc.Hash); } }; + using DebugParamMap = SmallDenseMap<const DILocalVariable *, MachineInstr *>; using VarLocMap = UniqueVector<VarLoc>; using VarLocSet = SparseBitVector<>; using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>; struct TransferDebugPair { - MachineInstr *TransferInst; /// Instruction where this transfer occurs. - unsigned LocationID; /// Location number for the transfer dest. + MachineInstr *TransferInst; + MachineInstr *DebugInst; }; using TransferMap = SmallVector<TransferDebugPair, 4>; @@ -432,18 +292,10 @@ private: /// This holds the working set of currently open ranges. For fast /// access, this is done both as a set of VarLocIDs, and a map of /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all - /// previous open ranges for the same variable. In addition, we keep - /// two different maps (Vars/EntryValuesBackupVars), so erase/insert - /// methods act differently depending on whether a VarLoc is primary - /// location or backup one. In the case the VarLoc is backup location - /// we will erase/insert from the EntryValuesBackupVars map, otherwise - /// we perform the operation on the Vars. + /// previous open ranges for the same variable. class OpenRangesSet { VarLocSet VarLocs; - // Map the DebugVariable to recent primary location ID. SmallDenseMap<DebugVariable, unsigned, 8> Vars; - // Map the DebugVariable to recent backup location ID. - SmallDenseMap<DebugVariable, unsigned, 8> EntryValuesBackupVars; OverlapMap &OverlappingFragments; public: @@ -451,62 +303,38 @@ private: const VarLocSet &getVarLocs() const { return VarLocs; } - /// Terminate all open ranges for VL.Var by removing it from the set. - void erase(const VarLoc &VL); + /// Terminate all open ranges for Var by removing it from the set. + void erase(DebugVariable Var); /// Terminate all open ranges listed in \c KillSet by removing /// them from the set. - void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs); + void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) { + VarLocs.intersectWithComplement(KillSet); + for (unsigned ID : KillSet) + Vars.erase(VarLocIDs[ID].Var); + } /// Insert a new range into the set. - void insert(unsigned VarLocID, const VarLoc &VL); - - /// Insert a set of ranges. - void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) { - for (unsigned Id : ToLoad) { - const VarLoc &VarL = Map[Id]; - insert(Id, VarL); - } + void insert(unsigned VarLocID, DebugVariable Var) { + VarLocs.set(VarLocID); + Vars.insert({Var, VarLocID}); } - llvm::Optional<unsigned> getEntryValueBackup(DebugVariable Var); - /// Empty the set. void clear() { VarLocs.clear(); Vars.clear(); - EntryValuesBackupVars.clear(); } /// Return whether the set is empty or not. bool empty() const { - assert(Vars.empty() == EntryValuesBackupVars.empty() && - Vars.empty() == VarLocs.empty() && - "open ranges are inconsistent"); + assert(Vars.empty() == VarLocs.empty() && "open ranges are inconsistent"); return VarLocs.empty(); } }; - /// Tests whether this instruction is a spill to a stack location. - bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); - - /// Decide if @MI is a spill instruction and return true if it is. We use 2 - /// criteria to make this decision: - /// - Is this instruction a store to a spill slot? - /// - Is there a register operand that is both used and killed? - /// TODO: Store optimization can fold spills into other stores (including - /// other spills). We do not handle this yet (more than one memory operand). - bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, - unsigned &Reg); - - /// Returns true if the given machine instruction is a debug value which we - /// can emit entry values for. - /// - /// Currently, we generate debug entry values only for parameters that are - /// unmodified throughout the function and located in a register. - bool isEntryValueCandidate(const MachineInstr &MI, - const DefinedRegsSet &Regs) const; - + bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF, + unsigned &Reg); /// If a given instruction is identified as a spill, return the spill location /// and set \p Reg to the spilled register. Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI, @@ -524,23 +352,23 @@ private: VarLocMap &VarLocIDs); void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers); - bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs, const VarLoc &EntryVL); void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers, + DebugParamMap &DebugEntryVals, SparseBitVector<> &KillSet); - void recordEntryValue(const MachineInstr &MI, - const DefinedRegsSet &DefinedRegs, - OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs); void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers); void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs, TransferMap &Transfers); - bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges, - VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); + VarLocMap &VarLocIDs, TransferMap &Transfers, + DebugParamMap &DebugEntryVals); + bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges, + VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); - void process(MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs, TransferMap &Transfers); + bool process(MachineInstr &MI, OpenRangesSet &OpenRanges, + VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, + TransferMap &Transfers, DebugParamMap &DebugEntryVals, + bool transferChanges, OverlapMap &OverlapFragments, + VarToFragments &SeenFragments); void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, OverlapMap &OLapMap); @@ -548,12 +376,7 @@ private: bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, const VarLocMap &VarLocIDs, SmallPtrSet<const MachineBasicBlock *, 16> &Visited, - SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks, - VarLocInMBB &PendingInLocs); - - /// Create DBG_VALUE insts for inlocs that have been propagated but - /// had their instruction creation deferred. - void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs); + SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks); bool ExtendRanges(MachineFunction &MF); @@ -583,10 +406,46 @@ public: } // end anonymous namespace +namespace llvm { + +template <> struct DenseMapInfo<LiveDebugValues::DebugVariable> { + using DV = LiveDebugValues::DebugVariable; + using OptFragmentInfo = LiveDebugValues::OptFragmentInfo; + using FragmentInfo = LiveDebugValues::FragmentInfo; + + // Empty key: no key should be generated that has no DILocalVariable. + static inline DV getEmptyKey() { + return DV(nullptr, OptFragmentInfo(), nullptr); + } + + // Difference in tombstone is that the Optional is meaningful + static inline DV getTombstoneKey() { + return DV(nullptr, OptFragmentInfo({0, 0}), nullptr); + } + + static unsigned getHashValue(const DV &D) { + unsigned HV = 0; + const OptFragmentInfo &Fragment = D.getFragment(); + if (Fragment) + HV = DenseMapInfo<FragmentInfo>::getHashValue(*Fragment); + + return hash_combine(D.getVar(), HV, D.getInlinedAt()); + } + + static bool isEqual(const DV &A, const DV &B) { return A == B; } +}; + +} // namespace llvm + //===----------------------------------------------------------------------===// // Implementation //===----------------------------------------------------------------------===// +const DIExpression::FragmentInfo + LiveDebugValues::DebugVariable::DefaultFragment = { + std::numeric_limits<uint64_t>::max(), + std::numeric_limits<uint64_t>::min()}; + char LiveDebugValues::ID = 0; char &llvm::LiveDebugValuesID = LiveDebugValues::ID; @@ -607,72 +466,38 @@ void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const { } /// Erase a variable from the set of open ranges, and additionally erase any -/// fragments that may overlap it. If the VarLoc is a buckup location, erase -/// the variable from the EntryValuesBackupVars set, indicating we should stop -/// tracking its backup entry location. Otherwise, if the VarLoc is primary -/// location, erase the variable from the Vars set. -void LiveDebugValues::OpenRangesSet::erase(const VarLoc &VL) { +/// fragments that may overlap it. +void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) { // Erasure helper. - auto DoErase = [VL, this](DebugVariable VarToErase) { - auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; - auto It = EraseFrom->find(VarToErase); - if (It != EraseFrom->end()) { + auto DoErase = [this](DebugVariable VarToErase) { + auto It = Vars.find(VarToErase); + if (It != Vars.end()) { unsigned ID = It->second; VarLocs.reset(ID); - EraseFrom->erase(It); + Vars.erase(It); } }; - DebugVariable Var = VL.Var; - // Erase the variable/fragment that ends here. DoErase(Var); // Extract the fragment. Interpret an empty fragment as one that covers all // possible bits. - FragmentInfo ThisFragment = Var.getFragmentOrDefault(); + FragmentInfo ThisFragment = Var.getFragmentDefault(); // There may be fragments that overlap the designated fragment. Look them up // in the pre-computed overlap map, and erase them too. - auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment}); + auto MapIt = OverlappingFragments.find({Var.getVar(), ThisFragment}); if (MapIt != OverlappingFragments.end()) { for (auto Fragment : MapIt->second) { LiveDebugValues::OptFragmentInfo FragmentHolder; - if (!DebugVariable::isDefaultFragment(Fragment)) + if (!DebugVariable::isFragmentDefault(Fragment)) FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment); - DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()}); + DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()}); } } } -void LiveDebugValues::OpenRangesSet::erase(const VarLocSet &KillSet, - const VarLocMap &VarLocIDs) { - VarLocs.intersectWithComplement(KillSet); - for (unsigned ID : KillSet) { - const VarLoc *VL = &VarLocIDs[ID]; - auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; - EraseFrom->erase(VL->Var); - } -} - -void LiveDebugValues::OpenRangesSet::insert(unsigned VarLocID, - const VarLoc &VL) { - auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; - VarLocs.set(VarLocID); - InsertInto->insert({VL.Var, VarLocID}); -} - -/// Return the Loc ID of an entry value backup location, if it exists for the -/// variable. -llvm::Optional<unsigned> -LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { - auto It = EntryValuesBackupVars.find(Var); - if (It != EntryValuesBackupVars.end()) - return It->second; - - return llvm::None; -} - //===----------------------------------------------------------------------===// // Debug Range Extension Implementation //===----------------------------------------------------------------------===// @@ -691,9 +516,9 @@ void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF, Out << "MBB: " << BB.getNumber() << ":\n"; for (unsigned VLL : L) { const VarLoc &VL = VarLocIDs[VLL]; - Out << " Var: " << VL.Var.getVariable()->getName(); + Out << " Var: " << VL.Var.getVar()->getName(); Out << " MI: "; - VL.dump(TRI, Out); + VL.dump(); } } Out << "\n"; @@ -715,62 +540,6 @@ LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) { return {Reg, Offset}; } -/// Try to salvage the debug entry value if we encounter a new debug value -/// describing the same parameter, otherwise stop tracking the value. Return -/// true if we should stop tracking the entry value, otherwise return false. -bool LiveDebugValues::removeEntryValue(const MachineInstr &MI, - OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs, - const VarLoc &EntryVL) { - // Skip the DBG_VALUE which is the debug entry value itself. - if (MI.isIdenticalTo(EntryVL.MI)) - return false; - - // If the parameter's location is not register location, we can not track - // the entry value any more. In addition, if the debug expression from the - // DBG_VALUE is not empty, we can assume the parameter's value has changed - // indicating that we should stop tracking its entry value as well. - if (!MI.getOperand(0).isReg() || - MI.getDebugExpression()->getNumElements() != 0) - return true; - - // If the DBG_VALUE comes from a copy instruction that copies the entry value, - // it means the parameter's value has not changed and we should be able to use - // its entry value. - bool TrySalvageEntryValue = false; - Register Reg = MI.getOperand(0).getReg(); - auto I = std::next(MI.getReverseIterator()); - const MachineOperand *SrcRegOp, *DestRegOp; - if (I != MI.getParent()->rend()) { - // TODO: Try to keep tracking of an entry value if we encounter a propagated - // DBG_VALUE describing the copy of the entry value. (Propagated entry value - // does not indicate the parameter modification.) - auto DestSrc = TII->isCopyInstr(*I); - if (!DestSrc) - return true; - - SrcRegOp = DestSrc->Source; - DestRegOp = DestSrc->Destination; - if (Reg != DestRegOp->getReg()) - return true; - TrySalvageEntryValue = true; - } - - if (TrySalvageEntryValue) { - for (unsigned ID : OpenRanges.getVarLocs()) { - const VarLoc &VL = VarLocIDs[ID]; - if (!VL.isEntryBackupLoc()) - continue; - - if (VL.getEntryValueCopyBackupReg() == Reg && - VL.MI.getOperand(0).getReg() == SrcRegOp->getReg()) - return false; - } - } - - return true; -} - /// End all previous ranges related to @MI and start a new range from @MI /// if it is a DBG_VALUE instr. void LiveDebugValues::transferDebugValue(const MachineInstr &MI, @@ -785,35 +554,24 @@ void LiveDebugValues::transferDebugValue(const MachineInstr &MI, assert(Var->isValidLocationForIntrinsic(DebugLoc) && "Expected inlined-at fields to agree"); + // End all previous ranges of Var. DebugVariable V(Var, Expr, InlinedAt); + OpenRanges.erase(V); - // Check if this DBG_VALUE indicates a parameter's value changing. - // If that is the case, we should stop tracking its entry value. - auto EntryValBackupID = OpenRanges.getEntryValueBackup(V); - if (Var->isParameter() && EntryValBackupID) { - const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; - if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) { - LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: "; - MI.print(dbgs(), /*IsStandalone*/ false, - /*SkipOpers*/ false, /*SkipDebugLoc*/ false, - /*AddNewLine*/ true, TII)); - OpenRanges.erase(EntryVL); - } - } - + // Add the VarLoc to OpenRanges from this DBG_VALUE. unsigned ID; if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) { // Use normal VarLoc constructor for registers and immediates. VarLoc VL(MI, LS); - // End all previous ranges of VL.Var. - OpenRanges.erase(VL); - ID = VarLocIDs.insert(VL); - // Add the VarLoc to OpenRanges from this DBG_VALUE. - OpenRanges.insert(ID, VL); + OpenRanges.insert(ID, VL.Var); } else if (MI.hasOneMemOperand()) { - llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?"); + // It's a stack spill -- fetch spill base and offset. + VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI); + VarLoc VL(MI, SpillLocation.SpillBase, SpillLocation.SpillOffset, LS); + ID = VarLocIDs.insert(VL); + OpenRanges.insert(ID, VL.Var); } else { // This must be an undefined location. We should leave OpenRanges closed. assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 && @@ -821,30 +579,41 @@ void LiveDebugValues::transferDebugValue(const MachineInstr &MI, } } -/// Turn the entry value backup locations into primary locations. void LiveDebugValues::emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers, + DebugParamMap &DebugEntryVals, SparseBitVector<> &KillSet) { + MachineFunction *MF = MI.getParent()->getParent(); for (unsigned ID : KillSet) { - if (!VarLocIDs[ID].Var.getVariable()->isParameter()) + if (!VarLocIDs[ID].Var.getVar()->isParameter()) continue; - auto DebugVar = VarLocIDs[ID].Var; - auto EntryValBackupID = OpenRanges.getEntryValueBackup(DebugVar); + const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI; - // If the parameter has the entry value backup, it means we should - // be able to use its entry value. - if (!EntryValBackupID) + // If parameter's DBG_VALUE is not in the map that means we can't + // generate parameter's entry value. + if (!DebugEntryVals.count(CurrDebugInstr->getDebugVariable())) continue; - const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; - VarLoc EntryLoc = - VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo); - unsigned EntryValueID = VarLocIDs.insert(EntryLoc); - Transfers.push_back({&MI, EntryValueID}); - OpenRanges.insert(EntryValueID, EntryLoc); + auto ParamDebugInstr = DebugEntryVals[CurrDebugInstr->getDebugVariable()]; + DIExpression *NewExpr = DIExpression::prepend( + ParamDebugInstr->getDebugExpression(), DIExpression::EntryValue); + MachineInstr *EntryValDbgMI = + BuildMI(*MF, ParamDebugInstr->getDebugLoc(), ParamDebugInstr->getDesc(), + ParamDebugInstr->isIndirectDebugValue(), + ParamDebugInstr->getOperand(0).getReg(), + ParamDebugInstr->getDebugVariable(), NewExpr); + + if (ParamDebugInstr->isIndirectDebugValue()) + EntryValDbgMI->getOperand(1).setImm( + ParamDebugInstr->getOperand(1).getImm()); + + Transfers.push_back({&MI, EntryValDbgMI}); + VarLoc VL(*EntryValDbgMI, LS); + unsigned EntryValLocID = VarLocIDs.insert(VL); + OpenRanges.insert(EntryValLocID, VL.Var); } } @@ -858,60 +627,87 @@ void LiveDebugValues::insertTransferDebugPair( VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind, unsigned NewReg) { const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI; + MachineFunction *MF = MI.getParent()->getParent(); + MachineInstr *NewDebugInstr; - auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) { + auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &DebugInstr, + &VarLocIDs](VarLoc &VL, MachineInstr *NewDebugInstr) { unsigned LocId = VarLocIDs.insert(VL); // Close this variable's previous location range. - OpenRanges.erase(VL); + DebugVariable V(*DebugInstr); + OpenRanges.erase(V); - // Record the new location as an open range, and a postponed transfer - // inserting a DBG_VALUE for this location. - OpenRanges.insert(LocId, VL); - TransferDebugPair MIP = {&MI, LocId}; + OpenRanges.insert(LocId, VL.Var); + // The newly created DBG_VALUE instruction NewDebugInstr must be inserted + // after MI. Keep track of the pairing. + TransferDebugPair MIP = {&MI, NewDebugInstr}; Transfers.push_back(MIP); }; - // End all previous ranges of VL.Var. - OpenRanges.erase(VarLocIDs[OldVarID]); + // End all previous ranges of Var. + OpenRanges.erase(VarLocIDs[OldVarID].Var); switch (Kind) { case TransferKind::TransferCopy: { assert(NewReg && "No register supplied when handling a copy of a debug value"); // Create a DBG_VALUE instruction to describe the Var in its new // register location. - VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); - ProcessVarLoc(VL); - LLVM_DEBUG({ - dbgs() << "Creating VarLoc for register copy:"; - VL.dump(TRI); - }); + NewDebugInstr = BuildMI( + *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), + DebugInstr->isIndirectDebugValue(), NewReg, + DebugInstr->getDebugVariable(), DebugInstr->getDebugExpression()); + if (DebugInstr->isIndirectDebugValue()) + NewDebugInstr->getOperand(1).setImm(DebugInstr->getOperand(1).getImm()); + VarLoc VL(*NewDebugInstr, LS); + ProcessVarLoc(VL, NewDebugInstr); + LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register copy: "; + NewDebugInstr->print(dbgs(), /*IsStandalone*/false, + /*SkipOpers*/false, /*SkipDebugLoc*/false, + /*AddNewLine*/true, TII)); return; } case TransferKind::TransferSpill: { // Create a DBG_VALUE instruction to describe the Var in its spilled // location. VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI); - VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase, - SpillLocation.SpillOffset, LS); - ProcessVarLoc(VL); - LLVM_DEBUG({ - dbgs() << "Creating VarLoc for spill:"; - VL.dump(TRI); - }); + auto *SpillExpr = DIExpression::prepend(DebugInstr->getDebugExpression(), + DIExpression::ApplyOffset, + SpillLocation.SpillOffset); + NewDebugInstr = BuildMI( + *MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), true, + SpillLocation.SpillBase, DebugInstr->getDebugVariable(), SpillExpr); + VarLoc VL(*NewDebugInstr, SpillLocation.SpillBase, + SpillLocation.SpillOffset, LS); + ProcessVarLoc(VL, NewDebugInstr); + LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for spill: "; + NewDebugInstr->print(dbgs(), /*IsStandalone*/false, + /*SkipOpers*/false, /*SkipDebugLoc*/false, + /*AddNewLine*/true, TII)); return; } case TransferKind::TransferRestore: { assert(NewReg && "No register supplied when handling a restore of a debug value"); - // DebugInstr refers to the pre-spill location, therefore we can reuse - // its expression. - VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); - ProcessVarLoc(VL); - LLVM_DEBUG({ - dbgs() << "Creating VarLoc for restore:"; - VL.dump(TRI); - }); + MachineFunction *MF = MI.getMF(); + DIBuilder DIB(*const_cast<Function &>(MF->getFunction()).getParent()); + + const DIExpression *NewExpr; + if (auto Fragment = DebugInstr->getDebugExpression()->getFragmentInfo()) + NewExpr = *DIExpression::createFragmentExpression(DIB.createExpression(), + Fragment->OffsetInBits, Fragment->SizeInBits); + else + NewExpr = DIB.createExpression(); + + NewDebugInstr = + BuildMI(*MF, DebugInstr->getDebugLoc(), DebugInstr->getDesc(), false, + NewReg, DebugInstr->getDebugVariable(), NewExpr); + VarLoc VL(*NewDebugInstr, LS); + ProcessVarLoc(VL, NewDebugInstr); + LLVM_DEBUG(dbgs() << "Creating DBG_VALUE inst for register restore: "; + NewDebugInstr->print(dbgs(), /*IsStandalone*/false, + /*SkipOpers*/false, /*SkipDebugLoc*/false, + /*AddNewLine*/true, TII)); return; } } @@ -921,7 +717,7 @@ void LiveDebugValues::insertTransferDebugPair( /// A definition of a register may mark the end of a range. void LiveDebugValues::transferRegisterDef( MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, - TransferMap &Transfers) { + TransferMap &Transfers, DebugParamMap &DebugEntryVals) { MachineFunction *MF = MI.getMF(); const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); @@ -931,7 +727,7 @@ void LiveDebugValues::transferRegisterDef( // instructions never clobber SP, because some backends (e.g., AArch64) // never list SP in the regmask. if (MO.isReg() && MO.isDef() && MO.getReg() && - Register::isPhysicalRegister(MO.getReg()) && + TRI->isPhysicalRegister(MO.getReg()) && !(MI.isCall() && MO.getReg() == SP)) { // Remove ranges of all aliased registers. for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) @@ -955,12 +751,21 @@ void LiveDebugValues::transferRegisterDef( if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) { auto &TM = TPC->getTM<TargetMachine>(); if (TM.Options.EnableDebugEntryValues) - emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet); + emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals, + KillSet); } } +/// Decide if @MI is a spill instruction and return true if it is. We use 2 +/// criteria to make this decision: +/// - Is this instruction a store to a spill slot? +/// - Is there a register operand that is both used and killed? +/// TODO: Store optimization can fold spills into other stores (including +/// other spills). We do not handle this yet (more than one memory operand). bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI, - MachineFunction *MF) { + MachineFunction *MF, unsigned &Reg) { + SmallVector<const MachineMemOperand*, 1> Accesses; + // TODO: Handle multiple stores folded into one. if (!MI.hasOneMemOperand()) return false; @@ -969,14 +774,6 @@ bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI, return false; // This is not a spill instruction, since no valid size was // returned from either function. - return true; -} - -bool LiveDebugValues::isLocationSpill(const MachineInstr &MI, - MachineFunction *MF, unsigned &Reg) { - if (!isSpillInstruction(MI, MF)) - return false; - auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) { if (!MO.isReg() || !MO.isUse()) { Reg = 0; @@ -1045,37 +842,7 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); - // First, if there are any DBG_VALUEs pointing at a spill slot that is - // written to, then close the variable location. The value in memory - // will have changed. - VarLocSet KillSet; - if (isSpillInstruction(MI, MF)) { - Loc = extractSpillBaseRegAndOffset(MI); - for (unsigned ID : OpenRanges.getVarLocs()) { - const VarLoc &VL = VarLocIDs[ID]; - if (VL.Kind == VarLoc::SpillLocKind && VL.Loc.SpillLocation == *Loc) { - // This location is overwritten by the current instruction -- terminate - // the open range, and insert an explicit DBG_VALUE $noreg. - // - // Doing this at a later stage would require re-interpreting all - // DBG_VALUes and DIExpressions to identify whether they point at - // memory, and then analysing all memory writes to see if they - // overwrite that memory, which is expensive. - // - // At this stage, we already know which DBG_VALUEs are for spills and - // where they are located; it's best to fix handle overwrites now. - KillSet.set(ID); - VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0); - unsigned UndefLocID = VarLocIDs.insert(UndefVL); - Transfers.push_back({&MI, UndefLocID}); - } - } - OpenRanges.erase(KillSet, VarLocIDs); - } - - // Try to recognise spill and restore instructions that may create a new - // variable location. - if (isLocationSpill(MI, MF, Reg)) { + if (isSpillInstruction(MI, MF, Reg)) { TKind = TransferKind::TransferSpill; LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump();); LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) @@ -1089,16 +856,20 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, << "\n"); } // Check if the register or spill location is the location of a debug value. + // FIXME: Don't create a spill transfer if there is a complex expression, + // because we currently cannot recover the original expression on restore. for (unsigned ID : OpenRanges.getVarLocs()) { + const MachineInstr *DebugInstr = &VarLocIDs[ID].MI; + if (TKind == TransferKind::TransferSpill && - VarLocIDs[ID].isDescribedByReg() == Reg) { + VarLocIDs[ID].isDescribedByReg() == Reg && + !DebugInstr->getDebugExpression()->isComplex()) { LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '(' - << VarLocIDs[ID].Var.getVariable()->getName() << ")\n"); + << VarLocIDs[ID].Var.getVar()->getName() << ")\n"); } else if (TKind == TransferKind::TransferRestore && - VarLocIDs[ID].Kind == VarLoc::SpillLocKind && VarLocIDs[ID].Loc.SpillLocation == *Loc) { LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '(' - << VarLocIDs[ID].Var.getVariable()->getName() << ")\n"); + << VarLocIDs[ID].Var.getVar()->getName() << ")\n"); } else continue; insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind, @@ -1114,56 +885,28 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers) { - auto DestSrc = TII->isCopyInstr(MI); - if (!DestSrc) - return; - - const MachineOperand *DestRegOp = DestSrc->Destination; - const MachineOperand *SrcRegOp = DestSrc->Source; + const MachineOperand *SrcRegOp, *DestRegOp; - if (!DestRegOp->isDef()) + if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() || + !DestRegOp->isDef()) return; - auto isCalleeSavedReg = [&](unsigned Reg) { + auto isCalleSavedReg = [&](unsigned Reg) { for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) if (CalleeSavedRegs.test(*RAI)) return true; return false; }; - Register SrcReg = SrcRegOp->getReg(); - Register DestReg = DestRegOp->getReg(); + unsigned SrcReg = SrcRegOp->getReg(); + unsigned DestReg = DestRegOp->getReg(); // We want to recognize instructions where destination register is callee // saved register. If register that could be clobbered by the call is // included, there would be a great chance that it is going to be clobbered // soon. It is more likely that previous register location, which is callee // saved, is going to stay unclobbered longer, even if it is killed. - if (!isCalleeSavedReg(DestReg)) - return; - - // Remember an entry value movement. If we encounter a new debug value of - // a parameter describing only a moving of the value around, rather then - // modifying it, we are still able to use the entry value if needed. - if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) { - for (unsigned ID : OpenRanges.getVarLocs()) { - if (VarLocIDs[ID].getEntryValueBackupReg() == SrcReg) { - LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump();); - VarLoc EntryValLocCopyBackup = VarLoc::CreateEntryCopyBackupLoc( - VarLocIDs[ID].MI, LS, VarLocIDs[ID].Expr, DestReg); - - // Stop tracking the original entry value. - OpenRanges.erase(VarLocIDs[ID]); - - // Start tracking the entry value copy. - unsigned EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup); - OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup); - break; - } - } - } - - if (!SrcRegOp->isKill()) + if (!isCalleSavedReg(DestReg)) return; for (unsigned ID : OpenRanges.getVarLocs()) { @@ -1176,20 +919,26 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, } /// Terminate all open ranges at the end of the current basic block. -bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB, - OpenRangesSet &OpenRanges, - VarLocInMBB &OutLocs, - const VarLocMap &VarLocIDs) { +bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, + OpenRangesSet &OpenRanges, + VarLocInMBB &OutLocs, + const VarLocMap &VarLocIDs) { bool Changed = false; + const MachineBasicBlock *CurMBB = MI.getParent(); + if (!(MI.isTerminator() || (&MI == &CurMBB->back()))) + return false; + + if (OpenRanges.empty()) + return false; LLVM_DEBUG(for (unsigned ID : OpenRanges.getVarLocs()) { // Copy OpenRanges to OutLocs, if not already present. dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": "; - VarLocIDs[ID].dump(TRI); + VarLocIDs[ID].dump(); }); VarLocSet &VLS = OutLocs[CurMBB]; - Changed = VLS != OpenRanges.getVarLocs(); + Changed = VLS |= OpenRanges.getVarLocs(); // New OutLocs set may be different due to spill, restore or register // copy instruction processing. if (Changed) @@ -1211,27 +960,26 @@ bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB, void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, OverlapMap &OverlappingFragments) { - DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), - MI.getDebugLoc()->getInlinedAt()); - FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); + DebugVariable MIVar(MI); + FragmentInfo ThisFragment = MIVar.getFragmentDefault(); // If this is the first sighting of this variable, then we are guaranteed // there are currently no overlapping fragments either. Initialize the set // of seen fragments, record no overlaps for the current one, and return. - auto SeenIt = SeenFragments.find(MIVar.getVariable()); + auto SeenIt = SeenFragments.find(MIVar.getVar()); if (SeenIt == SeenFragments.end()) { SmallSet<FragmentInfo, 4> OneFragment; OneFragment.insert(ThisFragment); - SeenFragments.insert({MIVar.getVariable(), OneFragment}); + SeenFragments.insert({MIVar.getVar(), OneFragment}); - OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); + OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}}); return; } // If this particular Variable/Fragment pair already exists in the overlap // map, it has already been accounted for. auto IsInOLapMap = - OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); + OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}}); if (!IsInOLapMap.second) return; @@ -1249,7 +997,7 @@ void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, // Mark the previously seen fragment as being overlapped by the current // one. auto ASeenFragmentsOverlaps = - OverlappingFragments.find({MIVar.getVariable(), ASeenFragment}); + OverlappingFragments.find({MIVar.getVar(), ASeenFragment}); assert(ASeenFragmentsOverlaps != OverlappingFragments.end() && "Previously seen var fragment has no vector of overlaps"); ASeenFragmentsOverlaps->second.push_back(ThisFragment); @@ -1259,13 +1007,27 @@ void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, AllSeenFragments.insert(ThisFragment); } -/// This routine creates OpenRanges. -void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs, TransferMap &Transfers) { +/// This routine creates OpenRanges and OutLocs. +bool LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges, + VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, + TransferMap &Transfers, DebugParamMap &DebugEntryVals, + bool transferChanges, + OverlapMap &OverlapFragments, + VarToFragments &SeenFragments) { + bool Changed = false; transferDebugValue(MI, OpenRanges, VarLocIDs); - transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers); - transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers); - transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers); + transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers, + DebugEntryVals); + if (transferChanges) { + transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers); + transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers); + } else { + // Build up a map of overlapping fragments on the first run through. + if (MI.isDebugValue()) + accumulateFragmentMap(MI, SeenFragments, OverlapFragments); + } + Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs); + return Changed; } /// This routine joins the analysis results of all incoming edges in @MBB by @@ -1275,8 +1037,7 @@ bool LiveDebugValues::join( MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, const VarLocMap &VarLocIDs, SmallPtrSet<const MachineBasicBlock *, 16> &Visited, - SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks, - VarLocInMBB &PendingInLocs) { + SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) { LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); bool Changed = false; @@ -1286,11 +1047,9 @@ bool LiveDebugValues::join( // can be joined. int NumVisited = 0; for (auto p : MBB.predecessors()) { - // Ignore backedges if we have not visited the predecessor yet. As the - // predecessor hasn't yet had locations propagated into it, most locations - // will not yet be valid, so treat them as all being uninitialized and - // potentially valid. If a location guessed to be correct here is - // invalidated later, we will remove it when we revisit this block. + // Ignore unvisited predecessor blocks. As we are processing + // the blocks in reverse post-order any unvisited block can + // be considered to not remove any incoming values. if (!Visited.count(p)) { LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber() << "\n"); @@ -1312,7 +1071,7 @@ bool LiveDebugValues::join( if (!InLocsT.empty()) { for (auto ID : InLocsT) dbgs() << " gathered candidate incoming var: " - << VarLocIDs[ID].Var.getVariable()->getName() << "\n"; + << VarLocIDs[ID].Var.getVar()->getName() << "\n"; } }); @@ -1327,7 +1086,7 @@ bool LiveDebugValues::join( if (!VarLocIDs[ID].dominates(MBB)) { KillSet.set(ID); LLVM_DEBUG({ - auto Name = VarLocIDs[ID].Var.getVariable()->getName(); + auto Name = VarLocIDs[ID].Var.getVar()->getName(); dbgs() << " killing " << Name << ", it doesn't dominate MBB\n"; }); } @@ -1340,142 +1099,44 @@ bool LiveDebugValues::join( // is the entry block which has no predecessor. assert((NumVisited || MBB.pred_empty()) && "Should have processed at least one predecessor"); + if (InLocsT.empty()) + return false; VarLocSet &ILS = InLocs[&MBB]; - VarLocSet &Pending = PendingInLocs[&MBB]; - // New locations will have DBG_VALUE insts inserted at the start of the - // block, after location propagation has finished. Record the insertions - // that we need to perform in the Pending set. + // Insert DBG_VALUE instructions, if not already inserted. VarLocSet Diff = InLocsT; Diff.intersectWithComplement(ILS); for (auto ID : Diff) { - Pending.set(ID); + // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a + // new range is started for the var from the mbb's beginning by inserting + // a new DBG_VALUE. process() will end this range however appropriate. + const VarLoc &DiffIt = VarLocIDs[ID]; + const MachineInstr *DebugInstr = &DiffIt.MI; + MachineInstr *MI = nullptr; + if (DiffIt.isConstant()) { + MachineOperand MO(DebugInstr->getOperand(0)); + MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(), + DebugInstr->getDesc(), false, MO, + DebugInstr->getDebugVariable(), + DebugInstr->getDebugExpression()); + } else { + MI = BuildMI(MBB, MBB.instr_begin(), DebugInstr->getDebugLoc(), + DebugInstr->getDesc(), DebugInstr->isIndirectDebugValue(), + DebugInstr->getOperand(0).getReg(), + DebugInstr->getDebugVariable(), + DebugInstr->getDebugExpression()); + if (DebugInstr->isIndirectDebugValue()) + MI->getOperand(1).setImm(DebugInstr->getOperand(1).getImm()); + } + LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump();); ILS.set(ID); ++NumInserted; Changed = true; } - - // We may have lost locations by learning about a predecessor that either - // loses or moves a variable. Find any locations in ILS that are not in the - // new in-locations, and delete those. - VarLocSet Removed = ILS; - Removed.intersectWithComplement(InLocsT); - for (auto ID : Removed) { - Pending.reset(ID); - ILS.reset(ID); - ++NumRemoved; - Changed = true; - } - return Changed; } -void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs, - VarLocMap &VarLocIDs) { - // PendingInLocs records all locations propagated into blocks, which have - // not had DBG_VALUE insts created. Go through and create those insts now. - for (auto &Iter : PendingInLocs) { - // Map is keyed on a constant pointer, unwrap it so we can insert insts. - auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first); - VarLocSet &Pending = Iter.second; - - for (unsigned ID : Pending) { - // The ID location is live-in to MBB -- work out what kind of machine - // location it is and create a DBG_VALUE. - const VarLoc &DiffIt = VarLocIDs[ID]; - if (DiffIt.isEntryBackupLoc()) - continue; - MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent()); - MBB.insert(MBB.instr_begin(), MI); - - (void)MI; - LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump();); - } - } -} - -bool LiveDebugValues::isEntryValueCandidate( - const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const { - assert(MI.isDebugValue() && "This must be DBG_VALUE."); - - // TODO: Add support for local variables that are expressed in terms of - // parameters entry values. - // TODO: Add support for modified arguments that can be expressed - // by using its entry value. - auto *DIVar = MI.getDebugVariable(); - if (!DIVar->isParameter()) - return false; - - // Do not consider parameters that belong to an inlined function. - if (MI.getDebugLoc()->getInlinedAt()) - return false; - - // Do not consider indirect debug values (TODO: explain why). - if (MI.isIndirectDebugValue()) - return false; - - // Only consider parameters that are described using registers. Parameters - // that are passed on the stack are not yet supported, so ignore debug - // values that are described by the frame or stack pointer. - if (!isRegOtherThanSPAndFP(MI.getOperand(0), MI, TRI)) - return false; - - // If a parameter's value has been propagated from the caller, then the - // parameter's DBG_VALUE may be described using a register defined by some - // instruction in the entry block, in which case we shouldn't create an - // entry value. - if (DefinedRegs.count(MI.getOperand(0).getReg())) - return false; - - // TODO: Add support for parameters that have a pre-existing debug expressions - // (e.g. fragments, or indirect parameters using DW_OP_deref). - if (MI.getDebugExpression()->getNumElements() > 0) - return false; - - return true; -} - -/// Collect all register defines (including aliases) for the given instruction. -static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs, - const TargetRegisterInfo *TRI) { - for (const MachineOperand &MO : MI.operands()) - if (MO.isReg() && MO.isDef() && MO.getReg()) - for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) - Regs.insert(*AI); -} - -/// This routine records the entry values of function parameters. The values -/// could be used as backup values. If we loose the track of some unmodified -/// parameters, the backup values will be used as a primary locations. -void LiveDebugValues::recordEntryValue(const MachineInstr &MI, - const DefinedRegsSet &DefinedRegs, - OpenRangesSet &OpenRanges, - VarLocMap &VarLocIDs) { - if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) { - auto &TM = TPC->getTM<TargetMachine>(); - if (!TM.Options.EnableDebugEntryValues) - return; - } - - DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(), - MI.getDebugLoc()->getInlinedAt()); - - if (!isEntryValueCandidate(MI, DefinedRegs) || - OpenRanges.getEntryValueBackup(V)) - return; - - LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump();); - - // Create the entry value and use it as a backup location until it is - // valid. It is valid until a parameter is not changed. - DIExpression *NewExpr = - DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue); - VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr); - unsigned EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup); - OpenRanges.insert(EntryValLocID, EntryValLocAsBackup); -} - /// Calculate the liveness information for the given machine function and /// extend ranges across basic blocks. bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { @@ -1486,16 +1147,12 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { bool MBBJoined = false; VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors. - OverlapMap OverlapFragments; // Map of overlapping variable fragments. + OverlapMap OverlapFragments; // Map of overlapping variable fragments OpenRangesSet OpenRanges(OverlapFragments); // Ranges that are open until end of bb. VarLocInMBB OutLocs; // Ranges that exist beyond bb. VarLocInMBB InLocs; // Ranges that are incoming after joining. - TransferMap Transfers; // DBG_VALUEs associated with transfers (such as - // spills, copies and restores). - VarLocInMBB PendingInLocs; // Ranges that are incoming after joining, but - // that we have deferred creating DBG_VALUE insts - // for immediately. + TransferMap Transfers; // DBG_VALUEs associated with spills. VarToFragments SeenFragments; @@ -1512,27 +1169,62 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { std::greater<unsigned int>> Pending; - // Set of register defines that are seen when traversing the entry block - // looking for debug entry value candidates. - DefinedRegsSet DefinedRegs; + enum : bool { dontTransferChanges = false, transferChanges = true }; + // Besides parameter's modification, check whether a DBG_VALUE is inlined + // in order to deduce whether the variable that it tracks comes from + // a different function. If that is the case we can't track its entry value. + auto IsUnmodifiedFuncParam = [&](const MachineInstr &MI) { + auto *DIVar = MI.getDebugVariable(); + return DIVar->isParameter() && DIVar->isNotModified() && + !MI.getDebugLoc()->getInlinedAt(); + }; + + const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); + unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); + unsigned FP = TRI->getFrameRegister(MF); + auto IsRegOtherThanSPAndFP = [&](const MachineOperand &Op) -> bool { + return Op.isReg() && Op.getReg() != SP && Op.getReg() != FP; + }; + + // Working set of currently collected debug variables mapped to DBG_VALUEs + // representing candidates for production of debug entry values. + DebugParamMap DebugEntryVals; + + MachineBasicBlock &First_MBB = *(MF.begin()); // Only in the case of entry MBB collect DBG_VALUEs representing // function parameters in order to generate debug entry values for them. - MachineBasicBlock &First_MBB = *(MF.begin()); - for (auto &MI : First_MBB) { - collectRegDefs(MI, DefinedRegs, TRI); - if (MI.isDebugValue()) - recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs); - } - - // Initialize per-block structures and scan for fragment overlaps. + // Currently, we generate debug entry values only for parameters that are + // unmodified throughout the function and located in a register. + // TODO: Add support for parameters that are described as fragments. + // TODO: Add support for modified arguments that can be expressed + // by using its entry value. + // TODO: Add support for local variables that are expressed in terms of + // parameters entry values. + for (auto &MI : First_MBB) + if (MI.isDebugValue() && IsUnmodifiedFuncParam(MI) && + !MI.isIndirectDebugValue() && IsRegOtherThanSPAndFP(MI.getOperand(0)) && + !DebugEntryVals.count(MI.getDebugVariable()) && + !MI.getDebugExpression()->isFragment()) + DebugEntryVals[MI.getDebugVariable()] = &MI; + + // Initialize every mbb with OutLocs. + // We are not looking at any spill instructions during the initial pass + // over the BBs. The LiveDebugVariables pass has already created DBG_VALUE + // instructions for spills of registers that are known to be user variables + // within the BB in which the spill occurs. for (auto &MBB : MF) { - PendingInLocs[&MBB] = VarLocSet(); - for (auto &MI : MBB) { - if (MI.isDebugValue()) - accumulateFragmentMap(MI, SeenFragments, OverlapFragments); + process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, DebugEntryVals, + dontTransferChanges, OverlapFragments, SeenFragments); + } + // Add any entry DBG_VALUE instructions necessitated by parameter + // clobbering. + for (auto &TR : Transfers) { + MBB.insertAfter(MachineBasicBlock::iterator(*TR.TransferInst), + TR.DebugInst); } + Transfers.clear(); } auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { @@ -1569,20 +1261,26 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { while (!Worklist.empty()) { MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; Worklist.pop(); - MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, - ArtificialBlocks, PendingInLocs); - MBBJoined |= Visited.insert(MBB).second; + MBBJoined = + join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks); + Visited.insert(MBB); if (MBBJoined) { MBBJoined = false; Changed = true; // Now that we have started to extend ranges across BBs we need to - // examine spill, copy and restore instructions to see whether they - // operate with registers that correspond to user variables. - // First load any pending inlocs. - OpenRanges.insertFromLocSet(PendingInLocs[MBB], VarLocIDs); + // examine spill instructions to see whether they spill registers that + // correspond to user variables. for (auto &MI : *MBB) - process(MI, OpenRanges, VarLocIDs, Transfers); - OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs); + OLChanged |= + process(MI, OpenRanges, OutLocs, VarLocIDs, Transfers, + DebugEntryVals, transferChanges, OverlapFragments, + SeenFragments); + + // Add any DBG_VALUE instructions necessitated by spills. + for (auto &TR : Transfers) + MBB->insertAfter(MachineBasicBlock::iterator(*TR.TransferInst), + TR.DebugInst); + Transfers.clear(); LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after propagating", dbgs())); @@ -1604,19 +1302,6 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { assert(Pending.empty() && "Pending should be empty"); } - // Add any DBG_VALUE instructions created by location transfers. - for (auto &TR : Transfers) { - MachineBasicBlock *MBB = TR.TransferInst->getParent(); - const VarLoc &VL = VarLocIDs[TR.LocationID]; - MachineInstr *MI = VL.BuildDbgValue(MF); - MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI); - } - Transfers.clear(); - - // Deferred inlocs will not have had any DBG_VALUE insts created; do - // that now. - flushPendingLocs(PendingInLocs, VarLocIDs); - LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); return Changed; @@ -1635,7 +1320,8 @@ bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) { TRI = MF.getSubtarget().getRegisterInfo(); TII = MF.getSubtarget().getInstrInfo(); TFI = MF.getSubtarget().getFrameLowering(); - TFI->getCalleeSaves(MF, CalleeSavedRegs); + TFI->determineCalleeSaves(MF, CalleeSavedRegs, + make_unique<RegScavenger>().get()); LS.initialize(MF); bool Changed = ExtendRanges(MF); |