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