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-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H
10#define LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H
11
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. Each
43/// DebugVariable consists of three pointers, and after a small amount of
44/// work to identify overlapping fragments of variables we mostly only use
45/// DebugVariables as identities of variables. It's much more compile-time
46/// 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(Val: 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(KV: {Var, Size});
61 if (ItPair.second) {
62 IdxToVar.push_back(Elt: {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 uniquely
78/// symbolises a register or stack location, allowing manipulation of locations
79/// without concern for where that location is. Practically, this allows us to
80/// 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 24
91 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 and
120// an offset.
121struct SpillLoc {
122 unsigned SpillBase;
123 StackOffset SpillOffset;
124 bool operator==(const SpillLoc &Other) const {
125 return std::make_pair(x: SpillBase, y: SpillOffset) ==
126 std::make_pair(x: Other.SpillBase, y: Other.SpillOffset);
127 }
128 bool operator<(const SpillLoc &Other) const {
129 return std::make_tuple(args: SpillBase, args: SpillOffset.getFixed(),
130 args: SpillOffset.getScalable()) <
131 std::make_tuple(args: Other.SpillBase, args: Other.SpillOffset.getFixed(),
132 args: 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 less
138/// bit-constrained. Each value identifies the instruction and machine location
139/// where the value is defined, although there may be no corresponding machine
140/// operand for it (ex: regmasks clobbering values). The instructions are
141/// 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 are
144/// problematic; but by that point we should probably have bailed out of
145/// 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 LocNo
153 : 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 IndexedMaps
162 // 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 = {.BlockNo: Block, .InstNo: Inst, .LocNo: Loc};
167 }
168
169 ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc) {
170 u.s = {.BlockNo: Block, .InstNo: Inst, .LocNo: 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(Suffix: Twine(u.s.BlockNo)
199 .concat(Suffix: Twine(", inst: ")
200 .concat(Suffix: (u.s.InstNo ? Twine(u.s.InstNo)
201 : Twine("live-in"))
202 .concat(Suffix: Twine(", loc: ").concat(
203 Suffix: Twine(mlocname)))
204 .concat(Suffix: 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 LiveDebugValues
213
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(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 llvm
242
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 convenient
250/// accessor methods.
251struct FuncValueTable {
252 FuncValueTable(int NumBBs, int NumLocs) {
253 Storage.reserve(N: NumBBs);
254 for (int i = 0; i != NumBBs; ++i)
255 Storage.push_back(
256 Elt: std::make_unique<ValueTable>(args&: NumLocs, args&: 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 number
265 /// 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 during
287 /// LDV; this was measured to have a significant impact on compiler memory
288 /// usage.
289 SmallVector<std::unique_ptr<ValueTable>, 0> Storage;
290};
291
292/// Thin wrapper around an integer -- designed to give more type safety to
293/// 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 qualify
313/// 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(FirstExpr: DIExpr, FirstIndirect: Indirect, SecondExpr: Other.DIExpr,
331 SecondIndirect: Other.Indirect);
332 }
333
334 bool operator==(const DbgValueProperties &Other) const {
335 return std::tie(args: DIExpr, args: Indirect, args: IsVariadic) ==
336 std::tie(args: Other.DIExpr, args: Other.Indirect, args: 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, since
353/// MachineOperand is width 32, making this struct width 33. We could also
354/// potentially avoid storing the whole MachineOperand (sizeof=32), instead
355/// 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 for
358/// directly storing immediate values, or a ValueIDNum representing some value
359/// 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 NDEBUG
374 void dump(const MLocTracker *MTrack) const;
375#endif
376};
377
378/// A DbgOp whose ID (if any) has resolved to an actual location, LocIdx. Used
379/// when working with concrete debug values, i.e. when joining MLocs and VLocs
380/// in the TransferTracker or emitting DBG_VALUE/DBG_VALUE_LIST instructions in
381/// 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: Other.MO);
397 return Loc == Other.Loc;
398 }
399
400#ifndef NDEBUG
401 void dump(const MLocTracker *MTrack) const;
402#endif
403};
404
405/// An ID used in the DbgOpIDMap (below) to lookup a stored DbgOp. This is used
406/// in place of actual DbgOps inside of a DbgValue to reduce its size, as
407/// DbgValue is very frequently used and passed around, and the actual DbgOp is
408/// over 8x larger than this class, due to storing a MachineOperand. This ID
409/// should be equal for all equal DbgOps, and also encodes whether the mapped
410/// DbgOp is a constant, meaning that for simple equality or const-ness checks
411/// 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: IsConst, .Index: 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 NDEBUG
441 void dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const;
442#endif
443};
444
445/// Class storing the complete set of values that are observed by DbgValues
446/// within the current function. Allows 2-way lookup, with `find` returning the
447/// Op for a given ID and `insert` returning the ID for a given Op (creating one
448/// 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 the
459 /// corresponding DbgOpID is returned. If Op already exists in this map, then
460 /// 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(MO&: Op.MO);
467 return insertValueOp(VID: Op.ID);
468 }
469 /// Returns the DbgOp associated with \p ID. Should only be used for IDs
470 /// 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(Key: MO, Args: true, Args: ConstOps.size());
489 if (Inserted)
490 ConstOps.push_back(Elt: MO);
491 return It->second;
492 }
493 DbgOpID insertValueOp(ValueIDNum VID) {
494 auto [It, Inserted] = ValueOpToID.try_emplace(Key: VID, Args: false, Args: ValueOps.size());
495 if (Inserted)
496 ValueOps.push_back(Elt: VID);
497 return It->second;
498 }
499};
500
501// We set the maximum number of operands that we will handle to keep DbgValue
502// within a reasonable size (64 bytes), as we store and pass a lot of them
503// around.
504#define MAX_DBG_OPS 8
505
506/// Class recording the (high level) _value_ of a variable. Identifies the value
507/// of the variable as a list of ValueIDNums and constant MachineOperands, or as
508/// an empty list for undef debug values or VPHI values which we have not found
509/// 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 second
512/// (DebugVariable specific) dataflow analysis.
513class DbgValue {
514private:
515 /// If Kind is Def or VPHI, the set of IDs corresponding to the DbgOps that
516 /// are used. VPHIs set every ID to EmptyID when we have not found a valid
517 /// machine-value for every operand, and sets them to the corresponding
518 /// 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 by
534 // 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(Range&: DbgOps, P: [](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_TYPE
556 } 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 NDEBUG
574 void dump(const MLocTracker *MTrack = nullptr,
575 const DbgOpIDMap *OpStore = nullptr) const;
576#endif
577
578 bool operator==(const DbgValue &Other) const {
579 if (std::tie(args: Kind, args: Properties) != std::tie(args: Other.Kind, args: Other.Properties))
580 return false;
581 else if (Kind == Def && !equal(LRange: getDbgOpIDs(), RRange: 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(LRange: getDbgOpIDs(), RRange: 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 variable
596 // 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, or
600 // 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 of
609 // \p NewIDs. The number of DbgOpIDs passed must be equal to the number of
610 // arguments expected by this DbgValue's properties (the return value of
611 // `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 an
623 // 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 defined
629 // Loc Ops, or if the `n`th Loc Op for this has a different constness to the
630 // `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(Index: Idx).isConst() != Other.getDbgOpID(Index: 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(LRange: getDbgOpIDs(), RRange: 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 Things
657/// being Done by various instructions, and maintains a table of what machine
658/// locations have what values (as defined by a ValueIDNum).
659///
660/// There are potentially a much larger number of machine locations on the
661/// target machine than the actual working-set size of the function. On x86 for
662/// example, we're extremely unlikely to want to track values through control
663/// or debug registers. To avoid doing so, MLocTracker has several layers of
664/// indirection going on, described below, to avoid unnecessarily tracking
665/// 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 stack
670/// \ /
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 => LocIdx
680/// |
681/// LocIdx => ValueIDNum
682///
683/// The aim here is that the LocIdx => ValueIDNum vector is just an array of
684/// values in numbered locations, so that later analyses can ignore whether the
685/// location is a register or otherwise. To map a register / spill location to
686/// a LocIdx, you have to use the (sparse) LocationID => LocIdx map. And to
687/// build a LocationID for a stack slot, you need to combine identifiers for
688/// 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 and
692/// 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 tightly
704 /// 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 the
708 /// LocIdx key / number for that location. There are always at least as many
709 /// as the number of registers on the target -- if the value in the register
710 /// is not being tracked, then the LocIdx value will be zero. New entries are
711 /// appended if a new spill slot begins being tracked.
712 /// This, and the corresponding reverse map persist for the analysis of the
713 /// whole function, and is necessarying for decoding various vectors of
714 /// 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 model
721 /// 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 is
726 /// 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 this
730 // 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 stack
737 /// slot that can take on the value of a subregister, when a super-register
738 /// is written to the stack.
739 unsigned NumSlotIdxes;
740
741 /// Collection of register mask operands that have been observed. Second part
742 /// of pair indicates the instruction that they happened in. Used to
743 /// reconstruct where defs happened if we start tracking a location later
744 /// on.
745 SmallVector<std::pair<const MachineOperand *, unsigned>, 32> Masks;
746
747 /// Pair for describing a position within a stack slot -- first the size in
748 /// 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 a
752 /// numeric identifier for that position. Allows easier identification of
753 /// 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. Dereferencing
760 /// produces a struct/pair containing the LocIdx key for this location,
761 /// and a reference to the value currently stored. Simplifies the process
762 /// 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 of
797 /// 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(Idx: SpillSubReg);
806 unsigned short Offs = TRI.getSubRegIdxOffset(Idx: SpillSubReg);
807 return getLocID(Spill, Idx: {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 number
823 /// 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(Val: 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. Used
852 /// sometimes for actual PHI values, othertimes to indicate the block entry
853 /// 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 current
861 /// 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-in
865 // 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 loadFromArray
873 // or setMPhis should be called before this object is re-used. Just
874 // clear Masks, they're definitely not needed.
875 Masks.clear();
876 }
877
878 /// Clear all data. Destroys the LocID <=> LocIdx map, which makes most of
879 /// 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 from
886 // 0
887 SpillLocs = decltype(SpillLocs)();
888 StackSlotIdxes.clear();
889 StackIdxesToPos.clear();
890
891 LocIDToLocIdx.resize(new_size: NumRegs, x: 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 location
901 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 an
907 /// 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 location
925 /// are synonymous.
926 void defReg(Register R, unsigned BB, unsigned Inst) {
927 unsigned ID = getLocID(Reg: 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 is
934 /// known in advance.
935 void setReg(Register R, ValueIDNum ValueID) {
936 unsigned ID = getLocID(Reg: R);
937 LocIdx Idx = lookupOrTrackRegister(ID);
938 LocIdxToIDNum[Idx] = ValueID;
939 }
940
941 ValueIDNum readReg(Register R) {
942 unsigned ID = getLocID(Reg: R);
943 LocIdx Idx = lookupOrTrackRegister(ID);
944 return LocIdxToIDNum[Idx];
945 }
946
947 /// Reset a register value to zero / empty. Needed to replicate the
948 /// VarLoc implementation where a copy to/from a register effectively
949 /// clears the contents of the source register. (Values can only have one
950 /// machine location in VarLocBasedImpl).
951 void wipeRegister(Register R) {
952 unsigned ID = getLocID(Reg: 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(Reg: 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 currently
966 /// track, stores a pointer to the mask in case we have to account for it
967 /// 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 be
972 /// 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(Idx: L)) {
989 return TRI.getRegSizeInBits(Reg: Register(ID), MRI: MF.getRegInfo());
990 } else {
991 // The slot location on the stack is uninteresting, we care about the
992 // 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(x: begin(), y: end());
1007 }
1008
1009 std::string LocIdxToName(LocIdx Idx) const;
1010
1011 std::string IDAsString(const ValueIDNum &Num) const;
1012
1013#ifndef NDEBUG
1014 LLVM_DUMP_METHOD void dump();
1015
1016 LLVM_DUMP_METHOD void dump_mloc_map();
1017#endif
1018
1019 /// Create a DBG_VALUE based on debug operands \p DbgOps. Qualify it with the
1020 /// 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 given
1028/// local variable, we record all other fragments of that variable that could
1029/// 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 each
1036/// variable and the value the DBG_VALUE refers to. Requires the machine value
1037/// location dataflow algorithm to have run already, so that values can be
1038/// 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 from
1045 /// the order in this container. (FIXME: likely no longer true as the ordering
1046 /// is now provided by DebugVariableMap).
1047 /// We only retain the last DbgValue in each block for each variable, to
1048 /// determine the blocks live-out variable value. The Vars container forms the
1049 /// transfer function for this block, as part of the dataflow analysis. The
1050 /// movement of values between locations inside of a block is handled at a
1051 /// 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, Loc: 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(Key: VarID, Val&: Rec);
1077 Scopes[VarID] = MI.getDebugLoc().get();
1078
1079 considerOverlaps(Var, Loc: MI.getDebugLoc().get());
1080 }
1081
1082 void considerOverlaps(const DebugVariable &Var, const DILocation *Loc) {
1083 auto Overlaps = OverlappingFragments.find(
1084 Val: {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, so
1091 // that it overlaps with everything, however its cannonical representation
1092 // in a DebugVariable is as "None".
1093 std::optional<DIExpression::FragmentInfo> OptFragmentInfo = FragmentInfo;
1094 if (DebugVariable::isDefaultFragment(F: 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(Var&: Overlapped, Loc);
1101 DbgValue Rec = DbgValue(EmptyProperties, DbgValue::Undef);
1102
1103 // Attempt insertion; overwrite if it's already mapped.
1104 Vars.insert_or_assign(Key: OverlappedID, Val&: Rec);
1105 Scopes[OverlappedID] = Loc;
1106 }
1107 }
1108
1109 void clear() {
1110 Vars.clear();
1111 Scopes.clear();
1112 }
1113};
1114
1115// XXX XXX docs
1116class 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 given
1124 // DILocalVariable.
1125 using VarToFragments =
1126 DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
1127
1128 /// Machine location/value transfer function, a mapping of which locations
1129 /// 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 of
1133 /// 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 are
1153 /// assigned. Such blocks aren't necessarily "in" the lexical scope, it's
1154 /// 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 DbgValueProperties
1168 // 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. Could
1172 /// 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 InstrRefBasedImpl
1182 /// steps through a block. Reads the values at each location from the
1183 /// MLocTracker object.
1184 VLocTracker *VTracker = nullptr;
1185
1186 /// Tracker for transfers, listens to DBG_VALUEs and transfers of values
1187 /// between locations during stepping, creates new DBG_VALUEs when values move
1188 /// location.
1189 TransferTracker *TTracker = nullptr;
1190
1191 /// Blocks which are artificial, i.e. blocks which exclusively contain
1192 /// 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 that
1203 /// number, and its location within the function. Used to transform
1204 /// 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't
1215 /// refer to a value.
1216 std::optional<ValueIDNum> ValueRead;
1217 /// Register/Stack location the DBG_PHI reads -- or std::nullopt if it
1218 /// 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 that
1225 /// DBG_PHI read and where. Populated and edited during the machine value
1226 /// location problem -- we use LLVMs SSA Updater to fix changes by
1227 /// 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 those
1235 /// DBG_INSTR_REFs that call resolveDbgPHIs. These variable references solve
1236 /// a mini SSA problem caused by DBG_PHIs being cloned, this collection caches
1237 /// 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 more
1244 /// efficient way to represent the identity of a variable, versus a plain
1245 /// DebugVariable.
1246 DebugVariableMap DVMap;
1247
1248 /// True if we need to examine call instructions for stack clobbers. We
1249 /// normally assume that they don't clobber SP, but stack probes on Windows
1250 /// do.
1251 bool AdjustsStackInCalls = false;
1252
1253 /// If AdjustsStackInCalls is true, this holds the name of the target's stack
1254 /// probe function, which is the function we expect will alter the stack
1255 /// 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 2
1263 /// 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 (including
1267 /// 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 slot
1272 /// 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's
1278 /// 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 instruction
1283 /// \p MI returns the Value pointed to by that instruction reference if any
1284 /// 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 what
1304 /// 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, and
1313 /// 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 subregisters
1320 /// 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 duplicate
1327 /// DBG_PHIs, shifting the position where values in registers merge, and
1328 /// forming another mini-ssa problem to solve.
1329 /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
1330 /// \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 movements
1345 /// in an MLocTracker. Convert the observations into a per-block transfer
1346 /// function in \p MLocTransfer, suitable for using with the machine value
1347 /// location dataflow problem.
1348 LLVM_ABI_FOR_TEST void
1349 produceMLocTransferFunction(MachineFunction &MF,
1350 SmallVectorImpl<MLocTransferMap> &MLocTransfer,
1351 unsigned MaxNumBlocks);
1352
1353 /// Solve the machine value location dataflow problem. Takes as input the
1354 /// transfer functions in \p MLocTransfer. Writes the output live-in and
1355 /// live-out arrays to the (initialized to zero) multidimensional arrays in
1356 /// \p MInLocs and \p MOutLocs. The outer dimension is indexed by block
1357 /// number, the inner by LocIdx.
1358 LLVM_ABI_FOR_TEST void
1359 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 the
1364 /// 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 to
1368 /// 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's
1374 /// only one value assigned to the variable. This function has better
1375 /// performance as it doesn't have to find the dominance frontier between
1376 /// 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 the
1383 /// existing LLVM facilities for this. Works for a single "value" or
1384 /// 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 machine
1393 /// locations at \p MBB. Follows the algorithm described in the file-comment,
1394 /// reading live-outs of predecessors from \p OutLocs, the current live ins
1395 /// from \p InLocs, and assigning the newly computed live ins back into
1396 /// \p InLocs. \returns two bools -- the first indicates whether a change
1397 /// was made, the second whether a lattice downgrade occurred. If the latter
1398 /// 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 means
1404 /// those blocks that contain instructions "in" the scope, blocks where
1405 /// assignments to variables in scope occur, and artificial blocks that are
1406 /// successors to any of the earlier blocks. See https://llvm.org/PR48091 for
1407 /// 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 void
1412 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 joins
1418 /// using PHI placement and value propagation. Reads the locations of machine
1419 /// 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-ins
1422 /// permanently stored to \p Output once a fixedpoint is reached.
1423 /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
1424 /// that we should be tracking.
1425 /// \p AssignBlocks contains the set of blocks that aren't in \p DILoc's
1426 /// scope, but which do contain DBG_VALUEs, which VarLocBasedImpl tracks
1427 /// locations through.
1428 LLVM_ABI_FOR_TEST void
1429 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 the
1437 /// live-in values coming from predecessors live-outs, and replaces any PHIs
1438 /// already present in this blocks live-ins with a live-through value if the
1439 /// 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 propagation
1442 /// or PHI elimination.
1443 LLVM_ABI_FOR_TEST bool
1444 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 find
1449 /// machine locations for each debug operand where all the values feeding
1450 /// into that operand join together.
1451 /// \returns true if a joined location was found for every value that needed
1452 /// to be joined.
1453 LLVM_ABI_FOR_TEST bool
1454 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, and
1464 /// install them into their output blocks.
1465 bool emitTransfers();
1466
1467 /// Boilerplate computation of some initial sets, artifical blocks and
1468 /// 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 the
1472 /// 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 per
1482 /// 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_METHOD
1501 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't
1508 // 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::FixedStack
1516 && !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 LiveDebugValues
1528
1529#endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */
1530