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