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