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