contrib/llvm/lib/CodeGen/LiveDebugVariables.cpp

   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"
  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/IR/DebugInfoMetadata.h"
  48 #include "llvm/IR/DebugLoc.h"
  49 #include "llvm/IR/Function.h"
  50 #include "llvm/IR/Metadata.h"
  51 #include "llvm/MC/MCRegisterInfo.h"
  52 #include "llvm/Pass.h"
  53 #include "llvm/Support/Casting.h"
  54 #include "llvm/Support/CommandLine.h"
  55 #include "llvm/Support/Compiler.h"
  56 #include "llvm/Support/Debug.h"
  57 #include "llvm/Support/raw_ostream.h"
  58 #include <algorithm>
  59 #include <cassert>
  60 #include <iterator>
  61 #include <memory>
  62 #include <utility>
  63
  64 using namespace llvm;
  65
  66 #define DEBUG_TYPE "livedebugvars"
  67
  68 static cl::opt<bool>
  69 EnableLDV("live-debug-variables", cl::init(true),
  70           cl::desc("Enable the live debug variables pass"), cl::Hidden);
  71
  72 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
  73
  74 char LiveDebugVariables::ID = 0;
  75
  76 INITIALIZE_PASS_BEGIN(LiveDebugVariables, DEBUG_TYPE,
  77                 "Debug Variable Analysis", false, false)
  78 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  79 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  80 INITIALIZE_PASS_END(LiveDebugVariables, DEBUG_TYPE,
  81                 "Debug Variable Analysis", false, false)
  82
  83 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
  84   AU.addRequired<MachineDominatorTree>();
  85   AU.addRequiredTransitive<LiveIntervals>();
  86   AU.setPreservesAll();
  87   MachineFunctionPass::getAnalysisUsage(AU);
  88 }
  89
  90 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) {
  91   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
  92 }
  93
  94 enum : unsigned { UndefLocNo = ~0U };
  95
  96 /// Describes a location by number along with some flags about the original
  97 /// usage of the location.
  98 class DbgValueLocation {
  99 public:
 100   DbgValueLocation(unsigned LocNo, bool WasIndirect)
 101       : LocNo(LocNo), WasIndirect(WasIndirect) {
 102     static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing");
 103     assert(locNo() == LocNo && "location truncation");
 104   }
 105
 106   DbgValueLocation() : LocNo(0), WasIndirect(0) {}
 107
 108   unsigned locNo() const {
 109     // Fix up the undef location number, which gets truncated.
 110     return LocNo == INT_MAX ? UndefLocNo : LocNo;
 111   }
 112   bool wasIndirect() const { return WasIndirect; }
 113   bool isUndef() const { return locNo() == UndefLocNo; }
 114
 115   DbgValueLocation changeLocNo(unsigned NewLocNo) const {
 116     return DbgValueLocation(NewLocNo, WasIndirect);
 117   }
 118
 119   friend inline bool operator==(const DbgValueLocation &LHS,
 120                                 const DbgValueLocation &RHS) {
 121     return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect;
 122   }
 123
 124   friend inline bool operator!=(const DbgValueLocation &LHS,
 125                                 const DbgValueLocation &RHS) {
 126     return !(LHS == RHS);
 127   }
 128
 129 private:
 130   unsigned LocNo : 31;
 131   unsigned WasIndirect : 1;
 132 };
 133
 134 /// LocMap - Map of where a user value is live, and its location.
 135 using LocMap = IntervalMap<SlotIndex, DbgValueLocation, 4>;
 136
 137 namespace {
 138
 139 class LDVImpl;
 140
 141 /// UserValue - A user value is a part of a debug info user variable.
 142 ///
 143 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 144 /// holds part of a user variable. The part is identified by a byte offset.
 145 ///
 146 /// UserValues are grouped into equivalence classes for easier searching. Two
 147 /// user values are related if they refer to the same variable, or if they are
 148 /// held by the same virtual register. The equivalence class is the transitive
 149 /// closure of that relation.
 150 class UserValue {
 151   const DILocalVariable *Variable; ///< The debug info variable we are part of.
 152   const DIExpression *Expression; ///< Any complex address expression.
 153   DebugLoc dl;            ///< The debug location for the variable. This is
 154                           ///< used by dwarf writer to find lexical scope.
 155   UserValue *leader;      ///< Equivalence class leader.
 156   UserValue *next = nullptr; ///< Next value in equivalence class, or null.
 157
 158   /// Numbered locations referenced by locmap.
 159   SmallVector<MachineOperand, 4> locations;
 160
 161   /// Map of slot indices where this value is live.
 162   LocMap locInts;
 163
 164   /// Set of interval start indexes that have been trimmed to the
 165   /// lexical scope.
 166   SmallSet<SlotIndex, 2> trimmedDefs;
 167
 168   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
 169   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
 170                         SlotIndex StopIdx,
 171                         DbgValueLocation Loc, bool Spilled, LiveIntervals &LIS,
 172                         const TargetInstrInfo &TII,
 173                         const TargetRegisterInfo &TRI);
 174
 175   /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
 176   /// is live. Returns true if any changes were made.
 177   bool splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 178                      LiveIntervals &LIS);
 179
 180 public:
 181   /// UserValue - Create a new UserValue.
 182   UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
 183             LocMap::Allocator &alloc)
 184       : Variable(var), Expression(expr), dl(std::move(L)), leader(this),
 185         locInts(alloc) {}
 186
 187   /// getLeader - Get the leader of this value's equivalence class.
 188   UserValue *getLeader() {
 189     UserValue *l = leader;
 190     while (l != l->leader)
 191       l = l->leader;
 192     return leader = l;
 193   }
 194
 195   /// getNext - Return the next UserValue in the equivalence class.
 196   UserValue *getNext() const { return next; }
 197
 198   /// match - Does this UserValue match the parameters?
 199   bool match(const DILocalVariable *Var, const DIExpression *Expr,
 200              const DILocation *IA) const {
 201     // FIXME: The fragment should be part of the equivalence class, but not
 202     // other things in the expression like stack values.
 203     return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA;
 204   }
 205
 206   /// merge - Merge equivalence classes.
 207   static UserValue *merge(UserValue *L1, UserValue *L2) {
 208     L2 = L2->getLeader();
 209     if (!L1)
 210       return L2;
 211     L1 = L1->getLeader();
 212     if (L1 == L2)
 213       return L1;
 214     // Splice L2 before L1's members.
 215     UserValue *End = L2;
 216     while (End->next) {
 217       End->leader = L1;
 218       End = End->next;
 219     }
 220     End->leader = L1;
 221     End->next = L1->next;
 222     L1->next = L2;
 223     return L1;
 224   }
 225
 226   /// getLocationNo - Return the location number that matches Loc.
 227   unsigned getLocationNo(const MachineOperand &LocMO) {
 228     if (LocMO.isReg()) {
 229       if (LocMO.getReg() == 0)
 230         return UndefLocNo;
 231       // For register locations we dont care about use/def and other flags.
 232       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 233         if (locations[i].isReg() &&
 234             locations[i].getReg() == LocMO.getReg() &&
 235             locations[i].getSubReg() == LocMO.getSubReg())
 236           return i;
 237     } else
 238       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 239         if (LocMO.isIdenticalTo(locations[i]))
 240           return i;
 241     locations.push_back(LocMO);
 242     // We are storing a MachineOperand outside a MachineInstr.
 243     locations.back().clearParent();
 244     // Don't store def operands.
 245     if (locations.back().isReg()) {
 246       if (locations.back().isDef())
 247         locations.back().setIsDead(false);
 248       locations.back().setIsUse();
 249     }
 250     return locations.size() - 1;
 251   }
 252
 253   /// mapVirtRegs - Ensure that all virtual register locations are mapped.
 254   void mapVirtRegs(LDVImpl *LDV);
 255
 256   /// addDef - Add a definition point to this value.
 257   void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect) {
 258     DbgValueLocation Loc(getLocationNo(LocMO), IsIndirect);
 259     // Add a singular (Idx,Idx) -> Loc mapping.
 260     LocMap::iterator I = locInts.find(Idx);
 261     if (!I.valid() || I.start() != Idx)
 262       I.insert(Idx, Idx.getNextSlot(), Loc);
 263     else
 264       // A later DBG_VALUE at the same SlotIndex overrides the old location.
 265       I.setValue(Loc);
 266   }
 267
 268   /// extendDef - Extend the current definition as far as possible down.
 269   /// Stop when meeting an existing def or when leaving the live
 270   /// range of VNI.
 271   /// End points where VNI is no longer live are added to Kills.
 272   /// @param Idx   Starting point for the definition.
 273   /// @param Loc   Location number to propagate.
 274   /// @param LR    Restrict liveness to where LR has the value VNI. May be null.
 275   /// @param VNI   When LR is not null, this is the value to restrict to.
 276   /// @param Kills Append end points of VNI's live range to Kills.
 277   /// @param LIS   Live intervals analysis.
 278   void extendDef(SlotIndex Idx, DbgValueLocation Loc,
 279                  LiveRange *LR, const VNInfo *VNI,
 280                  SmallVectorImpl<SlotIndex> *Kills,
 281                  LiveIntervals &LIS);
 282
 283   /// addDefsFromCopies - The value in LI/LocNo may be copies to other
 284   /// registers. Determine if any of the copies are available at the kill
 285   /// points, and add defs if possible.
 286   /// @param LI      Scan for copies of the value in LI->reg.
 287   /// @param LocNo   Location number of LI->reg.
 288   /// @param WasIndirect Indicates if the original use of LI->reg was indirect
 289   /// @param Kills   Points where the range of LocNo could be extended.
 290   /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
 291   void addDefsFromCopies(
 292       LiveInterval *LI, unsigned LocNo, bool WasIndirect,
 293       const SmallVectorImpl<SlotIndex> &Kills,
 294       SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
 295       MachineRegisterInfo &MRI, LiveIntervals &LIS);
 296
 297   /// computeIntervals - Compute the live intervals of all locations after
 298   /// collecting all their def points.
 299   void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
 300                         LiveIntervals &LIS, LexicalScopes &LS);
 301
 302   /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
 303   /// live. Returns true if any changes were made.
 304   bool splitRegister(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 305                      LiveIntervals &LIS);
 306
 307   /// rewriteLocations - Rewrite virtual register locations according to the
 308   /// provided virtual register map. Record which locations were spilled.
 309   void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI,
 310                         BitVector &SpilledLocations);
 311
 312   /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
 313   void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
 314                        const TargetInstrInfo &TII,
 315                        const TargetRegisterInfo &TRI,
 316                        const BitVector &SpilledLocations);
 317
 318   /// getDebugLoc - Return DebugLoc of this UserValue.
 319   DebugLoc getDebugLoc() { return dl;}
 320
 321   void print(raw_ostream &, const TargetRegisterInfo *);
 322 };
 323
 324 /// LDVImpl - Implementation of the LiveDebugVariables pass.
 325 class LDVImpl {
 326   LiveDebugVariables &pass;
 327   LocMap::Allocator allocator;
 328   MachineFunction *MF = nullptr;
 329   LiveIntervals *LIS;
 330   const TargetRegisterInfo *TRI;
 331
 332   /// Whether emitDebugValues is called.
 333   bool EmitDone = false;
 334
 335   /// Whether the machine function is modified during the pass.
 336   bool ModifiedMF = false;
 337
 338   /// userValues - All allocated UserValue instances.
 339   SmallVector<std::unique_ptr<UserValue>, 8> userValues;
 340
 341   /// Map virtual register to eq class leader.
 342   using VRMap = DenseMap<unsigned, UserValue *>;
 343   VRMap virtRegToEqClass;
 344
 345   /// Map user variable to eq class leader.
 346   using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
 347   UVMap userVarMap;
 348
 349   /// getUserValue - Find or create a UserValue.
 350   UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
 351                           const DebugLoc &DL);
 352
 353   /// lookupVirtReg - Find the EC leader for VirtReg or null.
 354   UserValue *lookupVirtReg(unsigned VirtReg);
 355
 356   /// handleDebugValue - Add DBG_VALUE instruction to our maps.
 357   /// @param MI  DBG_VALUE instruction
 358   /// @param Idx Last valid SLotIndex before instruction.
 359   /// @return    True if the DBG_VALUE instruction should be deleted.
 360   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
 361
 362   /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
 363   /// a UserValue def for each instruction.
 364   /// @param mf MachineFunction to be scanned.
 365   /// @return True if any debug values were found.
 366   bool collectDebugValues(MachineFunction &mf);
 367
 368   /// computeIntervals - Compute the live intervals of all user values after
 369   /// collecting all their def points.
 370   void computeIntervals();
 371
 372 public:
 373   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 374
 375   bool runOnMachineFunction(MachineFunction &mf);
 376
 377   /// clear - Release all memory.
 378   void clear() {
 379     MF = nullptr;
 380     userValues.clear();
 381     virtRegToEqClass.clear();
 382     userVarMap.clear();
 383     // Make sure we call emitDebugValues if the machine function was modified.
 384     assert((!ModifiedMF || EmitDone) &&
 385            "Dbg values are not emitted in LDV");
 386     EmitDone = false;
 387     ModifiedMF = false;
 388   }
 389
 390   /// mapVirtReg - Map virtual register to an equivalence class.
 391   void mapVirtReg(unsigned VirtReg, UserValue *EC);
 392
 393   /// splitRegister -  Replace all references to OldReg with NewRegs.
 394   void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
 395
 396   /// emitDebugValues - Recreate DBG_VALUE instruction from data structures.
 397   void emitDebugValues(VirtRegMap *VRM);
 398
 399   void print(raw_ostream&);
 400 };
 401
 402 } // end anonymous namespace
 403
 404 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 405 static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS,
 406                           const LLVMContext &Ctx) {
 407   if (!DL)
 408     return;
 409
 410   auto *Scope = cast<DIScope>(DL.getScope());
 411   // Omit the directory, because it's likely to be long and uninteresting.
 412   CommentOS << Scope->getFilename();
 413   CommentOS << ':' << DL.getLine();
 414   if (DL.getCol() != 0)
 415     CommentOS << ':' << DL.getCol();
 416
 417   DebugLoc InlinedAtDL = DL.getInlinedAt();
 418   if (!InlinedAtDL)
 419     return;
 420
 421   CommentOS << " @[ ";
 422   printDebugLoc(InlinedAtDL, CommentOS, Ctx);
 423   CommentOS << " ]";
 424 }
 425
 426 static void printExtendedName(raw_ostream &OS, const DILocalVariable *V,
 427                               const DILocation *DL) {
 428   const LLVMContext &Ctx = V->getContext();
 429   StringRef Res = V->getName();
 430   if (!Res.empty())
 431     OS << Res << "," << V->getLine();
 432   if (auto *InlinedAt = DL->getInlinedAt()) {
 433     if (DebugLoc InlinedAtDL = InlinedAt) {
 434       OS << " @[";
 435       printDebugLoc(InlinedAtDL, OS, Ctx);
 436       OS << "]";
 437     }
 438   }
 439 }
 440
 441 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
 442   auto *DV = cast<DILocalVariable>(Variable);
 443   OS << "!\"";
 444   printExtendedName(OS, DV, dl);
 445
 446   OS << "\"\t";
 447   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
 448     OS << " [" << I.start() << ';' << I.stop() << "):";
 449     if (I.value().isUndef())
 450       OS << "undef";
 451     else {
 452       OS << I.value().locNo();
 453       if (I.value().wasIndirect())
 454         OS << " ind";
 455     }
 456   }
 457   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
 458     OS << " Loc" << i << '=';
 459     locations[i].print(OS, TRI);
 460   }
 461   OS << '\n';
 462 }
 463
 464 void LDVImpl::print(raw_ostream &OS) {
 465   OS << "********** DEBUG VARIABLES **********\n";
 466   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
 467     userValues[i]->print(OS, TRI);
 468 }
 469 #endif
 470
 471 void UserValue::mapVirtRegs(LDVImpl *LDV) {
 472   for (unsigned i = 0, e = locations.size(); i != e; ++i)
 473     if (locations[i].isReg() &&
 474         TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
 475       LDV->mapVirtReg(locations[i].getReg(), this);
 476 }
 477
 478 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
 479                                  const DIExpression *Expr, const DebugLoc &DL) {
 480   UserValue *&Leader = userVarMap[Var];
 481   if (Leader) {
 482     UserValue *UV = Leader->getLeader();
 483     Leader = UV;
 484     for (; UV; UV = UV->getNext())
 485       if (UV->match(Var, Expr, DL->getInlinedAt()))
 486         return UV;
 487   }
 488
 489   userValues.push_back(
 490       llvm::make_unique<UserValue>(Var, Expr, DL, allocator));
 491   UserValue *UV = userValues.back().get();
 492   Leader = UserValue::merge(Leader, UV);
 493   return UV;
 494 }
 495
 496 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
 497   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
 498   UserValue *&Leader = virtRegToEqClass[VirtReg];
 499   Leader = UserValue::merge(Leader, EC);
 500 }
 501
 502 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
 503   if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
 504     return UV->getLeader();
 505   return nullptr;
 506 }
 507
 508 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
 509   // DBG_VALUE loc, offset, variable
 510   if (MI.getNumOperands() != 4 ||
 511       !(MI.getOperand(1).isReg() || MI.getOperand(1).isImm()) ||
 512       !MI.getOperand(2).isMetadata()) {
 513     DEBUG(dbgs() << "Can't handle " << MI);
 514     return false;
 515   }
 516
 517   // Detect invalid DBG_VALUE instructions, with a debug-use of a virtual
 518   // register that hasn't been defined yet. If we do not remove those here, then
 519   // the re-insertion of the DBG_VALUE instruction after register allocation
 520   // will be incorrect.
 521   // TODO: If earlier passes are corrected to generate sane debug information
 522   // (and if the machine verifier is improved to catch this), then these checks
 523   // could be removed or replaced by asserts.
 524   bool Discard = false;
 525   if (MI.getOperand(0).isReg() &&
 526       TargetRegisterInfo::isVirtualRegister(MI.getOperand(0).getReg())) {
 527     const unsigned Reg = MI.getOperand(0).getReg();
 528     if (!LIS->hasInterval(Reg)) {
 529       // The DBG_VALUE is described by a virtual register that does not have a
 530       // live interval. Discard the DBG_VALUE.
 531       Discard = true;
 532       DEBUG(dbgs() << "Discarding debug info (no LIS interval): "
 533             << Idx << " " << MI);
 534     } else {
 535       // The DBG_VALUE is only valid if either Reg is live out from Idx, or Reg
 536       // is defined dead at Idx (where Idx is the slot index for the instruction
 537       // preceeding the DBG_VALUE).
 538       const LiveInterval &LI = LIS->getInterval(Reg);
 539       LiveQueryResult LRQ = LI.Query(Idx);
 540       if (!LRQ.valueOutOrDead()) {
 541         // We have found a DBG_VALUE with the value in a virtual register that
 542         // is not live. Discard the DBG_VALUE.
 543         Discard = true;
 544         DEBUG(dbgs() << "Discarding debug info (reg not live): "
 545               << Idx << " " << MI);
 546       }
 547     }
 548   }
 549
 550   // Get or create the UserValue for (variable,offset) here.
 551   bool IsIndirect = MI.getOperand(1).isImm();
 552   if (IsIndirect)
 553     assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
 554   const DILocalVariable *Var = MI.getDebugVariable();
 555   const DIExpression *Expr = MI.getDebugExpression();
 556   UserValue *UV =
 557       getUserValue(Var, Expr, MI.getDebugLoc());
 558   if (!Discard)
 559     UV->addDef(Idx, MI.getOperand(0), IsIndirect);
 560   else {
 561     MachineOperand MO = MachineOperand::CreateReg(0U, false);
 562     MO.setIsDebug();
 563     UV->addDef(Idx, MO, false);
 564   }
 565   return true;
 566 }
 567
 568 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
 569   bool Changed = false;
 570   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
 571        ++MFI) {
 572     MachineBasicBlock *MBB = &*MFI;
 573     for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
 574          MBBI != MBBE;) {
 575       if (!MBBI->isDebugValue()) {
 576         ++MBBI;
 577         continue;
 578       }
 579       // DBG_VALUE has no slot index, use the previous instruction instead.
 580       SlotIndex Idx =
 581           MBBI == MBB->begin()
 582               ? LIS->getMBBStartIdx(MBB)
 583               : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
 584       // Handle consecutive DBG_VALUE instructions with the same slot index.
 585       do {
 586         if (handleDebugValue(*MBBI, Idx)) {
 587           MBBI = MBB->erase(MBBI);
 588           Changed = true;
 589         } else
 590           ++MBBI;
 591       } while (MBBI != MBBE && MBBI->isDebugValue());
 592     }
 593   }
 594   return Changed;
 595 }
 596
 597 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
 598 /// data-flow analysis to propagate them beyond basic block boundaries.
 599 void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
 600                           const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
 601                           LiveIntervals &LIS) {
 602   SlotIndex Start = Idx;
 603   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
 604   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
 605   LocMap::iterator I = locInts.find(Start);
 606
 607   // Limit to VNI's live range.
 608   bool ToEnd = true;
 609   if (LR && VNI) {
 610     LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
 611     if (!Segment || Segment->valno != VNI) {
 612       if (Kills)
 613         Kills->push_back(Start);
 614       return;
 615     }
 616     if (Segment->end < Stop) {
 617       Stop = Segment->end;
 618       ToEnd = false;
 619     }
 620   }
 621
 622   // There could already be a short def at Start.
 623   if (I.valid() && I.start() <= Start) {
 624     // Stop when meeting a different location or an already extended interval.
 625     Start = Start.getNextSlot();
 626     if (I.value() != Loc || I.stop() != Start)
 627       return;
 628     // This is a one-slot placeholder. Just skip it.
 629     ++I;
 630   }
 631
 632   // Limited by the next def.
 633   if (I.valid() && I.start() < Stop) {
 634     Stop = I.start();
 635     ToEnd = false;
 636   }
 637   // Limited by VNI's live range.
 638   else if (!ToEnd && Kills)
 639     Kills->push_back(Stop);
 640
 641   if (Start < Stop)
 642     I.insert(Start, Stop, Loc);
 643 }
 644
 645 void UserValue::addDefsFromCopies(
 646     LiveInterval *LI, unsigned LocNo, bool WasIndirect,
 647     const SmallVectorImpl<SlotIndex> &Kills,
 648     SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
 649     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
 650   if (Kills.empty())
 651     return;
 652   // Don't track copies from physregs, there are too many uses.
 653   if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
 654     return;
 655
 656   // Collect all the (vreg, valno) pairs that are copies of LI.
 657   SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
 658   for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
 659     MachineInstr *MI = MO.getParent();
 660     // Copies of the full value.
 661     if (MO.getSubReg() || !MI->isCopy())
 662       continue;
 663     unsigned DstReg = MI->getOperand(0).getReg();
 664
 665     // Don't follow copies to physregs. These are usually setting up call
 666     // arguments, and the argument registers are always call clobbered. We are
 667     // better off in the source register which could be a callee-saved register,
 668     // or it could be spilled.
 669     if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 670       continue;
 671
 672     // Is LocNo extended to reach this copy? If not, another def may be blocking
 673     // it, or we are looking at a wrong value of LI.
 674     SlotIndex Idx = LIS.getInstructionIndex(*MI);
 675     LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
 676     if (!I.valid() || I.value().locNo() != LocNo)
 677       continue;
 678
 679     if (!LIS.hasInterval(DstReg))
 680       continue;
 681     LiveInterval *DstLI = &LIS.getInterval(DstReg);
 682     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
 683     assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
 684     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
 685   }
 686
 687   if (CopyValues.empty())
 688     return;
 689
 690   DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n');
 691
 692   // Try to add defs of the copied values for each kill point.
 693   for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 694     SlotIndex Idx = Kills[i];
 695     for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
 696       LiveInterval *DstLI = CopyValues[j].first;
 697       const VNInfo *DstVNI = CopyValues[j].second;
 698       if (DstLI->getVNInfoAt(Idx) != DstVNI)
 699         continue;
 700       // Check that there isn't already a def at Idx
 701       LocMap::iterator I = locInts.find(Idx);
 702       if (I.valid() && I.start() <= Idx)
 703         continue;
 704       DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
 705                    << DstVNI->id << " in " << *DstLI << '\n');
 706       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
 707       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
 708       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
 709       DbgValueLocation NewLoc(LocNo, WasIndirect);
 710       I.insert(Idx, Idx.getNextSlot(), NewLoc);
 711       NewDefs.push_back(std::make_pair(Idx, NewLoc));
 712       break;
 713     }
 714   }
 715 }
 716
 717 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
 718                                  const TargetRegisterInfo &TRI,
 719                                  LiveIntervals &LIS, LexicalScopes &LS) {
 720   SmallVector<std::pair<SlotIndex, DbgValueLocation>, 16> Defs;
 721
 722   // Collect all defs to be extended (Skipping undefs).
 723   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
 724     if (!I.value().isUndef())
 725       Defs.push_back(std::make_pair(I.start(), I.value()));
 726
 727   // Extend all defs, and possibly add new ones along the way.
 728   for (unsigned i = 0; i != Defs.size(); ++i) {
 729     SlotIndex Idx = Defs[i].first;
 730     DbgValueLocation Loc = Defs[i].second;
 731     const MachineOperand &LocMO = locations[Loc.locNo()];
 732
 733     if (!LocMO.isReg()) {
 734       extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
 735       continue;
 736     }
 737
 738     // Register locations are constrained to where the register value is live.
 739     if (TargetRegisterInfo::isVirtualRegister(LocMO.getReg())) {
 740       LiveInterval *LI = nullptr;
 741       const VNInfo *VNI = nullptr;
 742       if (LIS.hasInterval(LocMO.getReg())) {
 743         LI = &LIS.getInterval(LocMO.getReg());
 744         VNI = LI->getVNInfoAt(Idx);
 745       }
 746       SmallVector<SlotIndex, 16> Kills;
 747       extendDef(Idx, Loc, LI, VNI, &Kills, LIS);
 748       if (LI)
 749         addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
 750                           LIS);
 751       continue;
 752     }
 753
 754     // For physregs, we only mark the start slot idx. DwarfDebug will see it
 755     // as if the DBG_VALUE is valid up until the end of the basic block, or
 756     // the next def of the physical register. So we do not need to extend the
 757     // range. It might actually happen that the DBG_VALUE is the last use of
 758     // the physical register (e.g. if this is an unused input argument to a
 759     // function).
 760   }
 761
 762   // Erase all the undefs.
 763   for (LocMap::iterator I = locInts.begin(); I.valid();)
 764     if (I.value().isUndef())
 765       I.erase();
 766     else
 767       ++I;
 768
 769   // The computed intervals may extend beyond the range of the debug
 770   // location's lexical scope. In this case, splitting of an interval
 771   // can result in an interval outside of the scope being created,
 772   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
 773   // this, trim the intervals to the lexical scope.
 774
 775   LexicalScope *Scope = LS.findLexicalScope(dl);
 776   if (!Scope)
 777     return;
 778
 779   SlotIndex PrevEnd;
 780   LocMap::iterator I = locInts.begin();
 781
 782   // Iterate over the lexical scope ranges. Each time round the loop
 783   // we check the intervals for overlap with the end of the previous
 784   // range and the start of the next. The first range is handled as
 785   // a special case where there is no PrevEnd.
 786   for (const InsnRange &Range : Scope->getRanges()) {
 787     SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
 788     SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
 789
 790     // At the start of each iteration I has been advanced so that
 791     // I.stop() >= PrevEnd. Check for overlap.
 792     if (PrevEnd && I.start() < PrevEnd) {
 793       SlotIndex IStop = I.stop();
 794       DbgValueLocation Loc = I.value();
 795
 796       // Stop overlaps previous end - trim the end of the interval to
 797       // the scope range.
 798       I.setStopUnchecked(PrevEnd);
 799       ++I;
 800
 801       // If the interval also overlaps the start of the "next" (i.e.
 802       // current) range create a new interval for the remainder (which
 803       // may be further trimmed).
 804       if (RStart < IStop)
 805         I.insert(RStart, IStop, Loc);
 806     }
 807
 808     // Advance I so that I.stop() >= RStart, and check for overlap.
 809     I.advanceTo(RStart);
 810     if (!I.valid())
 811       return;
 812
 813     if (I.start() < RStart) {
 814       // Interval start overlaps range - trim to the scope range.
 815       I.setStartUnchecked(RStart);
 816       // Remember that this interval was trimmed.
 817       trimmedDefs.insert(RStart);
 818     }
 819
 820     // The end of a lexical scope range is the last instruction in the
 821     // range. To convert to an interval we need the index of the
 822     // instruction after it.
 823     REnd = REnd.getNextIndex();
 824
 825     // Advance I to first interval outside current range.
 826     I.advanceTo(REnd);
 827     if (!I.valid())
 828       return;
 829
 830     PrevEnd = REnd;
 831   }
 832
 833   // Check for overlap with end of final range.
 834   if (PrevEnd && I.start() < PrevEnd)
 835     I.setStopUnchecked(PrevEnd);
 836 }
 837
 838 void LDVImpl::computeIntervals() {
 839   LexicalScopes LS;
 840   LS.initialize(*MF);
 841
 842   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 843     userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
 844     userValues[i]->mapVirtRegs(this);
 845   }
 846 }
 847
 848 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
 849   clear();
 850   MF = &mf;
 851   LIS = &pass.getAnalysis<LiveIntervals>();
 852   TRI = mf.getSubtarget().getRegisterInfo();
 853   DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
 854                << mf.getName() << " **********\n");
 855
 856   bool Changed = collectDebugValues(mf);
 857   computeIntervals();
 858   DEBUG(print(dbgs()));
 859   ModifiedMF = Changed;
 860   return Changed;
 861 }
 862
 863 static void removeDebugValues(MachineFunction &mf) {
 864   for (MachineBasicBlock &MBB : mf) {
 865     for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
 866       if (!MBBI->isDebugValue()) {
 867         ++MBBI;
 868         continue;
 869       }
 870       MBBI = MBB.erase(MBBI);
 871     }
 872   }
 873 }
 874
 875 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
 876   if (!EnableLDV)
 877     return false;
 878   if (!mf.getFunction().getSubprogram()) {
 879     removeDebugValues(mf);
 880     return false;
 881   }
 882   if (!pImpl)
 883     pImpl = new LDVImpl(this);
 884   return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
 885 }
 886
 887 void LiveDebugVariables::releaseMemory() {
 888   if (pImpl)
 889     static_cast<LDVImpl*>(pImpl)->clear();
 890 }
 891
 892 LiveDebugVariables::~LiveDebugVariables() {
 893   if (pImpl)
 894     delete static_cast<LDVImpl*>(pImpl);
 895 }
 896
 897 //===----------------------------------------------------------------------===//
 898 //                           Live Range Splitting
 899 //===----------------------------------------------------------------------===//
 900
 901 bool
 902 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 903                          LiveIntervals& LIS) {
 904   DEBUG({
 905     dbgs() << "Splitting Loc" << OldLocNo << '\t';
 906     print(dbgs(), nullptr);
 907   });
 908   bool DidChange = false;
 909   LocMap::iterator LocMapI;
 910   LocMapI.setMap(locInts);
 911   for (unsigned i = 0; i != NewRegs.size(); ++i) {
 912     LiveInterval *LI = &LIS.getInterval(NewRegs[i]);
 913     if (LI->empty())
 914       continue;
 915
 916     // Don't allocate the new LocNo until it is needed.
 917     unsigned NewLocNo = UndefLocNo;
 918
 919     // Iterate over the overlaps between locInts and LI.
 920     LocMapI.find(LI->beginIndex());
 921     if (!LocMapI.valid())
 922       continue;
 923     LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
 924     LiveInterval::iterator LIE = LI->end();
 925     while (LocMapI.valid() && LII != LIE) {
 926       // At this point, we know that LocMapI.stop() > LII->start.
 927       LII = LI->advanceTo(LII, LocMapI.start());
 928       if (LII == LIE)
 929         break;
 930
 931       // Now LII->end > LocMapI.start(). Do we have an overlap?
 932       if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
 933         // Overlapping correct location. Allocate NewLocNo now.
 934         if (NewLocNo == UndefLocNo) {
 935           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
 936           MO.setSubReg(locations[OldLocNo].getSubReg());
 937           NewLocNo = getLocationNo(MO);
 938           DidChange = true;
 939         }
 940
 941         SlotIndex LStart = LocMapI.start();
 942         SlotIndex LStop  = LocMapI.stop();
 943         DbgValueLocation OldLoc = LocMapI.value();
 944
 945         // Trim LocMapI down to the LII overlap.
 946         if (LStart < LII->start)
 947           LocMapI.setStartUnchecked(LII->start);
 948         if (LStop > LII->end)
 949           LocMapI.setStopUnchecked(LII->end);
 950
 951         // Change the value in the overlap. This may trigger coalescing.
 952         LocMapI.setValue(OldLoc.changeLocNo(NewLocNo));
 953
 954         // Re-insert any removed OldLocNo ranges.
 955         if (LStart < LocMapI.start()) {
 956           LocMapI.insert(LStart, LocMapI.start(), OldLoc);
 957           ++LocMapI;
 958           assert(LocMapI.valid() && "Unexpected coalescing");
 959         }
 960         if (LStop > LocMapI.stop()) {
 961           ++LocMapI;
 962           LocMapI.insert(LII->end, LStop, OldLoc);
 963           --LocMapI;
 964         }
 965       }
 966
 967       // Advance to the next overlap.
 968       if (LII->end < LocMapI.stop()) {
 969         if (++LII == LIE)
 970           break;
 971         LocMapI.advanceTo(LII->start);
 972       } else {
 973         ++LocMapI;
 974         if (!LocMapI.valid())
 975           break;
 976         LII = LI->advanceTo(LII, LocMapI.start());
 977       }
 978     }
 979   }
 980
 981   // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
 982   locations.erase(locations.begin() + OldLocNo);
 983   LocMapI.goToBegin();
 984   while (LocMapI.valid()) {
 985     DbgValueLocation v = LocMapI.value();
 986     if (v.locNo() == OldLocNo) {
 987       DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
 988                    << LocMapI.stop() << ")\n");
 989       LocMapI.erase();
 990     } else {
 991       if (v.locNo() > OldLocNo)
 992         LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
 993       ++LocMapI;
 994     }
 995   }
 996
 997   DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);});
 998   return DidChange;
 999 }
