diff options
Diffstat (limited to 'llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp')
| -rw-r--r-- | llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp | 2913 |
1 files changed, 1134 insertions, 1779 deletions
diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp index dc9907058340..a4eb3094612b 100644 --- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -11,114 +11,48 @@ /// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information. /// /// This pass propagates variable locations between basic blocks, resolving -/// control flow conflicts between them. The problem is much like SSA -/// construction, where each DBG_VALUE instruction assigns the *value* that -/// a variable has, and every instruction where the variable is in scope uses -/// that variable. The resulting map of instruction-to-value is then translated -/// into a register (or spill) location for each variable over each instruction. +/// control flow conflicts between them. The problem is SSA construction, where +/// each debug instruction assigns the *value* that a variable has, and every +/// instruction where the variable is in scope uses that variable. The resulting +/// map of instruction-to-value is then translated into a register (or spill) +/// location for each variable over each instruction. /// -/// This pass determines which DBG_VALUE dominates which instructions, or if -/// none do, where values must be merged (like PHI nodes). The added -/// complication is that because codegen has already finished, a PHI node may -/// be needed for a variable location to be correct, but no register or spill -/// slot merges the necessary values. In these circumstances, the variable -/// location is dropped. +/// The primary difference from normal SSA construction is that we cannot +/// _create_ PHI values that contain variable values. CodeGen has already +/// completed, and we can't alter it just to make debug-info complete. Thus: +/// we can identify function positions where we would like a PHI value for a +/// variable, but must search the MachineFunction to see whether such a PHI is +/// available. If no such PHI exists, the variable location must be dropped. /// -/// What makes this analysis non-trivial is loops: we cannot tell in advance -/// whether a variable location is live throughout a loop, or whether its -/// location is clobbered (or redefined by another DBG_VALUE), without -/// exploring all the way through. -/// -/// To make this simpler we perform two kinds of analysis. First, we identify +/// To achieve this, we perform two kinds of analysis. First, we identify /// every value defined by every instruction (ignoring those that only move -/// another value), then compute a map of which values are available for each -/// instruction. This is stronger than a reaching-def analysis, as we create -/// PHI values where other values merge. -/// -/// Secondly, for each variable, we effectively re-construct SSA using each -/// DBG_VALUE as a def. The DBG_VALUEs read a value-number computed by the -/// first analysis from the location they refer to. We can then compute the -/// dominance frontiers of where a variable has a value, and create PHI nodes -/// where they merge. -/// This isn't precisely SSA-construction though, because the function shape -/// is pre-defined. If a variable location requires a PHI node, but no -/// PHI for the relevant values is present in the function (as computed by the -/// first analysis), the location must be dropped. -/// -/// Once both are complete, we can pass back over all instructions knowing: -/// * What _value_ each variable should contain, either defined by an -/// instruction or where control flow merges -/// * What the location of that value is (if any). -/// Allowing us to create appropriate live-in DBG_VALUEs, and DBG_VALUEs when -/// a value moves location. After this pass runs, all variable locations within -/// a block should be specified by DBG_VALUEs within that block, allowing -/// DbgEntityHistoryCalculator to focus on individual blocks. -/// -/// This pass is able to go fast because the size of the first -/// reaching-definition analysis is proportional to the working-set size of -/// the function, which the compiler tries to keep small. (It's also -/// proportional to the number of blocks). Additionally, we repeatedly perform -/// the second reaching-definition analysis with only the variables and blocks -/// in a single lexical scope, exploiting their locality. -/// -/// Determining where PHIs happen is trickier with this approach, and it comes -/// to a head in the major problem for LiveDebugValues: is a value live-through -/// a loop, or not? Your garden-variety dataflow analysis aims to build a set of -/// facts about a function, however this analysis needs to generate new value -/// numbers at joins. -/// -/// To do this, consider a lattice of all definition values, from instructions -/// and from PHIs. Each PHI is characterised by the RPO number of the block it -/// occurs in. Each value pair A, B can be ordered by RPO(A) < RPO(B): -/// with non-PHI values at the top, and any PHI value in the last block (by RPO -/// order) at the bottom. -/// -/// (Awkwardly: lower-down-the _lattice_ means a greater RPO _number_. Below, -/// "rank" always refers to the former). -/// -/// At any join, for each register, we consider: -/// * All incoming values, and -/// * The PREVIOUS live-in value at this join. -/// If all incoming values agree: that's the live-in value. If they do not, the -/// incoming values are ranked according to the partial order, and the NEXT -/// LOWEST rank after the PREVIOUS live-in value is picked (multiple values of -/// the same rank are ignored as conflicting). If there are no candidate values, -/// or if the rank of the live-in would be lower than the rank of the current -/// blocks PHIs, create a new PHI value. -/// -/// Intuitively: if it's not immediately obvious what value a join should result -/// in, we iteratively descend from instruction-definitions down through PHI -/// values, getting closer to the current block each time. If the current block -/// is a loop head, this ordering is effectively searching outer levels of -/// loops, to find a value that's live-through the current loop. +/// another value), then re-compute an SSA-form representation of the +/// MachineFunction, using value propagation to eliminate any un-necessary +/// PHI values. This gives us a map of every value computed in the function, +/// and its location within the register file / stack. /// -/// If there is no value that's live-through this loop, a PHI is created for -/// this location instead. We can't use a lower-ranked PHI because by definition -/// it doesn't dominate the current block. We can't create a PHI value any -/// earlier, because we risk creating a PHI value at a location where values do -/// not in fact merge, thus misrepresenting the truth, and not making the true -/// live-through value for variable locations. +/// Secondly, for each variable we perform the same analysis, where each debug +/// instruction is considered a def, and every instruction where the variable +/// is in lexical scope as a use. Value propagation is used again to eliminate +/// any un-necessary PHIs. This gives us a map of each variable to the value +/// it should have in a block. /// -/// This algorithm applies to both calculating the availability of values in -/// the first analysis, and the location of variables in the second. However -/// for the second we add an extra dimension of pain: creating a variable -/// location PHI is only valid if, for each incoming edge, -/// * There is a value for the variable on the incoming edge, and -/// * All the edges have that value in the same register. -/// Or put another way: we can only create a variable-location PHI if there is -/// a matching machine-location PHI, each input to which is the variables value -/// in the predecessor block. +/// Once both are complete, we have two maps for each block: +/// * Variables to the values they should have, +/// * Values to the register / spill slot they are located in. +/// After which we can marry-up variable values with a location, and emit +/// DBG_VALUE instructions specifying those locations. Variable locations may +/// be dropped in this process due to the desired variable value not being +/// resident in any machine location, or because there is no PHI value in any +/// location that accurately represents the desired value. The building of +/// location lists for each block is left to DbgEntityHistoryCalculator. /// -/// To accommodate this difference, each point on the lattice is split in -/// two: a "proposed" PHI and "definite" PHI. Any PHI that can immediately -/// have a location determined are "definite" PHIs, and no further work is -/// needed. Otherwise, a location that all non-backedge predecessors agree -/// on is picked and propagated as a "proposed" PHI value. If that PHI value -/// is truly live-through, it'll appear on the loop backedges on the next -/// dataflow iteration, after which the block live-in moves to be a "definite" -/// PHI. If it's not truly live-through, the variable value will be downgraded -/// further as we explore the lattice, or remains "proposed" and is considered -/// invalid once dataflow completes. +/// This pass is kept efficient because the size of the first SSA problem +/// is proportional to the working-set size of the function, which the compiler +/// tries to keep small. (It's also proportional to the number of blocks). +/// Additionally, we repeatedly perform the second SSA problem analysis with +/// only the variables and blocks in a single lexical scope, exploiting their +/// locality. /// /// ### Terminology /// @@ -128,15 +62,13 @@ /// contain the appropriate variable value. A value that is a PHI node is /// occasionally called an mphi. /// -/// The first dataflow problem is the "machine value location" problem, +/// The first SSA problem is the "machine value location" problem, /// because we're determining which machine locations contain which values. /// The "locations" are constant: what's unknown is what value they contain. /// -/// The second dataflow problem (the one for variables) is the "variable value +/// The second SSA problem (the one for variables) is the "variable value /// problem", because it's determining what values a variable has, rather than -/// what location those values are placed in. Unfortunately, it's not that -/// simple, because producing a PHI value always involves picking a location. -/// This is an imperfection that we just have to accept, at least for now. +/// what location those values are placed in. /// /// TODO: /// Overlapping fragments @@ -153,9 +85,10 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/UniqueVector.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" #include "llvm/CodeGen/LexicalScopes.h" #include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -192,16 +125,18 @@ #include <cassert> #include <cstdint> #include <functional> +#include <limits.h> +#include <limits> #include <queue> #include <tuple> #include <utility> #include <vector> -#include <limits.h> -#include <limits> +#include "InstrRefBasedImpl.h" #include "LiveDebugValues.h" using namespace llvm; +using namespace LiveDebugValues; // SSAUpdaterImple sets DEBUG_TYPE, change it. #undef DEBUG_TYPE @@ -213,730 +148,6 @@ static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden, 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 { -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; -}; - -/// 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<ValueIDNum, LocIdxToIndexFunctor>; - - /// 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<LocIdx> LocIDToLocIdx; - - /// Inverse map of LocIDToLocIdx. - IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID; - - /// Unique-ification of spill slots. Used to number them -- their LocID - /// number is the index in SpillLocs minus one plus NumRegs. - UniqueVector<SpillLoc> 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<std::pair<const MachineOperand *, unsigned>, 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<ValueIDNum> 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<LocIdx> 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<MLocIterator> 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<LocIdx> MLoc, const DebugVariable &Var, - const DbgValueProperties &Properties) { - DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, - Var.getVariable()->getScope(), - const_cast<DILocation *>(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, RegState::Debug); - MIB.addReg(0, RegState::Debug); - } 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, RegState::Debug); - MIB.addImm(0); - } else { - unsigned LocID = LocIdxToLocID[*MLoc]; - MIB.addReg(LocID, RegState::Debug); - if (Properties.Indirect) - MIB.addImm(0); - else - MIB.addReg(0, RegState::Debug); - } - - 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<const DILocalVariable *, DIExpression::FragmentInfo>; -using OverlapMap = - DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>; - -/// 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 -/// identified. -class VLocTracker { -public: - /// Map DebugVariable to the latest Value it's defined to have. - /// Needs to be a MapVector because we determine order-in-the-input-MIR from - /// the order in this container. - /// We only retain the last DbgValue in each block for each variable, to - /// determine the blocks live-out variable value. The Vars container forms the - /// transfer function for this block, as part of the dataflow analysis. The - /// movement of values between locations inside of a block is handled at a - /// much later stage, in the TransferTracker class. - MapVector<DebugVariable, DbgValue> Vars; - DenseMap<DebugVariable, const DILocation *> Scopes; - MachineBasicBlock *MBB; - -public: - VLocTracker() {} - - void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, - Optional<ValueIDNum> ID) { - assert(MI.isDebugValue() || MI.isDebugRef()); - DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), - MI.getDebugLoc()->getInlinedAt()); - DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def) - : DbgValue(Properties, DbgValue::Undef); - - // Attempt insertion; overwrite if it's already mapped. - auto Result = Vars.insert(std::make_pair(Var, Rec)); - if (!Result.second) - Result.first->second = Rec; - Scopes[Var] = MI.getDebugLoc().get(); - } - - void defVar(const MachineInstr &MI, const MachineOperand &MO) { - // Only DBG_VALUEs can define constant-valued variables. - assert(MI.isDebugValue()); - DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(), - MI.getDebugLoc()->getInlinedAt()); - DbgValueProperties Properties(MI); - DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const); - - // Attempt insertion; overwrite if it's already mapped. - auto Result = Vars.insert(std::make_pair(Var, Rec)); - if (!Result.second) - Result.first->second = Rec; - Scopes[Var] = MI.getDebugLoc().get(); - } -}; - /// Tracker for converting machine value locations and variable values into /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs /// specifying block live-in locations and transfers within blocks. @@ -985,12 +196,12 @@ public: /// between TransferTrackers view of variable locations and MLocTrackers. For /// example, MLocTracker observes all clobbers, but TransferTracker lazily /// does not. - std::vector<ValueIDNum> VarLocs; + SmallVector<ValueIDNum, 32> VarLocs; /// Map from LocIdxes to which DebugVariables are based that location. /// Mantained while stepping through the block. Not accurate if /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx]. - std::map<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs; + DenseMap<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs; /// Map from DebugVariable to it's current location and qualifying meta /// information. To be used in conjunction with ActiveMLocs to construct @@ -1062,6 +273,8 @@ public: // Map of the preferred location for each value. std::map<ValueIDNum, LocIdx> ValueToLoc; + ActiveMLocs.reserve(VLocs.size()); + ActiveVLocs.reserve(VLocs.size()); // Produce a map of value numbers to the current machine locs they live // in. When emulating VarLocBasedImpl, there should only be one @@ -1088,7 +301,7 @@ public: for (auto Var : VLocs) { if (Var.second.Kind == DbgValue::Const) { PendingDbgValues.push_back( - emitMOLoc(Var.second.MO, Var.first, Var.second.Properties)); + emitMOLoc(*Var.second.MO, Var.first, Var.second.Properties)); continue; } @@ -1142,7 +355,7 @@ public: // instruction or similar with an instruction number, where it doesn't // actually define a new value, instead it moves a value. In case this // happens, discard. - if (MTracker->LocIdxToIDNum[L] != Use.ID) + if (MTracker->readMLoc(L) != Use.ID) continue; // If a different debug instruction defined the variable value / location @@ -1220,7 +433,6 @@ public: DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue); Register Reg = MTracker->LocIdxToLocID[Num.getLoc()]; MachineOperand MO = MachineOperand::CreateReg(Reg, false); - MO.setIsDebug(true); PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect})); return true; @@ -1274,12 +486,12 @@ public: // Check whether our local copy of values-by-location in #VarLocs is out of // date. Wipe old tracking data for the location if it's been clobbered in // the meantime. - if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) { + if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) { for (auto &P : ActiveMLocs[NewLoc]) { ActiveVLocs.erase(P); } ActiveMLocs[NewLoc.asU64()].clear(); - VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc); + VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc); } ActiveMLocs[NewLoc].insert(Var); @@ -1358,6 +570,8 @@ public: flushDbgValues(Pos, nullptr); + // Re-find ActiveMLocIt, iterator could have been invalidated. + ActiveMLocIt = ActiveMLocs.find(MLoc); ActiveMLocIt->second.clear(); } @@ -1367,21 +581,23 @@ public: void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) { // Does Src still contain the value num we expect? If not, it's been // clobbered in the meantime, and our variable locations are stale. - if (VarLocs[Src.asU64()] != MTracker->getNumAtPos(Src)) + if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src)) return; // assert(ActiveMLocs[Dst].size() == 0); //^^^ Legitimate scenario on account of un-clobbered slot being assigned to? - ActiveMLocs[Dst] = ActiveMLocs[Src]; + + // Move set of active variables from one location to another. + auto MovingVars = ActiveMLocs[Src]; + ActiveMLocs[Dst] = MovingVars; VarLocs[Dst.asU64()] = VarLocs[Src.asU64()]; // For each variable based on Src; create a location at Dst. - for (auto &Var : ActiveMLocs[Src]) { + for (auto &Var : MovingVars) { auto ActiveVLocIt = ActiveVLocs.find(Var); assert(ActiveVLocIt != ActiveVLocs.end()); ActiveVLocIt->second.Loc = Dst; - assert(Dst != 0); MachineInstr *MI = MTracker->emitLoc(Dst, Var, ActiveVLocIt->second.Properties); PendingDbgValues.push_back(MI); @@ -1413,306 +629,245 @@ public: } }; -class InstrRefBasedLDV : public LDVImpl { -private: - using FragmentInfo = DIExpression::FragmentInfo; - using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; - - // Helper while building OverlapMap, a map of all fragments seen for a given - // DILocalVariable. - using VarToFragments = - DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; - - /// Machine location/value transfer function, a mapping of which locations - /// are assigned which new values. - using MLocTransferMap = std::map<LocIdx, ValueIDNum>; - - /// Live in/out structure for the variable values: a per-block map of - /// variables to their values. XXX, better name? - using LiveIdxT = - DenseMap<const MachineBasicBlock *, DenseMap<DebugVariable, DbgValue> *>; - - using VarAndLoc = std::pair<DebugVariable, DbgValue>; - - /// Type for a live-in value: the predecessor block, and its value. - using InValueT = std::pair<MachineBasicBlock *, DbgValue *>; - - /// 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<SmallVector<VarAndLoc, 8>, 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; +//===----------------------------------------------------------------------===// +// Implementation +//===----------------------------------------------------------------------===// - /// Number of the current block LiveDebugValues is stepping through. - unsigned CurBB; +ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX}; +ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1}; - /// Number of the current instruction LiveDebugValues is evaluating. - unsigned CurInst; +#ifndef NDEBUG +void DbgValue::dump(const MLocTracker *MTrack) const { + if (Kind == Const) { + MO->dump(); + } else if (Kind == NoVal) { + dbgs() << "NoVal(" << BlockNo << ")"; + } else if (Kind == VPHI) { + dbgs() << "VPHI(" << BlockNo << "," << MTrack->IDAsString(ID) << ")"; + } else { + assert(Kind == Def); + dbgs() << MTrack->IDAsString(ID); + } + if (Properties.Indirect) + dbgs() << " indir"; + if (Properties.DIExpr) + dbgs() << " " << *Properties.DIExpr; +} +#endif - /// 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; +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); + (void)lookupOrTrackRegister(ID); + + for (MCRegAliasIterator RAI(SP, &TRI, true); RAI.isValid(); ++RAI) + SPAliases.insert(*RAI); + } + + // Build some common stack positions -- full registers being spilt to the + // stack. + StackSlotIdxes.insert({{8, 0}, 0}); + StackSlotIdxes.insert({{16, 0}, 1}); + StackSlotIdxes.insert({{32, 0}, 2}); + StackSlotIdxes.insert({{64, 0}, 3}); + StackSlotIdxes.insert({{128, 0}, 4}); + StackSlotIdxes.insert({{256, 0}, 5}); + StackSlotIdxes.insert({{512, 0}, 6}); + + // Traverse all the subregister idxes, and ensure there's an index for them. + // Duplicates are no problem: we're interested in their position in the + // stack slot, we don't want to type the slot. + for (unsigned int I = 1; I < TRI.getNumSubRegIndices(); ++I) { + unsigned Size = TRI.getSubRegIdxSize(I); + unsigned Offs = TRI.getSubRegIdxOffset(I); + unsigned Idx = StackSlotIdxes.size(); + + // Some subregs have -1, -2 and so forth fed into their fields, to mean + // special backend things. Ignore those. + if (Size > 60000 || Offs > 60000) + continue; - /// 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; + StackSlotIdxes.insert({{Size, Offs}, Idx}); + } - /// Blocks which are artificial, i.e. blocks which exclusively contain - /// instructions without DebugLocs, or with line 0 locations. - SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; + for (auto &Idx : StackSlotIdxes) + StackIdxesToPos[Idx.second] = Idx.first; - // Mapping of blocks to and from their RPOT order. - DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; - DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; - DenseMap<unsigned, unsigned> BBNumToRPO; + NumSlotIdxes = StackSlotIdxes.size(); +} - /// Pair of MachineInstr, and its 1-based offset into the containing block. - using InstAndNum = std::pair<const MachineInstr *, unsigned>; - /// 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<uint64_t, InstAndNum> 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) { + // 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 && !SPAliases.count(ID) && 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<DebugPHIRecord, 32> 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<SpillLoc> 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<ValueIDNum> 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<MLocTransferMap> &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<MLocTransferMap> &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<bool, bool> - mlocJoin(MachineBasicBlock &MBB, - SmallPtrSet<const MachineBasicBlock *, 16> &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<DebugVariable, 4> &VarsWeCareAbout, - SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, - LiveInsT &Output, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, - SmallVectorImpl<VLocTracker> &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<bool, bool> - vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, - SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, - unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars, - ValueIDNum **MOutLocs, ValueIDNum **MInLocs, - SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, - SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, - DenseMap<DebugVariable, DbgValue> &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<InValueT> &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<Optional<ValueIDNum>, bool> - pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var, - const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, - const SmallVectorImpl<MachineBasicBlock *> &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<DebugVariable, unsigned> &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) override; +SpillLocationNo MLocTracker::getOrTrackSpillLoc(SpillLoc L) { + SpillLocationNo SpillID(SpillLocs.idFor(L)); + if (SpillID.id() == 0) { + // Spill location is untracked: create record for this one, and all + // subregister slots too. + SpillID = SpillLocationNo(SpillLocs.insert(L)); + for (unsigned StackIdx = 0; StackIdx < NumSlotIdxes; ++StackIdx) { + unsigned L = getSpillIDWithIdx(SpillID, StackIdx); + LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx + LocIdxToIDNum.grow(Idx); + LocIdxToLocID.grow(Idx); + LocIDToLocIdx.push_back(Idx); + LocIdxToLocID[Idx] = L; + // Initialize to PHI value; corresponds to the location's live-in value + // during transfer function construction. + LocIdxToIDNum[Idx] = ValueIDNum(CurBB, 0, Idx); + } + } + return SpillID; +} -public: - /// Default construct and initialize the pass. - InstrRefBasedLDV(); +std::string MLocTracker::LocIdxToName(LocIdx Idx) const { + unsigned ID = LocIdxToLocID[Idx]; + if (ID >= NumRegs) { + StackSlotPos Pos = locIDToSpillIdx(ID); + ID -= NumRegs; + unsigned Slot = ID / NumSlotIdxes; + return Twine("slot ") + .concat(Twine(Slot).concat(Twine(" sz ").concat(Twine(Pos.first) + .concat(Twine(" offs ").concat(Twine(Pos.second)))))) + .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; +#ifndef NDEBUG +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"; + } +} +#endif -//===----------------------------------------------------------------------===// -// Implementation -//===----------------------------------------------------------------------===// +MachineInstrBuilder MLocTracker::emitLoc(Optional<LocIdx> MLoc, + const DebugVariable &Var, + const DbgValueProperties &Properties) { + DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0, + Var.getVariable()->getScope(), + const_cast<DILocation *>(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]; + SpillLocationNo SpillID = locIDToSpill(LocID); + StackSlotPos StackIdx = locIDToSpillIdx(LocID); + unsigned short Offset = StackIdx.second; + + // TODO: support variables that are located in spill slots, with non-zero + // offsets from the start of the spill slot. It would require some more + // complex DIExpression calculations. This doesn't seem to be produced by + // LLVM right now, so don't try and support it. + // Accept no-subregister slots and subregisters where the offset is zero. + // The consumer should already have type information to work out how large + // the variable is. + if (Offset == 0) { + const SpillLoc &Spill = SpillLocs[SpillID.id()]; + Expr = TRI.prependOffsetExpression(Expr, DIExpression::ApplyOffset, + Spill.SpillOffset); + unsigned Base = Spill.SpillBase; + MIB.addReg(Base); + MIB.addImm(0); + } else { + // This is a stack location with a weird subregister offset: emit an undef + // DBG_VALUE instead. + MIB.addReg(0); + MIB.addReg(0); + } + } else { + // Non-empty, non-stack slot, must be a plain register. + 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 //===----------------------------------------------------------------------===// @@ -1722,7 +877,7 @@ InstrRefBasedLDV::InstrRefBasedLDV() {} // void InstrRefBasedLDV::printVarLocInMBB(..) #endif -SpillLoc +SpillLocationNo InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { assert(MI.hasOneMemOperand() && "Spill instruction does not have exactly one memory operand?"); @@ -1734,7 +889,28 @@ InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { const MachineBasicBlock *MBB = MI.getParent(); Register Reg; StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); - return {Reg, Offset}; + return MTracker->getOrTrackSpillLoc({Reg, Offset}); +} + +Optional<LocIdx> InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) { + SpillLocationNo SpillLoc = extractSpillBaseRegAndOffset(MI); + + // Where in the stack slot is this value defined -- i.e., what size of value + // is this? An important question, because it could be loaded into a register + // from the stack at some point. Happily the memory operand will tell us + // the size written to the stack. + auto *MemOperand = *MI.memoperands_begin(); + unsigned SizeInBits = MemOperand->getSizeInBits(); + + // Find that position in the stack indexes we're tracking. + auto IdxIt = MTracker->StackSlotIdxes.find({SizeInBits, 0}); + if (IdxIt == MTracker->StackSlotIdxes.end()) + // That index is not tracked. This is suprising, and unlikely to ever + // occur, but the safe action is to indicate the variable is optimised out. + return None; + + unsigned SpillID = MTracker->getSpillIDWithIdx(SpillLoc, IdxIt->second); + return MTracker->getSpillMLoc(SpillID); } /// End all previous ranges related to @MI and start a new range from @MI @@ -1759,6 +935,17 @@ bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) { if (Scope == nullptr) return true; // handled it; by doing nothing + // For now, ignore DBG_VALUE_LISTs when extending ranges. Allow it to + // contribute to locations in this block, but don't propagate further. + // Interpret it like a DBG_VALUE $noreg. + if (MI.isDebugValueList()) { + if (VTracker) + VTracker->defVar(MI, Properties, None); + if (TTracker) + TTracker->redefVar(MI, Properties, None); + return true; + } + const MachineOperand &MO = MI.getOperand(0); // MLocTracker needs to know that this register is read, even if it's only @@ -1852,16 +1039,25 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, const MachineInstr &TargetInstr = *InstrIt->second.first; uint64_t BlockNo = TargetInstr.getParent()->getNumber(); - // Pick out the designated operand. - assert(OpNo < TargetInstr.getNumOperands()); - const MachineOperand &MO = TargetInstr.getOperand(OpNo); - - // Today, this can only be a register. - assert(MO.isReg() && MO.isDef()); - - unsigned LocID = MTracker->getLocID(MO.getReg(), false); - LocIdx L = MTracker->LocIDToLocIdx[LocID]; - NewID = ValueIDNum(BlockNo, InstrIt->second.second, L); + // Pick out the designated operand. It might be a memory reference, if + // a register def was folded into a stack store. + if (OpNo == MachineFunction::DebugOperandMemNumber && + TargetInstr.hasOneMemOperand()) { + Optional<LocIdx> L = findLocationForMemOperand(TargetInstr); + if (L) + NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L); + } else if (OpNo != MachineFunction::DebugOperandMemNumber) { + assert(OpNo < TargetInstr.getNumOperands()); + const MachineOperand &MO = TargetInstr.getOperand(OpNo); + + // Today, this can only be a register. + assert(MO.isReg() && MO.isDef()); + + unsigned LocID = MTracker->getLocID(MO.getReg()); + LocIdx L = MTracker->LocIDToLocIdx[LocID]; + NewID = ValueIDNum(BlockNo, InstrIt->second.second, L); + } + // else: NewID is left as None. } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) { // It's actually a PHI value. Which value it is might not be obvious, use // the resolver helper to find out. @@ -1957,7 +1153,7 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI, Optional<LocIdx> FoundLoc = None; for (auto Location : MTracker->locations()) { LocIdx CurL = Location.Idx; - ValueIDNum ID = MTracker->LocIdxToIDNum[CurL]; + ValueIDNum ID = MTracker->readMLoc(CurL); if (NewID && ID == NewID) { // If this is the first location with that value, pick it. Otherwise, // consider whether it's a "longer term" location. @@ -2016,6 +1212,10 @@ bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { auto PHIRec = DebugPHIRecord( {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)}); DebugPHINumToValue.push_back(PHIRec); + + // Ensure this register is tracked. + for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) + MTracker->lookupOrTrackRegister(*RAI); } else { // The value is whatever's in this stack slot. assert(MO.isFI()); @@ -2026,19 +1226,46 @@ bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) { if (MFI->isDeadObjectIndex(FI)) return true; - // Identify this spill slot. + // Identify this spill slot, ensure it's tracked. Register Base; StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base); SpillLoc SL = {Base, Offs}; - Optional<ValueIDNum> Num = MTracker->readSpill(SL); + SpillLocationNo SpillNo = MTracker->getOrTrackSpillLoc(SL); + + // Problem: what value should we extract from the stack? LLVM does not + // record what size the last store to the slot was, and it would become + // sketchy after stack slot colouring anyway. Take a look at what values + // are stored on the stack, and pick the largest one that wasn't def'd + // by a spill (i.e., the value most likely to have been def'd in a register + // and then spilt. + std::array<unsigned, 4> CandidateSizes = {64, 32, 16, 8}; + Optional<ValueIDNum> Result = None; + Optional<LocIdx> SpillLoc = None; + for (unsigned int I = 0; I < CandidateSizes.size(); ++I) { + unsigned SpillID = MTracker->getLocID(SpillNo, {CandidateSizes[I], 0}); + SpillLoc = MTracker->getSpillMLoc(SpillID); + ValueIDNum Val = MTracker->readMLoc(*SpillLoc); + // If this value was defined in it's own position, then it was probably + // an aliasing index of a small value that was spilt. + if (Val.getLoc() != SpillLoc->asU64()) { + Result = Val; + break; + } + } - if (!Num) - // Nothing ever writes to this slot. Curious, but nothing we can do. - return true; + // If we didn't find anything, we're probably looking at a PHI, or a memory + // store folded into an instruction. FIXME: Take a guess that's it's 64 + // bits. This isn't ideal, but tracking the size that the spill is + // "supposed" to be is more complex, and benefits a small number of + // locations. + if (!Result) { + unsigned SpillID = MTracker->getLocID(SpillNo, {64, 0}); + SpillLoc = MTracker->getSpillMLoc(SpillID); + Result = MTracker->readMLoc(*SpillLoc); + } // Record this DBG_PHI for later analysis. - auto DbgPHI = DebugPHIRecord( - {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)}); + auto DbgPHI = DebugPHIRecord({InstrNum, MI.getParent(), *Result, *SpillLoc}); DebugPHINumToValue.push_back(DbgPHI); } @@ -2061,10 +1288,6 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { } else if (MI.isMetaInstruction()) return; - MachineFunction *MF = MI.getMF(); - const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); - Register SP = TLI->getStackPointerRegisterToSaveRestore(); - // Find the regs killed by MI, and find regmasks of preserved regs. // Max out the number of statically allocated elements in `DeadRegs`, as this // prevents fallback to std::set::count() operations. @@ -2075,7 +1298,7 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { // Determine whether the operand is a register def. if (MO.isReg() && MO.isDef() && MO.getReg() && Register::isPhysicalRegister(MO.getReg()) && - !(MI.isCall() && MO.getReg() == SP)) { + !(MI.isCall() && MTracker->SPAliases.count(MO.getReg()))) { // Remove ranges of all aliased registers. for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) // FIXME: Can we break out of this loop early if no insertion occurs? @@ -2093,6 +1316,16 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { for (auto *MO : RegMaskPtrs) MTracker->writeRegMask(MO, CurBB, CurInst); + // If this instruction writes to a spill slot, def that slot. + if (hasFoldedStackStore(MI)) { + SpillLocationNo SpillNo = extractSpillBaseRegAndOffset(MI); + for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) { + unsigned SpillID = MTracker->getSpillIDWithIdx(SpillNo, I); + LocIdx L = MTracker->getSpillMLoc(SpillID); + MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L)); + } + } + if (!TTracker) return; @@ -2118,32 +1351,27 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) { if (MO->clobbersPhysReg(Reg)) TTracker->clobberMloc(L.Idx, MI.getIterator(), false); } + + // Tell TTracker about any folded stack store. + if (hasFoldedStackStore(MI)) { + SpillLocationNo SpillNo = extractSpillBaseRegAndOffset(MI); + for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) { + unsigned SpillID = MTracker->getSpillIDWithIdx(SpillNo, I); + LocIdx L = MTracker->getSpillMLoc(SpillID); + TTracker->clobberMloc(L, MI.getIterator(), true); + } + } } void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { - ValueIDNum SrcValue = MTracker->readReg(SrcRegNum); + // In all circumstances, re-def all aliases. It's definitely a new value now. + for (MCRegAliasIterator RAI(DstRegNum, TRI, true); RAI.isValid(); ++RAI) + MTracker->defReg(*RAI, CurBB, CurInst); + ValueIDNum SrcValue = MTracker->readReg(SrcRegNum); MTracker->setReg(DstRegNum, SrcValue); - // In all circumstances, re-def the super registers. It's definitely a new - // value now. This doesn't uniquely identify the composition of subregs, for - // example, two identical values in subregisters composed in different - // places would not get equal value numbers. - for (MCSuperRegIterator SRI(DstRegNum, TRI); SRI.isValid(); ++SRI) - MTracker->defReg(*SRI, CurBB, CurInst); - - // If we're emulating VarLocBasedImpl, just define all the subregisters. - // DBG_VALUEs of them will expect to be tracked from the DBG_VALUE, not - // through prior copies. - if (EmulateOldLDV) { - for (MCSubRegIndexIterator DRI(DstRegNum, TRI); DRI.isValid(); ++DRI) - MTracker->defReg(DRI.getSubReg(), CurBB, CurInst); - return; - } - - // Otherwise, actually copy subregisters from one location to another. - // XXX: in addition, any subregisters of DstRegNum that don't line up with - // the source register should be def'd. + // Copy subregisters from one location to another. for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) { unsigned SrcSubReg = SRI.getSubReg(); unsigned SubRegIdx = SRI.getSubRegIndex(); @@ -2154,15 +1382,13 @@ void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) { // Do copy. There are two matching subregisters, the source value should // have been def'd when the super-reg was, the latter might not be tracked // yet. - // This will force SrcSubReg to be tracked, if it isn't yet. - (void)MTracker->readReg(SrcSubReg); - LocIdx SrcL = MTracker->getRegMLoc(SrcSubReg); - assert(SrcL.asU64()); - (void)MTracker->readReg(DstSubReg); - LocIdx DstL = MTracker->getRegMLoc(DstSubReg); - assert(DstL.asU64()); + // This will force SrcSubReg to be tracked, if it isn't yet. Will read + // mphi values if it wasn't tracked. + LocIdx SrcL = MTracker->lookupOrTrackRegister(SrcSubReg); + LocIdx DstL = MTracker->lookupOrTrackRegister(DstSubReg); + (void)SrcL; (void)DstL; - ValueIDNum CpyValue = {SrcValue.getBlock(), SrcValue.getInst(), SrcL}; + ValueIDNum CpyValue = MTracker->readReg(SrcSubReg); MTracker->setReg(DstSubReg, CpyValue); } @@ -2174,6 +1400,12 @@ bool InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI, if (!MI.hasOneMemOperand()) return false; + // Reject any memory operand that's aliased -- we can't guarantee its value. + auto MMOI = MI.memoperands_begin(); + const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); + if (PVal->isAliased(MFI)) + return false; + if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) return false; // This is not a spill instruction, since no valid size was // returned from either function. @@ -2191,7 +1423,7 @@ bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI, return Reg != 0; } -Optional<SpillLoc> +Optional<SpillLocationNo> InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI, MachineFunction *MF, unsigned &Reg) { if (!MI.hasOneMemOperand()) @@ -2213,84 +1445,117 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) { if (EmulateOldLDV) return false; + // Strictly limit ourselves to plain loads and stores, not all instructions + // that can access the stack. + int DummyFI = -1; + if (!TII->isStoreToStackSlotPostFE(MI, DummyFI) && + !TII->isLoadFromStackSlotPostFE(MI, DummyFI)) + return false; + MachineFunction *MF = MI.getMF(); unsigned Reg; - Optional<SpillLoc> Loc; LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); + // Strictly limit ourselves to plain loads and stores, not all instructions + // that can access the stack. + int FIDummy; + if (!TII->isStoreToStackSlotPostFE(MI, FIDummy) && + !TII->isLoadFromStackSlotPostFE(MI, FIDummy)) + return false; + // First, if there are any DBG_VALUEs pointing at a spill slot that is // written to, terminate that variable location. The value in memory // will have changed. DbgEntityHistoryCalculator doesn't try to detect this. if (isSpillInstruction(MI, MF)) { - Loc = extractSpillBaseRegAndOffset(MI); - - if (TTracker) { - Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc); - if (MLoc) { - // Un-set this location before clobbering, so that we don't salvage - // the variable location back to the same place. - MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue); + SpillLocationNo Loc = extractSpillBaseRegAndOffset(MI); + + // Un-set this location and clobber, so that earlier locations don't + // continue past this store. + for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) { + unsigned SpillID = MTracker->getSpillIDWithIdx(Loc, SlotIdx); + Optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID); + if (!MLoc) + continue; + + // We need to over-write the stack slot with something (here, a def at + // this instruction) to ensure no values are preserved in this stack slot + // after the spill. It also prevents TTracker from trying to recover the + // location and re-installing it in the same place. + ValueIDNum Def(CurBB, CurInst, *MLoc); + MTracker->setMLoc(*MLoc, Def); + if (TTracker) TTracker->clobberMloc(*MLoc, MI.getIterator()); - } } } // Try to recognise spill and restore instructions that may transfer a value. if (isLocationSpill(MI, MF, Reg)) { - Loc = extractSpillBaseRegAndOffset(MI); - auto ValueID = MTracker->readReg(Reg); + SpillLocationNo Loc = extractSpillBaseRegAndOffset(MI); - // If the location is empty, produce a phi, signify it's the live-in value. - if (ValueID.getLoc() == 0) - ValueID = {CurBB, 0, MTracker->getRegMLoc(Reg)}; + auto DoTransfer = [&](Register SrcReg, unsigned SpillID) { + auto ReadValue = MTracker->readReg(SrcReg); + LocIdx DstLoc = MTracker->getSpillMLoc(SpillID); + MTracker->setMLoc(DstLoc, ReadValue); + + if (TTracker) { + LocIdx SrcLoc = MTracker->getRegMLoc(SrcReg); + TTracker->transferMlocs(SrcLoc, DstLoc, MI.getIterator()); + } + }; - MTracker->setSpill(*Loc, ValueID); - auto OptSpillLocIdx = MTracker->getSpillMLoc(*Loc); - assert(OptSpillLocIdx && "Spill slot set but has no LocIdx?"); - LocIdx SpillLocIdx = *OptSpillLocIdx; + // Then, transfer subreg bits. + for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) { + // Ensure this reg is tracked, + (void)MTracker->lookupOrTrackRegister(*SRI); + unsigned SubregIdx = TRI->getSubRegIndex(Reg, *SRI); + unsigned SpillID = MTracker->getLocID(Loc, SubregIdx); + DoTransfer(*SRI, SpillID); + } - // Tell TransferTracker about this spill, produce DBG_VALUEs for it. - if (TTracker) - TTracker->transferMlocs(MTracker->getRegMLoc(Reg), SpillLocIdx, - MI.getIterator()); + // Directly lookup size of main source reg, and transfer. + unsigned Size = TRI->getRegSizeInBits(Reg, *MRI); + unsigned SpillID = MTracker->getLocID(Loc, {Size, 0}); + DoTransfer(Reg, SpillID); } else { - if (!(Loc = isRestoreInstruction(MI, MF, Reg))) + Optional<SpillLocationNo> OptLoc = isRestoreInstruction(MI, MF, Reg); + if (!OptLoc) return false; + SpillLocationNo Loc = *OptLoc; - // Is there a value to be restored? - auto OptValueID = MTracker->readSpill(*Loc); - if (OptValueID) { - ValueIDNum ValueID = *OptValueID; - LocIdx SpillLocIdx = *MTracker->getSpillMLoc(*Loc); - // XXX -- can we recover sub-registers of this value? Until we can, first - // overwrite all defs of the register being restored to. - for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) - MTracker->defReg(*RAI, CurBB, CurInst); + // Assumption: we're reading from the base of the stack slot, not some + // offset into it. It seems very unlikely LLVM would ever generate + // restores where this wasn't true. This then becomes a question of what + // subregisters in the destination register line up with positions in the + // stack slot. - // Now override the reg we're restoring to. - MTracker->setReg(Reg, ValueID); + // Def all registers that alias the destination. + for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) + MTracker->defReg(*RAI, CurBB, CurInst); + + // Now find subregisters within the destination register, and load values + // from stack slot positions. + auto DoTransfer = [&](Register DestReg, unsigned SpillID) { + LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID); + auto ReadValue = MTracker->readMLoc(SrcIdx); + MTracker->setReg(DestReg, ReadValue); + + if (TTracker) { + LocIdx DstLoc = MTracker->getRegMLoc(DestReg); + TTracker->transferMlocs(SrcIdx, DstLoc, MI.getIterator()); + } + }; - // Report this restore to the transfer tracker too. - if (TTracker) - TTracker->transferMlocs(SpillLocIdx, MTracker->getRegMLoc(Reg), - MI.getIterator()); - } else { - // There isn't anything in the location; not clear if this is a code path - // that still runs. Def this register anyway just in case. - for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) - MTracker->defReg(*RAI, CurBB, CurInst); - - // Force the spill slot to be tracked. - LocIdx L = MTracker->getOrTrackSpillLoc(*Loc); - - // Set the restored value to be a machine phi number, signifying that it's - // whatever the spills live-in value is in this block. Definitely has - // a LocIdx due to the setSpill above. - ValueIDNum ValueID = {CurBB, 0, L}; - MTracker->setReg(Reg, ValueID); - MTracker->setSpill(*Loc, ValueID); + for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) { + unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI); + unsigned SpillID = MTracker->getLocID(Loc, Subreg); + DoTransfer(*SRI, SpillID); } + + // Directly look up this registers slot idx by size, and transfer. + unsigned Size = TRI->getRegSizeInBits(Reg, *MRI); + unsigned SpillID = MTracker->getLocID(Loc, {Size, 0}); + DoTransfer(Reg, SpillID); } return true; } @@ -2510,12 +1775,11 @@ void InstrRefBasedLDV::produceMLocTransferFunction( } // Compute a bitvector of all the registers that are tracked in this block. - const TargetLowering *TLI = MF.getSubtarget().getTargetLowering(); - Register SP = TLI->getStackPointerRegisterToSaveRestore(); BitVector UsedRegs(TRI->getNumRegs()); for (auto Location : MTracker->locations()) { unsigned ID = MTracker->LocIdxToLocID[Location.Idx]; - if (ID >= TRI->getNumRegs() || ID == SP) + // Ignore stack slots, and aliases of the stack pointer. + if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID)) continue; UsedRegs.set(ID); } @@ -2531,7 +1795,7 @@ void InstrRefBasedLDV::produceMLocTransferFunction( // they're all clobbered or at least set in the designated transfer // elem. for (unsigned Bit : BV.set_bits()) { - unsigned ID = MTracker->getLocID(Bit, false); + unsigned ID = MTracker->getLocID(Bit); LocIdx Idx = MTracker->LocIDToLocIdx[ID]; auto &TransferMap = MLocTransfer[I]; @@ -2553,23 +1817,20 @@ void InstrRefBasedLDV::produceMLocTransferFunction( } } -std::tuple<bool, bool> -InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB, - SmallPtrSet<const MachineBasicBlock *, 16> &Visited, - ValueIDNum **OutLocs, ValueIDNum *InLocs) { +bool InstrRefBasedLDV::mlocJoin( + MachineBasicBlock &MBB, SmallPtrSet<const MachineBasicBlock *, 16> &Visited, + ValueIDNum **OutLocs, ValueIDNum *InLocs) { LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); bool Changed = false; - bool DowngradeOccurred = false; - // Collect predecessors that have been visited. Anything that hasn't been - // visited yet is a backedge on the first iteration, and the meet of it's - // lattice value for all locations will be unaffected. + // Handle value-propagation when control flow merges on entry to a block. For + // any location without a PHI already placed, the location has the same value + // as its predecessors. If a PHI is placed, test to see whether it's now a + // redundant PHI that we can eliminate. + SmallVector<const MachineBasicBlock *, 8> BlockOrders; - for (auto Pred : MBB.predecessors()) { - if (Visited.count(Pred)) { - BlockOrders.push_back(Pred); - } - } + for (auto Pred : MBB.predecessors()) + BlockOrders.push_back(Pred); // Visit predecessors in RPOT order. auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { @@ -2579,83 +1840,216 @@ InstrRefBasedLDV::mlocJoin(MachineBasicBlock &MBB, // Skip entry block. if (BlockOrders.size() == 0) - return std::tuple<bool, bool>(false, false); + return false; - // Step through all machine locations, then look at each predecessor and - // detect disagreements. - unsigned ThisBlockRPO = BBToOrder.find(&MBB)->second; + // Step through all machine locations, look at each predecessor and test + // whether we can eliminate redundant PHIs. for (auto Location : MTracker->locations()) { LocIdx Idx = Location.Idx; + // Pick out the first predecessors live-out value for this location. It's - // guaranteed to be not a backedge, as we order by RPO. - ValueIDNum BaseVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()]; + // guaranteed to not be a backedge, as we order by RPO. + ValueIDNum FirstVal = OutLocs[BlockOrders[0]->getNumber()][Idx.asU64()]; + + // If we've already eliminated a PHI here, do no further checking, just + // propagate the first live-in value into this block. + if (InLocs[Idx.asU64()] != ValueIDNum(MBB.getNumber(), 0, Idx)) { + if (InLocs[Idx.asU64()] != FirstVal) { + InLocs[Idx.asU64()] = FirstVal; + Changed |= true; + } + continue; + } - // Some flags for whether there's a disagreement, and whether it's a - // disagreement with a backedge or not. + // We're now examining a PHI to see whether it's un-necessary. Loop around + // the other live-in values and test whether they're all the same. bool Disagree = false; - bool NonBackEdgeDisagree = false; - - // Loop around everything that wasn't 'base'. for (unsigned int I = 1; I < BlockOrders.size(); ++I) { - auto *MBB = BlockOrders[I]; - if (BaseVal != OutLocs[MBB->getNumber()][Idx.asU64()]) { - // Live-out of a predecessor disagrees with the first predecessor. - Disagree = true; - - // Test whether it's a disagreemnt in the backedges or not. - if (BBToOrder.find(MBB)->second < ThisBlockRPO) // might be self b/e - NonBackEdgeDisagree = true; - } - } + const MachineBasicBlock *PredMBB = BlockOrders[I]; + const ValueIDNum &PredLiveOut = + OutLocs[PredMBB->getNumber()][Idx.asU64()]; - bool OverRide = false; - if (Disagree && !NonBackEdgeDisagree) { - // Only the backedges disagree. Consider demoting the livein - // lattice value, as per the file level comment. The value we consider - // demoting to is the value that the non-backedge predecessors agree on. - // The order of values is that non-PHIs are \top, a PHI at this block - // \bot, and phis between the two are ordered by their RPO number. - // If there's no agreement, or we've already demoted to this PHI value - // before, replace with a PHI value at this block. - - // Calculate order numbers: zero means normal def, nonzero means RPO - // number. - unsigned BaseBlockRPONum = BBNumToRPO[BaseVal.getBlock()] + 1; - if (!BaseVal.isPHI()) - BaseBlockRPONum = 0; - - ValueIDNum &InLocID = InLocs[Idx.asU64()]; - unsigned InLocRPONum = BBNumToRPO[InLocID.getBlock()] + 1; - if (!InLocID.isPHI()) - InLocRPONum = 0; - - // Should we ignore the disagreeing backedges, and override with the - // value the other predecessors agree on (in "base")? - unsigned ThisBlockRPONum = BBNumToRPO[MBB.getNumber()] + 1; - if (BaseBlockRPONum > InLocRPONum && BaseBlockRPONum < ThisBlockRPONum) { - // Override. - OverRide = true; - DowngradeOccurred = true; - } + // Incoming values agree, continue trying to eliminate this PHI. + if (FirstVal == PredLiveOut) + continue; + + // We can also accept a PHI value that feeds back into itself. + if (PredLiveOut == ValueIDNum(MBB.getNumber(), 0, Idx)) + continue; + + // Live-out of a predecessor disagrees with the first predecessor. + Disagree = true; } - // else: if we disagree in the non-backedges, then this is definitely - // a control flow merge where different values merge. Make it a PHI. - // Generate a phi... - ValueIDNum PHI = {(uint64_t)MBB.getNumber(), 0, Idx}; - ValueIDNum NewVal = (Disagree && !OverRide) ? PHI : BaseVal; - if (InLocs[Idx.asU64()] != NewVal) { + // No disagreement? No PHI. Otherwise, leave the PHI in live-ins. + if (!Disagree) { + InLocs[Idx.asU64()] = FirstVal; Changed |= true; - InLocs[Idx.asU64()] = NewVal; } } // TODO: Reimplement NumInserted and NumRemoved. - return std::tuple<bool, bool>(Changed, DowngradeOccurred); + return Changed; +} + +void InstrRefBasedLDV::findStackIndexInterference( + SmallVectorImpl<unsigned> &Slots) { + // We could spend a bit of time finding the exact, minimal, set of stack + // indexes that interfere with each other, much like reg units. Or, we can + // rely on the fact that: + // * The smallest / lowest index will interfere with everything at zero + // offset, which will be the largest set of registers, + // * Most indexes with non-zero offset will end up being interference units + // anyway. + // So just pick those out and return them. + + // We can rely on a single-byte stack index existing already, because we + // initialize them in MLocTracker. + auto It = MTracker->StackSlotIdxes.find({8, 0}); + assert(It != MTracker->StackSlotIdxes.end()); + Slots.push_back(It->second); + + // Find anything that has a non-zero offset and add that too. + for (auto &Pair : MTracker->StackSlotIdxes) { + // Is offset zero? If so, ignore. + if (!Pair.first.second) + continue; + Slots.push_back(Pair.second); + } } -void InstrRefBasedLDV::mlocDataflow( - ValueIDNum **MInLocs, ValueIDNum **MOutLocs, +void InstrRefBasedLDV::placeMLocPHIs( + MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks, + ValueIDNum **MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) { + SmallVector<unsigned, 4> StackUnits; + findStackIndexInterference(StackUnits); + + // To avoid repeatedly running the PHI placement algorithm, leverage the + // fact that a def of register MUST also def its register units. Find the + // units for registers, place PHIs for them, and then replicate them for + // aliasing registers. Some inputs that are never def'd (DBG_PHIs of + // arguments) don't lead to register units being tracked, just place PHIs for + // those registers directly. Stack slots have their own form of "unit", + // store them to one side. + SmallSet<Register, 32> RegUnitsToPHIUp; + SmallSet<LocIdx, 32> NormalLocsToPHI; + SmallSet<SpillLocationNo, 32> StackSlots; + for (auto Location : MTracker->locations()) { + LocIdx L = Location.Idx; + if (MTracker->isSpill(L)) { + StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L])); + continue; + } + + Register R = MTracker->LocIdxToLocID[L]; + SmallSet<Register, 8> FoundRegUnits; + bool AnyIllegal = false; + for (MCRegUnitIterator RUI(R.asMCReg(), TRI); RUI.isValid(); ++RUI) { + for (MCRegUnitRootIterator URoot(*RUI, TRI); URoot.isValid(); ++URoot){ + if (!MTracker->isRegisterTracked(*URoot)) { + // Not all roots were loaded into the tracking map: this register + // isn't actually def'd anywhere, we only read from it. Generate PHIs + // for this reg, but don't iterate units. + AnyIllegal = true; + } else { + FoundRegUnits.insert(*URoot); + } + } + } + + if (AnyIllegal) { + NormalLocsToPHI.insert(L); + continue; + } + + RegUnitsToPHIUp.insert(FoundRegUnits.begin(), FoundRegUnits.end()); + } + + // Lambda to fetch PHIs for a given location, and write into the PHIBlocks + // collection. + SmallVector<MachineBasicBlock *, 32> PHIBlocks; + auto CollectPHIsForLoc = [&](LocIdx L) { + // Collect the set of defs. + SmallPtrSet<MachineBasicBlock *, 32> DefBlocks; + for (unsigned int I = 0; I < OrderToBB.size(); ++I) { + MachineBasicBlock *MBB = OrderToBB[I]; + const auto &TransferFunc = MLocTransfer[MBB->getNumber()]; + if (TransferFunc.find(L) != TransferFunc.end()) + DefBlocks.insert(MBB); + } + + // The entry block defs the location too: it's the live-in / argument value. + // Only insert if there are other defs though; everything is trivially live + // through otherwise. + if (!DefBlocks.empty()) + DefBlocks.insert(&*MF.begin()); + + // Ask the SSA construction algorithm where we should put PHIs. Clear + // anything that might have been hanging around from earlier. + PHIBlocks.clear(); + BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks); + }; + + auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) { + for (const MachineBasicBlock *MBB : PHIBlocks) + MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L); + }; + + // For locations with no reg units, just place PHIs. + for (LocIdx L : NormalLocsToPHI) { + CollectPHIsForLoc(L); + // Install those PHI values into the live-in value array. + InstallPHIsAtLoc(L); + } + + // For stack slots, calculate PHIs for the equivalent of the units, then + // install for each index. + for (SpillLocationNo Slot : StackSlots) { + for (unsigned Idx : StackUnits) { + unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx); + LocIdx L = MTracker->getSpillMLoc(SpillID); + CollectPHIsForLoc(L); + InstallPHIsAtLoc(L); + + // Find anything that aliases this stack index, install PHIs for it too. + unsigned Size, Offset; + std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx]; + for (auto &Pair : MTracker->StackSlotIdxes) { + unsigned ThisSize, ThisOffset; + std::tie(ThisSize, ThisOffset) = Pair.first; + if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset) + continue; + + unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second); + LocIdx ThisL = MTracker->getSpillMLoc(ThisID); + InstallPHIsAtLoc(ThisL); + } + } + } + + // For reg units, place PHIs, and then place them for any aliasing registers. + for (Register R : RegUnitsToPHIUp) { + LocIdx L = MTracker->lookupOrTrackRegister(R); + CollectPHIsForLoc(L); + + // Install those PHI values into the live-in value array. + InstallPHIsAtLoc(L); + + // Now find aliases and install PHIs for those. + for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) { + // Super-registers that are "above" the largest register read/written by + // the function will alias, but will not be tracked. + if (!MTracker->isRegisterTracked(*RAI)) + continue; + + LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI); + InstallPHIsAtLoc(AliasLoc); + } + } +} + +void InstrRefBasedLDV::buildMLocValueMap( + MachineFunction &MF, ValueIDNum **MInLocs, ValueIDNum **MOutLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) { std::priority_queue<unsigned int, std::vector<unsigned int>, std::greater<unsigned int>> @@ -2666,20 +2060,34 @@ void InstrRefBasedLDV::mlocDataflow( // but this is probably not worth it. SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist; - // Initialize worklist with every block to be visited. + // Initialize worklist with every block to be visited. Also produce list of + // all blocks. + SmallPtrSet<MachineBasicBlock *, 32> AllBlocks; for (unsigned int I = 0; I < BBToOrder.size(); ++I) { Worklist.push(I); OnWorklist.insert(OrderToBB[I]); + AllBlocks.insert(OrderToBB[I]); } - MTracker->reset(); - - // Set inlocs for entry block -- each as a PHI at the entry block. Represents - // the incoming value to the function. - MTracker->setMPhis(0); + // Initialize entry block to PHIs. These represent arguments. for (auto Location : MTracker->locations()) - MInLocs[0][Location.Idx.asU64()] = Location.Value; + MInLocs[0][Location.Idx.asU64()] = ValueIDNum(0, 0, Location.Idx); + MTracker->reset(); + + // Start by placing PHIs, using the usual SSA constructor algorithm. Consider + // any machine-location that isn't live-through a block to be def'd in that + // block. + placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer); + + // Propagate values to eliminate redundant PHIs. At the same time, this + // produces the table of Block x Location => Value for the entry to each + // block. + // The kind of PHIs we can eliminate are, for example, where one path in a + // conditional spills and restores a register, and the register still has + // the same value once control flow joins, unbeknowns to the PHI placement + // code. Propagating values allows us to identify such un-necessary PHIs and + // remove them. SmallPtrSet<const MachineBasicBlock *, 16> Visited; while (!Worklist.empty() || !Pending.empty()) { // Vector for storing the evaluated block transfer function. @@ -2691,16 +2099,10 @@ void InstrRefBasedLDV::mlocDataflow( Worklist.pop(); // Join the values in all predecessor blocks. - bool InLocsChanged, DowngradeOccurred; - std::tie(InLocsChanged, DowngradeOccurred) = - mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]); + bool InLocsChanged; + InLocsChanged = mlocJoin(*MBB, Visited, MOutLocs, MInLocs[CurBB]); InLocsChanged |= Visited.insert(MBB).second; - // If a downgrade occurred, book us in for re-examination on the next - // iteration. - if (DowngradeOccurred && OnPending.insert(MBB).second) - Pending.push(BBToOrder[MBB]); - // Don't examine transfer function if we've visited this loc at least // once, and inlocs haven't changed. if (!InLocsChanged) @@ -2715,7 +2117,7 @@ void InstrRefBasedLDV::mlocDataflow( for (auto &P : MLocTransfer[CurBB]) { if (P.second.getBlock() == CurBB && P.second.isPHI()) { // This is a movement of whatever was live in. Read it. - ValueIDNum NewID = MTracker->getNumAtPos(P.second.getLoc()); + ValueIDNum NewID = MTracker->readMLoc(P.second.getLoc()); ToRemap.push_back(std::make_pair(P.first, NewID)); } else { // It's a def. Just set it. @@ -2745,8 +2147,8 @@ void InstrRefBasedLDV::mlocDataflow( continue; // All successors should be visited: put any back-edges on the pending - // list for the next dataflow iteration, and any other successors to be - // visited this iteration, if they're not going to be already. + // list for the next pass-through, and any other successors to be + // visited this pass, if they're not going to be already. for (auto s : MBB->successors()) { // Does branching to this successor represent a back-edge? if (BBToOrder[s] > BBToOrder[MBB]) { @@ -2769,170 +2171,169 @@ void InstrRefBasedLDV::mlocDataflow( assert(Pending.empty() && "Pending should be empty"); } - // Once all the live-ins don't change on mlocJoin(), we've reached a - // fixedpoint. + // Once all the live-ins don't change on mlocJoin(), we've eliminated all + // redundant PHIs. } -bool InstrRefBasedLDV::vlocDowngradeLattice( - const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation, - const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) { - // Ranking value preference: see file level comment, the highest rank is - // a plain def, followed by PHI values in reverse post-order. Numerically, - // we assign all defs the rank '0', all PHIs their blocks RPO number plus - // one, and consider the lowest value the highest ranked. - int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1; - if (!OldLiveInLocation.ID.isPHI()) - OldLiveInRank = 0; - - // Allow any unresolvable conflict to be over-ridden. - if (OldLiveInLocation.Kind == DbgValue::NoVal) { - // Although if it was an unresolvable conflict from _this_ block, then - // all other seeking of downgrades and PHIs must have failed before hand. - if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber()) - return false; - OldLiveInRank = INT_MIN; - } - - auto &InValue = *Values[0].second; +// Boilerplate for feeding MachineBasicBlocks into IDF calculator. Provide +// template specialisations for graph traits and a successor enumerator. +namespace llvm { +template <> struct GraphTraits<MachineBasicBlock> { + using NodeRef = MachineBasicBlock *; + using ChildIteratorType = MachineBasicBlock::succ_iterator; - if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal) - return false; + static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; } + static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } + static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } +}; - unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()]; - int ThisRank = ThisRPO + 1; - if (!InValue.ID.isPHI()) - ThisRank = 0; +template <> struct GraphTraits<const MachineBasicBlock> { + using NodeRef = const MachineBasicBlock *; + using ChildIteratorType = MachineBasicBlock::const_succ_iterator; - // Too far down the lattice? - if (ThisRPO >= CurBlockRPONum) - return false; + static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; } + static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } + static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } +}; - // Higher in the lattice than what we've already explored? - if (ThisRank <= OldLiveInRank) - return false; +using MachineDomTreeBase = DomTreeBase<MachineBasicBlock>::NodeType; +using MachineDomTreeChildGetter = + typename IDFCalculatorDetail::ChildrenGetterTy<MachineDomTreeBase, false>; - return true; +namespace IDFCalculatorDetail { +template <> +typename MachineDomTreeChildGetter::ChildrenTy +MachineDomTreeChildGetter::get(const NodeRef &N) { + return {N->succ_begin(), N->succ_end()}; +} +} // namespace IDFCalculatorDetail +} // namespace llvm + +void InstrRefBasedLDV::BlockPHIPlacement( + const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks, + const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks, + SmallVectorImpl<MachineBasicBlock *> &PHIBlocks) { + // Apply IDF calculator to the designated set of location defs, storing + // required PHIs into PHIBlocks. Uses the dominator tree stored in the + // InstrRefBasedLDV object. + IDFCalculatorDetail::ChildrenGetterTy<MachineDomTreeBase, false> foo; + IDFCalculatorBase<MachineDomTreeBase, false> IDF(DomTree->getBase(), foo); + + IDF.setLiveInBlocks(AllBlocks); + IDF.setDefiningBlocks(DefBlocks); + IDF.calculate(PHIBlocks); } -std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc( - MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts, - ValueIDNum **MOutLocs, ValueIDNum **MInLocs, - const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) { +Optional<ValueIDNum> InstrRefBasedLDV::pickVPHILoc( + const MachineBasicBlock &MBB, const DebugVariable &Var, + const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, + const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) { // Collect a set of locations from predecessor where its live-out value can // be found. SmallVector<SmallVector<LocIdx, 4>, 8> Locs; + SmallVector<const DbgValueProperties *, 4> Properties; unsigned NumLocs = MTracker->getNumLocs(); - unsigned BackEdgesStart = 0; - for (auto p : BlockOrders) { - // Pick out where backedges start in the list of predecessors. Relies on - // BlockOrders being sorted by RPO. - if (BBToOrder[p] < BBToOrder[&MBB]) - ++BackEdgesStart; + // No predecessors means no PHIs. + if (BlockOrders.empty()) + return None; - // For each predecessor, create a new set of locations. - Locs.resize(Locs.size() + 1); + for (auto p : BlockOrders) { unsigned ThisBBNum = p->getNumber(); - auto LiveOutMap = LiveOuts.find(p); - if (LiveOutMap == LiveOuts.end()) - // This predecessor isn't in scope, it must have no live-in/live-out - // locations. - continue; - - auto It = LiveOutMap->second->find(Var); - if (It == LiveOutMap->second->end()) - // There's no value recorded for this variable in this predecessor, - // leave an empty set of locations. - continue; - - const DbgValue &OutVal = It->second; + auto OutValIt = LiveOuts.find(p); + if (OutValIt == LiveOuts.end()) + // If we have a predecessor not in scope, we'll never find a PHI position. + return None; + const DbgValue &OutVal = *OutValIt->second; if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal) // Consts and no-values cannot have locations we can join on. - continue; + return None; - assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def); - ValueIDNum ValToLookFor = OutVal.ID; + Properties.push_back(&OutVal.Properties); + + // Create new empty vector of locations. + Locs.resize(Locs.size() + 1); - // Search the live-outs of the predecessor for the specified value. - for (unsigned int I = 0; I < NumLocs; ++I) { - if (MOutLocs[ThisBBNum][I] == ValToLookFor) - Locs.back().push_back(LocIdx(I)); + // If the live-in value is a def, find the locations where that value is + // present. Do the same for VPHIs where we know the VPHI value. + if (OutVal.Kind == DbgValue::Def || + (OutVal.Kind == DbgValue::VPHI && OutVal.BlockNo != MBB.getNumber() && + OutVal.ID != ValueIDNum::EmptyValue)) { + ValueIDNum ValToLookFor = OutVal.ID; + // Search the live-outs of the predecessor for the specified value. + for (unsigned int I = 0; I < NumLocs; ++I) { + if (MOutLocs[ThisBBNum][I] == ValToLookFor) + Locs.back().push_back(LocIdx(I)); + } + } else { + assert(OutVal.Kind == DbgValue::VPHI); + // For VPHIs where we don't know the location, we definitely can't find + // a join loc. + if (OutVal.BlockNo != MBB.getNumber()) + return None; + + // Otherwise: this is a VPHI on a backedge feeding back into itself, i.e. + // a value that's live-through the whole loop. (It has to be a backedge, + // because a block can't dominate itself). We can accept as a PHI location + // any location where the other predecessors agree, _and_ the machine + // locations feed back into themselves. Therefore, add all self-looping + // machine-value PHI locations. + for (unsigned int I = 0; I < NumLocs; ++I) { + ValueIDNum MPHI(MBB.getNumber(), 0, LocIdx(I)); + if (MOutLocs[ThisBBNum][I] == MPHI) + Locs.back().push_back(LocIdx(I)); + } } } - // If there were no locations at all, return an empty result. - if (Locs.empty()) - return std::tuple<Optional<ValueIDNum>, bool>(None, false); - - // Lambda for seeking a common location within a range of location-sets. - using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator; - auto SeekLocation = - [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> { - // Starting with the first set of locations, take the intersection with - // subsequent sets. - SmallVector<LocIdx, 4> base = Locs[0]; - for (auto &S : SearchRange) { - SmallVector<LocIdx, 4> new_base; - std::set_intersection(base.begin(), base.end(), S.begin(), S.end(), - std::inserter(new_base, new_base.begin())); - base = new_base; - } - if (base.empty()) - return None; + // We should have found locations for all predecessors, or returned. + assert(Locs.size() == BlockOrders.size()); - // We now have a set of LocIdxes that contain the right output value in - // each of the predecessors. Pick the lowest; if there's a register loc, - // that'll be it. - return *base.begin(); - }; + // Check that all properties are the same. We can't pick a location if they're + // not. + const DbgValueProperties *Properties0 = Properties[0]; + for (auto *Prop : Properties) + if (*Prop != *Properties0) + return None; - // Search for a common location for all predecessors. If we can't, then fall - // back to only finding a common location between non-backedge predecessors. - bool ValidForAllLocs = true; - auto TheLoc = SeekLocation(Locs); - if (!TheLoc) { - ValidForAllLocs = false; - TheLoc = - SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart)); - } + // Starting with the first set of locations, take the intersection with + // subsequent sets. + SmallVector<LocIdx, 4> CandidateLocs = Locs[0]; + for (unsigned int I = 1; I < Locs.size(); ++I) { + auto &LocVec = Locs[I]; + SmallVector<LocIdx, 4> NewCandidates; + std::set_intersection(CandidateLocs.begin(), CandidateLocs.end(), + LocVec.begin(), LocVec.end(), std::inserter(NewCandidates, NewCandidates.begin())); + CandidateLocs = NewCandidates; + } + if (CandidateLocs.empty()) + return None; - if (!TheLoc) - return std::tuple<Optional<ValueIDNum>, bool>(None, false); + // We now have a set of LocIdxes that contain the right output value in + // each of the predecessors. Pick the lowest; if there's a register loc, + // that'll be it. + LocIdx L = *CandidateLocs.begin(); // Return a PHI-value-number for the found location. - LocIdx L = *TheLoc; ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L}; - return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs); + return PHIVal; } -std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin( - MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs, - SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum, - const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs, - ValueIDNum **MInLocs, +bool InstrRefBasedLDV::vlocJoin( + MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks, SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore, - DenseMap<DebugVariable, DbgValue> &InLocsT) { - bool DowngradeOccurred = false; - + DbgValue &LiveIn) { // To emulate VarLocBasedImpl, process this block if it's not in scope but // _does_ assign a variable value. No live-ins for this scope are transferred // in though, so we can return immediately. - if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) { - if (VLOCVisited) - return std::tuple<bool, bool>(true, false); - return std::tuple<bool, bool>(false, false); - } + if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) + return false; LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); bool Changed = false; - // Find any live-ins computed in a prior iteration. - auto ILSIt = VLOCInLocs.find(&MBB); - assert(ILSIt != VLOCInLocs.end()); - auto &ILS = *ILSIt->second; - // Order predecessors by RPOT order, for exploring them in that order. SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors()); @@ -2944,244 +2345,102 @@ std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin( unsigned CurBlockRPONum = BBToOrder[&MBB]; - // Force a re-visit to loop heads in the first dataflow iteration. - // FIXME: if we could "propose" Const values this wouldn't be needed, - // because they'd need to be confirmed before being emitted. - if (!BlockOrders.empty() && - BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum && - VLOCVisited) - DowngradeOccurred = true; - - auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) { - auto Result = InLocsT.insert(std::make_pair(DV, VR)); - (void)Result; - assert(Result.second); - }; - - auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) { - DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal); - - ConfirmValue(Var, NoLocPHIVal); - }; + // Collect all the incoming DbgValues for this variable, from predecessor + // live-out values. + SmallVector<InValueT, 8> Values; + bool Bail = false; + int BackEdgesStart = 0; + for (auto p : BlockOrders) { + // If the predecessor isn't in scope / to be explored, we'll never be + // able to join any locations. + if (!BlocksToExplore.contains(p)) { + Bail = true; + break; + } - // Attempt to join the values for each variable. - for (auto &Var : AllVars) { - // Collect all the DbgValues for this variable. - SmallVector<InValueT, 8> Values; - bool Bail = false; - unsigned BackEdgesStart = 0; - for (auto p : BlockOrders) { - // If the predecessor isn't in scope / to be explored, we'll never be - // able to join any locations. - if (!BlocksToExplore.contains(p)) { - Bail = true; - break; - } + // All Live-outs will have been initialized. + DbgValue &OutLoc = *VLOCOutLocs.find(p)->second; - // Don't attempt to handle unvisited predecessors: they're implicitly - // "unknown"s in the lattice. - if (VLOCVisited && !VLOCVisited->count(p)) - continue; + // Keep track of where back-edges begin in the Values vector. Relies on + // BlockOrders being sorted by RPO. + unsigned ThisBBRPONum = BBToOrder[p]; + if (ThisBBRPONum < CurBlockRPONum) + ++BackEdgesStart; - // If the predecessors OutLocs is absent, there's not much we can do. - auto OL = VLOCOutLocs.find(p); - if (OL == VLOCOutLocs.end()) { - Bail = true; - break; - } + Values.push_back(std::make_pair(p, &OutLoc)); + } - // No live-out value for this predecessor also means we can't produce - // a joined value. - auto VIt = OL->second->find(Var); - if (VIt == OL->second->end()) { - Bail = true; - break; - } + // If there were no values, or one of the predecessors couldn't have a + // value, then give up immediately. It's not safe to produce a live-in + // value. Leave as whatever it was before. + if (Bail || Values.size() == 0) + return false; - // Keep track of where back-edges begin in the Values vector. Relies on - // BlockOrders being sorted by RPO. - unsigned ThisBBRPONum = BBToOrder[p]; - if (ThisBBRPONum < CurBlockRPONum) - ++BackEdgesStart; + // All (non-entry) blocks have at least one non-backedge predecessor. + // Pick the variable value from the first of these, to compare against + // all others. + const DbgValue &FirstVal = *Values[0].second; + + // If the old live-in value is not a PHI then either a) no PHI is needed + // here, or b) we eliminated the PHI that was here. If so, we can just + // propagate in the first parent's incoming value. + if (LiveIn.Kind != DbgValue::VPHI || LiveIn.BlockNo != MBB.getNumber()) { + Changed = LiveIn != FirstVal; + if (Changed) + LiveIn = FirstVal; + return Changed; + } + + // Scan for variable values that can never be resolved: if they have + // different DIExpressions, different indirectness, or are mixed constants / + // non-constants. + for (auto &V : Values) { + if (V.second->Properties != FirstVal.Properties) + return false; + if (V.second->Kind == DbgValue::NoVal) + return false; + if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const) + return false; + } - Values.push_back(std::make_pair(p, &VIt->second)); - } + // Try to eliminate this PHI. Do the incoming values all agree? + bool Disagree = false; + for (auto &V : Values) { + if (*V.second == FirstVal) + continue; // No disagreement. - // If there were no values, or one of the predecessors couldn't have a - // value, then give up immediately. It's not safe to produce a live-in - // value. - if (Bail || Values.size() == 0) + // Eliminate if a backedge feeds a VPHI back into itself. + if (V.second->Kind == DbgValue::VPHI && + V.second->BlockNo == MBB.getNumber() && + // Is this a backedge? + std::distance(Values.begin(), &V) >= BackEdgesStart) continue; - // Enumeration identifying the current state of the predecessors values. - enum { - Unset = 0, - Agreed, // All preds agree on the variable value. - PropDisagree, // All preds agree, but the value kind is Proposed in some. - BEDisagree, // Only back-edges disagree on variable value. - PHINeeded, // Non-back-edge predecessors have conflicing values. - NoSolution // Conflicting Value metadata makes solution impossible. - } OurState = Unset; - - // All (non-entry) blocks have at least one non-backedge predecessor. - // Pick the variable value from the first of these, to compare against - // all others. - const DbgValue &FirstVal = *Values[0].second; - const ValueIDNum &FirstID = FirstVal.ID; - - // Scan for variable values that can't be resolved: if they have different - // DIExpressions, different indirectness, or are mixed constants / - // non-constants. - for (auto &V : Values) { - if (V.second->Properties != FirstVal.Properties) - OurState = NoSolution; - if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const) - OurState = NoSolution; - } - - // Flags diagnosing _how_ the values disagree. - bool NonBackEdgeDisagree = false; - bool DisagreeOnPHINess = false; - bool IDDisagree = false; - bool Disagree = false; - if (OurState == Unset) { - for (auto &V : Values) { - if (*V.second == FirstVal) - continue; // No disagreement. - - Disagree = true; - - // Flag whether the value number actually diagrees. - if (V.second->ID != FirstID) - IDDisagree = true; - - // Distinguish whether disagreement happens in backedges or not. - // Relies on Values (and BlockOrders) being sorted by RPO. - unsigned ThisBBRPONum = BBToOrder[V.first]; - if (ThisBBRPONum < CurBlockRPONum) - NonBackEdgeDisagree = true; - - // Is there a difference in whether the value is definite or only - // proposed? - if (V.second->Kind != FirstVal.Kind && - (V.second->Kind == DbgValue::Proposed || - V.second->Kind == DbgValue::Def) && - (FirstVal.Kind == DbgValue::Proposed || - FirstVal.Kind == DbgValue::Def)) - DisagreeOnPHINess = true; - } - - // Collect those flags together and determine an overall state for - // what extend the predecessors agree on a live-in value. - if (!Disagree) - OurState = Agreed; - else if (!IDDisagree && DisagreeOnPHINess) - OurState = PropDisagree; - else if (!NonBackEdgeDisagree) - OurState = BEDisagree; - else - OurState = PHINeeded; - } - - // An extra indicator: if we only disagree on whether the value is a - // Def, or proposed, then also flag whether that disagreement happens - // in backedges only. - bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess && - !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def; - - const auto &Properties = FirstVal.Properties; - - auto OldLiveInIt = ILS.find(Var); - const DbgValue *OldLiveInLocation = - (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr; - - bool OverRide = false; - if (OurState == BEDisagree && OldLiveInLocation) { - // Only backedges disagree: we can consider downgrading. If there was a - // previous live-in value, use it to work out whether the current - // incoming value represents a lattice downgrade or not. - OverRide = - vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum); - } - - // Use the current state of predecessor agreement and other flags to work - // out what to do next. Possibilities include: - // * Accept a value all predecessors agree on, or accept one that - // represents a step down the exploration lattice, - // * Use a PHI value number, if one can be found, - // * Propose a PHI value number, and see if it gets confirmed later, - // * Emit a 'NoVal' value, indicating we couldn't resolve anything. - if (OurState == Agreed) { - // Easiest solution: all predecessors agree on the variable value. - ConfirmValue(Var, FirstVal); - } else if (OurState == BEDisagree && OverRide) { - // Only backedges disagree, and the other predecessors have produced - // a new live-in value further down the exploration lattice. - DowngradeOccurred = true; - ConfirmValue(Var, FirstVal); - } else if (OurState == PropDisagree) { - // Predecessors agree on value, but some say it's only a proposed value. - // Propagate it as proposed: unless it was proposed in this block, in - // which case we're able to confirm the value. - if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) { - ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); - } else if (PropOnlyInBEs) { - // If only backedges disagree, a higher (in RPO) block confirmed this - // location, and we need to propagate it into this loop. - ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def)); - } else { - // Otherwise; a Def meeting a Proposed is still a Proposed. - ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed)); - } - } else if ((OurState == PHINeeded || OurState == BEDisagree)) { - // Predecessors disagree and can't be downgraded: this can only be - // solved with a PHI. Use pickVPHILoc to go look for one. - Optional<ValueIDNum> VPHI; - bool AllEdgesVPHI = false; - std::tie(VPHI, AllEdgesVPHI) = - pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders); - - if (VPHI && AllEdgesVPHI) { - // There's a PHI value that's valid for all predecessors -- we can use - // it. If any of the non-backedge predecessors have proposed values - // though, this PHI is also only proposed, until the predecessors are - // confirmed. - DbgValue::KindT K = DbgValue::Def; - for (unsigned int I = 0; I < BackEdgesStart; ++I) - if (Values[I].second->Kind == DbgValue::Proposed) - K = DbgValue::Proposed; - - ConfirmValue(Var, DbgValue(*VPHI, Properties, K)); - } else if (VPHI) { - // There's a PHI value, but it's only legal for backedges. Leave this - // as a proposed PHI value: it might come back on the backedges, - // and allow us to confirm it in the future. - DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed); - ConfirmValue(Var, NoBEValue); - } else { - ConfirmNoVal(Var, Properties); - } - } else { - // Otherwise: we don't know. Emit a "phi but no real loc" phi. - ConfirmNoVal(Var, Properties); - } + Disagree = true; } - // Store newly calculated in-locs into VLOCInLocs, if they've changed. - Changed = ILS != InLocsT; - if (Changed) - ILS = InLocsT; - - return std::tuple<bool, bool>(Changed, DowngradeOccurred); + // No disagreement -> live-through value. + if (!Disagree) { + Changed = LiveIn != FirstVal; + if (Changed) + LiveIn = FirstVal; + return Changed; + } else { + // Otherwise use a VPHI. + DbgValue VPHI(MBB.getNumber(), FirstVal.Properties, DbgValue::VPHI); + Changed = LiveIn != VPHI; + if (Changed) + LiveIn = VPHI; + return Changed; + } } -void InstrRefBasedLDV::vlocDataflow( - const LexicalScope *Scope, const DILocation *DILoc, +void InstrRefBasedLDV::buildVLocValueMap(const DILocation *DILoc, const SmallSet<DebugVariable, 4> &VarsWeCareAbout, SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output, ValueIDNum **MOutLocs, ValueIDNum **MInLocs, SmallVectorImpl<VLocTracker> &AllTheVLocs) { - // This method is much like mlocDataflow: but focuses on a single + // This method is much like buildMLocValueMap: but focuses on a single // LexicalScope at a time. Pick out a set of blocks and variables that are // to have their value assignments solved, then run our dataflow algorithm // until a fixedpoint is reached. @@ -3235,8 +2494,8 @@ void InstrRefBasedLDV::vlocDataflow( continue; if (!ArtificialBlocks.count(succ)) continue; - DFS.push_back(std::make_pair(succ, succ->succ_begin())); ToAdd.insert(succ); + DFS.push_back(std::make_pair(succ, succ->succ_begin())); } // Search all those blocks, depth first. @@ -3252,8 +2511,8 @@ void InstrRefBasedLDV::vlocDataflow( // If the current successor is artificial and unexplored, descend into // it. if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) { - DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin())); ToAdd.insert(*CurSucc); + DFS.push_back(std::make_pair(*CurSucc, (*CurSucc)->succ_begin())); continue; } @@ -3278,6 +2537,13 @@ void InstrRefBasedLDV::vlocDataflow( if (BlocksToExplore.size() == 1) return; + // Convert a const set to a non-const set. LexicalScopes + // getMachineBasicBlocks returns const MBB pointers, IDF wants mutable ones. + // (Neither of them mutate anything). + SmallPtrSet<MachineBasicBlock *, 8> MutBlocksToExplore; + for (const auto *MBB : BlocksToExplore) + MutBlocksToExplore.insert(const_cast<MachineBasicBlock *>(MBB)); + // Picks out relevants blocks RPO order and sort them. for (auto *MBB : BlocksToExplore) BlockOrders.push_back(const_cast<MachineBasicBlock *>(MBB)); @@ -3286,9 +2552,18 @@ void InstrRefBasedLDV::vlocDataflow( unsigned NumBlocks = BlockOrders.size(); // Allocate some vectors for storing the live ins and live outs. Large. - SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts; - LiveIns.resize(NumBlocks); - LiveOuts.resize(NumBlocks); + SmallVector<DbgValue, 32> LiveIns, LiveOuts; + LiveIns.reserve(NumBlocks); + LiveOuts.reserve(NumBlocks); + + // Initialize all values to start as NoVals. This signifies "it's live + // through, but we don't know what it is". + DbgValueProperties EmptyProperties(EmptyExpr, false); + for (unsigned int I = 0; I < NumBlocks; ++I) { + DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal); + LiveIns.push_back(EmptyDbgValue); + LiveOuts.push_back(EmptyDbgValue); + } // Produce by-MBB indexes of live-in/live-outs, to ease lookup within // vlocJoin. @@ -3300,108 +2575,164 @@ void InstrRefBasedLDV::vlocDataflow( LiveInIdx[BlockOrders[I]] = &LiveIns[I]; } - for (auto *MBB : BlockOrders) { - Worklist.push(BBToOrder[MBB]); - OnWorklist.insert(MBB); - } + // Loop over each variable and place PHIs for it, then propagate values + // between blocks. This keeps the locality of working on one lexical scope at + // at time, but avoids re-processing variable values because some other + // variable has been assigned. + for (auto &Var : VarsWeCareAbout) { + // Re-initialize live-ins and live-outs, to clear the remains of previous + // variables live-ins / live-outs. + for (unsigned int I = 0; I < NumBlocks; ++I) { + DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal); + LiveIns[I] = EmptyDbgValue; + LiveOuts[I] = EmptyDbgValue; + } - // Iterate over all the blocks we selected, propagating variable values. - bool FirstTrip = true; - SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited; - while (!Worklist.empty() || !Pending.empty()) { - while (!Worklist.empty()) { - auto *MBB = OrderToBB[Worklist.top()]; - CurBB = MBB->getNumber(); - Worklist.pop(); + // Place PHIs for variable values, using the LLVM IDF calculator. + // Collect the set of blocks where variables are def'd. + SmallPtrSet<MachineBasicBlock *, 32> DefBlocks; + for (const MachineBasicBlock *ExpMBB : BlocksToExplore) { + auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars; + if (TransferFunc.find(Var) != TransferFunc.end()) + DefBlocks.insert(const_cast<MachineBasicBlock *>(ExpMBB)); + } - DenseMap<DebugVariable, DbgValue> JoinedInLocs; + SmallVector<MachineBasicBlock *, 32> PHIBlocks; - // Join values from predecessors. Updates LiveInIdx, and writes output - // into JoinedInLocs. - bool InLocsChanged, DowngradeOccurred; - std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin( - *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr, - CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks, - BlocksToExplore, JoinedInLocs); + // Request the set of PHIs we should insert for this variable. + BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks); - bool FirstVisit = VLOCVisited.insert(MBB).second; + // Insert PHIs into the per-block live-in tables for this variable. + for (MachineBasicBlock *PHIMBB : PHIBlocks) { + unsigned BlockNo = PHIMBB->getNumber(); + DbgValue *LiveIn = LiveInIdx[PHIMBB]; + *LiveIn = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI); + } - // Always explore transfer function if inlocs changed, or if we've not - // visited this block before. - InLocsChanged |= FirstVisit; + for (auto *MBB : BlockOrders) { + Worklist.push(BBToOrder[MBB]); + OnWorklist.insert(MBB); + } - // If a downgrade occurred, book us in for re-examination on the next - // iteration. - if (DowngradeOccurred && OnPending.insert(MBB).second) - Pending.push(BBToOrder[MBB]); + // Iterate over all the blocks we selected, propagating the variables value. + // This loop does two things: + // * Eliminates un-necessary VPHIs in vlocJoin, + // * Evaluates the blocks transfer function (i.e. variable assignments) and + // stores the result to the blocks live-outs. + // Always evaluate the transfer function on the first iteration, and when + // the live-ins change thereafter. + bool FirstTrip = true; + while (!Worklist.empty() || !Pending.empty()) { + while (!Worklist.empty()) { + auto *MBB = OrderToBB[Worklist.top()]; + CurBB = MBB->getNumber(); + Worklist.pop(); + + auto LiveInsIt = LiveInIdx.find(MBB); + assert(LiveInsIt != LiveInIdx.end()); + DbgValue *LiveIn = LiveInsIt->second; + + // Join values from predecessors. Updates LiveInIdx, and writes output + // into JoinedInLocs. + bool InLocsChanged = + vlocJoin(*MBB, LiveOutIdx, InScopeBlocks, BlocksToExplore, *LiveIn); + + SmallVector<const MachineBasicBlock *, 8> Preds; + for (const auto *Pred : MBB->predecessors()) + Preds.push_back(Pred); + + // If this block's live-in value is a VPHI, try to pick a machine-value + // for it. This makes the machine-value available and propagated + // through all blocks by the time value propagation finishes. We can't + // do this any earlier as it needs to read the block live-outs. + if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) { + // There's a small possibility that on a preceeding path, a VPHI is + // eliminated and transitions from VPHI-with-location to + // live-through-value. As a result, the selected location of any VPHI + // might change, so we need to re-compute it on each iteration. + Optional<ValueIDNum> ValueNum = + pickVPHILoc(*MBB, Var, LiveOutIdx, MOutLocs, Preds); + + if (ValueNum) { + InLocsChanged |= LiveIn->ID != *ValueNum; + LiveIn->ID = *ValueNum; + } + } - if (!InLocsChanged) - continue; + if (!InLocsChanged && !FirstTrip) + continue; + + DbgValue *LiveOut = LiveOutIdx[MBB]; + bool OLChanged = false; - // Do transfer function. - auto &VTracker = AllTheVLocs[MBB->getNumber()]; - for (auto &Transfer : VTracker.Vars) { - // Is this var we're mangling in this scope? - if (VarsWeCareAbout.count(Transfer.first)) { + // Do transfer function. + auto &VTracker = AllTheVLocs[MBB->getNumber()]; + auto TransferIt = VTracker.Vars.find(Var); + if (TransferIt != VTracker.Vars.end()) { // Erase on empty transfer (DBG_VALUE $noreg). - if (Transfer.second.Kind == DbgValue::Undef) { - JoinedInLocs.erase(Transfer.first); + if (TransferIt->second.Kind == DbgValue::Undef) { + DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal); + if (*LiveOut != NewVal) { + *LiveOut = NewVal; + OLChanged = true; + } } else { // Insert new variable value; or overwrite. - auto NewValuePair = std::make_pair(Transfer.first, Transfer.second); - auto Result = JoinedInLocs.insert(NewValuePair); - if (!Result.second) - Result.first->second = Transfer.second; + if (*LiveOut != TransferIt->second) { + *LiveOut = TransferIt->second; + OLChanged = true; + } + } + } else { + // Just copy live-ins to live-outs, for anything not transferred. + if (*LiveOut != *LiveIn) { + *LiveOut = *LiveIn; + OLChanged = true; } } - } - - // Did the live-out locations change? - bool OLChanged = JoinedInLocs != *LiveOutIdx[MBB]; - - // If they haven't changed, there's no need to explore further. - if (!OLChanged) - continue; - // Commit to the live-out record. - *LiveOutIdx[MBB] = JoinedInLocs; - - // We should visit all successors. Ensure we'll visit any non-backedge - // successors during this dataflow iteration; book backedge successors - // to be visited next time around. - for (auto s : MBB->successors()) { - // Ignore out of scope / not-to-be-explored successors. - if (LiveInIdx.find(s) == LiveInIdx.end()) + // If no live-out value changed, there's no need to explore further. + if (!OLChanged) continue; - if (BBToOrder[s] > BBToOrder[MBB]) { - if (OnWorklist.insert(s).second) - Worklist.push(BBToOrder[s]); - } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) { - Pending.push(BBToOrder[s]); + // We should visit all successors. Ensure we'll visit any non-backedge + // successors during this dataflow iteration; book backedge successors + // to be visited next time around. + for (auto s : MBB->successors()) { + // Ignore out of scope / not-to-be-explored successors. + if (LiveInIdx.find(s) == LiveInIdx.end()) + continue; + + if (BBToOrder[s] > BBToOrder[MBB]) { + if (OnWorklist.insert(s).second) + Worklist.push(BBToOrder[s]); + } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) { + Pending.push(BBToOrder[s]); + } } } + Worklist.swap(Pending); + std::swap(OnWorklist, OnPending); + OnPending.clear(); + assert(Pending.empty()); + FirstTrip = false; } - Worklist.swap(Pending); - std::swap(OnWorklist, OnPending); - OnPending.clear(); - assert(Pending.empty()); - FirstTrip = false; - } - - // Dataflow done. Now what? Save live-ins. Ignore any that are still marked - // as being variable-PHIs, because those did not have their machine-PHI - // value confirmed. Such variable values are places that could have been - // PHIs, but are not. - for (auto *MBB : BlockOrders) { - auto &VarMap = *LiveInIdx[MBB]; - for (auto &P : VarMap) { - if (P.second.Kind == DbgValue::Proposed || - P.second.Kind == DbgValue::NoVal) + + // Save live-ins to output vector. Ignore any that are still marked as being + // VPHIs with no location -- those are variables that we know the value of, + // but are not actually available in the register file. + for (auto *MBB : BlockOrders) { + DbgValue *BlockLiveIn = LiveInIdx[MBB]; + if (BlockLiveIn->Kind == DbgValue::NoVal) continue; - Output[MBB->getNumber()].push_back(P); + if (BlockLiveIn->Kind == DbgValue::VPHI && + BlockLiveIn->ID == ValueIDNum::EmptyValue) + continue; + if (BlockLiveIn->Kind == DbgValue::VPHI) + BlockLiveIn->Kind = DbgValue::Def; + Output[MBB->getNumber()].push_back(std::make_pair(Var, *BlockLiveIn)); } - } + } // Per-variable loop. BlockOrders.clear(); BlocksToExplore.clear(); @@ -3485,6 +2816,10 @@ void InstrRefBasedLDV::emitLocations( void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { // Build some useful data structures. + + LLVMContext &Context = MF.getFunction().getContext(); + EmptyExpr = DIExpression::get(Context, {}); + auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { if (const DebugLoc &DL = MI.getDebugLoc()) return DL.getLine() != 0; @@ -3524,7 +2859,10 @@ void InstrRefBasedLDV::initialSetup(MachineFunction &MF) { /// Calculate the liveness information for the given machine function and /// extend ranges across basic blocks. bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, - TargetPassConfig *TPC) { + MachineDominatorTree *DomTree, + TargetPassConfig *TPC, + unsigned InputBBLimit, + unsigned InputDbgValLimit) { // No subprogram means this function contains no debuginfo. if (!MF.getFunction().getSubprogram()) return false; @@ -3532,7 +2870,9 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n"); this->TPC = TPC; + this->DomTree = DomTree; TRI = MF.getSubtarget().getRegisterInfo(); + MRI = &MF.getRegInfo(); TII = MF.getSubtarget().getInstrInfo(); TFI = MF.getSubtarget().getFrameLowering(); TFI->getCalleeSaves(MF, CalleeSavedRegs); @@ -3569,6 +2909,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, ValueIDNum **MInLocs = new ValueIDNum *[MaxNumBlocks]; unsigned NumLocs = MTracker->getNumLocs(); for (int i = 0; i < MaxNumBlocks; ++i) { + // These all auto-initialize to ValueIDNum::EmptyValue MOutLocs[i] = new ValueIDNum[NumLocs]; MInLocs[i] = new ValueIDNum[NumLocs]; } @@ -3577,7 +2918,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, // storing the computed live-ins / live-outs into the array-of-arrays. We use // both live-ins and live-outs for decision making in the variable value // dataflow problem. - mlocDataflow(MInLocs, MOutLocs, MLocTransfer); + buildMLocValueMap(MF, MInLocs, MOutLocs, MLocTransfer); // Patch up debug phi numbers, turning unknown block-live-in values into // either live-through machine values, or PHIs. @@ -3626,6 +2967,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise // the order is unimportant, it just has to be stable. + unsigned VarAssignCount = 0; for (unsigned int I = 0; I < OrderToBB.size(); ++I) { auto *MBB = OrderToBB[I]; auto *VTracker = &vlocs[MBB->getNumber()]; @@ -3643,24 +2985,42 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, ScopeToVars[Scope].insert(Var); ScopeToBlocks[Scope].insert(VTracker->MBB); ScopeToDILocation[Scope] = ScopeLoc; + ++VarAssignCount; } } - // OK. Iterate over scopes: there might be something to be said for - // ordering them by size/locality, but that's for the future. For each scope, - // solve the variable value problem, producing a map of variables to values - // in SavedLiveIns. - for (auto &P : ScopeToVars) { - vlocDataflow(P.first, ScopeToDILocation[P.first], P.second, - ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs, - vlocs); - } + bool Changed = false; + + // If we have an extremely large number of variable assignments and blocks, + // bail out at this point. We've burnt some time doing analysis already, + // however we should cut our losses. + if ((unsigned)MaxNumBlocks > InputBBLimit && + VarAssignCount > InputDbgValLimit) { + LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName() + << " has " << MaxNumBlocks << " basic blocks and " + << VarAssignCount + << " variable assignments, exceeding limits.\n"); + } else { + // Compute the extended ranges, iterating over scopes. There might be + // something to be said for ordering them by size/locality, but that's for + // the future. For each scope, solve the variable value problem, producing + // a map of variables to values in SavedLiveIns. + for (auto &P : ScopeToVars) { + buildVLocValueMap(ScopeToDILocation[P.first], P.second, + ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs, + vlocs); + } + + // Using the computed value locations and variable values for each block, + // create the DBG_VALUE instructions representing the extended variable + // locations. + emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC); - // Using the computed value locations and variable values for each block, - // create the DBG_VALUE instructions representing the extended variable - // locations. - emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC); + // Did we actually make any changes? If we created any DBG_VALUEs, then yes. + Changed = TTracker->Transfers.size() != 0; + } + // Common clean-up of memory. for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) { delete[] MOutLocs[Idx]; delete[] MInLocs[Idx]; @@ -3668,9 +3028,6 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF, delete[] MOutLocs; delete[] MInLocs; - // Did we actually make any changes? If we created any DBG_VALUEs, then yes. - bool Changed = TTracker->Transfers.size() != 0; - delete MTracker; delete TTracker; MTracker = nullptr; @@ -3883,10 +3240,8 @@ public: /// vector. static void FindPredecessorBlocks(LDVSSABlock *BB, SmallVectorImpl<LDVSSABlock *> *Preds) { - for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(), - E = BB->BB.pred_end(); - PI != E; ++PI) - Preds->push_back(BB->Updater.getSSALDVBlock(*PI)); + for (MachineBasicBlock *Pred : BB->BB.predecessors()) + Preds->push_back(BB->Updater.getSSALDVBlock(Pred)); } /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new |