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