LLVM  8.0.0svn
LiveDebugVariables.cpp
Go to the documentation of this file.
1 //===- LiveDebugVariables.cpp - Tracking debug info variables -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LiveDebugVariables analysis.
11 //
12 // Remove all DBG_VALUE instructions referencing virtual registers and replace
13 // them with a data structure tracking where live user variables are kept - in a
14 // virtual register or in a stack slot.
15 //
16 // Allow the data structure to be updated during register allocation when values
17 // are moved between registers and stack slots. Finally emit new DBG_VALUE
18 // instructions after register allocation is complete.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #include "LiveDebugVariables.h"
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/IntervalMap.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"
47 #include "llvm/Config/llvm-config.h"
49 #include "llvm/IR/DebugLoc.h"
50 #include "llvm/IR/Function.h"
51 #include "llvm/IR/Metadata.h"
52 #include "llvm/MC/MCRegisterInfo.h"
53 #include "llvm/Pass.h"
54 #include "llvm/Support/Casting.h"
56 #include "llvm/Support/Compiler.h"
57 #include "llvm/Support/Debug.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 
75 char LiveDebugVariables::ID = 0;
76 
78  "Debug Variable Analysis", false, false)
82  "Debug Variable Analysis", false, false)
83 
84 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
85  AU.addRequired<MachineDominatorTree>();
86  AU.addRequiredTransitive<LiveIntervals>();
87  AU.setPreservesAll();
89 }
90 
93 }
94 
95 enum : unsigned { UndefLocNo = ~0U };
96 
97 /// Describes a location by number along with some flags about the original
98 /// usage of the location.
100 public:
101  DbgValueLocation(unsigned LocNo, bool WasIndirect)
102  : LocNo(LocNo), WasIndirect(WasIndirect) {
103  static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
104  assert(locNo() == LocNo && "location truncation");
105  }
106 
107  DbgValueLocation() : LocNo(0), WasIndirect(0) {}
108 
109  unsigned locNo() const {
110  // Fix up the undef location number, which gets truncated.
111  return LocNo == INT_MAX ? UndefLocNo : LocNo;
112  }
113  bool wasIndirect() const { return WasIndirect; }
114  bool isUndef() const { return locNo() == UndefLocNo; }
115 
116  DbgValueLocation changeLocNo(unsigned NewLocNo) const {
117  return DbgValueLocation(NewLocNo, WasIndirect);
118  }
119 
120  friend inline bool operator==(const DbgValueLocation &LHS,
121  const DbgValueLocation &RHS) {
122  return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect;
123  }
124 
125  friend inline bool operator!=(const DbgValueLocation &LHS,
126  const DbgValueLocation &RHS) {
127  return !(LHS == RHS);
128  }
129 
130 private:
131  unsigned LocNo : 31;
132  unsigned WasIndirect : 1;
133 };
134 
135 /// LocMap - Map of where a user value is live, and its location.
137 
138 /// SpillOffsetMap - Map of stack slot offsets for spilled locations.
139 /// Non-spilled locations are not added to the map.
141 
142 namespace {
143 
144 class LDVImpl;
145 
146 /// UserValue - A user value is a part of a debug info user variable.
147 ///
148 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
149 /// holds part of a user variable. The part is identified by a byte offset.
150 ///
151 /// UserValues are grouped into equivalence classes for easier searching. Two
152 /// user values are related if they refer to the same variable, or if they are
153 /// held by the same virtual register. The equivalence class is the transitive
154 /// closure of that relation.
155 class UserValue {
156  const DILocalVariable *Variable; ///< The debug info variable we are part of.
157  const DIExpression *Expression; ///< Any complex address expression.
158  DebugLoc dl; ///< The debug location for the variable. This is
159  ///< used by dwarf writer to find lexical scope.
160  UserValue *leader; ///< Equivalence class leader.
161  UserValue *next = nullptr; ///< Next value in equivalence class, or null.
162 
163  /// Numbered locations referenced by locmap.
165 
166  /// Map of slot indices where this value is live.
167  LocMap locInts;
168 
169  /// Set of interval start indexes that have been trimmed to the
170  /// lexical scope.
171  SmallSet<SlotIndex, 2> trimmedDefs;
172 
173  /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
174  void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
175  SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled,
176  unsigned SpillOffset, LiveIntervals &LIS,
177  const TargetInstrInfo &TII,
178  const TargetRegisterInfo &TRI);
179 
180  /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
181  /// is live. Returns true if any changes were made.
182  bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
183  LiveIntervals &LIS);
184 
185 public:
186  /// UserValue - Create a new UserValue.
187  UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
188  LocMap::Allocator &alloc)
189  : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
190  locInts(alloc) {}
191 
192  /// getLeader - Get the leader of this value's equivalence class.
193  UserValue *getLeader() {
194  UserValue *l = leader;
195  while (l != l->leader)
196  l = l->leader;
197  return leader = l;
198  }
199 
200  /// getNext - Return the next UserValue in the equivalence class.
201  UserValue *getNext() const { return next; }
202 
203  /// match - Does this UserValue match the parameters?
204  bool match(const DILocalVariable *Var, const DIExpression *Expr,
205  const DILocation *IA) const {
206  // FIXME: The fragment should be part of the equivalence class, but not
207  // other things in the expression like stack values.
208  return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
209  }
210 
211  /// merge - Merge equivalence classes.
212  static UserValue *merge(UserValue *L1, UserValue *L2) {
213  L2 = L2->getLeader();
214  if (!L1)
215  return L2;
216  L1 = L1->getLeader();
217  if (L1 == L2)
218  return L1;
219  // Splice L2 before L1's members.
220  UserValue *End = L2;
221  while (End->next) {
222  End->leader = L1;
223  End = End->next;
224  }
225  End->leader = L1;
226  End->next = L1->next;
227  L1->next = L2;
228  return L1;
229  }
230 
231  /// Return the location number that matches Loc.
232  ///
233  /// For undef values we always return location number UndefLocNo without
234  /// inserting anything in locations. Since locations is a vector and the
235  /// location number is the position in the vector and UndefLocNo is ~0,
236  /// we would need a very big vector to put the value at the right position.
237  unsigned getLocationNo(const MachineOperand &LocMO) {
238  if (LocMO.isReg()) {
239  if (LocMO.getReg() == 0)
240  return UndefLocNo;
241  // For register locations we dont care about use/def and other flags.
242  for (unsigned i = 0, e = locations.size(); i != e; ++i)
243  if (locations[i].isReg() &&
244  locations[i].getReg() == LocMO.getReg() &&
245  locations[i].getSubReg() == LocMO.getSubReg())
246  return i;
247  } else
248  for (unsigned i = 0, e = locations.size(); i != e; ++i)
249  if (LocMO.isIdenticalTo(locations[i]))
250  return i;
251  locations.push_back(LocMO);
252  // We are storing a MachineOperand outside a MachineInstr.
253  locations.back().clearParent();
254  // Don't store def operands.
255  if (locations.back().isReg()) {
256  if (locations.back().isDef())
257  locations.back().setIsDead(false);
258  locations.back().setIsUse();
259  }
260  return locations.size() - 1;
261  }
262 
263  /// mapVirtRegs - Ensure that all virtual register locations are mapped.
264  void mapVirtRegs(LDVImpl *LDV);
265 
266  /// addDef - Add a definition point to this value.
267  void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect) {
268  DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect);
269  // Add a singular (Idx,Idx) -> Loc mapping.
270  LocMap::iterator I = locInts.find(Idx);
271  if (!I.valid() || I.start() != Idx)
272  I.insert(Idx, Idx.getNextSlot(), Loc);
273  else
274  // A later DBG_VALUE at the same SlotIndex overrides the old location.
275  I.setValue(Loc);
276  }
277 
278  /// extendDef - Extend the current definition as far as possible down.
279  /// Stop when meeting an existing def or when leaving the live
280  /// range of VNI.
281  /// End points where VNI is no longer live are added to Kills.
282  /// @param Idx Starting point for the definition.
283  /// @param Loc Location number to propagate.
284  /// @param LR Restrict liveness to where LR has the value VNI. May be null.
285  /// @param VNI When LR is not null, this is the value to restrict to.
286  /// @param Kills Append end points of VNI's live range to Kills.
287  /// @param LIS Live intervals analysis.
288  void extendDef(SlotIndex Idx, DbgValueLocation Loc,
289  LiveRange *LR, const VNInfo *VNI,
291  LiveIntervals &LIS);
292 
293  /// addDefsFromCopies - The value in LI/LocNo may be copies to other
294  /// registers. Determine if any of the copies are available at the kill
295  /// points, and add defs if possible.
296  /// @param LI Scan for copies of the value in LI->reg.
297  /// @param LocNo Location number of LI->reg.
298  /// @param WasIndirect Indicates if the original use of LI->reg was indirect
299  /// @param Kills Points where the range of LocNo could be extended.
300  /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
301  void addDefsFromCopies(
302  LiveInterval *LI, unsigned LocNo, bool WasIndirect,
303  const SmallVectorImpl<SlotIndex> &Kills,
304  SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
306 
307  /// computeIntervals - Compute the live intervals of all locations after
308  /// collecting all their def points.
309  void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
311 
312  /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
313  /// live. Returns true if any changes were made.
314  bool splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
315  LiveIntervals &LIS);
316 
317  /// rewriteLocations - Rewrite virtual register locations according to the
318  /// provided virtual register map. Record the stack slot offsets for the
319  /// locations that were spilled.
320  void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
321  const TargetInstrInfo &TII,
322  const TargetRegisterInfo &TRI,
323  SpillOffsetMap &SpillOffsets);
324 
325  /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
326  void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
327  const TargetInstrInfo &TII,
328  const TargetRegisterInfo &TRI,
329  const SpillOffsetMap &SpillOffsets);
330 
331  /// getDebugLoc - Return DebugLoc of this UserValue.
332  DebugLoc getDebugLoc() { return dl;}
333 
334  void print(raw_ostream &, const TargetRegisterInfo *);
335 };
336 
337 /// LDVImpl - Implementation of the LiveDebugVariables pass.
338 class LDVImpl {
340  LocMap::Allocator allocator;
341  MachineFunction *MF = nullptr;
342  LiveIntervals *LIS;
343  const TargetRegisterInfo *TRI;
344 
345  /// Whether emitDebugValues is called.
346  bool EmitDone = false;
347 
348  /// Whether the machine function is modified during the pass.
349  bool ModifiedMF = false;
350 
351  /// userValues - All allocated UserValue instances.
353 
354  /// Map virtual register to eq class leader.
355  using VRMap = DenseMap<unsigned, UserValue *>;
356  VRMap virtRegToEqClass;
357 
358  /// Map user variable to eq class leader.
360  UVMap userVarMap;
361 
362  /// getUserValue - Find or create a UserValue.
363  UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
364  const DebugLoc &DL);
365 
366  /// lookupVirtReg - Find the EC leader for VirtReg or null.
367  UserValue *lookupVirtReg(unsigned VirtReg);
368 
369  /// handleDebugValue - Add DBG_VALUE instruction to our maps.
370  /// @param MI DBG_VALUE instruction
371  /// @param Idx Last valid SLotIndex before instruction.
372  /// @return True if the DBG_VALUE instruction should be deleted.
373  bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
374 
375  /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
376  /// a UserValue def for each instruction.
377  /// @param mf MachineFunction to be scanned.
378  /// @return True if any debug values were found.
379  bool collectDebugValues(MachineFunction &mf);
380 
381  /// computeIntervals - Compute the live intervals of all user values after
382  /// collecting all their def points.
383  void computeIntervals();
384 
385 public:
386  LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
387 
388  bool runOnMachineFunction(MachineFunction &mf);
389 
390  /// clear - Release all memory.
391  void clear() {
392  MF = nullptr;
393  userValues.clear();
394  virtRegToEqClass.clear();
395  userVarMap.clear();
396  // Make sure we call emitDebugValues if the machine function was modified.
397  assert((!ModifiedMF || EmitDone) &&
398  "Dbg values are not emitted in LDV");
399  EmitDone = false;
400  ModifiedMF = false;
401  }
402 
403  /// mapVirtReg - Map virtual register to an equivalence class.
404  void mapVirtReg(unsigned VirtReg, UserValue *EC);
405 
406  /// splitRegister - Replace all references to OldReg with NewRegs.
407  void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
408 
409  /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
410  void emitDebugValues(VirtRegMap *VRM);
411 
412  void print(raw_ostream&);
413 };
414 
415 } // end anonymous namespace
416 
417 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
418 static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS,
419  const LLVMContext &Ctx) {
420  if (!DL)
421  return;
422 
423  auto *Scope = cast<DIScope>(DL.getScope());
424  // Omit the directory, because it's likely to be long and uninteresting.
425  CommentOS << Scope->getFilename();
426  CommentOS << ':' << DL.getLine();
427  if (DL.getCol() != 0)
428  CommentOS << ':' << DL.getCol();
429 
430  DebugLoc InlinedAtDL = DL.getInlinedAt();
431  if (!InlinedAtDL)
432  return;
433 
434  CommentOS << " @[ ";
435  printDebugLoc(InlinedAtDL, CommentOS, Ctx);
436  CommentOS << " ]";
437 }
438 
440  const DILocation *DL) {
441  const LLVMContext &Ctx = V->getContext();
442  StringRef Res = V->getName();
443  if (!Res.empty())
444  OS << Res << "," << V->getLine();
445  if (auto *InlinedAt = DL->getInlinedAt()) {
446  if (DebugLoc InlinedAtDL = InlinedAt) {
447  OS << " @[";
448  printDebugLoc(InlinedAtDL, OS, Ctx);
449  OS << "]";
450  }
451  }
452 }
453 
455  auto *DV = cast<DILocalVariable>(Variable);
456  OS << "!\"";
457  printExtendedName(OS, DV, dl);
458 
459  OS << "\"\t";
460  for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
461  OS << " [" << I.start() << ';' << I.stop() << "):";
462  if (I.value().isUndef())
463  OS << "undef";
464  else {
465  OS << I.value().locNo();
466  if (I.value().wasIndirect())
467  OS << " ind";
468  }
469  }
470  for (unsigned i = 0, e = locations.size(); i != e; ++i) {
471  OS << " Loc" << i << '=';
472  locations[i].print(OS, TRI);
473  }
474  OS << '\n';
475 }
476 
477 void LDVImpl::print(raw_ostream &OS) {
478  OS << "********** DEBUG VARIABLES **********\n";
479  for (unsigned i = 0, e = userValues.size(); i != e; ++i)
480  userValues[i]->print(OS, TRI);
481 }
482 #endif
483 
484 void UserValue::mapVirtRegs(LDVImpl *LDV) {
485  for (unsigned i = 0, e = locations.size(); i != e; ++i)
486  if (locations[i].isReg() &&
488  LDV->mapVirtReg(locations[i].getReg(), this);
489 }
490 
491 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
492  const DIExpression *Expr, const DebugLoc &DL) {
493  UserValue *&Leader = userVarMap[Var];
494  if (Leader) {
495  UserValue *UV = Leader->getLeader();
496  Leader = UV;
497  for (; UV; UV = UV->getNext())
498  if (UV->match(Var, Expr, DL->getInlinedAt()))
499  return UV;
500  }
501 
502  userValues.push_back(
503  llvm::make_unique<UserValue>(Var, Expr, DL, allocator));
504  UserValue *UV = userValues.back().get();
505  Leader = UserValue::merge(Leader, UV);
506  return UV;
507 }
508 
509 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
510  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
511  UserValue *&Leader = virtRegToEqClass[VirtReg];
512  Leader = UserValue::merge(Leader, EC);
513 }
514 
515 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
516  if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
517  return UV->getLeader();
518  return nullptr;
519 }
520 
521 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
522  // DBG_VALUE loc, offset, variable
523  if (MI.getNumOperands() != 4 ||
524  !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
525  !MI.getOperand(2).isMetadata()) {
526  LLVM_DEBUG(dbgs() << "Can't handle " << MI);
527  return false;
528  }
529 
530  // Detect invalid DBG_VALUE instructions, with a debug-use of a virtual
531  // register that hasn't been defined yet. If we do not remove those here, then
532  // the re-insertion of the DBG_VALUE instruction after register allocation
533  // will be incorrect.
534  // TODO: If earlier passes are corrected to generate sane debug information
535  // (and if the machine verifier is improved to catch this), then these checks
536  // could be removed or replaced by asserts.
537  bool Discard = false;
538  if (MI.getOperand(0).isReg() &&
540  const unsigned Reg = MI.getOperand(0).getReg();
541  if (!LIS->hasInterval(Reg)) {
542  // The DBG_VALUE is described by a virtual register that does not have a
543  // live interval. Discard the DBG_VALUE.
544  Discard = true;
545  LLVM_DEBUG(dbgs() << "Discarding debug info (no LIS interval): " << Idx
546  << " " << MI);
547  } else {
548  // The DBG_VALUE is only valid if either Reg is live out from Idx, or Reg
549  // is defined dead at Idx (where Idx is the slot index for the instruction
550  // preceeding the DBG_VALUE).
551  const LiveInterval &LI = LIS->getInterval(Reg);
552  LiveQueryResult LRQ = LI.Query(Idx);
553  if (!LRQ.valueOutOrDead()) {
554  // We have found a DBG_VALUE with the value in a virtual register that
555  // is not live. Discard the DBG_VALUE.
556  Discard = true;
557  LLVM_DEBUG(dbgs() << "Discarding debug info (reg not live): " << Idx
558  << " " << MI);
559  }
560  }
561  }
562 
563  // Get or create the UserValue for (variable,offset) here.
564  bool IsIndirect = MI.getOperand(1).isImm();
565  if (IsIndirect)
566  assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
567  const DILocalVariable *Var = MI.getDebugVariable();
568  const DIExpression *Expr = MI.getDebugExpression();
569  UserValue *UV =
570  getUserValue(Var, Expr, MI.getDebugLoc());
571  if (!Discard)
572  UV->addDef(Idx, MI.getOperand(0), IsIndirect);
573  else {
575  MO.setIsDebug();
576  UV->addDef(Idx, MO, false);
577  }
578  return true;
579 }
580 
581 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
582  bool Changed = false;
583  for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
584  ++MFI) {
585  MachineBasicBlock *MBB = &*MFI;
586  for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
587  MBBI != MBBE;) {
588  // Use the first debug instruction in the sequence to get a SlotIndex
589  // for following consecutive debug instructions.
590  if (!MBBI->isDebugInstr()) {
591  ++MBBI;
592  continue;
593  }
594  // Debug instructions has no slot index. Use the previous
595  // non-debug instruction's SlotIndex as its SlotIndex.
596  SlotIndex Idx =
597  MBBI == MBB->begin()
598  ? LIS->getMBBStartIdx(MBB)
599  : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
600  // Handle consecutive debug instructions with the same slot index.
601  do {
602  // Only handle DBG_VALUE in handleDebugValue(). Skip all other
603  // kinds of debug instructions.
604  if (MBBI->isDebugValue() && handleDebugValue(*MBBI, Idx)) {
605  MBBI = MBB->erase(MBBI);
606  Changed = true;
607  } else
608  ++MBBI;
609  } while (MBBI != MBBE && MBBI->isDebugInstr());
610  }
611  }
612  return Changed;
613 }
614 
615 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
616 /// data-flow analysis to propagate them beyond basic block boundaries.
617 void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
618  const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
619  LiveIntervals &LIS) {
620  SlotIndex Start = Idx;
621  MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
622  SlotIndex Stop = LIS.getMBBEndIdx(MBB);
623  LocMap::iterator I = locInts.find(Start);
624 
625  // Limit to VNI's live range.
626  bool ToEnd = true;
627  if (LR && VNI) {
628  LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
629  if (!Segment || Segment->valno != VNI) {
630  if (Kills)
631  Kills->push_back(Start);
632  return;
633  }
634  if (Segment->end < Stop) {
635  Stop = Segment->end;
636  ToEnd = false;
637  }
638  }
639 
640  // There could already be a short def at Start.
641  if (I.valid() && I.start() <= Start) {
642  // Stop when meeting a different location or an already extended interval.
643  Start = Start.getNextSlot();
644  if (I.value() != Loc || I.stop() != Start)
645  return;
646  // This is a one-slot placeholder. Just skip it.
647  ++I;
648  }
649 
650  // Limited by the next def.
651  if (I.valid() && I.start() < Stop) {
652  Stop = I.start();
653  ToEnd = false;
654  }
655  // Limited by VNI's live range.
656  else if (!ToEnd && Kills)
657  Kills->push_back(Stop);
658 
659  if (Start < Stop)
660  I.insert(Start, Stop, Loc);
661 }
662 
663 void UserValue::addDefsFromCopies(
664  LiveInterval *LI, unsigned LocNo, bool WasIndirect,
665  const SmallVectorImpl<SlotIndex> &Kills,
666  SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
668  if (Kills.empty())
669  return;
670  // Don't track copies from physregs, there are too many uses.
672  return;
673 
674  // Collect all the (vreg, valno) pairs that are copies of LI.
676  for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
677  MachineInstr *MI = MO.getParent();
678  // Copies of the full value.
679  if (MO.getSubReg() || !MI->isCopy())
680  continue;
681  unsigned DstReg = MI->getOperand(0).getReg();
682 
683  // Don't follow copies to physregs. These are usually setting up call
684  // arguments, and the argument registers are always call clobbered. We are
685  // better off in the source register which could be a callee-saved register,
686  // or it could be spilled.
688  continue;
689 
690  // Is LocNo extended to reach this copy? If not, another def may be blocking
691  // it, or we are looking at a wrong value of LI.
692  SlotIndex Idx = LIS.getInstructionIndex(*MI);
693  LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
694  if (!I.valid() || I.value().locNo() != LocNo)
695  continue;
696 
697  if (!LIS.hasInterval(DstReg))
698  continue;
699  LiveInterval *DstLI = &LIS.getInterval(DstReg);
700  const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
701  assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
702  CopyValues.push_back(std::make_pair(DstLI, DstVNI));
703  }
704 
705  if (CopyValues.empty())
706  return;
707 
708  LLVM_DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI
709  << '\n');
710 
711  // Try to add defs of the copied values for each kill point.
712  for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
713  SlotIndex Idx = Kills[i];
714  for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
715  LiveInterval *DstLI = CopyValues[j].first;
716  const VNInfo *DstVNI = CopyValues[j].second;
717  if (DstLI->getVNInfoAt(Idx) != DstVNI)
718  continue;
719  // Check that there isn't already a def at Idx
720  LocMap::iterator I = locInts.find(Idx);
721  if (I.valid() && I.start() <= Idx)
722  continue;
723  LLVM_DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
724  << DstVNI->id << " in " << *DstLI << '\n');
725  MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
726  assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
727  unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
728  DbgValueLocation NewLoc(LocNo, WasIndirect);
729  I.insert(Idx, Idx.getNextSlot(), NewLoc);
730  NewDefs.push_back(std::make_pair(Idx, NewLoc));
731  break;
732  }
733  }
734 }
735 
736 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
737  const TargetRegisterInfo &TRI,
738  LiveIntervals &LIS, LexicalScopes &LS) {
740 
741  // Collect all defs to be extended (Skipping undefs).
742  for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
743  if (!I.value().isUndef())
744  Defs.push_back(std::make_pair(I.start(), I.value()));
745 
746  // Extend all defs, and possibly add new ones along the way.
747  for (unsigned i = 0; i != Defs.size(); ++i) {
748  SlotIndex Idx = Defs[i].first;
749  DbgValueLocation Loc = Defs[i].second;
750  const MachineOperand &LocMO = locations[Loc.locNo()];
751 
752  if (!LocMO.isReg()) {
753  extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
754  continue;
755  }
756 
757  // Register locations are constrained to where the register value is live.
759  LiveInterval *LI = nullptr;
760  const VNInfo *VNI = nullptr;
761  if (LIS.hasInterval(LocMO.getReg())) {
762  LI = &LIS.getInterval(LocMO.getReg());
763  VNI = LI->getVNInfoAt(Idx);
764  }
766  extendDef(Idx, Loc, LI, VNI, &Kills, LIS);
767  // FIXME: Handle sub-registers in addDefsFromCopies. The problem is that
768  // if the original location for example is %vreg0:sub_hi, and we find a
769  // full register copy in addDefsFromCopies (at the moment it only handles
770  // full register copies), then we must add the sub1 sub-register index to
771  // the new location. However, that is only possible if the new virtual
772  // register is of the same regclass (or if there is an equivalent
773  // sub-register in that regclass). For now, simply skip handling copies if
774  // a sub-register is involved.
775  if (LI && !LocMO.getSubReg())
776  addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
777  LIS);
778  continue;
779  }
780 
781  // For physregs, we only mark the start slot idx. DwarfDebug will see it
782  // as if the DBG_VALUE is valid up until the end of the basic block, or
783  // the next def of the physical register. So we do not need to extend the
784  // range. It might actually happen that the DBG_VALUE is the last use of
785  // the physical register (e.g. if this is an unused input argument to a
786  // function).
787  }
788 
789  // The computed intervals may extend beyond the range of the debug
790  // location's lexical scope. In this case, splitting of an interval
791  // can result in an interval outside of the scope being created,
792  // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
793  // this, trim the intervals to the lexical scope.
794 
795  LexicalScope *Scope = LS.findLexicalScope(dl);
796  if (!Scope)
797  return;
798 
799  SlotIndex PrevEnd;
800  LocMap::iterator I = locInts.begin();
801 
802  // Iterate over the lexical scope ranges. Each time round the loop
803  // we check the intervals for overlap with the end of the previous
804  // range and the start of the next. The first range is handled as
805  // a special case where there is no PrevEnd.
806  for (const InsnRange &Range : Scope->getRanges()) {
807  SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
808  SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
809 
810  // At the start of each iteration I has been advanced so that
811  // I.stop() >= PrevEnd. Check for overlap.
812  if (PrevEnd && I.start() < PrevEnd) {
813  SlotIndex IStop = I.stop();
814  DbgValueLocation Loc = I.value();
815 
816  // Stop overlaps previous end - trim the end of the interval to
817  // the scope range.
818  I.setStopUnchecked(PrevEnd);
819  ++I;
820 
821  // If the interval also overlaps the start of the "next" (i.e.
822  // current) range create a new interval for the remainder (which
823  // may be further trimmed).
824  if (RStart < IStop)
825  I.insert(RStart, IStop, Loc);
826  }
827 
828  // Advance I so that I.stop() >= RStart, and check for overlap.
829  I.advanceTo(RStart);
830  if (!I.valid())
831  return;
832 
833  if (I.start() < RStart) {
834  // Interval start overlaps range - trim to the scope range.
835  I.setStartUnchecked(RStart);
836  // Remember that this interval was trimmed.
837  trimmedDefs.insert(RStart);
838  }
839 
840  // The end of a lexical scope range is the last instruction in the
841  // range. To convert to an interval we need the index of the
842  // instruction after it.
843  REnd = REnd.getNextIndex();
844 
845  // Advance I to first interval outside current range.
846  I.advanceTo(REnd);
847  if (!I.valid())
848  return;
849 
850  PrevEnd = REnd;
851  }
852 
853  // Check for overlap with end of final range.
854  if (PrevEnd && I.start() < PrevEnd)
855  I.setStopUnchecked(PrevEnd);
856 }
857 
858 void LDVImpl::computeIntervals() {
860  LS.initialize(*MF);
861 
862  for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
863  userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
864  userValues[i]->mapVirtRegs(this);
865  }
866 }
867 
868 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
869  clear();
870  MF = &mf;
871  LIS = &pass.getAnalysis<LiveIntervals>();
872  TRI = mf.getSubtarget().getRegisterInfo();
873  LLVM_DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
874  << mf.getName() << " **********\n");
875 
876  bool Changed = collectDebugValues(mf);
877  computeIntervals();
878  LLVM_DEBUG(print(dbgs()));
879  ModifiedMF = Changed;
880  return Changed;
881 }
882 
884  for (MachineBasicBlock &MBB : mf) {
885  for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
886  if (!MBBI->isDebugValue()) {
887  ++MBBI;
888  continue;
889  }
890  MBBI = MBB.erase(MBBI);
891  }
892  }
893 }
894 
895 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
896  if (!EnableLDV)
897  return false;
898  if (!mf.getFunction().getSubprogram()) {
899  removeDebugValues(mf);
900  return false;
901  }
902  if (!pImpl)
903  pImpl = new LDVImpl(this);
904  return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
905 }
906 
907 void LiveDebugVariables::releaseMemory() {
908  if (pImpl)
909  static_cast<LDVImpl*>(pImpl)->clear();
910 }
911 
913  if (pImpl)
914  delete static_cast<LDVImpl*>(pImpl);
915 }
916 
917 //===----------------------------------------------------------------------===//
918 // Live Range Splitting
919 //===----------------------------------------------------------------------===//
920 
921 bool
922 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
923  LiveIntervals& LIS) {
924  LLVM_DEBUG({
925  dbgs() << "Splitting Loc" << OldLocNo << '\t';
926  print(dbgs(), nullptr);
927  });
928  bool DidChange = false;
929  LocMap::iterator LocMapI;
930  LocMapI.setMap(locInts);
931  for (unsigned i = 0; i != NewRegs.size(); ++i) {
932  LiveInterval *LI = &LIS.getInterval(NewRegs[i]);
933  if (LI->empty())
934  continue;
935 
936  // Don't allocate the new LocNo until it is needed.
937  unsigned NewLocNo = UndefLocNo;
938 
939  // Iterate over the overlaps between locInts and LI.
940  LocMapI.find(LI->beginIndex());
941  if (!LocMapI.valid())
942  continue;
943  LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
944  LiveInterval::iterator LIE = LI->end();
945  while (LocMapI.valid() && LII != LIE) {
946  // At this point, we know that LocMapI.stop() > LII->start.
947  LII = LI->advanceTo(LII, LocMapI.start());
948  if (LII == LIE)
949  break;
950 
951  // Now LII->end > LocMapI.start(). Do we have an overlap?
952  if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
953  // Overlapping correct location. Allocate NewLocNo now.
954  if (NewLocNo == UndefLocNo) {
956  MO.setSubReg(locations[OldLocNo].getSubReg());
957  NewLocNo = getLocationNo(MO);
958  DidChange = true;
959  }
960 
961  SlotIndex LStart = LocMapI.start();
962  SlotIndex LStop = LocMapI.stop();
963  DbgValueLocation OldLoc = LocMapI.value();
964 
965  // Trim LocMapI down to the LII overlap.
966  if (LStart < LII->start)
967  LocMapI.setStartUnchecked(LII->start);
968  if (LStop > LII->end)
969  LocMapI.setStopUnchecked(LII->end);
970 
971  // Change the value in the overlap. This may trigger coalescing.
972  LocMapI.setValue(OldLoc.changeLocNo(NewLocNo));
973 
974  // Re-insert any removed OldLocNo ranges.
975  if (LStart < LocMapI.start()) {
976  LocMapI.insert(LStart, LocMapI.start(), OldLoc);
977  ++LocMapI;
978  assert(LocMapI.valid() && "Unexpected coalescing");
979  }
980  if (LStop > LocMapI.stop()) {
981  ++LocMapI;
982  LocMapI.insert(LII->end, LStop, OldLoc);
983  --LocMapI;
984  }
985  }
986 
987  // Advance to the next overlap.
988  if (LII->end < LocMapI.stop()) {
989  if (++LII == LIE)
990  break;
991  LocMapI.advanceTo(LII->start);
992  } else {
993  ++LocMapI;
994  if (!LocMapI.valid())
995  break;
996  LII = LI->advanceTo(LII, LocMapI.start());
997  }
998  }
999  }
1000 
1001  // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
1002  locations.erase(locations.begin() + OldLocNo);
1003  LocMapI.goToBegin();
1004  while (LocMapI.valid()) {
1005  DbgValueLocation v = LocMapI.value();
1006  if (v.locNo() == OldLocNo) {
1007  LLVM_DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
1008  << LocMapI.stop() << ")\n");
1009  LocMapI.erase();
1010  } else {
1011  // Undef values always have location number UndefLocNo, so don't change
1012  // locNo in that case. See getLocationNo().
1013  if (!v.isUndef() && v.locNo() > OldLocNo)
1014  LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
1015  ++LocMapI;
1016  }
1017  }
1018 
1019  LLVM_DEBUG({
1020  dbgs() << "Split result: \t";
1021  print(dbgs(), nullptr);
1022  });
1023  return DidChange;
1024 }
1025 
1026 bool
1027 UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
1028  LiveIntervals &LIS) {
1029  bool DidChange = false;
1030  // Split locations referring to OldReg. Iterate backwards so splitLocation can
1031  // safely erase unused locations.
1032  for (unsigned i = locations.size(); i ; --i) {
1033  unsigned LocNo = i-1;
1034  const MachineOperand *Loc = &locations[LocNo];
1035  if (!Loc->isReg() || Loc->getReg() != OldReg)
1036  continue;
1037  DidChange |= splitLocation(LocNo, NewRegs, LIS);
1038  }
1039  return DidChange;
1040 }
1041 
1042 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
1043  bool DidChange = false;
1044  for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
1045  DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
1046 
1047  if (!DidChange)
1048  return;
1049 
1050  // Map all of the new virtual registers.
1051  UserValue *UV = lookupVirtReg(OldReg);
1052  for (unsigned i = 0; i != NewRegs.size(); ++i)
1053  mapVirtReg(NewRegs[i], UV);
1054 }
1055 
1057 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
1058  if (pImpl)
1059  static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
1060 }
1061 
1062 void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF,
1063  const TargetInstrInfo &TII,
1064  const TargetRegisterInfo &TRI,
1065  SpillOffsetMap &SpillOffsets) {
1066  // Build a set of new locations with new numbers so we can coalesce our
1067  // IntervalMap if two vreg intervals collapse to the same physical location.
1068  // Use MapVector instead of SetVector because MapVector::insert returns the
1069  // position of the previously or newly inserted element. The boolean value
1070  // tracks if the location was produced by a spill.
1071  // FIXME: This will be problematic if we ever support direct and indirect
1072  // frame index locations, i.e. expressing both variables in memory and
1073  // 'int x, *px = &x'. The "spilled" bit must become part of the location.
1075  SmallVector<unsigned, 4> LocNoMap(locations.size());
1076  for (unsigned I = 0, E = locations.size(); I != E; ++I) {
1077  bool Spilled = false;
1078  unsigned SpillOffset = 0;
1079  MachineOperand Loc = locations[I];
1080  // Only virtual registers are rewritten.
1081  if (Loc.isReg() && Loc.getReg() &&
1083  unsigned VirtReg = Loc.getReg();
1084  if (VRM.isAssignedReg(VirtReg) &&
1086  // This can create a %noreg operand in rare cases when the sub-register
1087  // index is no longer available. That means the user value is in a
1088  // non-existent sub-register, and %noreg is exactly what we want.
1089  Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
1090  } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
1091  // Retrieve the stack slot offset.
1092  unsigned SpillSize;
1093  const MachineRegisterInfo &MRI = MF.getRegInfo();
1094  const TargetRegisterClass *TRC = MRI.getRegClass(VirtReg);
1095  bool Success = TII.getStackSlotRange(TRC, Loc.getSubReg(), SpillSize,
1096  SpillOffset, MF);
1097 
1098  // FIXME: Invalidate the location if the offset couldn't be calculated.
1099  (void)Success;
1100 
1101  Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
1102  Spilled = true;
1103  } else {
1104  Loc.setReg(0);
1105  Loc.setSubReg(0);
1106  }
1107  }
1108 
1109  // Insert this location if it doesn't already exist and record a mapping
1110  // from the old number to the new number.
1111  auto InsertResult = NewLocations.insert({Loc, {Spilled, SpillOffset}});
1112  unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first);
1113  LocNoMap[I] = NewLocNo;
1114  }
1115 
1116  // Rewrite the locations and record the stack slot offsets for spills.
1117  locations.clear();
1118  SpillOffsets.clear();
1119  for (auto &Pair : NewLocations) {
1120  bool Spilled;
1121  unsigned SpillOffset;
1122  std::tie(Spilled, SpillOffset) = Pair.second;
1123  locations.push_back(Pair.first);
1124  if (Spilled) {
1125  unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair);
1126  SpillOffsets[NewLocNo] = SpillOffset;
1127  }
1128  }
1129 
1130  // Update the interval map, but only coalesce left, since intervals to the
1131  // right use the old location numbers. This should merge two contiguous
1132  // DBG_VALUE intervals with different vregs that were allocated to the same
1133  // physical register.
1134  for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
1135  DbgValueLocation Loc = I.value();
1136  // Undef values don't exist in locations (and thus not in LocNoMap either)
1137  // so skip over them. See getLocationNo().
1138  if (Loc.isUndef())
1139  continue;
1140  unsigned NewLocNo = LocNoMap[Loc.locNo()];
1141  I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
1142  I.setStart(I.start());
1143  }
1144 }
1145 
1146 /// Find an iterator for inserting a DBG_VALUE instruction.
1149  LiveIntervals &LIS) {
1150  SlotIndex Start = LIS.getMBBStartIdx(MBB);
1151  Idx = Idx.getBaseIndex();
1152 
1153  // Try to find an insert location by going backwards from Idx.
1154  MachineInstr *MI;
1155  while (!(MI = LIS.getInstructionFromIndex(Idx))) {
1156  // We've reached the beginning of MBB.
1157  if (Idx == Start) {
1159  return I;
1160  }
1161  Idx = Idx.getPrevIndex();
1162  }
1163 
1164  // Don't insert anything after the first terminator, though.
1165  return MI->isTerminator() ? MBB->getFirstTerminator() :
1166  std::next(MachineBasicBlock::iterator(MI));
1167 }
1168 
1169 /// Find an iterator for inserting the next DBG_VALUE instruction
1170 /// (or end if no more insert locations found).
1174  SlotIndex StopIdx, MachineOperand &LocMO,
1175  LiveIntervals &LIS,
1176  const TargetRegisterInfo &TRI) {
1177  if (!LocMO.isReg())
1178  return MBB->instr_end();
1179  unsigned Reg = LocMO.getReg();
1180 
1181  // Find the next instruction in the MBB that define the register Reg.
1182  while (I != MBB->end() && !I->isTerminator()) {
1183  if (!LIS.isNotInMIMap(*I) &&
1185  break;
1186  if (I->definesRegister(Reg, &TRI))
1187  // The insert location is directly after the instruction/bundle.
1188  return std::next(I);
1189  ++I;
1190  }
1191  return MBB->end();
1192 }
1193 
1194 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
1195  SlotIndex StopIdx, DbgValueLocation Loc,
1196  bool Spilled, unsigned SpillOffset,
1197  LiveIntervals &LIS, const TargetInstrInfo &TII,
1198  const TargetRegisterInfo &TRI) {
1199  SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
1200  // Only search within the current MBB.
1201  StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
1202  MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
1203  // Undef values don't exist in locations so create new "noreg" register MOs
1204  // for them. See getLocationNo().
1205  MachineOperand MO = !Loc.isUndef() ?
1206  locations[Loc.locNo()] :
1207  MachineOperand::CreateReg(/* Reg */ 0, /* isDef */ false, /* isImp */ false,
1208  /* isKill */ false, /* isDead */ false,
1209  /* isUndef */ false, /* isEarlyClobber */ false,
1210  /* SubReg */ 0, /* isDebug */ true);
1211 
1212  ++NumInsertedDebugValues;
1213 
1214  assert(cast<DILocalVariable>(Variable)
1215  ->isValidLocationForIntrinsic(getDebugLoc()) &&
1216  "Expected inlined-at fields to agree");
1217 
1218  // If the location was spilled, the new DBG_VALUE will be indirect. If the
1219  // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
1220  // that the original virtual register was a pointer. Also, add the stack slot
1221  // offset for the spilled register to the expression.
1222  const DIExpression *Expr = Expression;
1223  bool IsIndirect = Loc.wasIndirect();
1224  if (Spilled) {
1225  auto Deref = IsIndirect ? DIExpression::WithDeref : DIExpression::NoDeref;
1226  Expr =
1227  DIExpression::prepend(Expr, DIExpression::NoDeref, SpillOffset, Deref);
1228  IsIndirect = true;
1229  }
1230 
1231  assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
1232 
1233  do {
1234  BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE),
1235  IsIndirect, MO, Variable, Expr);
1236 
1237  // Continue and insert DBG_VALUES after every redefinition of register
1238  // associated with the debug value within the range
1239  I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
1240  } while (I != MBB->end());
1241 }
1242 
1243 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
1244  const TargetInstrInfo &TII,
1245  const TargetRegisterInfo &TRI,
1246  const SpillOffsetMap &SpillOffsets) {
1248 
1249  for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
1250  SlotIndex Start = I.start();
1251  SlotIndex Stop = I.stop();
1252  DbgValueLocation Loc = I.value();
1253  auto SpillIt =
1254  !Loc.isUndef() ? SpillOffsets.find(Loc.locNo()) : SpillOffsets.end();
1255  bool Spilled = SpillIt != SpillOffsets.end();
1256  unsigned SpillOffset = Spilled ? SpillIt->second : 0;
1257 
1258  // If the interval start was trimmed to the lexical scope insert the
1259  // DBG_VALUE at the previous index (otherwise it appears after the
1260  // first instruction in the range).
1261  if (trimmedDefs.count(Start))
1262  Start = Start.getPrevIndex();
1263 
1264  LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
1266  SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
1267 
1268  LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1269  insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
1270  TRI);
1271  // This interval may span multiple basic blocks.
1272  // Insert a DBG_VALUE into each one.
1273  while (Stop > MBBEnd) {
1274  // Move to the next block.
1275  Start = MBBEnd;
1276  if (++MBB == MFEnd)
1277  break;
1278  MBBEnd = LIS.getMBBEndIdx(&*MBB);
1279  LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1280  insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII,
1281  TRI);
1282  }
1283  LLVM_DEBUG(dbgs() << '\n');
1284  if (MBB == MFEnd)
1285  break;
1286 
1287  ++I;
1288  }
1289 }
1290 
1291 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1292  LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1293  if (!MF)
1294  return;
1295  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1296  SpillOffsetMap SpillOffsets;
1297  for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
1298  LLVM_DEBUG(userValues[i]->print(dbgs(), TRI));
1299  userValues[i]->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
1300  userValues[i]->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets);
1301  }
1302  EmitDone = true;
1303 }
1304 
1306  if (pImpl)
1307  static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1308 }
1309 
1310 bool LiveDebugVariables::doInitialization(Module &M) {
1311  return Pass::doInitialization(M);
1312 }
1313 
1314 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1316  if (pImpl)
1317  static_cast<LDVImpl*>(pImpl)->print(dbgs());
1318 }
1319 #endif
static bool isReg(const MCInst &MI, unsigned OpNo)
void setValueUnchecked(ValT x)
setValueUnchecked - Change the mapped value of the current interval without checking for coalescing...
Definition: IntervalMap.h:1563
bool empty() const
Definition: LiveInterval.h:370
void setValue(ValT x)
setValue - Change the mapped value of the current interval.
Definition: IntervalMap.h:1701
Safe Stack instrumentation pass
Definition: SafeStack.cpp:910
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const unsigned reg
Definition: LiveInterval.h:667
instr_iterator instr_end()
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:242
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:61
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:300
static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS, const LLVMContext &Ctx)
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Segments::iterator iterator
Definition: LiveInterval.h:208
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:383
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
void initializeLiveDebugVariablesPass(PassRegistry &)
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
iterator advanceTo(iterator I, SlotIndex Pos)
advanceTo - Advance the specified iterator to point to the Segment containing the specified position...
Definition: LiveInterval.h:259
unsigned Reg
This file contains the declarations for metadata subclasses.
unsigned getSubReg() const
SmallVectorImpl< InsnRange > & getRanges()
Definition: LexicalScopes.h:67
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
bool isMetadata() const
isMetadata - Tests if this is a MO_Metadata operand.
unsigned getLine() const
Definition: DebugLoc.cpp:26
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
A debug info location.
Definition: DebugLoc.h:34
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1346
void setIsDead(bool Val=true)
void setMap(const IntervalMap &m)
setMap - Change the map iterated over.
Definition: IntervalMap.h:1343
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:45
void dump() const
dump - Print data structures to dbgs().
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
static DIExpression * prepend(const DIExpression *Expr, bool DerefBefore, int64_t Offset=0, bool DerefAfter=false, bool StackValue=false)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value...
static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
bool isNotInMIMap(const MachineInstr &Instr) const
Returns true if the specified machine instr has been removed or was never entered in the map...
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
SlotIndex getNextIndex() const
Returns the next index.
Definition: SlotIndexes.h:280
MachineFunction & getMachineFunction() const
Definition: VirtRegMap.h:83
StringRef getName() const
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
void emitDebugValues(VirtRegMap *VRM)
emitDebugValues - Emit new DBG_VALUE instructions reflecting the changes that happened during registe...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:412
iterator end()
Definition: LiveInterval.h:212
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
Result of a LiveRange query.
Definition: LiveInterval.h:90
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1430
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:649
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
DbgValueLocation(unsigned LocNo, bool WasIndirect)
friend bool operator==(const DbgValueLocation &LHS, const DbgValueLocation &RHS)
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:255
void initialize(const MachineFunction &)
initialize - Scan machine function and constuct lexical scope nest, resets the instance if necessary...
void erase()
erase - Erase the current interval.
Definition: IntervalMap.h:1858
LLVMContext & getContext() const
Definition: Metadata.h:924
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
bool isAssignedReg(unsigned virtReg) const
returns true if the specified virtual register is not mapped to a stack slot or rematerialized.
Definition: VirtRegMap.h:154
SlotIndex getNextSlot() const
Returns the next slot in the index list.
Definition: SlotIndexes.h:270
void clearParent()
clearParent - Reset the parent pointer.
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
virtual const TargetInstrInfo * getInstrInfo() const
Debug location.
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end()...
Definition: IntervalMap.h:1126
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:106
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void setStartUnchecked(KeyT a)
setStartUnchecked - Move the start of the current interval without checking for coalescing or overlap...
Definition: IntervalMap.h:1547
DbgValueLocation changeLocNo(unsigned NewLocNo) const
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:529
TargetInstrInfo - Interface to description of machine instruction set.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:151
bool isIdenticalTo(const MachineOperand &Other) const
Returns true if this operand is identical to the specified operand except for liveness related flags ...
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:409
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
unsigned const MachineRegisterInfo * MRI
bool hasInterval(unsigned Reg) const
static void removeDebugValues(MachineFunction &mf)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:960
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1508
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
INITIALIZE_PASS_BEGIN(LiveDebugVariables, DEBUG_TYPE, "Debug Variable Analysis", false, false) INITIALIZE_PASS_END(LiveDebugVariables
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
void find(KeyT x)
find - Move to the first interval with stop >= x, or end().
Definition: IntervalMap.h:1420
const KeyT & start() const
start - Return the beginning of the current interval.
Definition: IntervalMap.h:1352
void goToBegin()
goToBegin - Move to the first interval in map.
Definition: IntervalMap.h:1376
Represent the analysis usage information of a pass.
void substPhysReg(unsigned Reg, const TargetRegisterInfo &)
substPhysReg - Substitute the current register with the physical register Reg, taking any existing Su...
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
self_iterator getIterator()
Definition: ilist_node.h:82
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
MDNode * getScope() const
Definition: DebugLoc.cpp:36
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
virtual bool getStackSlotRange(const TargetRegisterClass *RC, unsigned SubIdx, unsigned &Size, unsigned &Offset, const MachineFunction &MF) const
Compute the size in bytes and offset within a stack slot of a spilled register or subregister...
bool isCopy() const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
size_t size() const
Definition: SmallVector.h:53
DILocation * getInlinedAt() const
Definition: DebugLoc.cpp:41
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
const DIExpression * getDebugExpression() const
Return the complex address expression referenced by this DBG_VALUE instruction.
unsigned id
The ID number of this value.
Definition: LiveInterval.h:58
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
#define DEBUG_TYPE
Iterator for intrusive lists based on ilist_node.
void splitRegister(unsigned OldReg, ArrayRef< unsigned > NewRegs, LiveIntervals &LIS)
splitRegister - Move any user variables in OldReg to the live ranges in NewRegs where they are live...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
friend bool operator!=(const DbgValueLocation &LHS, const DbgValueLocation &RHS)
Debug Variable Analysis
LiveInterval & getInterval(unsigned Reg)
int64_t getImm() const
DWARF expression.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const ValT & value() const
value - Return the mapped value at the current interval.
Definition: IntervalMap.h:1358
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
VNInfo * valueOutOrDead() const
Returns the value alive at the end of the instruction, if any.
Definition: LiveInterval.h:129
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:212
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1355
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:254
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
#define Success
void insert(KeyT a, KeyT b, ValT y)
insert - Insert mapping [a;b] -> y before the current position.
Definition: IntervalMap.h:1769
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
static void printExtendedName(raw_ostream &OS, const DILocalVariable *V, const DILocation *DL)
static bool isEarlierEqualInstr(SlotIndex A, SlotIndex B)
Return true if A refers to the same instruction as B or an earlier one.
Definition: SlotIndexes.h:210
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static DebugLoc getDebugLoc(MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
Return the first found DebugLoc that has a DILocation, given a range of instructions.
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
static MachineBasicBlock::iterator findNextInsertLocation(MachineBasicBlock *MBB, MachineBasicBlock::iterator I, SlotIndex StopIdx, MachineOperand &LocMO, LiveIntervals &LIS, const TargetRegisterInfo &TRI)
Find an iterator for inserting the next DBG_VALUE instruction (or end if no more insert locations fou...
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:45
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
static cl::opt< bool > EnableLDV("live-debug-variables", cl::init(true), cl::desc("Enable the live debug variables pass"), cl::Hidden)
void setIsUse(bool Val=true)
void setSubReg(unsigned subReg)
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
iterator end()
Definition: DenseMap.h:84
virtual void print(raw_ostream &OS, const Module *M) const
print - Print out the internal state of the pass.
Definition: Pass.cpp:124
Describes a location by number along with some flags about the original usage of the location...
unsigned getPhys(unsigned virtReg) const
returns the physical register mapped to the specified virtual register
Definition: VirtRegMap.h:101
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Segment * getSegmentContaining(SlotIndex Idx) const
Return the segment that contains the specified index, or null if there is none.
Definition: LiveInterval.h:396
iterator begin()
Definition: MapVector.h:70
unsigned getCol() const
Definition: DebugLoc.cpp:31
iterator begin()
Definition: LiveInterval.h:211
unsigned locNo() const
void setStopUnchecked(KeyT b)
setStopUnchecked - Move the end of the current interval without checking for coalescing or overlaps...
Definition: IntervalMap.h:1553
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:373
int getStackSlot(unsigned virtReg) const
returns the stack slot mapped to the specified virtual register
Definition: VirtRegMap.h:164
static cl::opt< bool, true > Debug("debug", cl::desc("Enable debug output"), cl::Hidden, cl::location(DebugFlag))
const DILocalVariable * getDebugVariable() const
Return the debug variable referenced by this DBG_VALUE instruction.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
iterator SkipPHIsLabelsAndDebug(iterator I)
Return the first instruction in MBB after I that is not a PHI, label or debug.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
unsigned getLine() const
static MachineBasicBlock::iterator findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, LiveIntervals &LIS)
Find an iterator for inserting a DBG_VALUE instruction.
void setIsDebug(bool Val=true)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
static MachineOperand CreateFI(int Idx)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
std::pair< const MachineInstr *, const MachineInstr * > InsnRange
InsnRange - This is used to track range of instructions with identical lexical scope.
Definition: LexicalScopes.h:40