xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/LiveDebugVariables.cpp (revision 5e3190f700637fcfc1a52daeaa4a031fdd2557c7)
1 //===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
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 // This file implements the LiveDebugVariables analysis.
10 //
11 // Remove all DBG_VALUE instructions referencing virtual registers and replace
12 // them with a data structure tracking where live user variables are kept - in a
13 // virtual register or in a stack slot.
14 //
15 // Allow the data structure to be updated during register allocation when values
16 // are moved between registers and stack slots. Finally emit new DBG_VALUE
17 // instructions after register allocation is complete.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "LiveDebugVariables.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/IntervalMap.h"
25 #include "llvm/ADT/MapVector.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/SmallSet.h"
28 #include "llvm/ADT/SmallVector.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/StringRef.h"
31 #include "llvm/BinaryFormat/Dwarf.h"
32 #include "llvm/CodeGen/LexicalScopes.h"
33 #include "llvm/CodeGen/LiveInterval.h"
34 #include "llvm/CodeGen/LiveIntervals.h"
35 #include "llvm/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineDominators.h"
37 #include "llvm/CodeGen/MachineFunction.h"
38 #include "llvm/CodeGen/MachineInstr.h"
39 #include "llvm/CodeGen/MachineInstrBuilder.h"
40 #include "llvm/CodeGen/MachineOperand.h"
41 #include "llvm/CodeGen/MachineRegisterInfo.h"
42 #include "llvm/CodeGen/SlotIndexes.h"
43 #include "llvm/CodeGen/TargetInstrInfo.h"
44 #include "llvm/CodeGen/TargetOpcodes.h"
45 #include "llvm/CodeGen/TargetRegisterInfo.h"
46 #include "llvm/CodeGen/TargetSubtargetInfo.h"
47 #include "llvm/CodeGen/VirtRegMap.h"
48 #include "llvm/Config/llvm-config.h"
49 #include "llvm/IR/DebugInfoMetadata.h"
50 #include "llvm/IR/DebugLoc.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/InitializePasses.h"
53 #include "llvm/Pass.h"
54 #include "llvm/Support/Casting.h"
55 #include "llvm/Support/CommandLine.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/raw_ostream.h"
58 #include <algorithm>
59 #include <cassert>
60 #include <iterator>
61 #include <memory>
62 #include <optional>
63 #include <utility>
64 
65 using namespace llvm;
66 
67 #define DEBUG_TYPE "livedebugvars"
68 
69 static cl::opt<bool>
70 EnableLDV("live-debug-variables", cl::init(true),
71           cl::desc("Enable the live debug variables pass"), cl::Hidden);
72 
73 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
74 STATISTIC(NumInsertedDebugLabels, "Number of DBG_LABELs inserted");
75 
76 char LiveDebugVariables::ID = 0;
77 
78 INITIALIZE_PASS_BEGIN(LiveDebugVariables, DEBUG_TYPE,
79                 "Debug Variable Analysis", false, false)
80 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
81 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
82 INITIALIZE_PASS_END(LiveDebugVariables, DEBUG_TYPE,
83                 "Debug Variable Analysis", false, false)
84 
85 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
86   AU.addRequired<MachineDominatorTree>();
87   AU.addRequiredTransitive<LiveIntervals>();
88   AU.setPreservesAll();
89   MachineFunctionPass::getAnalysisUsage(AU);
90 }
91 
92 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) {
93   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
94 }
95 
96 enum : unsigned { UndefLocNo = ~0U };
97 
98 namespace {
99 /// Describes a debug variable value by location number and expression along
100 /// with some flags about the original usage of the location.
101 class DbgVariableValue {
102 public:
103   DbgVariableValue(ArrayRef<unsigned> NewLocs, bool WasIndirect, bool WasList,
104                    const DIExpression &Expr)
105       : WasIndirect(WasIndirect), WasList(WasList), Expression(&Expr) {
106     assert(!(WasIndirect && WasList) &&
107            "DBG_VALUE_LISTs should not be indirect.");
108     SmallVector<unsigned> LocNoVec;
109     for (unsigned LocNo : NewLocs) {
110       auto It = find(LocNoVec, LocNo);
111       if (It == LocNoVec.end())
112         LocNoVec.push_back(LocNo);
113       else {
114         // Loc duplicates an element in LocNos; replace references to Op
115         // with references to the duplicating element.
116         unsigned OpIdx = LocNoVec.size();
117         unsigned DuplicatingIdx = std::distance(LocNoVec.begin(), It);
118         Expression =
119             DIExpression::replaceArg(Expression, OpIdx, DuplicatingIdx);
120       }
121     }
122     // FIXME: Debug values referencing 64+ unique machine locations are rare and
123     // currently unsupported for performance reasons. If we can verify that
124     // performance is acceptable for such debug values, we can increase the
125     // bit-width of LocNoCount to 14 to enable up to 16384 unique machine
126     // locations. We will also need to verify that this does not cause issues
127     // with LiveDebugVariables' use of IntervalMap.
128     if (LocNoVec.size() < 64) {
129       LocNoCount = LocNoVec.size();
130       if (LocNoCount > 0) {
131         LocNos = std::make_unique<unsigned[]>(LocNoCount);
132         std::copy(LocNoVec.begin(), LocNoVec.end(), loc_nos_begin());
133       }
134     } else {
135       LLVM_DEBUG(dbgs() << "Found debug value with 64+ unique machine "
136                            "locations, dropping...\n");
137       LocNoCount = 1;
138       // Turn this into an undef debug value list; right now, the simplest form
139       // of this is an expression with one arg, and an undef debug operand.
140       Expression =
141           DIExpression::get(Expr.getContext(), {dwarf::DW_OP_LLVM_arg, 0});
142       if (auto FragmentInfoOpt = Expr.getFragmentInfo())
143         Expression = *DIExpression::createFragmentExpression(
144             Expression, FragmentInfoOpt->OffsetInBits,
145             FragmentInfoOpt->SizeInBits);
146       LocNos = std::make_unique<unsigned[]>(LocNoCount);
147       LocNos[0] = UndefLocNo;
148     }
149   }
150 
151   DbgVariableValue() : LocNoCount(0), WasIndirect(false), WasList(false) {}
152   DbgVariableValue(const DbgVariableValue &Other)
153       : LocNoCount(Other.LocNoCount), WasIndirect(Other.getWasIndirect()),
154         WasList(Other.getWasList()), Expression(Other.getExpression()) {
155     if (Other.getLocNoCount()) {
156       LocNos.reset(new unsigned[Other.getLocNoCount()]);
157       std::copy(Other.loc_nos_begin(), Other.loc_nos_end(), loc_nos_begin());
158     }
159   }
160 
161   DbgVariableValue &operator=(const DbgVariableValue &Other) {
162     if (this == &Other)
163       return *this;
164     if (Other.getLocNoCount()) {
165       LocNos.reset(new unsigned[Other.getLocNoCount()]);
166       std::copy(Other.loc_nos_begin(), Other.loc_nos_end(), loc_nos_begin());
167     } else {
168       LocNos.release();
169     }
170     LocNoCount = Other.getLocNoCount();
171     WasIndirect = Other.getWasIndirect();
172     WasList = Other.getWasList();
173     Expression = Other.getExpression();
174     return *this;
175   }
176 
177   const DIExpression *getExpression() const { return Expression; }
178   uint8_t getLocNoCount() const { return LocNoCount; }
179   bool containsLocNo(unsigned LocNo) const {
180     return is_contained(loc_nos(), LocNo);
181   }
182   bool getWasIndirect() const { return WasIndirect; }
183   bool getWasList() const { return WasList; }
184   bool isUndef() const { return LocNoCount == 0 || containsLocNo(UndefLocNo); }
185 
186   DbgVariableValue decrementLocNosAfterPivot(unsigned Pivot) const {
187     SmallVector<unsigned, 4> NewLocNos;
188     for (unsigned LocNo : loc_nos())
189       NewLocNos.push_back(LocNo != UndefLocNo && LocNo > Pivot ? LocNo - 1
190                                                                : LocNo);
191     return DbgVariableValue(NewLocNos, WasIndirect, WasList, *Expression);
192   }
193 
194   DbgVariableValue remapLocNos(ArrayRef<unsigned> LocNoMap) const {
195     SmallVector<unsigned> NewLocNos;
196     for (unsigned LocNo : loc_nos())
197       // Undef values don't exist in locations (and thus not in LocNoMap
198       // either) so skip over them. See getLocationNo().
199       NewLocNos.push_back(LocNo == UndefLocNo ? UndefLocNo : LocNoMap[LocNo]);
200     return DbgVariableValue(NewLocNos, WasIndirect, WasList, *Expression);
201   }
202 
203   DbgVariableValue changeLocNo(unsigned OldLocNo, unsigned NewLocNo) const {
204     SmallVector<unsigned> NewLocNos;
205     NewLocNos.assign(loc_nos_begin(), loc_nos_end());
206     auto OldLocIt = find(NewLocNos, OldLocNo);
207     assert(OldLocIt != NewLocNos.end() && "Old location must be present.");
208     *OldLocIt = NewLocNo;
209     return DbgVariableValue(NewLocNos, WasIndirect, WasList, *Expression);
210   }
211 
212   bool hasLocNoGreaterThan(unsigned LocNo) const {
213     return any_of(loc_nos(),
214                   [LocNo](unsigned ThisLocNo) { return ThisLocNo > LocNo; });
215   }
216 
217   void printLocNos(llvm::raw_ostream &OS) const {
218     for (const unsigned &Loc : loc_nos())
219       OS << (&Loc == loc_nos_begin() ? " " : ", ") << Loc;
220   }
221 
222   friend inline bool operator==(const DbgVariableValue &LHS,
223                                 const DbgVariableValue &RHS) {
224     if (std::tie(LHS.LocNoCount, LHS.WasIndirect, LHS.WasList,
225                  LHS.Expression) !=
226         std::tie(RHS.LocNoCount, RHS.WasIndirect, RHS.WasList, RHS.Expression))
227       return false;
228     return std::equal(LHS.loc_nos_begin(), LHS.loc_nos_end(),
229                       RHS.loc_nos_begin());
230   }
231 
232   friend inline bool operator!=(const DbgVariableValue &LHS,
233                                 const DbgVariableValue &RHS) {
234     return !(LHS == RHS);
235   }
236 
237   unsigned *loc_nos_begin() { return LocNos.get(); }
238   const unsigned *loc_nos_begin() const { return LocNos.get(); }
239   unsigned *loc_nos_end() { return LocNos.get() + LocNoCount; }
240   const unsigned *loc_nos_end() const { return LocNos.get() + LocNoCount; }
241   ArrayRef<unsigned> loc_nos() const {
242     return ArrayRef<unsigned>(LocNos.get(), LocNoCount);
243   }
244 
245 private:
246   // IntervalMap requires the value object to be very small, to the extent
247   // that we do not have enough room for an std::vector. Using a C-style array
248   // (with a unique_ptr wrapper for convenience) allows us to optimize for this
249   // specific case by packing the array size into only 6 bits (it is highly
250   // unlikely that any debug value will need 64+ locations).
251   std::unique_ptr<unsigned[]> LocNos;
252   uint8_t LocNoCount : 6;
253   bool WasIndirect : 1;
254   bool WasList : 1;
255   const DIExpression *Expression = nullptr;
256 };
257 } // namespace
258 
259 /// Map of where a user value is live to that value.
260 using LocMap = IntervalMap<SlotIndex, DbgVariableValue, 4>;
261 
262 /// Map of stack slot offsets for spilled locations.
263 /// Non-spilled locations are not added to the map.
264 using SpillOffsetMap = DenseMap<unsigned, unsigned>;
265 
266 /// Cache to save the location where it can be used as the starting
267 /// position as input for calling MachineBasicBlock::SkipPHIsLabelsAndDebug.
268 /// This is to prevent MachineBasicBlock::SkipPHIsLabelsAndDebug from
269 /// repeatedly searching the same set of PHIs/Labels/Debug instructions
270 /// if it is called many times for the same block.
271 using BlockSkipInstsMap =
272     DenseMap<MachineBasicBlock *, MachineBasicBlock::iterator>;
273 
274 namespace {
275 
276 class LDVImpl;
277 
278 /// A user value is a part of a debug info user variable.
279 ///
280 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
281 /// holds part of a user variable. The part is identified by a byte offset.
282 ///
283 /// UserValues are grouped into equivalence classes for easier searching. Two
284 /// user values are related if they are held by the same virtual register. The
285 /// equivalence class is the transitive closure of that relation.
286 class UserValue {
287   const DILocalVariable *Variable; ///< The debug info variable we are part of.
288   /// The part of the variable we describe.
289   const std::optional<DIExpression::FragmentInfo> Fragment;
290   DebugLoc dl;            ///< The debug location for the variable. This is
291                           ///< used by dwarf writer to find lexical scope.
292   UserValue *leader;      ///< Equivalence class leader.
293   UserValue *next = nullptr; ///< Next value in equivalence class, or null.
294 
295   /// Numbered locations referenced by locmap.
296   SmallVector<MachineOperand, 4> locations;
297 
298   /// Map of slot indices where this value is live.
299   LocMap locInts;
300 
301   /// Set of interval start indexes that have been trimmed to the
302   /// lexical scope.
303   SmallSet<SlotIndex, 2> trimmedDefs;
304 
305   /// Insert a DBG_VALUE into MBB at Idx for DbgValue.
306   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
307                         SlotIndex StopIdx, DbgVariableValue DbgValue,
308                         ArrayRef<bool> LocSpills,
309                         ArrayRef<unsigned> SpillOffsets, LiveIntervals &LIS,
310                         const TargetInstrInfo &TII,
311                         const TargetRegisterInfo &TRI,
312                         BlockSkipInstsMap &BBSkipInstsMap);
313 
314   /// Replace OldLocNo ranges with NewRegs ranges where NewRegs
315   /// is live. Returns true if any changes were made.
316   bool splitLocation(unsigned OldLocNo, ArrayRef<Register> NewRegs,
317                      LiveIntervals &LIS);
318 
319 public:
320   /// Create a new UserValue.
321   UserValue(const DILocalVariable *var,
322             std::optional<DIExpression::FragmentInfo> Fragment, DebugLoc L,
323             LocMap::Allocator &alloc)
324       : Variable(var), Fragment(Fragment), dl(std::move(L)), leader(this),
325         locInts(alloc) {}
326 
327   /// Get the leader of this value's equivalence class.
328   UserValue *getLeader() {
329     UserValue *l = leader;
330     while (l != l->leader)
331       l = l->leader;
332     return leader = l;
333   }
334 
335   /// Return the next UserValue in the equivalence class.
336   UserValue *getNext() const { return next; }
337 
338   /// Merge equivalence classes.
339   static UserValue *merge(UserValue *L1, UserValue *L2) {
340     L2 = L2->getLeader();
341     if (!L1)
342       return L2;
343     L1 = L1->getLeader();
344     if (L1 == L2)
345       return L1;
346     // Splice L2 before L1's members.
347     UserValue *End = L2;
348     while (End->next) {
349       End->leader = L1;
350       End = End->next;
351     }
352     End->leader = L1;
353     End->next = L1->next;
354     L1->next = L2;
355     return L1;
356   }
357 
358   /// Return the location number that matches Loc.
359   ///
360   /// For undef values we always return location number UndefLocNo without
361   /// inserting anything in locations. Since locations is a vector and the
362   /// location number is the position in the vector and UndefLocNo is ~0,
363   /// we would need a very big vector to put the value at the right position.
364   unsigned getLocationNo(const MachineOperand &LocMO) {
365     if (LocMO.isReg()) {
366       if (LocMO.getReg() == 0)
367         return UndefLocNo;
368       // For register locations we dont care about use/def and other flags.
369       for (unsigned i = 0, e = locations.size(); i != e; ++i)
370         if (locations[i].isReg() &&
371             locations[i].getReg() == LocMO.getReg() &&
372             locations[i].getSubReg() == LocMO.getSubReg())
373           return i;
374     } else
375       for (unsigned i = 0, e = locations.size(); i != e; ++i)
376         if (LocMO.isIdenticalTo(locations[i]))
377           return i;
378     locations.push_back(LocMO);
379     // We are storing a MachineOperand outside a MachineInstr.
380     locations.back().clearParent();
381     // Don't store def operands.
382     if (locations.back().isReg()) {
383       if (locations.back().isDef())
384         locations.back().setIsDead(false);
385       locations.back().setIsUse();
386     }
387     return locations.size() - 1;
388   }
389 
390   /// Remove (recycle) a location number. If \p LocNo still is used by the
391   /// locInts nothing is done.
392   void removeLocationIfUnused(unsigned LocNo) {
393     // Bail out if LocNo still is used.
394     for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
395       const DbgVariableValue &DbgValue = I.value();
396       if (DbgValue.containsLocNo(LocNo))
397         return;
398     }
399     // Remove the entry in the locations vector, and adjust all references to
400     // location numbers above the removed entry.
401     locations.erase(locations.begin() + LocNo);
402     for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
403       const DbgVariableValue &DbgValue = I.value();
404       if (DbgValue.hasLocNoGreaterThan(LocNo))
405         I.setValueUnchecked(DbgValue.decrementLocNosAfterPivot(LocNo));
406     }
407   }
408 
409   /// Ensure that all virtual register locations are mapped.
410   void mapVirtRegs(LDVImpl *LDV);
411 
412   /// Add a definition point to this user value.
413   void addDef(SlotIndex Idx, ArrayRef<MachineOperand> LocMOs, bool IsIndirect,
414               bool IsList, const DIExpression &Expr) {
415     SmallVector<unsigned> Locs;
416     for (const MachineOperand &Op : LocMOs)
417       Locs.push_back(getLocationNo(Op));
418     DbgVariableValue DbgValue(Locs, IsIndirect, IsList, Expr);
419     // Add a singular (Idx,Idx) -> value mapping.
420     LocMap::iterator I = locInts.find(Idx);
421     if (!I.valid() || I.start() != Idx)
422       I.insert(Idx, Idx.getNextSlot(), std::move(DbgValue));
423     else
424       // A later DBG_VALUE at the same SlotIndex overrides the old location.
425       I.setValue(std::move(DbgValue));
426   }
427 
428   /// Extend the current definition as far as possible down.
429   ///
430   /// Stop when meeting an existing def or when leaving the live
431   /// range of VNI. End points where VNI is no longer live are added to Kills.
432   ///
433   /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
434   /// data-flow analysis to propagate them beyond basic block boundaries.
435   ///
436   /// \param Idx Starting point for the definition.
437   /// \param DbgValue value to propagate.
438   /// \param LiveIntervalInfo For each location number key in this map,
439   /// restricts liveness to where the LiveRange has the value equal to the\
440   /// VNInfo.
441   /// \param [out] Kills Append end points of VNI's live range to Kills.
442   /// \param LIS Live intervals analysis.
443   void
444   extendDef(SlotIndex Idx, DbgVariableValue DbgValue,
445             SmallDenseMap<unsigned, std::pair<LiveRange *, const VNInfo *>>
446                 &LiveIntervalInfo,
447             std::optional<std::pair<SlotIndex, SmallVector<unsigned>>> &Kills,
448             LiveIntervals &LIS);
449 
450   /// The value in LI may be copies to other registers. Determine if
451   /// any of the copies are available at the kill points, and add defs if
452   /// possible.
453   ///
454   /// \param DbgValue Location number of LI->reg, and DIExpression.
455   /// \param LocIntervals Scan for copies of the value for each location in the
456   /// corresponding LiveInterval->reg.
457   /// \param KilledAt The point where the range of DbgValue could be extended.
458   /// \param [in,out] NewDefs Append (Idx, DbgValue) of inserted defs here.
459   void addDefsFromCopies(
460       DbgVariableValue DbgValue,
461       SmallVectorImpl<std::pair<unsigned, LiveInterval *>> &LocIntervals,
462       SlotIndex KilledAt,
463       SmallVectorImpl<std::pair<SlotIndex, DbgVariableValue>> &NewDefs,
464       MachineRegisterInfo &MRI, LiveIntervals &LIS);
465 
466   /// Compute the live intervals of all locations after collecting all their
467   /// def points.
468   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
469                         LiveIntervals &LIS, LexicalScopes &LS);
470 
471   /// Replace OldReg ranges with NewRegs ranges where NewRegs is
472   /// live. Returns true if any changes were made.
473   bool splitRegister(Register OldReg, ArrayRef<Register> NewRegs,
474                      LiveIntervals &LIS);
475 
476   /// Rewrite virtual register locations according to the provided virtual
477   /// register map. Record the stack slot offsets for the locations that
478   /// were spilled.
479   void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
480                         const TargetInstrInfo &TII,
481                         const TargetRegisterInfo &TRI,
482                         SpillOffsetMap &SpillOffsets);
483 
484   /// Recreate DBG_VALUE instruction from data structures.
485   void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
486                        const TargetInstrInfo &TII,
487                        const TargetRegisterInfo &TRI,
488                        const SpillOffsetMap &SpillOffsets,
489                        BlockSkipInstsMap &BBSkipInstsMap);
490 
491   /// Return DebugLoc of this UserValue.
492   const DebugLoc &getDebugLoc() { return dl; }
493 
494   void print(raw_ostream &, const TargetRegisterInfo *);
495 };
496 
497 /// A user label is a part of a debug info user label.
498 class UserLabel {
499   const DILabel *Label; ///< The debug info label we are part of.
500   DebugLoc dl;          ///< The debug location for the label. This is
501                         ///< used by dwarf writer to find lexical scope.
502   SlotIndex loc;        ///< Slot used by the debug label.
503 
504   /// Insert a DBG_LABEL into MBB at Idx.
505   void insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
506                         LiveIntervals &LIS, const TargetInstrInfo &TII,
507                         BlockSkipInstsMap &BBSkipInstsMap);
508 
509 public:
510   /// Create a new UserLabel.
511   UserLabel(const DILabel *label, DebugLoc L, SlotIndex Idx)
512       : Label(label), dl(std::move(L)), loc(Idx) {}
513 
514   /// Does this UserLabel match the parameters?
515   bool matches(const DILabel *L, const DILocation *IA,
516              const SlotIndex Index) const {
517     return Label == L && dl->getInlinedAt() == IA && loc == Index;
518   }
519 
520   /// Recreate DBG_LABEL instruction from data structures.
521   void emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII,
522                       BlockSkipInstsMap &BBSkipInstsMap);
523 
524   /// Return DebugLoc of this UserLabel.
525   const DebugLoc &getDebugLoc() { return dl; }
526 
527   void print(raw_ostream &, const TargetRegisterInfo *);
528 };
529 
530 /// Implementation of the LiveDebugVariables pass.
531 class LDVImpl {
532   LiveDebugVariables &pass;
533   LocMap::Allocator allocator;
534   MachineFunction *MF = nullptr;
535   LiveIntervals *LIS;
536   const TargetRegisterInfo *TRI;
537 
538   /// Position and VReg of a PHI instruction during register allocation.
539   struct PHIValPos {
540     SlotIndex SI;    /// Slot where this PHI occurs.
541     Register Reg;    /// VReg this PHI occurs in.
542     unsigned SubReg; /// Qualifiying subregister for Reg.
543   };
544 
545   /// Map from debug instruction number to PHI position during allocation.
546   std::map<unsigned, PHIValPos> PHIValToPos;
547   /// Index of, for each VReg, which debug instruction numbers and corresponding
548   /// PHIs are sensitive to splitting. Each VReg may have multiple PHI defs,
549   /// at different positions.
550   DenseMap<Register, std::vector<unsigned>> RegToPHIIdx;
551 
552   /// Record for any debug instructions unlinked from their blocks during
553   /// regalloc. Stores the instr and it's location, so that they can be
554   /// re-inserted after regalloc is over.
555   struct InstrPos {
556     MachineInstr *MI;       ///< Debug instruction, unlinked from it's block.
557     SlotIndex Idx;          ///< Slot position where MI should be re-inserted.
558     MachineBasicBlock *MBB; ///< Block that MI was in.
559   };
560 
561   /// Collection of stored debug instructions, preserved until after regalloc.
562   SmallVector<InstrPos, 32> StashedDebugInstrs;
563 
564   /// Whether emitDebugValues is called.
565   bool EmitDone = false;
566 
567   /// Whether the machine function is modified during the pass.
568   bool ModifiedMF = false;
569 
570   /// All allocated UserValue instances.
571   SmallVector<std::unique_ptr<UserValue>, 8> userValues;
572 
573   /// All allocated UserLabel instances.
574   SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
575 
576   /// Map virtual register to eq class leader.
577   using VRMap = DenseMap<unsigned, UserValue *>;
578   VRMap virtRegToEqClass;
579 
580   /// Map to find existing UserValue instances.
581   using UVMap = DenseMap<DebugVariable, UserValue *>;
582   UVMap userVarMap;
583 
584   /// Find or create a UserValue.
585   UserValue *getUserValue(const DILocalVariable *Var,
586                           std::optional<DIExpression::FragmentInfo> Fragment,
587                           const DebugLoc &DL);
588 
589   /// Find the EC leader for VirtReg or null.
590   UserValue *lookupVirtReg(Register VirtReg);
591 
592   /// Add DBG_VALUE instruction to our maps.
593   ///
594   /// \param MI DBG_VALUE instruction
595   /// \param Idx Last valid SLotIndex before instruction.
596   ///
597   /// \returns True if the DBG_VALUE instruction should be deleted.
598   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
599 
600   /// Track variable location debug instructions while using the instruction
601   /// referencing implementation. Such debug instructions do not need to be
602   /// updated during regalloc because they identify instructions rather than
603   /// register locations. However, they needs to be removed from the
604   /// MachineFunction during regalloc, then re-inserted later, to avoid
605   /// disrupting the allocator.
606   ///
607   /// \param MI Any DBG_VALUE / DBG_INSTR_REF / DBG_PHI instruction
608   /// \param Idx Last valid SlotIndex before instruction
609   ///
610   /// \returns Iterator to continue processing from after unlinking.
611   MachineBasicBlock::iterator handleDebugInstr(MachineInstr &MI, SlotIndex Idx);
612 
613   /// Add DBG_LABEL instruction to UserLabel.
614   ///
615   /// \param MI DBG_LABEL instruction
616   /// \param Idx Last valid SlotIndex before instruction.
617   ///
618   /// \returns True if the DBG_LABEL instruction should be deleted.
619   bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx);
620 
621   /// Collect and erase all DBG_VALUE instructions, adding a UserValue def
622   /// for each instruction.
623   ///
624   /// \param mf MachineFunction to be scanned.
625   /// \param InstrRef Whether to operate in instruction referencing mode. If
626   ///        true, most of LiveDebugVariables doesn't run.
627   ///
628   /// \returns True if any debug values were found.
629   bool collectDebugValues(MachineFunction &mf, bool InstrRef);
630 
631   /// Compute the live intervals of all user values after collecting all
632   /// their def points.
633   void computeIntervals();
634 
635 public:
636   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
637 
638   bool runOnMachineFunction(MachineFunction &mf, bool InstrRef);
639 
640   /// Release all memory.
641   void clear() {
642     MF = nullptr;
643     PHIValToPos.clear();
644     RegToPHIIdx.clear();
645     StashedDebugInstrs.clear();
646     userValues.clear();
647     userLabels.clear();
648     virtRegToEqClass.clear();
649     userVarMap.clear();
650     // Make sure we call emitDebugValues if the machine function was modified.
651     assert((!ModifiedMF || EmitDone) &&
652            "Dbg values are not emitted in LDV");
653     EmitDone = false;
654     ModifiedMF = false;
655   }
656 
657   /// Map virtual register to an equivalence class.
658   void mapVirtReg(Register VirtReg, UserValue *EC);
659 
660   /// Replace any PHI referring to OldReg with its corresponding NewReg, if
661   /// present.
662   void splitPHIRegister(Register OldReg, ArrayRef<Register> NewRegs);
663 
664   /// Replace all references to OldReg with NewRegs.
665   void splitRegister(Register OldReg, ArrayRef<Register> NewRegs);
666 
667   /// Recreate DBG_VALUE instruction from data structures.
668   void emitDebugValues(VirtRegMap *VRM);
669 
670   void print(raw_ostream&);
671 };
672 
673 } // end anonymous namespace
674 
675 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
676 static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS,
677                           const LLVMContext &Ctx) {
678   if (!DL)
679     return;
680 
681   auto *Scope = cast<DIScope>(DL.getScope());
682   // Omit the directory, because it's likely to be long and uninteresting.
683   CommentOS << Scope->getFilename();
684   CommentOS << ':' << DL.getLine();
685   if (DL.getCol() != 0)
686     CommentOS << ':' << DL.getCol();
687 
688   DebugLoc InlinedAtDL = DL.getInlinedAt();
689   if (!InlinedAtDL)
690     return;
691 
692   CommentOS << " @[ ";
693   printDebugLoc(InlinedAtDL, CommentOS, Ctx);
694   CommentOS << " ]";
695 }
696 
697 static void printExtendedName(raw_ostream &OS, const DINode *Node,
698                               const DILocation *DL) {
699   const LLVMContext &Ctx = Node->getContext();
700   StringRef Res;
701   unsigned Line = 0;
702   if (const auto *V = dyn_cast<const DILocalVariable>(Node)) {
703     Res = V->getName();
704     Line = V->getLine();
705   } else if (const auto *L = dyn_cast<const DILabel>(Node)) {
706     Res = L->getName();
707     Line = L->getLine();
708   }
709 
710   if (!Res.empty())
711     OS << Res << "," << Line;
712   auto *InlinedAt = DL ? DL->getInlinedAt() : nullptr;
713   if (InlinedAt) {
714     if (DebugLoc InlinedAtDL = InlinedAt) {
715       OS << " @[";
716       printDebugLoc(InlinedAtDL, OS, Ctx);
717       OS << "]";
718     }
719   }
720 }
721 
722 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
723   OS << "!\"";
724   printExtendedName(OS, Variable, dl);
725 
726   OS << "\"\t";
727   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
728     OS << " [" << I.start() << ';' << I.stop() << "):";
729     if (I.value().isUndef())
730       OS << " undef";
731     else {
732       I.value().printLocNos(OS);
733       if (I.value().getWasIndirect())
734         OS << " ind";
735       else if (I.value().getWasList())
736         OS << " list";
737     }
738   }
739   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
740     OS << " Loc" << i << '=';
741     locations[i].print(OS, TRI);
742   }
743   OS << '\n';
744 }
745 
746 void UserLabel::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
747   OS << "!\"";
748   printExtendedName(OS, Label, dl);
749 
750   OS << "\"\t";
751   OS << loc;
752   OS << '\n';
753 }
754 
755 void LDVImpl::print(raw_ostream &OS) {
756   OS << "********** DEBUG VARIABLES **********\n";
757   for (auto &userValue : userValues)
758     userValue->print(OS, TRI);
759   OS << "********** DEBUG LABELS **********\n";
760   for (auto &userLabel : userLabels)
761     userLabel->print(OS, TRI);
762 }
763 #endif
764 
765 void UserValue::mapVirtRegs(LDVImpl *LDV) {
766   for (unsigned i = 0, e = locations.size(); i != e; ++i)
767     if (locations[i].isReg() && locations[i].getReg().isVirtual())
768       LDV->mapVirtReg(locations[i].getReg(), this);
769 }
770 
771 UserValue *
772 LDVImpl::getUserValue(const DILocalVariable *Var,
773                       std::optional<DIExpression::FragmentInfo> Fragment,
774                       const DebugLoc &DL) {
775   // FIXME: Handle partially overlapping fragments. See
776   // https://reviews.llvm.org/D70121#1849741.
777   DebugVariable ID(Var, Fragment, DL->getInlinedAt());
778   UserValue *&UV = userVarMap[ID];
779   if (!UV) {
780     userValues.push_back(
781         std::make_unique<UserValue>(Var, Fragment, DL, allocator));
782     UV = userValues.back().get();
783   }
784   return UV;
785 }
786 
787 void LDVImpl::mapVirtReg(Register VirtReg, UserValue *EC) {
788   assert(VirtReg.isVirtual() && "Only map VirtRegs");
789   UserValue *&Leader = virtRegToEqClass[VirtReg];
790   Leader = UserValue::merge(Leader, EC);
791 }
792 
793 UserValue *LDVImpl::lookupVirtReg(Register VirtReg) {
794   if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
795     return UV->getLeader();
796   return nullptr;
797 }
798 
799 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
800   // DBG_VALUE loc, offset, variable, expr
801   // DBG_VALUE_LIST variable, expr, locs...
802   if (!MI.isDebugValue()) {
803     LLVM_DEBUG(dbgs() << "Can't handle non-DBG_VALUE*: " << MI);
804     return false;
805   }
806   if (!MI.getDebugVariableOp().isMetadata()) {
807     LLVM_DEBUG(dbgs() << "Can't handle DBG_VALUE* with invalid variable: "
808                       << MI);
809     return false;
810   }
811   if (MI.isNonListDebugValue() &&
812       (MI.getNumOperands() != 4 ||
813        !(MI.getDebugOffset().isImm() || MI.getDebugOffset().isReg()))) {
814     LLVM_DEBUG(dbgs() << "Can't handle malformed DBG_VALUE: " << MI);
815     return false;
816   }
817 
818   // Detect invalid DBG_VALUE instructions, with a debug-use of a virtual
819   // register that hasn't been defined yet. If we do not remove those here, then
820   // the re-insertion of the DBG_VALUE instruction after register allocation
821   // will be incorrect.
822   bool Discard = false;
823   for (const MachineOperand &Op : MI.debug_operands()) {
824     if (Op.isReg() && Op.getReg().isVirtual()) {
825       const Register Reg = Op.getReg();
826       if (!LIS->hasInterval(Reg)) {
827         // The DBG_VALUE is described by a virtual register that does not have a
828         // live interval. Discard the DBG_VALUE.
829         Discard = true;
830         LLVM_DEBUG(dbgs() << "Discarding debug info (no LIS interval): " << Idx
831                           << " " << MI);
832       } else {
833         // The DBG_VALUE is only valid if either Reg is live out from Idx, or
834         // Reg is defined dead at Idx (where Idx is the slot index for the
835         // instruction preceding the DBG_VALUE).
836         const LiveInterval &LI = LIS->getInterval(Reg);
837         LiveQueryResult LRQ = LI.Query(Idx);
838         if (!LRQ.valueOutOrDead()) {
839           // We have found a DBG_VALUE with the value in a virtual register that
840           // is not live. Discard the DBG_VALUE.
841           Discard = true;
842           LLVM_DEBUG(dbgs() << "Discarding debug info (reg not live): " << Idx
843                             << " " << MI);
844         }
845       }
846     }
847   }
848 
849   // Get or create the UserValue for (variable,offset) here.
850   bool IsIndirect = MI.isDebugOffsetImm();
851   if (IsIndirect)
852     assert(MI.getDebugOffset().getImm() == 0 &&
853            "DBG_VALUE with nonzero offset");
854   bool IsList = MI.isDebugValueList();
855   const DILocalVariable *Var = MI.getDebugVariable();
856   const DIExpression *Expr = MI.getDebugExpression();
857   UserValue *UV = getUserValue(Var, Expr->getFragmentInfo(), MI.getDebugLoc());
858   if (!Discard)
859     UV->addDef(Idx,
860                ArrayRef<MachineOperand>(MI.debug_operands().begin(),
861                                         MI.debug_operands().end()),
862                IsIndirect, IsList, *Expr);
863   else {
864     MachineOperand MO = MachineOperand::CreateReg(0U, false);
865     MO.setIsDebug();
866     // We should still pass a list the same size as MI.debug_operands() even if
867     // all MOs are undef, so that DbgVariableValue can correctly adjust the
868     // expression while removing the duplicated undefs.
869     SmallVector<MachineOperand, 4> UndefMOs(MI.getNumDebugOperands(), MO);
870     UV->addDef(Idx, UndefMOs, false, IsList, *Expr);
871   }
872   return true;
873 }
874 
875 MachineBasicBlock::iterator LDVImpl::handleDebugInstr(MachineInstr &MI,
876                                                       SlotIndex Idx) {
877   assert(MI.isDebugValueLike() || MI.isDebugPHI());
878 
879   // In instruction referencing mode, there should be no DBG_VALUE instructions
880   // that refer to virtual registers. They might still refer to constants.
881   if (MI.isDebugValueLike())
882     assert(none_of(MI.debug_operands(),
883                    [](const MachineOperand &MO) {
884                      return MO.isReg() && MO.getReg().isVirtual();
885                    }) &&
886            "MIs should not refer to Virtual Registers in InstrRef mode.");
887 
888   // Unlink the instruction, store it in the debug instructions collection.
889   auto NextInst = std::next(MI.getIterator());
890   auto *MBB = MI.getParent();
891   MI.removeFromParent();
892   StashedDebugInstrs.push_back({&MI, Idx, MBB});
893   return NextInst;
894 }
895 
896 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) {
897   // DBG_LABEL label
898   if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) {
899     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
900     return false;
901   }
902 
903   // Get or create the UserLabel for label here.
904   const DILabel *Label = MI.getDebugLabel();
905   const DebugLoc &DL = MI.getDebugLoc();
906   bool Found = false;
907   for (auto const &L : userLabels) {
908     if (L->matches(Label, DL->getInlinedAt(), Idx)) {
909       Found = true;
910       break;
911     }
912   }
913   if (!Found)
914     userLabels.push_back(std::make_unique<UserLabel>(Label, DL, Idx));
915 
916   return true;
917 }
918 
919 bool LDVImpl::collectDebugValues(MachineFunction &mf, bool InstrRef) {
920   bool Changed = false;
921   for (MachineBasicBlock &MBB : mf) {
922     for (MachineBasicBlock::iterator MBBI = MBB.begin(), MBBE = MBB.end();
923          MBBI != MBBE;) {
924       // Use the first debug instruction in the sequence to get a SlotIndex
925       // for following consecutive debug instructions.
926       if (!MBBI->isDebugOrPseudoInstr()) {
927         ++MBBI;
928         continue;
929       }
930       // Debug instructions has no slot index. Use the previous
931       // non-debug instruction's SlotIndex as its SlotIndex.
932       SlotIndex Idx =
933           MBBI == MBB.begin()
934               ? LIS->getMBBStartIdx(&MBB)
935               : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
936       // Handle consecutive debug instructions with the same slot index.
937       do {
938         // In instruction referencing mode, pass each instr to handleDebugInstr
939         // to be unlinked. Ignore DBG_VALUE_LISTs -- they refer to vregs, and
940         // need to go through the normal live interval splitting process.
941         if (InstrRef && (MBBI->isNonListDebugValue() || MBBI->isDebugPHI() ||
942                          MBBI->isDebugRef())) {
943           MBBI = handleDebugInstr(*MBBI, Idx);
944           Changed = true;
945         // In normal debug mode, use the dedicated DBG_VALUE / DBG_LABEL handler
946         // to track things through register allocation, and erase the instr.
947         } else if ((MBBI->isDebugValue() && handleDebugValue(*MBBI, Idx)) ||
948                    (MBBI->isDebugLabel() && handleDebugLabel(*MBBI, Idx))) {
949           MBBI = MBB.erase(MBBI);
950           Changed = true;
951         } else
952           ++MBBI;
953       } while (MBBI != MBBE && MBBI->isDebugOrPseudoInstr());
954     }
955   }
956   return Changed;
957 }
958 
959 void UserValue::extendDef(
960     SlotIndex Idx, DbgVariableValue DbgValue,
961     SmallDenseMap<unsigned, std::pair<LiveRange *, const VNInfo *>>
962         &LiveIntervalInfo,
963     std::optional<std::pair<SlotIndex, SmallVector<unsigned>>> &Kills,
964     LiveIntervals &LIS) {
965   SlotIndex Start = Idx;
966   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
967   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
968   LocMap::iterator I = locInts.find(Start);
969 
970   // Limit to the intersection of the VNIs' live ranges.
971   for (auto &LII : LiveIntervalInfo) {
972     LiveRange *LR = LII.second.first;
973     assert(LR && LII.second.second && "Missing range info for Idx.");
974     LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
975     assert(Segment && Segment->valno == LII.second.second &&
976            "Invalid VNInfo for Idx given?");
977     if (Segment->end < Stop) {
978       Stop = Segment->end;
979       Kills = {Stop, {LII.first}};
980     } else if (Segment->end == Stop && Kills) {
981       // If multiple locations end at the same place, track all of them in
982       // Kills.
983       Kills->second.push_back(LII.first);
984     }
985   }
986 
987   // There could already be a short def at Start.
988   if (I.valid() && I.start() <= Start) {
989     // Stop when meeting a different location or an already extended interval.
990     Start = Start.getNextSlot();
991     if (I.value() != DbgValue || I.stop() != Start) {
992       // Clear `Kills`, as we have a new def available.
993       Kills = std::nullopt;
994       return;
995     }
996     // This is a one-slot placeholder. Just skip it.
997     ++I;
998   }
999 
1000   // Limited by the next def.
1001   if (I.valid() && I.start() < Stop) {
1002     Stop = I.start();
1003     // Clear `Kills`, as we have a new def available.
1004     Kills = std::nullopt;
1005   }
1006 
1007   if (Start < Stop) {
1008     DbgVariableValue ExtDbgValue(DbgValue);
1009     I.insert(Start, Stop, std::move(ExtDbgValue));
1010   }
1011 }
1012 
1013 void UserValue::addDefsFromCopies(
1014     DbgVariableValue DbgValue,
1015     SmallVectorImpl<std::pair<unsigned, LiveInterval *>> &LocIntervals,
1016     SlotIndex KilledAt,
1017     SmallVectorImpl<std::pair<SlotIndex, DbgVariableValue>> &NewDefs,
1018     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
1019   // Don't track copies from physregs, there are too many uses.
1020   if (any_of(LocIntervals,
1021              [](auto LocI) { return !LocI.second->reg().isVirtual(); }))
1022     return;
1023 
1024   // Collect all the (vreg, valno) pairs that are copies of LI.
1025   SmallDenseMap<unsigned,
1026                 SmallVector<std::pair<LiveInterval *, const VNInfo *>, 4>>
1027       CopyValues;
1028   for (auto &LocInterval : LocIntervals) {
1029     unsigned LocNo = LocInterval.first;
1030     LiveInterval *LI = LocInterval.second;
1031     for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg())) {
1032       MachineInstr *MI = MO.getParent();
1033       // Copies of the full value.
1034       if (MO.getSubReg() || !MI->isCopy())
1035         continue;
1036       Register DstReg = MI->getOperand(0).getReg();
1037 
1038       // Don't follow copies to physregs. These are usually setting up call
1039       // arguments, and the argument registers are always call clobbered. We are
1040       // better off in the source register which could be a callee-saved
1041       // register, or it could be spilled.
1042       if (!DstReg.isVirtual())
1043         continue;
1044 
1045       // Is the value extended to reach this copy? If not, another def may be
1046       // blocking it, or we are looking at a wrong value of LI.
1047       SlotIndex Idx = LIS.getInstructionIndex(*MI);
1048       LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
1049       if (!I.valid() || I.value() != DbgValue)
1050         continue;
1051 
1052       if (!LIS.hasInterval(DstReg))
1053         continue;
1054       LiveInterval *DstLI = &LIS.getInterval(DstReg);
1055       const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
1056       assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
1057       CopyValues[LocNo].push_back(std::make_pair(DstLI, DstVNI));
1058     }
1059   }
1060 
1061   if (CopyValues.empty())
1062     return;
1063 
1064 #if !defined(NDEBUG)
1065   for (auto &LocInterval : LocIntervals)
1066     LLVM_DEBUG(dbgs() << "Got " << CopyValues[LocInterval.first].size()
1067                       << " copies of " << *LocInterval.second << '\n');
1068 #endif
1069 
1070   // Try to add defs of the copied values for the kill point. Check that there
1071   // isn't already a def at Idx.
1072   LocMap::iterator I = locInts.find(KilledAt);
1073   if (I.valid() && I.start() <= KilledAt)
1074     return;
1075   DbgVariableValue NewValue(DbgValue);
1076   for (auto &LocInterval : LocIntervals) {
1077     unsigned LocNo = LocInterval.first;
1078     bool FoundCopy = false;
1079     for (auto &LIAndVNI : CopyValues[LocNo]) {
1080       LiveInterval *DstLI = LIAndVNI.first;
1081       const VNInfo *DstVNI = LIAndVNI.second;
1082       if (DstLI->getVNInfoAt(KilledAt) != DstVNI)
1083         continue;
1084       LLVM_DEBUG(dbgs() << "Kill at " << KilledAt << " covered by valno #"
1085                         << DstVNI->id << " in " << *DstLI << '\n');
1086       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
1087       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
1088       unsigned NewLocNo = getLocationNo(CopyMI->getOperand(0));
1089       NewValue = NewValue.changeLocNo(LocNo, NewLocNo);
1090       FoundCopy = true;
1091       break;
1092     }
1093     // If there are any killed locations we can't find a copy for, we can't
1094     // extend the variable value.
1095     if (!FoundCopy)
1096       return;
1097   }
1098   I.insert(KilledAt, KilledAt.getNextSlot(), NewValue);
1099   NewDefs.push_back(std::make_pair(KilledAt, NewValue));
1100 }
1101 
1102 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
1103                                  const TargetRegisterInfo &TRI,
1104                                  LiveIntervals &LIS, LexicalScopes &LS) {
1105   SmallVector<std::pair<SlotIndex, DbgVariableValue>, 16> Defs;
1106 
1107   // Collect all defs to be extended (Skipping undefs).
1108   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
1109     if (!I.value().isUndef())
1110       Defs.push_back(std::make_pair(I.start(), I.value()));
1111 
1112   // Extend all defs, and possibly add new ones along the way.
1113   for (unsigned i = 0; i != Defs.size(); ++i) {
1114     SlotIndex Idx = Defs[i].first;
1115     DbgVariableValue DbgValue = Defs[i].second;
1116     SmallDenseMap<unsigned, std::pair<LiveRange *, const VNInfo *>> LIs;
1117     SmallVector<const VNInfo *, 4> VNIs;
1118     bool ShouldExtendDef = false;
1119     for (unsigned LocNo : DbgValue.loc_nos()) {
1120       const MachineOperand &LocMO = locations[LocNo];
1121       if (!LocMO.isReg() || !LocMO.getReg().isVirtual()) {
1122         ShouldExtendDef |= !LocMO.isReg();
1123         continue;
1124       }
1125       ShouldExtendDef = true;
1126       LiveInterval *LI = nullptr;
1127       const VNInfo *VNI = nullptr;
1128       if (LIS.hasInterval(LocMO.getReg())) {
1129         LI = &LIS.getInterval(LocMO.getReg());
1130         VNI = LI->getVNInfoAt(Idx);
1131       }
1132       if (LI && VNI)
1133         LIs[LocNo] = {LI, VNI};
1134     }
1135     if (ShouldExtendDef) {
1136       std::optional<std::pair<SlotIndex, SmallVector<unsigned>>> Kills;
1137       extendDef(Idx, DbgValue, LIs, Kills, LIS);
1138 
1139       if (Kills) {
1140         SmallVector<std::pair<unsigned, LiveInterval *>, 2> KilledLocIntervals;
1141         bool AnySubreg = false;
1142         for (unsigned LocNo : Kills->second) {
1143           const MachineOperand &LocMO = this->locations[LocNo];
1144           if (LocMO.getSubReg()) {
1145             AnySubreg = true;
1146             break;
1147           }
1148           LiveInterval *LI = &LIS.getInterval(LocMO.getReg());
1149           KilledLocIntervals.push_back({LocNo, LI});
1150         }
1151 
1152         // FIXME: Handle sub-registers in addDefsFromCopies. The problem is that
1153         // if the original location for example is %vreg0:sub_hi, and we find a
1154         // full register copy in addDefsFromCopies (at the moment it only
1155         // handles full register copies), then we must add the sub1 sub-register
1156         // index to the new location. However, that is only possible if the new
1157         // virtual register is of the same regclass (or if there is an
1158         // equivalent sub-register in that regclass). For now, simply skip
1159         // handling copies if a sub-register is involved.
1160         if (!AnySubreg)
1161           addDefsFromCopies(DbgValue, KilledLocIntervals, Kills->first, Defs,
1162                             MRI, LIS);
1163       }
1164     }
1165 
1166     // For physregs, we only mark the start slot idx. DwarfDebug will see it
1167     // as if the DBG_VALUE is valid up until the end of the basic block, or
1168     // the next def of the physical register. So we do not need to extend the
1169     // range. It might actually happen that the DBG_VALUE is the last use of
1170     // the physical register (e.g. if this is an unused input argument to a
1171     // function).
1172   }
1173 
1174   // The computed intervals may extend beyond the range of the debug
1175   // location's lexical scope. In this case, splitting of an interval
1176   // can result in an interval outside of the scope being created,
1177   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
1178   // this, trim the intervals to the lexical scope in the case of inlined
1179   // variables, since heavy inlining may cause production of dramatically big
1180   // number of DBG_VALUEs to be generated.
1181   if (!dl.getInlinedAt())
1182     return;
1183 
1184   LexicalScope *Scope = LS.findLexicalScope(dl);
1185   if (!Scope)
1186     return;
1187 
1188   SlotIndex PrevEnd;
1189   LocMap::iterator I = locInts.begin();
1190 
1191   // Iterate over the lexical scope ranges. Each time round the loop
1192   // we check the intervals for overlap with the end of the previous
1193   // range and the start of the next. The first range is handled as
1194   // a special case where there is no PrevEnd.
1195   for (const InsnRange &Range : Scope->getRanges()) {
1196     SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
1197     SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
1198 
1199     // Variable locations at the first instruction of a block should be
1200     // based on the block's SlotIndex, not the first instruction's index.
1201     if (Range.first == Range.first->getParent()->begin())
1202       RStart = LIS.getSlotIndexes()->getIndexBefore(*Range.first);
1203 
1204     // At the start of each iteration I has been advanced so that
1205     // I.stop() >= PrevEnd. Check for overlap.
1206     if (PrevEnd && I.start() < PrevEnd) {
1207       SlotIndex IStop = I.stop();
1208       DbgVariableValue DbgValue = I.value();
1209 
1210       // Stop overlaps previous end - trim the end of the interval to
1211       // the scope range.
1212       I.setStopUnchecked(PrevEnd);
1213       ++I;
1214 
1215       // If the interval also overlaps the start of the "next" (i.e.
1216       // current) range create a new interval for the remainder (which
1217       // may be further trimmed).
1218       if (RStart < IStop)
1219         I.insert(RStart, IStop, DbgValue);
1220     }
1221 
1222     // Advance I so that I.stop() >= RStart, and check for overlap.
1223     I.advanceTo(RStart);
1224     if (!I.valid())
1225       return;
1226 
1227     if (I.start() < RStart) {
1228       // Interval start overlaps range - trim to the scope range.
1229       I.setStartUnchecked(RStart);
1230       // Remember that this interval was trimmed.
1231       trimmedDefs.insert(RStart);
1232     }
1233 
1234     // The end of a lexical scope range is the last instruction in the
1235     // range. To convert to an interval we need the index of the
1236     // instruction after it.
1237     REnd = REnd.getNextIndex();
1238 
1239     // Advance I to first interval outside current range.
1240     I.advanceTo(REnd);
1241     if (!I.valid())
1242       return;
1243 
1244     PrevEnd = REnd;
1245   }
1246 
1247   // Check for overlap with end of final range.
1248   if (PrevEnd && I.start() < PrevEnd)
1249     I.setStopUnchecked(PrevEnd);
1250 }
1251 
1252 void LDVImpl::computeIntervals() {
1253   LexicalScopes LS;
1254   LS.initialize(*MF);
1255 
1256   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
1257     userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
1258     userValues[i]->mapVirtRegs(this);
1259   }
1260 }
1261 
1262 bool LDVImpl::runOnMachineFunction(MachineFunction &mf, bool InstrRef) {
1263   clear();
1264   MF = &mf;
1265   LIS = &pass.getAnalysis<LiveIntervals>();
1266   TRI = mf.getSubtarget().getRegisterInfo();
1267   LLVM_DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
1268                     << mf.getName() << " **********\n");
1269 
1270   bool Changed = collectDebugValues(mf, InstrRef);
1271   computeIntervals();
1272   LLVM_DEBUG(print(dbgs()));
1273 
1274   // Collect the set of VReg / SlotIndexs where PHIs occur; index the sensitive
1275   // VRegs too, for when we're notified of a range split.
1276   SlotIndexes *Slots = LIS->getSlotIndexes();
1277   for (const auto &PHIIt : MF->DebugPHIPositions) {
1278     const MachineFunction::DebugPHIRegallocPos &Position = PHIIt.second;
1279     MachineBasicBlock *MBB = Position.MBB;
1280     Register Reg = Position.Reg;
1281     unsigned SubReg = Position.SubReg;
1282     SlotIndex SI = Slots->getMBBStartIdx(MBB);
1283     PHIValPos VP = {SI, Reg, SubReg};
1284     PHIValToPos.insert(std::make_pair(PHIIt.first, VP));
1285     RegToPHIIdx[Reg].push_back(PHIIt.first);
1286   }
1287 
1288   ModifiedMF = Changed;
1289   return Changed;
1290 }
1291 
1292 static void removeDebugInstrs(MachineFunction &mf) {
1293   for (MachineBasicBlock &MBB : mf) {
1294     for (MachineInstr &MI : llvm::make_early_inc_range(MBB))
1295       if (MI.isDebugInstr())
1296         MBB.erase(&MI);
1297   }
1298 }
1299 
1300 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
1301   if (!EnableLDV)
1302     return false;
1303   if (!mf.getFunction().getSubprogram()) {
1304     removeDebugInstrs(mf);
1305     return false;
1306   }
1307 
1308   // Have we been asked to track variable locations using instruction
1309   // referencing?
1310   bool InstrRef = mf.useDebugInstrRef();
1311 
1312   if (!pImpl)
1313     pImpl = new LDVImpl(this);
1314   return static_cast<LDVImpl *>(pImpl)->runOnMachineFunction(mf, InstrRef);
1315 }
1316 
1317 void LiveDebugVariables::releaseMemory() {
1318   if (pImpl)
1319     static_cast<LDVImpl*>(pImpl)->clear();
1320 }
1321 
1322 LiveDebugVariables::~LiveDebugVariables() {
1323   if (pImpl)
1324     delete static_cast<LDVImpl*>(pImpl);
1325 }
1326 
1327 //===----------------------------------------------------------------------===//
1328 //                           Live Range Splitting
1329 //===----------------------------------------------------------------------===//
1330 
1331 bool
1332 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<Register> NewRegs,
1333                          LiveIntervals& LIS) {
1334   LLVM_DEBUG({
1335     dbgs() << "Splitting Loc" << OldLocNo << '\t';
1336     print(dbgs(), nullptr);
1337   });
1338   bool DidChange = false;
1339   LocMap::iterator LocMapI;
1340   LocMapI.setMap(locInts);
1341   for (Register NewReg : NewRegs) {
1342     LiveInterval *LI = &LIS.getInterval(NewReg);
1343     if (LI->empty())
1344       continue;
1345 
1346     // Don't allocate the new LocNo until it is needed.
1347     unsigned NewLocNo = UndefLocNo;
1348 
1349     // Iterate over the overlaps between locInts and LI.
1350     LocMapI.find(LI->beginIndex());
1351     if (!LocMapI.valid())
1352       continue;
1353     LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
1354     LiveInterval::iterator LIE = LI->end();
1355     while (LocMapI.valid() && LII != LIE) {
1356       // At this point, we know that LocMapI.stop() > LII->start.
1357       LII = LI->advanceTo(LII, LocMapI.start());
1358       if (LII == LIE)
1359         break;
1360 
1361       // Now LII->end > LocMapI.start(). Do we have an overlap?
1362       if (LocMapI.value().containsLocNo(OldLocNo) &&
1363           LII->start < LocMapI.stop()) {
1364         // Overlapping correct location. Allocate NewLocNo now.
1365         if (NewLocNo == UndefLocNo) {
1366           MachineOperand MO = MachineOperand::CreateReg(LI->reg(), false);
1367           MO.setSubReg(locations[OldLocNo].getSubReg());
1368           NewLocNo = getLocationNo(MO);
1369           DidChange = true;
1370         }
1371 
1372         SlotIndex LStart = LocMapI.start();
1373         SlotIndex LStop = LocMapI.stop();
1374         DbgVariableValue OldDbgValue = LocMapI.value();
1375 
1376         // Trim LocMapI down to the LII overlap.
1377         if (LStart < LII->start)
1378           LocMapI.setStartUnchecked(LII->start);
1379         if (LStop > LII->end)
1380           LocMapI.setStopUnchecked(LII->end);
1381 
1382         // Change the value in the overlap. This may trigger coalescing.
1383         LocMapI.setValue(OldDbgValue.changeLocNo(OldLocNo, NewLocNo));
1384 
1385         // Re-insert any removed OldDbgValue ranges.
1386         if (LStart < LocMapI.start()) {
1387           LocMapI.insert(LStart, LocMapI.start(), OldDbgValue);
1388           ++LocMapI;
1389           assert(LocMapI.valid() && "Unexpected coalescing");
1390         }
1391         if (LStop > LocMapI.stop()) {
1392           ++LocMapI;
1393           LocMapI.insert(LII->end, LStop, OldDbgValue);
1394           --LocMapI;
1395         }
1396       }
1397 
1398       // Advance to the next overlap.
1399       if (LII->end < LocMapI.stop()) {
1400         if (++LII == LIE)
1401           break;
1402         LocMapI.advanceTo(LII->start);
1403       } else {
1404         ++LocMapI;
1405         if (!LocMapI.valid())
1406           break;
1407         LII = LI->advanceTo(LII, LocMapI.start());
1408       }
1409     }
1410   }
1411 
1412   // Finally, remove OldLocNo unless it is still used by some interval in the
1413   // locInts map. One case when OldLocNo still is in use is when the register
1414   // has been spilled. In such situations the spilled register is kept as a
1415   // location until rewriteLocations is called (VirtRegMap is mapping the old
1416   // register to the spill slot). So for a while we can have locations that map
1417   // to virtual registers that have been removed from both the MachineFunction
1418   // and from LiveIntervals.
1419   //
1420   // We may also just be using the location for a value with a different
1421   // expression.
1422   removeLocationIfUnused(OldLocNo);
1423 
1424   LLVM_DEBUG({
1425     dbgs() << "Split result: \t";
1426     print(dbgs(), nullptr);
1427   });
1428   return DidChange;
1429 }
1430 
1431 bool
1432 UserValue::splitRegister(Register OldReg, ArrayRef<Register> NewRegs,
1433                          LiveIntervals &LIS) {
1434   bool DidChange = false;
1435   // Split locations referring to OldReg. Iterate backwards so splitLocation can
1436   // safely erase unused locations.
1437   for (unsigned i = locations.size(); i ; --i) {
1438     unsigned LocNo = i-1;
1439     const MachineOperand *Loc = &locations[LocNo];
1440     if (!Loc->isReg() || Loc->getReg() != OldReg)
1441       continue;
1442     DidChange |= splitLocation(LocNo, NewRegs, LIS);
1443   }
1444   return DidChange;
1445 }
1446 
1447 void LDVImpl::splitPHIRegister(Register OldReg, ArrayRef<Register> NewRegs) {
1448   auto RegIt = RegToPHIIdx.find(OldReg);
1449   if (RegIt == RegToPHIIdx.end())
1450     return;
1451 
1452   std::vector<std::pair<Register, unsigned>> NewRegIdxes;
1453   // Iterate over all the debug instruction numbers affected by this split.
1454   for (unsigned InstrID : RegIt->second) {
1455     auto PHIIt = PHIValToPos.find(InstrID);
1456     assert(PHIIt != PHIValToPos.end());
1457     const SlotIndex &Slot = PHIIt->second.SI;
1458     assert(OldReg == PHIIt->second.Reg);
1459 
1460     // Find the new register that covers this position.
1461     for (auto NewReg : NewRegs) {
1462       const LiveInterval &LI = LIS->getInterval(NewReg);
1463       auto LII = LI.find(Slot);
1464       if (LII != LI.end() && LII->start <= Slot) {
1465         // This new register covers this PHI position, record this for indexing.
1466         NewRegIdxes.push_back(std::make_pair(NewReg, InstrID));
1467         // Record that this value lives in a different VReg now.
1468         PHIIt->second.Reg = NewReg;
1469         break;
1470       }
1471     }
1472 
1473     // If we do not find a new register covering this PHI, then register
1474     // allocation has dropped its location, for example because it's not live.
1475     // The old VReg will not be mapped to a physreg, and the instruction
1476     // number will have been optimized out.
1477   }
1478 
1479   // Re-create register index using the new register numbers.
1480   RegToPHIIdx.erase(RegIt);
1481   for (auto &RegAndInstr : NewRegIdxes)
1482     RegToPHIIdx[RegAndInstr.first].push_back(RegAndInstr.second);
1483 }
1484 
1485 void LDVImpl::splitRegister(Register OldReg, ArrayRef<Register> NewRegs) {
1486   // Consider whether this split range affects any PHI locations.
1487   splitPHIRegister(OldReg, NewRegs);
1488 
1489   // Check whether any intervals mapped by a DBG_VALUE were split and need
1490   // updating.
1491   bool DidChange = false;
1492   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
1493     DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
1494 
1495   if (!DidChange)
1496     return;
1497 
1498   // Map all of the new virtual registers.
1499   UserValue *UV = lookupVirtReg(OldReg);
1500   for (Register NewReg : NewRegs)
1501     mapVirtReg(NewReg, UV);
1502 }
1503 
1504 void LiveDebugVariables::
1505 splitRegister(Register OldReg, ArrayRef<Register> NewRegs, LiveIntervals &LIS) {
1506   if (pImpl)
1507     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
1508 }
1509 
1510 void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
1511                                  const TargetInstrInfo &TII,
1512                                  const TargetRegisterInfo &TRI,
1513                                  SpillOffsetMap &SpillOffsets) {
1514   // Build a set of new locations with new numbers so we can coalesce our
1515   // IntervalMap if two vreg intervals collapse to the same physical location.
1516   // Use MapVector instead of SetVector because MapVector::insert returns the
1517   // position of the previously or newly inserted element. The boolean value
1518   // tracks if the location was produced by a spill.
1519   // FIXME: This will be problematic if we ever support direct and indirect
1520   // frame index locations, i.e. expressing both variables in memory and
1521   // 'int x, *px = &x'. The "spilled" bit must become part of the location.
1522   MapVector<MachineOperand, std::pair<bool, unsigned>> NewLocations;
1523   SmallVector<unsigned, 4> LocNoMap(locations.size());
1524   for (unsigned I = 0, E = locations.size(); I != E; ++I) {
1525     bool Spilled = false;
1526     unsigned SpillOffset = 0;
1527     MachineOperand Loc = locations[I];
1528     // Only virtual registers are rewritten.
1529     if (Loc.isReg() && Loc.getReg() && Loc.getReg().isVirtual()) {
1530       Register VirtReg = Loc.getReg();
1531       if (VRM.isAssignedReg(VirtReg) &&
1532           Register::isPhysicalRegister(VRM.getPhys(VirtReg))) {
1533         // This can create a %noreg operand in rare cases when the sub-register
1534         // index is no longer available. That means the user value is in a
1535         // non-existent sub-register, and %noreg is exactly what we want.
1536         Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
1537       } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
1538         // Retrieve the stack slot offset.
1539         unsigned SpillSize;
1540         const MachineRegisterInfo &MRI = MF.getRegInfo();
1541         const TargetRegisterClass *TRC = MRI.getRegClass(VirtReg);
1542         bool Success = TII.getStackSlotRange(TRC, Loc.getSubReg(), SpillSize,
1543                                              SpillOffset, MF);
1544 
1545         // FIXME: Invalidate the location if the offset couldn't be calculated.
1546         (void)Success;
1547 
1548         Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
1549         Spilled = true;
1550       } else {
1551         Loc.setReg(0);
1552         Loc.setSubReg(0);
1553       }
1554     }
1555 
1556     // Insert this location if it doesn't already exist and record a mapping
1557     // from the old number to the new number.
1558     auto InsertResult = NewLocations.insert({Loc, {Spilled, SpillOffset}});
1559     unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first);
1560     LocNoMap[I] = NewLocNo;
1561   }
1562 
1563   // Rewrite the locations and record the stack slot offsets for spills.
1564   locations.clear();
1565   SpillOffsets.clear();
1566   for (auto &Pair : NewLocations) {
1567     bool Spilled;
1568     unsigned SpillOffset;
1569     std::tie(Spilled, SpillOffset) = Pair.second;
1570     locations.push_back(Pair.first);
1571     if (Spilled) {
1572       unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair);
1573       SpillOffsets[NewLocNo] = SpillOffset;
1574     }
1575   }
1576 
1577   // Update the interval map, but only coalesce left, since intervals to the
1578   // right use the old location numbers. This should merge two contiguous
1579   // DBG_VALUE intervals with different vregs that were allocated to the same
1580   // physical register.
1581   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
1582     I.setValueUnchecked(I.value().remapLocNos(LocNoMap));
1583     I.setStart(I.start());
1584   }
1585 }
1586 
1587 /// Find an iterator for inserting a DBG_VALUE instruction.
1588 static MachineBasicBlock::iterator
1589 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, LiveIntervals &LIS,
1590                    BlockSkipInstsMap &BBSkipInstsMap) {
1591   SlotIndex Start = LIS.getMBBStartIdx(MBB);
1592   Idx = Idx.getBaseIndex();
1593 
1594   // Try to find an insert location by going backwards from Idx.
1595   MachineInstr *MI;
1596   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
1597     // We've reached the beginning of MBB.
1598     if (Idx == Start) {
1599       // Retrieve the last PHI/Label/Debug location found when calling
1600       // SkipPHIsLabelsAndDebug last time. Start searching from there.
1601       //
1602       // Note the iterator kept in BBSkipInstsMap is one step back based
1603       // on the iterator returned by SkipPHIsLabelsAndDebug last time.
1604       // One exception is when SkipPHIsLabelsAndDebug returns MBB->begin(),
1605       // BBSkipInstsMap won't save it. This is to consider the case that
1606       // new instructions may be inserted at the beginning of MBB after
1607       // last call of SkipPHIsLabelsAndDebug. If we save MBB->begin() in
1608       // BBSkipInstsMap, after new non-phi/non-label/non-debug instructions
1609       // are inserted at the beginning of the MBB, the iterator in
1610       // BBSkipInstsMap won't point to the beginning of the MBB anymore.
1611       // Therefore The next search in SkipPHIsLabelsAndDebug will skip those
1612       // newly added instructions and that is unwanted.
1613       MachineBasicBlock::iterator BeginIt;
1614       auto MapIt = BBSkipInstsMap.find(MBB);
1615       if (MapIt == BBSkipInstsMap.end())
1616         BeginIt = MBB->begin();
1617       else
1618         BeginIt = std::next(MapIt->second);
1619       auto I = MBB->SkipPHIsLabelsAndDebug(BeginIt);
1620       if (I != BeginIt)
1621         BBSkipInstsMap[MBB] = std::prev(I);
1622       return I;
1623     }
1624     Idx = Idx.getPrevIndex();
1625   }
1626 
1627   // Don't insert anything after the first terminator, though.
1628   return MI->isTerminator() ? MBB->getFirstTerminator() :
1629                               std::next(MachineBasicBlock::iterator(MI));
1630 }
1631 
1632 /// Find an iterator for inserting the next DBG_VALUE instruction
1633 /// (or end if no more insert locations found).
1634 static MachineBasicBlock::iterator
1635 findNextInsertLocation(MachineBasicBlock *MBB, MachineBasicBlock::iterator I,
1636                        SlotIndex StopIdx, ArrayRef<MachineOperand> LocMOs,
1637                        LiveIntervals &LIS, const TargetRegisterInfo &TRI) {
1638   SmallVector<Register, 4> Regs;
1639   for (const MachineOperand &LocMO : LocMOs)
1640     if (LocMO.isReg())
1641       Regs.push_back(LocMO.getReg());
1642   if (Regs.empty())
1643     return MBB->instr_end();
1644 
1645   // Find the next instruction in the MBB that define the register Reg.
1646   while (I != MBB->end() && !I->isTerminator()) {
1647     if (!LIS.isNotInMIMap(*I) &&
1648         SlotIndex::isEarlierEqualInstr(StopIdx, LIS.getInstructionIndex(*I)))
1649       break;
1650     if (any_of(Regs, [&I, &TRI](Register &Reg) {
1651           return I->definesRegister(Reg, &TRI);
1652         }))
1653       // The insert location is directly after the instruction/bundle.
1654       return std::next(I);
1655     ++I;
1656   }
1657   return MBB->end();
1658 }
1659 
1660 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
1661                                  SlotIndex StopIdx, DbgVariableValue DbgValue,
1662                                  ArrayRef<bool> LocSpills,
1663                                  ArrayRef<unsigned> SpillOffsets,
1664                                  LiveIntervals &LIS, const TargetInstrInfo &TII,
1665                                  const TargetRegisterInfo &TRI,
1666                                  BlockSkipInstsMap &BBSkipInstsMap) {
1667   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
1668   // Only search within the current MBB.
1669   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
1670   MachineBasicBlock::iterator I =
1671       findInsertLocation(MBB, StartIdx, LIS, BBSkipInstsMap);
1672   // Undef values don't exist in locations so create new "noreg" register MOs
1673   // for them. See getLocationNo().
1674   SmallVector<MachineOperand, 8> MOs;
1675   if (DbgValue.isUndef()) {
1676     MOs.assign(DbgValue.loc_nos().size(),
1677                MachineOperand::CreateReg(
1678                    /* Reg */ 0, /* isDef */ false, /* isImp */ false,
1679                    /* isKill */ false, /* isDead */ false,
1680                    /* isUndef */ false, /* isEarlyClobber */ false,
1681                    /* SubReg */ 0, /* isDebug */ true));
1682   } else {
1683     for (unsigned LocNo : DbgValue.loc_nos())
1684       MOs.push_back(locations[LocNo]);
1685   }
1686 
1687   ++NumInsertedDebugValues;
1688 
1689   assert(cast<DILocalVariable>(Variable)
1690              ->isValidLocationForIntrinsic(getDebugLoc()) &&
1691          "Expected inlined-at fields to agree");
1692 
1693   // If the location was spilled, the new DBG_VALUE will be indirect. If the
1694   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
1695   // that the original virtual register was a pointer. Also, add the stack slot
1696   // offset for the spilled register to the expression.
1697   const DIExpression *Expr = DbgValue.getExpression();
1698   bool IsIndirect = DbgValue.getWasIndirect();
1699   bool IsList = DbgValue.getWasList();
1700   for (unsigned I = 0, E = LocSpills.size(); I != E; ++I) {
1701     if (LocSpills[I]) {
1702       if (!IsList) {
1703         uint8_t DIExprFlags = DIExpression::ApplyOffset;
1704         if (IsIndirect)
1705           DIExprFlags |= DIExpression::DerefAfter;
1706         Expr = DIExpression::prepend(Expr, DIExprFlags, SpillOffsets[I]);
1707         IsIndirect = true;
1708       } else {
1709         SmallVector<uint64_t, 4> Ops;
1710         DIExpression::appendOffset(Ops, SpillOffsets[I]);
1711         Ops.push_back(dwarf::DW_OP_deref);
1712         Expr = DIExpression::appendOpsToArg(Expr, Ops, I);
1713       }
1714     }
1715 
1716     assert((!LocSpills[I] || MOs[I].isFI()) &&
1717            "a spilled location must be a frame index");
1718   }
1719 
1720   unsigned DbgValueOpcode =
1721       IsList ? TargetOpcode::DBG_VALUE_LIST : TargetOpcode::DBG_VALUE;
1722   do {
1723     BuildMI(*MBB, I, getDebugLoc(), TII.get(DbgValueOpcode), IsIndirect, MOs,
1724             Variable, Expr);
1725 
1726     // Continue and insert DBG_VALUES after every redefinition of a register
1727     // associated with the debug value within the range
1728     I = findNextInsertLocation(MBB, I, StopIdx, MOs, LIS, TRI);
1729   } while (I != MBB->end());
1730 }
1731 
1732 void UserLabel::insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx,
1733                                  LiveIntervals &LIS, const TargetInstrInfo &TII,
1734                                  BlockSkipInstsMap &BBSkipInstsMap) {
1735   MachineBasicBlock::iterator I =
1736       findInsertLocation(MBB, Idx, LIS, BBSkipInstsMap);
1737   ++NumInsertedDebugLabels;
1738   BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_LABEL))
1739       .addMetadata(Label);
1740 }
1741 
1742 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
1743                                 const TargetInstrInfo &TII,
1744                                 const TargetRegisterInfo &TRI,
1745                                 const SpillOffsetMap &SpillOffsets,
1746                                 BlockSkipInstsMap &BBSkipInstsMap) {
1747   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
1748 
1749   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
1750     SlotIndex Start = I.start();
1751     SlotIndex Stop = I.stop();
1752     DbgVariableValue DbgValue = I.value();
1753 
1754     SmallVector<bool> SpilledLocs;
1755     SmallVector<unsigned> LocSpillOffsets;
1756     for (unsigned LocNo : DbgValue.loc_nos()) {
1757       auto SpillIt =
1758           !DbgValue.isUndef() ? SpillOffsets.find(LocNo) : SpillOffsets.end();
1759       bool Spilled = SpillIt != SpillOffsets.end();
1760       SpilledLocs.push_back(Spilled);
1761       LocSpillOffsets.push_back(Spilled ? SpillIt->second : 0);
1762     }
1763 
1764     // If the interval start was trimmed to the lexical scope insert the
1765     // DBG_VALUE at the previous index (otherwise it appears after the
1766     // first instruction in the range).
1767     if (trimmedDefs.count(Start))
1768       Start = Start.getPrevIndex();
1769 
1770     LLVM_DEBUG(auto &dbg = dbgs(); dbg << "\t[" << Start << ';' << Stop << "):";
1771                DbgValue.printLocNos(dbg));
1772     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1773     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
1774 
1775     LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1776     insertDebugValue(&*MBB, Start, Stop, DbgValue, SpilledLocs, LocSpillOffsets,
1777                      LIS, TII, TRI, BBSkipInstsMap);
1778     // This interval may span multiple basic blocks.
1779     // Insert a DBG_VALUE into each one.
1780     while (Stop > MBBEnd) {
1781       // Move to the next block.
1782       Start = MBBEnd;
1783       if (++MBB == MFEnd)
1784         break;
1785       MBBEnd = LIS.getMBBEndIdx(&*MBB);
1786       LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1787       insertDebugValue(&*MBB, Start, Stop, DbgValue, SpilledLocs,
1788                        LocSpillOffsets, LIS, TII, TRI, BBSkipInstsMap);
1789     }
1790     LLVM_DEBUG(dbgs() << '\n');
1791     if (MBB == MFEnd)
1792       break;
1793 
1794     ++I;
1795   }
1796 }
1797 
1798 void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII,
1799                                BlockSkipInstsMap &BBSkipInstsMap) {
1800   LLVM_DEBUG(dbgs() << "\t" << loc);
1801   MachineFunction::iterator MBB = LIS.getMBBFromIndex(loc)->getIterator();
1802 
1803   LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB));
1804   insertDebugLabel(&*MBB, loc, LIS, TII, BBSkipInstsMap);
1805 
1806   LLVM_DEBUG(dbgs() << '\n');
1807 }
1808 
1809 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1810   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1811   if (!MF)
1812     return;
1813 
1814   BlockSkipInstsMap BBSkipInstsMap;
1815   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1816   SpillOffsetMap SpillOffsets;
1817   for (auto &userValue : userValues) {
1818     LLVM_DEBUG(userValue->print(dbgs(), TRI));
1819     userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
1820     userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets,
1821                                BBSkipInstsMap);
1822   }
1823   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n");
1824   for (auto &userLabel : userLabels) {
1825     LLVM_DEBUG(userLabel->print(dbgs(), TRI));
1826     userLabel->emitDebugLabel(*LIS, *TII, BBSkipInstsMap);
1827   }
1828 
1829   LLVM_DEBUG(dbgs() << "********** EMITTING DEBUG PHIS **********\n");
1830 
1831   auto Slots = LIS->getSlotIndexes();
1832   for (auto &It : PHIValToPos) {
1833     // For each ex-PHI, identify its physreg location or stack slot, and emit
1834     // a DBG_PHI for it.
1835     unsigned InstNum = It.first;
1836     auto Slot = It.second.SI;
1837     Register Reg = It.second.Reg;
1838     unsigned SubReg = It.second.SubReg;
1839 
1840     MachineBasicBlock *OrigMBB = Slots->getMBBFromIndex(Slot);
1841     if (VRM->isAssignedReg(Reg) &&
1842         Register::isPhysicalRegister(VRM->getPhys(Reg))) {
1843       unsigned PhysReg = VRM->getPhys(Reg);
1844       if (SubReg != 0)
1845         PhysReg = TRI->getSubReg(PhysReg, SubReg);
1846 
1847       auto Builder = BuildMI(*OrigMBB, OrigMBB->begin(), DebugLoc(),
1848                              TII->get(TargetOpcode::DBG_PHI));
1849       Builder.addReg(PhysReg);
1850       Builder.addImm(InstNum);
1851     } else if (VRM->getStackSlot(Reg) != VirtRegMap::NO_STACK_SLOT) {
1852       const MachineRegisterInfo &MRI = MF->getRegInfo();
1853       const TargetRegisterClass *TRC = MRI.getRegClass(Reg);
1854       unsigned SpillSize, SpillOffset;
1855 
1856       unsigned regSizeInBits = TRI->getRegSizeInBits(*TRC);
1857       if (SubReg)
1858         regSizeInBits = TRI->getSubRegIdxSize(SubReg);
1859 
1860       // Test whether this location is legal with the given subreg. If the
1861       // subregister has a nonzero offset, drop this location, it's too complex
1862       // to describe. (TODO: future work).
1863       bool Success =
1864           TII->getStackSlotRange(TRC, SubReg, SpillSize, SpillOffset, *MF);
1865 
1866       if (Success && SpillOffset == 0) {
1867         auto Builder = BuildMI(*OrigMBB, OrigMBB->begin(), DebugLoc(),
1868                                TII->get(TargetOpcode::DBG_PHI));
1869         Builder.addFrameIndex(VRM->getStackSlot(Reg));
1870         Builder.addImm(InstNum);
1871         // Record how large the original value is. The stack slot might be
1872         // merged and altered during optimisation, but we will want to know how
1873         // large the value is, at this DBG_PHI.
1874         Builder.addImm(regSizeInBits);
1875       }
1876 
1877       LLVM_DEBUG(
1878       if (SpillOffset != 0) {
1879         dbgs() << "DBG_PHI for Vreg " << Reg << " subreg " << SubReg <<
1880                   " has nonzero offset\n";
1881       }
1882       );
1883     }
1884     // If there was no mapping for a value ID, it's optimized out. Create no
1885     // DBG_PHI, and any variables using this value will become optimized out.
1886   }
1887   MF->DebugPHIPositions.clear();
1888 
1889   LLVM_DEBUG(dbgs() << "********** EMITTING INSTR REFERENCES **********\n");
1890 
1891   // Re-insert any debug instrs back in the position they were. We must
1892   // re-insert in the same order to ensure that debug instructions don't swap,
1893   // which could re-order assignments. Do so in a batch -- once we find the
1894   // insert position, insert all instructions at the same SlotIdx. They are
1895   // guaranteed to appear in-sequence in StashedDebugInstrs because we insert
1896   // them in order.
1897   for (auto *StashIt = StashedDebugInstrs.begin();
1898        StashIt != StashedDebugInstrs.end(); ++StashIt) {
1899     SlotIndex Idx = StashIt->Idx;
1900     MachineBasicBlock *MBB = StashIt->MBB;
1901     MachineInstr *MI = StashIt->MI;
1902 
1903     auto EmitInstsHere = [this, &StashIt, MBB, Idx,
1904                           MI](MachineBasicBlock::iterator InsertPos) {
1905       // Insert this debug instruction.
1906       MBB->insert(InsertPos, MI);
1907 
1908       // Look at subsequent stashed debug instructions: if they're at the same
1909       // index, insert those too.
1910       auto NextItem = std::next(StashIt);
1911       while (NextItem != StashedDebugInstrs.end() && NextItem->Idx == Idx) {
1912         assert(NextItem->MBB == MBB && "Instrs with same slot index should be"
1913                "in the same block");
1914         MBB->insert(InsertPos, NextItem->MI);
1915         StashIt = NextItem;
1916         NextItem = std::next(StashIt);
1917       };
1918     };
1919 
1920     // Start block index: find the first non-debug instr in the block, and
1921     // insert before it.
1922     if (Idx == Slots->getMBBStartIdx(MBB)) {
1923       MachineBasicBlock::iterator InsertPos =
1924           findInsertLocation(MBB, Idx, *LIS, BBSkipInstsMap);
1925       EmitInstsHere(InsertPos);
1926       continue;
1927     }
1928 
1929     if (MachineInstr *Pos = Slots->getInstructionFromIndex(Idx)) {
1930       // Insert at the end of any debug instructions.
1931       auto PostDebug = std::next(Pos->getIterator());
1932       PostDebug = skipDebugInstructionsForward(PostDebug, MBB->instr_end());
1933       EmitInstsHere(PostDebug);
1934     } else {
1935       // Insert position disappeared; walk forwards through slots until we
1936       // find a new one.
1937       SlotIndex End = Slots->getMBBEndIdx(MBB);
1938       for (; Idx < End; Idx = Slots->getNextNonNullIndex(Idx)) {
1939         Pos = Slots->getInstructionFromIndex(Idx);
1940         if (Pos) {
1941           EmitInstsHere(Pos->getIterator());
1942           break;
1943         }
1944       }
1945 
1946       // We have reached the end of the block and didn't find anywhere to
1947       // insert! It's not safe to discard any debug instructions; place them
1948       // in front of the first terminator, or in front of end().
1949       if (Idx >= End) {
1950         auto TermIt = MBB->getFirstTerminator();
1951         EmitInstsHere(TermIt);
1952       }
1953     }
1954   }
1955 
1956   EmitDone = true;
1957   BBSkipInstsMap.clear();
1958 }
1959 
1960 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
1961   if (pImpl)
1962     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1963 }
1964 
1965 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1966 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
1967   if (pImpl)
1968     static_cast<LDVImpl*>(pImpl)->print(dbgs());
1969 }
1970 #endif
1971