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

source code of llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h