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