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