1000
1001 bool
1002 UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
1003                          LiveIntervals &LIS) {
1004   bool DidChange = false;
1005   // Split locations referring to OldReg. Iterate backwards so splitLocation can
1006   // safely erase unused locations.
1007   for (unsigned i = locations.size(); i ; --i) {
1008     unsigned LocNo = i-1;
1009     const MachineOperand *Loc = &locations[LocNo];
1010     if (!Loc->isReg() || Loc->getReg() != OldReg)
1011       continue;
1012     DidChange |= splitLocation(LocNo, NewRegs, LIS);
1013   }
1014   return DidChange;
1015 }
1016
1017 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
1018   bool DidChange = false;
1019   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
1020     DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
1021
1022   if (!DidChange)
1023     return;
1024
1025   // Map all of the new virtual registers.
1026   UserValue *UV = lookupVirtReg(OldReg);
1027   for (unsigned i = 0; i != NewRegs.size(); ++i)
1028     mapVirtReg(NewRegs[i], UV);
1029 }
1030
1031 void LiveDebugVariables::
1032 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
1033   if (pImpl)
1034     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
1035 }
1036
1037 void UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI,
1038                                  BitVector &SpilledLocations) {
1039   // Build a set of new locations with new numbers so we can coalesce our
1040   // IntervalMap if two vreg intervals collapse to the same physical location.
1041   // Use MapVector instead of SetVector because MapVector::insert returns the
1042   // position of the previously or newly inserted element. The boolean value
1043   // tracks if the location was produced by a spill.
1044   // FIXME: This will be problematic if we ever support direct and indirect
1045   // frame index locations, i.e. expressing both variables in memory and
1046   // 'int x, *px = &x'. The "spilled" bit must become part of the location.
1047   MapVector<MachineOperand, bool> NewLocations;
1048   SmallVector<unsigned, 4> LocNoMap(locations.size());
1049   for (unsigned I = 0, E = locations.size(); I != E; ++I) {
1050     bool Spilled = false;
1051     MachineOperand Loc = locations[I];
1052     // Only virtual registers are rewritten.
1053     if (Loc.isReg() && Loc.getReg() &&
1054         TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
1055       unsigned VirtReg = Loc.getReg();
1056       if (VRM.isAssignedReg(VirtReg) &&
1057           TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
1058         // This can create a %noreg operand in rare cases when the sub-register
1059         // index is no longer available. That means the user value is in a
1060         // non-existent sub-register, and %noreg is exactly what we want.
1061         Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
1062       } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
1063         // FIXME: Translate SubIdx to a stackslot offset.
1064         Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
1065         Spilled = true;
1066       } else {
1067         Loc.setReg(0);
1068         Loc.setSubReg(0);
1069       }
1070     }
1071
1072     // Insert this location if it doesn't already exist and record a mapping
1073     // from the old number to the new number.
1074     auto InsertResult = NewLocations.insert({Loc, Spilled});
1075     unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first);
1076     LocNoMap[I] = NewLocNo;
1077   }
1078
1079   // Rewrite the locations and record which ones were spill slots.
1080   locations.clear();
1081   SpilledLocations.clear();
1082   SpilledLocations.resize(NewLocations.size());
1083   for (auto &Pair : NewLocations) {
1084     locations.push_back(Pair.first);
1085     if (Pair.second) {
1086       unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair);
1087       SpilledLocations.set(NewLocNo);
1088     }
1089   }
1090
1091   // Update the interval map, but only coalesce left, since intervals to the
1092   // right use the old location numbers. This should merge two contiguous
1093   // DBG_VALUE intervals with different vregs that were allocated to the same
1094   // physical register.
1095   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
1096     DbgValueLocation Loc = I.value();
1097     unsigned NewLocNo = LocNoMap[Loc.locNo()];
1098     I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
1099     I.setStart(I.start());
1100   }
1101 }
1102
1103 /// Find an iterator for inserting a DBG_VALUE instruction.
1104 static MachineBasicBlock::iterator
1105 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
1106                    LiveIntervals &LIS) {
1107   SlotIndex Start = LIS.getMBBStartIdx(MBB);
1108   Idx = Idx.getBaseIndex();
1109
1110   // Try to find an insert location by going backwards from Idx.
1111   MachineInstr *MI;
1112   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
1113     // We've reached the beginning of MBB.
1114     if (Idx == Start) {
1115       MachineBasicBlock::iterator I = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
1116       return I;
1117     }
1118     Idx = Idx.getPrevIndex();
1119   }
1120
1121   // Don't insert anything after the first terminator, though.
1122   return MI->isTerminator() ? MBB->getFirstTerminator() :
1123                               std::next(MachineBasicBlock::iterator(MI));
1124 }
1125
1126 /// Find an iterator for inserting the next DBG_VALUE instruction
1127 /// (or end if no more insert locations found).
1128 static MachineBasicBlock::iterator
1129 findNextInsertLocation(MachineBasicBlock *MBB,
1130                        MachineBasicBlock::iterator I,
1131                        SlotIndex StopIdx, MachineOperand &LocMO,
1132                        LiveIntervals &LIS,
1133                        const TargetRegisterInfo &TRI) {
1134   if (!LocMO.isReg())
1135     return MBB->instr_end();
1136   unsigned Reg = LocMO.getReg();
1137
1138   // Find the next instruction in the MBB that define the register Reg.
1139   while (I != MBB->end()) {
1140     if (!LIS.isNotInMIMap(*I) &&
1141         SlotIndex::isEarlierEqualInstr(StopIdx, LIS.getInstructionIndex(*I)))
1142       break;
1143     if (I->definesRegister(Reg, &TRI))
1144       // The insert location is directly after the instruction/bundle.
1145       return std::next(I);
1146     ++I;
1147   }
1148   return MBB->end();
1149 }
1150
1151 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
1152                                  SlotIndex StopIdx,
1153                                  DbgValueLocation Loc, bool Spilled,
1154                                  LiveIntervals &LIS,
1155                                  const TargetInstrInfo &TII,
1156                                  const TargetRegisterInfo &TRI) {
1157   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
1158   // Only search within the current MBB.
1159   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
1160   MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
1161   MachineOperand &MO = locations[Loc.locNo()];
1162   ++NumInsertedDebugValues;
1163
1164   assert(cast<DILocalVariable>(Variable)
1165              ->isValidLocationForIntrinsic(getDebugLoc()) &&
1166          "Expected inlined-at fields to agree");
1167
1168   // If the location was spilled, the new DBG_VALUE will be indirect. If the
1169   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
1170   // that the original virtual register was a pointer.
1171   const DIExpression *Expr = Expression;
1172   bool IsIndirect = Loc.wasIndirect();
1173   if (Spilled) {
1174     if (IsIndirect)
1175       Expr = DIExpression::prepend(Expr, DIExpression::WithDeref);
1176     IsIndirect = true;
1177   }
1178
1179   assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
1180
1181   do {
1182     MachineInstrBuilder MIB =
1183       BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
1184           .add(MO);
1185     if (IsIndirect)
1186       MIB.addImm(0U);
1187     else
1188       MIB.addReg(0U, RegState::Debug);
1189     MIB.addMetadata(Variable).addMetadata(Expr);
1190
1191     // Continue and insert DBG_VALUES after every redefinition of register
1192     // associated with the debug value within the range
1193     I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
1194   } while (I != MBB->end());
1195 }
1196
1197 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
1198                                 const TargetInstrInfo &TII,
1199                                 const TargetRegisterInfo &TRI,
1200                                 const BitVector &SpilledLocations) {
1201   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
1202
1203   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
1204     SlotIndex Start = I.start();
1205     SlotIndex Stop = I.stop();
1206     DbgValueLocation Loc = I.value();
1207     bool Spilled = !Loc.isUndef() ? SpilledLocations.test(Loc.locNo()) : false;
1208
1209     // If the interval start was trimmed to the lexical scope insert the
1210     // DBG_VALUE at the previous index (otherwise it appears after the
1211     // first instruction in the range).
1212     if (trimmedDefs.count(Start))
1213       Start = Start.getPrevIndex();
1214
1215     DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
1216     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1217     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
1218
1219     DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1220     insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, LIS, TII, TRI);
1221     // This interval may span multiple basic blocks.
1222     // Insert a DBG_VALUE into each one.
1223     while (Stop > MBBEnd) {
1224       // Move to the next block.
1225       Start = MBBEnd;
1226       if (++MBB == MFEnd)
1227         break;
1228       MBBEnd = LIS.getMBBEndIdx(&*MBB);
1229       DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1230       insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, LIS, TII, TRI);
1231     }
1232     DEBUG(dbgs() << '\n');
1233     if (MBB == MFEnd)
1234       break;
1235
1236     ++I;
1237   }
1238 }
1239
1240 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1241   DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1242   if (!MF)
1243     return;
1244   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1245   BitVector SpilledLocations;
1246   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
1247     DEBUG(userValues[i]->print(dbgs(), TRI));
1248     userValues[i]->rewriteLocations(*VRM, *TRI, SpilledLocations);
1249     userValues[i]->emitDebugValues(VRM, *LIS, *TII, *TRI, SpilledLocations);
1250   }
1251   EmitDone = true;
1252 }
1253
1254 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
1255   if (pImpl)
1256     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1257 }
1258
1259 bool LiveDebugVariables::doInitialization(Module &M) {
1260   return Pass::doInitialization(M);
1261 }
1262
1263 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1264 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
1265   if (pImpl)
1266     static_cast<LDVImpl*>(pImpl)->print(dbgs());
1267 }
1268 #endif