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