diff options
Diffstat (limited to 'llvm/lib/CodeGen/LiveDebugValues.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/LiveDebugValues.cpp | 799 |
1 files changed, 566 insertions, 233 deletions
diff --git a/llvm/lib/CodeGen/LiveDebugValues.cpp b/llvm/lib/CodeGen/LiveDebugValues.cpp index 2226c10b49a4..07a275b546f6 100644 --- a/llvm/lib/CodeGen/LiveDebugValues.cpp +++ b/llvm/lib/CodeGen/LiveDebugValues.cpp @@ -6,32 +6,107 @@ // //===----------------------------------------------------------------------===// /// -/// 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). +/// \file LiveDebugValues.cpp /// -/// This is a separate pass from DbgValueHistoryCalculator to facilitate -/// testing and improve modularity. +/// LiveDebugValues is an optimistic "available expressions" dataflow +/// algorithm. The set of expressions is the set of machine locations +/// (registers, spill slots, constants) that a variable fragment might be +/// located, qualified by a DIExpression and indirect-ness flag, while each +/// variable is identified by a DebugVariable object. The availability of an +/// expression begins when a DBG_VALUE instruction specifies the location of a +/// DebugVariable, and continues until that location is clobbered or +/// re-specified by a different DBG_VALUE for the same DebugVariable. /// -/// 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. +/// The cannonical "available expressions" problem doesn't have expression +/// clobbering, instead when a variable is re-assigned, any expressions using +/// that variable get invalidated. LiveDebugValues can map onto "available +/// expressions" by having every register represented by a variable, which is +/// used in an expression that becomes available at a DBG_VALUE instruction. +/// When the register is clobbered, its variable is effectively reassigned, and +/// expressions computed from it become unavailable. A similar construct is +/// needed when a DebugVariable has its location re-specified, to invalidate +/// all other locations for that DebugVariable. +/// +/// Using the dataflow analysis to compute the available expressions, we create +/// a DBG_VALUE at the beginning of each block where the expression is +/// live-in. This propagates variable locations into every basic block where +/// the location can be determined, rather than only having DBG_VALUEs in blocks +/// where locations are specified due to an assignment or some optimization. +/// Movements of values between registers and spill slots are annotated with +/// DBG_VALUEs too to track variable values bewteen locations. All this allows +/// DbgEntityHistoryCalculator to focus on only the locations within individual +/// blocks, facilitating testing and improving modularity. +/// +/// We follow an optimisic dataflow approach, with this lattice: +/// +/// \verbatim +/// ┬ "Unknown" +/// | +/// v +/// True +/// | +/// v +/// ⊥ False +/// \endverbatim With "True" signifying that the expression is available (and +/// thus a DebugVariable's location is the corresponding register), while +/// "False" signifies that the expression is unavailable. "Unknown"s never +/// survive to the end of the analysis (see below). +/// +/// Formally, all DebugVariable locations that are live-out of a block are +/// initialized to \top. A blocks live-in values take the meet of the lattice +/// value for every predecessors live-outs, except for the entry block, where +/// all live-ins are \bot. The usual dataflow propagation occurs: the transfer +/// function for a block assigns an expression for a DebugVariable to be "True" +/// if a DBG_VALUE in the block specifies it; "False" if the location is +/// clobbered; or the live-in value if it is unaffected by the block. We +/// visit each block in reverse post order until a fixedpoint is reached. The +/// solution produced is maximal. +/// +/// Intuitively, we start by assuming that every expression / variable location +/// is at least "True", and then propagate "False" from the entry block and any +/// clobbers until there are no more changes to make. This gives us an accurate +/// solution because all incorrect locations will have a "False" propagated into +/// them. It also gives us a solution that copes well with loops by assuming +/// that variable locations are live-through every loop, and then removing those +/// that are not through dataflow. +/// +/// Within LiveDebugValues: 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) \p 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 indicies. +/// +/// All the storage for the dataflow analysis is local to the ExtendRanges +/// method and passed down to helper methods. "OutLocs" and "InLocs" record the +/// in and out lattice values for each block. "OpenRanges" maintains a list of +/// variable locations and, with the "process" method, evaluates the transfer +/// function of each block. "flushPendingLocs" installs DBG_VALUEs for each +/// live-in location at the start of blocks, while "Transfers" records +/// transfers of values between machine-locations. +/// +/// We avoid explicitly representing the "Unknown" (\top) lattice value in the +/// implementation. Instead, unvisited blocks implicitly have all lattice +/// values set as "Unknown". After being visited, there will be path back to +/// the entry block where the lattice value is "False", and as the transfer +/// function cannot make new "Unknown" locations, there are no scenarios where +/// a block can have an "Unknown" location after being visited. Similarly, we +/// don't enumerate all possible variable locations before exploring the +/// function: when a new location is discovered, all blocks previously explored +/// were implicitly "False" but unrecorded, and become explicitly "False" when +/// a new VarLoc is created with its bit not set in predecessor InLocs or +/// OutLocs. /// //===----------------------------------------------------------------------===// +#include "llvm/ADT/CoalescingBitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/SparseBitVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/UniqueVector.h" #include "llvm/CodeGen/LexicalScopes.h" @@ -64,6 +139,7 @@ #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetMachine.h" #include <algorithm> #include <cassert> #include <cstdint> @@ -78,7 +154,18 @@ using namespace llvm; #define DEBUG_TYPE "livedebugvalues" STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); -STATISTIC(NumRemoved, "Number of DBG_VALUE instructions removed"); + +// Options to prevent pathological compile-time behavior. If InputBBLimit and +// InputDbgValueLimit are both exceeded, range extension is disabled. +static cl::opt<unsigned> InputBBLimit( + "livedebugvalues-input-bb-limit", + cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), + cl::init(10000), cl::Hidden); +static cl::opt<unsigned> InputDbgValueLimit( + "livedebugvalues-input-dbg-value-limit", + cl::desc( + "Maximum input DBG_VALUE insts supported by debug range extension"), + cl::init(50000), cl::Hidden); // 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. @@ -87,7 +174,8 @@ static Register isDbgValueDescribedByReg(const MachineInstr &MI) { assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); // If location of variable is described using a register (directly // or indirectly), this register is always a first operand. - return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : Register(); + return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg() + : Register(); } /// If \p Op is a stack or frame register return true, otherwise return false. @@ -101,7 +189,7 @@ static bool isRegOtherThanSPAndFP(const MachineOperand &Op, const MachineFunction *MF = MI.getParent()->getParent(); const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); - unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); + Register SP = TLI->getStackPointerRegisterToSaveRestore(); Register FP = TRI->getFrameRegister(*MF); Register Reg = Op.getReg(); @@ -110,8 +198,72 @@ static bool isRegOtherThanSPAndFP(const MachineOperand &Op, namespace { +// Max out the number of statically allocated elements in DefinedRegsSet, as +// this prevents fallback to std::set::count() operations. using DefinedRegsSet = SmallSet<Register, 32>; +using VarLocSet = CoalescingBitVector<uint64_t>; + +/// A type-checked pair of {Register Location (or 0), Index}, used to index +/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int +/// for insertion into a \ref VarLocSet, and efficiently converted back. The +/// type-checker helps ensure that the conversions aren't lossy. +/// +/// Why encode a location /into/ the VarLocMap index? This makes it possible +/// to find the open VarLocs killed by a register def very quickly. This is a +/// performance-critical operation for LiveDebugValues. +struct LocIndex { + using u32_location_t = uint32_t; + using u32_index_t = uint32_t; + + u32_location_t Location; // Physical registers live in the range [1;2^30) (see + // \ref MCRegister), so we have plenty of range left + // here to encode non-register locations. + u32_index_t Index; + + /// The first location greater than 0 that is not reserved for VarLocs of + /// kind RegisterKind. + static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30; + + /// A special location reserved for VarLocs of kind SpillLocKind. + static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation; + + /// A special location reserved for VarLocs of kind EntryValueBackupKind and + /// EntryValueCopyBackupKind. + static constexpr u32_location_t kEntryValueBackupLocation = + kFirstInvalidRegLocation + 1; + + LocIndex(u32_location_t Location, u32_index_t Index) + : Location(Location), Index(Index) {} + + uint64_t getAsRawInteger() const { + return (static_cast<uint64_t>(Location) << 32) | Index; + } + + template<typename IntT> static LocIndex fromRawInteger(IntT ID) { + static_assert(std::is_unsigned<IntT>::value && + sizeof(ID) == sizeof(uint64_t), + "Cannot convert raw integer to LocIndex"); + return {static_cast<u32_location_t>(ID >> 32), + static_cast<u32_index_t>(ID)}; + } + + /// Get the start of the interval reserved for VarLocs of kind RegisterKind + /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1. + static uint64_t rawIndexForReg(uint32_t Reg) { + return LocIndex(Reg, 0).getAsRawInteger(); + } + + /// Return a range covering all set indices in the interval reserved for + /// \p Location in \p Set. + static auto indexRangeForLocation(const VarLocSet &Set, + u32_location_t Location) { + uint64_t Start = LocIndex(Location, 0).getAsRawInteger(); + uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger(); + return Set.half_open_range(Start, End); + } +}; + class LiveDebugValues : public MachineFunctionPass { private: const TargetRegisterInfo *TRI; @@ -119,28 +271,10 @@ private: const TargetFrameLowering *TFI; BitVector CalleeSavedRegs; LexicalScopes LS; + VarLocSet::Allocator Alloc; enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore }; - /// Keeps track of lexical scopes associated with a user value's source - /// location. - class UserValueScopes { - DebugLoc DL; - LexicalScopes &LS; - SmallPtrSet<const MachineBasicBlock *, 4> LBlocks; - - public: - UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(std::move(D)), LS(L) {} - - /// Return true if current scope dominates at least one machine - /// instruction in a given machine basic block. - bool dominates(MachineBasicBlock *MBB) { - if (LBlocks.empty()) - LS.getMachineBasicBlocks(DL, LBlocks); - return LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB); - } - }; - using FragmentInfo = DIExpression::FragmentInfo; using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; @@ -154,6 +288,9 @@ private: bool operator==(const SpillLoc &Other) const { return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset; } + bool operator!=(const SpillLoc &Other) const { + return !(*this == Other); + } }; /// Identity of the variable at this location. @@ -166,7 +303,6 @@ private: /// is moved. const MachineInstr &MI; - mutable UserValueScopes UVS; enum VarLocKind { InvalidKind = 0, RegisterKind, @@ -191,7 +327,7 @@ private: VarLoc(const MachineInstr &MI, LexicalScopes &LS) : Var(MI.getDebugVariable(), MI.getDebugExpression(), MI.getDebugLoc()->getInlinedAt()), - Expr(MI.getDebugExpression()), MI(MI), UVS(MI.getDebugLoc(), LS) { + Expr(MI.getDebugExpression()), MI(MI) { static_assert((sizeof(Loc) == sizeof(uint64_t)), "hash does not cover all members of Loc"); assert(MI.isDebugValue() && "not a DBG_VALUE"); @@ -199,15 +335,15 @@ private: if (int RegNo = isDbgValueDescribedByReg(MI)) { Kind = RegisterKind; Loc.RegNo = RegNo; - } else if (MI.getOperand(0).isImm()) { + } else if (MI.getDebugOperand(0).isImm()) { Kind = ImmediateKind; - Loc.Immediate = MI.getOperand(0).getImm(); - } else if (MI.getOperand(0).isFPImm()) { + Loc.Immediate = MI.getDebugOperand(0).getImm(); + } else if (MI.getDebugOperand(0).isFPImm()) { Kind = ImmediateKind; - Loc.FPImm = MI.getOperand(0).getFPImm(); - } else if (MI.getOperand(0).isCImm()) { + Loc.FPImm = MI.getDebugOperand(0).getFPImm(); + } else if (MI.getDebugOperand(0).isCImm()) { Kind = ImmediateKind; - Loc.CImm = MI.getOperand(0).getCImm(); + Loc.CImm = MI.getDebugOperand(0).getCImm(); } // We create the debug entry values from the factory functions rather than @@ -218,7 +354,7 @@ private: /// 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) { + const DIExpression *EntryExpr, Register Reg) { VarLoc VL(MI, LS); assert(VL.Kind == RegisterKind); VL.Kind = EntryValueKind; @@ -247,7 +383,7 @@ private: static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI, LexicalScopes &LS, const DIExpression *EntryExpr, - unsigned NewReg) { + Register NewReg) { VarLoc VL(MI, LS); assert(VL.Kind == RegisterKind); VL.Kind = EntryValueCopyBackupKind; @@ -259,7 +395,7 @@ private: /// Copy the register location in DBG_VALUE MI, updating the register to /// be NewReg. static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS, - unsigned NewReg) { + Register NewReg) { VarLoc VL(MI, LS); assert(VL.Kind == RegisterKind); VL.Loc.RegNo = NewReg; @@ -287,6 +423,7 @@ private: const auto &IID = MI.getDesc(); const DILocalVariable *Var = MI.getDebugVariable(); const DIExpression *DIExpr = MI.getDebugExpression(); + NumInserted++; switch (Kind) { case EntryValueKind: @@ -294,8 +431,8 @@ private: // 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); + return BuildMI(MF, DbgLoc, IID, Indirect, + MI.getDebugOperand(0).getReg(), Var, Expr); case RegisterKind: // Register locations are like the source DBG_VALUE, but with the // register number from this VarLoc. @@ -311,7 +448,7 @@ private: return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr); } case ImmediateKind: { - MachineOperand MO = MI.getOperand(0); + MachineOperand MO = MI.getDebugOperand(0); return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr); } case EntryValueBackupKind: @@ -357,41 +494,42 @@ private: /// Determine whether the lexical scope of this value's debug location /// dominates MBB. - bool dominates(MachineBasicBlock &MBB) const { return UVS.dominates(&MBB); } + bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const { + return LS.dominates(MI.getDebugLoc().get(), &MBB); + } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) // TRI can be null. void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const { - dbgs() << "VarLoc("; + Out << "VarLoc("; switch (Kind) { case RegisterKind: case EntryValueKind: case EntryValueBackupKind: case EntryValueCopyBackupKind: - dbgs() << printReg(Loc.RegNo, TRI); + Out << printReg(Loc.RegNo, TRI); break; case SpillLocKind: - dbgs() << printReg(Loc.SpillLocation.SpillBase, TRI); - dbgs() << "[" << Loc.SpillLocation.SpillOffset << "]"; + Out << printReg(Loc.SpillLocation.SpillBase, TRI); + Out << "[" << Loc.SpillLocation.SpillOffset << "]"; break; case ImmediateKind: - dbgs() << Loc.Immediate; + Out << Loc.Immediate; break; case InvalidKind: llvm_unreachable("Invalid VarLoc in dump method"); } - dbgs() << ", \"" << Var.getVariable()->getName() << "\", " << *Expr - << ", "; + Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", "; if (Var.getInlinedAt()) - dbgs() << "!" << Var.getInlinedAt()->getMetadataID() << ")\n"; + Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n"; else - dbgs() << "(null))"; + Out << "(null))"; if (isEntryBackupLoc()) - dbgs() << " (backup loc)\n"; + Out << " (backup loc)\n"; else - dbgs() << "\n"; + Out << "\n"; } #endif @@ -407,12 +545,62 @@ private: } }; - using VarLocMap = UniqueVector<VarLoc>; - using VarLocSet = SparseBitVector<>; - using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>; + /// VarLocMap is used for two things: + /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to + /// virtually insert a VarLoc into a VarLocSet. + /// 2) Given a LocIndex, look up the unique associated VarLoc. + class VarLocMap { + /// Map a VarLoc to an index within the vector reserved for its location + /// within Loc2Vars. + std::map<VarLoc, LocIndex::u32_index_t> Var2Index; + + /// Map a location to a vector which holds VarLocs which live in that + /// location. + SmallDenseMap<LocIndex::u32_location_t, std::vector<VarLoc>> Loc2Vars; + + /// Determine the 32-bit location reserved for \p VL, based on its kind. + static LocIndex::u32_location_t getLocationForVar(const VarLoc &VL) { + switch (VL.Kind) { + case VarLoc::RegisterKind: + assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) && + "Physreg out of range?"); + return VL.Loc.RegNo; + case VarLoc::SpillLocKind: + return LocIndex::kSpillLocation; + case VarLoc::EntryValueBackupKind: + case VarLoc::EntryValueCopyBackupKind: + return LocIndex::kEntryValueBackupLocation; + default: + return 0; + } + } + + public: + /// Retrieve a unique LocIndex for \p VL. + LocIndex insert(const VarLoc &VL) { + LocIndex::u32_location_t Location = getLocationForVar(VL); + LocIndex::u32_index_t &Index = Var2Index[VL]; + if (!Index) { + auto &Vars = Loc2Vars[Location]; + Vars.push_back(VL); + Index = Vars.size(); + } + return {Location, Index - 1}; + } + + /// Retrieve the unique VarLoc associated with \p ID. + const VarLoc &operator[](LocIndex ID) const { + auto LocIt = Loc2Vars.find(ID.Location); + assert(LocIt != Loc2Vars.end() && "Location not tracked"); + return LocIt->second[ID.Index]; + } + }; + + using VarLocInMBB = + SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>; struct TransferDebugPair { - MachineInstr *TransferInst; /// Instruction where this transfer occurs. - unsigned LocationID; /// Location number for the transfer dest. + MachineInstr *TransferInst; ///< Instruction where this transfer occurs. + LocIndex LocationID; ///< Location number for the transfer dest. }; using TransferMap = SmallVector<TransferDebugPair, 4>; @@ -441,13 +629,14 @@ private: class OpenRangesSet { VarLocSet VarLocs; // Map the DebugVariable to recent primary location ID. - SmallDenseMap<DebugVariable, unsigned, 8> Vars; + SmallDenseMap<DebugVariable, LocIndex, 8> Vars; // Map the DebugVariable to recent backup location ID. - SmallDenseMap<DebugVariable, unsigned, 8> EntryValuesBackupVars; + SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars; OverlapMap &OverlappingFragments; public: - OpenRangesSet(OverlapMap &_OLapMap) : OverlappingFragments(_OLapMap) {} + OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap) + : VarLocs(Alloc), OverlappingFragments(_OLapMap) {} const VarLocSet &getVarLocs() const { return VarLocs; } @@ -459,17 +648,18 @@ private: void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs); /// Insert a new range into the set. - void insert(unsigned VarLocID, const VarLoc &VL); + void insert(LocIndex 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); + for (uint64_t ID : ToLoad) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + const VarLoc &VarL = Map[Idx]; + insert(Idx, VarL); } } - llvm::Optional<unsigned> getEntryValueBackup(DebugVariable Var); + llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var); /// Empty the set. void clear() { @@ -485,8 +675,57 @@ private: "open ranges are inconsistent"); return VarLocs.empty(); } + + /// Get an empty range of VarLoc IDs. + auto getEmptyVarLocRange() const { + return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(), + getVarLocs().end()); + } + + /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg. + auto getRegisterVarLocs(Register Reg) const { + return LocIndex::indexRangeForLocation(getVarLocs(), Reg); + } + + /// Get all set IDs for VarLocs of kind SpillLocKind. + auto getSpillVarLocs() const { + return LocIndex::indexRangeForLocation(getVarLocs(), + LocIndex::kSpillLocation); + } + + /// Get all set IDs for VarLocs of kind EntryValueBackupKind or + /// EntryValueCopyBackupKind. + auto getEntryValueBackupVarLocs() const { + return LocIndex::indexRangeForLocation( + getVarLocs(), LocIndex::kEntryValueBackupLocation); + } }; + /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind + /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs + /// into \p Collected. + void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs, + const VarLocSet &CollectFrom) const; + + /// Get the registers which are used by VarLocs of kind RegisterKind tracked + /// by \p CollectFrom. + void getUsedRegs(const VarLocSet &CollectFrom, + SmallVectorImpl<uint32_t> &UsedRegs) const; + + VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) { + std::unique_ptr<VarLocSet> &VLS = Locs[MBB]; + if (!VLS) + VLS = std::make_unique<VarLocSet>(Alloc); + return *VLS.get(); + } + + const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, + const VarLocInMBB &Locs) const { + auto It = Locs.find(MBB); + assert(It != Locs.end() && "MBB not in map"); + return *It->second.get(); + } + /// Tests whether this instruction is a spill to a stack location. bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); @@ -497,7 +736,7 @@ private: /// 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); + Register &Reg); /// Returns true if the given machine instruction is a debug value which we /// can emit entry values for. @@ -511,14 +750,14 @@ private: /// and set \p Reg to the spilled register. Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI, MachineFunction *MF, - unsigned &Reg); + Register &Reg); /// Given a spill instruction, extract the register and offset used to /// address the spill location in a target independent way. VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers, VarLocMap &VarLocIDs, - unsigned OldVarID, TransferKind Kind, - unsigned NewReg = 0); + LocIndex OldVarID, TransferKind Kind, + Register NewReg = Register()); void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs); @@ -528,7 +767,7 @@ private: VarLocMap &VarLocIDs, const VarLoc &EntryVL); void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers, - SparseBitVector<> &KillSet); + VarLocSet &KillSet); void recordEntryValue(const MachineInstr &MI, const DefinedRegsSet &DefinedRegs, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs); @@ -548,8 +787,7 @@ private: bool 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); /// Create DBG_VALUE insts for inlocs that have been propagated but /// had their instruction creation deferred. @@ -617,8 +855,8 @@ void LiveDebugValues::OpenRangesSet::erase(const VarLoc &VL) { auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; auto It = EraseFrom->find(VarToErase); if (It != EraseFrom->end()) { - unsigned ID = It->second; - VarLocs.reset(ID); + LocIndex ID = It->second; + VarLocs.reset(ID.getAsRawInteger()); EraseFrom->erase(It); } }; @@ -648,23 +886,23 @@ void LiveDebugValues::OpenRangesSet::erase(const VarLoc &VL) { void LiveDebugValues::OpenRangesSet::erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs) { VarLocs.intersectWithComplement(KillSet); - for (unsigned ID : KillSet) { - const VarLoc *VL = &VarLocIDs[ID]; + for (uint64_t ID : KillSet) { + const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)]; auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; EraseFrom->erase(VL->Var); } } -void LiveDebugValues::OpenRangesSet::insert(unsigned VarLocID, +void LiveDebugValues::OpenRangesSet::insert(LocIndex VarLocID, const VarLoc &VL) { auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; - VarLocs.set(VarLocID); + VarLocs.set(VarLocID.getAsRawInteger()); InsertInto->insert({VL.Var, VarLocID}); } /// Return the Loc ID of an entry value backup location, if it exists for the /// variable. -llvm::Optional<unsigned> +llvm::Optional<LocIndex> LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { auto It = EntryValuesBackupVars.find(Var); if (It != EntryValuesBackupVars.end()) @@ -673,6 +911,57 @@ LiveDebugValues::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { return llvm::None; } +void LiveDebugValues::collectIDsForRegs(VarLocSet &Collected, + const DefinedRegsSet &Regs, + const VarLocSet &CollectFrom) const { + assert(!Regs.empty() && "Nothing to collect"); + SmallVector<uint32_t, 32> SortedRegs; + for (Register Reg : Regs) + SortedRegs.push_back(Reg); + array_pod_sort(SortedRegs.begin(), SortedRegs.end()); + auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front())); + auto End = CollectFrom.end(); + for (uint32_t Reg : SortedRegs) { + // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all + // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg. + uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg); + uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1); + It.advanceToLowerBound(FirstIndexForReg); + + // Iterate through that half-open interval and collect all the set IDs. + for (; It != End && *It < FirstInvalidIndex; ++It) + Collected.set(*It); + + if (It == End) + return; + } +} + +void LiveDebugValues::getUsedRegs(const VarLocSet &CollectFrom, + SmallVectorImpl<uint32_t> &UsedRegs) const { + // All register-based VarLocs are assigned indices greater than or equal to + // FirstRegIndex. + uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1); + uint64_t FirstInvalidIndex = + LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation); + for (auto It = CollectFrom.find(FirstRegIndex), + End = CollectFrom.find(FirstInvalidIndex); + It != End;) { + // We found a VarLoc ID for a VarLoc that lives in a register. Figure out + // which register and add it to UsedRegs. + uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location; + assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) && + "Duplicate used reg"); + UsedRegs.push_back(FoundReg); + + // Skip to the next /set/ register. Note that this finds a lower bound, so + // even if there aren't any VarLocs living in `FoundReg+1`, we're still + // guaranteed to move on to the next register (or to end()). + uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1); + It.advanceToLowerBound(NextRegIndex); + } +} + //===----------------------------------------------------------------------===// // Debug Range Extension Implementation //===----------------------------------------------------------------------===// @@ -685,12 +974,14 @@ void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF, raw_ostream &Out) const { Out << '\n' << msg << '\n'; for (const MachineBasicBlock &BB : MF) { - const VarLocSet &L = V.lookup(&BB); + if (!V.count(&BB)) + continue; + const VarLocSet &L = getVarLocsInMBB(&BB, V); if (L.empty()) continue; Out << "MBB: " << BB.getNumber() << ":\n"; - for (unsigned VLL : L) { - const VarLoc &VL = VarLocIDs[VLL]; + for (uint64_t VLL : L) { + const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)]; Out << " Var: " << VL.Var.getVariable()->getName(); Out << " MI: "; VL.dump(TRI, Out); @@ -710,7 +1001,7 @@ LiveDebugValues::extractSpillBaseRegAndOffset(const MachineInstr &MI) { "Inconsistent memory operand in spill instruction"); int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); const MachineBasicBlock *MBB = MI.getParent(); - unsigned Reg; + Register Reg; int Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); return {Reg, Offset}; } @@ -730,7 +1021,7 @@ bool LiveDebugValues::removeEntryValue(const MachineInstr &MI, // 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() || + if (!MI.getDebugOperand(0).isReg() || MI.getDebugExpression()->getNumElements() != 0) return true; @@ -738,7 +1029,7 @@ bool LiveDebugValues::removeEntryValue(const MachineInstr &MI, // 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(); + Register Reg = MI.getDebugOperand(0).getReg(); auto I = std::next(MI.getReverseIterator()); const MachineOperand *SrcRegOp, *DestRegOp; if (I != MI.getParent()->rend()) { @@ -757,13 +1048,10 @@ bool LiveDebugValues::removeEntryValue(const MachineInstr &MI, } if (TrySalvageEntryValue) { - for (unsigned ID : OpenRanges.getVarLocs()) { - const VarLoc &VL = VarLocIDs[ID]; - if (!VL.isEntryBackupLoc()) - continue; - + for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { + const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)]; if (VL.getEntryValueCopyBackupReg() == Reg && - VL.MI.getOperand(0).getReg() == SrcRegOp->getReg()) + VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg()) return false; } } @@ -801,23 +1089,25 @@ void LiveDebugValues::transferDebugValue(const MachineInstr &MI, } } - unsigned ID; - if (isDbgValueDescribedByReg(MI) || MI.getOperand(0).isImm() || - MI.getOperand(0).isFPImm() || MI.getOperand(0).isCImm()) { + if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() || + MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(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); + LocIndex ID = VarLocIDs.insert(VL); // Add the VarLoc to OpenRanges from this DBG_VALUE. OpenRanges.insert(ID, VL); } else if (MI.hasOneMemOperand()) { 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 && + // This must be an undefined location. If it has an open range, erase it. + assert(MI.getDebugOperand(0).isReg() && + MI.getDebugOperand(0).getReg() == 0 && "Unexpected non-undef DBG_VALUE encountered"); + VarLoc VL(MI, LS); + OpenRanges.erase(VL); } } @@ -826,13 +1116,20 @@ void LiveDebugValues::emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers, - SparseBitVector<> &KillSet) { - for (unsigned ID : KillSet) { - if (!VarLocIDs[ID].Var.getVariable()->isParameter()) + VarLocSet &KillSet) { + // Do not insert entry value locations after a terminator. + if (MI.isTerminator()) + return; + + for (uint64_t ID : KillSet) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + const VarLoc &VL = VarLocIDs[Idx]; + if (!VL.Var.getVariable()->isParameter()) continue; - auto DebugVar = VarLocIDs[ID].Var; - auto EntryValBackupID = OpenRanges.getEntryValueBackup(DebugVar); + auto DebugVar = VL.Var; + Optional<LocIndex> EntryValBackupID = + OpenRanges.getEntryValueBackup(DebugVar); // If the parameter has the entry value backup, it means we should // be able to use its entry value. @@ -842,7 +1139,7 @@ void LiveDebugValues::emitEntryValues(MachineInstr &MI, const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; VarLoc EntryLoc = VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo); - unsigned EntryValueID = VarLocIDs.insert(EntryLoc); + LocIndex EntryValueID = VarLocIDs.insert(EntryLoc); Transfers.push_back({&MI, EntryValueID}); OpenRanges.insert(EntryValueID, EntryLoc); } @@ -855,12 +1152,12 @@ void LiveDebugValues::emitEntryValues(MachineInstr &MI, /// otherwise it is variable's location on the stack. void LiveDebugValues::insertTransferDebugPair( MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers, - VarLocMap &VarLocIDs, unsigned OldVarID, TransferKind Kind, - unsigned NewReg) { + VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind, + Register NewReg) { const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI; auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) { - unsigned LocId = VarLocIDs.insert(VL); + LocIndex LocId = VarLocIDs.insert(VL); // Close this variable's previous location range. OpenRanges.erase(VL); @@ -868,6 +1165,7 @@ void LiveDebugValues::insertTransferDebugPair( // Record the new location as an open range, and a postponed transfer // inserting a DBG_VALUE for this location. OpenRanges.insert(LocId, VL); + assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator"); TransferDebugPair MIP = {&MI, LocId}; Transfers.push_back(MIP); }; @@ -922,39 +1220,67 @@ void LiveDebugValues::insertTransferDebugPair( void LiveDebugValues::transferRegisterDef( MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers) { + + // Meta Instructions do not affect the debug liveness of any register they + // define. + if (MI.isMetaInstruction()) + return; + MachineFunction *MF = MI.getMF(); const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); - unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); - SparseBitVector<> KillSet; + Register SP = TLI->getStackPointerRegisterToSaveRestore(); + + // Find the regs killed by MI, and find regmasks of preserved regs. + DefinedRegsSet DeadRegs; + SmallVector<const uint32_t *, 4> RegMasks; for (const MachineOperand &MO : MI.operands()) { - // Determine whether the operand is a register def. Assume that call - // instructions never clobber SP, because some backends (e.g., AArch64) - // never list SP in the regmask. + // Determine whether the operand is a register def. if (MO.isReg() && MO.isDef() && 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) - for (unsigned ID : OpenRanges.getVarLocs()) - if (VarLocIDs[ID].isDescribedByReg() == *RAI) - KillSet.set(ID); + // FIXME: Can we break out of this loop early if no insertion occurs? + DeadRegs.insert(*RAI); } else if (MO.isRegMask()) { + RegMasks.push_back(MO.getRegMask()); + } + } + + // Erase VarLocs which reside in one of the dead registers. For performance + // reasons, it's critical to not iterate over the full set of open VarLocs. + // Iterate over the set of dying/used regs instead. + if (!RegMasks.empty()) { + SmallVector<uint32_t, 32> UsedRegs; + getUsedRegs(OpenRanges.getVarLocs(), UsedRegs); + for (uint32_t Reg : UsedRegs) { // Remove ranges of all clobbered registers. Register masks don't usually - // list SP as preserved. While the debug info may be off for an - // instruction or two around callee-cleanup calls, transferring the - // DEBUG_VALUE across the call is still a better user experience. - for (unsigned ID : OpenRanges.getVarLocs()) { - unsigned Reg = VarLocIDs[ID].isDescribedByReg(); - if (Reg && Reg != SP && MO.clobbersPhysReg(Reg)) - KillSet.set(ID); - } + // list SP as preserved. Assume that call instructions never clobber SP, + // because some backends (e.g., AArch64) never list SP in the regmask. + // While the debug info may be off for an instruction or two around + // callee-cleanup calls, transferring the DEBUG_VALUE across the call is + // still a better user experience. + if (Reg == SP) + continue; + bool AnyRegMaskKillsReg = + any_of(RegMasks, [Reg](const uint32_t *RegMask) { + return MachineOperand::clobbersPhysReg(RegMask, Reg); + }); + if (AnyRegMaskKillsReg) + DeadRegs.insert(Reg); } } + + if (DeadRegs.empty()) + return; + + VarLocSet KillSet(Alloc); + collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs()); OpenRanges.erase(KillSet, VarLocIDs); if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) { auto &TM = TPC->getTM<TargetMachine>(); - if (TM.Options.EnableDebugEntryValues) + if (TM.Options.ShouldEmitDebugEntryValues()) emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet); } } @@ -973,11 +1299,11 @@ bool LiveDebugValues::isSpillInstruction(const MachineInstr &MI, } bool LiveDebugValues::isLocationSpill(const MachineInstr &MI, - MachineFunction *MF, unsigned &Reg) { + MachineFunction *MF, Register &Reg) { if (!isSpillInstruction(MI, MF)) return false; - auto isKilledReg = [&](const MachineOperand MO, unsigned &Reg) { + auto isKilledReg = [&](const MachineOperand MO, Register &Reg) { if (!MO.isReg() || !MO.isUse()) { Reg = 0; return false; @@ -999,7 +1325,7 @@ bool LiveDebugValues::isLocationSpill(const MachineInstr &MI, // Skip next instruction that points to basic block end iterator. if (MI.getParent()->end() == NextI) continue; - unsigned RegNext; + Register RegNext; for (const MachineOperand &MONext : NextI->operands()) { // Return true if we came across the register from the // previous spill instruction that is killed in NextI. @@ -1014,7 +1340,7 @@ bool LiveDebugValues::isLocationSpill(const MachineInstr &MI, Optional<LiveDebugValues::VarLoc::SpillLoc> LiveDebugValues::isRestoreInstruction(const MachineInstr &MI, - MachineFunction *MF, unsigned &Reg) { + MachineFunction *MF, Register &Reg) { if (!MI.hasOneMemOperand()) return None; @@ -1040,7 +1366,7 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, TransferMap &Transfers) { MachineFunction *MF = MI.getMF(); TransferKind TKind; - unsigned Reg; + Register Reg; Optional<VarLoc::SpillLoc> Loc; LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); @@ -1048,12 +1374,14 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, // 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; + VarLocSet KillSet(Alloc); 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) { + for (uint64_t ID : OpenRanges.getSpillVarLocs()) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + const VarLoc &VL = VarLocIDs[Idx]; + assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); + if (VL.Loc.SpillLocation == *Loc) { // This location is overwritten by the current instruction -- terminate // the open range, and insert an explicit DBG_VALUE $noreg. // @@ -1066,7 +1394,7 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, // 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); + LocIndex UndefLocID = VarLocIDs.insert(UndefVL); Transfers.push_back({&MI, UndefLocID}); } } @@ -1089,20 +1417,31 @@ void LiveDebugValues::transferSpillOrRestoreInst(MachineInstr &MI, << "\n"); } // Check if the register or spill location is the location of a debug value. - for (unsigned ID : OpenRanges.getVarLocs()) { - if (TKind == TransferKind::TransferSpill && - VarLocIDs[ID].isDescribedByReg() == Reg) { + auto TransferCandidates = OpenRanges.getEmptyVarLocRange(); + if (TKind == TransferKind::TransferSpill) + TransferCandidates = OpenRanges.getRegisterVarLocs(Reg); + else if (TKind == TransferKind::TransferRestore) + TransferCandidates = OpenRanges.getSpillVarLocs(); + for (uint64_t ID : TransferCandidates) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + const VarLoc &VL = VarLocIDs[Idx]; + if (TKind == TransferKind::TransferSpill) { + assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?"); LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '(' - << VarLocIDs[ID].Var.getVariable()->getName() << ")\n"); - } else if (TKind == TransferKind::TransferRestore && - VarLocIDs[ID].Kind == VarLoc::SpillLocKind && - VarLocIDs[ID].Loc.SpillLocation == *Loc) { + << VL.Var.getVariable()->getName() << ")\n"); + } else { + assert(TKind == TransferKind::TransferRestore && + VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); + if (VL.Loc.SpillLocation != *Loc) + // The spill location is not the location of a debug value. + continue; LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '(' - << VarLocIDs[ID].Var.getVariable()->getName() << ")\n"); - } else - continue; - insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, TKind, + << VL.Var.getVariable()->getName() << ")\n"); + } + insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind, Reg); + // FIXME: A comment should explain why it's correct to return early here, + // if that is in fact correct. return; } } @@ -1124,7 +1463,7 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, if (!DestRegOp->isDef()) return; - auto isCalleeSavedReg = [&](unsigned Reg) { + auto isCalleeSavedReg = [&](Register Reg) { for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) if (CalleeSavedRegs.test(*RAI)) return true; @@ -1146,17 +1485,19 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, // 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) { + for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + const VarLoc &VL = VarLocIDs[Idx]; + if (VL.getEntryValueBackupReg() == SrcReg) { LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump();); - VarLoc EntryValLocCopyBackup = VarLoc::CreateEntryCopyBackupLoc( - VarLocIDs[ID].MI, LS, VarLocIDs[ID].Expr, DestReg); + VarLoc EntryValLocCopyBackup = + VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg); // Stop tracking the original entry value. - OpenRanges.erase(VarLocIDs[ID]); + OpenRanges.erase(VL); // Start tracking the entry value copy. - unsigned EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup); + LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup); OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup); break; } @@ -1166,12 +1507,14 @@ void LiveDebugValues::transferRegisterCopy(MachineInstr &MI, if (!SrcRegOp->isKill()) return; - for (unsigned ID : OpenRanges.getVarLocs()) { - if (VarLocIDs[ID].isDescribedByReg() == SrcReg) { - insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, ID, - TransferKind::TransferCopy, DestReg); - return; - } + for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?"); + insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, + TransferKind::TransferCopy, DestReg); + // FIXME: A comment should explain why it's correct to return early here, + // if that is in fact correct. + return; } } @@ -1182,13 +1525,13 @@ bool LiveDebugValues::transferTerminator(MachineBasicBlock *CurMBB, const VarLocMap &VarLocIDs) { bool Changed = false; - LLVM_DEBUG(for (unsigned ID + LLVM_DEBUG(for (uint64_t ID : OpenRanges.getVarLocs()) { // Copy OpenRanges to OutLocs, if not already present. dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": "; - VarLocIDs[ID].dump(TRI); + VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI); }); - VarLocSet &VLS = OutLocs[CurMBB]; + VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs); Changed = VLS != OpenRanges.getVarLocs(); // New OutLocs set may be different due to spill, restore or register // copy instruction processing. @@ -1275,12 +1618,10 @@ 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; - VarLocSet InLocsT; // Temporary incoming locations. + VarLocSet InLocsT(Alloc); // Temporary incoming locations. // For all predecessors of this MBB, find the set of VarLocs that // can be joined. @@ -1303,16 +1644,20 @@ bool LiveDebugValues::join( // Just copy over the Out locs to incoming locs for the first visited // predecessor, and for all other predecessors join the Out locs. + VarLocSet &OutLocVLS = *OL->second.get(); if (!NumVisited) - InLocsT = OL->second; + InLocsT = OutLocVLS; else - InLocsT &= OL->second; + InLocsT &= OutLocVLS; LLVM_DEBUG({ if (!InLocsT.empty()) { - for (auto ID : InLocsT) + for (uint64_t ID : InLocsT) dbgs() << " gathered candidate incoming var: " - << VarLocIDs[ID].Var.getVariable()->getName() << "\n"; + << VarLocIDs[LocIndex::fromRawInteger(ID)] + .Var.getVariable() + ->getName() + << "\n"; } }); @@ -1320,14 +1665,15 @@ bool LiveDebugValues::join( } // Filter out DBG_VALUES that are out of scope. - VarLocSet KillSet; + VarLocSet KillSet(Alloc); bool IsArtificial = ArtificialBlocks.count(&MBB); if (!IsArtificial) { - for (auto ID : InLocsT) { - if (!VarLocIDs[ID].dominates(MBB)) { + for (uint64_t ID : InLocsT) { + LocIndex Idx = LocIndex::fromRawInteger(ID); + if (!VarLocIDs[Idx].dominates(LS, MBB)) { KillSet.set(ID); LLVM_DEBUG({ - auto Name = VarLocIDs[ID].Var.getVariable()->getName(); + auto Name = VarLocIDs[Idx].Var.getVariable()->getName(); dbgs() << " killing " << Name << ", it doesn't dominate MBB\n"; }); } @@ -1341,30 +1687,10 @@ bool LiveDebugValues::join( assert((NumVisited || MBB.pred_empty()) && "Should have processed at least one predecessor"); - 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. - VarLocSet Diff = InLocsT; - Diff.intersectWithComplement(ILS); - for (auto ID : Diff) { - 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; + VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs); + bool Changed = false; + if (ILS != InLocsT) { + ILS = InLocsT; Changed = true; } @@ -1378,12 +1704,12 @@ void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs, 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; + VarLocSet &Pending = *Iter.second.get(); - for (unsigned ID : Pending) { + for (uint64_t 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]; + const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)]; if (DiffIt.isEntryBackupLoc()) continue; MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent()); @@ -1411,25 +1737,21 @@ bool LiveDebugValues::isEntryValueCandidate( 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)) + if (!isRegOtherThanSPAndFP(MI.getDebugOperand(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())) + if (DefinedRegs.count(MI.getDebugOperand(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). + // (e.g. fragments). if (MI.getDebugExpression()->getNumElements() > 0) return false; @@ -1454,7 +1776,7 @@ void LiveDebugValues::recordEntryValue(const MachineInstr &MI, VarLocMap &VarLocIDs) { if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) { auto &TM = TPC->getTM<TargetMachine>(); - if (!TM.Options.EnableDebugEntryValues) + if (!TM.Options.ShouldEmitDebugEntryValues()) return; } @@ -1472,7 +1794,7 @@ void LiveDebugValues::recordEntryValue(const MachineInstr &MI, DIExpression *NewExpr = DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue); VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr); - unsigned EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup); + LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup); OpenRanges.insert(EntryValLocID, EntryValLocAsBackup); } @@ -1487,15 +1809,12 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors. OverlapMap OverlapFragments; // Map of overlapping variable fragments. - OpenRangesSet OpenRanges(OverlapFragments); + OpenRangesSet OpenRanges(Alloc, 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. VarToFragments SeenFragments; @@ -1526,14 +1845,10 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { } // Initialize per-block structures and scan for fragment overlaps. - for (auto &MBB : MF) { - PendingInLocs[&MBB] = VarLocSet(); - - for (auto &MI : MBB) { + for (auto &MBB : MF) + for (auto &MI : MBB) if (MI.isDebugValue()) accumulateFragmentMap(MI, SeenFragments, OverlapFragments); - } - } auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { if (const DebugLoc &DL = MI.getDebugLoc()) @@ -1555,6 +1870,22 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { Worklist.push(RPONumber); ++RPONumber; } + + if (RPONumber > InputBBLimit) { + unsigned NumInputDbgValues = 0; + for (auto &MBB : MF) + for (auto &MI : MBB) + if (MI.isDebugValue()) + ++NumInputDbgValues; + if (NumInputDbgValues > InputDbgValueLimit) { + LLVM_DEBUG(dbgs() << "Disabling LiveDebugValues: " << MF.getName() + << " has " << RPONumber << " basic blocks and " + << NumInputDbgValues + << " input DBG_VALUEs, exceeding limits.\n"); + return false; + } + } + // This is a standard "union of predecessor outs" dataflow problem. // To solve it, we perform join() and process() using the two worklist method // until the ranges converge. @@ -1570,7 +1901,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; Worklist.pop(); MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, - ArtificialBlocks, PendingInLocs); + ArtificialBlocks); MBBJoined |= Visited.insert(MBB).second; if (MBBJoined) { MBBJoined = false; @@ -1579,7 +1910,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { // 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); + OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs); for (auto &MI : *MBB) process(MI, OpenRanges, VarLocIDs, Transfers); OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs); @@ -1606,6 +1937,8 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { // Add any DBG_VALUE instructions created by location transfers. for (auto &TR : Transfers) { + assert(!TR.TransferInst->isTerminator() && + "Cannot insert DBG_VALUE after terminator"); MachineBasicBlock *MBB = TR.TransferInst->getParent(); const VarLoc &VL = VarLocIDs[TR.LocationID]; MachineInstr *MI = VL.BuildDbgValue(MF); @@ -1615,7 +1948,7 @@ bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { // Deferred inlocs will not have had any DBG_VALUE insts created; do // that now. - flushPendingLocs(PendingInLocs, VarLocIDs); + flushPendingLocs(InLocs, VarLocIDs); LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); |