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