LLVM 20.0.0git
InstrRefBasedImpl.h
Go to the documentation of this file.
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"
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
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.
49
50public:
52 auto It = VarToIdx.find(Var);
53 assert(It != VarToIdx.end());
54 return It->second;
55 }
56
58 unsigned Size = VarToIdx.size();
59 auto ItPair = VarToIdx.insert({Var, Size});
60 if (ItPair.second) {
61 IdxToVar.push_back({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(); }
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;
123 bool operator==(const SpillLoc &Other) const {
124 return std::make_pair(SpillBase, SpillOffset) ==
125 std::make_pair(Other.SpillBase, Other.SpillOffset);
126 }
127 bool operator<(const SpillLoc &Other) const {
128 return std::make_tuple(SpillBase, SpillOffset.getFixed(),
130 std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
131 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.
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.
152 : NUM_LOC_BITS; /// The machine location where the def happens.
153 } s;
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
165 u.s = {Block, Inst, Loc};
166 }
167
169 u.s = {Block, Inst, 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
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(Twine(u.s.BlockNo)
198 .concat(Twine(", inst: ")
199 .concat((u.s.InstNo ? Twine(u.s.InstNo)
200 : Twine("live-in"))
201 .concat(Twine(", loc: ").concat(
202 Twine(mlocname)))
203 .concat(Twine("}")))))
204 .str();
205 }
206
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> {
227 static inline ValueIDNum getTombstoneKey() {
229 }
230
231 static unsigned getHashValue(const ValueIDNum &Val) {
232 return hash_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.
247
248/// A collection of ValueTables, one per BB in a function, with convenient
249/// accessor methods.
251 FuncValueTable(int NumBBs, int NumLocs) {
252 Storage.reserve(NumBBs);
253 for (int i = 0; i != NumBBs; ++i)
254 Storage.push_back(
255 std::make_unique<ValueTable>(NumLocs, ValueIDNum::EmptyValue));
256 }
257
258 /// Returns the ValueTable associated with MBB.
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.
276 return Storage[MBB.getNumber()] != nullptr;
277 }
278
279 /// Frees the memory of the ValueTable associated with 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.
289};
290
291/// Thin wrapper around an integer -- designed to give more type safety to
292/// spill location numbers.
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.
314public:
317
318 /// Extract properties from an existing DBG_VALUE instruction.
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
330 Other.Indirect);
331 }
332
334 return std::tie(DIExpr, Indirect, IsVariadic) ==
335 std::tie(Other.DIExpr, Other.Indirect, Other.IsVariadic);
336 }
337
339 return !(*this == Other);
340 }
341
342 unsigned getLocationOpCount() const {
344 }
345
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 {
363 };
365
366 DbgOp() : ID(ValueIDNum::EmptyValue), IsConst(false) {}
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.
382 union {
385 };
387
390
391 bool operator==(const ResolvedDbgOp &Other) const {
392 if (IsConst != Other.IsConst)
393 return false;
394 if (IsConst)
395 return MO.isIdenticalTo(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 {
415 };
416
417 union {
420 };
421
423 static_assert(sizeof(DbgOpID) == 4, "DbgOpID should fit within 4 bytes.");
424 }
426 DbgOpID(bool IsConst, uint32_t Index) : ID({IsConst, Index}) {}
427
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).
449
452
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.
462 if (Op.isUndef())
463 return DbgOpID::UndefID;
464 if (Op.IsConst)
465 return insertConstOp(Op.MO);
466 return insertValueOp(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.
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(MO);
488 if (ExistingIt != ConstOpToID.end())
489 return ExistingIt->second;
490 DbgOpID ID(true, ConstOps.size());
491 ConstOpToID.insert(std::make_pair(MO, ID));
492 ConstOps.push_back(MO);
493 return ID;
494 }
495 DbgOpID insertValueOp(ValueIDNum VID) {
496 auto ExistingIt = ValueOpToID.find(VID);
497 if (ExistingIt != ValueOpToID.end())
498 return ExistingIt->second;
499 DbgOpID ID(false, ValueOps.size());
500 ValueOpToID.insert(std::make_pair(VID, ID));
501 ValueOps.push_back(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.
530
531 /// Qualifiers for the ValueIDNum above.
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.
545
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(DbgOps, [](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
568 : OpCount(0), BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
569 assert(Kind == NoVal || Kind == VPHI);
570 }
571
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(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
585 return false;
586 else if (Kind == Def && !equal(getDbgOpIDs(), 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(getDbgOpIDs(), 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()`).
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 {
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(Idx).isConst() != Other.getDbgOpID(Idx).isConst())
641 return false;
642 }
643 return true;
644 }
645
646 bool isUnjoinedPHI() const { return Kind == VPHI && OpCount == 0; }
647
649 if (!OpCount)
650 return false;
651 return equal(getDbgOpIDs(), Other.getDbgOpIDs());
652 }
653};
654
656public:
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.
699public:
704
705 /// IndexedMap type, mapping from LocIdx to ValueIDNum.
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.
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.
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.
729
730 /// Unique-ification of spill. Used to number them -- their LocID number is
731 /// the index in SpillLocs minus one plus NumRegs.
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.
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.
760
761 /// Inverse of StackSlotIdxes.
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.
770 LocIdx Idx;
771
772 public:
774 public:
776 const LocIdx Idx; /// Read-only index of this location.
777 ValueIDNum &Value; /// Reference to the stored value at this location.
778 };
779
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
795 };
796
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(SpillSubReg);
810 unsigned short Offs = TRI.getSubRegIdxOffset(SpillSubReg);
811 return getLocID(Spill, {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.
818 unsigned SlotNo = Spill.id() - 1;
819 SlotNo *= NumSlotIdxes;
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.
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.
847 assert(ID >= NumRegs);
848 ID -= NumRegs;
849 unsigned Idx = ID % NumSlotIdxes;
850 return StackIdxesToPos.find(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();
889 // SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from
890 // 0
891 SpillLocs = decltype(SpillLocs)();
894
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
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
916 if (Index.isIllegal())
918 return Index;
919 }
920
921 /// Is register R currently tracked by MLocTracker?
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(R);
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(R);
942 LocIdxToIDNum[Idx] = ValueID;
943 }
944
946 unsigned ID = getLocID(R);
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).
956 unsigned ID = getLocID(R);
959 }
960
961 /// Determine the LocIdx of an existing register.
963 unsigned ID = getLocID(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(L)) {
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).
997 return Pos.first;
998 }
999 }
1000
1002
1005 }
1006
1007 /// Return a range over all locations currently tracked.
1009 return llvm::make_range(begin(), 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
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.
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.
1034 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
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.
1043public:
1044 /// Ref to function-wide map of DebugVariable <=> ID-numbers.
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.
1060
1061public:
1063 const DIExpression *EmptyExpr)
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, 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(std::make_pair(VarID, Rec));
1080 if (!Result.second)
1081 Result.first->second = Rec;
1082 Scopes[VarID] = MI.getDebugLoc().get();
1083
1084 considerOverlaps(Var, MI.getDebugLoc().get());
1085 }
1086
1087 void considerOverlaps(const DebugVariable &Var, const DILocation *Loc) {
1088 auto Overlaps = OverlappingFragments.find(
1089 {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(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(Overlapped, Loc);
1107
1108 // Attempt insertion; overwrite if it's already mapped.
1109 auto Result = Vars.insert(std::make_pair(OverlappedID, 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
1124public:
1125 friend class ::InstrRefLDVTest;
1126
1128 using OptFragmentInfo = std::optional<DIExpression::FragmentInfo>;
1129
1130 // Helper while building OverlapMap, a map of all fragments seen for a given
1131 // DILocalVariable.
1134
1135 /// Machine location/value transfer function, a mapping of which locations
1136 /// are assigned which new values.
1138
1139 /// Live in/out structure for the variable values: a per-block map of
1140 /// variables to their values.
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.
1151
1152 /// Mapping from lexical scopes to a DILocation in that scope.
1154
1155 /// Mapping from lexical scopes to variables in that scope.
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.
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.
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.
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
1463
1464 std::optional<ValueIDNum> pickOperandPHILoc(
1465 unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,
1466 FuncValueTable &MOutLocs,
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.
1507
1509 void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1510
1511 bool isCalleeSaved(LocIdx L) const;
1512 bool isCalleeSavedReg(Register R) const;
1513
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.
1531 return DVMap;
1532 }
1533};
1534
1535} // namespace LiveDebugValues
1536
1537#endif /* LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_INSTRREFBASEDLDV_H */
MachineBasicBlock & MBB
static cl::opt< unsigned > MaxNumBlocks("debug-ata-max-blocks", cl::init(10000), cl::desc("Maximum num basic blocks before debug info dropped"), cl::Hidden)
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
uint64_t Size
IRTranslator LLVM IR MI
This file implements an indexed map.
#define NUM_LOC_BITS
#define MAX_DBG_OPS
static cl::opt< unsigned > InputBBLimit("livedebugvalues-input-bb-limit", cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), cl::init(10000), cl::Hidden)
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class storing the complete set of values that are observed by DbgValues within the current function.
DbgOp find(DbgOpID ID) const
Returns the DbgOp associated with ID.
DbgOpID insert(DbgOp Op)
If Op does not already exist in this map, it is inserted and the corresponding DbgOpID is returned.
Meta qualifiers for a value.
bool operator==(const DbgValueProperties &Other) const
DbgValueProperties(const DIExpression *DIExpr, bool Indirect, bool IsVariadic)
DbgValueProperties(const MachineInstr &MI)
Extract properties from an existing DBG_VALUE instruction.
bool isJoinable(const DbgValueProperties &Other) const
bool operator!=(const DbgValueProperties &Other) const
Class recording the (high level) value of a variable.
int BlockNo
For a NoVal or VPHI DbgValue, which block it was generated in.
DbgValueProperties Properties
Qualifiers for the ValueIDNum above.
ArrayRef< DbgOpID > getDbgOpIDs() const
void setDbgOpIDs(ArrayRef< DbgOpID > NewIDs)
bool hasJoinableLocOps(const DbgValue &Other) const
void dump(const MLocTracker *MTrack=nullptr, const DbgOpIDMap *OpStore=nullptr) const
DbgValue(ArrayRef< DbgOpID > DbgOps, const DbgValueProperties &Prop)
DbgOpID getDbgOpID(unsigned Index) const
DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
bool operator!=(const DbgValue &Other) const
DbgValue(const DbgValueProperties &Prop, KindT Kind)
KindT Kind
Discriminator for whether this is a constant or an in-program value.
unsigned getLocationOpCount() const
bool operator==(const DbgValue &Other) const
bool hasIdenticalValidLocOps(const DbgValue &Other) const
Mapping from DebugVariable to/from a unique identifying number.
const VarAndLoc & lookupDVID(DebugVariableID ID) const
DebugVariableID insertDVID(DebugVariable &Var, const DILocation *Loc)
DebugVariableID getDVID(const DebugVariable &Var) const
DenseMap< const MachineBasicBlock *, DbgValue * > LiveIdxT
Live in/out structure for the variable values: a per-block map of variables to their values.
DenseMap< const LexicalScope *, const DILocation * > ScopeToDILocT
Mapping from lexical scopes to a DILocation in that scope.
std::optional< LocIdx > findLocationForMemOperand(const MachineInstr &MI)
std::pair< MachineBasicBlock *, DbgValue * > InValueT
Type for a live-in value: the predecessor block, and its value.
std::pair< DebugVariableID, DbgValue > VarAndLoc
SmallVector< SmallVector< VarAndLoc, 8 >, 8 > LiveInsT
Vector (per block) of a collection (inner smallvector) of live-ins.
InstrRefBasedLDV()
Default construct and initialize the pass.
DenseMap< const DILocalVariable *, SmallSet< FragmentInfo, 4 > > VarToFragments
std::optional< DIExpression::FragmentInfo > OptFragmentInfo
bool hasFoldedStackStore(const MachineInstr &MI)
DenseMap< const LexicalScope *, SmallPtrSet< MachineBasicBlock *, 4 > > ScopeToAssignBlocksT
Mapping from lexical scopes to blocks where variables in that scope are assigned.
LLVM_DUMP_METHOD void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const
DenseMap< const LexicalScope *, SmallSet< DebugVariableID, 4 > > ScopeToVarsT
Mapping from lexical scopes to variables in that scope.
unsigned operator()(const LocIdx &L) const
Handle-class for a particular "location".
bool operator!=(const LocIdx &L) const
bool operator<(const LocIdx &Other) const
static LocIdx MakeTombstoneLoc()
static LocIdx MakeIllegalLoc()
bool operator!=(unsigned L) const
bool operator==(unsigned L) const
bool operator==(const LocIdx &L) const
ValueIDNum & Value
Read-only index of this location.
Iterator for locations and the values they contain.
bool operator!=(const MLocIterator &Other) const
MLocIterator(LocToValueType &ValueMap, LocIdx Idx)
bool operator==(const MLocIterator &Other) const
Tracker for what values are in machine locations.
unsigned getLocSizeInBits(LocIdx L) const
How large is this location (aka, how wide is a value defined there?).
bool isRegisterTracked(Register R)
Is register R currently tracked by MLocTracker?
std::optional< SpillLocationNo > getOrTrackSpillLoc(SpillLoc L)
Find LocIdx for SpillLoc L, creating a new one if it's not tracked.
void loadFromArray(ValueTable &Locs, unsigned NewCurBB)
Load values for each location from array of ValueIDNums.
IndexedMap< unsigned, LocIdxToIndexFunctor > LocIdxToLocID
Inverse map of LocIDToLocIdx.
unsigned getSpillIDWithIdx(SpillLocationNo Spill, unsigned Idx)
Given a spill number, and a slot within the spill, calculate the ID number for that location.
unsigned getLocID(SpillLocationNo Spill, unsigned SpillSubReg)
Produce location ID number for a spill position.
iterator_range< MLocIterator > locations()
Return a range over all locations currently tracked.
unsigned getLocID(SpillLocationNo Spill, StackSlotPos Idx)
Produce location ID number for a spill position.
SmallSet< Register, 8 > SPAliases
When clobbering register masks, we chose to not believe the machine model and don't clobber SP.
unsigned getLocID(Register Reg)
Produce location ID number for a Register.
const TargetLowering & TLI
const TargetRegisterInfo & TRI
unsigned NumRegs
Cached local copy of the number of registers the target has.
DenseMap< StackSlotPos, unsigned > StackSlotIdxes
Map from a size/offset pair describing a position in a stack slot, to a numeric identifier for that p...
LocIdx lookupOrTrackRegister(unsigned ID)
void setReg(Register R, ValueIDNum ValueID)
Set a register to a value number.
SpillLocationNo locIDToSpill(unsigned ID) const
Return the spill number that a location ID corresponds to.
void reset()
Wipe any un-necessary location records after traversing a block.
DenseMap< unsigned, StackSlotPos > StackIdxesToPos
Inverse of StackSlotIdxes.
std::string IDAsString(const ValueIDNum &Num) const
void writeRegMask(const MachineOperand *MO, unsigned CurBB, unsigned InstID)
Record a RegMask operand being executed.
std::pair< unsigned short, unsigned short > StackSlotPos
Pair for describing a position within a stack slot – first the size in bits, then the offset.
const TargetInstrInfo & TII
bool isSpill(LocIdx Idx) const
Return true if Idx is a spill machine location.
LocIdx getRegMLoc(Register R)
Determine the LocIdx of an existing register.
MachineInstrBuilder emitLoc(const SmallVectorImpl< ResolvedDbgOp > &DbgOps, const DebugVariable &Var, const DILocation *DILoc, const DbgValueProperties &Properties)
Create a DBG_VALUE based on debug operands DbgOps.
void wipeRegister(Register R)
Reset a register value to zero / empty.
void setMLoc(LocIdx L, ValueIDNum Num)
Set a locaiton to a certain value.
LocToValueType LocIdxToIDNum
Map of LocIdxes to the ValueIDNums that they store.
std::vector< LocIdx > LocIDToLocIdx
"Map" of machine location IDs (i.e., raw register or spill number) to the LocIdx key / number for tha...
void clear()
Clear all data.
SmallVector< std::pair< const MachineOperand *, unsigned >, 32 > Masks
Collection of register mask operands that have been observed.
unsigned NumSlotIdxes
Number of slot indexes the target has – distinct segments of a stack slot that can take on the value ...
UniqueVector< SpillLoc > SpillLocs
Unique-ification of spill.
ValueIDNum readMLoc(LocIdx L)
Read the value of a particular location.
void setMPhis(unsigned NewCurBB)
Reset all locations to contain a PHI value at the designated block.
ValueIDNum readReg(Register R)
void defReg(Register R, unsigned BB, unsigned Inst)
Record a definition of the specified register at the given block / inst.
LLVM_DUMP_METHOD void dump()
LocIdx trackRegister(unsigned ID)
Create a LocIdx for an untracked register ID.
LLVM_DUMP_METHOD void dump_mloc_map()
StackSlotPos locIDToSpillIdx(unsigned ID) const
Returns the spill-slot size/offs that a location ID corresponds to.
LocIdx getSpillMLoc(unsigned SpillID)
std::string LocIdxToName(LocIdx Idx) const
Thin wrapper around an integer – designed to give more type safety to spill location numbers.
bool operator==(const SpillLocationNo &Other) const
bool operator!=(const SpillLocationNo &Other) const
bool operator<(const SpillLocationNo &Other) const
Collection of DBG_VALUEs observed when traversing a block.
const OverlapMap & OverlappingFragments
SmallDenseMap< DebugVariableID, const DILocation *, 8 > Scopes
void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, const SmallVectorImpl< DbgOpID > &DebugOps)
MapVector< DebugVariableID, DbgValue > Vars
Map DebugVariable to the latest Value it's defined to have.
void considerOverlaps(const DebugVariable &Var, const DILocation *Loc)
VLocTracker(DebugVariableMap &DVMap, const OverlapMap &O, const DIExpression *EmptyExpr)
DebugVariableMap & DVMap
Ref to function-wide map of DebugVariable <=> ID-numbers.
DbgValueProperties EmptyProperties
Unique identifier for a value defined by an instruction, as a value type.
uint64_t LocNo
The Instruction where the def happens.
ValueIDNum(uint64_t Block, uint64_t Inst, uint64_t Loc)
bool operator==(const ValueIDNum &Other) const
bool operator<(const ValueIDNum &Other) const
static ValueIDNum fromU64(uint64_t v)
std::string asString(const std::string &mlocname) const
ValueIDNum(uint64_t Block, uint64_t Inst, LocIdx Loc)
struct LiveDebugValues::ValueIDNum::@458::@459 s
bool operator!=(const ValueIDNum &Other) const
static ValueIDNum TombstoneValue
uint64_t InstNo
The block where the def happens.
Tracker for converting machine value locations and variable values into variable locations (the outpu...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
DWARF expression.
DbgVariableFragmentInfo FragmentInfo
static bool isEqualExpression(const DIExpression *FirstExpr, bool FirstIndirect, const DIExpression *SecondExpr, bool SecondIndirect)
Determines whether two debug values should produce equivalent DWARF expressions, using their DIExpres...
uint64_t getNumLocationOperands() const
Return the number of unique location operands referred to (via DW_OP_LLVM_arg) in this expression; th...
Debug location.
This class represents an Operation in the Expression.
Identifies a unique instance of a variable.
static bool isDefaultFragment(const FragmentInfo F)
const DILocation * getInlinedAt() const
FragmentInfo getFragmentOrDefault() const
const DILocalVariable * getVariable() const
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
unsigned size() const
Definition: DenseMap.h:99
iterator end()
Definition: DenseMap.h:84
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:146
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
StorageT::size_type size() const
Definition: IndexedMap.h:79
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:346
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StackOffset holds a fixed and a scalable offset in bytes.
Definition: TypeSize.h:33
static StackOffset getScalable(int64_t Scalable)
Definition: TypeSize.h:43
static StackOffset getFixed(int64_t Fixed)
Definition: TypeSize.h:42
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Information about stack frame layout on the target.
TargetInstrInfo - Interface to description of machine instruction set.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TypeSize getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
unsigned getSubRegIdxSize(unsigned Idx) const
Get the size of the bit range covered by a sub-register index.
unsigned getSubRegIdxOffset(unsigned Idx) const
Get the offset of the bit range covered by a sub-register index.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
Twine concat(const Twine &Suffix) const
Definition: Twine.h:525
UniqueVector - This class produces a sequential ID number (base 1) for each unique entry that is adde...
Definition: UniqueVector.h:24
See the file comment.
Definition: ValueMap.h:84
LLVM Value Representation.
Definition: Value.h:74
A range adaptor for a pair of iterators.
std::pair< DebugVariable, const DILocation * > VarAndLoc
std::pair< const DILocalVariable *, DIExpression::FragmentInfo > FragmentOfVar
Types for recording sets of variable fragments that overlap.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
hash_code hash_value(const FixedPointSemantics &Val)
Definition: APFixedPoint.h:127
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1176
@ Other
Any other memory.
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Definition: STLExtras.h:2032
An ID used in the DbgOpIDMap (below) to lookup a stored DbgOp.
bool operator==(const DbgOpID &Other) const
bool operator!=(const DbgOpID &Other) const
void dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const
DbgOpID(bool IsConst, uint32_t Index)
TODO: Might pack better if we changed this to a Struct of Arrays, since MachineOperand is width 32,...
void dump(const MLocTracker *MTrack) const
DbgOp(MachineOperand MO)
A collection of ValueTables, one per BB in a function, with convenient accessor methods.
ValueTable & operator[](int MBBNum) const
Returns the ValueTable associated with the MachineBasicBlock whose number is MBBNum.
void ejectTableForBlock(const MachineBasicBlock &MBB)
Frees the memory of the ValueTable associated with MBB.
ValueTable & tableForEntryMBB() const
Returns the ValueTable associated with the entry MachineBasicBlock.
FuncValueTable(int NumBBs, int NumLocs)
ValueTable & operator[](const MachineBasicBlock &MBB) const
Returns the ValueTable associated with MBB.
bool hasTableFor(MachineBasicBlock &MBB) const
Returns true if the ValueTable associated with MBB has not been freed.
A DbgOp whose ID (if any) has resolved to an actual location, LocIdx.
bool operator==(const ResolvedDbgOp &Other) const
void dump(const MLocTracker *MTrack) const
bool operator<(const SpillLoc &Other) const
bool operator==(const SpillLoc &Other) const
static bool isEqual(const LocIdx &A, const LocIdx &B)
static unsigned getHashValue(const LocIdx &Loc)
static unsigned getHashValue(const ValueIDNum &Val)
static bool isEqual(const ValueIDNum &A, const ValueIDNum &B)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:52