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   // Get or create the UserValue for (variable,offset) here.
 518   bool IsIndirect = MI.getOperand(1).isImm();
 519   if (IsIndirect)
 520     assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
 521   const DILocalVariable *Var = MI.getDebugVariable();
 522   const DIExpression *Expr = MI.getDebugExpression();
 523   UserValue *UV =
 524       getUserValue(Var, Expr, MI.getDebugLoc());
 525   UV->addDef(Idx, MI.getOperand(0), IsIndirect);
 526   return true;
 527 }
 528
 529 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
 530   bool Changed = false;
 531   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
 532        ++MFI) {
 533     MachineBasicBlock *MBB = &*MFI;
 534     for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
 535          MBBI != MBBE;) {
 536       if (!MBBI->isDebugValue()) {
 537         ++MBBI;
 538         continue;
 539       }
 540       // DBG_VALUE has no slot index, use the previous instruction instead.
 541       SlotIndex Idx =
 542           MBBI == MBB->begin()
 543               ? LIS->getMBBStartIdx(MBB)
 544               : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
 545       // Handle consecutive DBG_VALUE instructions with the same slot index.
 546       do {
 547         if (handleDebugValue(*MBBI, Idx)) {
 548           MBBI = MBB->erase(MBBI);
 549           Changed = true;
 550         } else
 551           ++MBBI;
 552       } while (MBBI != MBBE && MBBI->isDebugValue());
 553     }
 554   }
 555   return Changed;
 556 }
 557
 558 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a
 559 /// data-flow analysis to propagate them beyond basic block boundaries.
 560 void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR,
 561                           const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills,
 562                           LiveIntervals &LIS) {
 563   SlotIndex Start = Idx;
 564   MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
 565   SlotIndex Stop = LIS.getMBBEndIdx(MBB);
 566   LocMap::iterator I = locInts.find(Start);
 567
 568   // Limit to VNI's live range.
 569   bool ToEnd = true;
 570   if (LR && VNI) {
 571     LiveInterval::Segment *Segment = LR->getSegmentContaining(Start);
 572     if (!Segment || Segment->valno != VNI) {
 573       if (Kills)
 574         Kills->push_back(Start);
 575       return;
 576     }
 577     if (Segment->end < Stop) {
 578       Stop = Segment->end;
 579       ToEnd = false;
 580     }
 581   }
 582
 583   // There could already be a short def at Start.
 584   if (I.valid() && I.start() <= Start) {
 585     // Stop when meeting a different location or an already extended interval.
 586     Start = Start.getNextSlot();
 587     if (I.value() != Loc || I.stop() != Start)
 588       return;
 589     // This is a one-slot placeholder. Just skip it.
 590     ++I;
 591   }
 592
 593   // Limited by the next def.
 594   if (I.valid() && I.start() < Stop) {
 595     Stop = I.start();
 596     ToEnd = false;
 597   }
 598   // Limited by VNI's live range.
 599   else if (!ToEnd && Kills)
 600     Kills->push_back(Stop);
 601
 602   if (Start < Stop)
 603     I.insert(Start, Stop, Loc);
 604 }
 605
 606 void UserValue::addDefsFromCopies(
 607     LiveInterval *LI, unsigned LocNo, bool WasIndirect,
 608     const SmallVectorImpl<SlotIndex> &Kills,
 609     SmallVectorImpl<std::pair<SlotIndex, DbgValueLocation>> &NewDefs,
 610     MachineRegisterInfo &MRI, LiveIntervals &LIS) {
 611   if (Kills.empty())
 612     return;
 613   // Don't track copies from physregs, there are too many uses.
 614   if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
 615     return;
 616
 617   // Collect all the (vreg, valno) pairs that are copies of LI.
 618   SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
 619   for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) {
 620     MachineInstr *MI = MO.getParent();
 621     // Copies of the full value.
 622     if (MO.getSubReg() || !MI->isCopy())
 623       continue;
 624     unsigned DstReg = MI->getOperand(0).getReg();
 625
 626     // Don't follow copies to physregs. These are usually setting up call
 627     // arguments, and the argument registers are always call clobbered. We are
 628     // better off in the source register which could be a callee-saved register,
 629     // or it could be spilled.
 630     if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 631       continue;
 632
 633     // Is LocNo extended to reach this copy? If not, another def may be blocking
 634     // it, or we are looking at a wrong value of LI.
 635     SlotIndex Idx = LIS.getInstructionIndex(*MI);
 636     LocMap::iterator I = locInts.find(Idx.getRegSlot(true));
 637     if (!I.valid() || I.value().locNo() != LocNo)
 638       continue;
 639
 640     if (!LIS.hasInterval(DstReg))
 641       continue;
 642     LiveInterval *DstLI = &LIS.getInterval(DstReg);
 643     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot());
 644     assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value");
 645     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
 646   }
 647
 648   if (CopyValues.empty())
 649     return;
 650
 651   DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n');
 652
 653   // Try to add defs of the copied values for each kill point.
 654   for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 655     SlotIndex Idx = Kills[i];
 656     for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
 657       LiveInterval *DstLI = CopyValues[j].first;
 658       const VNInfo *DstVNI = CopyValues[j].second;
 659       if (DstLI->getVNInfoAt(Idx) != DstVNI)
 660         continue;
 661       // Check that there isn't already a def at Idx
 662       LocMap::iterator I = locInts.find(Idx);
 663       if (I.valid() && I.start() <= Idx)
 664         continue;
 665       DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
 666                    << DstVNI->id << " in " << *DstLI << '\n');
 667       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
 668       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
 669       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
 670       DbgValueLocation NewLoc(LocNo, WasIndirect);
 671       I.insert(Idx, Idx.getNextSlot(), NewLoc);
 672       NewDefs.push_back(std::make_pair(Idx, NewLoc));
 673       break;
 674     }
 675   }
 676 }
 677
 678 void UserValue::computeIntervals(MachineRegisterInfo &MRI,
 679                                  const TargetRegisterInfo &TRI,
 680                                  LiveIntervals &LIS, LexicalScopes &LS) {
 681   SmallVector<std::pair<SlotIndex, DbgValueLocation>, 16> Defs;
 682
 683   // Collect all defs to be extended (Skipping undefs).
 684   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
 685     if (!I.value().isUndef())
 686       Defs.push_back(std::make_pair(I.start(), I.value()));
 687
 688   // Extend all defs, and possibly add new ones along the way.
 689   for (unsigned i = 0; i != Defs.size(); ++i) {
 690     SlotIndex Idx = Defs[i].first;
 691     DbgValueLocation Loc = Defs[i].second;
 692     const MachineOperand &LocMO = locations[Loc.locNo()];
 693
 694     if (!LocMO.isReg()) {
 695       extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS);
 696       continue;
 697     }
 698
 699     // Register locations are constrained to where the register value is live.
 700     if (TargetRegisterInfo::isVirtualRegister(LocMO.getReg())) {
 701       LiveInterval *LI = nullptr;
 702       const VNInfo *VNI = nullptr;
 703       if (LIS.hasInterval(LocMO.getReg())) {
 704         LI = &LIS.getInterval(LocMO.getReg());
 705         VNI = LI->getVNInfoAt(Idx);
 706       }
 707       SmallVector<SlotIndex, 16> Kills;
 708       extendDef(Idx, Loc, LI, VNI, &Kills, LIS);
 709       if (LI)
 710         addDefsFromCopies(LI, Loc.locNo(), Loc.wasIndirect(), Kills, Defs, MRI,
 711                           LIS);
 712       continue;
 713     }
 714
 715     // For physregs, we only mark the start slot idx. DwarfDebug will see it
 716     // as if the DBG_VALUE is valid up until the end of the basic block, or
 717     // the next def of the physical register. So we do not need to extend the
 718     // range. It might actually happen that the DBG_VALUE is the last use of
 719     // the physical register (e.g. if this is an unused input argument to a
 720     // function).
 721   }
 722
 723   // Erase all the undefs.
 724   for (LocMap::iterator I = locInts.begin(); I.valid();)
 725     if (I.value().isUndef())
 726       I.erase();
 727     else
 728       ++I;
 729
 730   // The computed intervals may extend beyond the range of the debug
 731   // location's lexical scope. In this case, splitting of an interval
 732   // can result in an interval outside of the scope being created,
 733   // causing extra unnecessary DBG_VALUEs to be emitted. To prevent
 734   // this, trim the intervals to the lexical scope.
 735
 736   LexicalScope *Scope = LS.findLexicalScope(dl);
 737   if (!Scope)
 738     return;
 739
 740   SlotIndex PrevEnd;
 741   LocMap::iterator I = locInts.begin();
 742
 743   // Iterate over the lexical scope ranges. Each time round the loop
 744   // we check the intervals for overlap with the end of the previous
 745   // range and the start of the next. The first range is handled as
 746   // a special case where there is no PrevEnd.
 747   for (const InsnRange &Range : Scope->getRanges()) {
 748     SlotIndex RStart = LIS.getInstructionIndex(*Range.first);
 749     SlotIndex REnd = LIS.getInstructionIndex(*Range.second);
 750
 751     // At the start of each iteration I has been advanced so that
 752     // I.stop() >= PrevEnd. Check for overlap.
 753     if (PrevEnd && I.start() < PrevEnd) {
 754       SlotIndex IStop = I.stop();
 755       DbgValueLocation Loc = I.value();
 756
 757       // Stop overlaps previous end - trim the end of the interval to
 758       // the scope range.
 759       I.setStopUnchecked(PrevEnd);
 760       ++I;
 761
 762       // If the interval also overlaps the start of the "next" (i.e.
 763       // current) range create a new interval for the remainder (which
 764       // may be further trimmed).
 765       if (RStart < IStop)
 766         I.insert(RStart, IStop, Loc);
 767     }
 768
 769     // Advance I so that I.stop() >= RStart, and check for overlap.
 770     I.advanceTo(RStart);
 771     if (!I.valid())
 772       return;
 773
 774     if (I.start() < RStart) {
 775       // Interval start overlaps range - trim to the scope range.
 776       I.setStartUnchecked(RStart);
 777       // Remember that this interval was trimmed.
 778       trimmedDefs.insert(RStart);
 779     }
 780
 781     // The end of a lexical scope range is the last instruction in the
 782     // range. To convert to an interval we need the index of the
 783     // instruction after it.
 784     REnd = REnd.getNextIndex();
 785
 786     // Advance I to first interval outside current range.
 787     I.advanceTo(REnd);
 788     if (!I.valid())
 789       return;
 790
 791     PrevEnd = REnd;
 792   }
 793
 794   // Check for overlap with end of final range.
 795   if (PrevEnd && I.start() < PrevEnd)
 796     I.setStopUnchecked(PrevEnd);
 797 }
 798
 799 void LDVImpl::computeIntervals() {
 800   LexicalScopes LS;
 801   LS.initialize(*MF);
 802
 803   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 804     userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS);
 805     userValues[i]->mapVirtRegs(this);
 806   }
 807 }
 808
 809 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
 810   clear();
 811   MF = &mf;
 812   LIS = &pass.getAnalysis<LiveIntervals>();
 813   TRI = mf.getSubtarget().getRegisterInfo();
 814   DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
 815                << mf.getName() << " **********\n");
 816
 817   bool Changed = collectDebugValues(mf);
 818   computeIntervals();
 819   DEBUG(print(dbgs()));
 820   ModifiedMF = Changed;
 821   return Changed;
 822 }
 823
 824 static void removeDebugValues(MachineFunction &mf) {
 825   for (MachineBasicBlock &MBB : mf) {
 826     for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
 827       if (!MBBI->isDebugValue()) {
 828         ++MBBI;
 829         continue;
 830       }
 831       MBBI = MBB.erase(MBBI);
 832     }
 833   }
 834 }
 835
 836 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
 837   if (!EnableLDV)
 838     return false;
 839   if (!mf.getFunction().getSubprogram()) {
 840     removeDebugValues(mf);
 841     return false;
 842   }
 843   if (!pImpl)
 844     pImpl = new LDVImpl(this);
 845   return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
 846 }
 847
 848 void LiveDebugVariables::releaseMemory() {
 849   if (pImpl)
 850     static_cast<LDVImpl*>(pImpl)->clear();
 851 }
 852
 853 LiveDebugVariables::~LiveDebugVariables() {
 854   if (pImpl)
 855     delete static_cast<LDVImpl*>(pImpl);
 856 }
 857
 858 //===----------------------------------------------------------------------===//
 859 //                           Live Range Splitting
 860 //===----------------------------------------------------------------------===//
 861
 862 bool
 863 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
 864                          LiveIntervals& LIS) {
 865   DEBUG({
 866     dbgs() << "Splitting Loc" << OldLocNo << '\t';
 867     print(dbgs(), nullptr);
 868   });
 869   bool DidChange = false;
 870   LocMap::iterator LocMapI;
 871   LocMapI.setMap(locInts);
 872   for (unsigned i = 0; i != NewRegs.size(); ++i) {
 873     LiveInterval *LI = &LIS.getInterval(NewRegs[i]);
 874     if (LI->empty())
 875       continue;
 876
 877     // Don't allocate the new LocNo until it is needed.
 878     unsigned NewLocNo = UndefLocNo;
 879
 880     // Iterate over the overlaps between locInts and LI.
 881     LocMapI.find(LI->beginIndex());
 882     if (!LocMapI.valid())
 883       continue;
 884     LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
 885     LiveInterval::iterator LIE = LI->end();
 886     while (LocMapI.valid() && LII != LIE) {
 887       // At this point, we know that LocMapI.stop() > LII->start.
 888       LII = LI->advanceTo(LII, LocMapI.start());
 889       if (LII == LIE)
 890         break;
 891
 892       // Now LII->end > LocMapI.start(). Do we have an overlap?
 893       if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) {
 894         // Overlapping correct location. Allocate NewLocNo now.
 895         if (NewLocNo == UndefLocNo) {
 896           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
 897           MO.setSubReg(locations[OldLocNo].getSubReg());
 898           NewLocNo = getLocationNo(MO);
 899           DidChange = true;
 900         }
 901
 902         SlotIndex LStart = LocMapI.start();
 903         SlotIndex LStop  = LocMapI.stop();
 904         DbgValueLocation OldLoc = LocMapI.value();
 905
 906         // Trim LocMapI down to the LII overlap.
 907         if (LStart < LII->start)
 908           LocMapI.setStartUnchecked(LII->start);
 909         if (LStop > LII->end)
 910           LocMapI.setStopUnchecked(LII->end);
 911
 912         // Change the value in the overlap. This may trigger coalescing.
 913         LocMapI.setValue(OldLoc.changeLocNo(NewLocNo));
 914
 915         // Re-insert any removed OldLocNo ranges.
 916         if (LStart < LocMapI.start()) {
 917           LocMapI.insert(LStart, LocMapI.start(), OldLoc);
 918           ++LocMapI;
 919           assert(LocMapI.valid() && "Unexpected coalescing");
 920         }
 921         if (LStop > LocMapI.stop()) {
 922           ++LocMapI;
 923           LocMapI.insert(LII->end, LStop, OldLoc);
 924           --LocMapI;
 925         }
 926       }
 927
 928       // Advance to the next overlap.
 929       if (LII->end < LocMapI.stop()) {
 930         if (++LII == LIE)
 931           break;
 932         LocMapI.advanceTo(LII->start);
 933       } else {
 934         ++LocMapI;
 935         if (!LocMapI.valid())
 936           break;
 937         LII = LI->advanceTo(LII, LocMapI.start());
 938       }
 939     }
 940   }
 941
 942   // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
 943   locations.erase(locations.begin() + OldLocNo);
 944   LocMapI.goToBegin();
 945   while (LocMapI.valid()) {
 946     DbgValueLocation v = LocMapI.value();
 947     if (v.locNo() == OldLocNo) {
 948       DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
 949                    << LocMapI.stop() << ")\n");
 950       LocMapI.erase();
 951     } else {
 952       if (v.locNo() > OldLocNo)
 953         LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
 954       ++LocMapI;
 955     }
 956   }
 957
 958   DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);});
 959   return DidChange;
 960 }
 961
 962 bool
 963 UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
 964                          LiveIntervals &LIS) {
 965   bool DidChange = false;
 966   // Split locations referring to OldReg. Iterate backwards so splitLocation can
 967   // safely erase unused locations.
 968   for (unsigned i = locations.size(); i ; --i) {
 969     unsigned LocNo = i-1;
 970     const MachineOperand *Loc = &locations[LocNo];
 971     if (!Loc->isReg() || Loc->getReg() != OldReg)
 972       continue;
 973     DidChange |= splitLocation(LocNo, NewRegs, LIS);
 974   }
 975   return DidChange;
 976 }
 977
 978 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
 979   bool DidChange = false;
 980   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
 981     DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
 982
 983   if (!DidChange)
 984     return;
 985
 986   // Map all of the new virtual registers.
 987   UserValue *UV = lookupVirtReg(OldReg);
 988   for (unsigned i = 0; i != NewRegs.size(); ++i)
 989     mapVirtReg(NewRegs[i], UV);
 990 }
 991
 992 void LiveDebugVariables::
 993 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) {
 994   if (pImpl)
 995     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
 996 }
 997
 998 void UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI,
 999                                  BitVector &SpilledLocations) {
1000   // Build a set of new locations with new numbers so we can coalesce our
1001   // IntervalMap if two vreg intervals collapse to the same physical location.
1002   // Use MapVector instead of SetVector because MapVector::insert returns the
1003   // position of the previously or newly inserted element. The boolean value
1004   // tracks if the location was produced by a spill.
1005   // FIXME: This will be problematic if we ever support direct and indirect
1006   // frame index locations, i.e. expressing both variables in memory and
1007   // 'int x, *px = &x'. The "spilled" bit must become part of the location.
1008   MapVector<MachineOperand, bool> NewLocations;
1009   SmallVector<unsigned, 4> LocNoMap(locations.size());
1010   for (unsigned I = 0, E = locations.size(); I != E; ++I) {
1011     bool Spilled = false;
1012     MachineOperand Loc = locations[I];
1013     // Only virtual registers are rewritten.
1014     if (Loc.isReg() && Loc.getReg() &&
1015         TargetRegisterInfo::isVirtualRegister(Loc.getReg())) {
1016       unsigned VirtReg = Loc.getReg();
1017       if (VRM.isAssignedReg(VirtReg) &&
1018           TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
1019         // This can create a %noreg operand in rare cases when the sub-register
1020         // index is no longer available. That means the user value is in a
1021         // non-existent sub-register, and %noreg is exactly what we want.
1022         Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
1023       } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
1024         // FIXME: Translate SubIdx to a stackslot offset.
1025         Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
1026         Spilled = true;
1027       } else {
1028         Loc.setReg(0);
1029         Loc.setSubReg(0);
1030       }
1031     }
1032
1033     // Insert this location if it doesn't already exist and record a mapping
1034     // from the old number to the new number.
1035     auto InsertResult = NewLocations.insert({Loc, Spilled});
1036     unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first);
1037     LocNoMap[I] = NewLocNo;
1038   }
1039
1040   // Rewrite the locations and record which ones were spill slots.
1041   locations.clear();
1042   SpilledLocations.clear();
1043   SpilledLocations.resize(NewLocations.size());
1044   for (auto &Pair : NewLocations) {
1045     locations.push_back(Pair.first);
1046     if (Pair.second) {
1047       unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair);
1048       SpilledLocations.set(NewLocNo);
1049     }
1050   }
1051
1052   // Update the interval map, but only coalesce left, since intervals to the
1053   // right use the old location numbers. This should merge two contiguous
1054   // DBG_VALUE intervals with different vregs that were allocated to the same
1055   // physical register.
1056   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
1057     DbgValueLocation Loc = I.value();
1058     unsigned NewLocNo = LocNoMap[Loc.locNo()];
1059     I.setValueUnchecked(Loc.changeLocNo(NewLocNo));
1060     I.setStart(I.start());
1061   }
1062 }
1063
1064 /// Find an iterator for inserting a DBG_VALUE instruction.
1065 static MachineBasicBlock::iterator
1066 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
1067                    LiveIntervals &LIS) {
1068   SlotIndex Start = LIS.getMBBStartIdx(MBB);
1069   Idx = Idx.getBaseIndex();
1070
1071   // Try to find an insert location by going backwards from Idx.
1072   MachineInstr *MI;
1073   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
1074     // We've reached the beginning of MBB.
1075     if (Idx == Start) {
1076       MachineBasicBlock::iterator I = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
1077       return I;
1078     }
1079     Idx = Idx.getPrevIndex();
1080   }
1081
1082   // Don't insert anything after the first terminator, though.
1083   return MI->isTerminator() ? MBB->getFirstTerminator() :
1084                               std::next(MachineBasicBlock::iterator(MI));
1085 }
1086
1087 /// Find an iterator for inserting the next DBG_VALUE instruction
1088 /// (or end if no more insert locations found).
1089 static MachineBasicBlock::iterator
1090 findNextInsertLocation(MachineBasicBlock *MBB,
1091                        MachineBasicBlock::iterator I,
1092                        SlotIndex StopIdx, MachineOperand &LocMO,
1093                        LiveIntervals &LIS,
1094                        const TargetRegisterInfo &TRI) {
1095   if (!LocMO.isReg())
1096     return MBB->instr_end();
1097   unsigned Reg = LocMO.getReg();
1098
1099   // Find the next instruction in the MBB that define the register Reg.
1100   while (I != MBB->end()) {
1101     if (!LIS.isNotInMIMap(*I) &&
1102         SlotIndex::isEarlierEqualInstr(StopIdx, LIS.getInstructionIndex(*I)))
1103       break;
1104     if (I->definesRegister(Reg, &TRI))
1105       // The insert location is directly after the instruction/bundle.
1106       return std::next(I);
1107     ++I;
1108   }
1109   return MBB->end();
1110 }
1111
1112 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx,
1113                                  SlotIndex StopIdx,
1114                                  DbgValueLocation Loc, bool Spilled,
1115                                  LiveIntervals &LIS,
1116                                  const TargetInstrInfo &TII,
1117                                  const TargetRegisterInfo &TRI) {
1118   SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB);
1119   // Only search within the current MBB.
1120   StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx;
1121   MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS);
1122   MachineOperand &MO = locations[Loc.locNo()];
1123   ++NumInsertedDebugValues;
1124
1125   assert(cast<DILocalVariable>(Variable)
1126              ->isValidLocationForIntrinsic(getDebugLoc()) &&
1127          "Expected inlined-at fields to agree");
1128
1129   // If the location was spilled, the new DBG_VALUE will be indirect. If the
1130   // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate
1131   // that the original virtual register was a pointer.
1132   const DIExpression *Expr = Expression;
1133   bool IsIndirect = Loc.wasIndirect();
1134   if (Spilled) {
1135     if (IsIndirect)
1136       Expr = DIExpression::prepend(Expr, DIExpression::WithDeref);
1137     IsIndirect = true;
1138   }
1139
1140   assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index");
1141
1142   do {
1143     MachineInstrBuilder MIB =
1144       BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
1145           .add(MO);
1146     if (IsIndirect)
1147       MIB.addImm(0U);
1148     else
1149       MIB.addReg(0U, RegState::Debug);
1150     MIB.addMetadata(Variable).addMetadata(Expr);
1151
1152     // Continue and insert DBG_VALUES after every redefinition of register
1153     // associated with the debug value within the range
1154     I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI);
1155   } while (I != MBB->end());
1156 }
1157
1158 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
1159                                 const TargetInstrInfo &TII,
1160                                 const TargetRegisterInfo &TRI,
1161                                 const BitVector &SpilledLocations) {
1162   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
1163
1164   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
1165     SlotIndex Start = I.start();
1166     SlotIndex Stop = I.stop();
1167     DbgValueLocation Loc = I.value();
1168     bool Spilled = !Loc.isUndef() ? SpilledLocations.test(Loc.locNo()) : false;
1169
1170     // If the interval start was trimmed to the lexical scope insert the
1171     // DBG_VALUE at the previous index (otherwise it appears after the
1172     // first instruction in the range).
1173     if (trimmedDefs.count(Start))
1174       Start = Start.getPrevIndex();
1175
1176     DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo());
1177     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator();
1178     SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB);
1179
1180     DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1181     insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, LIS, TII, TRI);
1182     // This interval may span multiple basic blocks.
1183     // Insert a DBG_VALUE into each one.
1184     while (Stop > MBBEnd) {
1185       // Move to the next block.
1186       Start = MBBEnd;
1187       if (++MBB == MFEnd)
1188         break;
1189       MBBEnd = LIS.getMBBEndIdx(&*MBB);
1190       DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd);
1191       insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, LIS, TII, TRI);
1192     }
1193     DEBUG(dbgs() << '\n');
1194     if (MBB == MFEnd)
1195       break;
1196
1197     ++I;
1198   }
1199 }
1200
1201 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
1202   DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
1203   if (!MF)
1204     return;
1205   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1206   BitVector SpilledLocations;
1207   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
1208     DEBUG(userValues[i]->print(dbgs(), TRI));
1209     userValues[i]->rewriteLocations(*VRM, *TRI, SpilledLocations);
1210     userValues[i]->emitDebugValues(VRM, *LIS, *TII, *TRI, SpilledLocations);
1211   }
1212   EmitDone = true;
1213 }
1214
1215 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
1216   if (pImpl)
1217     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
1218 }
1219
1220 bool LiveDebugVariables::doInitialization(Module &M) {
1221   return Pass::doInitialization(M);
1222 }
1223
1224 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1225 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
1226   if (pImpl)
1227     static_cast<LDVImpl*>(pImpl)->print(dbgs());
1228 }
1229 #endif