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/Analysis/DebugInfo.h"
  29 #include "llvm/ADT/IntervalMap.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  32 #include "llvm/CodeGen/MachineDominators.h"
  33 #include "llvm/CodeGen/MachineFunction.h"
  34 #include "llvm/CodeGen/MachineInstrBuilder.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/Passes.h"
  37 #include "llvm/Support/CommandLine.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Target/TargetInstrInfo.h"
  40 #include "llvm/Target/TargetMachine.h"
  41 #include "llvm/Target/TargetRegisterInfo.h"
  42
  43 using namespace llvm;
  44
  45 static cl::opt<bool>
  46 EnableLDV("live-debug-variables", cl::init(true),
  47           cl::desc("Enable the live debug variables pass"), cl::Hidden);
  48
  49 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted");
  50 char LiveDebugVariables::ID = 0;
  51
  52 INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars",
  53                 "Debug Variable Analysis", false, false)
  54 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  55 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
  56 INITIALIZE_PASS_END(LiveDebugVariables, "livedebugvars",
  57                 "Debug Variable Analysis", false, false)
  58
  59 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const {
  60   AU.addRequired<MachineDominatorTree>();
  61   AU.addRequiredTransitive<LiveIntervals>();
  62   AU.setPreservesAll();
  63   MachineFunctionPass::getAnalysisUsage(AU);
  64 }
  65
  66 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(0) {
  67   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
  68 }
  69
  70 /// LocMap - Map of where a user value is live, and its location.
  71 typedef IntervalMap<SlotIndex, unsigned, 4> LocMap;
  72
  73 /// UserValue - A user value is a part of a debug info user variable.
  74 ///
  75 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register
  76 /// holds part of a user variable. The part is identified by a byte offset.
  77 ///
  78 /// UserValues are grouped into equivalence classes for easier searching. Two
  79 /// user values are related if they refer to the same variable, or if they are
  80 /// held by the same virtual register. The equivalence class is the transitive
  81 /// closure of that relation.
  82 namespace {
  83 class LDVImpl;
  84 class UserValue {
  85   const MDNode *variable; ///< The debug info variable we are part of.
  86   unsigned offset;        ///< Byte offset into variable.
  87   DebugLoc dl;            ///< The debug location for the variable. This is
  88                           ///< used by dwarf writer to find lexical scope.
  89   UserValue *leader;      ///< Equivalence class leader.
  90   UserValue *next;        ///< Next value in equivalence class, or null.
  91
  92   /// Numbered locations referenced by locmap.
  93   SmallVector<MachineOperand, 4> locations;
  94
  95   /// Map of slot indices where this value is live.
  96   LocMap locInts;
  97
  98   /// coalesceLocation - After LocNo was changed, check if it has become
  99   /// identical to another location, and coalesce them. This may cause LocNo or
 100   /// a later location to be erased, but no earlier location will be erased.
 101   void coalesceLocation(unsigned LocNo);
 102
 103   /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo.
 104   void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo,
 105                         LiveIntervals &LIS, const TargetInstrInfo &TII);
 106
 107   /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs
 108   /// is live. Returns true if any changes were made.
 109   bool splitLocation(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs);
 110
 111 public:
 112   /// UserValue - Create a new UserValue.
 113   UserValue(const MDNode *var, unsigned o, DebugLoc L,
 114             LocMap::Allocator &alloc)
 115     : variable(var), offset(o), dl(L), leader(this), next(0), locInts(alloc)
 116   {}
 117
 118   /// getLeader - Get the leader of this value's equivalence class.
 119   UserValue *getLeader() {
 120     UserValue *l = leader;
 121     while (l != l->leader)
 122       l = l->leader;
 123     return leader = l;
 124   }
 125
 126   /// getNext - Return the next UserValue in the equivalence class.
 127   UserValue *getNext() const { return next; }
 128
 129   /// match - Does this UserValue match the parameters?
 130   bool match(const MDNode *Var, unsigned Offset) const {
 131     return Var == variable && Offset == offset;
 132   }
 133
 134   /// merge - Merge equivalence classes.
 135   static UserValue *merge(UserValue *L1, UserValue *L2) {
 136     L2 = L2->getLeader();
 137     if (!L1)
 138       return L2;
 139     L1 = L1->getLeader();
 140     if (L1 == L2)
 141       return L1;
 142     // Splice L2 before L1's members.
 143     UserValue *End = L2;
 144     while (End->next)
 145       End->leader = L1, End = End->next;
 146     End->leader = L1;
 147     End->next = L1->next;
 148     L1->next = L2;
 149     return L1;
 150   }
 151
 152   /// getLocationNo - Return the location number that matches Loc.
 153   unsigned getLocationNo(const MachineOperand &LocMO) {
 154     if (LocMO.isReg()) {
 155       if (LocMO.getReg() == 0)
 156         return ~0u;
 157       // For register locations we dont care about use/def and other flags.
 158       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 159         if (locations[i].isReg() &&
 160             locations[i].getReg() == LocMO.getReg() &&
 161             locations[i].getSubReg() == LocMO.getSubReg())
 162           return i;
 163     } else
 164       for (unsigned i = 0, e = locations.size(); i != e; ++i)
 165         if (LocMO.isIdenticalTo(locations[i]))
 166           return i;
 167     locations.push_back(LocMO);
 168     // We are storing a MachineOperand outside a MachineInstr.
 169     locations.back().clearParent();
 170     // Don't store def operands.
 171     if (locations.back().isReg())
 172       locations.back().setIsUse();
 173     return locations.size() - 1;
 174   }
 175
 176   /// mapVirtRegs - Ensure that all virtual register locations are mapped.
 177   void mapVirtRegs(LDVImpl *LDV);
 178
 179   /// addDef - Add a definition point to this value.
 180   void addDef(SlotIndex Idx, const MachineOperand &LocMO) {
 181     // Add a singular (Idx,Idx) -> Loc mapping.
 182     LocMap::iterator I = locInts.find(Idx);
 183     if (!I.valid() || I.start() != Idx)
 184       I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO));
 185     else
 186       // A later DBG_VALUE at the same SlotIndex overrides the old location.
 187       I.setValue(getLocationNo(LocMO));
 188   }
 189
 190   /// extendDef - Extend the current definition as far as possible down the
 191   /// dominator tree. Stop when meeting an existing def or when leaving the live
 192   /// range of VNI.
 193   /// End points where VNI is no longer live are added to Kills.
 194   /// @param Idx   Starting point for the definition.
 195   /// @param LocNo Location number to propagate.
 196   /// @param LI    Restrict liveness to where LI has the value VNI. May be null.
 197   /// @param VNI   When LI is not null, this is the value to restrict to.
 198   /// @param Kills Append end points of VNI's live range to Kills.
 199   /// @param LIS   Live intervals analysis.
 200   /// @param MDT   Dominator tree.
 201   void extendDef(SlotIndex Idx, unsigned LocNo,
 202                  LiveInterval *LI, const VNInfo *VNI,
 203                  SmallVectorImpl<SlotIndex> *Kills,
 204                  LiveIntervals &LIS, MachineDominatorTree &MDT);
 205
 206   /// addDefsFromCopies - The value in LI/LocNo may be copies to other
 207   /// registers. Determine if any of the copies are available at the kill
 208   /// points, and add defs if possible.
 209   /// @param LI      Scan for copies of the value in LI->reg.
 210   /// @param LocNo   Location number of LI->reg.
 211   /// @param Kills   Points where the range of LocNo could be extended.
 212   /// @param NewDefs Append (Idx, LocNo) of inserted defs here.
 213   void addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
 214                       const SmallVectorImpl<SlotIndex> &Kills,
 215                       SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
 216                       MachineRegisterInfo &MRI,
 217                       LiveIntervals &LIS);
 218
 219   /// computeIntervals - Compute the live intervals of all locations after
 220   /// collecting all their def points.
 221   void computeIntervals(MachineRegisterInfo &MRI,
 222                         LiveIntervals &LIS, MachineDominatorTree &MDT);
 223
 224   /// renameRegister - Update locations to rewrite OldReg as NewReg:SubIdx.
 225   void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
 226                       const TargetRegisterInfo *TRI);
 227
 228   /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is
 229   /// live. Returns true if any changes were made.
 230   bool splitRegister(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs);
 231
 232   /// rewriteLocations - Rewrite virtual register locations according to the
 233   /// provided virtual register map.
 234   void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI);
 235
 236   /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
 237   void emitDebugValues(VirtRegMap *VRM,
 238                        LiveIntervals &LIS, const TargetInstrInfo &TRI);
 239
 240   /// findDebugLoc - Return DebugLoc used for this DBG_VALUE instruction. A
 241   /// variable may have more than one corresponding DBG_VALUE instructions.
 242   /// Only first one needs DebugLoc to identify variable's lexical scope
 243   /// in source file.
 244   DebugLoc findDebugLoc();
 245   void print(raw_ostream&, const TargetMachine*);
 246 };
 247 } // namespace
 248
 249 /// LDVImpl - Implementation of the LiveDebugVariables pass.
 250 namespace {
 251 class LDVImpl {
 252   LiveDebugVariables &pass;
 253   LocMap::Allocator allocator;
 254   MachineFunction *MF;
 255   LiveIntervals *LIS;
 256   MachineDominatorTree *MDT;
 257   const TargetRegisterInfo *TRI;
 258
 259   /// userValues - All allocated UserValue instances.
 260   SmallVector<UserValue*, 8> userValues;
 261
 262   /// Map virtual register to eq class leader.
 263   typedef DenseMap<unsigned, UserValue*> VRMap;
 264   VRMap virtRegToEqClass;
 265
 266   /// Map user variable to eq class leader.
 267   typedef DenseMap<const MDNode *, UserValue*> UVMap;
 268   UVMap userVarMap;
 269
 270   /// getUserValue - Find or create a UserValue.
 271   UserValue *getUserValue(const MDNode *Var, unsigned Offset, DebugLoc DL);
 272
 273   /// lookupVirtReg - Find the EC leader for VirtReg or null.
 274   UserValue *lookupVirtReg(unsigned VirtReg);
 275
 276   /// handleDebugValue - Add DBG_VALUE instruction to our maps.
 277   /// @param MI  DBG_VALUE instruction
 278   /// @param Idx Last valid SLotIndex before instruction.
 279   /// @return    True if the DBG_VALUE instruction should be deleted.
 280   bool handleDebugValue(MachineInstr *MI, SlotIndex Idx);
 281
 282   /// collectDebugValues - Collect and erase all DBG_VALUE instructions, adding
 283   /// a UserValue def for each instruction.
 284   /// @param mf MachineFunction to be scanned.
 285   /// @return True if any debug values were found.
 286   bool collectDebugValues(MachineFunction &mf);
 287
 288   /// computeIntervals - Compute the live intervals of all user values after
 289   /// collecting all their def points.
 290   void computeIntervals();
 291
 292 public:
 293   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 294   bool runOnMachineFunction(MachineFunction &mf);
 295
 296   /// clear - Relase all memory.
 297   void clear() {
 298     DeleteContainerPointers(userValues);
 299     userValues.clear();
 300     virtRegToEqClass.clear();
 301     userVarMap.clear();
 302   }
 303
 304   /// mapVirtReg - Map virtual register to an equivalence class.
 305   void mapVirtReg(unsigned VirtReg, UserValue *EC);
 306
 307   /// renameRegister - Replace all references to OldReg with NewReg:SubIdx.
 308   void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx);
 309
 310   /// splitRegister -  Replace all references to OldReg with NewRegs.
 311   void splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs);
 312
 313   /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures.
 314   void emitDebugValues(VirtRegMap *VRM);
 315
 316   void print(raw_ostream&);
 317 };
 318 } // namespace
 319
 320 void UserValue::print(raw_ostream &OS, const TargetMachine *TM) {
 321   DIVariable DV(variable);
 322   OS << "!\"";
 323   DV.printExtendedName(OS);
 324   OS << "\"\t";
 325   if (offset)
 326     OS << '+' << offset;
 327   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) {
 328     OS << " [" << I.start() << ';' << I.stop() << "):";
 329     if (I.value() == ~0u)
 330       OS << "undef";
 331     else
 332       OS << I.value();
 333   }
 334   for (unsigned i = 0, e = locations.size(); i != e; ++i) {
 335     OS << " Loc" << i << '=';
 336     locations[i].print(OS, TM);
 337   }
 338   OS << '\n';
 339 }
 340
 341 void LDVImpl::print(raw_ostream &OS) {
 342   OS << "********** DEBUG VARIABLES **********\n";
 343   for (unsigned i = 0, e = userValues.size(); i != e; ++i)
 344     userValues[i]->print(OS, &MF->getTarget());
 345 }
 346
 347 void UserValue::coalesceLocation(unsigned LocNo) {
 348   unsigned KeepLoc = 0;
 349   for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) {
 350     if (KeepLoc == LocNo)
 351       continue;
 352     if (locations[KeepLoc].isIdenticalTo(locations[LocNo]))
 353       break;
 354   }
 355   // No matches.
 356   if (KeepLoc == locations.size())
 357     return;
 358
 359   // Keep the smaller location, erase the larger one.
 360   unsigned EraseLoc = LocNo;
 361   if (KeepLoc > EraseLoc)
 362     std::swap(KeepLoc, EraseLoc);
 363   locations.erase(locations.begin() + EraseLoc);
 364
 365   // Rewrite values.
 366   for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) {
 367     unsigned v = I.value();
 368     if (v == EraseLoc)
 369       I.setValue(KeepLoc);      // Coalesce when possible.
 370     else if (v > EraseLoc)
 371       I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values.
 372   }
 373 }
 374
 375 void UserValue::mapVirtRegs(LDVImpl *LDV) {
 376   for (unsigned i = 0, e = locations.size(); i != e; ++i)
 377     if (locations[i].isReg() &&
 378         TargetRegisterInfo::isVirtualRegister(locations[i].getReg()))
 379       LDV->mapVirtReg(locations[i].getReg(), this);
 380 }
 381
 382 UserValue *LDVImpl::getUserValue(const MDNode *Var, unsigned Offset,
 383                                  DebugLoc DL) {
 384   UserValue *&Leader = userVarMap[Var];
 385   if (Leader) {
 386     UserValue *UV = Leader->getLeader();
 387     Leader = UV;
 388     for (; UV; UV = UV->getNext())
 389       if (UV->match(Var, Offset))
 390         return UV;
 391   }
 392
 393   UserValue *UV = new UserValue(Var, Offset, DL, allocator);
 394   userValues.push_back(UV);
 395   Leader = UserValue::merge(Leader, UV);
 396   return UV;
 397 }
 398
 399 void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
 400   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && "Only map VirtRegs");
 401   UserValue *&Leader = virtRegToEqClass[VirtReg];
 402   Leader = UserValue::merge(Leader, EC);
 403 }
 404
 405 UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
 406   if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
 407     return UV->getLeader();
 408   return 0;
 409 }
 410
 411 bool LDVImpl::handleDebugValue(MachineInstr *MI, SlotIndex Idx) {
 412   // DBG_VALUE loc, offset, variable
 413   if (MI->getNumOperands() != 3 ||
 414       !MI->getOperand(1).isImm() || !MI->getOperand(2).isMetadata()) {
 415     DEBUG(dbgs() << "Can't handle " << *MI);
 416     return false;
 417   }
 418
 419   // Get or create the UserValue for (variable,offset).
 420   unsigned Offset = MI->getOperand(1).getImm();
 421   const MDNode *Var = MI->getOperand(2).getMetadata();
 422   UserValue *UV = getUserValue(Var, Offset, MI->getDebugLoc());
 423   UV->addDef(Idx, MI->getOperand(0));
 424   return true;
 425 }
 426
 427 bool LDVImpl::collectDebugValues(MachineFunction &mf) {
 428   bool Changed = false;
 429   for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE;
 430        ++MFI) {
 431     MachineBasicBlock *MBB = MFI;
 432     for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
 433          MBBI != MBBE;) {
 434       if (!MBBI->isDebugValue()) {
 435         ++MBBI;
 436         continue;
 437       }
 438       // DBG_VALUE has no slot index, use the previous instruction instead.
 439       SlotIndex Idx = MBBI == MBB->begin() ?
 440         LIS->getMBBStartIdx(MBB) :
 441         LIS->getInstructionIndex(llvm::prior(MBBI)).getDefIndex();
 442       // Handle consecutive DBG_VALUE instructions with the same slot index.
 443       do {
 444         if (handleDebugValue(MBBI, Idx)) {
 445           MBBI = MBB->erase(MBBI);
 446           Changed = true;
 447         } else
 448           ++MBBI;
 449       } while (MBBI != MBBE && MBBI->isDebugValue());
 450     }
 451   }
 452   return Changed;
 453 }
 454
 455 void UserValue::extendDef(SlotIndex Idx, unsigned LocNo,
 456                           LiveInterval *LI, const VNInfo *VNI,
 457                           SmallVectorImpl<SlotIndex> *Kills,
 458                           LiveIntervals &LIS, MachineDominatorTree &MDT) {
 459   SmallVector<SlotIndex, 16> Todo;
 460   Todo.push_back(Idx);
 461
 462   do {
 463     SlotIndex Start = Todo.pop_back_val();
 464     MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start);
 465     SlotIndex Stop = LIS.getMBBEndIdx(MBB);
 466     LocMap::iterator I = locInts.find(Start);
 467
 468     // Limit to VNI's live range.
 469     bool ToEnd = true;
 470     if (LI && VNI) {
 471       LiveRange *Range = LI->getLiveRangeContaining(Start);
 472       if (!Range || Range->valno != VNI) {
 473         if (Kills)
 474           Kills->push_back(Start);
 475         continue;
 476       }
 477       if (Range->end < Stop)
 478         Stop = Range->end, ToEnd = false;
 479     }
 480
 481     // There could already be a short def at Start.
 482     if (I.valid() && I.start() <= Start) {
 483       // Stop when meeting a different location or an already extended interval.
 484       Start = Start.getNextSlot();
 485       if (I.value() != LocNo || I.stop() != Start)
 486         continue;
 487       // This is a one-slot placeholder. Just skip it.
 488       ++I;
 489     }
 490
 491     // Limited by the next def.
 492     if (I.valid() && I.start() < Stop)
 493       Stop = I.start(), ToEnd = false;
 494     // Limited by VNI's live range.
 495     else if (!ToEnd && Kills)
 496       Kills->push_back(Stop);
 497
 498     if (Start >= Stop)
 499       continue;
 500
 501     I.insert(Start, Stop, LocNo);
 502
 503     // If we extended to the MBB end, propagate down the dominator tree.
 504     if (!ToEnd)
 505       continue;
 506     const std::vector<MachineDomTreeNode*> &Children =
 507       MDT.getNode(MBB)->getChildren();
 508     for (unsigned i = 0, e = Children.size(); i != e; ++i)
 509       Todo.push_back(LIS.getMBBStartIdx(Children[i]->getBlock()));
 510   } while (!Todo.empty());
 511 }
 512
 513 void
 514 UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo,
 515                       const SmallVectorImpl<SlotIndex> &Kills,
 516                       SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs,
 517                       MachineRegisterInfo &MRI, LiveIntervals &LIS) {
 518   if (Kills.empty())
 519     return;
 520   // Don't track copies from physregs, there are too many uses.
 521   if (!TargetRegisterInfo::isVirtualRegister(LI->reg))
 522     return;
 523
 524   // Collect all the (vreg, valno) pairs that are copies of LI.
 525   SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues;
 526   for (MachineRegisterInfo::use_nodbg_iterator
 527          UI = MRI.use_nodbg_begin(LI->reg),
 528          UE = MRI.use_nodbg_end(); UI != UE; ++UI) {
 529     // Copies of the full value.
 530     if (UI.getOperand().getSubReg() || !UI->isCopy())
 531       continue;
 532     MachineInstr *MI = &*UI;
 533     unsigned DstReg = MI->getOperand(0).getReg();
 534
 535     // Don't follow copies to physregs. These are usually setting up call
 536     // arguments, and the argument registers are always call clobbered. We are
 537     // better off in the source register which could be a callee-saved register,
 538     // or it could be spilled.
 539     if (!TargetRegisterInfo::isVirtualRegister(DstReg))
 540       continue;
 541
 542     // Is LocNo extended to reach this copy? If not, another def may be blocking
 543     // it, or we are looking at a wrong value of LI.
 544     SlotIndex Idx = LIS.getInstructionIndex(MI);
 545     LocMap::iterator I = locInts.find(Idx.getUseIndex());
 546     if (!I.valid() || I.value() != LocNo)
 547       continue;
 548
 549     if (!LIS.hasInterval(DstReg))
 550       continue;
 551     LiveInterval *DstLI = &LIS.getInterval(DstReg);
 552     const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getDefIndex());
 553     assert(DstVNI && DstVNI->def == Idx.getDefIndex() && "Bad copy value");
 554     CopyValues.push_back(std::make_pair(DstLI, DstVNI));
 555   }
 556
 557   if (CopyValues.empty())
 558     return;
 559
 560   DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n');
 561
 562   // Try to add defs of the copied values for each kill point.
 563   for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 564     SlotIndex Idx = Kills[i];
 565     for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) {
 566       LiveInterval *DstLI = CopyValues[j].first;
 567       const VNInfo *DstVNI = CopyValues[j].second;
 568       if (DstLI->getVNInfoAt(Idx) != DstVNI)
 569         continue;
 570       // Check that there isn't already a def at Idx
 571       LocMap::iterator I = locInts.find(Idx);
 572       if (I.valid() && I.start() <= Idx)
 573         continue;
 574       DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #"
 575                    << DstVNI->id << " in " << *DstLI << '\n');
 576       MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def);
 577       assert(CopyMI && CopyMI->isCopy() && "Bad copy value");
 578       unsigned LocNo = getLocationNo(CopyMI->getOperand(0));
 579       I.insert(Idx, Idx.getNextSlot(), LocNo);
 580       NewDefs.push_back(std::make_pair(Idx, LocNo));
 581       break;
 582     }
 583   }
 584 }
 585
 586 void
 587 UserValue::computeIntervals(MachineRegisterInfo &MRI,
 588                             LiveIntervals &LIS,
 589                             MachineDominatorTree &MDT) {
 590   SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs;
 591
 592   // Collect all defs to be extended (Skipping undefs).
 593   for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I)
 594     if (I.value() != ~0u)
 595       Defs.push_back(std::make_pair(I.start(), I.value()));
 596
 597   // Extend all defs, and possibly add new ones along the way.
 598   for (unsigned i = 0; i != Defs.size(); ++i) {
 599     SlotIndex Idx = Defs[i].first;
 600     unsigned LocNo = Defs[i].second;
 601     const MachineOperand &Loc = locations[LocNo];
 602
 603     // Register locations are constrained to where the register value is live.
 604     if (Loc.isReg() && LIS.hasInterval(Loc.getReg())) {
 605       LiveInterval *LI = &LIS.getInterval(Loc.getReg());
 606       const VNInfo *VNI = LI->getVNInfoAt(Idx);
 607       SmallVector<SlotIndex, 16> Kills;
 608       extendDef(Idx, LocNo, LI, VNI, &Kills, LIS, MDT);
 609       addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS);
 610     } else
 611       extendDef(Idx, LocNo, 0, 0, 0, LIS, MDT);
 612   }
 613
 614   // Finally, erase all the undefs.
 615   for (LocMap::iterator I = locInts.begin(); I.valid();)
 616     if (I.value() == ~0u)
 617       I.erase();
 618     else
 619       ++I;
 620 }
 621
 622 void LDVImpl::computeIntervals() {
 623   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 624     userValues[i]->computeIntervals(MF->getRegInfo(), *LIS, *MDT);
 625     userValues[i]->mapVirtRegs(this);
 626   }
 627 }
 628
 629 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
 630   MF = &mf;
 631   LIS = &pass.getAnalysis<LiveIntervals>();
 632   MDT = &pass.getAnalysis<MachineDominatorTree>();
 633   TRI = mf.getTarget().getRegisterInfo();
 634   clear();
 635   DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
 636                << ((Value*)mf.getFunction())->getName()
 637                << " **********\n");
 638
 639   bool Changed = collectDebugValues(mf);
 640   computeIntervals();
 641   DEBUG(print(dbgs()));
 642   return Changed;
 643 }
 644
 645 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) {
 646   if (!EnableLDV)
 647     return false;
 648   if (!pImpl)
 649     pImpl = new LDVImpl(this);
 650   return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf);
 651 }
 652
 653 void LiveDebugVariables::releaseMemory() {
 654   if (pImpl)
 655     static_cast<LDVImpl*>(pImpl)->clear();
 656 }
 657
 658 LiveDebugVariables::~LiveDebugVariables() {
 659   if (pImpl)
 660     delete static_cast<LDVImpl*>(pImpl);
 661 }
 662
 663 void UserValue::
 664 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx,
 665                const TargetRegisterInfo *TRI) {
 666   for (unsigned i = locations.size(); i; --i) {
 667     unsigned LocNo = i - 1;
 668     MachineOperand &Loc = locations[LocNo];
 669     if (!Loc.isReg() || Loc.getReg() != OldReg)
 670       continue;
 671     if (TargetRegisterInfo::isPhysicalRegister(NewReg))
 672       Loc.substPhysReg(NewReg, *TRI);
 673     else
 674       Loc.substVirtReg(NewReg, SubIdx, *TRI);
 675     coalesceLocation(LocNo);
 676   }
 677 }
 678
 679 void LDVImpl::
 680 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
 681   UserValue *UV = lookupVirtReg(OldReg);
 682   if (!UV)
 683     return;
 684
 685   if (TargetRegisterInfo::isVirtualRegister(NewReg))
 686     mapVirtReg(NewReg, UV);
 687   virtRegToEqClass.erase(OldReg);
 688
 689   do {
 690     UV->renameRegister(OldReg, NewReg, SubIdx, TRI);
 691     UV = UV->getNext();
 692   } while (UV);
 693 }
 694
 695 void LiveDebugVariables::
 696 renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) {
 697   if (pImpl)
 698     static_cast<LDVImpl*>(pImpl)->renameRegister(OldReg, NewReg, SubIdx);
 699 }
 700
 701 //===----------------------------------------------------------------------===//
 702 //                           Live Range Splitting
 703 //===----------------------------------------------------------------------===//
 704
 705 bool
 706 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<LiveInterval*> NewRegs) {
 707   DEBUG({
 708     dbgs() << "Splitting Loc" << OldLocNo << '\t';
 709     print(dbgs(), 0);
 710   });
 711   bool DidChange = false;
 712   LocMap::iterator LocMapI;
 713   LocMapI.setMap(locInts);
 714   for (unsigned i = 0; i != NewRegs.size(); ++i) {
 715     LiveInterval *LI = NewRegs[i];
 716     if (LI->empty())
 717       continue;
 718
 719     // Don't allocate the new LocNo until it is needed.
 720     unsigned NewLocNo = ~0u;
 721
 722     // Iterate over the overlaps between locInts and LI.
 723     LocMapI.find(LI->beginIndex());
 724     if (!LocMapI.valid())
 725       continue;
 726     LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start());
 727     LiveInterval::iterator LIE = LI->end();
 728     while (LocMapI.valid() && LII != LIE) {
 729       // At this point, we know that LocMapI.stop() > LII->start.
 730       LII = LI->advanceTo(LII, LocMapI.start());
 731       if (LII == LIE)
 732         break;
 733
 734       // Now LII->end > LocMapI.start(). Do we have an overlap?
 735       if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) {
 736         // Overlapping correct location. Allocate NewLocNo now.
 737         if (NewLocNo == ~0u) {
 738           MachineOperand MO = MachineOperand::CreateReg(LI->reg, false);
 739           MO.setSubReg(locations[OldLocNo].getSubReg());
 740           NewLocNo = getLocationNo(MO);
 741           DidChange = true;
 742         }
 743
 744         SlotIndex LStart = LocMapI.start();
 745         SlotIndex LStop  = LocMapI.stop();
 746
 747         // Trim LocMapI down to the LII overlap.
 748         if (LStart < LII->start)
 749           LocMapI.setStartUnchecked(LII->start);
 750         if (LStop > LII->end)
 751           LocMapI.setStopUnchecked(LII->end);
 752
 753         // Change the value in the overlap. This may trigger coalescing.
 754         LocMapI.setValue(NewLocNo);
 755
 756         // Re-insert any removed OldLocNo ranges.
 757         if (LStart < LocMapI.start()) {
 758           LocMapI.insert(LStart, LocMapI.start(), OldLocNo);
 759           ++LocMapI;
 760           assert(LocMapI.valid() && "Unexpected coalescing");
 761         }
 762         if (LStop > LocMapI.stop()) {
 763           ++LocMapI;
 764           LocMapI.insert(LII->end, LStop, OldLocNo);
 765           --LocMapI;
 766         }
 767       }
 768
 769       // Advance to the next overlap.
 770       if (LII->end < LocMapI.stop()) {
 771         if (++LII == LIE)
 772           break;
 773         LocMapI.advanceTo(LII->start);
 774       } else {
 775         ++LocMapI;
 776         if (!LocMapI.valid())
 777           break;
 778         LII = LI->advanceTo(LII, LocMapI.start());
 779       }
 780     }
 781   }
 782
 783   // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
 784   locations.erase(locations.begin() + OldLocNo);
 785   LocMapI.goToBegin();
 786   while (LocMapI.valid()) {
 787     unsigned v = LocMapI.value();
 788     if (v == OldLocNo) {
 789       DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
 790                    << LocMapI.stop() << ")\n");
 791       LocMapI.erase();
 792     } else {
 793       if (v > OldLocNo)
 794         LocMapI.setValueUnchecked(v-1);
 795       ++LocMapI;
 796     }
 797   }
 798
 799   DEBUG({dbgs() << "Split result: \t"; print(dbgs(), 0);});
 800   return DidChange;
 801 }
 802
 803 bool
 804 UserValue::splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
 805   bool DidChange = false;
 806   // Split locations referring to OldReg. Iterate backwards so splitLocation can
 807   // safely erase unuused locations.
 808   for (unsigned i = locations.size(); i ; --i) {
 809     unsigned LocNo = i-1;
 810     const MachineOperand *Loc = &locations[LocNo];
 811     if (!Loc->isReg() || Loc->getReg() != OldReg)
 812       continue;
 813     DidChange |= splitLocation(LocNo, NewRegs);
 814   }
 815   return DidChange;
 816 }
 817
 818 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
 819   bool DidChange = false;
 820   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
 821     DidChange |= UV->splitRegister(OldReg, NewRegs);
 822
 823   if (!DidChange)
 824     return;
 825
 826   // Map all of the new virtual registers.
 827   UserValue *UV = lookupVirtReg(OldReg);
 828   for (unsigned i = 0; i != NewRegs.size(); ++i)
 829     mapVirtReg(NewRegs[i]->reg, UV);
 830 }
 831
 832 void LiveDebugVariables::
 833 splitRegister(unsigned OldReg, ArrayRef<LiveInterval*> NewRegs) {
 834   if (pImpl)
 835     static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs);
 836 }
 837
 838 void
 839 UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) {
 840   // Iterate over locations in reverse makes it easier to handle coalescing.
 841   for (unsigned i = locations.size(); i ; --i) {
 842     unsigned LocNo = i-1;
 843     MachineOperand &Loc = locations[LocNo];
 844     // Only virtual registers are rewritten.
 845     if (!Loc.isReg() || !Loc.getReg() ||
 846         !TargetRegisterInfo::isVirtualRegister(Loc.getReg()))
 847       continue;
 848     unsigned VirtReg = Loc.getReg();
 849     if (VRM.isAssignedReg(VirtReg) &&
 850         TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) {
 851       // This can create a %noreg operand in rare cases when the sub-register
 852       // index is no longer available. That means the user value is in a
 853       // non-existent sub-register, and %noreg is exactly what we want.
 854       Loc.substPhysReg(VRM.getPhys(VirtReg), TRI);
 855     } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT &&
 856                VRM.isSpillSlotUsed(VRM.getStackSlot(VirtReg))) {
 857       // FIXME: Translate SubIdx to a stackslot offset.
 858       Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg));
 859     } else {
 860       Loc.setReg(0);
 861       Loc.setSubReg(0);
 862     }
 863     coalesceLocation(LocNo);
 864   }
 865 }
 866
 867 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE
 868 /// instruction.
 869 static MachineBasicBlock::iterator
 870 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx,
 871                    LiveIntervals &LIS) {
 872   SlotIndex Start = LIS.getMBBStartIdx(MBB);
 873   Idx = Idx.getBaseIndex();
 874
 875   // Try to find an insert location by going backwards from Idx.
 876   MachineInstr *MI;
 877   while (!(MI = LIS.getInstructionFromIndex(Idx))) {
 878     // We've reached the beginning of MBB.
 879     if (Idx == Start) {
 880       MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin());
 881       return I;
 882     }
 883     Idx = Idx.getPrevIndex();
 884   }
 885
 886   // Don't insert anything after the first terminator, though.
 887   return MI->getDesc().isTerminator() ? MBB->getFirstTerminator() :
 888                                     llvm::next(MachineBasicBlock::iterator(MI));
 889 }
 890
 891 DebugLoc UserValue::findDebugLoc() {
 892   DebugLoc D = dl;
 893   dl = DebugLoc();
 894   return D;
 895 }
 896 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx,
 897                                  unsigned LocNo,
 898                                  LiveIntervals &LIS,
 899                                  const TargetInstrInfo &TII) {
 900   MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS);
 901   MachineOperand &Loc = locations[LocNo];
 902   ++NumInsertedDebugValues;
 903
 904   // Frame index locations may require a target callback.
 905   if (Loc.isFI()) {
 906     MachineInstr *MI = TII.emitFrameIndexDebugValue(*MBB->getParent(),
 907                                           Loc.getIndex(), offset, variable,
 908                                                     findDebugLoc());
 909     if (MI) {
 910       MBB->insert(I, MI);
 911       return;
 912     }
 913   }
 914   // This is not a frame index, or the target is happy with a standard FI.
 915   BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE))
 916     .addOperand(Loc).addImm(offset).addMetadata(variable);
 917 }
 918
 919 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS,
 920                                 const TargetInstrInfo &TII) {
 921   MachineFunction::iterator MFEnd = VRM->getMachineFunction().end();
 922
 923   for (LocMap::const_iterator I = locInts.begin(); I.valid();) {
 924     SlotIndex Start = I.start();
 925     SlotIndex Stop = I.stop();
 926     unsigned LocNo = I.value();
 927     DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo);
 928     MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
 929     SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
 930
 931     DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
 932     insertDebugValue(MBB, Start, LocNo, LIS, TII);
 933     // This interval may span multiple basic blocks.
 934     // Insert a DBG_VALUE into each one.
 935     while(Stop > MBBEnd) {
 936       // Move to the next block.
 937       Start = MBBEnd;
 938       if (++MBB == MFEnd)
 939         break;
 940       MBBEnd = LIS.getMBBEndIdx(MBB);
 941       DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd);
 942       insertDebugValue(MBB, Start, LocNo, LIS, TII);
 943     }
 944     DEBUG(dbgs() << '\n');
 945     if (MBB == MFEnd)
 946       break;
 947
 948     ++I;
 949   }
 950 }
 951
 952 void LDVImpl::emitDebugValues(VirtRegMap *VRM) {
 953   DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n");
 954   const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
 955   for (unsigned i = 0, e = userValues.size(); i != e; ++i) {
 956     DEBUG(userValues[i]->print(dbgs(), &MF->getTarget()));
 957     userValues[i]->rewriteLocations(*VRM, *TRI);
 958     userValues[i]->emitDebugValues(VRM, *LIS, *TII);
 959   }
 960 }
 961
 962 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
 963   if (pImpl)
 964     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
 965 }
 966
 967
 968 #ifndef NDEBUG
 969 void LiveDebugVariables::dump() {
 970   if (pImpl)
 971     static_cast<LDVImpl*>(pImpl)->print(dbgs());
 972 }
 973 #endif
 974