1 //===- LiveDebugVariables.cpp - Tracking debug info variables -------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the LiveDebugVariables analysis. 10 // 11 // Remove all DBG_VALUE instructions referencing virtual registers and replace 12 // them with a data structure tracking where live user variables are kept - in a 13 // virtual register or in a stack slot. 14 // 15 // Allow the data structure to be updated during register allocation when values 16 // are moved between registers and stack slots. Finally emit new DBG_VALUE 17 // instructions after register allocation is complete. 18 // 19 //===----------------------------------------------------------------------===// 20 21 #include "LiveDebugVariables.h" 22 #include "llvm/ADT/ArrayRef.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/IntervalMap.h" 25 #include "llvm/ADT/MapVector.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/LiveIntervals.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/TargetInstrInfo.h" 43 #include "llvm/CodeGen/TargetOpcodes.h" 44 #include "llvm/CodeGen/TargetRegisterInfo.h" 45 #include "llvm/CodeGen/TargetSubtargetInfo.h" 46 #include "llvm/CodeGen/VirtRegMap.h" 47 #include "llvm/Config/llvm-config.h" 48 #include "llvm/IR/DebugInfoMetadata.h" 49 #include "llvm/IR/DebugLoc.h" 50 #include "llvm/IR/Function.h" 51 #include "llvm/IR/Metadata.h" 52 #include "llvm/InitializePasses.h" 53 #include "llvm/MC/MCRegisterInfo.h" 54 #include "llvm/Pass.h" 55 #include "llvm/Support/Casting.h" 56 #include "llvm/Support/CommandLine.h" 57 #include "llvm/Support/Compiler.h" 58 #include "llvm/Support/Debug.h" 59 #include "llvm/Support/raw_ostream.h" 60 #include <algorithm> 61 #include <cassert> 62 #include <iterator> 63 #include <memory> 64 #include <utility> 65 66 using namespace llvm; 67 68 #define DEBUG_TYPE "livedebugvars" 69 70 static cl::opt<bool> 71 EnableLDV("live-debug-variables", cl::init(true), 72 cl::desc("Enable the live debug variables pass"), cl::Hidden); 73 74 STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted"); 75 STATISTIC(NumInsertedDebugLabels, "Number of DBG_LABELs inserted"); 76 77 char LiveDebugVariables::ID = 0; 78 79 INITIALIZE_PASS_BEGIN(LiveDebugVariables, DEBUG_TYPE, 80 "Debug Variable Analysis", false, false) 81 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 82 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 83 INITIALIZE_PASS_END(LiveDebugVariables, DEBUG_TYPE, 84 "Debug Variable Analysis", false, false) 85 86 void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const { 87 AU.addRequired<MachineDominatorTree>(); 88 AU.addRequiredTransitive<LiveIntervals>(); 89 AU.setPreservesAll(); 90 MachineFunctionPass::getAnalysisUsage(AU); 91 } 92 93 LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID) { 94 initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); 95 } 96 97 enum : unsigned { UndefLocNo = ~0U }; 98 99 /// Describes a debug variable value by location number and expression along 100 /// with some flags about the original usage of the location. 101 class DbgVariableValue { 102 public: 103 DbgVariableValue(unsigned LocNo, bool WasIndirect, 104 const DIExpression &Expression) 105 : LocNo(LocNo), WasIndirect(WasIndirect), Expression(&Expression) { 106 assert(getLocNo() == LocNo && "location truncation"); 107 } 108 109 DbgVariableValue() : LocNo(0), WasIndirect(0) {} 110 111 const DIExpression *getExpression() const { return Expression; } 112 unsigned getLocNo() const { 113 // Fix up the undef location number, which gets truncated. 114 return LocNo == INT_MAX ? UndefLocNo : LocNo; 115 } 116 bool getWasIndirect() const { return WasIndirect; } 117 bool isUndef() const { return getLocNo() == UndefLocNo; } 118 119 DbgVariableValue changeLocNo(unsigned NewLocNo) const { 120 return DbgVariableValue(NewLocNo, WasIndirect, *Expression); 121 } 122 123 friend inline bool operator==(const DbgVariableValue &LHS, 124 const DbgVariableValue &RHS) { 125 return LHS.LocNo == RHS.LocNo && LHS.WasIndirect == RHS.WasIndirect && 126 LHS.Expression == RHS.Expression; 127 } 128 129 friend inline bool operator!=(const DbgVariableValue &LHS, 130 const DbgVariableValue &RHS) { 131 return !(LHS == RHS); 132 } 133 134 private: 135 unsigned LocNo : 31; 136 unsigned WasIndirect : 1; 137 const DIExpression *Expression = nullptr; 138 }; 139 140 /// Map of where a user value is live to that value. 141 using LocMap = IntervalMap<SlotIndex, DbgVariableValue, 4>; 142 143 /// Map of stack slot offsets for spilled locations. 144 /// Non-spilled locations are not added to the map. 145 using SpillOffsetMap = DenseMap<unsigned, unsigned>; 146 147 namespace { 148 149 class LDVImpl; 150 151 /// A user value is a part of a debug info user variable. 152 /// 153 /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register 154 /// holds part of a user variable. The part is identified by a byte offset. 155 /// 156 /// UserValues are grouped into equivalence classes for easier searching. Two 157 /// user values are related if they are held by the same virtual register. The 158 /// equivalence class is the transitive closure of that relation. 159 class UserValue { 160 const DILocalVariable *Variable; ///< The debug info variable we are part of. 161 /// The part of the variable we describe. 162 const Optional<DIExpression::FragmentInfo> Fragment; 163 DebugLoc dl; ///< The debug location for the variable. This is 164 ///< used by dwarf writer to find lexical scope. 165 UserValue *leader; ///< Equivalence class leader. 166 UserValue *next = nullptr; ///< Next value in equivalence class, or null. 167 168 /// Numbered locations referenced by locmap. 169 SmallVector<MachineOperand, 4> locations; 170 171 /// Map of slot indices where this value is live. 172 LocMap locInts; 173 174 /// Set of interval start indexes that have been trimmed to the 175 /// lexical scope. 176 SmallSet<SlotIndex, 2> trimmedDefs; 177 178 /// Insert a DBG_VALUE into MBB at Idx for DbgValue. 179 void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx, 180 SlotIndex StopIdx, DbgVariableValue DbgValue, 181 bool Spilled, unsigned SpillOffset, LiveIntervals &LIS, 182 const TargetInstrInfo &TII, 183 const TargetRegisterInfo &TRI); 184 185 /// Replace OldLocNo ranges with NewRegs ranges where NewRegs 186 /// is live. Returns true if any changes were made. 187 bool splitLocation(unsigned OldLocNo, ArrayRef<Register> NewRegs, 188 LiveIntervals &LIS); 189 190 public: 191 /// Create a new UserValue. 192 UserValue(const DILocalVariable *var, 193 Optional<DIExpression::FragmentInfo> Fragment, DebugLoc L, 194 LocMap::Allocator &alloc) 195 : Variable(var), Fragment(Fragment), dl(std::move(L)), leader(this), 196 locInts(alloc) {} 197 198 /// Get the leader of this value's equivalence class. 199 UserValue *getLeader() { 200 UserValue *l = leader; 201 while (l != l->leader) 202 l = l->leader; 203 return leader = l; 204 } 205 206 /// Return the next UserValue in the equivalence class. 207 UserValue *getNext() const { return next; } 208 209 /// Merge equivalence classes. 210 static UserValue *merge(UserValue *L1, UserValue *L2) { 211 L2 = L2->getLeader(); 212 if (!L1) 213 return L2; 214 L1 = L1->getLeader(); 215 if (L1 == L2) 216 return L1; 217 // Splice L2 before L1's members. 218 UserValue *End = L2; 219 while (End->next) { 220 End->leader = L1; 221 End = End->next; 222 } 223 End->leader = L1; 224 End->next = L1->next; 225 L1->next = L2; 226 return L1; 227 } 228 229 /// Return the location number that matches Loc. 230 /// 231 /// For undef values we always return location number UndefLocNo without 232 /// inserting anything in locations. Since locations is a vector and the 233 /// location number is the position in the vector and UndefLocNo is ~0, 234 /// we would need a very big vector to put the value at the right position. 235 unsigned getLocationNo(const MachineOperand &LocMO) { 236 if (LocMO.isReg()) { 237 if (LocMO.getReg() == 0) 238 return UndefLocNo; 239 // For register locations we dont care about use/def and other flags. 240 for (unsigned i = 0, e = locations.size(); i != e; ++i) 241 if (locations[i].isReg() && 242 locations[i].getReg() == LocMO.getReg() && 243 locations[i].getSubReg() == LocMO.getSubReg()) 244 return i; 245 } else 246 for (unsigned i = 0, e = locations.size(); i != e; ++i) 247 if (LocMO.isIdenticalTo(locations[i])) 248 return i; 249 locations.push_back(LocMO); 250 // We are storing a MachineOperand outside a MachineInstr. 251 locations.back().clearParent(); 252 // Don't store def operands. 253 if (locations.back().isReg()) { 254 if (locations.back().isDef()) 255 locations.back().setIsDead(false); 256 locations.back().setIsUse(); 257 } 258 return locations.size() - 1; 259 } 260 261 /// Remove (recycle) a location number. If \p LocNo still is used by the 262 /// locInts nothing is done. 263 void removeLocationIfUnused(unsigned LocNo) { 264 // Bail out if LocNo still is used. 265 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) { 266 DbgVariableValue DbgValue = I.value(); 267 if (DbgValue.getLocNo() == LocNo) 268 return; 269 } 270 // Remove the entry in the locations vector, and adjust all references to 271 // location numbers above the removed entry. 272 locations.erase(locations.begin() + LocNo); 273 for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) { 274 DbgVariableValue DbgValue = I.value(); 275 if (!DbgValue.isUndef() && DbgValue.getLocNo() > LocNo) 276 I.setValueUnchecked(DbgValue.changeLocNo(DbgValue.getLocNo() - 1)); 277 } 278 } 279 280 /// Ensure that all virtual register locations are mapped. 281 void mapVirtRegs(LDVImpl *LDV); 282 283 /// Add a definition point to this user value. 284 void addDef(SlotIndex Idx, const MachineOperand &LocMO, bool IsIndirect, 285 const DIExpression &Expr) { 286 DbgVariableValue DbgValue(getLocationNo(LocMO), IsIndirect, Expr); 287 // Add a singular (Idx,Idx) -> value mapping. 288 LocMap::iterator I = locInts.find(Idx); 289 if (!I.valid() || I.start() != Idx) 290 I.insert(Idx, Idx.getNextSlot(), DbgValue); 291 else 292 // A later DBG_VALUE at the same SlotIndex overrides the old location. 293 I.setValue(DbgValue); 294 } 295 296 /// Extend the current definition as far as possible down. 297 /// 298 /// Stop when meeting an existing def or when leaving the live 299 /// range of VNI. End points where VNI is no longer live are added to Kills. 300 /// 301 /// We only propagate DBG_VALUES locally here. LiveDebugValues performs a 302 /// data-flow analysis to propagate them beyond basic block boundaries. 303 /// 304 /// \param Idx Starting point for the definition. 305 /// \param DbgValue value to propagate. 306 /// \param LR Restrict liveness to where LR has the value VNI. May be null. 307 /// \param VNI When LR is not null, this is the value to restrict to. 308 /// \param [out] Kills Append end points of VNI's live range to Kills. 309 /// \param LIS Live intervals analysis. 310 void extendDef(SlotIndex Idx, DbgVariableValue DbgValue, LiveRange *LR, 311 const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills, 312 LiveIntervals &LIS); 313 314 /// The value in LI may be copies to other registers. Determine if 315 /// any of the copies are available at the kill points, and add defs if 316 /// possible. 317 /// 318 /// \param LI Scan for copies of the value in LI->reg. 319 /// \param DbgValue Location number of LI->reg, and DIExpression. 320 /// \param Kills Points where the range of DbgValue could be extended. 321 /// \param [in,out] NewDefs Append (Idx, DbgValue) of inserted defs here. 322 void addDefsFromCopies( 323 LiveInterval *LI, DbgVariableValue DbgValue, 324 const SmallVectorImpl<SlotIndex> &Kills, 325 SmallVectorImpl<std::pair<SlotIndex, DbgVariableValue>> &NewDefs, 326 MachineRegisterInfo &MRI, LiveIntervals &LIS); 327 328 /// Compute the live intervals of all locations after collecting all their 329 /// def points. 330 void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, 331 LiveIntervals &LIS, LexicalScopes &LS); 332 333 /// Replace OldReg ranges with NewRegs ranges where NewRegs is 334 /// live. Returns true if any changes were made. 335 bool splitRegister(Register OldReg, ArrayRef<Register> NewRegs, 336 LiveIntervals &LIS); 337 338 /// Rewrite virtual register locations according to the provided virtual 339 /// register map. Record the stack slot offsets for the locations that 340 /// were spilled. 341 void rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF, 342 const TargetInstrInfo &TII, 343 const TargetRegisterInfo &TRI, 344 SpillOffsetMap &SpillOffsets); 345 346 /// Recreate DBG_VALUE instruction from data structures. 347 void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, 348 const TargetInstrInfo &TII, 349 const TargetRegisterInfo &TRI, 350 const SpillOffsetMap &SpillOffsets); 351 352 /// Return DebugLoc of this UserValue. 353 DebugLoc getDebugLoc() { return dl;} 354 355 void print(raw_ostream &, const TargetRegisterInfo *); 356 }; 357 358 /// A user label is a part of a debug info user label. 359 class UserLabel { 360 const DILabel *Label; ///< The debug info label we are part of. 361 DebugLoc dl; ///< The debug location for the label. This is 362 ///< used by dwarf writer to find lexical scope. 363 SlotIndex loc; ///< Slot used by the debug label. 364 365 /// Insert a DBG_LABEL into MBB at Idx. 366 void insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx, 367 LiveIntervals &LIS, const TargetInstrInfo &TII); 368 369 public: 370 /// Create a new UserLabel. 371 UserLabel(const DILabel *label, DebugLoc L, SlotIndex Idx) 372 : Label(label), dl(std::move(L)), loc(Idx) {} 373 374 /// Does this UserLabel match the parameters? 375 bool matches(const DILabel *L, const DILocation *IA, 376 const SlotIndex Index) const { 377 return Label == L && dl->getInlinedAt() == IA && loc == Index; 378 } 379 380 /// Recreate DBG_LABEL instruction from data structures. 381 void emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII); 382 383 /// Return DebugLoc of this UserLabel. 384 DebugLoc getDebugLoc() { return dl; } 385 386 void print(raw_ostream &, const TargetRegisterInfo *); 387 }; 388 389 /// Implementation of the LiveDebugVariables pass. 390 class LDVImpl { 391 LiveDebugVariables &pass; 392 LocMap::Allocator allocator; 393 MachineFunction *MF = nullptr; 394 LiveIntervals *LIS; 395 const TargetRegisterInfo *TRI; 396 397 /// Whether emitDebugValues is called. 398 bool EmitDone = false; 399 400 /// Whether the machine function is modified during the pass. 401 bool ModifiedMF = false; 402 403 /// All allocated UserValue instances. 404 SmallVector<std::unique_ptr<UserValue>, 8> userValues; 405 406 /// All allocated UserLabel instances. 407 SmallVector<std::unique_ptr<UserLabel>, 2> userLabels; 408 409 /// Map virtual register to eq class leader. 410 using VRMap = DenseMap<unsigned, UserValue *>; 411 VRMap virtRegToEqClass; 412 413 /// Map to find existing UserValue instances. 414 using UVMap = DenseMap<DebugVariable, UserValue *>; 415 UVMap userVarMap; 416 417 /// Find or create a UserValue. 418 UserValue *getUserValue(const DILocalVariable *Var, 419 Optional<DIExpression::FragmentInfo> Fragment, 420 const DebugLoc &DL); 421 422 /// Find the EC leader for VirtReg or null. 423 UserValue *lookupVirtReg(Register VirtReg); 424 425 /// Add DBG_VALUE instruction to our maps. 426 /// 427 /// \param MI DBG_VALUE instruction 428 /// \param Idx Last valid SLotIndex before instruction. 429 /// 430 /// \returns True if the DBG_VALUE instruction should be deleted. 431 bool handleDebugValue(MachineInstr &MI, SlotIndex Idx); 432 433 /// Add DBG_LABEL instruction to UserLabel. 434 /// 435 /// \param MI DBG_LABEL instruction 436 /// \param Idx Last valid SlotIndex before instruction. 437 /// 438 /// \returns True if the DBG_LABEL instruction should be deleted. 439 bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx); 440 441 /// Collect and erase all DBG_VALUE instructions, adding a UserValue def 442 /// for each instruction. 443 /// 444 /// \param mf MachineFunction to be scanned. 445 /// 446 /// \returns True if any debug values were found. 447 bool collectDebugValues(MachineFunction &mf); 448 449 /// Compute the live intervals of all user values after collecting all 450 /// their def points. 451 void computeIntervals(); 452 453 public: 454 LDVImpl(LiveDebugVariables *ps) : pass(*ps) {} 455 456 bool runOnMachineFunction(MachineFunction &mf); 457 458 /// Release all memory. 459 void clear() { 460 MF = nullptr; 461 userValues.clear(); 462 userLabels.clear(); 463 virtRegToEqClass.clear(); 464 userVarMap.clear(); 465 // Make sure we call emitDebugValues if the machine function was modified. 466 assert((!ModifiedMF || EmitDone) && 467 "Dbg values are not emitted in LDV"); 468 EmitDone = false; 469 ModifiedMF = false; 470 } 471 472 /// Map virtual register to an equivalence class. 473 void mapVirtReg(Register VirtReg, UserValue *EC); 474 475 /// Replace all references to OldReg with NewRegs. 476 void splitRegister(Register OldReg, ArrayRef<Register> NewRegs); 477 478 /// Recreate DBG_VALUE instruction from data structures. 479 void emitDebugValues(VirtRegMap *VRM); 480 481 void print(raw_ostream&); 482 }; 483 484 } // end anonymous namespace 485 486 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 487 static void printDebugLoc(const DebugLoc &DL, raw_ostream &CommentOS, 488 const LLVMContext &Ctx) { 489 if (!DL) 490 return; 491 492 auto *Scope = cast<DIScope>(DL.getScope()); 493 // Omit the directory, because it's likely to be long and uninteresting. 494 CommentOS << Scope->getFilename(); 495 CommentOS << ':' << DL.getLine(); 496 if (DL.getCol() != 0) 497 CommentOS << ':' << DL.getCol(); 498 499 DebugLoc InlinedAtDL = DL.getInlinedAt(); 500 if (!InlinedAtDL) 501 return; 502 503 CommentOS << " @[ "; 504 printDebugLoc(InlinedAtDL, CommentOS, Ctx); 505 CommentOS << " ]"; 506 } 507 508 static void printExtendedName(raw_ostream &OS, const DINode *Node, 509 const DILocation *DL) { 510 const LLVMContext &Ctx = Node->getContext(); 511 StringRef Res; 512 unsigned Line = 0; 513 if (const auto *V = dyn_cast<const DILocalVariable>(Node)) { 514 Res = V->getName(); 515 Line = V->getLine(); 516 } else if (const auto *L = dyn_cast<const DILabel>(Node)) { 517 Res = L->getName(); 518 Line = L->getLine(); 519 } 520 521 if (!Res.empty()) 522 OS << Res << "," << Line; 523 auto *InlinedAt = DL ? DL->getInlinedAt() : nullptr; 524 if (InlinedAt) { 525 if (DebugLoc InlinedAtDL = InlinedAt) { 526 OS << " @["; 527 printDebugLoc(InlinedAtDL, OS, Ctx); 528 OS << "]"; 529 } 530 } 531 } 532 533 void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { 534 OS << "!\""; 535 printExtendedName(OS, Variable, dl); 536 537 OS << "\"\t"; 538 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) { 539 OS << " [" << I.start() << ';' << I.stop() << "):"; 540 if (I.value().isUndef()) 541 OS << "undef"; 542 else { 543 OS << I.value().getLocNo(); 544 if (I.value().getWasIndirect()) 545 OS << " ind"; 546 } 547 } 548 for (unsigned i = 0, e = locations.size(); i != e; ++i) { 549 OS << " Loc" << i << '='; 550 locations[i].print(OS, TRI); 551 } 552 OS << '\n'; 553 } 554 555 void UserLabel::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { 556 OS << "!\""; 557 printExtendedName(OS, Label, dl); 558 559 OS << "\"\t"; 560 OS << loc; 561 OS << '\n'; 562 } 563 564 void LDVImpl::print(raw_ostream &OS) { 565 OS << "********** DEBUG VARIABLES **********\n"; 566 for (auto &userValue : userValues) 567 userValue->print(OS, TRI); 568 OS << "********** DEBUG LABELS **********\n"; 569 for (auto &userLabel : userLabels) 570 userLabel->print(OS, TRI); 571 } 572 #endif 573 574 void UserValue::mapVirtRegs(LDVImpl *LDV) { 575 for (unsigned i = 0, e = locations.size(); i != e; ++i) 576 if (locations[i].isReg() && 577 Register::isVirtualRegister(locations[i].getReg())) 578 LDV->mapVirtReg(locations[i].getReg(), this); 579 } 580 581 UserValue *LDVImpl::getUserValue(const DILocalVariable *Var, 582 Optional<DIExpression::FragmentInfo> Fragment, 583 const DebugLoc &DL) { 584 // FIXME: Handle partially overlapping fragments. See 585 // https://reviews.llvm.org/D70121#1849741. 586 DebugVariable ID(Var, Fragment, DL->getInlinedAt()); 587 UserValue *&UV = userVarMap[ID]; 588 if (!UV) { 589 userValues.push_back( 590 std::make_unique<UserValue>(Var, Fragment, DL, allocator)); 591 UV = userValues.back().get(); 592 } 593 return UV; 594 } 595 596 void LDVImpl::mapVirtReg(Register VirtReg, UserValue *EC) { 597 assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs"); 598 UserValue *&Leader = virtRegToEqClass[VirtReg]; 599 Leader = UserValue::merge(Leader, EC); 600 } 601 602 UserValue *LDVImpl::lookupVirtReg(Register VirtReg) { 603 if (UserValue *UV = virtRegToEqClass.lookup(VirtReg)) 604 return UV->getLeader(); 605 return nullptr; 606 } 607 608 bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) { 609 // DBG_VALUE loc, offset, variable 610 if (MI.getNumOperands() != 4 || 611 !(MI.getDebugOffset().isReg() || MI.getDebugOffset().isImm()) || 612 !MI.getDebugVariableOp().isMetadata()) { 613 LLVM_DEBUG(dbgs() << "Can't handle " << MI); 614 return false; 615 } 616 617 // Detect invalid DBG_VALUE instructions, with a debug-use of a virtual 618 // register that hasn't been defined yet. If we do not remove those here, then 619 // the re-insertion of the DBG_VALUE instruction after register allocation 620 // will be incorrect. 621 // TODO: If earlier passes are corrected to generate sane debug information 622 // (and if the machine verifier is improved to catch this), then these checks 623 // could be removed or replaced by asserts. 624 bool Discard = false; 625 if (MI.getDebugOperand(0).isReg() && 626 Register::isVirtualRegister(MI.getDebugOperand(0).getReg())) { 627 const Register Reg = MI.getDebugOperand(0).getReg(); 628 if (!LIS->hasInterval(Reg)) { 629 // The DBG_VALUE is described by a virtual register that does not have a 630 // live interval. Discard the DBG_VALUE. 631 Discard = true; 632 LLVM_DEBUG(dbgs() << "Discarding debug info (no LIS interval): " << Idx 633 << " " << MI); 634 } else { 635 // The DBG_VALUE is only valid if either Reg is live out from Idx, or Reg 636 // is defined dead at Idx (where Idx is the slot index for the instruction 637 // preceding the DBG_VALUE). 638 const LiveInterval &LI = LIS->getInterval(Reg); 639 LiveQueryResult LRQ = LI.Query(Idx); 640 if (!LRQ.valueOutOrDead()) { 641 // We have found a DBG_VALUE with the value in a virtual register that 642 // is not live. Discard the DBG_VALUE. 643 Discard = true; 644 LLVM_DEBUG(dbgs() << "Discarding debug info (reg not live): " << Idx 645 << " " << MI); 646 } 647 } 648 } 649 650 // Get or create the UserValue for (variable,offset) here. 651 bool IsIndirect = MI.isDebugOffsetImm(); 652 if (IsIndirect) 653 assert(MI.getDebugOffset().getImm() == 0 && 654 "DBG_VALUE with nonzero offset"); 655 const DILocalVariable *Var = MI.getDebugVariable(); 656 const DIExpression *Expr = MI.getDebugExpression(); 657 UserValue *UV = getUserValue(Var, Expr->getFragmentInfo(), MI.getDebugLoc()); 658 if (!Discard) 659 UV->addDef(Idx, MI.getDebugOperand(0), IsIndirect, *Expr); 660 else { 661 MachineOperand MO = MachineOperand::CreateReg(0U, false); 662 MO.setIsDebug(); 663 UV->addDef(Idx, MO, false, *Expr); 664 } 665 return true; 666 } 667 668 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) { 669 // DBG_LABEL label 670 if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) { 671 LLVM_DEBUG(dbgs() << "Can't handle " << MI); 672 return false; 673 } 674 675 // Get or create the UserLabel for label here. 676 const DILabel *Label = MI.getDebugLabel(); 677 const DebugLoc &DL = MI.getDebugLoc(); 678 bool Found = false; 679 for (auto const &L : userLabels) { 680 if (L->matches(Label, DL->getInlinedAt(), Idx)) { 681 Found = true; 682 break; 683 } 684 } 685 if (!Found) 686 userLabels.push_back(std::make_unique<UserLabel>(Label, DL, Idx)); 687 688 return true; 689 } 690 691 bool LDVImpl::collectDebugValues(MachineFunction &mf) { 692 bool Changed = false; 693 for (MachineFunction::iterator MFI = mf.begin(), MFE = mf.end(); MFI != MFE; 694 ++MFI) { 695 MachineBasicBlock *MBB = &*MFI; 696 for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end(); 697 MBBI != MBBE;) { 698 // Use the first debug instruction in the sequence to get a SlotIndex 699 // for following consecutive debug instructions. 700 if (!MBBI->isDebugInstr()) { 701 ++MBBI; 702 continue; 703 } 704 // Debug instructions has no slot index. Use the previous 705 // non-debug instruction's SlotIndex as its SlotIndex. 706 SlotIndex Idx = 707 MBBI == MBB->begin() 708 ? LIS->getMBBStartIdx(MBB) 709 : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot(); 710 // Handle consecutive debug instructions with the same slot index. 711 do { 712 // Only handle DBG_VALUE in handleDebugValue(). Skip all other 713 // kinds of debug instructions. 714 if ((MBBI->isDebugValue() && handleDebugValue(*MBBI, Idx)) || 715 (MBBI->isDebugLabel() && handleDebugLabel(*MBBI, Idx))) { 716 MBBI = MBB->erase(MBBI); 717 Changed = true; 718 } else 719 ++MBBI; 720 } while (MBBI != MBBE && MBBI->isDebugInstr()); 721 } 722 } 723 return Changed; 724 } 725 726 void UserValue::extendDef(SlotIndex Idx, DbgVariableValue DbgValue, LiveRange *LR, 727 const VNInfo *VNI, SmallVectorImpl<SlotIndex> *Kills, 728 LiveIntervals &LIS) { 729 SlotIndex Start = Idx; 730 MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start); 731 SlotIndex Stop = LIS.getMBBEndIdx(MBB); 732 LocMap::iterator I = locInts.find(Start); 733 734 // Limit to VNI's live range. 735 bool ToEnd = true; 736 if (LR && VNI) { 737 LiveInterval::Segment *Segment = LR->getSegmentContaining(Start); 738 if (!Segment || Segment->valno != VNI) { 739 if (Kills) 740 Kills->push_back(Start); 741 return; 742 } 743 if (Segment->end < Stop) { 744 Stop = Segment->end; 745 ToEnd = false; 746 } 747 } 748 749 // There could already be a short def at Start. 750 if (I.valid() && I.start() <= Start) { 751 // Stop when meeting a different location or an already extended interval. 752 Start = Start.getNextSlot(); 753 if (I.value() != DbgValue || I.stop() != Start) 754 return; 755 // This is a one-slot placeholder. Just skip it. 756 ++I; 757 } 758 759 // Limited by the next def. 760 if (I.valid() && I.start() < Stop) 761 Stop = I.start(); 762 // Limited by VNI's live range. 763 else if (!ToEnd && Kills) 764 Kills->push_back(Stop); 765 766 if (Start < Stop) 767 I.insert(Start, Stop, DbgValue); 768 } 769 770 void UserValue::addDefsFromCopies( 771 LiveInterval *LI, DbgVariableValue DbgValue, 772 const SmallVectorImpl<SlotIndex> &Kills, 773 SmallVectorImpl<std::pair<SlotIndex, DbgVariableValue>> &NewDefs, 774 MachineRegisterInfo &MRI, LiveIntervals &LIS) { 775 if (Kills.empty()) 776 return; 777 // Don't track copies from physregs, there are too many uses. 778 if (!Register::isVirtualRegister(LI->reg)) 779 return; 780 781 // Collect all the (vreg, valno) pairs that are copies of LI. 782 SmallVector<std::pair<LiveInterval*, const VNInfo*>, 8> CopyValues; 783 for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) { 784 MachineInstr *MI = MO.getParent(); 785 // Copies of the full value. 786 if (MO.getSubReg() || !MI->isCopy()) 787 continue; 788 Register DstReg = MI->getOperand(0).getReg(); 789 790 // Don't follow copies to physregs. These are usually setting up call 791 // arguments, and the argument registers are always call clobbered. We are 792 // better off in the source register which could be a callee-saved register, 793 // or it could be spilled. 794 if (!Register::isVirtualRegister(DstReg)) 795 continue; 796 797 // Is the value extended to reach this copy? If not, another def may be 798 // blocking it, or we are looking at a wrong value of LI. 799 SlotIndex Idx = LIS.getInstructionIndex(*MI); 800 LocMap::iterator I = locInts.find(Idx.getRegSlot(true)); 801 if (!I.valid() || I.value() != DbgValue) 802 continue; 803 804 if (!LIS.hasInterval(DstReg)) 805 continue; 806 LiveInterval *DstLI = &LIS.getInterval(DstReg); 807 const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot()); 808 assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value"); 809 CopyValues.push_back(std::make_pair(DstLI, DstVNI)); 810 } 811 812 if (CopyValues.empty()) 813 return; 814 815 LLVM_DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI 816 << '\n'); 817 818 // Try to add defs of the copied values for each kill point. 819 for (unsigned i = 0, e = Kills.size(); i != e; ++i) { 820 SlotIndex Idx = Kills[i]; 821 for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) { 822 LiveInterval *DstLI = CopyValues[j].first; 823 const VNInfo *DstVNI = CopyValues[j].second; 824 if (DstLI->getVNInfoAt(Idx) != DstVNI) 825 continue; 826 // Check that there isn't already a def at Idx 827 LocMap::iterator I = locInts.find(Idx); 828 if (I.valid() && I.start() <= Idx) 829 continue; 830 LLVM_DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #" 831 << DstVNI->id << " in " << *DstLI << '\n'); 832 MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def); 833 assert(CopyMI && CopyMI->isCopy() && "Bad copy value"); 834 unsigned LocNo = getLocationNo(CopyMI->getOperand(0)); 835 DbgVariableValue NewValue = DbgValue.changeLocNo(LocNo); 836 I.insert(Idx, Idx.getNextSlot(), NewValue); 837 NewDefs.push_back(std::make_pair(Idx, NewValue)); 838 break; 839 } 840 } 841 } 842 843 void UserValue::computeIntervals(MachineRegisterInfo &MRI, 844 const TargetRegisterInfo &TRI, 845 LiveIntervals &LIS, LexicalScopes &LS) { 846 SmallVector<std::pair<SlotIndex, DbgVariableValue>, 16> Defs; 847 848 // Collect all defs to be extended (Skipping undefs). 849 for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) 850 if (!I.value().isUndef()) 851 Defs.push_back(std::make_pair(I.start(), I.value())); 852 853 // Extend all defs, and possibly add new ones along the way. 854 for (unsigned i = 0; i != Defs.size(); ++i) { 855 SlotIndex Idx = Defs[i].first; 856 DbgVariableValue DbgValue = Defs[i].second; 857 const MachineOperand &LocMO = locations[DbgValue.getLocNo()]; 858 859 if (!LocMO.isReg()) { 860 extendDef(Idx, DbgValue, nullptr, nullptr, nullptr, LIS); 861 continue; 862 } 863 864 // Register locations are constrained to where the register value is live. 865 if (Register::isVirtualRegister(LocMO.getReg())) { 866 LiveInterval *LI = nullptr; 867 const VNInfo *VNI = nullptr; 868 if (LIS.hasInterval(LocMO.getReg())) { 869 LI = &LIS.getInterval(LocMO.getReg()); 870 VNI = LI->getVNInfoAt(Idx); 871 } 872 SmallVector<SlotIndex, 16> Kills; 873 extendDef(Idx, DbgValue, LI, VNI, &Kills, LIS); 874 // FIXME: Handle sub-registers in addDefsFromCopies. The problem is that 875 // if the original location for example is %vreg0:sub_hi, and we find a 876 // full register copy in addDefsFromCopies (at the moment it only handles 877 // full register copies), then we must add the sub1 sub-register index to 878 // the new location. However, that is only possible if the new virtual 879 // register is of the same regclass (or if there is an equivalent 880 // sub-register in that regclass). For now, simply skip handling copies if 881 // a sub-register is involved. 882 if (LI && !LocMO.getSubReg()) 883 addDefsFromCopies(LI, DbgValue, Kills, Defs, MRI, LIS); 884 continue; 885 } 886 887 // For physregs, we only mark the start slot idx. DwarfDebug will see it 888 // as if the DBG_VALUE is valid up until the end of the basic block, or 889 // the next def of the physical register. So we do not need to extend the 890 // range. It might actually happen that the DBG_VALUE is the last use of 891 // the physical register (e.g. if this is an unused input argument to a 892 // function). 893 } 894 895 // The computed intervals may extend beyond the range of the debug 896 // location's lexical scope. In this case, splitting of an interval 897 // can result in an interval outside of the scope being created, 898 // causing extra unnecessary DBG_VALUEs to be emitted. To prevent 899 // this, trim the intervals to the lexical scope. 900 901 LexicalScope *Scope = LS.findLexicalScope(dl); 902 if (!Scope) 903 return; 904 905 SlotIndex PrevEnd; 906 LocMap::iterator I = locInts.begin(); 907 908 // Iterate over the lexical scope ranges. Each time round the loop 909 // we check the intervals for overlap with the end of the previous 910 // range and the start of the next. The first range is handled as 911 // a special case where there is no PrevEnd. 912 for (const InsnRange &Range : Scope->getRanges()) { 913 SlotIndex RStart = LIS.getInstructionIndex(*Range.first); 914 SlotIndex REnd = LIS.getInstructionIndex(*Range.second); 915 916 // Variable locations at the first instruction of a block should be 917 // based on the block's SlotIndex, not the first instruction's index. 918 if (Range.first == Range.first->getParent()->begin()) 919 RStart = LIS.getSlotIndexes()->getIndexBefore(*Range.first); 920 921 // At the start of each iteration I has been advanced so that 922 // I.stop() >= PrevEnd. Check for overlap. 923 if (PrevEnd && I.start() < PrevEnd) { 924 SlotIndex IStop = I.stop(); 925 DbgVariableValue DbgValue = I.value(); 926 927 // Stop overlaps previous end - trim the end of the interval to 928 // the scope range. 929 I.setStopUnchecked(PrevEnd); 930 ++I; 931 932 // If the interval also overlaps the start of the "next" (i.e. 933 // current) range create a new interval for the remainder (which 934 // may be further trimmed). 935 if (RStart < IStop) 936 I.insert(RStart, IStop, DbgValue); 937 } 938 939 // Advance I so that I.stop() >= RStart, and check for overlap. 940 I.advanceTo(RStart); 941 if (!I.valid()) 942 return; 943 944 if (I.start() < RStart) { 945 // Interval start overlaps range - trim to the scope range. 946 I.setStartUnchecked(RStart); 947 // Remember that this interval was trimmed. 948 trimmedDefs.insert(RStart); 949 } 950 951 // The end of a lexical scope range is the last instruction in the 952 // range. To convert to an interval we need the index of the 953 // instruction after it. 954 REnd = REnd.getNextIndex(); 955 956 // Advance I to first interval outside current range. 957 I.advanceTo(REnd); 958 if (!I.valid()) 959 return; 960 961 PrevEnd = REnd; 962 } 963 964 // Check for overlap with end of final range. 965 if (PrevEnd && I.start() < PrevEnd) 966 I.setStopUnchecked(PrevEnd); 967 } 968 969 void LDVImpl::computeIntervals() { 970 LexicalScopes LS; 971 LS.initialize(*MF); 972 973 for (unsigned i = 0, e = userValues.size(); i != e; ++i) { 974 userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS); 975 userValues[i]->mapVirtRegs(this); 976 } 977 } 978 979 bool LDVImpl::runOnMachineFunction(MachineFunction &mf) { 980 clear(); 981 MF = &mf; 982 LIS = &pass.getAnalysis<LiveIntervals>(); 983 TRI = mf.getSubtarget().getRegisterInfo(); 984 LLVM_DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: " 985 << mf.getName() << " **********\n"); 986 987 bool Changed = collectDebugValues(mf); 988 computeIntervals(); 989 LLVM_DEBUG(print(dbgs())); 990 ModifiedMF = Changed; 991 return Changed; 992 } 993 994 static void removeDebugValues(MachineFunction &mf) { 995 for (MachineBasicBlock &MBB : mf) { 996 for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) { 997 if (!MBBI->isDebugValue()) { 998 ++MBBI; 999 continue; 1000 } 1001 MBBI = MBB.erase(MBBI); 1002 } 1003 } 1004 } 1005 1006 bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) { 1007 if (!EnableLDV) 1008 return false; 1009 if (!mf.getFunction().getSubprogram()) { 1010 removeDebugValues(mf); 1011 return false; 1012 } 1013 if (!pImpl) 1014 pImpl = new LDVImpl(this); 1015 return static_cast<LDVImpl*>(pImpl)->runOnMachineFunction(mf); 1016 } 1017 1018 void LiveDebugVariables::releaseMemory() { 1019 if (pImpl) 1020 static_cast<LDVImpl*>(pImpl)->clear(); 1021 } 1022 1023 LiveDebugVariables::~LiveDebugVariables() { 1024 if (pImpl) 1025 delete static_cast<LDVImpl*>(pImpl); 1026 } 1027 1028 //===----------------------------------------------------------------------===// 1029 // Live Range Splitting 1030 //===----------------------------------------------------------------------===// 1031 1032 bool 1033 UserValue::splitLocation(unsigned OldLocNo, ArrayRef<Register> NewRegs, 1034 LiveIntervals& LIS) { 1035 LLVM_DEBUG({ 1036 dbgs() << "Splitting Loc" << OldLocNo << '\t'; 1037 print(dbgs(), nullptr); 1038 }); 1039 bool DidChange = false; 1040 LocMap::iterator LocMapI; 1041 LocMapI.setMap(locInts); 1042 for (unsigned i = 0; i != NewRegs.size(); ++i) { 1043 LiveInterval *LI = &LIS.getInterval(NewRegs[i]); 1044 if (LI->empty()) 1045 continue; 1046 1047 // Don't allocate the new LocNo until it is needed. 1048 unsigned NewLocNo = UndefLocNo; 1049 1050 // Iterate over the overlaps between locInts and LI. 1051 LocMapI.find(LI->beginIndex()); 1052 if (!LocMapI.valid()) 1053 continue; 1054 LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start()); 1055 LiveInterval::iterator LIE = LI->end(); 1056 while (LocMapI.valid() && LII != LIE) { 1057 // At this point, we know that LocMapI.stop() > LII->start. 1058 LII = LI->advanceTo(LII, LocMapI.start()); 1059 if (LII == LIE) 1060 break; 1061 1062 // Now LII->end > LocMapI.start(). Do we have an overlap? 1063 if (LocMapI.value().getLocNo() == OldLocNo && 1064 LII->start < LocMapI.stop()) { 1065 // Overlapping correct location. Allocate NewLocNo now. 1066 if (NewLocNo == UndefLocNo) { 1067 MachineOperand MO = MachineOperand::CreateReg(LI->reg, false); 1068 MO.setSubReg(locations[OldLocNo].getSubReg()); 1069 NewLocNo = getLocationNo(MO); 1070 DidChange = true; 1071 } 1072 1073 SlotIndex LStart = LocMapI.start(); 1074 SlotIndex LStop = LocMapI.stop(); 1075 DbgVariableValue OldDbgValue = LocMapI.value(); 1076 1077 // Trim LocMapI down to the LII overlap. 1078 if (LStart < LII->start) 1079 LocMapI.setStartUnchecked(LII->start); 1080 if (LStop > LII->end) 1081 LocMapI.setStopUnchecked(LII->end); 1082 1083 // Change the value in the overlap. This may trigger coalescing. 1084 LocMapI.setValue(OldDbgValue.changeLocNo(NewLocNo)); 1085 1086 // Re-insert any removed OldDbgValue ranges. 1087 if (LStart < LocMapI.start()) { 1088 LocMapI.insert(LStart, LocMapI.start(), OldDbgValue); 1089 ++LocMapI; 1090 assert(LocMapI.valid() && "Unexpected coalescing"); 1091 } 1092 if (LStop > LocMapI.stop()) { 1093 ++LocMapI; 1094 LocMapI.insert(LII->end, LStop, OldDbgValue); 1095 --LocMapI; 1096 } 1097 } 1098 1099 // Advance to the next overlap. 1100 if (LII->end < LocMapI.stop()) { 1101 if (++LII == LIE) 1102 break; 1103 LocMapI.advanceTo(LII->start); 1104 } else { 1105 ++LocMapI; 1106 if (!LocMapI.valid()) 1107 break; 1108 LII = LI->advanceTo(LII, LocMapI.start()); 1109 } 1110 } 1111 } 1112 1113 // Finally, remove OldLocNo unless it is still used by some interval in the 1114 // locInts map. One case when OldLocNo still is in use is when the register 1115 // has been spilled. In such situations the spilled register is kept as a 1116 // location until rewriteLocations is called (VirtRegMap is mapping the old 1117 // register to the spill slot). So for a while we can have locations that map 1118 // to virtual registers that have been removed from both the MachineFunction 1119 // and from LiveIntervals. 1120 // 1121 // We may also just be using the location for a value with a different 1122 // expression. 1123 removeLocationIfUnused(OldLocNo); 1124 1125 LLVM_DEBUG({ 1126 dbgs() << "Split result: \t"; 1127 print(dbgs(), nullptr); 1128 }); 1129 return DidChange; 1130 } 1131 1132 bool 1133 UserValue::splitRegister(Register OldReg, ArrayRef<Register> NewRegs, 1134 LiveIntervals &LIS) { 1135 bool DidChange = false; 1136 // Split locations referring to OldReg. Iterate backwards so splitLocation can 1137 // safely erase unused locations. 1138 for (unsigned i = locations.size(); i ; --i) { 1139 unsigned LocNo = i-1; 1140 const MachineOperand *Loc = &locations[LocNo]; 1141 if (!Loc->isReg() || Loc->getReg() != OldReg) 1142 continue; 1143 DidChange |= splitLocation(LocNo, NewRegs, LIS); 1144 } 1145 return DidChange; 1146 } 1147 1148 void LDVImpl::splitRegister(Register OldReg, ArrayRef<Register> NewRegs) { 1149 bool DidChange = false; 1150 for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext()) 1151 DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS); 1152 1153 if (!DidChange) 1154 return; 1155 1156 // Map all of the new virtual registers. 1157 UserValue *UV = lookupVirtReg(OldReg); 1158 for (unsigned i = 0; i != NewRegs.size(); ++i) 1159 mapVirtReg(NewRegs[i], UV); 1160 } 1161 1162 void LiveDebugVariables:: 1163 splitRegister(Register OldReg, ArrayRef<Register> NewRegs, LiveIntervals &LIS) { 1164 if (pImpl) 1165 static_cast<LDVImpl*>(pImpl)->splitRegister(OldReg, NewRegs); 1166 } 1167 1168 void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF, 1169 const TargetInstrInfo &TII, 1170 const TargetRegisterInfo &TRI, 1171 SpillOffsetMap &SpillOffsets) { 1172 // Build a set of new locations with new numbers so we can coalesce our 1173 // IntervalMap if two vreg intervals collapse to the same physical location. 1174 // Use MapVector instead of SetVector because MapVector::insert returns the 1175 // position of the previously or newly inserted element. The boolean value 1176 // tracks if the location was produced by a spill. 1177 // FIXME: This will be problematic if we ever support direct and indirect 1178 // frame index locations, i.e. expressing both variables in memory and 1179 // 'int x, *px = &x'. The "spilled" bit must become part of the location. 1180 MapVector<MachineOperand, std::pair<bool, unsigned>> NewLocations; 1181 SmallVector<unsigned, 4> LocNoMap(locations.size()); 1182 for (unsigned I = 0, E = locations.size(); I != E; ++I) { 1183 bool Spilled = false; 1184 unsigned SpillOffset = 0; 1185 MachineOperand Loc = locations[I]; 1186 // Only virtual registers are rewritten. 1187 if (Loc.isReg() && Loc.getReg() && 1188 Register::isVirtualRegister(Loc.getReg())) { 1189 Register VirtReg = Loc.getReg(); 1190 if (VRM.isAssignedReg(VirtReg) && 1191 Register::isPhysicalRegister(VRM.getPhys(VirtReg))) { 1192 // This can create a %noreg operand in rare cases when the sub-register 1193 // index is no longer available. That means the user value is in a 1194 // non-existent sub-register, and %noreg is exactly what we want. 1195 Loc.substPhysReg(VRM.getPhys(VirtReg), TRI); 1196 } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) { 1197 // Retrieve the stack slot offset. 1198 unsigned SpillSize; 1199 const MachineRegisterInfo &MRI = MF.getRegInfo(); 1200 const TargetRegisterClass *TRC = MRI.getRegClass(VirtReg); 1201 bool Success = TII.getStackSlotRange(TRC, Loc.getSubReg(), SpillSize, 1202 SpillOffset, MF); 1203 1204 // FIXME: Invalidate the location if the offset couldn't be calculated. 1205 (void)Success; 1206 1207 Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg)); 1208 Spilled = true; 1209 } else { 1210 Loc.setReg(0); 1211 Loc.setSubReg(0); 1212 } 1213 } 1214 1215 // Insert this location if it doesn't already exist and record a mapping 1216 // from the old number to the new number. 1217 auto InsertResult = NewLocations.insert({Loc, {Spilled, SpillOffset}}); 1218 unsigned NewLocNo = std::distance(NewLocations.begin(), InsertResult.first); 1219 LocNoMap[I] = NewLocNo; 1220 } 1221 1222 // Rewrite the locations and record the stack slot offsets for spills. 1223 locations.clear(); 1224 SpillOffsets.clear(); 1225 for (auto &Pair : NewLocations) { 1226 bool Spilled; 1227 unsigned SpillOffset; 1228 std::tie(Spilled, SpillOffset) = Pair.second; 1229 locations.push_back(Pair.first); 1230 if (Spilled) { 1231 unsigned NewLocNo = std::distance(&*NewLocations.begin(), &Pair); 1232 SpillOffsets[NewLocNo] = SpillOffset; 1233 } 1234 } 1235 1236 // Update the interval map, but only coalesce left, since intervals to the 1237 // right use the old location numbers. This should merge two contiguous 1238 // DBG_VALUE intervals with different vregs that were allocated to the same 1239 // physical register. 1240 for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) { 1241 DbgVariableValue DbgValue = I.value(); 1242 // Undef values don't exist in locations (and thus not in LocNoMap either) 1243 // so skip over them. See getLocationNo(). 1244 if (DbgValue.isUndef()) 1245 continue; 1246 unsigned NewLocNo = LocNoMap[DbgValue.getLocNo()]; 1247 I.setValueUnchecked(DbgValue.changeLocNo(NewLocNo)); 1248 I.setStart(I.start()); 1249 } 1250 } 1251 1252 /// Find an iterator for inserting a DBG_VALUE instruction. 1253 static MachineBasicBlock::iterator 1254 findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, 1255 LiveIntervals &LIS) { 1256 SlotIndex Start = LIS.getMBBStartIdx(MBB); 1257 Idx = Idx.getBaseIndex(); 1258 1259 // Try to find an insert location by going backwards from Idx. 1260 MachineInstr *MI; 1261 while (!(MI = LIS.getInstructionFromIndex(Idx))) { 1262 // We've reached the beginning of MBB. 1263 if (Idx == Start) { 1264 MachineBasicBlock::iterator I = MBB->SkipPHIsLabelsAndDebug(MBB->begin()); 1265 return I; 1266 } 1267 Idx = Idx.getPrevIndex(); 1268 } 1269 1270 // Don't insert anything after the first terminator, though. 1271 return MI->isTerminator() ? MBB->getFirstTerminator() : 1272 std::next(MachineBasicBlock::iterator(MI)); 1273 } 1274 1275 /// Find an iterator for inserting the next DBG_VALUE instruction 1276 /// (or end if no more insert locations found). 1277 static MachineBasicBlock::iterator 1278 findNextInsertLocation(MachineBasicBlock *MBB, 1279 MachineBasicBlock::iterator I, 1280 SlotIndex StopIdx, MachineOperand &LocMO, 1281 LiveIntervals &LIS, 1282 const TargetRegisterInfo &TRI) { 1283 if (!LocMO.isReg()) 1284 return MBB->instr_end(); 1285 Register Reg = LocMO.getReg(); 1286 1287 // Find the next instruction in the MBB that define the register Reg. 1288 while (I != MBB->end() && !I->isTerminator()) { 1289 if (!LIS.isNotInMIMap(*I) && 1290 SlotIndex::isEarlierEqualInstr(StopIdx, LIS.getInstructionIndex(*I))) 1291 break; 1292 if (I->definesRegister(Reg, &TRI)) 1293 // The insert location is directly after the instruction/bundle. 1294 return std::next(I); 1295 ++I; 1296 } 1297 return MBB->end(); 1298 } 1299 1300 void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx, 1301 SlotIndex StopIdx, DbgVariableValue DbgValue, 1302 bool Spilled, unsigned SpillOffset, 1303 LiveIntervals &LIS, const TargetInstrInfo &TII, 1304 const TargetRegisterInfo &TRI) { 1305 SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB); 1306 // Only search within the current MBB. 1307 StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx; 1308 MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS); 1309 // Undef values don't exist in locations so create new "noreg" register MOs 1310 // for them. See getLocationNo(). 1311 MachineOperand MO = 1312 !DbgValue.isUndef() 1313 ? locations[DbgValue.getLocNo()] 1314 : MachineOperand::CreateReg( 1315 /* Reg */ 0, /* isDef */ false, /* isImp */ false, 1316 /* isKill */ false, /* isDead */ false, 1317 /* isUndef */ false, /* isEarlyClobber */ false, 1318 /* SubReg */ 0, /* isDebug */ true); 1319 1320 ++NumInsertedDebugValues; 1321 1322 assert(cast<DILocalVariable>(Variable) 1323 ->isValidLocationForIntrinsic(getDebugLoc()) && 1324 "Expected inlined-at fields to agree"); 1325 1326 // If the location was spilled, the new DBG_VALUE will be indirect. If the 1327 // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate 1328 // that the original virtual register was a pointer. Also, add the stack slot 1329 // offset for the spilled register to the expression. 1330 const DIExpression *Expr = DbgValue.getExpression(); 1331 uint8_t DIExprFlags = DIExpression::ApplyOffset; 1332 bool IsIndirect = DbgValue.getWasIndirect(); 1333 if (Spilled) { 1334 if (IsIndirect) 1335 DIExprFlags |= DIExpression::DerefAfter; 1336 Expr = 1337 DIExpression::prepend(Expr, DIExprFlags, SpillOffset); 1338 IsIndirect = true; 1339 } 1340 1341 assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index"); 1342 1343 do { 1344 BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE), 1345 IsIndirect, MO, Variable, Expr); 1346 1347 // Continue and insert DBG_VALUES after every redefinition of register 1348 // associated with the debug value within the range 1349 I = findNextInsertLocation(MBB, I, StopIdx, MO, LIS, TRI); 1350 } while (I != MBB->end()); 1351 } 1352 1353 void UserLabel::insertDebugLabel(MachineBasicBlock *MBB, SlotIndex Idx, 1354 LiveIntervals &LIS, 1355 const TargetInstrInfo &TII) { 1356 MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS); 1357 ++NumInsertedDebugLabels; 1358 BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_LABEL)) 1359 .addMetadata(Label); 1360 } 1361 1362 void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, 1363 const TargetInstrInfo &TII, 1364 const TargetRegisterInfo &TRI, 1365 const SpillOffsetMap &SpillOffsets) { 1366 MachineFunction::iterator MFEnd = VRM->getMachineFunction().end(); 1367 1368 for (LocMap::const_iterator I = locInts.begin(); I.valid();) { 1369 SlotIndex Start = I.start(); 1370 SlotIndex Stop = I.stop(); 1371 DbgVariableValue DbgValue = I.value(); 1372 auto SpillIt = !DbgValue.isUndef() ? SpillOffsets.find(DbgValue.getLocNo()) 1373 : SpillOffsets.end(); 1374 bool Spilled = SpillIt != SpillOffsets.end(); 1375 unsigned SpillOffset = Spilled ? SpillIt->second : 0; 1376 1377 // If the interval start was trimmed to the lexical scope insert the 1378 // DBG_VALUE at the previous index (otherwise it appears after the 1379 // first instruction in the range). 1380 if (trimmedDefs.count(Start)) 1381 Start = Start.getPrevIndex(); 1382 1383 LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop 1384 << "):" << DbgValue.getLocNo()); 1385 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); 1386 SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB); 1387 1388 LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd); 1389 insertDebugValue(&*MBB, Start, Stop, DbgValue, Spilled, SpillOffset, LIS, 1390 TII, TRI); 1391 // This interval may span multiple basic blocks. 1392 // Insert a DBG_VALUE into each one. 1393 while (Stop > MBBEnd) { 1394 // Move to the next block. 1395 Start = MBBEnd; 1396 if (++MBB == MFEnd) 1397 break; 1398 MBBEnd = LIS.getMBBEndIdx(&*MBB); 1399 LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd); 1400 insertDebugValue(&*MBB, Start, Stop, DbgValue, Spilled, SpillOffset, LIS, 1401 TII, TRI); 1402 } 1403 LLVM_DEBUG(dbgs() << '\n'); 1404 if (MBB == MFEnd) 1405 break; 1406 1407 ++I; 1408 } 1409 } 1410 1411 void UserLabel::emitDebugLabel(LiveIntervals &LIS, const TargetInstrInfo &TII) { 1412 LLVM_DEBUG(dbgs() << "\t" << loc); 1413 MachineFunction::iterator MBB = LIS.getMBBFromIndex(loc)->getIterator(); 1414 1415 LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB)); 1416 insertDebugLabel(&*MBB, loc, LIS, TII); 1417 1418 LLVM_DEBUG(dbgs() << '\n'); 1419 } 1420 1421 void LDVImpl::emitDebugValues(VirtRegMap *VRM) { 1422 LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n"); 1423 if (!MF) 1424 return; 1425 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); 1426 SpillOffsetMap SpillOffsets; 1427 for (auto &userValue : userValues) { 1428 LLVM_DEBUG(userValue->print(dbgs(), TRI)); 1429 userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets); 1430 userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets); 1431 } 1432 LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n"); 1433 for (auto &userLabel : userLabels) { 1434 LLVM_DEBUG(userLabel->print(dbgs(), TRI)); 1435 userLabel->emitDebugLabel(*LIS, *TII); 1436 } 1437 EmitDone = true; 1438 } 1439 1440 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) { 1441 if (pImpl) 1442 static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM); 1443 } 1444 1445 bool LiveDebugVariables::doInitialization(Module &M) { 1446 return Pass::doInitialization(M); 1447 } 1448 1449 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1450 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const { 1451 if (pImpl) 1452 static_cast<LDVImpl*>(pImpl)->print(dbgs()); 1453 } 1454 #endif 1455