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