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