1 //===------ LiveDebugValues.cpp - Tracking Debug Value MIs ----------------===// 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 pass implements a data flow analysis that propagates debug location 11 /// information by inserting additional DBG_VALUE instructions into the machine 12 /// instruction stream. The pass internally builds debug location liveness 13 /// ranges to determine the points where additional DBG_VALUEs need to be 14 /// inserted. 15 /// 16 /// This is a separate pass from DbgValueHistoryCalculator to facilitate 17 /// testing and improve modularity. 18 /// 19 //===----------------------------------------------------------------------===// 20 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/ADT/PostOrderIterator.h" 23 #include "llvm/ADT/SmallPtrSet.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include "llvm/CodeGen/MachineFunction.h" 26 #include "llvm/CodeGen/MachineFunctionPass.h" 27 #include "llvm/CodeGen/MachineInstrBuilder.h" 28 #include "llvm/CodeGen/Passes.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include "llvm/Target/TargetInstrInfo.h" 33 #include "llvm/Target/TargetRegisterInfo.h" 34 #include "llvm/Target/TargetSubtargetInfo.h" 35 #include <queue> 36 #include <list> 37 38 using namespace llvm; 39 40 #define DEBUG_TYPE "live-debug-values" 41 42 STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); 43 44 namespace { 45 46 class LiveDebugValues : public MachineFunctionPass { 47 48 private: 49 const TargetRegisterInfo *TRI; 50 const TargetInstrInfo *TII; 51 52 typedef std::pair<const DILocalVariable *, const DILocation *> 53 InlinedVariable; 54 55 /// A potentially inlined instance of a variable. 56 struct DebugVariable { 57 const DILocalVariable *Var; 58 const DILocation *InlinedAt; 59 60 DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt) 61 : Var(_var), InlinedAt(_inlinedAt) {} 62 63 bool operator==(const DebugVariable &DV) const { 64 return (Var == DV.Var) && (InlinedAt == DV.InlinedAt); 65 } 66 }; 67 68 /// Member variables and functions for Range Extension across basic blocks. 69 struct VarLoc { 70 DebugVariable Var; 71 const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr. 72 73 VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {} 74 75 bool operator==(const VarLoc &V) const; 76 }; 77 78 typedef std::list<VarLoc> VarLocList; 79 typedef SmallDenseMap<const MachineBasicBlock *, VarLocList> VarLocInMBB; 80 81 void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges); 82 void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges); 83 bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges, 84 VarLocInMBB &OutLocs); 85 bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs); 86 87 bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs); 88 89 bool ExtendRanges(MachineFunction &MF); 90 91 public: 92 static char ID; 93 94 /// Default construct and initialize the pass. 95 LiveDebugValues(); 96 97 /// Tell the pass manager which passes we depend on and what 98 /// information we preserve. 99 void getAnalysisUsage(AnalysisUsage &AU) const override; 100 101 /// Print to ostream with a message. 102 void printVarLocInMBB(const VarLocInMBB &V, const char *msg, 103 raw_ostream &Out) const; 104 105 /// Calculate the liveness information for the given machine function. 106 bool runOnMachineFunction(MachineFunction &MF) override; 107 }; 108 } // namespace 109 110 //===----------------------------------------------------------------------===// 111 // Implementation 112 //===----------------------------------------------------------------------===// 113 114 char LiveDebugValues::ID = 0; 115 char &llvm::LiveDebugValuesID = LiveDebugValues::ID; 116 INITIALIZE_PASS(LiveDebugValues, "livedebugvalues", "Live DEBUG_VALUE analysis", 117 false, false) 118 119 /// Default construct and initialize the pass. 120 LiveDebugValues::LiveDebugValues() : MachineFunctionPass(ID) { 121 initializeLiveDebugValuesPass(*PassRegistry::getPassRegistry()); 122 } 123 124 /// Tell the pass manager which passes we depend on and what information we 125 /// preserve. 126 void LiveDebugValues::getAnalysisUsage(AnalysisUsage &AU) const { 127 MachineFunctionPass::getAnalysisUsage(AU); 128 } 129 130 // \brief If @MI is a DBG_VALUE with debug value described by a defined 131 // register, returns the number of this register. In the other case, returns 0. 132 static unsigned isDescribedByReg(const MachineInstr &MI) { 133 assert(MI.isDebugValue()); 134 assert(MI.getNumOperands() == 4); 135 // If location of variable is described using a register (directly or 136 // indirecltly), this register is always a first operand. 137 return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0; 138 } 139 140 // \brief This function takes two DBG_VALUE instructions and returns true 141 // if their offsets are equal; otherwise returns false. 142 static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) { 143 assert(MI1.isDebugValue()); 144 assert(MI1.getNumOperands() == 4); 145 146 assert(MI2.isDebugValue()); 147 assert(MI2.getNumOperands() == 4); 148 149 if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue()) 150 return true; 151 152 // Check if both MIs are indirect and they are equal. 153 if (MI1.isIndirectDebugValue() && MI2.isIndirectDebugValue()) 154 return MI1.getOperand(1).getImm() == MI2.getOperand(1).getImm(); 155 156 return false; 157 } 158 159 //===----------------------------------------------------------------------===// 160 // Debug Range Extension Implementation 161 //===----------------------------------------------------------------------===// 162 163 void LiveDebugValues::printVarLocInMBB(const VarLocInMBB &V, const char *msg, 164 raw_ostream &Out) const { 165 Out << "Printing " << msg << ":\n"; 166 for (const auto &L : V) { 167 Out << "MBB: " << L.first->getName() << ":\n"; 168 for (const auto &VLL : L.second) { 169 Out << " Var: " << VLL.Var.Var->getName(); 170 Out << " MI: "; 171 (*VLL.MI).dump(); 172 Out << "\n"; 173 } 174 } 175 Out << "\n"; 176 } 177 178 bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const { 179 return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) && 180 (areOffsetsEqual(*MI, *V.MI)); 181 } 182 183 /// End all previous ranges related to @MI and start a new range from @MI 184 /// if it is a DBG_VALUE instr. 185 void LiveDebugValues::transferDebugValue(MachineInstr &MI, 186 VarLocList &OpenRanges) { 187 if (!MI.isDebugValue()) 188 return; 189 const DILocalVariable *RawVar = MI.getDebugVariable(); 190 assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) && 191 "Expected inlined-at fields to agree"); 192 DebugVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt()); 193 194 // End all previous ranges of Var. 195 OpenRanges.erase( 196 std::remove_if(OpenRanges.begin(), OpenRanges.end(), 197 [&](const VarLoc &V) { return (Var == V.Var); }), 198 OpenRanges.end()); 199 200 // Add Var to OpenRanges from this DBG_VALUE. 201 // TODO: Currently handles DBG_VALUE which has only reg as location. 202 if (isDescribedByReg(MI)) { 203 VarLoc V(Var, &MI); 204 OpenRanges.push_back(std::move(V)); 205 } 206 } 207 208 /// A definition of a register may mark the end of a range. 209 void LiveDebugValues::transferRegisterDef(MachineInstr &MI, 210 VarLocList &OpenRanges) { 211 for (const MachineOperand &MO : MI.operands()) { 212 if (!(MO.isReg() && MO.isDef() && MO.getReg() && 213 TRI->isPhysicalRegister(MO.getReg()))) 214 continue; 215 // Remove ranges of all aliased registers. 216 for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) 217 OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(), 218 [&](const VarLoc &V) { 219 return (*RAI == 220 isDescribedByReg(*V.MI)); 221 }), 222 OpenRanges.end()); 223 } 224 } 225 226 /// Terminate all open ranges at the end of the current basic block. 227 bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, 228 VarLocList &OpenRanges, 229 VarLocInMBB &OutLocs) { 230 bool Changed = false; 231 const MachineBasicBlock *CurMBB = MI.getParent(); 232 if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back()))) 233 return false; 234 235 if (OpenRanges.empty()) 236 return false; 237 238 if (OutLocs.find(CurMBB) == OutLocs.end()) { 239 // Create space for new Outgoing locs entries. 240 VarLocList VLL; 241 OutLocs.insert(std::make_pair(CurMBB, std::move(VLL))); 242 } 243 auto OL = OutLocs.find(CurMBB); 244 assert(OL != OutLocs.end()); 245 VarLocList &VLL = OL->second; 246 247 for (auto OR : OpenRanges) { 248 // Copy OpenRanges to OutLocs, if not already present. 249 assert(OR.MI->isDebugValue()); 250 DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump();); 251 if (std::find_if(VLL.begin(), VLL.end(), 252 [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) { 253 VLL.push_back(std::move(OR)); 254 Changed = true; 255 } 256 } 257 OpenRanges.clear(); 258 return Changed; 259 } 260 261 /// This routine creates OpenRanges and OutLocs. 262 bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges, 263 VarLocInMBB &OutLocs) { 264 bool Changed = false; 265 transferDebugValue(MI, OpenRanges); 266 transferRegisterDef(MI, OpenRanges); 267 Changed = transferTerminatorInst(MI, OpenRanges, OutLocs); 268 return Changed; 269 } 270 271 /// This routine joins the analysis results of all incoming edges in @MBB by 272 /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same 273 /// source variable in all the predecessors of @MBB reside in the same location. 274 bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, 275 VarLocInMBB &InLocs) { 276 DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n"); 277 bool Changed = false; 278 279 VarLocList InLocsT; // Temporary incoming locations. 280 281 // For all predecessors of this MBB, find the set of VarLocs that can be 282 // joined. 283 for (auto p : MBB.predecessors()) { 284 auto OL = OutLocs.find(p); 285 // Join is null in case of empty OutLocs from any of the pred. 286 if (OL == OutLocs.end()) 287 return false; 288 289 // Just copy over the Out locs to incoming locs for the first predecessor. 290 if (p == *MBB.pred_begin()) { 291 InLocsT = OL->second; 292 continue; 293 } 294 295 // Join with this predecessor. 296 VarLocList &VLL = OL->second; 297 InLocsT.erase( 298 std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) { 299 return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) { 300 return (ILT == V); 301 }) == VLL.end()); 302 }), InLocsT.end()); 303 } 304 305 if (InLocsT.empty()) 306 return false; 307 308 if (InLocs.find(&MBB) == InLocs.end()) { 309 // Create space for new Incoming locs entries. 310 VarLocList VLL; 311 InLocs.insert(std::make_pair(&MBB, std::move(VLL))); 312 } 313 auto IL = InLocs.find(&MBB); 314 assert(IL != InLocs.end()); 315 VarLocList &ILL = IL->second; 316 317 // Insert DBG_VALUE instructions, if not already inserted. 318 for (auto ILT : InLocsT) { 319 if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) { 320 return (ILT == I); 321 }) == ILL.end()) { 322 // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a 323 // new range is started for the var from the mbb's beginning by inserting 324 // a new DBG_VALUE. transfer() will end this range however appropriate. 325 const MachineInstr *DMI = ILT.MI; 326 MachineInstr *MI = 327 BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(), 328 DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0, 329 DMI->getDebugVariable(), DMI->getDebugExpression()); 330 if (DMI->isIndirectDebugValue()) 331 MI->getOperand(1).setImm(DMI->getOperand(1).getImm()); 332 DEBUG(dbgs() << "Inserted: "; MI->dump();); 333 ++NumInserted; 334 Changed = true; 335 336 VarLoc V(ILT.Var, MI); 337 ILL.push_back(std::move(V)); 338 } 339 } 340 return Changed; 341 } 342 343 /// Calculate the liveness information for the given machine function and 344 /// extend ranges across basic blocks. 345 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) { 346 347 DEBUG(dbgs() << "\nDebug Range Extension\n"); 348 349 bool Changed = false; 350 bool OLChanged = false; 351 bool MBBJoined = false; 352 353 VarLocList OpenRanges; // Ranges that are open until end of bb. 354 VarLocInMBB OutLocs; // Ranges that exist beyond bb. 355 VarLocInMBB InLocs; // Ranges that are incoming after joining. 356 357 DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; 358 DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; 359 std::priority_queue<unsigned int, std::vector<unsigned int>, 360 std::greater<unsigned int>> Worklist; 361 std::priority_queue<unsigned int, std::vector<unsigned int>, 362 std::greater<unsigned int>> Pending; 363 // Initialize every mbb with OutLocs. 364 for (auto &MBB : MF) 365 for (auto &MI : MBB) 366 transfer(MI, OpenRanges, OutLocs); 367 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs())); 368 369 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); 370 unsigned int RPONumber = 0; 371 for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) { 372 OrderToBB[RPONumber] = *RI; 373 BBToOrder[*RI] = RPONumber; 374 Worklist.push(RPONumber); 375 ++RPONumber; 376 } 377 378 // This is a standard "union of predecessor outs" dataflow problem. 379 // To solve it, we perform join() and transfer() using the two worklist method 380 // until the ranges converge. 381 // Ranges have converged when both worklists are empty. 382 while (!Worklist.empty() || !Pending.empty()) { 383 // We track what is on the pending worklist to avoid inserting the same 384 // thing twice. We could avoid this with a custom priority queue, but this 385 // is probably not worth it. 386 SmallPtrSet<MachineBasicBlock *, 16> OnPending; 387 while (!Worklist.empty()) { 388 MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; 389 Worklist.pop(); 390 MBBJoined = join(*MBB, OutLocs, InLocs); 391 392 if (MBBJoined) { 393 MBBJoined = false; 394 Changed = true; 395 for (auto &MI : *MBB) 396 OLChanged |= transfer(MI, OpenRanges, OutLocs); 397 DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs())); 398 DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs())); 399 400 if (OLChanged) { 401 OLChanged = false; 402 for (auto s : MBB->successors()) 403 if (!OnPending.count(s)) { 404 OnPending.insert(s); 405 Pending.push(BBToOrder[s]); 406 } 407 } 408 } 409 } 410 Worklist.swap(Pending); 411 // At this point, pending must be empty, since it was just the empty 412 // worklist 413 assert(Pending.empty() && "Pending should be empty"); 414 } 415 416 DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs())); 417 DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs())); 418 return Changed; 419 } 420 421 bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) { 422 TRI = MF.getSubtarget().getRegisterInfo(); 423 TII = MF.getSubtarget().getInstrInfo(); 424 425 bool Changed = false; 426 427 Changed |= ExtendRanges(MF); 428 429 return Changed; 430 } 431
