LLVM 17.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.
208using 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.
212using FuncValueTable = std::unique_ptr<ValueTable[]>;
213
214/// Thin wrapper around an integer -- designed to give more type safety to
215/// spill location numbers.
217public:
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.
237public:
240
241 /// Extract properties from an existing DBG_VALUE instruction.
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
253 Other.Indirect);
254 }
255
257 return std::tie(DIExpr, Indirect, IsVariadic) ==
258 std::tie(Other.DIExpr, Other.Indirect, Other.IsVariadic);
259 }
260
262 return !(*this == Other);
263 }
264
265 unsigned getLocationOpCount() const {
267 }
268
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.
282struct DbgOp {
283 union {
286 };
288
289 DbgOp() : ID(ValueIDNum::EmptyValue), IsConst(false) {}
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.
305 union {
308 };
310
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.
334struct DbgOpID {
338 };
339
340 union {
343 };
344
346 static_assert(sizeof(DbgOpID) == 4, "DbgOpID should fit within 4 bytes.");
347 }
349 DbgOpID(bool IsConst, uint32_t Index) : ID({IsConst, Index}) {}
350
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).
372
375
378
379public:
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.
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.
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
408private:
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.
441class DbgValue {
442private:
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
450public:
451 /// For a NoVal or VPHI DbgValue, which block it was generated in.
453
454 /// Qualifiers for the ValueIDNum above.
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.
468
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
491 : OpCount(0), BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
492 assert(Kind == NoVal || Kind == VPHI);
493 }
494
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()`).
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 {
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
572 if (!OpCount)
573 return false;
574 return equal(getDbgOpIDs(), Other.getDbgOpIDs());
575 }
576};
577
579public:
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.
622public:
627
628 /// IndexedMap type, mapping from LocIdx to ValueIDNum.
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.
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.
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.
652
653 /// Unique-ification of spill. Used to number them -- their LocID number is
654 /// the index in SpillLocs minus one plus NumRegs.
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.
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.
683
684 /// Inverse of StackSlotIdxes.
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.
693 LocIdx Idx;
694
695 public:
697 public:
699 const LocIdx Idx; /// Read-only index of this location.
700 ValueIDNum &Value; /// Reference to the stored value at this location.
701 };
702
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
718 };
719
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.
741 unsigned SlotNo = Spill.id() - 1;
742 SlotNo *= NumSlotIdxes;
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.
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.
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();
812 // SpillLocs.reset(); XXX UniqueVector::reset assumes a SpillLoc casts from
813 // 0
814 SpillLocs = decltype(SpillLocs)();
817
819 }
820
821 /// Set a locaiton to a certain value.
822 void setMLoc(LocIdx L, ValueIDNum Num) {
824 LocIdxToIDNum[L] = Num;
825 }
826
827 /// Read the value of a particular location
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
839 if (Index.isIllegal())
841 return Index;
842 }
843
844 /// Is register R currently tracked by MLocTracker?
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);
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);
865 LocIdxToIDNum[Idx] = ValueID;
866 }
867
869 unsigned ID = getLocID(R);
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).
879 unsigned ID = getLocID(R);
882 }
883
884 /// Determine the LocIdx of an existing register.
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)) {
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).
920 return Pos.first;
921 }
922 }
923
925
928 }
929
930 /// Return a range over all locations currently tracked.
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
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.
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.
957 std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
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.
966public:
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.
980
981public:
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());
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
1038public:
1039 friend class ::InstrRefLDVTest;
1040
1042 using OptFragmentInfo = std::optional<DIExpression::FragmentInfo>;
1043
1044 // Helper while building OverlapMap, a map of all fragments seen for a given
1045 // DILocalVariable.
1048
1049 /// Machine location/value transfer function, a mapping of which locations
1050 /// are assigned which new values.
1052
1053 /// Live in/out structure for the variable values: a per-block map of
1054 /// variables to their values.
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.
1065
1066 /// Mapping from lexical scopes to a DILocation in that scope.
1068
1069 /// Mapping from lexical scopes to variables in that scope.
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.
1076
1077private:
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.
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.
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
1371
1372 std::optional<ValueIDNum> pickOperandPHILoc(
1373 unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,
1374 FuncValueTable &MOutLocs,
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,
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
1413public:
1414 /// Default construct and initialize the pass.
1416
1418 void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
1419
1420 bool isCalleeSaved(LocIdx L) const;
1421 bool isCalleeSavedReg(Register R) const;
1422
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 */
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:492
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
return ToRemove size() > 0
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)
struct LiveDebugValues::ValueIDNum::@425::@426 s
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
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:163
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.
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:150
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
StorageT::size_type size() const
Definition: IndexedMap.h:78
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:68
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:37
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
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:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StackOffset holds a fixed and a scalable offset in bytes.
Definition: TypeSize.h:36
static StackOffset getScalable(int64_t Scalable)
Definition: TypeSize.h:46
static StackOffset getFixed(int64_t Fixed)
Definition: TypeSize.h:45
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...
unsigned 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:506
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::unique_ptr< ValueTable[]> FuncValueTable
Type for a table-of-table-of-values, i.e., the collection of either live-in or live-out values for ea...
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
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
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:1742
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:1209
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:1972
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 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:51