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