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