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, 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(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 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 = 507 getUserValue(Var, Expr, Offset, IsIndirect, MI->getDebugLoc()); 508 UV->addDef(Idx, MI->getOperand(0)); 509 return true; 510 } 511 512 bool LDVImpl::collectDebugValues(MachineFunction &mf) { 513 bool Changed = false; 514 for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE; 515 ++MFI) { 516 MachineBasicBlock *MBB = &*MFI; 517 for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end(); 518 MBBI != MBBE;) { 519 if (!MBBI->isDebugValue()) { 520 ++MBBI; 521 continue; 522 } 523 // DBG_VALUE has no slot index, use the previous instruction instead. 524 SlotIndex Idx = 525 MBBI == MBB->begin() 526 ? LIS->getMBBStartIdx(MBB) 527 : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot(); 528 // Handle consecutive DBG_VALUE instructions with the same slot index. 529 do { 530 if (handleDebugValue(MBBI, Idx)) { 531 MBBI = MBB->erase(MBBI); 532 Changed = true; 533 } else 534 ++MBBI; 535 } while (MBBI != MBBE && MBBI->isDebugValue()); 536 } 537 } 538 return Changed; 539 } 540 541 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a 542 /// data-flow analysis to propagate them beyond basic block boundaries. 543 void UserValue::extendDef(SlotIndex Idx, unsigned LocNo, LiveRange *LR, 544 const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills, 545 LiveIntervals &LIS, MachineDominatorTree &MDT, 546 UserValueScopes &UVS) { 547 SlotIndex Start = Idx; 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 return; 560 } 561 if (Segment->end < Stop) { 562 Stop = Segment->end; 563 ToEnd = false; 564 } 565 } 566 567 // There could already be a short def at Start. 568 if (I.valid() && I.start() <= Start) { 569 // Stop when meeting a different location or an already extended interval. 570 Start = Start.getNextSlot(); 571 if (I.value() != LocNo || I.stop() != Start) 572 return; 573 // This is a one-slot placeholder. Just skip it. 574 ++I; 575 } 576 577 // Limited by the next def. 578 if (I.valid() && I.start() < Stop) { 579 Stop = I.start(); 580 ToEnd = false; 581 } 582 // Limited by VNI's live range. 583 else if (!ToEnd && Kills) 584 Kills->push_back(Stop); 585 586 if (Start < Stop) 587 I.insert(Start, Stop, LocNo); 588 } 589 590 void 591 UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo, 592 const SmallVectorImpl<SlotIndex> &Kills, 593 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &NewDefs, 594 MachineRegisterInfo &MRI, LiveIntervals &LIS) { 595 if (Kills.empty()) 596 return; 597 // Don't track copies from physregs, there are too many uses. 598 if (!TargetRegisterInfo::isVirtualRegister(LI->reg)) 599 return; 600 601 // Collect all the (vreg, valno) pairs that are copies of LI. 602 SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues; 603 for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) { 604 MachineInstr *MI = MO.getParent(); 605 // Copies of the full value. 606 if (MO.getSubReg() || !MI->isCopy()) 607 continue; 608 unsigned DstReg = MI->getOperand(0).getReg(); 609 610 // Don't follow copies to physregs. These are usually setting up call 611 // arguments, and the argument registers are always call clobbered. We are 612 // better off in the source register which could be a callee-saved register, 613 // or it could be spilled. 614 if (!TargetRegisterInfo::isVirtualRegister(DstReg)) 615 continue; 616 617 // Is LocNo extended to reach this copy? If not, another def may be blocking 618 // it, or we are looking at a wrong value of LI. 619 SlotIndex Idx = LIS.getInstructionIndex(*MI); 620 LocMap::iterator I = locInts.find(Idx.getRegSlot(true)); 621 if (!I.valid() || I.value() != LocNo) 622 continue; 623 624 if (!LIS.hasInterval(DstReg)) 625 continue; 626 LiveInterval *DstLI = &LIS.getInterval(DstReg); 627 const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot()); 628 assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value"); 629 CopyValues.push_back(std::make_pair(DstLI, DstVNI)); 630 } 631 632 if (CopyValues.empty()) 633 return; 634 635 DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n'); 636 637 // Try to add defs of the copied values for each kill point. 638 for (unsigned i = 0, e = Kills.size(); i != e; ++i) { 639 SlotIndex Idx = Kills[i]; 640 for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) { 641 LiveInterval *DstLI = CopyValues[j].first; 642 const VNInfo *DstVNI = CopyValues[j].second; 643 if (DstLI->getVNInfoAt(Idx) != DstVNI) 644 continue; 645 // Check that there isn't already a def at Idx 646 LocMap::iterator I = locInts.find(Idx); 647 if (I.valid() && I.start() <= Idx) 648 continue; 649 DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #" 650 << DstVNI->id << " in " << *DstLI << '\n'); 651 MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def); 652 assert(CopyMI && CopyMI->isCopy() && "Bad copy value"); 653 unsigned LocNo = getLocationNo(CopyMI->getOperand(0)); 654 I.insert(Idx, Idx.getNextSlot(), LocNo); 655 NewDefs.push_back(std::make_pair(Idx, LocNo)); 656 break; 657 } 658 } 659 } 660 661 void 662 UserValue::computeIntervals(MachineRegisterInfo &MRI, 663 const TargetRegisterInfo &TRI, 664 LiveIntervals &LIS, 665 MachineDominatorTree &MDT, 666 UserValueScopes &UVS) { 667 SmallVector<std::pair<SlotIndex, unsigned>, 16> Defs; 668 669 // Collect all defs to be extended (Skipping undefs). 670 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) 671 if (I.value() != ~0u) 672 Defs.push_back(std::make_pair(I.start(), I.value())); 673 674 // Extend all defs, and possibly add new ones along the way. 675 for (unsigned i = 0; i != Defs.size(); ++i) { 676 SlotIndex Idx = Defs[i].first; 677 unsigned LocNo = Defs[i].second; 678 const MachineOperand &Loc = locations[LocNo]; 679 680 if (!Loc.isReg()) { 681 extendDef(Idx, LocNo, nullptr, nullptr, nullptr, LIS, MDT, UVS); 682 continue; 683 } 684 685 // Register locations are constrained to where the register value is live. 686 if (TargetRegisterInfo::isVirtualRegister(Loc.getReg())) { 687 LiveInterval *LI = nullptr; 688 const VNInfo *VNI = nullptr; 689 if (LIS.hasInterval(Loc.getReg())) { 690 LI = &LIS.getInterval(Loc.getReg()); 691 VNI = LI->getVNInfoAt(Idx); 692 } 693 SmallVector<SlotIndex, 16> Kills; 694 extendDef(Idx, LocNo, LI, VNI, &Kills, LIS, MDT, UVS); 695 if (LI) 696 addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS); 697 continue; 698 } 699 700 // For physregs, use the live range of the first regunit as a guide. 701 unsigned Unit = *MCRegUnitIterator(Loc.getReg(), &TRI); 702 LiveRange *LR = &LIS.getRegUnit(Unit); 703 const VNInfo *VNI = LR->getVNInfoAt(Idx); 704 // Don't track copies from physregs, it is too expensive. 705 extendDef(Idx, LocNo, LR, VNI, nullptr, LIS, MDT, UVS); 706 } 707 708 // Finally, erase all the undefs. 709 for (LocMap::iterator I = locInts.begin(); I.valid();) 710 if (I.value() == ~0u) 711 I.erase(); 712 else 713 ++I; 714 } 715 716 void LDVImpl::computeIntervals() { 717 for (unsigned i = 0, e = userValues.size(); i != e; ++i) { 718 UserValueScopes UVS(userValues[i]->getDebugLoc(), LS); 719 userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, *MDT, UVS); 720 userValues[i]->mapVirtRegs(this); 721 } 722 } 723 724 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) { 725 clear(); 726 MF = &mf; 727 LIS = &pass.getAnalysis<LiveIntervals>(); 728 MDT = &pass.getAnalysis<MachineDominatorTree>(); 729 TRI = mf.getSubtarget().getRegisterInfo(); 730 LS.initialize(mf); 731 DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: " 732 << mf.getName() << " **********\n"); 733 734 bool Changed = collectDebugValues(mf); 735 computeIntervals(); 736 DEBUG(print(dbgs())); 737 ModifiedMF = Changed; 738 return Changed; 739 } 740 741 static void removeDebugValues(MachineFunction &mf) { 742 for (MachineBasicBlock &MBB : mf) { 743 for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) { 744 if (!MBBI->isDebugValue()) { 745 ++MBBI; 746 continue; 747 } 748 MBBI = MBB.erase(MBBI); 749 } 750 } 751 } 752 753 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) { 754 if (!EnableLDV) 755 return false; 756 if (!mf.getFunction()->getSubprogram()) { 757 removeDebugValues(mf); 758 return false; 759 } 760 if (!pImpl) 761 pImpl = new LDVImpl(this); 762 return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf); 763 } 764 765 void LiveDebugVariables::releaseMemory() { 766 if (pImpl) 767 static_cast<LDVImpl*>(pImpl)->clear(); 768 } 769 770 LiveDebugVariables::~LiveDebugVariables() { 771 if (pImpl) 772 delete static_cast<LDVImpl*>(pImpl); 773 } 774 775 //===----------------------------------------------------------------------===// 776 // Live Range Splitting 777 //===----------------------------------------------------------------------===// 778 779 bool 780 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs, 781 LiveIntervals& LIS) { 782 DEBUG({ 783 dbgs() << "Splitting Loc" << OldLocNo << '\t'; 784 print(dbgs(), nullptr); 785 }); 786 bool DidChange = false; 787 LocMap::iterator LocMapI; 788 LocMapI.setMap(locInts); 789 for (unsigned i = 0; i != NewRegs.size(); ++i) { 790 LiveInterval *LI = &LIS.getInterval(NewRegs[i]); 791 if (LI->empty()) 792 continue; 793 794 // Don't allocate the new LocNo until it is needed. 795 unsigned NewLocNo = ~0u; 796 797 // Iterate over the overlaps between locInts and LI. 798 LocMapI.find(LI->beginIndex()); 799 if (!LocMapI.valid()) 800 continue; 801 LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start()); 802 LiveInterval::iterator LIE = LI->end(); 803 while (LocMapI.valid() && LII != LIE) { 804 // At this point, we know that LocMapI.stop() > LII->start. 805 LII = LI->advanceTo(LII, LocMapI.start()); 806 if (LII == LIE) 807 break; 808 809 // Now LII->end > LocMapI.start(). Do we have an overlap? 810 if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) { 811 // Overlapping correct location. Allocate NewLocNo now. 812 if (NewLocNo == ~0u) { 813 MachineOperand MO = MachineOperand::CreateReg(LI->reg, false); 814 MO.setSubReg(locations[OldLocNo].getSubReg()); 815 NewLocNo = getLocationNo(MO); 816 DidChange = true; 817 } 818 819 SlotIndex LStart = LocMapI.start(); 820 SlotIndex LStop = LocMapI.stop(); 821 822 // Trim LocMapI down to the LII overlap. 823 if (LStart < LII->start) 824 LocMapI.setStartUnchecked(LII->start); 825 if (LStop > LII->end) 826 LocMapI.setStopUnchecked(LII->end); 827 828 // Change the value in the overlap. This may trigger coalescing. 829 LocMapI.setValue(NewLocNo); 830 831 // Re-insert any removed OldLocNo ranges. 832 if (LStart < LocMapI.start()) { 833 LocMapI.insert(LStart, LocMapI.start(), OldLocNo); 834 ++LocMapI; 835 assert(LocMapI.valid() && "Unexpected coalescing"); 836 } 837 if (LStop > LocMapI.stop()) { 838 ++LocMapI; 839 LocMapI.insert(LII->end, LStop, OldLocNo); 840 --LocMapI; 841 } 842 } 843 844 // Advance to the next overlap. 845 if (LII->end < LocMapI.stop()) { 846 if (++LII == LIE) 847 break; 848 LocMapI.advanceTo(LII->start); 849 } else { 850 ++LocMapI; 851 if (!LocMapI.valid()) 852 break; 853 LII = LI->advanceTo(LII, LocMapI.start()); 854 } 855 } 856 } 857 858 // Finally, remove any remaining OldLocNo intervals and OldLocNo itself. 859 locations.erase(locations.begin() + OldLocNo); 860 LocMapI.goToBegin(); 861 while (LocMapI.valid()) { 862 unsigned v = LocMapI.value(); 863 if (v == OldLocNo) { 864 DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';' 865 << LocMapI.stop() << ")\n"); 866 LocMapI.erase(); 867 } else { 868 if (v > OldLocNo) 869 LocMapI.setValueUnchecked(v-1); 870 ++LocMapI; 871 } 872 } 873 874 DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);}); 875 return DidChange; 876 } 877 878 bool 879 UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, 880 LiveIntervals &LIS) { 881 bool DidChange = false; 882 // Split locations referring to OldReg. Iterate backwards so splitLocation can 883 // safely erase unused locations. 884 for (unsigned i = locations.size(); i ; --i) { 885 unsigned LocNo = i-1; 886 const MachineOperand *Loc = &locations[LocNo]; 887 if (!Loc->isReg() || Loc->getReg() != OldReg) 888 continue; 889 DidChange |= splitLocation(LocNo, NewRegs, LIS); 890 } 891 return DidChange; 892 } 893 894 void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) { 895 bool DidChange = false; 896 for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext()) 897 DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS); 898 899 if (!DidChange) 900 return; 901 902 // Map all of the new virtual registers. 903 UserValue *UV = lookupVirtReg(OldReg); 904 for (unsigned i = 0; i != NewRegs.size(); ++i) 905 mapVirtReg(NewRegs[i], UV); 906 } 907 908 void LiveDebugVariables:: 909 splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs, LiveIntervals &LIS) { 910 if (pImpl) 911 static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs); 912 } 913 914 void 915 UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) { 916 // Iterate over locations in reverse makes it easier to handle coalescing. 917 for (unsigned i = locations.size(); i ; --i) { 918 unsigned LocNo = i-1; 919 MachineOperand &Loc = locations[LocNo]; 920 // Only virtual registers are rewritten. 921 if (!Loc.isReg() || !Loc.getReg() || 922 !TargetRegisterInfo::isVirtualRegister(Loc.getReg())) 923 continue; 924 unsigned VirtReg = Loc.getReg(); 925 if (VRM.isAssignedReg(VirtReg) && 926 TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) { 927 // This can create a %noreg operand in rare cases when the sub-register 928 // index is no longer available. That means the user value is in a 929 // non-existent sub-register, and %noreg is exactly what we want. 930 Loc.substPhysReg(VRM.getPhys(VirtReg), TRI); 931 } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) { 932 // FIXME: Translate SubIdx to a stackslot offset. 933 Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg)); 934 } else { 935 Loc.setReg(0); 936 Loc.setSubReg(0); 937 } 938 coalesceLocation(LocNo); 939 } 940 } 941 942 /// findInsertLocation - Find an iterator for inserting a DBG_VALUE 943 /// instruction. 944 static MachineBasicBlock::iterator 945 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, 946 LiveIntervals &LIS) { 947 SlotIndex Start = LIS.getMBBStartIdx(MBB); 948 Idx = Idx.getBaseIndex(); 949 950 // Try to find an insert location by going backwards from Idx. 951 MachineInstr *MI; 952 while (!(MI = LIS.getInstructionFromIndex(Idx))) { 953 // We've reached the beginning of MBB. 954 if (Idx == Start) { 955 MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin()); 956 return I; 957 } 958 Idx = Idx.getPrevIndex(); 959 } 960 961 // Don't insert anything after the first terminator, though. 962 return MI->isTerminator() ? MBB->getFirstTerminator() : 963 std::next(MachineBasicBlock::iterator(MI)); 964 } 965 966 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, 967 unsigned LocNo, 968 LiveIntervals &LIS, 969 const TargetInstrInfo &TII) { 970 MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS); 971 MachineOperand &Loc = locations[LocNo]; 972 ++NumInsertedDebugValues; 973 974 assert(cast<DILocalVariable>(Variable) 975 ->isValidLocationForIntrinsic(getDebugLoc()) && 976 "Expected inlined-at fields to agree"); 977 if (Loc.isReg()) 978 BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE), 979 IsIndirect, Loc.getReg(), offset, Variable, Expression); 980 else 981 BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE)) 982 .addOperand(Loc) 983 .addImm(offset) 984 .addMetadata(Variable) 985 .addMetadata(Expression); 986 } 987 988 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, 989 const TargetInstrInfo &TII) { 990 MachineFunction::iterator MFEnd = VRM->getMachineFunction().end(); 991 992 for (LocMap::const_iterator I = locInts.begin(); I.valid();) { 993 SlotIndex Start = I.start(); 994 SlotIndex Stop = I.stop(); 995 unsigned LocNo = I.value(); 996 DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << LocNo); 997 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); 998 SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB); 999 1000 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd); 1001 insertDebugValue(&*MBB, Start, LocNo, LIS, TII); 1002 // This interval may span multiple basic blocks. 1003 // Insert a DBG_VALUE into each one. 1004 while(Stop > MBBEnd) { 1005 // Move to the next block. 1006 Start = MBBEnd; 1007 if (++MBB == MFEnd) 1008 break; 1009 MBBEnd = LIS.getMBBEndIdx(&*MBB); 1010 DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd); 1011 insertDebugValue(&*MBB, Start, LocNo, LIS, TII); 1012 } 1013 DEBUG(dbgs() << '\n'); 1014 if (MBB == MFEnd) 1015 break; 1016 1017 ++I; 1018 } 1019 } 1020 1021 void LDVImpl::emitDebugValues(VirtRegMap *VRM) { 1022 DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n"); 1023 if (!MF) 1024 return; 1025 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 1026 for (unsigned i = 0, e = userValues.size(); i != e; ++i) { 1027 DEBUG(userValues[i]->print(dbgs(), TRI)); 1028 userValues[i]->rewriteLocations(*VRM, *TRI); 1029 userValues[i]->emitDebugValues(VRM, *LIS, *TII); 1030 } 1031 EmitDone = true; 1032 } 1033 1034 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) { 1035 if (pImpl) 1036 static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM); 1037 } 1038 1039 bool LiveDebugVariables::doInitialization(Module &M) { 1040 return Pass::doInitialization(M); 1041 } 1042 1043 #ifndef NDEBUG 1044 LLVM_DUMP_METHOD void LiveDebugVariables::dump() { 1045 if (pImpl) 1046 static_cast<LDVImpl*>(pImpl)->print(dbgs()); 1047 } 1048 #endif 1049