diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h @@ -0,0 +1,838 @@ +//===- InstrRefBasedImpl.h - Tracking Debug Value MIs ---------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H +#define LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/UniqueVector.h" +#include "llvm/CodeGen/LexicalScopes.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/TargetFrameLowering.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetPassConfig.h" +#include "llvm/IR/DebugInfoMetadata.h" + +#include "LiveDebugValues.h" + +class VLocTracker; +class TransferTracker; + +// Forward dec of unit test class, so that we can peer into the LDV object. +class InstrRefLDVTest; + +namespace LiveDebugValues { + +class MLocTracker; + +using namespace llvm; + +/// Handle-class for a particular "location". This value-type uniquely +/// symbolises a register or stack location, allowing manipulation of locations +/// without concern for where that location is. Practically, this allows us to +/// treat the state of the machine at a particular point as an array of values, +/// rather than a map of values. +class LocIdx { + unsigned Location; + + // Default constructor is private, initializing to an illegal location number. + // Use only for "not an entry" elements in IndexedMaps. + LocIdx() : Location(UINT_MAX) {} + +public: +#define NUM_LOC_BITS 24 + LocIdx(unsigned L) : Location(L) { + assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits"); + } + + static LocIdx MakeIllegalLoc() { return LocIdx(); } + + bool isIllegal() const { return Location == UINT_MAX; } + + uint64_t asU64() const { return Location; } + + bool operator==(unsigned L) const { return Location == L; } + + bool operator==(const LocIdx &L) const { return Location == L.Location; } + + bool operator!=(unsigned L) const { return !(*this == L); } + + bool operator!=(const LocIdx &L) const { return !(*this == L); } + + bool operator<(const LocIdx &Other) const { + return Location < Other.Location; + } +}; + +// The location at which a spilled value resides. It consists of a register and +// an offset. +struct SpillLoc { + unsigned SpillBase; + StackOffset SpillOffset; + bool operator==(const SpillLoc &Other) const { + return std::make_pair(SpillBase, SpillOffset) == + std::make_pair(Other.SpillBase, Other.SpillOffset); + } + bool operator<(const SpillLoc &Other) const { + return std::make_tuple(SpillBase, SpillOffset.getFixed(), + SpillOffset.getScalable()) < + std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(), + Other.SpillOffset.getScalable()); + } +}; + +/// Unique identifier for a value defined by an instruction, as a value type. +/// Casts back and forth to a uint64_t. Probably replacable with something less +/// bit-constrained. Each value identifies the instruction and machine location +/// where the value is defined, although there may be no corresponding machine +/// operand for it (ex: regmasks clobbering values). The instructions are +/// one-based, and definitions that are PHIs have instruction number zero. +/// +/// The obvious limits of a 1M block function or 1M instruction blocks are +/// problematic; but by that point we should probably have bailed out of +/// trying to analyse the function. +class ValueIDNum { + uint64_t BlockNo : 20; /// The block where the def happens. + uint64_t InstNo : 20; /// The Instruction where the def happens. + /// One based, is distance from start of block. + uint64_t LocNo : NUM_LOC_BITS; /// The machine location where the def happens. + +public: + // Default-initialize to EmptyValue. This is necessary to make IndexedMaps + // of values to work. + ValueIDNum() : BlockNo(0xFFFFF), InstNo(0xFFFFF), LocNo(0xFFFFFF) {} + + ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) + : BlockNo(Block), InstNo(Inst), LocNo(Loc) {} + + ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) + : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) {} + + uint64_t getBlock() const { return BlockNo; } + uint64_t getInst() const { return InstNo; } + uint64_t getLoc() const { return LocNo; } + bool isPHI() const { return InstNo == 0; } + + uint64_t asU64() const { + uint64_t TmpBlock = BlockNo; + uint64_t TmpInst = InstNo; + return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo; + } + + static ValueIDNum fromU64(uint64_t v) { + uint64_t L = (v & 0x3FFF); + return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L}; + } + + bool operator<(const ValueIDNum &Other) const { + return asU64() < Other.asU64(); + } + + bool operator==(const ValueIDNum &Other) const { + return std::tie(BlockNo, InstNo, LocNo) == + std::tie(Other.BlockNo, Other.InstNo, Other.LocNo); + } + + bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); } + + std::string asString(const std::string &mlocname) const { + return Twine("Value{bb: ") + .concat(Twine(BlockNo).concat( + Twine(", inst: ") + .concat((InstNo ? Twine(InstNo) : Twine("live-in")) + .concat(Twine(", loc: ").concat(Twine(mlocname))) + .concat(Twine("}"))))) + .str(); + } + + static ValueIDNum EmptyValue; +}; + +/// Meta qualifiers for a value. Pair of whatever expression is used to qualify +/// the the value, and Boolean of whether or not it's indirect. +class DbgValueProperties { +public: + DbgValueProperties(const DIExpression *DIExpr, bool Indirect) + : DIExpr(DIExpr), Indirect(Indirect) {} + + /// Extract properties from an existing DBG_VALUE instruction. + DbgValueProperties(const MachineInstr &MI) { + assert(MI.isDebugValue()); + DIExpr = MI.getDebugExpression(); + Indirect = MI.getOperand(1).isImm(); + } + + bool operator==(const DbgValueProperties &Other) const { + return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect); + } + + bool operator!=(const DbgValueProperties &Other) const { + return !(*this == Other); + } + + const DIExpression *DIExpr; + bool Indirect; +}; + +/// Class recording the (high level) _value_ of a variable. Identifies either +/// the value of the variable as a ValueIDNum, or a constant MachineOperand. +/// This class also stores meta-information about how the value is qualified. +/// Used to reason about variable values when performing the second +/// (DebugVariable specific) dataflow analysis. +class DbgValue { +public: + union { + /// If Kind is Def, the value number that this value is based on. + ValueIDNum ID; + /// If Kind is Const, the MachineOperand defining this value. + MachineOperand MO; + /// For a NoVal DbgValue, which block it was generated in. + unsigned BlockNo; + }; + /// Qualifiers for the ValueIDNum above. + DbgValueProperties Properties; + + typedef enum { + Undef, // Represents a DBG_VALUE $noreg in the transfer function only. + Def, // This value is defined by an inst, or is a PHI value. + Const, // A constant value contained in the MachineOperand field. + Proposed, // This is a tentative PHI value, which may be confirmed or + // invalidated later. + NoVal // Empty DbgValue, generated during dataflow. BlockNo stores + // which block this was generated in. + } KindT; + /// Discriminator for whether this is a constant or an in-program value. + KindT Kind; + + DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind) + : ID(Val), Properties(Prop), Kind(Kind) { + assert(Kind == Def || Kind == Proposed); + } + + DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind) + : BlockNo(BlockNo), Properties(Prop), Kind(Kind) { + assert(Kind == NoVal); + } + + DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind) + : MO(MO), Properties(Prop), Kind(Kind) { + assert(Kind == Const); + } + + DbgValue(const DbgValueProperties &Prop, KindT Kind) + : Properties(Prop), Kind(Kind) { + assert(Kind == Undef && + "Empty DbgValue constructor must pass in Undef kind"); + } + + void dump(const MLocTracker *MTrack) const; + + bool operator==(const DbgValue &Other) const { + if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties)) + return false; + else if (Kind == Proposed && ID != Other.ID) + return false; + else if (Kind == Def && ID != Other.ID) + return false; + else if (Kind == NoVal && BlockNo != Other.BlockNo) + return false; + else if (Kind == Const) + return MO.isIdenticalTo(Other.MO); + + return true; + } + + bool operator!=(const DbgValue &Other) const { return !(*this == Other); } +}; + +class LocIdxToIndexFunctor { +public: + using argument_type = LocIdx; + unsigned operator()(const LocIdx &L) const { return L.asU64(); } +}; + +/// Tracker for what values are in machine locations. Listens to the Things +/// being Done by various instructions, and maintains a table of what machine +/// locations have what values (as defined by a ValueIDNum). +/// +/// There are potentially a much larger number of machine locations on the +/// target machine than the actual working-set size of the function. On x86 for +/// example, we're extremely unlikely to want to track values through control +/// or debug registers. To avoid doing so, MLocTracker has several layers of +/// indirection going on, with two kinds of ``location'': +/// * A LocID uniquely identifies a register or spill location, with a +/// predictable value. +/// * A LocIdx is a key (in the database sense) for a LocID and a ValueIDNum. +/// Whenever a location is def'd or used by a MachineInstr, we automagically +/// create a new LocIdx for a location, but not otherwise. This ensures we only +/// account for locations that are actually used or defined. The cost is another +/// vector lookup (of LocID -> LocIdx) over any other implementation. This is +/// fairly cheap, and the compiler tries to reduce the working-set at any one +/// time in the function anyway. +/// +/// Register mask operands completely blow this out of the water; I've just +/// piled hacks on top of hacks to get around that. +class MLocTracker { +public: + MachineFunction &MF; + const TargetInstrInfo &TII; + const TargetRegisterInfo &TRI; + const TargetLowering &TLI; + + /// IndexedMap type, mapping from LocIdx to ValueIDNum. + using LocToValueType = IndexedMap; + + /// Map of LocIdxes to the ValueIDNums that they store. This is tightly + /// packed, entries only exist for locations that are being tracked. + LocToValueType LocIdxToIDNum; + + /// "Map" of machine location IDs (i.e., raw register or spill number) to the + /// LocIdx key / number for that location. There are always at least as many + /// as the number of registers on the target -- if the value in the register + /// is not being tracked, then the LocIdx value will be zero. New entries are + /// appended if a new spill slot begins being tracked. + /// This, and the corresponding reverse map persist for the analysis of the + /// whole function, and is necessarying for decoding various vectors of + /// values. + std::vector LocIDToLocIdx; + + /// Inverse map of LocIDToLocIdx. + IndexedMap LocIdxToLocID; + + /// Unique-ification of spill slots. Used to number them -- their LocID + /// number is the index in SpillLocs minus one plus NumRegs. + UniqueVector SpillLocs; + + // If we discover a new machine location, assign it an mphi with this + // block number. + unsigned CurBB; + + /// Cached local copy of the number of registers the target has. + unsigned NumRegs; + + /// Collection of register mask operands that have been observed. Second part + /// of pair indicates the instruction that they happened in. Used to + /// reconstruct where defs happened if we start tracking a location later + /// on. + SmallVector, 32> Masks; + + /// Iterator for locations and the values they contain. Dereferencing + /// produces a struct/pair containing the LocIdx key for this location, + /// and a reference to the value currently stored. Simplifies the process + /// of seeking a particular location. + class MLocIterator { + LocToValueType &ValueMap; + LocIdx Idx; + + public: + class value_type { + public: + value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) {} + const LocIdx Idx; /// Read-only index of this location. + ValueIDNum &Value; /// Reference to the stored value at this location. + }; + + MLocIterator(LocToValueType &ValueMap, LocIdx Idx) + : ValueMap(ValueMap), Idx(Idx) {} + + bool operator==(const MLocIterator &Other) const { + assert(&ValueMap == &Other.ValueMap); + return Idx == Other.Idx; + } + + bool operator!=(const MLocIterator &Other) const { + return !(*this == Other); + } + + void operator++() { Idx = LocIdx(Idx.asU64() + 1); } + + value_type operator*() { return value_type(Idx, ValueMap[LocIdx(Idx)]); } + }; + + MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI, const TargetLowering &TLI); + + /// Produce location ID number for indexing LocIDToLocIdx. Takes the register + /// or spill number, and flag for whether it's a spill or not. + unsigned getLocID(Register RegOrSpill, bool isSpill) { + return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id(); + } + + /// Accessor for reading the value at Idx. + ValueIDNum getNumAtPos(LocIdx Idx) const { + assert(Idx.asU64() < LocIdxToIDNum.size()); + return LocIdxToIDNum[Idx]; + } + + unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); } + + /// Reset all locations to contain a PHI value at the designated block. Used + /// sometimes for actual PHI values, othertimes to indicate the block entry + /// value (before any more information is known). + void setMPhis(unsigned NewCurBB) { + CurBB = NewCurBB; + for (auto Location : locations()) + Location.Value = {CurBB, 0, Location.Idx}; + } + + /// Load values for each location from array of ValueIDNums. Take current + /// bbnum just in case we read a value from a hitherto untouched register. + void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) { + CurBB = NewCurBB; + // Iterate over all tracked locations, and load each locations live-in + // value into our local index. + for (auto Location : locations()) + Location.Value = Locs[Location.Idx.asU64()]; + } + + /// Wipe any un-necessary location records after traversing a block. + void reset(void) { + // We could reset all the location values too; however either loadFromArray + // or setMPhis should be called before this object is re-used. Just + // clear Masks, they're definitely not needed. + Masks.clear(); + } + + /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of + /// the information in this pass uninterpretable. + void clear(void) { + reset(); + LocIDToLocIdx.clear(); + LocIdxToLocID.clear(); + LocIdxToIDNum.clear(); + // SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from + // 0 + SpillLocs = decltype(SpillLocs)(); + + LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); + } + + /// Set a locaiton to a certain value. + void setMLoc(LocIdx L, ValueIDNum Num) { + assert(L.asU64() < LocIdxToIDNum.size()); + LocIdxToIDNum[L] = Num; + } + + /// Create a LocIdx for an untracked register ID. Initialize it to either an + /// mphi value representing a live-in, or a recent register mask clobber. + LocIdx trackRegister(unsigned ID); + + LocIdx lookupOrTrackRegister(unsigned ID) { + LocIdx &Index = LocIDToLocIdx[ID]; + if (Index.isIllegal()) + Index = trackRegister(ID); + return Index; + } + + /// Record a definition of the specified register at the given block / inst. + /// This doesn't take a ValueIDNum, because the definition and its location + /// are synonymous. + void defReg(Register R, unsigned BB, unsigned Inst) { + unsigned ID = getLocID(R, false); + LocIdx Idx = lookupOrTrackRegister(ID); + ValueIDNum ValueID = {BB, Inst, Idx}; + LocIdxToIDNum[Idx] = ValueID; + } + + /// Set a register to a value number. To be used if the value number is + /// known in advance. + void setReg(Register R, ValueIDNum ValueID) { + unsigned ID = getLocID(R, false); + LocIdx Idx = lookupOrTrackRegister(ID); + LocIdxToIDNum[Idx] = ValueID; + } + + ValueIDNum readReg(Register R) { + unsigned ID = getLocID(R, false); + LocIdx Idx = lookupOrTrackRegister(ID); + return LocIdxToIDNum[Idx]; + } + + /// Reset a register value to zero / empty. Needed to replicate the + /// VarLoc implementation where a copy to/from a register effectively + /// clears the contents of the source register. (Values can only have one + /// machine location in VarLocBasedImpl). + void wipeRegister(Register R) { + unsigned ID = getLocID(R, false); + LocIdx Idx = LocIDToLocIdx[ID]; + LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue; + } + + /// Determine the LocIdx of an existing register. + LocIdx getRegMLoc(Register R) { + unsigned ID = getLocID(R, false); + return LocIDToLocIdx[ID]; + } + + /// Record a RegMask operand being executed. Defs any register we currently + /// track, stores a pointer to the mask in case we have to account for it + /// later. + void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID); + + /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked. + LocIdx getOrTrackSpillLoc(SpillLoc L); + + /// Set the value stored in a spill slot. + void setSpill(SpillLoc L, ValueIDNum ValueID) { + LocIdx Idx = getOrTrackSpillLoc(L); + LocIdxToIDNum[Idx] = ValueID; + } + + /// Read whatever value is in a spill slot, or None if it isn't tracked. + Optional readSpill(SpillLoc L) { + unsigned SpillID = SpillLocs.idFor(L); + if (SpillID == 0) + return None; + + unsigned LocID = getLocID(SpillID, true); + LocIdx Idx = LocIDToLocIdx[LocID]; + return LocIdxToIDNum[Idx]; + } + + /// Determine the LocIdx of a spill slot. Return None if it previously + /// hasn't had a value assigned. + Optional getSpillMLoc(SpillLoc L) { + unsigned SpillID = SpillLocs.idFor(L); + if (SpillID == 0) + return None; + unsigned LocNo = getLocID(SpillID, true); + return LocIDToLocIdx[LocNo]; + } + + /// Return true if Idx is a spill machine location. + bool isSpill(LocIdx Idx) const { return LocIdxToLocID[Idx] >= NumRegs; } + + MLocIterator begin() { return MLocIterator(LocIdxToIDNum, 0); } + + MLocIterator end() { + return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size()); + } + + /// Return a range over all locations currently tracked. + iterator_range locations() { + return llvm::make_range(begin(), end()); + } + + std::string LocIdxToName(LocIdx Idx) const; + + std::string IDAsString(const ValueIDNum &Num) const; + + LLVM_DUMP_METHOD void dump(); + + LLVM_DUMP_METHOD void dump_mloc_map(); + + /// Create a DBG_VALUE based on machine location \p MLoc. Qualify it with the + /// information in \pProperties, for variable Var. Don't insert it anywhere, + /// just return the builder for it. + MachineInstrBuilder emitLoc(Optional MLoc, const DebugVariable &Var, + const DbgValueProperties &Properties); +}; + +/// Types for recording sets of variable fragments that overlap. For a given +/// local variable, we record all other fragments of that variable that could +/// overlap it, to reduce search time. +using FragmentOfVar = + std::pair; +using OverlapMap = + DenseMap>; + +// XXX XXX docs +class InstrRefBasedLDV : public LDVImpl { +private: + friend class ::InstrRefLDVTest; + + using FragmentInfo = DIExpression::FragmentInfo; + using OptFragmentInfo = Optional; + + // Helper while building OverlapMap, a map of all fragments seen for a given + // DILocalVariable. + using VarToFragments = + DenseMap>; + + /// Machine location/value transfer function, a mapping of which locations + /// are assigned which new values. + using MLocTransferMap = std::map; + + /// Live in/out structure for the variable values: a per-block map of + /// variables to their values. XXX, better name? + using LiveIdxT = + DenseMap *>; + + using VarAndLoc = std::pair; + + /// Type for a live-in value: the predecessor block, and its value. + using InValueT = std::pair; + + /// Vector (per block) of a collection (inner smallvector) of live-ins. + /// Used as the result type for the variable value dataflow problem. + using LiveInsT = SmallVector, 8>; + + const TargetRegisterInfo *TRI; + const TargetInstrInfo *TII; + const TargetFrameLowering *TFI; + const MachineFrameInfo *MFI; + BitVector CalleeSavedRegs; + LexicalScopes LS; + TargetPassConfig *TPC; + + /// Object to track machine locations as we step through a block. Could + /// probably be a field rather than a pointer, as it's always used. + MLocTracker *MTracker; + + /// Number of the current block LiveDebugValues is stepping through. + unsigned CurBB; + + /// Number of the current instruction LiveDebugValues is evaluating. + unsigned CurInst; + + /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl + /// steps through a block. Reads the values at each location from the + /// MLocTracker object. + VLocTracker *VTracker; + + /// Tracker for transfers, listens to DBG_VALUEs and transfers of values + /// between locations during stepping, creates new DBG_VALUEs when values move + /// location. + TransferTracker *TTracker; + + /// Blocks which are artificial, i.e. blocks which exclusively contain + /// instructions without DebugLocs, or with line 0 locations. + SmallPtrSet ArtificialBlocks; + + // Mapping of blocks to and from their RPOT order. + DenseMap OrderToBB; + DenseMap BBToOrder; + DenseMap BBNumToRPO; + + /// Pair of MachineInstr, and its 1-based offset into the containing block. + using InstAndNum = std::pair; + /// Map from debug instruction number to the MachineInstr labelled with that + /// number, and its location within the function. Used to transform + /// instruction numbers in DBG_INSTR_REFs into machine value numbers. + std::map DebugInstrNumToInstr; + + /// Record of where we observed a DBG_PHI instruction. + class DebugPHIRecord { + public: + uint64_t InstrNum; ///< Instruction number of this DBG_PHI. + MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred. + ValueIDNum ValueRead; ///< The value number read by the DBG_PHI. + LocIdx ReadLoc; ///< Register/Stack location the DBG_PHI reads. + + operator unsigned() const { return InstrNum; } + }; + + /// Map from instruction numbers defined by DBG_PHIs to a record of what that + /// DBG_PHI read and where. Populated and edited during the machine value + /// location problem -- we use LLVMs SSA Updater to fix changes by + /// optimizations that destroy PHI instructions. + SmallVector DebugPHINumToValue; + + // Map of overlapping variable fragments. + OverlapMap OverlapFragments; + VarToFragments SeenFragments; + + /// Tests whether this instruction is a spill to a stack slot. + 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); + + /// If a given instruction is identified as a spill, return the spill slot + /// and set \p Reg to the spilled register. + Optional isRestoreInstruction(const MachineInstr &MI, + MachineFunction *MF, unsigned &Reg); + + /// Given a spill instruction, extract the register and offset used to + /// address the spill slot in a target independent way. + SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); + + /// Observe a single instruction while stepping through a block. + void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr, + ValueIDNum **MLiveIns = nullptr); + + /// Examines whether \p MI is a DBG_VALUE and notifies trackers. + /// \returns true if MI was recognized and processed. + bool transferDebugValue(const MachineInstr &MI); + + /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers. + /// \returns true if MI was recognized and processed. + bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts, + ValueIDNum **MLiveIns); + + /// Stores value-information about where this PHI occurred, and what + /// instruction number is associated with it. + /// \returns true if MI was recognized and processed. + bool transferDebugPHI(MachineInstr &MI); + + /// Examines whether \p MI is copy instruction, and notifies trackers. + /// \returns true if MI was recognized and processed. + bool transferRegisterCopy(MachineInstr &MI); + + /// Examines whether \p MI is stack spill or restore instruction, and + /// notifies trackers. \returns true if MI was recognized and processed. + bool transferSpillOrRestoreInst(MachineInstr &MI); + + /// Examines \p MI for any registers that it defines, and notifies trackers. + void transferRegisterDef(MachineInstr &MI); + + /// Copy one location to the other, accounting for movement of subregisters + /// too. + void performCopy(Register Src, Register Dst); + + void accumulateFragmentMap(MachineInstr &MI); + + /// Determine the machine value number referred to by (potentially several) + /// DBG_PHI instructions. Block duplication and tail folding can duplicate + /// DBG_PHIs, shifting the position where values in registers merge, and + /// forming another mini-ssa problem to solve. + /// \p Here the position of a DBG_INSTR_REF seeking a machine value number + /// \p InstrNum Debug instruction number defined by DBG_PHI instructions. + /// \returns The machine value number at position Here, or None. + Optional resolveDbgPHIs(MachineFunction &MF, + ValueIDNum **MLiveOuts, + ValueIDNum **MLiveIns, MachineInstr &Here, + uint64_t InstrNum); + + /// Step through the function, recording register definitions and movements + /// in an MLocTracker. Convert the observations into a per-block transfer + /// function in \p MLocTransfer, suitable for using with the machine value + /// location dataflow problem. + void + produceMLocTransferFunction(MachineFunction &MF, + SmallVectorImpl &MLocTransfer, + unsigned MaxNumBlocks); + + /// Solve the machine value location dataflow problem. Takes as input the + /// transfer functions in \p MLocTransfer. Writes the output live-in and + /// live-out arrays to the (initialized to zero) multidimensional arrays in + /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block + /// number, the inner by LocIdx. + void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs, + SmallVectorImpl &MLocTransfer); + + /// Perform a control flow join (lattice value meet) of the values in machine + /// locations at \p MBB. Follows the algorithm described in the file-comment, + /// reading live-outs of predecessors from \p OutLocs, the current live ins + /// from \p InLocs, and assigning the newly computed live ins back into + /// \p InLocs. \returns two bools -- the first indicates whether a change + /// was made, the second whether a lattice downgrade occurred. If the latter + /// is true, revisiting this block is necessary. + std::tuple + mlocJoin(MachineBasicBlock &MBB, + SmallPtrSet &Visited, + ValueIDNum **OutLocs, ValueIDNum *InLocs); + + /// Solve the variable value dataflow problem, for a single lexical scope. + /// Uses the algorithm from the file comment to resolve control flow joins, + /// although there are extra hacks, see vlocJoin. Reads the + /// locations of values from the \p MInLocs and \p MOutLocs arrays (see + /// mlocDataflow) and reads the variable values transfer function from + /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally, + /// with the live-ins permanently stored to \p Output once the fixedpoint is + /// reached. + /// \p VarsWeCareAbout contains a collection of the variables in \p Scope + /// that we should be tracking. + /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but + /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations + /// through. + void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc, + const SmallSet &VarsWeCareAbout, + SmallPtrSetImpl &AssignBlocks, + LiveInsT &Output, ValueIDNum **MOutLocs, + ValueIDNum **MInLocs, + SmallVectorImpl &AllTheVLocs); + + /// Compute the live-ins to a block, considering control flow merges according + /// to the method in the file comment. Live out and live in variable values + /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB + /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins + /// are modified. + /// \p InLocsT Output argument, storage for calculated live-ins. + /// \returns two bools -- the first indicates whether a change + /// was made, the second whether a lattice downgrade occurred. If the latter + /// is true, revisiting this block is necessary. + std::tuple + vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, + SmallPtrSet *VLOCVisited, + unsigned BBNum, const SmallSet &AllVars, + ValueIDNum **MOutLocs, ValueIDNum **MInLocs, + SmallPtrSet &InScopeBlocks, + SmallPtrSet &BlocksToExplore, + DenseMap &InLocsT); + + /// Continue exploration of the variable-value lattice, as explained in the + /// file-level comment. \p OldLiveInLocation contains the current + /// exploration position, from which we need to descend further. \p Values + /// contains the set of live-in values, \p CurBlockRPONum the RPO number of + /// the current block, and \p CandidateLocations a set of locations that + /// should be considered as PHI locations, if we reach the bottom of the + /// lattice. \returns true if we should downgrade; the value is the agreeing + /// value number in a non-backedge predecessor. + bool vlocDowngradeLattice(const MachineBasicBlock &MBB, + const DbgValue &OldLiveInLocation, + const SmallVectorImpl &Values, + unsigned CurBlockRPONum); + + /// For the given block and live-outs feeding into it, try to find a + /// machine location where they all join. If a solution for all predecessors + /// can't be found, a location where all non-backedge-predecessors join + /// will be returned instead. While this method finds a join location, this + /// says nothing as to whether it should be used. + /// \returns Pair of value ID if found, and true when the correct value + /// is available on all predecessor edges, or false if it's only available + /// for non-backedge predecessors. + std::tuple, bool> + pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, + const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, + ValueIDNum **MInLocs, + const SmallVectorImpl &BlockOrders); + + /// Given the solutions to the two dataflow problems, machine value locations + /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the + /// TransferTracker class over the function to produce live-in and transfer + /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the + /// order given by AllVarsNumbering -- this could be any stable order, but + /// right now "order of appearence in function, when explored in RPO", so + /// that we can compare explictly against VarLocBasedImpl. + void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns, + ValueIDNum **MOutLocs, ValueIDNum **MInLocs, + DenseMap &AllVarsNumbering, + const TargetPassConfig &TPC); + + /// Boilerplate computation of some initial sets, artifical blocks and + /// RPOT block ordering. + void initialSetup(MachineFunction &MF); + + bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC, + unsigned InputBBLimit, unsigned InputDbgValLimit) override; + +public: + /// Default construct and initialize the pass. + InstrRefBasedLDV(); + + LLVM_DUMP_METHOD + void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const; + + bool isCalleeSaved(LocIdx L) const; +}; + +} // namespace LiveDebugValues + +#endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */ diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp --- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -153,7 +153,6 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/UniqueVector.h" #include "llvm/CodeGen/LexicalScopes.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" @@ -192,16 +191,18 @@ #include #include #include +#include +#include #include #include #include #include -#include -#include +#include "InstrRefBasedImpl.h" #include "LiveDebugValues.h" using namespace llvm; +using namespace LiveDebugValues; // SSAUpdaterImple sets DEBUG_TYPE, change it. #undef DEBUG_TYPE @@ -213,678 +214,15 @@ cl::desc("Act like old LiveDebugValues did"), cl::init(false)); -namespace { - -// The location at which a spilled value resides. It consists of a register and -// an offset. -struct SpillLoc { - unsigned SpillBase; - StackOffset SpillOffset; - bool operator==(const SpillLoc &Other) const { - return std::make_pair(SpillBase, SpillOffset) == - std::make_pair(Other.SpillBase, Other.SpillOffset); - } - bool operator<(const SpillLoc &Other) const { - return std::make_tuple(SpillBase, SpillOffset.getFixed(), - SpillOffset.getScalable()) < - std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(), - Other.SpillOffset.getScalable()); - } -}; - -class LocIdx { - unsigned Location; - - // Default constructor is private, initializing to an illegal location number. - // Use only for "not an entry" elements in IndexedMaps. - LocIdx() : Location(UINT_MAX) { } - -public: - #define NUM_LOC_BITS 24 - LocIdx(unsigned L) : Location(L) { - assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits"); - } - - static LocIdx MakeIllegalLoc() { - return LocIdx(); - } - - bool isIllegal() const { - return Location == UINT_MAX; - } - - uint64_t asU64() const { - return Location; - } - - bool operator==(unsigned L) const { - return Location == L; - } - - bool operator==(const LocIdx &L) const { - return Location == L.Location; - } - - bool operator!=(unsigned L) const { - return !(*this == L); - } - - bool operator!=(const LocIdx &L) const { - return !(*this == L); - } - - bool operator<(const LocIdx &Other) const { - return Location < Other.Location; - } -}; - -class LocIdxToIndexFunctor { +/// Thin wrapper around an integer -- designed to give more type safety to +/// spill location numbers. +class SpillLocationNo { public: - using argument_type = LocIdx; - unsigned operator()(const LocIdx &L) const { - return L.asU64(); - } -}; - -/// Unique identifier for a value defined by an instruction, as a value type. -/// Casts back and forth to a uint64_t. Probably replacable with something less -/// bit-constrained. Each value identifies the instruction and machine location -/// where the value is defined, although there may be no corresponding machine -/// operand for it (ex: regmasks clobbering values). The instructions are -/// one-based, and definitions that are PHIs have instruction number zero. -/// -/// The obvious limits of a 1M block function or 1M instruction blocks are -/// problematic; but by that point we should probably have bailed out of -/// trying to analyse the function. -class ValueIDNum { - uint64_t BlockNo : 20; /// The block where the def happens. - uint64_t InstNo : 20; /// The Instruction where the def happens. - /// One based, is distance from start of block. - uint64_t LocNo : NUM_LOC_BITS; /// The machine location where the def happens. - -public: - // XXX -- temporarily enabled while the live-in / live-out tables are moved - // to something more type-y - ValueIDNum() : BlockNo(0xFFFFF), - InstNo(0xFFFFF), - LocNo(0xFFFFFF) { } - - ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) - : BlockNo(Block), InstNo(Inst), LocNo(Loc) { } - - ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) - : BlockNo(Block), InstNo(Inst), LocNo(Loc.asU64()) { } - - uint64_t getBlock() const { return BlockNo; } - uint64_t getInst() const { return InstNo; } - uint64_t getLoc() const { return LocNo; } - bool isPHI() const { return InstNo == 0; } - - uint64_t asU64() const { - uint64_t TmpBlock = BlockNo; - uint64_t TmpInst = InstNo; - return TmpBlock << 44ull | TmpInst << NUM_LOC_BITS | LocNo; - } - - static ValueIDNum fromU64(uint64_t v) { - uint64_t L = (v & 0x3FFF); - return {v >> 44ull, ((v >> NUM_LOC_BITS) & 0xFFFFF), L}; - } - - bool operator<(const ValueIDNum &Other) const { - return asU64() < Other.asU64(); - } - - bool operator==(const ValueIDNum &Other) const { - return std::tie(BlockNo, InstNo, LocNo) == - std::tie(Other.BlockNo, Other.InstNo, Other.LocNo); - } - - bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); } - - std::string asString(const std::string &mlocname) const { - return Twine("Value{bb: ") - .concat(Twine(BlockNo).concat( - Twine(", inst: ") - .concat((InstNo ? Twine(InstNo) : Twine("live-in")) - .concat(Twine(", loc: ").concat(Twine(mlocname))) - .concat(Twine("}"))))) - .str(); - } - - static ValueIDNum EmptyValue; -}; - -} // end anonymous namespace - -namespace { - -/// Meta qualifiers for a value. Pair of whatever expression is used to qualify -/// the the value, and Boolean of whether or not it's indirect. -class DbgValueProperties { -public: - DbgValueProperties(const DIExpression *DIExpr, bool Indirect) - : DIExpr(DIExpr), Indirect(Indirect) {} - - /// Extract properties from an existing DBG_VALUE instruction. - DbgValueProperties(const MachineInstr &MI) { - assert(MI.isDebugValue()); - DIExpr = MI.getDebugExpression(); - Indirect = MI.getOperand(1).isImm(); - } - - bool operator==(const DbgValueProperties &Other) const { - return std::tie(DIExpr, Indirect) == std::tie(Other.DIExpr, Other.Indirect); - } - - bool operator!=(const DbgValueProperties &Other) const { - return !(*this == Other); - } - - const DIExpression *DIExpr; - bool Indirect; + explicit SpillLocationNo(unsigned SpillNo) : SpillNo(SpillNo) {} + unsigned SpillNo; + unsigned id() const { return SpillNo; } }; -/// Tracker for what values are in machine locations. Listens to the Things -/// being Done by various instructions, and maintains a table of what machine -/// locations have what values (as defined by a ValueIDNum). -/// -/// There are potentially a much larger number of machine locations on the -/// target machine than the actual working-set size of the function. On x86 for -/// example, we're extremely unlikely to want to track values through control -/// or debug registers. To avoid doing so, MLocTracker has several layers of -/// indirection going on, with two kinds of ``location'': -/// * A LocID uniquely identifies a register or spill location, with a -/// predictable value. -/// * A LocIdx is a key (in the database sense) for a LocID and a ValueIDNum. -/// Whenever a location is def'd or used by a MachineInstr, we automagically -/// create a new LocIdx for a location, but not otherwise. This ensures we only -/// account for locations that are actually used or defined. The cost is another -/// vector lookup (of LocID -> LocIdx) over any other implementation. This is -/// fairly cheap, and the compiler tries to reduce the working-set at any one -/// time in the function anyway. -/// -/// Register mask operands completely blow this out of the water; I've just -/// piled hacks on top of hacks to get around that. -class MLocTracker { -public: - MachineFunction &MF; - const TargetInstrInfo &TII; - const TargetRegisterInfo &TRI; - const TargetLowering &TLI; - - /// IndexedMap type, mapping from LocIdx to ValueIDNum. - using LocToValueType = IndexedMap; - - /// Map of LocIdxes to the ValueIDNums that they store. This is tightly - /// packed, entries only exist for locations that are being tracked. - LocToValueType LocIdxToIDNum; - - /// "Map" of machine location IDs (i.e., raw register or spill number) to the - /// LocIdx key / number for that location. There are always at least as many - /// as the number of registers on the target -- if the value in the register - /// is not being tracked, then the LocIdx value will be zero. New entries are - /// appended if a new spill slot begins being tracked. - /// This, and the corresponding reverse map persist for the analysis of the - /// whole function, and is necessarying for decoding various vectors of - /// values. - std::vector LocIDToLocIdx; - - /// Inverse map of LocIDToLocIdx. - IndexedMap LocIdxToLocID; - - /// Unique-ification of spill slots. Used to number them -- their LocID - /// number is the index in SpillLocs minus one plus NumRegs. - UniqueVector SpillLocs; - - // If we discover a new machine location, assign it an mphi with this - // block number. - unsigned CurBB; - - /// Cached local copy of the number of registers the target has. - unsigned NumRegs; - - /// Collection of register mask operands that have been observed. Second part - /// of pair indicates the instruction that they happened in. Used to - /// reconstruct where defs happened if we start tracking a location later - /// on. - SmallVector, 32> Masks; - - /// Iterator for locations and the values they contain. Dereferencing - /// produces a struct/pair containing the LocIdx key for this location, - /// and a reference to the value currently stored. Simplifies the process - /// of seeking a particular location. - class MLocIterator { - LocToValueType &ValueMap; - LocIdx Idx; - - public: - class value_type { - public: - value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) { } - const LocIdx Idx; /// Read-only index of this location. - ValueIDNum &Value; /// Reference to the stored value at this location. - }; - - MLocIterator(LocToValueType &ValueMap, LocIdx Idx) - : ValueMap(ValueMap), Idx(Idx) { } - - bool operator==(const MLocIterator &Other) const { - assert(&ValueMap == &Other.ValueMap); - return Idx == Other.Idx; - } - - bool operator!=(const MLocIterator &Other) const { - return !(*this == Other); - } - - void operator++() { - Idx = LocIdx(Idx.asU64() + 1); - } - - value_type operator*() { - return value_type(Idx, ValueMap[LocIdx(Idx)]); - } - }; - - MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, - const TargetRegisterInfo &TRI, const TargetLowering &TLI) - : MF(MF), TII(TII), TRI(TRI), TLI(TLI), - LocIdxToIDNum(ValueIDNum::EmptyValue), - LocIdxToLocID(0) { - NumRegs = TRI.getNumRegs(); - reset(); - LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); - assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure - - // Always track SP. This avoids the implicit clobbering caused by regmasks - // from affectings its values. (LiveDebugValues disbelieves calls and - // regmasks that claim to clobber SP). - Register SP = TLI.getStackPointerRegisterToSaveRestore(); - if (SP) { - unsigned ID = getLocID(SP, false); - (void)lookupOrTrackRegister(ID); - } - } - - /// Produce location ID number for indexing LocIDToLocIdx. Takes the register - /// or spill number, and flag for whether it's a spill or not. - unsigned getLocID(Register RegOrSpill, bool isSpill) { - return (isSpill) ? RegOrSpill.id() + NumRegs - 1 : RegOrSpill.id(); - } - - /// Accessor for reading the value at Idx. - ValueIDNum getNumAtPos(LocIdx Idx) const { - assert(Idx.asU64() < LocIdxToIDNum.size()); - return LocIdxToIDNum[Idx]; - } - - unsigned getNumLocs(void) const { return LocIdxToIDNum.size(); } - - /// Reset all locations to contain a PHI value at the designated block. Used - /// sometimes for actual PHI values, othertimes to indicate the block entry - /// value (before any more information is known). - void setMPhis(unsigned NewCurBB) { - CurBB = NewCurBB; - for (auto Location : locations()) - Location.Value = {CurBB, 0, Location.Idx}; - } - - /// Load values for each location from array of ValueIDNums. Take current - /// bbnum just in case we read a value from a hitherto untouched register. - void loadFromArray(ValueIDNum *Locs, unsigned NewCurBB) { - CurBB = NewCurBB; - // Iterate over all tracked locations, and load each locations live-in - // value into our local index. - for (auto Location : locations()) - Location.Value = Locs[Location.Idx.asU64()]; - } - - /// Wipe any un-necessary location records after traversing a block. - void reset(void) { - // We could reset all the location values too; however either loadFromArray - // or setMPhis should be called before this object is re-used. Just - // clear Masks, they're definitely not needed. - Masks.clear(); - } - - /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of - /// the information in this pass uninterpretable. - void clear(void) { - reset(); - LocIDToLocIdx.clear(); - LocIdxToLocID.clear(); - LocIdxToIDNum.clear(); - //SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from 0 - SpillLocs = decltype(SpillLocs)(); - - LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); - } - - /// Set a locaiton to a certain value. - void setMLoc(LocIdx L, ValueIDNum Num) { - assert(L.asU64() < LocIdxToIDNum.size()); - LocIdxToIDNum[L] = Num; - } - - /// Create a LocIdx for an untracked register ID. Initialize it to either an - /// mphi value representing a live-in, or a recent register mask clobber. - LocIdx trackRegister(unsigned ID) { - assert(ID != 0); - LocIdx NewIdx = LocIdx(LocIdxToIDNum.size()); - LocIdxToIDNum.grow(NewIdx); - LocIdxToLocID.grow(NewIdx); - - // Default: it's an mphi. - ValueIDNum ValNum = {CurBB, 0, NewIdx}; - // Was this reg ever touched by a regmask? - for (const auto &MaskPair : reverse(Masks)) { - if (MaskPair.first->clobbersPhysReg(ID)) { - // There was an earlier def we skipped. - ValNum = {CurBB, MaskPair.second, NewIdx}; - break; - } - } - - LocIdxToIDNum[NewIdx] = ValNum; - LocIdxToLocID[NewIdx] = ID; - return NewIdx; - } - - LocIdx lookupOrTrackRegister(unsigned ID) { - LocIdx &Index = LocIDToLocIdx[ID]; - if (Index.isIllegal()) - Index = trackRegister(ID); - return Index; - } - - /// Record a definition of the specified register at the given block / inst. - /// This doesn't take a ValueIDNum, because the definition and its location - /// are synonymous. - void defReg(Register R, unsigned BB, unsigned Inst) { - unsigned ID = getLocID(R, false); - LocIdx Idx = lookupOrTrackRegister(ID); - ValueIDNum ValueID = {BB, Inst, Idx}; - LocIdxToIDNum[Idx] = ValueID; - } - - /// Set a register to a value number. To be used if the value number is - /// known in advance. - void setReg(Register R, ValueIDNum ValueID) { - unsigned ID = getLocID(R, false); - LocIdx Idx = lookupOrTrackRegister(ID); - LocIdxToIDNum[Idx] = ValueID; - } - - ValueIDNum readReg(Register R) { - unsigned ID = getLocID(R, false); - LocIdx Idx = lookupOrTrackRegister(ID); - return LocIdxToIDNum[Idx]; - } - - /// Reset a register value to zero / empty. Needed to replicate the - /// VarLoc implementation where a copy to/from a register effectively - /// clears the contents of the source register. (Values can only have one - /// machine location in VarLocBasedImpl). - void wipeRegister(Register R) { - unsigned ID = getLocID(R, false); - LocIdx Idx = LocIDToLocIdx[ID]; - LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue; - } - - /// Determine the LocIdx of an existing register. - LocIdx getRegMLoc(Register R) { - unsigned ID = getLocID(R, false); - return LocIDToLocIdx[ID]; - } - - /// Record a RegMask operand being executed. Defs any register we currently - /// track, stores a pointer to the mask in case we have to account for it - /// later. - void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID) { - // Ensure SP exists, so that we don't override it later. - Register SP = TLI.getStackPointerRegisterToSaveRestore(); - - // Def any register we track have that isn't preserved. The regmask - // terminates the liveness of a register, meaning its value can't be - // relied upon -- we represent this by giving it a new value. - for (auto Location : locations()) { - unsigned ID = LocIdxToLocID[Location.Idx]; - // Don't clobber SP, even if the mask says it's clobbered. - if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID)) - defReg(ID, CurBB, InstID); - } - Masks.push_back(std::make_pair(MO, InstID)); - } - - /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked. - LocIdx getOrTrackSpillLoc(SpillLoc L) { - unsigned SpillID = SpillLocs.idFor(L); - if (SpillID == 0) { - SpillID = SpillLocs.insert(L); - unsigned L = getLocID(SpillID, true); - LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx - LocIdxToIDNum.grow(Idx); - LocIdxToLocID.grow(Idx); - LocIDToLocIdx.push_back(Idx); - LocIdxToLocID[Idx] = L; - return Idx; - } else { - unsigned L = getLocID(SpillID, true); - LocIdx Idx = LocIDToLocIdx[L]; - return Idx; - } - } - - /// Set the value stored in a spill slot. - void setSpill(SpillLoc L, ValueIDNum ValueID) { - LocIdx Idx = getOrTrackSpillLoc(L); - LocIdxToIDNum[Idx] = ValueID; - } - - /// Read whatever value is in a spill slot, or None if it isn't tracked. - Optional readSpill(SpillLoc L) { - unsigned SpillID = SpillLocs.idFor(L); - if (SpillID == 0) - return None; - - unsigned LocID = getLocID(SpillID, true); - LocIdx Idx = LocIDToLocIdx[LocID]; - return LocIdxToIDNum[Idx]; - } - - /// Determine the LocIdx of a spill slot. Return None if it previously - /// hasn't had a value assigned. - Optional getSpillMLoc(SpillLoc L) { - unsigned SpillID = SpillLocs.idFor(L); - if (SpillID == 0) - return None; - unsigned LocNo = getLocID(SpillID, true); - return LocIDToLocIdx[LocNo]; - } - - /// Return true if Idx is a spill machine location. - bool isSpill(LocIdx Idx) const { - return LocIdxToLocID[Idx] >= NumRegs; - } - - MLocIterator begin() { - return MLocIterator(LocIdxToIDNum, 0); - } - - MLocIterator end() { - return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size()); - } - - /// Return a range over all locations currently tracked. - iterator_range locations() { - return llvm::make_range(begin(), end()); - } - - std::string LocIdxToName(LocIdx Idx) const { - unsigned ID = LocIdxToLocID[Idx]; - if (ID >= NumRegs) - return Twine("slot ").concat(Twine(ID - NumRegs)).str(); - else - return TRI.getRegAsmName(ID).str(); - } - - std::string IDAsString(const ValueIDNum &Num) const { - std::string DefName = LocIdxToName(Num.getLoc()); - return Num.asString(DefName); - } - - LLVM_DUMP_METHOD - void dump() { - for (auto Location : locations()) { - std::string MLocName = LocIdxToName(Location.Value.getLoc()); - std::string DefName = Location.Value.asString(MLocName); - dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n"; - } - } - - LLVM_DUMP_METHOD - void dump_mloc_map() { - for (auto Location : locations()) { - std::string foo = LocIdxToName(Location.Idx); - dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n"; - } - } - - /// Create a DBG_VALUE based on machine location \p MLoc. Qualify it with the - /// information in \pProperties, for variable Var. Don't insert it anywhere, - /// just return the builder for it. - MachineInstrBuilder emitLoc(Optional MLoc, const DebugVariable &Var, - const DbgValueProperties &Properties) { - DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, - Var.getVariable()->getScope(), - const_cast(Var.getInlinedAt())); - auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE)); - - const DIExpression *Expr = Properties.DIExpr; - if (!MLoc) { - // No location -> DBG_VALUE $noreg - MIB.addReg(0); - MIB.addReg(0); - } else if (LocIdxToLocID[*MLoc] >= NumRegs) { - unsigned LocID = LocIdxToLocID[*MLoc]; - const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1]; - - auto *TRI = MF.getSubtarget().getRegisterInfo(); - Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset, - Spill.SpillOffset); - unsigned Base = Spill.SpillBase; - MIB.addReg(Base); - MIB.addImm(0); - } else { - unsigned LocID = LocIdxToLocID[*MLoc]; - MIB.addReg(LocID); - if (Properties.Indirect) - MIB.addImm(0); - else - MIB.addReg(0); - } - - MIB.addMetadata(Var.getVariable()); - MIB.addMetadata(Expr); - return MIB; - } -}; - -/// Class recording the (high level) _value_ of a variable. Identifies either -/// the value of the variable as a ValueIDNum, or a constant MachineOperand. -/// This class also stores meta-information about how the value is qualified. -/// Used to reason about variable values when performing the second -/// (DebugVariable specific) dataflow analysis. -class DbgValue { -public: - union { - /// If Kind is Def, the value number that this value is based on. - ValueIDNum ID; - /// If Kind is Const, the MachineOperand defining this value. - MachineOperand MO; - /// For a NoVal DbgValue, which block it was generated in. - unsigned BlockNo; - }; - /// Qualifiers for the ValueIDNum above. - DbgValueProperties Properties; - - typedef enum { - Undef, // Represents a DBG_VALUE $noreg in the transfer function only. - Def, // This value is defined by an inst, or is a PHI value. - Const, // A constant value contained in the MachineOperand field. - Proposed, // This is a tentative PHI value, which may be confirmed or - // invalidated later. - NoVal // Empty DbgValue, generated during dataflow. BlockNo stores - // which block this was generated in. - } KindT; - /// Discriminator for whether this is a constant or an in-program value. - KindT Kind; - - DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind) - : ID(Val), Properties(Prop), Kind(Kind) { - assert(Kind == Def || Kind == Proposed); - } - - DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind) - : BlockNo(BlockNo), Properties(Prop), Kind(Kind) { - assert(Kind == NoVal); - } - - DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind) - : MO(MO), Properties(Prop), Kind(Kind) { - assert(Kind == Const); - } - - DbgValue(const DbgValueProperties &Prop, KindT Kind) - : Properties(Prop), Kind(Kind) { - assert(Kind == Undef && - "Empty DbgValue constructor must pass in Undef kind"); - } - - void dump(const MLocTracker *MTrack) const { - if (Kind == Const) { - MO.dump(); - } else if (Kind == NoVal) { - dbgs() << "NoVal(" << BlockNo << ")"; - } else if (Kind == Proposed) { - dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")"; - } else { - assert(Kind == Def); - dbgs() << MTrack->IDAsString(ID); - } - if (Properties.Indirect) - dbgs() << " indir"; - if (Properties.DIExpr) - dbgs() << " " << *Properties.DIExpr; - } - - bool operator==(const DbgValue &Other) const { - if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties)) - return false; - else if (Kind == Proposed && ID != Other.ID) - return false; - else if (Kind == Def && ID != Other.ID) - return false; - else if (Kind == NoVal && BlockNo != Other.BlockNo) - return false; - else if (Kind == Const) - return MO.isIdenticalTo(Other.MO); - - return true; - } - - bool operator!=(const DbgValue &Other) const { return !(*this == Other); } -}; - -/// Types for recording sets of variable fragments that overlap. For a given -/// local variable, we record all other fragments of that variable that could -/// overlap it, to reduce search time. -using FragmentOfVar = - std::pair; -using OverlapMap = - DenseMap>; - /// Collection of DBG_VALUEs observed when traversing a block. Records each /// variable and the value the DBG_VALUE refers to. Requires the machine value /// location dataflow algorithm to have run already, so that values can be @@ -1411,307 +749,182 @@ } }; -class InstrRefBasedLDV : public LDVImpl { -private: - using FragmentInfo = DIExpression::FragmentInfo; - using OptFragmentInfo = Optional; - - // Helper while building OverlapMap, a map of all fragments seen for a given - // DILocalVariable. - using VarToFragments = - DenseMap>; - - /// Machine location/value transfer function, a mapping of which locations - /// are assigned which new values. - using MLocTransferMap = std::map; - - /// Live in/out structure for the variable values: a per-block map of - /// variables to their values. XXX, better name? - using LiveIdxT = - DenseMap *>; - - using VarAndLoc = std::pair; - - /// Type for a live-in value: the predecessor block, and its value. - using InValueT = std::pair; - - /// Vector (per block) of a collection (inner smallvector) of live-ins. - /// Used as the result type for the variable value dataflow problem. - using LiveInsT = SmallVector, 8>; - - const TargetRegisterInfo *TRI; - const TargetInstrInfo *TII; - const TargetFrameLowering *TFI; - const MachineFrameInfo *MFI; - BitVector CalleeSavedRegs; - LexicalScopes LS; - TargetPassConfig *TPC; - - /// Object to track machine locations as we step through a block. Could - /// probably be a field rather than a pointer, as it's always used. - MLocTracker *MTracker; - - /// Number of the current block LiveDebugValues is stepping through. - unsigned CurBB; - - /// Number of the current instruction LiveDebugValues is evaluating. - unsigned CurInst; - - /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl - /// steps through a block. Reads the values at each location from the - /// MLocTracker object. - VLocTracker *VTracker; +//===----------------------------------------------------------------------===// +// Implementation +//===----------------------------------------------------------------------===// - /// Tracker for transfers, listens to DBG_VALUEs and transfers of values - /// between locations during stepping, creates new DBG_VALUEs when values move - /// location. - TransferTracker *TTracker; +ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX}; - /// Blocks which are artificial, i.e. blocks which exclusively contain - /// instructions without DebugLocs, or with line 0 locations. - SmallPtrSet ArtificialBlocks; +void DbgValue::dump(const MLocTracker *MTrack) const { + if (Kind == Const) { + MO.dump(); + } else if (Kind == NoVal) { + dbgs() << "NoVal(" << BlockNo << ")"; + } else if (Kind == Proposed) { + dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")"; + } else { + assert(Kind == Def); + dbgs() << MTrack->IDAsString(ID); + } + if (Properties.Indirect) + dbgs() << " indir"; + if (Properties.DIExpr) + dbgs() << " " << *Properties.DIExpr; +} - // Mapping of blocks to and from their RPOT order. - DenseMap OrderToBB; - DenseMap BBToOrder; - DenseMap BBNumToRPO; +MLocTracker::MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI, + const TargetLowering &TLI) + : MF(MF), TII(TII), TRI(TRI), TLI(TLI), + LocIdxToIDNum(ValueIDNum::EmptyValue), LocIdxToLocID(0) { + NumRegs = TRI.getNumRegs(); + reset(); + LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc()); + assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure + + // Always track SP. This avoids the implicit clobbering caused by regmasks + // from affectings its values. (LiveDebugValues disbelieves calls and + // regmasks that claim to clobber SP). + Register SP = TLI.getStackPointerRegisterToSaveRestore(); + if (SP) { + unsigned ID = getLocID(SP, false); + (void)lookupOrTrackRegister(ID); + } +} - /// Pair of MachineInstr, and its 1-based offset into the containing block. - using InstAndNum = std::pair; - /// Map from debug instruction number to the MachineInstr labelled with that - /// number, and its location within the function. Used to transform - /// instruction numbers in DBG_INSTR_REFs into machine value numbers. - std::map DebugInstrNumToInstr; +LocIdx MLocTracker::trackRegister(unsigned ID) { + assert(ID != 0); + LocIdx NewIdx = LocIdx(LocIdxToIDNum.size()); + LocIdxToIDNum.grow(NewIdx); + LocIdxToLocID.grow(NewIdx); + + // Default: it's an mphi. + ValueIDNum ValNum = {CurBB, 0, NewIdx}; + // Was this reg ever touched by a regmask? + for (const auto &MaskPair : reverse(Masks)) { + if (MaskPair.first->clobbersPhysReg(ID)) { + // There was an earlier def we skipped. + ValNum = {CurBB, MaskPair.second, NewIdx}; + break; + } + } - /// Record of where we observed a DBG_PHI instruction. - class DebugPHIRecord { - public: - uint64_t InstrNum; ///< Instruction number of this DBG_PHI. - MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred. - ValueIDNum ValueRead; ///< The value number read by the DBG_PHI. - LocIdx ReadLoc; ///< Register/Stack location the DBG_PHI reads. + LocIdxToIDNum[NewIdx] = ValNum; + LocIdxToLocID[NewIdx] = ID; + return NewIdx; +} - operator unsigned() const { return InstrNum; } - }; +void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB, + unsigned InstID) { + // Ensure SP exists, so that we don't override it later. + Register SP = TLI.getStackPointerRegisterToSaveRestore(); + + // Def any register we track have that isn't preserved. The regmask + // terminates the liveness of a register, meaning its value can't be + // relied upon -- we represent this by giving it a new value. + for (auto Location : locations()) { + unsigned ID = LocIdxToLocID[Location.Idx]; + // Don't clobber SP, even if the mask says it's clobbered. + if (ID < NumRegs && ID != SP && MO->clobbersPhysReg(ID)) + defReg(ID, CurBB, InstID); + } + Masks.push_back(std::make_pair(MO, InstID)); +} - /// Map from instruction numbers defined by DBG_PHIs to a record of what that - /// DBG_PHI read and where. Populated and edited during the machine value - /// location problem -- we use LLVMs SSA Updater to fix changes by - /// optimizations that destroy PHI instructions. - SmallVector DebugPHINumToValue; - - // Map of overlapping variable fragments. - OverlapMap OverlapFragments; - VarToFragments SeenFragments; - - /// Tests whether this instruction is a spill to a stack slot. - 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); - - /// If a given instruction is identified as a spill, return the spill slot - /// and set \p Reg to the spilled register. - Optional isRestoreInstruction(const MachineInstr &MI, - MachineFunction *MF, unsigned &Reg); - - /// Given a spill instruction, extract the register and offset used to - /// address the spill slot in a target independent way. - SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); - - /// Observe a single instruction while stepping through a block. - void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr, - ValueIDNum **MLiveIns = nullptr); - - /// Examines whether \p MI is a DBG_VALUE and notifies trackers. - /// \returns true if MI was recognized and processed. - bool transferDebugValue(const MachineInstr &MI); - - /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers. - /// \returns true if MI was recognized and processed. - bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts, - ValueIDNum **MLiveIns); - - /// Stores value-information about where this PHI occurred, and what - /// instruction number is associated with it. - /// \returns true if MI was recognized and processed. - bool transferDebugPHI(MachineInstr &MI); - - /// Examines whether \p MI is copy instruction, and notifies trackers. - /// \returns true if MI was recognized and processed. - bool transferRegisterCopy(MachineInstr &MI); - - /// Examines whether \p MI is stack spill or restore instruction, and - /// notifies trackers. \returns true if MI was recognized and processed. - bool transferSpillOrRestoreInst(MachineInstr &MI); - - /// Examines \p MI for any registers that it defines, and notifies trackers. - void transferRegisterDef(MachineInstr &MI); - - /// Copy one location to the other, accounting for movement of subregisters - /// too. - void performCopy(Register Src, Register Dst); - - void accumulateFragmentMap(MachineInstr &MI); - - /// Determine the machine value number referred to by (potentially several) - /// DBG_PHI instructions. Block duplication and tail folding can duplicate - /// DBG_PHIs, shifting the position where values in registers merge, and - /// forming another mini-ssa problem to solve. - /// \p Here the position of a DBG_INSTR_REF seeking a machine value number - /// \p InstrNum Debug instruction number defined by DBG_PHI instructions. - /// \returns The machine value number at position Here, or None. - Optional resolveDbgPHIs(MachineFunction &MF, - ValueIDNum **MLiveOuts, - ValueIDNum **MLiveIns, MachineInstr &Here, - uint64_t InstrNum); - - /// Step through the function, recording register definitions and movements - /// in an MLocTracker. Convert the observations into a per-block transfer - /// function in \p MLocTransfer, suitable for using with the machine value - /// location dataflow problem. - void - produceMLocTransferFunction(MachineFunction &MF, - SmallVectorImpl &MLocTransfer, - unsigned MaxNumBlocks); - - /// Solve the machine value location dataflow problem. Takes as input the - /// transfer functions in \p MLocTransfer. Writes the output live-in and - /// live-out arrays to the (initialized to zero) multidimensional arrays in - /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block - /// number, the inner by LocIdx. - void mlocDataflow(ValueIDNum **MInLocs, ValueIDNum **MOutLocs, - SmallVectorImpl &MLocTransfer); - - /// Perform a control flow join (lattice value meet) of the values in machine - /// locations at \p MBB. Follows the algorithm described in the file-comment, - /// reading live-outs of predecessors from \p OutLocs, the current live ins - /// from \p InLocs, and assigning the newly computed live ins back into - /// \p InLocs. \returns two bools -- the first indicates whether a change - /// was made, the second whether a lattice downgrade occurred. If the latter - /// is true, revisiting this block is necessary. - std::tuple - mlocJoin(MachineBasicBlock &MBB, - SmallPtrSet &Visited, - ValueIDNum **OutLocs, ValueIDNum *InLocs); - - /// Solve the variable value dataflow problem, for a single lexical scope. - /// Uses the algorithm from the file comment to resolve control flow joins, - /// although there are extra hacks, see vlocJoin. Reads the - /// locations of values from the \p MInLocs and \p MOutLocs arrays (see - /// mlocDataflow) and reads the variable values transfer function from - /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally, - /// with the live-ins permanently stored to \p Output once the fixedpoint is - /// reached. - /// \p VarsWeCareAbout contains a collection of the variables in \p Scope - /// that we should be tracking. - /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but - /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations - /// through. - void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc, - const SmallSet &VarsWeCareAbout, - SmallPtrSetImpl &AssignBlocks, - LiveInsT &Output, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, - SmallVectorImpl &AllTheVLocs); - - /// Compute the live-ins to a block, considering control flow merges according - /// to the method in the file comment. Live out and live in variable values - /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB - /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins - /// are modified. - /// \p InLocsT Output argument, storage for calculated live-ins. - /// \returns two bools -- the first indicates whether a change - /// was made, the second whether a lattice downgrade occurred. If the latter - /// is true, revisiting this block is necessary. - std::tuple - vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, - SmallPtrSet *VLOCVisited, - unsigned BBNum, const SmallSet &AllVars, - ValueIDNum **MOutLocs, ValueIDNum **MInLocs, - SmallPtrSet &InScopeBlocks, - SmallPtrSet &BlocksToExplore, - DenseMap &InLocsT); - - /// Continue exploration of the variable-value lattice, as explained in the - /// file-level comment. \p OldLiveInLocation contains the current - /// exploration position, from which we need to descend further. \p Values - /// contains the set of live-in values, \p CurBlockRPONum the RPO number of - /// the current block, and \p CandidateLocations a set of locations that - /// should be considered as PHI locations, if we reach the bottom of the - /// lattice. \returns true if we should downgrade; the value is the agreeing - /// value number in a non-backedge predecessor. - bool vlocDowngradeLattice(const MachineBasicBlock &MBB, - const DbgValue &OldLiveInLocation, - const SmallVectorImpl &Values, - unsigned CurBlockRPONum); - - /// For the given block and live-outs feeding into it, try to find a - /// machine location where they all join. If a solution for all predecessors - /// can't be found, a location where all non-backedge-predecessors join - /// will be returned instead. While this method finds a join location, this - /// says nothing as to whether it should be used. - /// \returns Pair of value ID if found, and true when the correct value - /// is available on all predecessor edges, or false if it's only available - /// for non-backedge predecessors. - std::tuple, bool> - pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, - const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, - const SmallVectorImpl &BlockOrders); - - /// Given the solutions to the two dataflow problems, machine value locations - /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the - /// TransferTracker class over the function to produce live-in and transfer - /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the - /// order given by AllVarsNumbering -- this could be any stable order, but - /// right now "order of appearence in function, when explored in RPO", so - /// that we can compare explictly against VarLocBasedImpl. - void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns, - ValueIDNum **MOutLocs, ValueIDNum **MInLocs, - DenseMap &AllVarsNumbering, - const TargetPassConfig &TPC); - - /// Boilerplate computation of some initial sets, artifical blocks and - /// RPOT block ordering. - void initialSetup(MachineFunction &MF); - - bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC, - unsigned InputBBLimit, unsigned InputDbgValLimit) override; +LocIdx MLocTracker::getOrTrackSpillLoc(SpillLoc L) { + unsigned SpillID = SpillLocs.idFor(L); + if (SpillID == 0) { + SpillID = SpillLocs.insert(L); + unsigned L = getLocID(SpillID, true); + LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx + LocIdxToIDNum.grow(Idx); + LocIdxToLocID.grow(Idx); + LocIDToLocIdx.push_back(Idx); + LocIdxToLocID[Idx] = L; + return Idx; + } else { + unsigned L = getLocID(SpillID, true); + LocIdx Idx = LocIDToLocIdx[L]; + return Idx; + } +} -public: - /// Default construct and initialize the pass. - InstrRefBasedLDV(); +std::string MLocTracker::LocIdxToName(LocIdx Idx) const { + unsigned ID = LocIdxToLocID[Idx]; + if (ID >= NumRegs) + return Twine("slot ").concat(Twine(ID - NumRegs)).str(); + else + return TRI.getRegAsmName(ID).str(); +} - LLVM_DUMP_METHOD - void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const; +std::string MLocTracker::IDAsString(const ValueIDNum &Num) const { + std::string DefName = LocIdxToName(Num.getLoc()); + return Num.asString(DefName); +} - bool isCalleeSaved(LocIdx L) { - unsigned Reg = MTracker->LocIdxToLocID[L]; - for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) - if (CalleeSavedRegs.test(*RAI)) - return true; - return false; +LLVM_DUMP_METHOD void MLocTracker::dump() { + for (auto Location : locations()) { + std::string MLocName = LocIdxToName(Location.Value.getLoc()); + std::string DefName = Location.Value.asString(MLocName); + dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n"; } -}; +} -} // end anonymous namespace +LLVM_DUMP_METHOD void MLocTracker::dump_mloc_map() { + for (auto Location : locations()) { + std::string foo = LocIdxToName(Location.Idx); + dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n"; + } +} -//===----------------------------------------------------------------------===// -// Implementation -//===----------------------------------------------------------------------===// +MachineInstrBuilder MLocTracker::emitLoc(Optional MLoc, + const DebugVariable &Var, + const DbgValueProperties &Properties) { + DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, + Var.getVariable()->getScope(), + const_cast(Var.getInlinedAt())); + auto MIB = BuildMI(MF, DL, TII.get(TargetOpcode::DBG_VALUE)); + + const DIExpression *Expr = Properties.DIExpr; + if (!MLoc) { + // No location -> DBG_VALUE $noreg + MIB.addReg(0); + MIB.addReg(0); + } else if (LocIdxToLocID[*MLoc] >= NumRegs) { + unsigned LocID = LocIdxToLocID[*MLoc]; + const SpillLoc &Spill = SpillLocs[LocID - NumRegs + 1]; + + auto *TRI = MF.getSubtarget().getRegisterInfo(); + Expr = TRI->prependOffsetExpression(Expr, DIExpression::ApplyOffset, + Spill.SpillOffset); + unsigned Base = Spill.SpillBase; + MIB.addReg(Base); + MIB.addImm(0); + } else { + unsigned LocID = LocIdxToLocID[*MLoc]; + MIB.addReg(LocID); + if (Properties.Indirect) + MIB.addImm(0); + else + MIB.addReg(0); + } -ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX}; + MIB.addMetadata(Var.getVariable()); + MIB.addMetadata(Expr); + return MIB; +} /// Default construct and initialize the pass. InstrRefBasedLDV::InstrRefBasedLDV() {} +bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const { + unsigned Reg = MTracker->LocIdxToLocID[L]; + for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) + if (CalleeSavedRegs.test(*RAI)) + return true; + return false; +} + //===----------------------------------------------------------------------===// // Debug Range Extension Implementation //===----------------------------------------------------------------------===// diff --git a/llvm/unittests/CodeGen/CMakeLists.txt b/llvm/unittests/CodeGen/CMakeLists.txt --- a/llvm/unittests/CodeGen/CMakeLists.txt +++ b/llvm/unittests/CodeGen/CMakeLists.txt @@ -20,6 +20,7 @@ AsmPrinterDwarfTest.cpp DIEHashTest.cpp DIETest.cpp + InstrRefLDVTest.cpp LowLevelTypeTest.cpp LexicalScopesTest.cpp MachineInstrBundleIteratorTest.cpp diff --git a/llvm/unittests/CodeGen/InstrRefLDVTest.cpp b/llvm/unittests/CodeGen/InstrRefLDVTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/CodeGen/InstrRefLDVTest.cpp @@ -0,0 +1,99 @@ +//===------------- llvm/unittest/CodeGen/InstrRefLDVTest.cpp --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/IR/DIBuilder.h" +#include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/MC/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" + +#include "../lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h" + +#include "gtest/gtest.h" + +using namespace llvm; +using namespace LiveDebugValues; + +// Include helper functions to ease the manipulation of MachineFunctions +#include "MFCommon.inc" + +class InstrRefLDVTest : public testing::Test { +public: + LLVMContext Ctx; + Module Mod; + std::unique_ptr MF; + DICompileUnit *OurCU; + DIFile *OurFile; + DISubprogram *OurFunc; + DILexicalBlock *OurBlock, *AnotherBlock; + DISubprogram *ToInlineFunc; + DILexicalBlock *ToInlineBlock; + + DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc; + + MachineBasicBlock *MBB1, *MBB2, *MBB3, *MBB4; + + InstrRefLDVTest() : Ctx(), Mod("beehives", Ctx) { + // Boilerplate that creates a MachineFunction and associated blocks. + MF = createMachineFunction(Ctx, Mod); + llvm::Function &F = const_cast(MF->getFunction()); + auto BB1 = BasicBlock::Create(Ctx, "a", &F); + auto BB2 = BasicBlock::Create(Ctx, "b", &F); + auto BB3 = BasicBlock::Create(Ctx, "c", &F); + auto BB4 = BasicBlock::Create(Ctx, "d", &F); + IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4); + IRB1.CreateBr(BB2); + IRB2.CreateBr(BB3); + IRB3.CreateBr(BB4); + IRB4.CreateRetVoid(); + MBB1 = MF->CreateMachineBasicBlock(BB1); + MF->insert(MF->end(), MBB1); + MBB2 = MF->CreateMachineBasicBlock(BB2); + MF->insert(MF->end(), MBB2); + MBB3 = MF->CreateMachineBasicBlock(BB3); + MF->insert(MF->end(), MBB3); + MBB4 = MF->CreateMachineBasicBlock(BB4); + MF->insert(MF->end(), MBB4); + MBB1->addSuccessor(MBB2); + MBB1->addSuccessor(MBB3); + MBB2->addSuccessor(MBB4); + MBB3->addSuccessor(MBB4); + + // Create metadata: CU, subprogram, some blocks and an inline function + // scope. + DIBuilder DIB(Mod); + OurFile = DIB.createFile("xyzzy.c", "/cave"); + OurCU = + DIB.createCompileUnit(dwarf::DW_LANG_C99, OurFile, "nou", false, "", 0); + auto OurSubT = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None)); + OurFunc = + DIB.createFunction(OurCU, "bees", "", OurFile, 1, OurSubT, 1, + DINode::FlagZero, DISubprogram::SPFlagDefinition); + F.setSubprogram(OurFunc); + OurBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 3); + AnotherBlock = DIB.createLexicalBlock(OurFunc, OurFile, 2, 6); + ToInlineFunc = + DIB.createFunction(OurFile, "shoes", "", OurFile, 10, OurSubT, 10, + DINode::FlagZero, DISubprogram::SPFlagDefinition); + + // Make some nested scopes. + OutermostLoc = DILocation::get(Ctx, 3, 1, OurFunc); + InBlockLoc = DILocation::get(Ctx, 4, 1, OurBlock); + InlinedLoc = DILocation::get(Ctx, 10, 1, ToInlineFunc, InBlockLoc.get()); + + // Make a scope that isn't nested within the others. + NotNestedBlockLoc = DILocation::get(Ctx, 4, 1, AnotherBlock); + + DIB.finalize(); + } +};