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