1530 lines · c
1//===- InstrRefBasedImpl.h - Tracking Debug Value MIs ---------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H10#define LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H11 12#include "llvm/ADT/DenseMap.h"13#include "llvm/ADT/IndexedMap.h"14#include "llvm/ADT/SmallPtrSet.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/UniqueVector.h"17#include "llvm/CodeGen/LexicalScopes.h"18#include "llvm/CodeGen/MachineBasicBlock.h"19#include "llvm/CodeGen/MachineInstr.h"20#include "llvm/CodeGen/TargetRegisterInfo.h"21#include "llvm/IR/DebugInfoMetadata.h"22#include "llvm/Support/Compiler.h"23#include <optional>24 25#include "LiveDebugValues.h"26 27class TransferTracker;28 29// Forward dec of unit test class, so that we can peer into the LDV object.30class InstrRefLDVTest;31 32namespace LiveDebugValues {33 34class MLocTracker;35class DbgOpIDMap;36 37using namespace llvm;38 39using DebugVariableID = unsigned;40using VarAndLoc = std::pair<DebugVariable, const DILocation *>;41 42/// Mapping from DebugVariable to/from a unique identifying number. Each43/// DebugVariable consists of three pointers, and after a small amount of44/// work to identify overlapping fragments of variables we mostly only use45/// DebugVariables as identities of variables. It's much more compile-time46/// efficient to use an ID number instead, which this class provides.47class DebugVariableMap {48 DenseMap<DebugVariable, unsigned> VarToIdx;49 SmallVector<VarAndLoc> IdxToVar;50 51public:52 DebugVariableID getDVID(const DebugVariable &Var) const {53 auto It = VarToIdx.find(Var);54 assert(It != VarToIdx.end());55 return It->second;56 }57 58 DebugVariableID insertDVID(DebugVariable &Var, const DILocation *Loc) {59 unsigned Size = VarToIdx.size();60 auto ItPair = VarToIdx.insert({Var, Size});61 if (ItPair.second) {62 IdxToVar.push_back({Var, Loc});63 return Size;64 }65 66 return ItPair.first->second;67 }68 69 const VarAndLoc &lookupDVID(DebugVariableID ID) const { return IdxToVar[ID]; }70 71 void clear() {72 VarToIdx.clear();73 IdxToVar.clear();74 }75};76 77/// Handle-class for a particular "location". This value-type uniquely78/// symbolises a register or stack location, allowing manipulation of locations79/// without concern for where that location is. Practically, this allows us to80/// treat the state of the machine at a particular point as an array of values,81/// rather than a map of values.82class LocIdx {83 unsigned Location;84 85 // Default constructor is private, initializing to an illegal location number.86 // Use only for "not an entry" elements in IndexedMaps.87 LocIdx() : Location(UINT_MAX) {}88 89public:90#define NUM_LOC_BITS 2491 LocIdx(unsigned L) : Location(L) {92 assert(L < (1 << NUM_LOC_BITS) && "Machine locations must fit in 24 bits");93 }94 95 static LocIdx MakeIllegalLoc() { return LocIdx(); }96 static LocIdx MakeTombstoneLoc() {97 LocIdx L = LocIdx();98 --L.Location;99 return L;100 }101 102 bool isIllegal() const { return Location == UINT_MAX; }103 104 uint64_t asU64() const { return Location; }105 106 bool operator==(unsigned L) const { return Location == L; }107 108 bool operator==(const LocIdx &L) const { return Location == L.Location; }109 110 bool operator!=(unsigned L) const { return !(*this == L); }111 112 bool operator!=(const LocIdx &L) const { return !(*this == L); }113 114 bool operator<(const LocIdx &Other) const {115 return Location < Other.Location;116 }117};118 119// The location at which a spilled value resides. It consists of a register and120// an offset.121struct SpillLoc {122 unsigned SpillBase;123 StackOffset SpillOffset;124 bool operator==(const SpillLoc &Other) const {125 return std::make_pair(SpillBase, SpillOffset) ==126 std::make_pair(Other.SpillBase, Other.SpillOffset);127 }128 bool operator<(const SpillLoc &Other) const {129 return std::make_tuple(SpillBase, SpillOffset.getFixed(),130 SpillOffset.getScalable()) <131 std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),132 Other.SpillOffset.getScalable());133 }134};135 136/// Unique identifier for a value defined by an instruction, as a value type.137/// Casts back and forth to a uint64_t. Probably replacable with something less138/// bit-constrained. Each value identifies the instruction and machine location139/// where the value is defined, although there may be no corresponding machine140/// operand for it (ex: regmasks clobbering values). The instructions are141/// one-based, and definitions that are PHIs have instruction number zero.142///143/// The obvious limits of a 1M block function or 1M instruction blocks are144/// problematic; but by that point we should probably have bailed out of145/// trying to analyse the function.146class ValueIDNum {147 union {148 struct {149 uint64_t BlockNo : 20; /// The block where the def happens.150 uint64_t InstNo : 20; /// The Instruction where the def happens.151 /// One based, is distance from start of block.152 uint64_t LocNo153 : NUM_LOC_BITS; /// The machine location where the def happens.154 } s;155 uint64_t Value;156 } u;157 158 static_assert(sizeof(u) == 8, "Badly packed ValueIDNum?");159 160public:161 // Default-initialize to EmptyValue. This is necessary to make IndexedMaps162 // of values to work.163 ValueIDNum() { u.Value = EmptyValue.asU64(); }164 165 ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc) {166 u.s = {Block, Inst, Loc};167 }168 169 ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) {170 u.s = {Block, Inst, Loc.asU64()};171 }172 173 uint64_t getBlock() const { return u.s.BlockNo; }174 uint64_t getInst() const { return u.s.InstNo; }175 uint64_t getLoc() const { return u.s.LocNo; }176 bool isPHI() const { return u.s.InstNo == 0; }177 178 uint64_t asU64() const { return u.Value; }179 180 static ValueIDNum fromU64(uint64_t v) {181 ValueIDNum Val;182 Val.u.Value = v;183 return Val;184 }185 186 bool operator<(const ValueIDNum &Other) const {187 return asU64() < Other.asU64();188 }189 190 bool operator==(const ValueIDNum &Other) const {191 return u.Value == Other.u.Value;192 }193 194 bool operator!=(const ValueIDNum &Other) const { return !(*this == Other); }195 196 std::string asString(const std::string &mlocname) const {197 return Twine("Value{bb: ")198 .concat(Twine(u.s.BlockNo)199 .concat(Twine(", inst: ")200 .concat((u.s.InstNo ? Twine(u.s.InstNo)201 : Twine("live-in"))202 .concat(Twine(", loc: ").concat(203 Twine(mlocname)))204 .concat(Twine("}")))))205 .str();206 }207 208 LLVM_ABI_FOR_TEST static ValueIDNum EmptyValue;209 LLVM_ABI_FOR_TEST static ValueIDNum TombstoneValue;210};211 212} // End namespace LiveDebugValues213 214namespace llvm {215using namespace LiveDebugValues;216 217template <> struct DenseMapInfo<LocIdx> {218 static inline LocIdx getEmptyKey() { return LocIdx::MakeIllegalLoc(); }219 static inline LocIdx getTombstoneKey() { return LocIdx::MakeTombstoneLoc(); }220 221 static unsigned getHashValue(const LocIdx &Loc) { return Loc.asU64(); }222 223 static bool isEqual(const LocIdx &A, const LocIdx &B) { return A == B; }224};225 226template <> struct DenseMapInfo<ValueIDNum> {227 static inline ValueIDNum getEmptyKey() { return ValueIDNum::EmptyValue; }228 static inline ValueIDNum getTombstoneKey() {229 return ValueIDNum::TombstoneValue;230 }231 232 static unsigned getHashValue(const ValueIDNum &Val) {233 return hash_value(Val.asU64());234 }235 236 static bool isEqual(const ValueIDNum &A, const ValueIDNum &B) {237 return A == B;238 }239};240 241} // end namespace llvm242 243namespace LiveDebugValues {244using namespace llvm;245 246/// Type for a table of values in a block.247using ValueTable = SmallVector<ValueIDNum, 0>;248 249/// A collection of ValueTables, one per BB in a function, with convenient250/// accessor methods.251struct FuncValueTable {252 FuncValueTable(int NumBBs, int NumLocs) {253 Storage.reserve(NumBBs);254 for (int i = 0; i != NumBBs; ++i)255 Storage.push_back(256 std::make_unique<ValueTable>(NumLocs, ValueIDNum::EmptyValue));257 }258 259 /// Returns the ValueTable associated with MBB.260 ValueTable &operator[](const MachineBasicBlock &MBB) const {261 return (*this)[MBB.getNumber()];262 }263 264 /// Returns the ValueTable associated with the MachineBasicBlock whose number265 /// is MBBNum.266 ValueTable &operator[](int MBBNum) const {267 auto &TablePtr = Storage[MBBNum];268 assert(TablePtr && "Trying to access a deleted table");269 return *TablePtr;270 }271 272 /// Returns the ValueTable associated with the entry MachineBasicBlock.273 ValueTable &tableForEntryMBB() const { return (*this)[0]; }274 275 /// Returns true if the ValueTable associated with MBB has not been freed.276 bool hasTableFor(MachineBasicBlock &MBB) const {277 return Storage[MBB.getNumber()] != nullptr;278 }279 280 /// Frees the memory of the ValueTable associated with MBB.281 void ejectTableForBlock(const MachineBasicBlock &MBB) {282 Storage[MBB.getNumber()].reset();283 }284 285private:286 /// ValueTables are stored as unique_ptrs to allow for deallocation during287 /// LDV; this was measured to have a significant impact on compiler memory288 /// usage.289 SmallVector<std::unique_ptr<ValueTable>, 0> Storage;290};291 292/// Thin wrapper around an integer -- designed to give more type safety to293/// spill location numbers.294class SpillLocationNo {295public:296 explicit SpillLocationNo(unsigned SpillNo) : SpillNo(SpillNo) {}297 unsigned SpillNo;298 unsigned id() const { return SpillNo; }299 300 bool operator<(const SpillLocationNo &Other) const {301 return SpillNo < Other.SpillNo;302 }303 304 bool operator==(const SpillLocationNo &Other) const {305 return SpillNo == Other.SpillNo;306 }307 bool operator!=(const SpillLocationNo &Other) const {308 return !(*this == Other);309 }310};311 312/// Meta qualifiers for a value. Pair of whatever expression is used to qualify313/// the value, and Boolean of whether or not it's indirect.314class DbgValueProperties {315public:316 DbgValueProperties(const DIExpression *DIExpr, bool Indirect, bool IsVariadic)317 : DIExpr(DIExpr), Indirect(Indirect), IsVariadic(IsVariadic) {}318 319 /// Extract properties from an existing DBG_VALUE instruction.320 DbgValueProperties(const MachineInstr &MI) {321 assert(MI.isDebugValue());322 assert(MI.getDebugExpression()->getNumLocationOperands() == 0 ||323 MI.isDebugValueList() || MI.isUndefDebugValue());324 IsVariadic = MI.isDebugValueList();325 DIExpr = MI.getDebugExpression();326 Indirect = MI.isDebugOffsetImm();327 }328 329 bool isJoinable(const DbgValueProperties &Other) const {330 return DIExpression::isEqualExpression(DIExpr, Indirect, Other.DIExpr,331 Other.Indirect);332 }333 334 bool operator==(const DbgValueProperties &Other) const {335 return std::tie(DIExpr, Indirect, IsVariadic) ==336 std::tie(Other.DIExpr, Other.Indirect, Other.IsVariadic);337 }338 339 bool operator!=(const DbgValueProperties &Other) const {340 return !(*this == Other);341 }342 343 unsigned getLocationOpCount() const {344 return IsVariadic ? DIExpr->getNumLocationOperands() : 1;345 }346 347 const DIExpression *DIExpr;348 bool Indirect;349 bool IsVariadic;350};351 352/// TODO: Might pack better if we changed this to a Struct of Arrays, since353/// MachineOperand is width 32, making this struct width 33. We could also354/// potentially avoid storing the whole MachineOperand (sizeof=32), instead355/// choosing to store just the contents portion (sizeof=8) and a Kind enum,356/// since we already know it is some type of immediate value.357/// Stores a single debug operand, which can either be a MachineOperand for358/// directly storing immediate values, or a ValueIDNum representing some value359/// computed at some point in the program. IsConst is used as a discriminator.360struct DbgOp {361 union {362 ValueIDNum ID;363 MachineOperand MO;364 };365 bool IsConst;366 367 DbgOp() : ID(ValueIDNum::EmptyValue), IsConst(false) {}368 DbgOp(ValueIDNum ID) : ID(ID), IsConst(false) {}369 DbgOp(MachineOperand MO) : MO(MO), IsConst(true) {}370 371 bool isUndef() const { return !IsConst && ID == ValueIDNum::EmptyValue; }372 373#ifndef NDEBUG374 void dump(const MLocTracker *MTrack) const;375#endif376};377 378/// A DbgOp whose ID (if any) has resolved to an actual location, LocIdx. Used379/// when working with concrete debug values, i.e. when joining MLocs and VLocs380/// in the TransferTracker or emitting DBG_VALUE/DBG_VALUE_LIST instructions in381/// the MLocTracker.382struct ResolvedDbgOp {383 union {384 LocIdx Loc;385 MachineOperand MO;386 };387 bool IsConst;388 389 ResolvedDbgOp(LocIdx Loc) : Loc(Loc), IsConst(false) {}390 ResolvedDbgOp(MachineOperand MO) : MO(MO), IsConst(true) {}391 392 bool operator==(const ResolvedDbgOp &Other) const {393 if (IsConst != Other.IsConst)394 return false;395 if (IsConst)396 return MO.isIdenticalTo(Other.MO);397 return Loc == Other.Loc;398 }399 400#ifndef NDEBUG401 void dump(const MLocTracker *MTrack) const;402#endif403};404 405/// An ID used in the DbgOpIDMap (below) to lookup a stored DbgOp. This is used406/// in place of actual DbgOps inside of a DbgValue to reduce its size, as407/// DbgValue is very frequently used and passed around, and the actual DbgOp is408/// over 8x larger than this class, due to storing a MachineOperand. This ID409/// should be equal for all equal DbgOps, and also encodes whether the mapped410/// DbgOp is a constant, meaning that for simple equality or const-ness checks411/// it is not necessary to lookup this ID.412struct DbgOpID {413 struct IsConstIndexPair {414 uint32_t IsConst : 1;415 uint32_t Index : 31;416 };417 418 union {419 struct IsConstIndexPair ID;420 uint32_t RawID;421 };422 423 DbgOpID() : RawID(UndefID.RawID) {424 static_assert(sizeof(DbgOpID) == 4, "DbgOpID should fit within 4 bytes.");425 }426 DbgOpID(uint32_t RawID) : RawID(RawID) {}427 DbgOpID(bool IsConst, uint32_t Index) : ID({IsConst, Index}) {}428 429 LLVM_ABI_FOR_TEST static DbgOpID UndefID;430 431 bool operator==(const DbgOpID &Other) const { return RawID == Other.RawID; }432 bool operator!=(const DbgOpID &Other) const { return !(*this == Other); }433 434 uint32_t asU32() const { return RawID; }435 436 bool isUndef() const { return *this == UndefID; }437 bool isConst() const { return ID.IsConst && !isUndef(); }438 uint32_t getIndex() const { return ID.Index; }439 440#ifndef NDEBUG441 void dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const;442#endif443};444 445/// Class storing the complete set of values that are observed by DbgValues446/// within the current function. Allows 2-way lookup, with `find` returning the447/// Op for a given ID and `insert` returning the ID for a given Op (creating one448/// if none exists).449class DbgOpIDMap {450 451 SmallVector<ValueIDNum, 0> ValueOps;452 SmallVector<MachineOperand, 0> ConstOps;453 454 DenseMap<ValueIDNum, DbgOpID> ValueOpToID;455 DenseMap<MachineOperand, DbgOpID> ConstOpToID;456 457public:458 /// If \p Op does not already exist in this map, it is inserted and the459 /// corresponding DbgOpID is returned. If Op already exists in this map, then460 /// no change is made and the existing ID for Op is returned.461 /// Calling this with the undef DbgOp will always return DbgOpID::UndefID.462 DbgOpID insert(DbgOp Op) {463 if (Op.isUndef())464 return DbgOpID::UndefID;465 if (Op.IsConst)466 return insertConstOp(Op.MO);467 return insertValueOp(Op.ID);468 }469 /// Returns the DbgOp associated with \p ID. Should only be used for IDs470 /// returned from calling `insert` from this map or DbgOpID::UndefID.471 DbgOp find(DbgOpID ID) const {472 if (ID == DbgOpID::UndefID)473 return DbgOp();474 if (ID.isConst())475 return DbgOp(ConstOps[ID.getIndex()]);476 return DbgOp(ValueOps[ID.getIndex()]);477 }478 479 void clear() {480 ValueOps.clear();481 ConstOps.clear();482 ValueOpToID.clear();483 ConstOpToID.clear();484 }485 486private:487 DbgOpID insertConstOp(MachineOperand &MO) {488 auto [It, Inserted] = ConstOpToID.try_emplace(MO, true, ConstOps.size());489 if (Inserted)490 ConstOps.push_back(MO);491 return It->second;492 }493 DbgOpID insertValueOp(ValueIDNum VID) {494 auto [It, Inserted] = ValueOpToID.try_emplace(VID, false, ValueOps.size());495 if (Inserted)496 ValueOps.push_back(VID);497 return It->second;498 }499};500 501// We set the maximum number of operands that we will handle to keep DbgValue502// within a reasonable size (64 bytes), as we store and pass a lot of them503// around.504#define MAX_DBG_OPS 8505 506/// Class recording the (high level) _value_ of a variable. Identifies the value507/// of the variable as a list of ValueIDNums and constant MachineOperands, or as508/// an empty list for undef debug values or VPHI values which we have not found509/// valid locations for.510/// This class also stores meta-information about how the value is qualified.511/// Used to reason about variable values when performing the second512/// (DebugVariable specific) dataflow analysis.513class DbgValue {514private:515 /// If Kind is Def or VPHI, the set of IDs corresponding to the DbgOps that516 /// are used. VPHIs set every ID to EmptyID when we have not found a valid517 /// machine-value for every operand, and sets them to the corresponding518 /// machine-values when we have found all of them.519 DbgOpID DbgOps[MAX_DBG_OPS];520 unsigned OpCount;521 522public:523 /// For a NoVal or VPHI DbgValue, which block it was generated in.524 int BlockNo;525 526 /// Qualifiers for the ValueIDNum above.527 DbgValueProperties Properties;528 529 typedef enum {530 Undef, // Represents a DBG_VALUE $noreg in the transfer function only.531 Def, // This value is defined by some combination of constants,532 // instructions, or PHI values.533 VPHI, // Incoming values to BlockNo differ, those values must be joined by534 // a PHI in this block.535 NoVal, // Empty DbgValue indicating an unknown value. Used as initializer,536 // before dominating blocks values are propagated in.537 } KindT;538 /// Discriminator for whether this is a constant or an in-program value.539 KindT Kind;540 541 DbgValue(ArrayRef<DbgOpID> DbgOps, const DbgValueProperties &Prop)542 : OpCount(DbgOps.size()), BlockNo(0), Properties(Prop), Kind(Def) {543 static_assert(sizeof(DbgValue) <= 64,544 "DbgValue should fit within 64 bytes.");545 assert(DbgOps.size() == Prop.getLocationOpCount());546 if (DbgOps.size() > MAX_DBG_OPS ||547 any_of(DbgOps, [](DbgOpID ID) { return ID.isUndef(); })) {548 Kind = Undef;549 OpCount = 0;550#define DEBUG_TYPE "LiveDebugValues"551 if (DbgOps.size() > MAX_DBG_OPS) {552 LLVM_DEBUG(dbgs() << "Found DbgValue with more than maximum allowed "553 "operands.\n");554 }555#undef DEBUG_TYPE556 } else {557 for (unsigned Idx = 0; Idx < DbgOps.size(); ++Idx)558 this->DbgOps[Idx] = DbgOps[Idx];559 }560 }561 562 DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)563 : OpCount(0), BlockNo(BlockNo), Properties(Prop), Kind(Kind) {564 assert(Kind == NoVal || Kind == VPHI);565 }566 567 DbgValue(const DbgValueProperties &Prop, KindT Kind)568 : OpCount(0), BlockNo(0), Properties(Prop), Kind(Kind) {569 assert(Kind == Undef &&570 "Empty DbgValue constructor must pass in Undef kind");571 }572 573#ifndef NDEBUG574 void dump(const MLocTracker *MTrack = nullptr,575 const DbgOpIDMap *OpStore = nullptr) const;576#endif577 578 bool operator==(const DbgValue &Other) const {579 if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties))580 return false;581 else if (Kind == Def && !equal(getDbgOpIDs(), Other.getDbgOpIDs()))582 return false;583 else if (Kind == NoVal && BlockNo != Other.BlockNo)584 return false;585 else if (Kind == VPHI && BlockNo != Other.BlockNo)586 return false;587 else if (Kind == VPHI && !equal(getDbgOpIDs(), Other.getDbgOpIDs()))588 return false;589 590 return true;591 }592 593 bool operator!=(const DbgValue &Other) const { return !(*this == Other); }594 595 // Returns an array of all the machine values used to calculate this variable596 // value, or an empty list for an Undef or unjoined VPHI.597 ArrayRef<DbgOpID> getDbgOpIDs() const { return {DbgOps, OpCount}; }598 599 // Returns either DbgOps[Index] if this DbgValue has Debug Operands, or600 // the ID for ValueIDNum::EmptyValue otherwise (i.e. if this is an Undef,601 // NoVal, or an unjoined VPHI).602 DbgOpID getDbgOpID(unsigned Index) const {603 if (!OpCount)604 return DbgOpID::UndefID;605 assert(Index < OpCount);606 return DbgOps[Index];607 }608 // Replaces this DbgValue's existing DbgOpIDs (if any) with the contents of609 // \p NewIDs. The number of DbgOpIDs passed must be equal to the number of610 // arguments expected by this DbgValue's properties (the return value of611 // `getLocationOpCount()`).612 void setDbgOpIDs(ArrayRef<DbgOpID> NewIDs) {613 // We can go from no ops to some ops, but not from some ops to no ops.614 assert(NewIDs.size() == getLocationOpCount() &&615 "Incorrect number of Debug Operands for this DbgValue.");616 OpCount = NewIDs.size();617 for (unsigned Idx = 0; Idx < NewIDs.size(); ++Idx)618 DbgOps[Idx] = NewIDs[Idx];619 }620 621 // The number of debug operands expected by this DbgValue's expression.622 // getDbgOpIDs() should return an array of this length, unless this is an623 // Undef or an unjoined VPHI.624 unsigned getLocationOpCount() const {625 return Properties.getLocationOpCount();626 }627 628 // Returns true if this or Other are unjoined PHIs, which do not have defined629 // Loc Ops, or if the `n`th Loc Op for this has a different constness to the630 // `n`th Loc Op for Other.631 bool hasJoinableLocOps(const DbgValue &Other) const {632 if (isUnjoinedPHI() || Other.isUnjoinedPHI())633 return true;634 for (unsigned Idx = 0; Idx < getLocationOpCount(); ++Idx) {635 if (getDbgOpID(Idx).isConst() != Other.getDbgOpID(Idx).isConst())636 return false;637 }638 return true;639 }640 641 bool isUnjoinedPHI() const { return Kind == VPHI && OpCount == 0; }642 643 bool hasIdenticalValidLocOps(const DbgValue &Other) const {644 if (!OpCount)645 return false;646 return equal(getDbgOpIDs(), Other.getDbgOpIDs());647 }648};649 650class LocIdxToIndexFunctor {651public:652 using argument_type = LocIdx;653 unsigned operator()(const LocIdx &L) const { return L.asU64(); }654};655 656/// Tracker for what values are in machine locations. Listens to the Things657/// being Done by various instructions, and maintains a table of what machine658/// locations have what values (as defined by a ValueIDNum).659///660/// There are potentially a much larger number of machine locations on the661/// target machine than the actual working-set size of the function. On x86 for662/// example, we're extremely unlikely to want to track values through control663/// or debug registers. To avoid doing so, MLocTracker has several layers of664/// indirection going on, described below, to avoid unnecessarily tracking665/// any location.666///667/// Here's a sort of diagram of the indexes, read from the bottom up:668///669/// Size on stack Offset on stack670/// \ /671/// Stack Idx (Where in slot is this?)672/// /673/// /674/// Slot Num (%stack.0) /675/// FrameIdx => SpillNum /676/// \ /677/// SpillID (int) Register number (int)678/// \ /679/// LocationID => LocIdx680/// |681/// LocIdx => ValueIDNum682///683/// The aim here is that the LocIdx => ValueIDNum vector is just an array of684/// values in numbered locations, so that later analyses can ignore whether the685/// location is a register or otherwise. To map a register / spill location to686/// a LocIdx, you have to use the (sparse) LocationID => LocIdx map. And to687/// build a LocationID for a stack slot, you need to combine identifiers for688/// which stack slot it is and where within that slot is being described.689///690/// Register mask operands cause trouble by technically defining every register;691/// various hacks are used to avoid tracking registers that are never read and692/// only written by regmasks.693class MLocTracker {694public:695 MachineFunction &MF;696 const TargetInstrInfo &TII;697 const TargetRegisterInfo &TRI;698 const TargetLowering &TLI;699 700 /// IndexedMap type, mapping from LocIdx to ValueIDNum.701 using LocToValueType = IndexedMap<ValueIDNum, LocIdxToIndexFunctor>;702 703 /// Map of LocIdxes to the ValueIDNums that they store. This is tightly704 /// packed, entries only exist for locations that are being tracked.705 LocToValueType LocIdxToIDNum;706 707 /// "Map" of machine location IDs (i.e., raw register or spill number) to the708 /// LocIdx key / number for that location. There are always at least as many709 /// as the number of registers on the target -- if the value in the register710 /// is not being tracked, then the LocIdx value will be zero. New entries are711 /// appended if a new spill slot begins being tracked.712 /// This, and the corresponding reverse map persist for the analysis of the713 /// whole function, and is necessarying for decoding various vectors of714 /// values.715 std::vector<LocIdx> LocIDToLocIdx;716 717 /// Inverse map of LocIDToLocIdx.718 IndexedMap<unsigned, LocIdxToIndexFunctor> LocIdxToLocID;719 720 /// When clobbering register masks, we chose to not believe the machine model721 /// and don't clobber SP. Do the same for SP aliases, and for efficiency,722 /// keep a set of them here.723 SmallSet<Register, 8> SPAliases;724 725 /// Unique-ification of spill. Used to number them -- their LocID number is726 /// the index in SpillLocs minus one plus NumRegs.727 UniqueVector<SpillLoc> SpillLocs;728 729 // If we discover a new machine location, assign it an mphi with this730 // block number.731 unsigned CurBB = -1;732 733 /// Cached local copy of the number of registers the target has.734 unsigned NumRegs;735 736 /// Number of slot indexes the target has -- distinct segments of a stack737 /// slot that can take on the value of a subregister, when a super-register738 /// is written to the stack.739 unsigned NumSlotIdxes;740 741 /// Collection of register mask operands that have been observed. Second part742 /// of pair indicates the instruction that they happened in. Used to743 /// reconstruct where defs happened if we start tracking a location later744 /// on.745 SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks;746 747 /// Pair for describing a position within a stack slot -- first the size in748 /// bits, then the offset.749 typedef std::pair<unsigned short, unsigned short> StackSlotPos;750 751 /// Map from a size/offset pair describing a position in a stack slot, to a752 /// numeric identifier for that position. Allows easier identification of753 /// individual positions.754 DenseMap<StackSlotPos, unsigned> StackSlotIdxes;755 756 /// Inverse of StackSlotIdxes.757 DenseMap<unsigned, StackSlotPos> StackIdxesToPos;758 759 /// Iterator for locations and the values they contain. Dereferencing760 /// produces a struct/pair containing the LocIdx key for this location,761 /// and a reference to the value currently stored. Simplifies the process762 /// of seeking a particular location.763 class MLocIterator {764 LocToValueType &ValueMap;765 LocIdx Idx;766 767 public:768 class value_type {769 public:770 value_type(LocIdx Idx, ValueIDNum &Value) : Idx(Idx), Value(Value) {}771 const LocIdx Idx; /// Read-only index of this location.772 ValueIDNum &Value; /// Reference to the stored value at this location.773 };774 775 MLocIterator(LocToValueType &ValueMap, LocIdx Idx)776 : ValueMap(ValueMap), Idx(Idx) {}777 778 bool operator==(const MLocIterator &Other) const {779 assert(&ValueMap == &Other.ValueMap);780 return Idx == Other.Idx;781 }782 783 bool operator!=(const MLocIterator &Other) const {784 return !(*this == Other);785 }786 787 void operator++() { Idx = LocIdx(Idx.asU64() + 1); }788 789 value_type operator*() { return value_type(Idx, ValueMap[LocIdx(Idx)]); }790 };791 792 LLVM_ABI_FOR_TEST MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,793 const TargetRegisterInfo &TRI,794 const TargetLowering &TLI);795 796 /// Produce location ID number for a Register. Provides some small amount of797 /// type safety.798 /// \param Reg The register we're looking up.799 unsigned getLocID(Register Reg) { return Reg.id(); }800 801 /// Produce location ID number for a spill position.802 /// \param Spill The number of the spill we're fetching the location for.803 /// \param SpillSubReg Subregister within the spill we're addressing.804 unsigned getLocID(SpillLocationNo Spill, unsigned SpillSubReg) {805 unsigned short Size = TRI.getSubRegIdxSize(SpillSubReg);806 unsigned short Offs = TRI.getSubRegIdxOffset(SpillSubReg);807 return getLocID(Spill, {Size, Offs});808 }809 810 /// Produce location ID number for a spill position.811 /// \param Spill The number of the spill we're fetching the location for.812 /// \apram SpillIdx size/offset within the spill slot to be addressed.813 unsigned getLocID(SpillLocationNo Spill, StackSlotPos Idx) {814 unsigned SlotNo = Spill.id() - 1;815 SlotNo *= NumSlotIdxes;816 assert(StackSlotIdxes.contains(Idx));817 SlotNo += StackSlotIdxes[Idx];818 SlotNo += NumRegs;819 return SlotNo;820 }821 822 /// Given a spill number, and a slot within the spill, calculate the ID number823 /// for that location.824 unsigned getSpillIDWithIdx(SpillLocationNo Spill, unsigned Idx) {825 unsigned SlotNo = Spill.id() - 1;826 SlotNo *= NumSlotIdxes;827 SlotNo += Idx;828 SlotNo += NumRegs;829 return SlotNo;830 }831 832 /// Return the spill number that a location ID corresponds to.833 SpillLocationNo locIDToSpill(unsigned ID) const {834 assert(ID >= NumRegs);835 ID -= NumRegs;836 // Truncate away the index part, leaving only the spill number.837 ID /= NumSlotIdxes;838 return SpillLocationNo(ID + 1); // The UniqueVector is one-based.839 }840 841 /// Returns the spill-slot size/offs that a location ID corresponds to.842 StackSlotPos locIDToSpillIdx(unsigned ID) const {843 assert(ID >= NumRegs);844 ID -= NumRegs;845 unsigned Idx = ID % NumSlotIdxes;846 return StackIdxesToPos.find(Idx)->second;847 }848 849 unsigned getNumLocs() const { return LocIdxToIDNum.size(); }850 851 /// Reset all locations to contain a PHI value at the designated block. Used852 /// sometimes for actual PHI values, othertimes to indicate the block entry853 /// value (before any more information is known).854 void setMPhis(unsigned NewCurBB) {855 CurBB = NewCurBB;856 for (auto Location : locations())857 Location.Value = {CurBB, 0, Location.Idx};858 }859 860 /// Load values for each location from array of ValueIDNums. Take current861 /// bbnum just in case we read a value from a hitherto untouched register.862 void loadFromArray(ValueTable &Locs, unsigned NewCurBB) {863 CurBB = NewCurBB;864 // Iterate over all tracked locations, and load each locations live-in865 // value into our local index.866 for (auto Location : locations())867 Location.Value = Locs[Location.Idx.asU64()];868 }869 870 /// Wipe any un-necessary location records after traversing a block.871 void reset() {872 // We could reset all the location values too; however either loadFromArray873 // or setMPhis should be called before this object is re-used. Just874 // clear Masks, they're definitely not needed.875 Masks.clear();876 }877 878 /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of879 /// the information in this pass uninterpretable.880 void clear() {881 reset();882 LocIDToLocIdx.clear();883 LocIdxToLocID.clear();884 LocIdxToIDNum.clear();885 // SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from886 // 0887 SpillLocs = decltype(SpillLocs)();888 StackSlotIdxes.clear();889 StackIdxesToPos.clear();890 891 LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());892 }893 894 /// Set a locaiton to a certain value.895 void setMLoc(LocIdx L, ValueIDNum Num) {896 assert(L.asU64() < LocIdxToIDNum.size());897 LocIdxToIDNum[L] = Num;898 }899 900 /// Read the value of a particular location901 ValueIDNum readMLoc(LocIdx L) {902 assert(L.asU64() < LocIdxToIDNum.size());903 return LocIdxToIDNum[L];904 }905 906 /// Create a LocIdx for an untracked register ID. Initialize it to either an907 /// mphi value representing a live-in, or a recent register mask clobber.908 LLVM_ABI_FOR_TEST LocIdx trackRegister(unsigned ID);909 910 LocIdx lookupOrTrackRegister(unsigned ID) {911 LocIdx &Index = LocIDToLocIdx[ID];912 if (Index.isIllegal())913 Index = trackRegister(ID);914 return Index;915 }916 917 /// Is register R currently tracked by MLocTracker?918 bool isRegisterTracked(Register R) {919 LocIdx &Index = LocIDToLocIdx[R];920 return !Index.isIllegal();921 }922 923 /// Record a definition of the specified register at the given block / inst.924 /// This doesn't take a ValueIDNum, because the definition and its location925 /// are synonymous.926 void defReg(Register R, unsigned BB, unsigned Inst) {927 unsigned ID = getLocID(R);928 LocIdx Idx = lookupOrTrackRegister(ID);929 ValueIDNum ValueID = {BB, Inst, Idx};930 LocIdxToIDNum[Idx] = ValueID;931 }932 933 /// Set a register to a value number. To be used if the value number is934 /// known in advance.935 void setReg(Register R, ValueIDNum ValueID) {936 unsigned ID = getLocID(R);937 LocIdx Idx = lookupOrTrackRegister(ID);938 LocIdxToIDNum[Idx] = ValueID;939 }940 941 ValueIDNum readReg(Register R) {942 unsigned ID = getLocID(R);943 LocIdx Idx = lookupOrTrackRegister(ID);944 return LocIdxToIDNum[Idx];945 }946 947 /// Reset a register value to zero / empty. Needed to replicate the948 /// VarLoc implementation where a copy to/from a register effectively949 /// clears the contents of the source register. (Values can only have one950 /// machine location in VarLocBasedImpl).951 void wipeRegister(Register R) {952 unsigned ID = getLocID(R);953 LocIdx Idx = LocIDToLocIdx[ID];954 LocIdxToIDNum[Idx] = ValueIDNum::EmptyValue;955 }956 957 /// Determine the LocIdx of an existing register.958 LocIdx getRegMLoc(Register R) {959 unsigned ID = getLocID(R);960 assert(ID < LocIDToLocIdx.size());961 assert(LocIDToLocIdx[ID] != UINT_MAX); // Sentinel for IndexedMap.962 return LocIDToLocIdx[ID];963 }964 965 /// Record a RegMask operand being executed. Defs any register we currently966 /// track, stores a pointer to the mask in case we have to account for it967 /// later.968 void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID);969 970 /// Find LocIdx for SpillLoc \p L, creating a new one if it's not tracked.971 /// Returns std::nullopt when in scenarios where a spill slot could be972 /// tracked, but we would likely run into resource limitations.973 LLVM_ABI_FOR_TEST std::optional<SpillLocationNo>974 getOrTrackSpillLoc(SpillLoc L);975 976 // Get LocIdx of a spill ID.977 LocIdx getSpillMLoc(unsigned SpillID) {978 assert(LocIDToLocIdx[SpillID] != UINT_MAX); // Sentinel for IndexedMap.979 return LocIDToLocIdx[SpillID];980 }981 982 /// Return true if Idx is a spill machine location.983 bool isSpill(LocIdx Idx) const { return LocIdxToLocID[Idx] >= NumRegs; }984 985 /// How large is this location (aka, how wide is a value defined there?).986 unsigned getLocSizeInBits(LocIdx L) const {987 unsigned ID = LocIdxToLocID[L];988 if (!isSpill(L)) {989 return TRI.getRegSizeInBits(Register(ID), MF.getRegInfo());990 } else {991 // The slot location on the stack is uninteresting, we care about the992 // position of the value within the slot (which comes with a size).993 StackSlotPos Pos = locIDToSpillIdx(ID);994 return Pos.first;995 }996 }997 998 MLocIterator begin() { return MLocIterator(LocIdxToIDNum, 0); }999 1000 MLocIterator end() {1001 return MLocIterator(LocIdxToIDNum, LocIdxToIDNum.size());1002 }1003 1004 /// Return a range over all locations currently tracked.1005 iterator_range<MLocIterator> locations() {1006 return llvm::make_range(begin(), end());1007 }1008 1009 std::string LocIdxToName(LocIdx Idx) const;1010 1011 std::string IDAsString(const ValueIDNum &Num) const;1012 1013#ifndef NDEBUG1014 LLVM_DUMP_METHOD void dump();1015 1016 LLVM_DUMP_METHOD void dump_mloc_map();1017#endif1018 1019 /// Create a DBG_VALUE based on debug operands \p DbgOps. Qualify it with the1020 /// information in \pProperties, for variable Var. Don't insert it anywhere,1021 /// just return the builder for it.1022 MachineInstrBuilder emitLoc(const SmallVectorImpl<ResolvedDbgOp> &DbgOps,1023 const DebugVariable &Var, const DILocation *DILoc,1024 const DbgValueProperties &Properties);1025};1026 1027/// Types for recording sets of variable fragments that overlap. For a given1028/// local variable, we record all other fragments of that variable that could1029/// overlap it, to reduce search time.1030using FragmentOfVar =1031 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;1032using OverlapMap =1033 DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;1034 1035/// Collection of DBG_VALUEs observed when traversing a block. Records each1036/// variable and the value the DBG_VALUE refers to. Requires the machine value1037/// location dataflow algorithm to have run already, so that values can be1038/// identified.1039class VLocTracker {1040public:1041 /// Ref to function-wide map of DebugVariable <=> ID-numbers.1042 DebugVariableMap &DVMap;1043 /// Map DebugVariable to the latest Value it's defined to have.1044 /// Needs to be a MapVector because we determine order-in-the-input-MIR from1045 /// the order in this container. (FIXME: likely no longer true as the ordering1046 /// is now provided by DebugVariableMap).1047 /// We only retain the last DbgValue in each block for each variable, to1048 /// determine the blocks live-out variable value. The Vars container forms the1049 /// transfer function for this block, as part of the dataflow analysis. The1050 /// movement of values between locations inside of a block is handled at a1051 /// much later stage, in the TransferTracker class.1052 SmallMapVector<DebugVariableID, DbgValue, 8> Vars;1053 SmallDenseMap<DebugVariableID, const DILocation *, 8> Scopes;1054 MachineBasicBlock *MBB = nullptr;1055 const OverlapMap &OverlappingFragments;1056 DbgValueProperties EmptyProperties;1057 1058public:1059 VLocTracker(DebugVariableMap &DVMap, const OverlapMap &O,1060 const DIExpression *EmptyExpr)1061 : DVMap(DVMap), OverlappingFragments(O),1062 EmptyProperties(EmptyExpr, false, false) {}1063 1064 void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,1065 const SmallVectorImpl<DbgOpID> &DebugOps) {1066 assert(MI.isDebugValueLike());1067 DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),1068 MI.getDebugLoc()->getInlinedAt());1069 // Either insert or fetch an ID number for this variable.1070 DebugVariableID VarID = DVMap.insertDVID(Var, MI.getDebugLoc().get());1071 DbgValue Rec = (DebugOps.size() > 0)1072 ? DbgValue(DebugOps, Properties)1073 : DbgValue(Properties, DbgValue::Undef);1074 1075 // Attempt insertion; overwrite if it's already mapped.1076 Vars.insert_or_assign(VarID, Rec);1077 Scopes[VarID] = MI.getDebugLoc().get();1078 1079 considerOverlaps(Var, MI.getDebugLoc().get());1080 }1081 1082 void considerOverlaps(const DebugVariable &Var, const DILocation *Loc) {1083 auto Overlaps = OverlappingFragments.find(1084 {Var.getVariable(), Var.getFragmentOrDefault()});1085 if (Overlaps == OverlappingFragments.end())1086 return;1087 1088 // Otherwise: terminate any overlapped variable locations.1089 for (auto FragmentInfo : Overlaps->second) {1090 // The "empty" fragment is stored as DebugVariable::DefaultFragment, so1091 // that it overlaps with everything, however its cannonical representation1092 // in a DebugVariable is as "None".1093 std::optional<DIExpression::FragmentInfo> OptFragmentInfo = FragmentInfo;1094 if (DebugVariable::isDefaultFragment(FragmentInfo))1095 OptFragmentInfo = std::nullopt;1096 1097 DebugVariable Overlapped(Var.getVariable(), OptFragmentInfo,1098 Var.getInlinedAt());1099 // Produce an ID number for this overlapping fragment of a variable.1100 DebugVariableID OverlappedID = DVMap.insertDVID(Overlapped, Loc);1101 DbgValue Rec = DbgValue(EmptyProperties, DbgValue::Undef);1102 1103 // Attempt insertion; overwrite if it's already mapped.1104 Vars.insert_or_assign(OverlappedID, Rec);1105 Scopes[OverlappedID] = Loc;1106 }1107 }1108 1109 void clear() {1110 Vars.clear();1111 Scopes.clear();1112 }1113};1114 1115// XXX XXX docs1116class InstrRefBasedLDV : public LDVImpl {1117public:1118 friend class ::InstrRefLDVTest;1119 1120 using FragmentInfo = DIExpression::FragmentInfo;1121 using OptFragmentInfo = std::optional<DIExpression::FragmentInfo>;1122 1123 // Helper while building OverlapMap, a map of all fragments seen for a given1124 // DILocalVariable.1125 using VarToFragments =1126 DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;1127 1128 /// Machine location/value transfer function, a mapping of which locations1129 /// are assigned which new values.1130 using MLocTransferMap = SmallDenseMap<LocIdx, ValueIDNum>;1131 1132 /// Live in/out structure for the variable values: a per-block map of1133 /// variables to their values.1134 using LiveIdxT = SmallDenseMap<const MachineBasicBlock *, DbgValue *, 16>;1135 1136 using VarAndLoc = std::pair<DebugVariableID, DbgValue>;1137 1138 /// Type for a live-in value: the predecessor block, and its value.1139 using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;1140 1141 /// Vector (per block) of a collection (inner smallvector) of live-ins.1142 /// Used as the result type for the variable value dataflow problem.1143 using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;1144 1145 /// Mapping from lexical scopes to a DILocation in that scope.1146 using ScopeToDILocT = DenseMap<const LexicalScope *, const DILocation *>;1147 1148 /// Mapping from lexical scopes to variables in that scope.1149 using ScopeToVarsT =1150 DenseMap<const LexicalScope *, SmallSet<DebugVariableID, 4>>;1151 1152 /// Mapping from lexical scopes to blocks where variables in that scope are1153 /// assigned. Such blocks aren't necessarily "in" the lexical scope, it's1154 /// just a block where an assignment happens.1155 using ScopeToAssignBlocksT = DenseMap<const LexicalScope *, SmallPtrSet<MachineBasicBlock *, 4>>;1156 1157private:1158 MachineDominatorTree *DomTree;1159 const TargetRegisterInfo *TRI;1160 const MachineRegisterInfo *MRI;1161 const TargetInstrInfo *TII;1162 const TargetFrameLowering *TFI;1163 const MachineFrameInfo *MFI;1164 BitVector CalleeSavedRegs;1165 LexicalScopes LS;1166 1167 // An empty DIExpression. Used default / placeholder DbgValueProperties1168 // objects, as we can't have null expressions.1169 const DIExpression *EmptyExpr;1170 1171 /// Object to track machine locations as we step through a block. Could1172 /// probably be a field rather than a pointer, as it's always used.1173 MLocTracker *MTracker = nullptr;1174 1175 /// Number of the current block LiveDebugValues is stepping through.1176 unsigned CurBB = -1;1177 1178 /// Number of the current instruction LiveDebugValues is evaluating.1179 unsigned CurInst;1180 1181 /// Variable tracker -- listens to DBG_VALUEs occurring as InstrRefBasedImpl1182 /// steps through a block. Reads the values at each location from the1183 /// MLocTracker object.1184 VLocTracker *VTracker = nullptr;1185 1186 /// Tracker for transfers, listens to DBG_VALUEs and transfers of values1187 /// between locations during stepping, creates new DBG_VALUEs when values move1188 /// location.1189 TransferTracker *TTracker = nullptr;1190 1191 /// Blocks which are artificial, i.e. blocks which exclusively contain1192 /// instructions without DebugLocs, or with line 0 locations.1193 SmallPtrSet<MachineBasicBlock *, 16> ArtificialBlocks;1194 1195 // Mapping of blocks to and from their RPOT order.1196 SmallVector<MachineBasicBlock *> OrderToBB;1197 DenseMap<const MachineBasicBlock *, unsigned int> BBToOrder;1198 DenseMap<unsigned, unsigned> BBNumToRPO;1199 1200 /// Pair of MachineInstr, and its 1-based offset into the containing block.1201 using InstAndNum = std::pair<const MachineInstr *, unsigned>;1202 /// Map from debug instruction number to the MachineInstr labelled with that1203 /// number, and its location within the function. Used to transform1204 /// instruction numbers in DBG_INSTR_REFs into machine value numbers.1205 std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;1206 1207 /// Record of where we observed a DBG_PHI instruction.1208 class DebugPHIRecord {1209 public:1210 /// Instruction number of this DBG_PHI.1211 uint64_t InstrNum;1212 /// Block where DBG_PHI occurred.1213 MachineBasicBlock *MBB;1214 /// The value number read by the DBG_PHI -- or std::nullopt if it didn't1215 /// refer to a value.1216 std::optional<ValueIDNum> ValueRead;1217 /// Register/Stack location the DBG_PHI reads -- or std::nullopt if it1218 /// referred to something unexpected.1219 std::optional<LocIdx> ReadLoc;1220 1221 operator unsigned() const { return InstrNum; }1222 };1223 1224 /// Map from instruction numbers defined by DBG_PHIs to a record of what that1225 /// DBG_PHI read and where. Populated and edited during the machine value1226 /// location problem -- we use LLVMs SSA Updater to fix changes by1227 /// optimizations that destroy PHI instructions.1228 SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;1229 1230 // Map of overlapping variable fragments.1231 OverlapMap OverlapFragments;1232 VarToFragments SeenFragments;1233 1234 /// Mapping of DBG_INSTR_REF instructions to their values, for those1235 /// DBG_INSTR_REFs that call resolveDbgPHIs. These variable references solve1236 /// a mini SSA problem caused by DBG_PHIs being cloned, this collection caches1237 /// the result.1238 DenseMap<std::pair<MachineInstr *, unsigned>, std::optional<ValueIDNum>>1239 SeenDbgPHIs;1240 1241 DbgOpIDMap DbgOpStore;1242 1243 /// Mapping between DebugVariables and unique ID numbers. This is a more1244 /// efficient way to represent the identity of a variable, versus a plain1245 /// DebugVariable.1246 DebugVariableMap DVMap;1247 1248 /// True if we need to examine call instructions for stack clobbers. We1249 /// normally assume that they don't clobber SP, but stack probes on Windows1250 /// do.1251 bool AdjustsStackInCalls = false;1252 1253 /// If AdjustsStackInCalls is true, this holds the name of the target's stack1254 /// probe function, which is the function we expect will alter the stack1255 /// pointer.1256 StringRef StackProbeSymbolName;1257 1258 /// Tests whether this instruction is a spill to a stack slot.1259 std::optional<SpillLocationNo> isSpillInstruction(const MachineInstr &MI,1260 MachineFunction *MF);1261 1262 /// Decide if @MI is a spill instruction and return true if it is. We use 21263 /// criteria to make this decision:1264 /// - Is this instruction a store to a spill slot?1265 /// - Is there a register operand that is both used and killed?1266 /// TODO: Store optimization can fold spills into other stores (including1267 /// other spills). We do not handle this yet (more than one memory operand).1268 bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,1269 unsigned &Reg);1270 1271 /// If a given instruction is identified as a spill, return the spill slot1272 /// and set \p Reg to the spilled register.1273 std::optional<SpillLocationNo> isRestoreInstruction(const MachineInstr &MI,1274 MachineFunction *MF,1275 unsigned &Reg);1276 1277 /// Given a spill instruction, extract the spill slot information, ensure it's1278 /// tracked, and return the spill number.1279 std::optional<SpillLocationNo>1280 extractSpillBaseRegAndOffset(const MachineInstr &MI);1281 1282 /// For an instruction reference given by \p InstNo and \p OpNo in instruction1283 /// \p MI returns the Value pointed to by that instruction reference if any1284 /// exists, otherwise returns std::nullopt.1285 std::optional<ValueIDNum> getValueForInstrRef(unsigned InstNo, unsigned OpNo,1286 MachineInstr &MI,1287 const FuncValueTable *MLiveOuts,1288 const FuncValueTable *MLiveIns);1289 1290 /// Observe a single instruction while stepping through a block.1291 void process(MachineInstr &MI, const FuncValueTable *MLiveOuts,1292 const FuncValueTable *MLiveIns);1293 1294 /// Examines whether \p MI is a DBG_VALUE and notifies trackers.1295 /// \returns true if MI was recognized and processed.1296 bool transferDebugValue(const MachineInstr &MI);1297 1298 /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.1299 /// \returns true if MI was recognized and processed.1300 bool transferDebugInstrRef(MachineInstr &MI, const FuncValueTable *MLiveOuts,1301 const FuncValueTable *MLiveIns);1302 1303 /// Stores value-information about where this PHI occurred, and what1304 /// instruction number is associated with it.1305 /// \returns true if MI was recognized and processed.1306 bool transferDebugPHI(MachineInstr &MI);1307 1308 /// Examines whether \p MI is copy instruction, and notifies trackers.1309 /// \returns true if MI was recognized and processed.1310 bool transferRegisterCopy(MachineInstr &MI);1311 1312 /// Examines whether \p MI is stack spill or restore instruction, and1313 /// notifies trackers. \returns true if MI was recognized and processed.1314 bool transferSpillOrRestoreInst(MachineInstr &MI);1315 1316 /// Examines \p MI for any registers that it defines, and notifies trackers.1317 void transferRegisterDef(MachineInstr &MI);1318 1319 /// Copy one location to the other, accounting for movement of subregisters1320 /// too.1321 void performCopy(Register Src, Register Dst);1322 1323 void accumulateFragmentMap(MachineInstr &MI);1324 1325 /// Determine the machine value number referred to by (potentially several)1326 /// DBG_PHI instructions. Block duplication and tail folding can duplicate1327 /// DBG_PHIs, shifting the position where values in registers merge, and1328 /// forming another mini-ssa problem to solve.1329 /// \p Here the position of a DBG_INSTR_REF seeking a machine value number1330 /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.1331 /// \returns The machine value number at position Here, or std::nullopt.1332 std::optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,1333 const FuncValueTable &MLiveOuts,1334 const FuncValueTable &MLiveIns,1335 MachineInstr &Here,1336 uint64_t InstrNum);1337 1338 std::optional<ValueIDNum> resolveDbgPHIsImpl(MachineFunction &MF,1339 const FuncValueTable &MLiveOuts,1340 const FuncValueTable &MLiveIns,1341 MachineInstr &Here,1342 uint64_t InstrNum);1343 1344 /// Step through the function, recording register definitions and movements1345 /// in an MLocTracker. Convert the observations into a per-block transfer1346 /// function in \p MLocTransfer, suitable for using with the machine value1347 /// location dataflow problem.1348 LLVM_ABI_FOR_TEST void1349 produceMLocTransferFunction(MachineFunction &MF,1350 SmallVectorImpl<MLocTransferMap> &MLocTransfer,1351 unsigned MaxNumBlocks);1352 1353 /// Solve the machine value location dataflow problem. Takes as input the1354 /// transfer functions in \p MLocTransfer. Writes the output live-in and1355 /// live-out arrays to the (initialized to zero) multidimensional arrays in1356 /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block1357 /// number, the inner by LocIdx.1358 LLVM_ABI_FOR_TEST void1359 buildMLocValueMap(MachineFunction &MF, FuncValueTable &MInLocs,1360 FuncValueTable &MOutLocs,1361 SmallVectorImpl<MLocTransferMap> &MLocTransfer);1362 1363 /// Examine the stack indexes (i.e. offsets within the stack) to find the1364 /// basic units of interference -- like reg units, but for the stack.1365 void findStackIndexInterference(SmallVectorImpl<unsigned> &Slots);1366 1367 /// Install PHI values into the live-in array for each block, according to1368 /// the IDF of each register.1369 LLVM_ABI_FOR_TEST void placeMLocPHIs(1370 MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,1371 FuncValueTable &MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer);1372 1373 /// Propagate variable values to blocks in the common case where there's1374 /// only one value assigned to the variable. This function has better1375 /// performance as it doesn't have to find the dominance frontier between1376 /// different assignments.1377 void placePHIsForSingleVarDefinition(1378 const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,1379 MachineBasicBlock *MBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,1380 DebugVariableID Var, LiveInsT &Output);1381 1382 /// Calculate the iterated-dominance-frontier for a set of defs, using the1383 /// existing LLVM facilities for this. Works for a single "value" or1384 /// machine/variable location.1385 /// \p AllBlocks Set of blocks where we might consume the value.1386 /// \p DefBlocks Set of blocks where the value/location is defined.1387 /// \p PHIBlocks Output set of blocks where PHIs must be placed.1388 void BlockPHIPlacement(const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,1389 const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,1390 SmallVectorImpl<MachineBasicBlock *> &PHIBlocks);1391 1392 /// Perform a control flow join (lattice value meet) of the values in machine1393 /// locations at \p MBB. Follows the algorithm described in the file-comment,1394 /// reading live-outs of predecessors from \p OutLocs, the current live ins1395 /// from \p InLocs, and assigning the newly computed live ins back into1396 /// \p InLocs. \returns two bools -- the first indicates whether a change1397 /// was made, the second whether a lattice downgrade occurred. If the latter1398 /// is true, revisiting this block is necessary.1399 bool mlocJoin(MachineBasicBlock &MBB,1400 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,1401 FuncValueTable &OutLocs, ValueTable &InLocs);1402 1403 /// Produce a set of blocks that are in the current lexical scope. This means1404 /// those blocks that contain instructions "in" the scope, blocks where1405 /// assignments to variables in scope occur, and artificial blocks that are1406 /// successors to any of the earlier blocks. See https://llvm.org/PR48091 for1407 /// more commentry on what "in scope" means.1408 /// \p DILoc A location in the scope that we're fetching blocks for.1409 /// \p Output Set to put in-scope-blocks into.1410 /// \p AssignBlocks Blocks known to contain assignments of variables in scope.1411 void1412 getBlocksForScope(const DILocation *DILoc,1413 SmallPtrSetImpl<const MachineBasicBlock *> &Output,1414 const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks);1415 1416 /// Solve the variable value dataflow problem, for a single lexical scope.1417 /// Uses the algorithm from the file comment to resolve control flow joins1418 /// using PHI placement and value propagation. Reads the locations of machine1419 /// values from the \p MInLocs and \p MOutLocs arrays (see buildMLocValueMap)1420 /// and reads the variable values transfer function from \p AllTheVlocs.1421 /// Live-in and Live-out variable values are stored locally, with the live-ins1422 /// permanently stored to \p Output once a fixedpoint is reached.1423 /// \p VarsWeCareAbout contains a collection of the variables in \p Scope1424 /// that we should be tracking.1425 /// \p AssignBlocks contains the set of blocks that aren't in \p DILoc's1426 /// scope, but which do contain DBG_VALUEs, which VarLocBasedImpl tracks1427 /// locations through.1428 LLVM_ABI_FOR_TEST void1429 buildVLocValueMap(const DILocation *DILoc,1430 const SmallSet<DebugVariableID, 4> &VarsWeCareAbout,1431 SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,1432 LiveInsT &Output, FuncValueTable &MOutLocs,1433 FuncValueTable &MInLocs,1434 SmallVectorImpl<VLocTracker> &AllTheVLocs);1435 1436 /// Attempt to eliminate un-necessary PHIs on entry to a block. Examines the1437 /// live-in values coming from predecessors live-outs, and replaces any PHIs1438 /// already present in this blocks live-ins with a live-through value if the1439 /// PHI isn't needed.1440 /// \p LiveIn Old live-in value, overwritten with new one if live-in changes.1441 /// \returns true if any live-ins change value, either from value propagation1442 /// or PHI elimination.1443 LLVM_ABI_FOR_TEST bool1444 vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,1445 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,1446 DbgValue &LiveIn);1447 1448 /// For the given block and live-outs feeding into it, try to find1449 /// machine locations for each debug operand where all the values feeding1450 /// into that operand join together.1451 /// \returns true if a joined location was found for every value that needed1452 /// to be joined.1453 LLVM_ABI_FOR_TEST bool1454 pickVPHILoc(SmallVectorImpl<DbgOpID> &OutValues, const MachineBasicBlock &MBB,1455 const LiveIdxT &LiveOuts, FuncValueTable &MOutLocs,1456 const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders);1457 1458 std::optional<ValueIDNum> pickOperandPHILoc(1459 unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,1460 FuncValueTable &MOutLocs,1461 const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders);1462 1463 /// Take collections of DBG_VALUE instructions stored in TTracker, and1464 /// install them into their output blocks.1465 bool emitTransfers();1466 1467 /// Boilerplate computation of some initial sets, artifical blocks and1468 /// RPOT block ordering.1469 LLVM_ABI_FOR_TEST void initialSetup(MachineFunction &MF);1470 1471 /// Produce a map of the last lexical scope that uses a block, using the1472 /// scopes DFSOut number. Mapping is block-number to DFSOut.1473 /// \p EjectionMap Pre-allocated vector in which to install the built ma.1474 /// \p ScopeToDILocation Mapping of LexicalScopes to their DILocations.1475 /// \p AssignBlocks Map of blocks where assignments happen for a scope.1476 void makeDepthFirstEjectionMap(SmallVectorImpl<unsigned> &EjectionMap,1477 const ScopeToDILocT &ScopeToDILocation,1478 ScopeToAssignBlocksT &AssignBlocks);1479 1480 /// When determining per-block variable values and emitting to DBG_VALUEs,1481 /// this function explores by lexical scope depth. Doing so means that per1482 /// block information can be fully computed before exploration finishes,1483 /// allowing us to emit it and free data structures earlier than otherwise.1484 /// It's also good for locality.1485 bool depthFirstVLocAndEmit(1486 unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,1487 const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToBlocks,1488 LiveInsT &Output, FuncValueTable &MOutLocs, FuncValueTable &MInLocs,1489 SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,1490 bool ShouldEmitDebugEntryValues);1491 1492 bool ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree,1493 bool ShouldEmitDebugEntryValues, unsigned InputBBLimit,1494 unsigned InputDbgValLimit) override;1495 1496public:1497 /// Default construct and initialize the pass.1498 LLVM_ABI_FOR_TEST InstrRefBasedLDV();1499 1500 LLVM_DUMP_METHOD1501 void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;1502 1503 bool isCalleeSaved(LocIdx L) const;1504 bool isCalleeSavedReg(Register R) const;1505 1506 bool hasFoldedStackStore(const MachineInstr &MI) {1507 // Instruction must have a memory operand that's a stack slot, and isn't1508 // aliased, meaning it's a spill from regalloc instead of a variable.1509 // If it's aliased, we can't guarantee its value.1510 if (!MI.hasOneMemOperand())1511 return false;1512 auto *MemOperand = *MI.memoperands_begin();1513 return MemOperand->isStore() &&1514 MemOperand->getPseudoValue() &&1515 MemOperand->getPseudoValue()->kind() == PseudoSourceValue::FixedStack1516 && !MemOperand->getPseudoValue()->isAliased(MFI);1517 }1518 1519 std::optional<LocIdx> findLocationForMemOperand(const MachineInstr &MI);1520 1521 // Utility for unit testing, don't use directly.1522 DebugVariableMap &getDVMap() {1523 return DVMap;1524 }1525};1526 1527} // namespace LiveDebugValues1528 1529#endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */1530