LLVM 19.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
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(); }
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;
85 bool operator==(const SpillLoc &Other) const {
86 return std::make_pair(SpillBase, SpillOffset) ==
87 std::make_pair(Other.SpillBase, Other.SpillOffset);
88 }
89 bool operator<(const SpillLoc &Other) const {
90 return std::make_tuple(SpillBase, SpillOffset.getFixed(),
92 std::make_tuple(Other.SpillBase, Other.SpillOffset.getFixed(),
93 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.
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.
114 : NUM_LOC_BITS; /// The machine location where the def happens.
115 } s;
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
127 u.s = {Block, Inst, Loc};
128 }
129
131 u.s = {Block, Inst, 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
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(Twine(u.s.BlockNo)
160 .concat(Twine(", inst: ")
161 .concat((u.s.InstNo ? Twine(u.s.InstNo)
162 : Twine("live-in"))
163 .concat(Twine(", loc: ").concat(
164 Twine(mlocname)))
165 .concat(Twine("}")))))
166 .str();
167 }
168
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> {
189 static inline ValueIDNum getTombstoneKey() {
191 }
192
193 static unsigned getHashValue(const ValueIDNum &Val) {
194 return hash_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.
209
210/// A collection of ValueTables, one per BB in a function, with convenient
211/// accessor methods.
213 FuncValueTable(int NumBBs, int NumLocs) {
214 Storage.reserve(NumBBs);
215 for (int i = 0; i != NumBBs; ++i)
216 Storage.push_back(
217 std::make_unique<ValueTable>(NumLocs, ValueIDNum::EmptyValue));
218 }
219
220 /// Returns the ValueTable associated with MBB.
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.
238 return Storage[MBB.getNumber()] != nullptr;
239 }
240
241 /// Frees the memory of the ValueTable associated with 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.
251};
252
253/// Thin wrapper around an integer -- designed to give more type safety to
254/// spill location numbers.
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.
276public:
279
280 /// Extract properties from an existing DBG_VALUE instruction.
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
292 Other.Indirect);
293 }
294
296 return std::tie(DIExpr, Indirect, IsVariadic) ==
297 std::tie(Other.DIExpr, Other.Indirect, Other.IsVariadic);
298 }
299
301 return !(*this == Other);
302 }
303
304 unsigned getLocationOpCount() const {
306 }
307
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 {
325 };
327
328 DbgOp() : ID(ValueIDNum::EmptyValue), IsConst(false) {}
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.
344 union {
347 };
349
352
353 bool operator==(const ResolvedDbgOp &Other) const {
354 if (IsConst != Other.IsConst)
355 return false;
356 if (IsConst)
357 return MO.isIdenticalTo(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 {
377 };
378
379 union {
382 };
383
385 static_assert(sizeof(DbgOpID) == 4, "DbgOpID should fit within 4 bytes.");
386 }
388 DbgOpID(bool IsConst, uint32_t Index) : ID({IsConst, Index}) {}
389
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).
411
414
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.
424 if (Op.isUndef())
425 return DbgOpID::UndefID;
426 if (Op.IsConst)
427 return insertConstOp(Op.MO);
428 return insertValueOp(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.
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(MO);
450 if (ExistingIt != ConstOpToID.end())
451 return ExistingIt->second;
452 DbgOpID ID(true, ConstOps.size());
453 ConstOpToID.insert(std::make_pair(MO, ID));
454 ConstOps.push_back(MO);
455 return ID;
456 }
457 DbgOpID insertValueOp(ValueIDNum VID) {
458 auto ExistingIt = ValueOpToID.find(VID);
459 if (ExistingIt != ValueOpToID.end())
460 return ExistingIt->second;
461 DbgOpID ID(false, ValueOps.size());
462 ValueOpToID.insert(std::make_pair(VID, ID));
463 ValueOps.push_back(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.
492
493 /// Qualifiers for the ValueIDNum above.
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.
507
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(DbgOps, [](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
530 : OpCount(0), BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
531 assert(Kind == NoVal || Kind == VPHI);
532 }
533
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(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
547 return false;
548 else if (Kind == Def && !equal(getDbgOpIDs(), 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(getDbgOpIDs(), 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()`).
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 {
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(Idx).isConst() != Other.getDbgOpID(Idx).isConst())
603 return false;
604 }
605 return true;
606 }
607
608 bool isUnjoinedPHI() const { return Kind == VPHI && OpCount == 0; }
609
611 if (!OpCount)
612 return false;
613 return equal(getDbgOpIDs(), Other.getDbgOpIDs());
614 }
615};
616
618public:
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.
661public:
666
667 /// IndexedMap type, mapping from LocIdx to ValueIDNum.
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.
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.
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.
691
692 /// Unique-ification of spill. Used to number them -- their LocID number is
693 /// the index in SpillLocs minus one plus NumRegs.
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.
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.
722
723 /// Inverse of StackSlotIdxes.
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.
732 LocIdx Idx;
733
734 public:
736 public:
738 const LocIdx Idx; /// Read-only index of this location.
739 ValueIDNum &Value; /// Reference to the stored value at this location.
740 };
741
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
757 };
758
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(SpillSubReg);
772 unsigned short Offs = TRI.getSubRegIdxOffset(SpillSubReg);
773 return getLocID(Spill, {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.
780 unsigned SlotNo = Spill.id() - 1;
781 SlotNo *= NumSlotIdxes;
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.
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.
809 assert(ID >= NumRegs);
810 ID -= NumRegs;
811 unsigned Idx = ID % NumSlotIdxes;
812 return StackIdxesToPos.find(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();
851 // SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from
852 // 0
853 SpillLocs = decltype(SpillLocs)();
856
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
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
878 if (Index.isIllegal())
880 return Index;
881 }
882
883 /// Is register R currently tracked by MLocTracker?
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(R);
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(R);
904 LocIdxToIDNum[Idx] = ValueID;
905 }
906
908 unsigned ID = getLocID(R);
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).
918 unsigned ID = getLocID(R);
921 }
922
923 /// Determine the LocIdx of an existing register.
925 unsigned ID = getLocID(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(L)) {
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).
959 return Pos.first;
960 }
961 }
962
964
967 }
968
969 /// Return a range over all locations currently tracked.
971 return llvm::make_range(begin(), 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
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.
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.
996 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
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.
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.
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(std::make_pair(Var, Rec));
1035 if (!Result.second)
1036 Result.first->second = Rec;
1037 Scopes[Var] = MI.getDebugLoc().get();
1038
1039 considerOverlaps(Var, MI.getDebugLoc().get());
1040 }
1041
1042 void considerOverlaps(const DebugVariable &Var, const DILocation *Loc) {
1043 auto Overlaps = OverlappingFragments.find(
1044 {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(FragmentInfo))
1055 OptFragmentInfo = std::nullopt;
1056
1057 DebugVariable Overlapped(Var.getVariable(), OptFragmentInfo,
1058 Var.getInlinedAt());
1060
1061 // Attempt insertion; overwrite if it's already mapped.
1062 auto Result = Vars.insert(std::make_pair(Overlapped, 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
1077public:
1078 friend class ::InstrRefLDVTest;
1079
1081 using OptFragmentInfo = std::optional<DIExpression::FragmentInfo>;
1082
1083 // Helper while building OverlapMap, a map of all fragments seen for a given
1084 // DILocalVariable.
1087
1088 /// Machine location/value transfer function, a mapping of which locations
1089 /// are assigned which new values.
1091
1092 /// Live in/out structure for the variable values: a per-block map of
1093 /// variables to their values.
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.
1104
1105 /// Mapping from lexical scopes to a DILocation in that scope.
1107
1108 /// Mapping from lexical scopes to variables in that scope.
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.
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.
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.
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
1410
1411 std::optional<ValueIDNum> pickOperandPHILoc(
1412 unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,
1413 FuncValueTable &MOutLocs,
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,
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.
1455
1457 void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1458
1459 bool isCalleeSaved(LocIdx L) const;
1460 bool isCalleeSavedReg(Register R) const;
1461
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 */
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:529
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
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.
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.
std::pair< DebugVariable, DbgValue > VarAndLoc
LLVM_DUMP_METHOD void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const
DenseMap< const LexicalScope *, SmallSet< DebugVariable, 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.
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...
MachineInstrBuilder emitLoc(const SmallVectorImpl< ResolvedDbgOp > &DbgOps, const DebugVariable &Var, const DbgValueProperties &Properties)
Create a DBG_VALUE based on debug operands DbgOps.
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
VLocTracker(const OverlapMap &O, const DIExpression *EmptyExpr)
void defVar(const MachineInstr &MI, const DbgValueProperties &Properties, const SmallVectorImpl< DbgOpID > &DebugOps)
void considerOverlaps(const DebugVariable &Var, const DILocation *Loc)
SmallDenseMap< DebugVariable, const DILocation *, 8 > Scopes
MapVector< DebugVariable, DbgValue > Vars
Map DebugVariable to the latest Value it's defined to have.
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)
bool operator!=(const ValueIDNum &Other) const
static ValueIDNum TombstoneValue
struct LiveDebugValues::ValueIDNum::@443::@444 s
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.
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
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:145
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
StorageT::size_type size() const
Definition: IndexedMap.h:79
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
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.
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:321
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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
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.
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< 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:128
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:1689
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:1738
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:1185
@ 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:2034
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
Holds the characteristics of one fragment of a larger variable.
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:50