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, 726 insertions, 412 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp index 05e994c9eb51..2226c10b49a4 100644 --- a/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp +++ b/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugValues.cpp @@ -7,14 +7,23 @@ //===----------------------------------------------------------------------===// /// /// This pass implements a data flow analysis that propagates debug location -/// 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. +/// 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). /// /// 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" @@ -48,6 +57,7 @@ #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" @@ -68,6 +78,7 @@ 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. @@ -79,8 +90,28 @@ 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; @@ -113,60 +144,6 @@ 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 @@ -179,15 +156,25 @@ private: } }; + /// Identity of the variable at this location. const DebugVariable Var; - const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE. + + /// 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; + mutable UserValueScopes UVS; enum VarLocKind { InvalidKind = 0, RegisterKind, SpillLocKind, ImmediateKind, - EntryValueKind + EntryValueKind, + EntryValueBackupKind, + EntryValueCopyBackupKind } Kind = InvalidKind; /// The value location. Stored separately to avoid repeatedly @@ -201,15 +188,16 @@ private: const ConstantInt *CImm; } Loc; - VarLoc(const MachineInstr &MI, LexicalScopes &LS, - VarLocKind K = InvalidKind) - : Var(MI), MI(MI), UVS(MI.getDebugLoc(), LS){ + VarLoc(const MachineInstr &MI, LexicalScopes &LS) + : Var(MI.getDebugVariable(), MI.getDebugExpression(), + MI.getDebugLoc()->getInlinedAt()), + Expr(MI.getDebugExpression()), 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 = MI.isDebugEntryValue() ? EntryValueKind : RegisterKind; + Kind = RegisterKind; Loc.RegNo = RegNo; } else if (MI.getOperand(0).isImm()) { Kind = ImmediateKind; @@ -221,23 +209,144 @@ private: Kind = ImmediateKind; Loc.CImm = MI.getOperand(0).getCImm(); } - assert((Kind != ImmediateKind || !MI.isDebugEntryValue()) && - "entry values must be register locations"); + + // We create the debug entry values from the factory functions rather than + // from this ctor. + assert(Kind != EntryValueKind && !isEntryBackupLoc()); } - /// 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}; + /// 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; } - // Is the Loc field a constant or constant object? + /// 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"); + } + + /// 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 { @@ -251,28 +360,59 @@ private: bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - LLVM_DUMP_METHOD void dump() const { MI.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"; + } #endif bool operator==(const VarLoc &Other) const { return Kind == Other.Kind && Var == Other.Var && - Loc.Hash == Other.Loc.Hash; + Loc.Hash == Other.Loc.Hash && Expr == Other.Expr; } /// This operator guarantees that VarLocs are sorted by Variable first. bool operator<(const VarLoc &Other) const { - return std::tie(Var, Kind, Loc.Hash) < - std::tie(Other.Var, Other.Kind, Other.Loc.Hash); + return std::tie(Var, Kind, Loc.Hash, Expr) < + std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr); } }; - using DebugParamMap = SmallDenseMap<const DILocalVariable *, MachineInstr *>; using VarLocMap = UniqueVector<VarLoc>; using VarLocSet = SparseBitVector<>; using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>; struct TransferDebugPair { - MachineInstr *TransferInst; - MachineInstr *DebugInst; + MachineInstr *TransferInst; /// Instruction where this transfer occurs. + unsigned LocationID; /// Location number for the transfer dest. }; using TransferMap = SmallVector<TransferDebugPair, 4>; @@ -292,10 +432,18 @@ 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. + /// 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. 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: @@ -303,38 +451,62 @@ private: const VarLocSet &getVarLocs() const { return VarLocs; } - /// Terminate all open ranges for Var by removing it from the set. - void erase(DebugVariable Var); + /// Terminate all open ranges for VL.Var by removing it from the set. + void erase(const VarLoc &VL); /// Terminate all open ranges listed in \c KillSet by removing /// them from the set. - void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) { - VarLocs.intersectWithComplement(KillSet); - for (unsigned ID : KillSet) - Vars.erase(VarLocIDs[ID].Var); - } + void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs); /// Insert a new range into the set. - void insert(unsigned VarLocID, DebugVariable Var) { - VarLocs.set(VarLocID); - Vars.insert({Var, VarLocID}); + 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); + } } + 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() == VarLocs.empty() && "open ranges are inconsistent"); + assert(Vars.empty() == EntryValuesBackupVars.empty() && + Vars.empty() == VarLocs.empty() && + "open ranges are inconsistent"); return VarLocs.empty(); } }; - bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF, - unsigned &Reg); + /// 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; + /// 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, @@ -352,23 +524,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, - DebugParamMap &DebugEntryVals); - bool transferTerminatorInst(MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); + VarLocMap &VarLocIDs, TransferMap &Transfers); + bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges, + VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); - bool process(MachineInstr &MI, OpenRangesSet &OpenRanges, - VarLocInMBB &OutLocs, VarLocMap &VarLocIDs, - TransferMap &Transfers, DebugParamMap &DebugEntryVals, - bool transferChanges, OverlapMap &OverlapFragments, - VarToFragments &SeenFragments); + void process(MachineInstr &MI, OpenRangesSet &OpenRanges, + VarLocMap &VarLocIDs, TransferMap &Transfers); void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, OverlapMap &OLapMap); @@ -376,7 +548,12 @@ private: bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, const VarLocMap &VarLocIDs, SmallPtrSet<const MachineBasicBlock *, 16> &Visited, - SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks); + 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); bool ExtendRanges(MachineFunction &MF); @@ -406,46 +583,10 @@ 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; @@ -466,38 +607,72 @@ void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const { } /// Erase a variable from the set of open ranges, and additionally erase any -/// fragments that may overlap it. -void LiveDebugValues::OpenRangesSet::erase(DebugVariable Var) { +/// 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) { // Erasure helper. - auto DoErase = [this](DebugVariable VarToErase) { - auto It = Vars.find(VarToErase); - if (It != Vars.end()) { + auto DoErase = [VL, this](DebugVariable VarToErase) { + auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; + auto It = EraseFrom->find(VarToErase); + if (It != EraseFrom->end()) { unsigned ID = It->second; VarLocs.reset(ID); - Vars.erase(It); + EraseFrom->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.getFragmentDefault(); + FragmentInfo ThisFragment = Var.getFragmentOrDefault(); // 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.getVar(), ThisFragment}); + auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment}); if (MapIt != OverlappingFragments.end()) { for (auto Fragment : MapIt->second) { LiveDebugValues::OptFragmentInfo FragmentHolder; - if (!DebugVariable::isFragmentDefault(Fragment)) + if (!DebugVariable::isDefaultFragment(Fragment)) FragmentHolder = LiveDebugValues::OptFragmentInfo(Fragment); - DoErase({Var.getVar(), FragmentHolder, Var.getInlinedAt()}); + DoErase({Var.getVariable(), 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 //===----------------------------------------------------------------------===// @@ -516,9 +691,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.getVar()->getName(); + Out << " Var: " << VL.Var.getVariable()->getName(); Out << " MI: "; - VL.dump(); + VL.dump(TRI, Out); } } Out << "\n"; @@ -540,6 +715,62 @@ 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, @@ -554,24 +785,35 @@ 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); - // Add the VarLoc to OpenRanges from this DBG_VALUE. + // 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); + } + } + 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); - OpenRanges.insert(ID, VL.Var); + // Add the VarLoc to OpenRanges from this DBG_VALUE. + OpenRanges.insert(ID, VL); } else if (MI.hasOneMemOperand()) { - // 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); + llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?"); } else { // This must be an undefined location. We should leave OpenRanges closed. assert(MI.getOperand(0).isReg() && MI.getOperand(0).getReg() == 0 && @@ -579,41 +821,30 @@ 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.getVar()->isParameter()) + if (!VarLocIDs[ID].Var.getVariable()->isParameter()) continue; - const MachineInstr *CurrDebugInstr = &VarLocIDs[ID].MI; + auto DebugVar = VarLocIDs[ID].Var; + auto EntryValBackupID = OpenRanges.getEntryValueBackup(DebugVar); - // 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())) + // If the parameter has the entry value backup, it means we should + // be able to use its entry value. + if (!EntryValBackupID) continue; - 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); + 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); } } @@ -627,87 +858,60 @@ 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, &DebugInstr, - &VarLocIDs](VarLoc &VL, MachineInstr *NewDebugInstr) { + auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) { unsigned LocId = VarLocIDs.insert(VL); // Close this variable's previous location range. - DebugVariable V(*DebugInstr); - OpenRanges.erase(V); + OpenRanges.erase(VL); - 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}; + // 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}; Transfers.push_back(MIP); }; - // End all previous ranges of Var. - OpenRanges.erase(VarLocIDs[OldVarID].Var); + // End all previous ranges of VL.Var. + OpenRanges.erase(VarLocIDs[OldVarID]); 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. - 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)); + VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); + ProcessVarLoc(VL); + LLVM_DEBUG({ + dbgs() << "Creating VarLoc for register copy:"; + VL.dump(TRI); + }); return; } case TransferKind::TransferSpill: { // Create a DBG_VALUE instruction to describe the Var in its spilled // location. VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI); - 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)); + VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase, + SpillLocation.SpillOffset, LS); + ProcessVarLoc(VL); + LLVM_DEBUG({ + dbgs() << "Creating VarLoc for spill:"; + VL.dump(TRI); + }); return; } case TransferKind::TransferRestore: { assert(NewReg && "No register supplied when handling a restore of a debug value"); - 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)); + // 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); + }); return; } } @@ -717,7 +921,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, DebugParamMap &DebugEntryVals) { + TransferMap &Transfers) { MachineFunction *MF = MI.getMF(); const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); @@ -727,7 +931,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() && - TRI->isPhysicalRegister(MO.getReg()) && + Register::isPhysicalRegister(MO.getReg()) && !(MI.isCall() && MO.getReg() == SP)) { // Remove ranges of all aliased registers. for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) @@ -751,21 +955,12 @@ void LiveDebugValues::transferRegisterDef( if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) { auto &TM = TPC->getTM<TargetMachine>(); if (TM.Options.EnableDebugEntryValues) - emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, DebugEntryVals, - KillSet); + emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, 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, unsigned &Reg) { - SmallVector<const MachineMemOperand*, 1> Accesses; - + MachineFunction *MF) { // TODO: Handle multiple stores folded into one. if (!MI.hasOneMemOperand()) return false; @@ -774,6 +969,14 @@ 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; @@ -842,7 +1045,37 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); - if (isSpillInstruction(MI, MF, Reg)) { + // 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)) { TKind = TransferKind::TransferSpill; LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump();); LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) @@ -856,20 +1089,16 @@ 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 && - !DebugInstr->getDebugExpression()->isComplex()) { + VarLocIDs[ID].isDescribedByReg() == Reg) { LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '(' - << VarLocIDs[ID].Var.getVar()->getName() << ")\n"); + << VarLocIDs[ID].Var.getVariable()->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.getVar()->getName() << ")\n"); + << VarLocIDs[ID].Var.getVariable()->getName() << ")\n"); } else continue; insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind, @@ -885,28 +1114,56 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers) { - const MachineOperand *SrcRegOp, *DestRegOp; + auto DestSrc = TII->isCopyInstr(MI); + if (!DestSrc) + return; + + const MachineOperand *DestRegOp = DestSrc->Destination; + const MachineOperand *SrcRegOp = DestSrc->Source; - if (!TII->isCopyInstr(MI, SrcRegOp, DestRegOp) || !SrcRegOp->isKill() || - !DestRegOp->isDef()) + if (!DestRegOp->isDef()) return; - auto isCalleSavedReg = [&](unsigned Reg) { + auto isCalleeSavedReg = [&](unsigned Reg) { for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) if (CalleeSavedRegs.test(*RAI)) return true; return false; }; - unsigned SrcReg = SrcRegOp->getReg(); - unsigned DestReg = DestRegOp->getReg(); + Register SrcReg = SrcRegOp->getReg(); + Register 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 (!isCalleSavedReg(DestReg)) + 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()) return; for (unsigned ID : OpenRanges.getVarLocs()) { @@ -919,26 +1176,20 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, } /// Terminate all open ranges at the end of the current basic block. -bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, - OpenRangesSet &OpenRanges, - VarLocInMBB &OutLocs, - const VarLocMap &VarLocIDs) { +bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB, + 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(); + VarLocIDs[ID].dump(TRI); }); 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) @@ -960,26 +1211,27 @@ bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, OverlapMap &OverlappingFragments) { - DebugVariable MIVar(MI); - FragmentInfo ThisFragment = MIVar.getFragmentDefault(); + DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), + MI.getDebugLoc()->getInlinedAt()); + FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); // 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.getVar()); + auto SeenIt = SeenFragments.find(MIVar.getVariable()); if (SeenIt == SeenFragments.end()) { SmallSet<FragmentInfo, 4> OneFragment; OneFragment.insert(ThisFragment); - SeenFragments.insert({MIVar.getVar(), OneFragment}); + SeenFragments.insert({MIVar.getVariable(), OneFragment}); - OverlappingFragments.insert({{MIVar.getVar(), ThisFragment}, {}}); + OverlappingFragments.insert({{MIVar.getVariable(), 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.getVar(), ThisFragment}, {}}); + OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); if (!IsInOLapMap.second) return; @@ -997,7 +1249,7 @@ void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, // Mark the previously seen fragment as being overlapped by the current // one. auto ASeenFragmentsOverlaps = - OverlappingFragments.find({MIVar.getVar(), ASeenFragment}); + OverlappingFragments.find({MIVar.getVariable(), ASeenFragment}); assert(ASeenFragmentsOverlaps != OverlappingFragments.end() && "Previously seen var fragment has no vector of overlaps"); ASeenFragmentsOverlaps->second.push_back(ThisFragment); @@ -1007,27 +1259,13 @@ void LiveDebugValues::accumulateFragmentMap(MachineInstr &MI, AllSeenFragments.insert(ThisFragment); } -/// 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; +/// This routine creates OpenRanges. +void LiveDebugValues::process(MachineInstr &MI, OpenRangesSet &OpenRanges, + VarLocMap &VarLocIDs, TransferMap &Transfers) { transferDebugValue(MI, OpenRanges, VarLocIDs); - 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; + transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers); + transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers); + transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers); } /// This routine joins the analysis results of all incoming edges in @MBB by @@ -1037,7 +1275,8 @@ bool LiveDebugValues::join( MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, const VarLocMap &VarLocIDs, SmallPtrSet<const MachineBasicBlock *, 16> &Visited, - SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) { + SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks, + VarLocInMBB &PendingInLocs) { LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); bool Changed = false; @@ -1047,9 +1286,11 @@ bool LiveDebugValues::join( // can be joined. int NumVisited = 0; for (auto p : MBB.predecessors()) { - // 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. + // 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. if (!Visited.count(p)) { LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber() << "\n"); @@ -1071,7 +1312,7 @@ bool LiveDebugValues::join( if (!InLocsT.empty()) { for (auto ID : InLocsT) dbgs() << " gathered candidate incoming var: " - << VarLocIDs[ID].Var.getVar()->getName() << "\n"; + << VarLocIDs[ID].Var.getVariable()->getName() << "\n"; } }); @@ -1086,7 +1327,7 @@ bool LiveDebugValues::join( if (!VarLocIDs[ID].dominates(MBB)) { KillSet.set(ID); LLVM_DEBUG({ - auto Name = VarLocIDs[ID].Var.getVar()->getName(); + auto Name = VarLocIDs[ID].Var.getVariable()->getName(); dbgs() << " killing " << Name << ", it doesn't dominate MBB\n"; }); } @@ -1099,44 +1340,142 @@ 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]; - // Insert DBG_VALUE instructions, if not already inserted. + // 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. VarLocSet Diff = InLocsT; Diff.intersectWithComplement(ILS); for (auto ID : Diff) { - // 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();); + Pending.set(ID); 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) { @@ -1147,12 +1486,16 @@ 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 spills. + 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. VarToFragments SeenFragments; @@ -1169,62 +1512,27 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { std::greater<unsigned int>> Pending; - enum : bool { dontTransferChanges = false, transferChanges = true }; + // Set of register defines that are seen when traversing the entry block + // looking for debug entry value candidates. + DefinedRegsSet DefinedRegs; - // 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. - // 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. + 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. for (auto &MBB : MF) { + PendingInLocs[&MBB] = VarLocSet(); + for (auto &MI : MBB) { - 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); + if (MI.isDebugValue()) + accumulateFragmentMap(MI, SeenFragments, OverlapFragments); } - Transfers.clear(); } auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { @@ -1261,26 +1569,20 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { while (!Worklist.empty()) { MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; Worklist.pop(); - MBBJoined = - join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, ArtificialBlocks); - Visited.insert(MBB); + MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, + ArtificialBlocks, PendingInLocs); + MBBJoined |= Visited.insert(MBB).second; if (MBBJoined) { MBBJoined = false; Changed = true; // Now that we have started to extend ranges across BBs we need to - // examine spill instructions to see whether they spill registers that - // correspond to user variables. + // 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); for (auto &MI : *MBB) - 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(); + process(MI, OpenRanges, VarLocIDs, Transfers); + OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs); LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after propagating", dbgs())); @@ -1302,6 +1604,19 @@ 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; @@ -1320,8 +1635,7 @@ bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) { TRI = MF.getSubtarget().getRegisterInfo(); TII = MF.getSubtarget().getInstrInfo(); TFI = MF.getSubtarget().getFrameLowering(); - TFI->determineCalleeSaves(MF, CalleeSavedRegs, - make_unique<RegScavenger>().get()); + TFI->getCalleeSaves(MF, CalleeSavedRegs); LS.initialize(MF); bool Changed = ExtendRanges(MF); |