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 #define DEBUG_TYPE "livedebug"
  23 #include "LiveDebugVariables.h"
  24 #include "VirtRegMap.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/Metadata.h"
  27 #include "llvm/Value.h"
  28 #include "llvm/ADT/IntervalMap.h"
  29 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  30 #include "llvm/CodeGen/MachineDominators.h"
  31 #include "llvm/CodeGen/MachineFunction.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/Passes.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Target/TargetInstrInfo.h"
  37 #include "llvm/Target/TargetMachine.h"
  38 #include "llvm/Target/TargetRegisterInfo.h"
  39
  40 using namespace llvm;
  41
  42 static cl::opt<bool>
  43 EnableLDV("live-debug-variables",
  44           cl::desc("Enable the live debug variables pass"), cl::Hidden);
  45
  46 char LiveDebugVariables::ID = 0;
  47
  48 INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars",
  49                 "Debug Variable Analysis", false, false)
  50 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  51 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  52 INITIALIZE_PASS_END(LiveDebugVariables, "livedebugvars",
  53                 "Debug Variable Analysis", false, false)
  54
  55 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
  56   AU.addRequired<MachineDominatorTree>();
  57   AU.addRequiredTransitive<LiveIntervals>();
  58   AU.setPreservesAll();
  59   MachineFunctionPass::getAnalysisUsage(AU);
  60 }
  61
  62 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(0) {
  63   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
  64 }
  65
  66 /// Location - All the different places a user value can reside.
  67 /// Note that this includes immediate values that technically aren't locations.
  68 namespace {
  69 struct Location {
  70   /// kind - What kind of location is this?
  71   enum Kind {
  72     locUndef = 0,
  73     locImm   = 0x80000000,
  74     locFPImm
  75   };
  76   /// Kind - One of the following:
  77   /// 1. locUndef
  78   /// 2. Register number (physical or virtual), data.SubIdx is the subreg index.
  79   /// 3. ~Frame index, data.Offset is the offset.
  80   /// 4. locImm, data.ImmVal is the constant integer value.
  81   /// 5. locFPImm, data.CFP points to the floating point constant.
  82   unsigned Kind;
  83
  84   /// Data - Extra data about location.
  85   union {
  86     unsigned SubIdx;          ///< For virtual registers.
  87     int64_t Offset;           ///< For frame indices.
  88     int64_t ImmVal;           ///< For locImm.
  89     const ConstantFP *CFP;    ///< For locFPImm.
  90   } Data;
  91
  92   Location(const MachineOperand &MO) {
  93     switch(MO.getType()) {
  94     case MachineOperand::MO_Register:
  95       Kind = MO.getReg();
  96       Data.SubIdx = MO.getSubReg();
  97       return;
  98     case MachineOperand::MO_Immediate:
  99       Kind = locImm;
 100       Data.ImmVal = MO.getImm();
 101       return;
 102     case MachineOperand::MO_FPImmediate:
 103       Kind = locFPImm;
 104       Data.CFP = MO.getFPImm();
 105       return;
 106     case MachineOperand::MO_FrameIndex:
 107       Kind = ~MO.getIndex();
 108       // FIXME: MO_FrameIndex should support an offset.
 109       Data.Offset = 0;
 110       return;
 111     default:
 112       Kind = locUndef;
 113       return;
 114     }
 115   }
 116
 117   /// addOperand - Add this location as a machine operand to MI.
 118   MachineInstrBuilder addOperand(MachineInstrBuilder MI) const {
 119     switch (Kind) {
 120     case locImm:
 121       return MI.addImm(Data.ImmVal);
 122     case locFPImm:
 123       return MI.addFPImm(Data.CFP);
 124     default:
 125       if (isFrameIndex())
 126         return MI.addFrameIndex(getFrameIndex());
 127       else
 128         return MI.addReg(Kind);  // reg and undef.
 129     }
 130   }
 131
 132   bool operator==(const Location &RHS) const {
 133     if (Kind != RHS.Kind)
 134       return false;
 135     switch (Kind) {
 136     case locUndef:
 137       return true;
 138     case locImm:
 139       return Data.ImmVal == RHS.Data.ImmVal;
 140     case locFPImm:
 141       return Data.CFP == RHS.Data.CFP;
 142     default:
 143       if (isReg())
 144         return Data.SubIdx == RHS.Data.SubIdx;
 145       else
 146          return Data.Offset == RHS.Data.Offset;
 147     }
 148   }
 149
 150   /// isUndef - is this the singleton undef?
 151   bool isUndef() const { return Kind == locUndef; }
 152
 153   /// isReg - is this a register location?
 154   bool isReg() const { return Kind && Kind < locImm; }
 155
 156   /// isFrameIndex - is this a frame index location?
 157   bool isFrameIndex() const { return Kind > locFPImm; }
 158
 159   int getFrameIndex() const { return ~Kind; }
 160
 161   void print(raw_ostream&, const TargetRegisterInfo*);
 162 };
 163 }
 164
 165 /// LocMap - Map of where a user value is live, and its location.
 166 typedef IntervalMap<SlotIndex, unsigned, 4> LocMap;
 167
 168 /// UserValue - A user value is a part of a debug info user variable.
 169 ///
 170 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
 171 /// holds part of a user variable. The part is identified by a byte offset.
 172 ///
 173 /// UserValues are grouped into equivalence classes for easier searching. Two
 174 /// user values are related if they refer to the same variable, or if they are
 175 /// held by the same virtual register. The equivalence class is the transitive
 176 /// closure of that relation.
 177 namespace {
 178 class UserValue {
 179   const MDNode *variable; ///< The debug info variable we are part of.
 180   unsigned offset;        ///< Byte offset into variable.
 181
 182   UserValue *leader;      ///< Equivalence class leader.
 183   UserValue *next;        ///< Next value in equivalence class, or null.
 184
 185   /// Numbered locations referenced by locmap.
 186   SmallVector<Location, 4> locations;
 187
 188   /// Map of slot indices where this value is live.
 189   LocMap locInts;
 190
 191   /// coalesceLocation - After LocNo was changed, check if it has become
 192   /// identical to another location, and coalesce them. This may cause LocNo or
 193   /// a later location to be erased, but no earlier location will be erased.
 194   void coalesceLocation(unsigned LocNo);
 195
 196   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
 197   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
 198                         LiveIntervals &LIS, const TargetInstrInfo &TII);
 199
 200   /// insertDebugKill - Insert an undef DBG_VALUE into MBB at Idx.
 201   void insertDebugKill(MachineBasicBlock *MBB, SlotIndex Idx,
 202                        LiveIntervals &LIS, const TargetInstrInfo &TII);
 203
 204 public:
 205   /// UserValue - Create a new UserValue.
 206   UserValue(const MDNode *var, unsigned o, LocMap::Allocator &alloc)
 207     : variable(var), offset(o), leader(this), next(0), locInts(alloc)
 208   {}
 209
 210   /// getLeader - Get the leader of this value's equivalence class.
 211   UserValue *getLeader() {
 212     UserValue *l = leader;
 213     while (l != l->leader)
 214       l = l->leader;
 215     return leader = l;
 216   }
 217
 218   /// getNext - Return the next UserValue in the equivalence class.
 219   UserValue *getNext() const { return next; }
 220
 221   /// match - Does this UserValue match the aprameters?
 222   bool match(const MDNode *Var, unsigned Offset) const {
 223     return Var == variable && Offset == offset;
 224   }
 225
 226   /// merge - Merge equivalence classes.
 227   static UserValue *merge(UserValue *L1, UserValue *L2) {
 228     L2 = L2->getLeader();
 229     if (!L1)
 230       return L2;
 231     L1 = L1->getLeader();
 232     if (L1 == L2)
 233       return L1;
 234     // Splice L2 before L1's members.
 235     UserValue *End = L2;
 236     while (End->next)
 237       End->leader = L1, End = End->next;
 238     End->leader = L1;
 239     End->next = L1->next;
 240     L1->next = L2;
 241     return L1;
 242   }
 243
 244   /// getLocationNo - Return the location number that matches Loc.
 245   unsigned getLocationNo(Location Loc) {
 246     if (Loc.isUndef())
 247       return ~0u;
 248     unsigned n = std::find(locations.begin(), locations.end(), Loc) -
 249                  locations.begin();
 250     if (n == locations.size())
 251       locations.push_back(Loc);
 252     return n;
 253   }
 254
 255   /// addDef - Add a definition point to this value.
 256   void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
 257     // Add a singular (Idx,Idx) -> Loc mapping.
 258     LocMap::iterator I = locInts.find(Idx);
 259     if (!I.valid() || I.start() != Idx)
 260       I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO));
 261   }
 262
 263   /// extendDef - Extend the current definition as far as possible down the
 264   /// dominator tree. Stop when meeting an existing def or when leaving the live
 265   /// range of VNI.
 266   /// @param Idx   Starting point for the definition.
 267   /// @param LocNo Location number to propagate.
 268   /// @param LI    Restrict liveness to where LI has the value VNI. May be null.
 269   /// @param VNI   When LI is not null, this is the value to restrict to.
 270   /// @param LIS   Live intervals analysis.
 271   /// @param MDT   Dominator tree.
 272   void extendDef(SlotIndex Idx, unsigned LocNo,
 273                  LiveInterval *LI, const VNInfo *VNI,
 274                  LiveIntervals &LIS, MachineDominatorTree &MDT);
 275
 276   /// computeIntervals - Compute the live intervals of all locations after
 277   /// collecting all their def points.
 278   void computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT);
 279
 280   /// renameRegister - Update locations to rewrite OldReg as NewReg:SubIdx.
 281   void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
 282                       const TargetRegisterInfo *TRI);
 283
 284   /// rewriteLocations - Rewrite virtual register locations according to the
 285   /// provided virtual register map.
 286   void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI);
 287
 288   /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
 289   void emitDebugValues(VirtRegMap *VRM,
 290                        LiveIntervals &LIS, const TargetInstrInfo &TRI);
 291
 292   void print(raw_ostream&, const TargetRegisterInfo*);
 293 };
 294 } // namespace
 295
 296 /// LDVImpl - Implementation of the LiveDebugVariables pass.
 297 namespace {
 298 class LDVImpl {
 299   LiveDebugVariables &pass;
 300   LocMap::Allocator allocator;
 301   MachineFunction *MF;
 302   LiveIntervals *LIS;
 303   MachineDominatorTree *MDT;
 304   const TargetRegisterInfo *TRI;
 305
 306   /// userValues - All allocated UserValue instances.
 307   SmallVector<UserValue*, 8> userValues;
 308
 309   /// Map virtual register to eq class leader.
 310   typedef DenseMap<unsigned, UserValue*> VRMap;
 311   VRMap virtRegToEqClass;
 312
 313   /// Map user variable to eq class leader.
 314   typedef DenseMap<const MDNode *, UserValue*> UVMap;
 315   UVMap userVarMap;
 316
 317   /// getUserValue - Find or create a UserValue.
 318   UserValue *getUserValue(const MDNode *Var, unsigned Offset);
 319
 320   /// lookupVirtReg - Find the EC leader for VirtReg or null.
 321   UserValue *lookupVirtReg(unsigned VirtReg);
 322
 323   /// mapVirtReg - Map virtual register to an equivalence class.
 324   void mapVirtReg(unsigned VirtReg, UserValue *EC);
 325
 326   /// handleDebugValue - Add DBG_VALUE instruction to our maps.
 327   /// @param MI  DBG_VALUE instruction
 328   /// @param Idx Last valid SLotIndex before instruction.
 329   /// @return    True if the DBG_VALUE instruction should be deleted.
 330   bool handleDebugValue(MachineInstr *MI, SlotIndex Idx);
 331
 332   /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
 333   /// a UserValue def for each instruction.
 334   /// @param mf MachineFunction to be scanned.
 335   /// @return True if any debug values were found.
 336   bool collectDebugValues(MachineFunction &mf);
 337
 338   /// computeIntervals - Compute the live intervals of all user values after
 339   /// collecting all their def points.
 340   void computeIntervals();
 341
 342 public:
 343   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 344   bool runOnMachineFunction(MachineFunction &mf);
 345
 346   /// clear - Relase all memory.
 347   void clear() {
 348     DeleteContainerPointers(userValues);
 349     userValues.clear();
 350     virtRegToEqClass.clear();
 351     userVarMap.clear();
 352   }
 353
 354   /// renameRegister - Replace all references to OldReg wiht NewReg:SubIdx.
 355   void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx);
 356
 357   /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
 358   void emitDebugValues(VirtRegMap *VRM);
 359
 360   void print(raw_ostream&);
 361 };
 362 } // namespace
 363
 364 void Location::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
 365   switch (Kind) {
 366   case locUndef:
 367     OS << "undef";
 368     return;
 369   case locImm:
 370     OS << "int:" << Data.ImmVal;
 371     return;
 372   case locFPImm:
 373     OS << "fp:" << Data.CFP->getValueAPF().convertToDouble();
 374     return;
 375   default:
 376     if (isReg()) {
 377       if (TargetRegisterInfo::isVirtualRegister(Kind)) {
 378         OS << "%reg" << Kind;
 379         if (Data.SubIdx)
 380           OS << ':' << TRI->getSubRegIndexName(Data.SubIdx);
 381       } else
 382         OS << '%' << TRI->getName(Kind);
 383     } else {
 384       OS << "fi#" << ~Kind;
 385       if (Data.Offset)
 386         OS << '+' << Data.Offset;
 387     }
 388     return;
 389   }
 390 }
 391
 392 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) {
 393   if (const MDString *MDS = dyn_cast<MDString>(variable->getOperand(2)))
 394     OS << "!\"" << MDS->getString() << "\"\t";
 395   if (offset)
 396     OS << '+' << offset;
 397   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
 398     OS << " [" << I.start() << ';' << I.stop() << "):";
 399     if (I.value() == ~0u)
 400       OS << "undef";
 401     else
 402       OS << I.value();
 403   }
 404   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
 405     OS << " Loc" << i << '=';
 406     locations[i].print(OS, TRI);
 407   }
 408   OS << '\n';
 409 }
 410
 411 void LDVImpl::print(raw_ostream &OS) {
 412   OS << "********** DEBUG VARIABLES **********\n";
 413   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
 414     userValues[i]->print(OS, TRI);
 415 }
 416
 417 void UserValue::coalesceLocation(unsigned LocNo) {
 418   unsigned KeepLoc = std::find(locations.begin(), locations.begin() + LocNo,
 419                                locations[LocNo]) - locations.begin();
 420   unsigned EraseLoc = LocNo;
 421   if (KeepLoc == LocNo) {
 422     EraseLoc = std::find(locations.begin() + LocNo + 1, locations.end(),
 423                          locations[LocNo]) - locations.begin();
 424     // No matches.
 425     if (EraseLoc == locations.size())
 426       return;
 427   }
 428   assert(KeepLoc < EraseLoc);
 429   locations.erase(locations.begin() + EraseLoc);
 430
 431   // Rewrite values.
 432   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
 433     unsigned v = I.value();
 434     if (v == EraseLoc)
 435       I.setValue(KeepLoc);      // Coalesce when possible.
 436     else if (v > EraseLoc)
 437       I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values.
 438   }
 439 }
 440
 441 UserValue *LDVImpl::getUserValue(const MDNode *Var, unsigned Offset) {
 442   UserValue *&Leader = userVarMap[Var];
 443   if (Leader) {
 444     UserValue *UV = Leader->getLeader();
 445     Leader = UV;
 446     for (; UV; UV = UV->getNext())
 447       if (UV->match(Var, Offset))
 448         return UV;
 449   }
 450
 451   UserValue *UV = new UserValue(Var, Offset, allocator);
 452   userValues.push_back(UV);
 453   Leader = UserValue::merge(Leader, UV);
 454   return UV;
 455 }
 456
 457 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
 458   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
 459   UserValue *&Leader = virtRegToEqClass[VirtReg];
 460   Leader = UserValue::merge(Leader, EC);
 461 }
 462
 463 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
 464   if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
 465     return UV->getLeader();
 466   return 0;
 467 }
 468
 469 bool LDVImpl::handleDebugValue(MachineInstr *MI, SlotIndex Idx) {
 470   // DBG_VALUE loc, offset, variable
 471   if (MI->getNumOperands() != 3 ||
 472       !MI->getOperand(1).isImm() || !MI->getOperand(2).isMetadata()) {
 473     DEBUG(dbgs() << "Can't handle " << *MI);
 474     return false;
 475   }
 476
 477   // Get or create the UserValue for (variable,offset).
 478   unsigned Offset = MI->getOperand(1).getImm();
 479   const MDNode *Var = MI->getOperand(2).getMetadata();
 480   UserValue *UV = getUserValue(Var, Offset);
 481
 482   // If the location is a virtual register, make sure it is mapped.
 483   if (MI->getOperand(0).isReg()) {
 484     unsigned Reg = MI->getOperand(0).getReg();
 485     if (Reg && TargetRegisterInfo::isVirtualRegister(Reg))
 486       mapVirtReg(Reg, UV);
 487   }
 488
 489   UV->addDef(Idx, MI->getOperand(0));
 490   return true;
 491 }
 492
 493 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
 494   bool Changed = false;
 495   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
 496        ++MFI) {
 497     MachineBasicBlock *MBB = MFI;
 498     for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
 499          MBBI != MBBE;) {
 500       if (!MBBI->isDebugValue()) {
 501         ++MBBI;
 502         continue;
 503       }
 504       // DBG_VALUE has no slot index, use the previous instruction instead.
 505       SlotIndex Idx = MBBI == MBB->begin() ?
 506         LIS->getMBBStartIdx(MBB) :
 507         LIS->getInstructionIndex(llvm::prior(MBBI)).getDefIndex();
 508       // Handle consecutive DBG_VALUE instructions with the same slot index.
 509       do {
 510         if (handleDebugValue(MBBI, Idx)) {
 511           MBBI = MBB->erase(MBBI);
 512           Changed = true;
 513         } else
 514           ++MBBI;
 515       } while (MBBI != MBBE && MBBI->isDebugValue());
 516     }
 517   }
 518   return Changed;
 519 }
 520
 521 void UserValue::extendDef(SlotIndex Idx, unsigned LocNo,
 522                           LiveInterval *LI, const VNInfo *VNI,
 523                           LiveIntervals &LIS, MachineDominatorTree &MDT) {
 524   SmallVector<SlotIndex, 16> Todo;
 525   Todo.push_back(Idx);
 526
 527   do {
 528     SlotIndex Start = Todo.pop_back_val();
 529     MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
 530     SlotIndex Stop = LIS.getMBBEndIdx(MBB);
 531     LocMap::iterator I = locInts.find(Idx);
 532
 533     // Limit to VNI's live range.
 534     bool ToEnd = true;
 535     if (LI && VNI) {
 536       LiveRange *Range = LI->getLiveRangeContaining(Start);
 537       if (!Range || Range->valno != VNI)
 538         continue;
 539       if (Range->end < Stop)
 540         Stop = Range->end, ToEnd = false;
 541     }
 542
 543     // There could already be a short def at Start.
 544     if (I.valid() && I.start() <= Start) {
 545       // Stop when meeting a different location or an already extended interval.
 546       Start = Start.getNextSlot();
 547       if (I.value() != LocNo || I.stop() != Start)
 548         continue;
 549       // This is a one-slot placeholder. Just skip it.
 550       ++I;
 551     }
 552
 553     // Limited by the next def.
 554     if (I.valid() && I.start() < Stop)
 555       Stop = I.start(), ToEnd = false;
 556
 557     if (Start >= Stop)
 558       continue;
 559
 560     I.insert(Start, Stop, LocNo);
 561
 562     // If we extended to the MBB end, propagate down the dominator tree.
 563     if (!ToEnd)
 564       continue;
 565     const std::vector<MachineDomTreeNode*> &Children =
 566       MDT.getNode(MBB)->getChildren();
 567     for (unsigned i = 0, e = Children.size(); i != e; ++i)
 568       Todo.push_back(LIS.getMBBStartIdx(Children[i]->getBlock()));
 569   } while (!Todo.empty());
 570 }
 571
 572 void
 573 UserValue::computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT) {
 574   SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
 575
 576   // Collect all defs to be extended (Skipping undefs).
 577   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
 578     if (I.value() != ~0u)
 579       Defs.push_back(std::make_pair(I.start(), I.value()));
 580
 581   for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
 582     SlotIndex Idx = Defs[i].first;
 583     unsigned LocNo = Defs[i].second;
 584     const Location &Loc = locations[LocNo];
 585
 586     // Register locations are constrained to where the register value is live.
 587     if (Loc.isReg() && LIS.hasInterval(Loc.Kind)) {
 588       LiveInterval *LI = &LIS.getInterval(Loc.Kind);
 589       const VNInfo *VNI = LI->getVNInfoAt(Idx);
 590       extendDef(Idx, LocNo, LI, VNI, LIS, MDT);
 591     } else
 592       extendDef(Idx, LocNo, 0, 0, LIS, MDT);
 593   }
 594
 595   // Finally, erase all the undefs.
 596   for (LocMap::iterator I = locInts.begin(); I.valid();)
 597     if (I.value() == ~0u)
 598       I.erase();
 599     else
 600       ++I;
 601 }
 602
 603 void LDVImpl::computeIntervals() {
 604   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
 605     userValues[i]->computeIntervals(*LIS, *MDT);
 606 }
 607
 608 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
 609   MF = &mf;
 610   LIS = &pass.getAnalysis<LiveIntervals>();
 611   MDT = &pass.getAnalysis<MachineDominatorTree>();
 612   TRI = mf.getTarget().getRegisterInfo();
 613   clear();
 614   DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
 615                << ((Value*)mf.getFunction())->getName()
 616                << " **********\n");
 617
 618   bool Changed = collectDebugValues(mf);
 619   computeIntervals();
 620   DEBUG(print(dbgs()));
 621   return Changed;
 622 }
 623
 624 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
 625   if (!EnableLDV)
 626     return false;
 627   if (!pImpl)
 628     pImpl = new LDVImpl(this);
 629   return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
 630 }
 631
 632 void LiveDebugVariables::releaseMemory() {
 633   if (pImpl)
 634     static_cast<LDVImpl*>(pImpl)->clear();
 635 }
 636
 637 LiveDebugVariables::~LiveDebugVariables() {
 638   if (pImpl)
 639     delete static_cast<LDVImpl*>(pImpl);
 640 }
 641
 642 void UserValue::
 643 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
 644                const TargetRegisterInfo *TRI) {
 645   for (unsigned i = locations.size(); i; --i) {
 646     unsigned LocNo = i - 1;
 647     Location &Loc = locations[LocNo];
 648     if (Loc.Kind != OldReg)
 649       continue;
 650     Loc.Kind = NewReg;
 651     if (SubIdx && Loc.Data.SubIdx)
 652       Loc.Data.SubIdx = TRI->composeSubRegIndices(SubIdx, Loc.Data.SubIdx);
 653     coalesceLocation(LocNo);
 654   }
 655 }
 656
 657 void LDVImpl::
 658 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
 659   UserValue *UV = lookupVirtReg(OldReg);
 660   if (!UV)
 661     return;
 662
 663   if (TargetRegisterInfo::isVirtualRegister(NewReg))
 664     mapVirtReg(NewReg, UV);
 665   virtRegToEqClass.erase(OldReg);
 666
 667   do {
 668     UV->renameRegister(OldReg, NewReg, SubIdx, TRI);
 669     UV = UV->getNext();
 670   } while (UV);
 671 }
 672
 673 void LiveDebugVariables::
 674 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
 675   if (pImpl)
 676     static_cast<LDVImpl*>(pImpl)->renameRegister(OldReg, NewReg, SubIdx);
 677 }
 678
 679 void
 680 UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) {
 681   // Iterate over locations in reverse makes it easier to handle coalescing.
 682   for (unsigned i = locations.size(); i ; --i) {
 683     unsigned LocNo = i-1;
 684     Location &Loc = locations[LocNo];
 685     // Only virtual registers are rewritten.
 686     if (!Loc.isReg() || !TargetRegisterInfo::isVirtualRegister(Loc.Kind))
 687       continue;
 688     unsigned VirtReg = Loc.Kind;
 689     if (VRM.isAssignedReg(VirtReg)) {
 690       unsigned PhysReg = VRM.getPhys(VirtReg);
 691       if (Loc.Data.SubIdx)
 692         PhysReg = TRI.getSubReg(PhysReg, Loc.Data.SubIdx);
 693       Loc.Kind = PhysReg;
 694       Loc.Data.SubIdx = 0;
 695     } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) {
 696       Loc.Kind = ~VRM.getStackSlot(VirtReg);
 697       // FIXME: Translate SubIdx to a stackslot offset.
 698       Loc.Data.Offset = 0;
 699     } else {
 700       Loc.Kind = Location::locUndef;
 701     }
 702     coalesceLocation(LocNo);
 703   }
 704   DEBUG(print(dbgs(), &TRI));
 705 }
 706
 707 /// findInsertLocation - Find an iterator and DebugLoc for inserting a DBG_VALUE
 708 /// instruction.
 709 static MachineBasicBlock::iterator
 710 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, DebugLoc &DL,
 711                    LiveIntervals &LIS) {
 712   SlotIndex Start = LIS.getMBBStartIdx(MBB);
 713   Idx = Idx.getBaseIndex();
 714
 715   // Try to find an insert location by going backwards from Idx.
 716   MachineInstr *MI;
 717   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
 718     // We've reached the beginning of MBB.
 719     if (Idx == Start) {
 720       MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin());
 721       if (I != MBB->end())
 722         DL = I->getDebugLoc();
 723       return I;
 724     }
 725     Idx = Idx.getPrevIndex();
 726   }
 727   // We found an instruction. The insert point is after the instr.
 728   DL = MI->getDebugLoc();
 729   return llvm::next(MachineBasicBlock::iterator(MI));
 730 }
 731
 732 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
 733                                  unsigned LocNo,
 734                                  LiveIntervals &LIS,
 735                                  const TargetInstrInfo &TII) {
 736   DebugLoc DL;
 737   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, DL, LIS);
 738   Location &Loc = locations[LocNo];
 739
 740   // Frame index locations may require a target callback.
 741   if (Loc.isFrameIndex()) {
 742     MachineInstr *MI = TII.emitFrameIndexDebugValue(*MBB->getParent(),
 743                                           Loc.getFrameIndex(),
 744                                           offset, variable, DL);
 745     if (MI) {
 746       MBB->insert(I, MI);
 747       return;
 748     }
 749   }
 750   // This is not a frame index, or the target is happy with a standard FI.
 751   Loc.addOperand(BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE)))
 752     .addImm(offset).addMetadata(variable);
 753 }
 754
 755 void UserValue::insertDebugKill(MachineBasicBlock *MBB, SlotIndex Idx,
 756                                LiveIntervals &LIS, const TargetInstrInfo &TII) {
 757   DebugLoc DL;
 758   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, DL, LIS);
 759   BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE)).addReg(0)
 760     .addImm(offset).addMetadata(variable);
 761 }
 762
 763 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
 764                                 const TargetInstrInfo &TII) {
 765   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 766
 767   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
 768     SlotIndex Start = I.start();
 769     SlotIndex Stop = I.stop();
 770     unsigned LocNo = I.value();
 771     DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
 772     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
 773     SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
 774
 775     DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
 776     insertDebugValue(MBB, Start, LocNo, LIS, TII);
 777
 778     // This interval may span multiple basic blocks.
 779     // Insert a DBG_VALUE into each one.
 780     while(Stop > MBBEnd) {
 781       // Move to the next block.
 782       Start = MBBEnd;
 783       if (++MBB == MFEnd)
 784         break;
 785       MBBEnd = LIS.getMBBEndIdx(MBB);
 786       DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
 787       insertDebugValue(MBB, Start, LocNo, LIS, TII);
 788     }
 789     DEBUG(dbgs() << '\n');
 790     if (MBB == MFEnd)
 791       break;
 792
 793     ++I;
 794     if (Stop == MBBEnd)
 795       continue;
 796     // The current interval ends before MBB.
 797     // Insert a kill if there is a gap.
 798     if (!I.valid() || I.start() > Stop)
 799       insertDebugKill(MBB, Stop, LIS, TII);
 800   }
 801 }
 802
 803 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
 804   DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
 805   const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
 806   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 807     userValues[i]->rewriteLocations(*VRM, *TRI);
 808     userValues[i]->emitDebugValues(VRM, *LIS, *TII);
 809   }
 810 }
 811
 812 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
 813   if (pImpl)
 814     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
 815 }
 816
 817
 818 #ifndef NDEBUG
 819 void LiveDebugVariables::dump() {
 820   if (pImpl)
 821     static_cast<LDVImpl*>(pImpl)->print(dbgs());
 822 }
 823 #endif
 824