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