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