1 //===- llvm/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp -------------===// 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 #include "llvm/CodeGen/DbgEntityHistoryCalculator.h" 10 #include "llvm/ADT/BitVector.h" 11 #include "llvm/ADT/STLExtras.h" 12 #include "llvm/ADT/SmallSet.h" 13 #include "llvm/ADT/SmallVector.h" 14 #include "llvm/CodeGen/MachineBasicBlock.h" 15 #include "llvm/CodeGen/MachineFunction.h" 16 #include "llvm/CodeGen/MachineInstr.h" 17 #include "llvm/CodeGen/MachineOperand.h" 18 #include "llvm/CodeGen/TargetLowering.h" 19 #include "llvm/CodeGen/TargetRegisterInfo.h" 20 #include "llvm/CodeGen/TargetSubtargetInfo.h" 21 #include "llvm/IR/DebugInfoMetadata.h" 22 #include "llvm/IR/DebugLoc.h" 23 #include "llvm/MC/MCRegisterInfo.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include <cassert> 27 #include <map> 28 #include <utility> 29 30 using namespace llvm; 31 32 #define DEBUG_TYPE "dwarfdebug" 33 34 namespace { 35 using EntryIndex = DbgValueHistoryMap::EntryIndex; 36 } 37 38 // If @MI is a DBG_VALUE with debug value described by a 39 // defined register, returns the number of this register. 40 // In the other case, returns 0. 41 static Register isDescribedByReg(const MachineInstr &MI) { 42 assert(MI.isDebugValue()); 43 assert(MI.getNumOperands() == 4); 44 // If the location of variable is an entry value (DW_OP_LLVM_entry_value) 45 // do not consider it as a register location. 46 if (MI.getDebugExpression()->isEntryValue()) 47 return 0; 48 // If location of variable is described using a register (directly or 49 // indirectly), this register is always a first operand. 50 return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg() 51 : Register(); 52 } 53 54 bool DbgValueHistoryMap::startDbgValue(InlinedEntity Var, 55 const MachineInstr &MI, 56 EntryIndex &NewIndex) { 57 // Instruction range should start with a DBG_VALUE instruction for the 58 // variable. 59 assert(MI.isDebugValue() && "not a DBG_VALUE"); 60 auto &Entries = VarEntries[Var]; 61 if (!Entries.empty() && Entries.back().isDbgValue() && 62 !Entries.back().isClosed() && 63 Entries.back().getInstr()->isIdenticalTo(MI)) { 64 LLVM_DEBUG(dbgs() << "Coalescing identical DBG_VALUE entries:\n" 65 << "\t" << Entries.back().getInstr() << "\t" << MI 66 << "\n"); 67 return false; 68 } 69 Entries.emplace_back(&MI, Entry::DbgValue); 70 NewIndex = Entries.size() - 1; 71 return true; 72 } 73 74 EntryIndex DbgValueHistoryMap::startClobber(InlinedEntity Var, 75 const MachineInstr &MI) { 76 auto &Entries = VarEntries[Var]; 77 // If an instruction clobbers multiple registers that the variable is 78 // described by, then we may have already created a clobbering instruction. 79 if (Entries.back().isClobber() && Entries.back().getInstr() == &MI) 80 return Entries.size() - 1; 81 Entries.emplace_back(&MI, Entry::Clobber); 82 return Entries.size() - 1; 83 } 84 85 void DbgValueHistoryMap::Entry::endEntry(EntryIndex Index) { 86 // For now, instruction ranges are not allowed to cross basic block 87 // boundaries. 88 assert(isDbgValue() && "Setting end index for non-debug value"); 89 assert(!isClosed() && "End index has already been set"); 90 EndIndex = Index; 91 } 92 93 void DbgLabelInstrMap::addInstr(InlinedEntity Label, const MachineInstr &MI) { 94 assert(MI.isDebugLabel() && "not a DBG_LABEL"); 95 LabelInstr[Label] = &MI; 96 } 97 98 namespace { 99 100 // Maps physreg numbers to the variables they describe. 101 using InlinedEntity = DbgValueHistoryMap::InlinedEntity; 102 using RegDescribedVarsMap = std::map<unsigned, SmallVector<InlinedEntity, 1>>; 103 104 // Keeps track of the debug value entries that are currently live for each 105 // inlined entity. As the history map entries are stored in a SmallVector, they 106 // may be moved at insertion of new entries, so store indices rather than 107 // pointers. 108 using DbgValueEntriesMap = std::map<InlinedEntity, SmallSet<EntryIndex, 1>>; 109 110 } // end anonymous namespace 111 112 // Claim that @Var is not described by @RegNo anymore. 113 static void dropRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 114 InlinedEntity Var) { 115 const auto &I = RegVars.find(RegNo); 116 assert(RegNo != 0U && I != RegVars.end()); 117 auto &VarSet = I->second; 118 const auto &VarPos = llvm::find(VarSet, Var); 119 assert(VarPos != VarSet.end()); 120 VarSet.erase(VarPos); 121 // Don't keep empty sets in a map to keep it as small as possible. 122 if (VarSet.empty()) 123 RegVars.erase(I); 124 } 125 126 // Claim that @Var is now described by @RegNo. 127 static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo, 128 InlinedEntity Var) { 129 assert(RegNo != 0U); 130 auto &VarSet = RegVars[RegNo]; 131 assert(!is_contained(VarSet, Var)); 132 VarSet.push_back(Var); 133 } 134 135 /// Create a clobbering entry and end all open debug value entries 136 /// for \p Var that are described by \p RegNo using that entry. 137 static void clobberRegEntries(InlinedEntity Var, unsigned RegNo, 138 const MachineInstr &ClobberingInstr, 139 DbgValueEntriesMap &LiveEntries, 140 DbgValueHistoryMap &HistMap) { 141 EntryIndex ClobberIndex = HistMap.startClobber(Var, ClobberingInstr); 142 143 // Close all entries whose values are described by the register. 144 SmallVector<EntryIndex, 4> IndicesToErase; 145 for (auto Index : LiveEntries[Var]) { 146 auto &Entry = HistMap.getEntry(Var, Index); 147 assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries"); 148 if (isDescribedByReg(*Entry.getInstr()) == RegNo) { 149 IndicesToErase.push_back(Index); 150 Entry.endEntry(ClobberIndex); 151 } 152 } 153 154 // Drop all entries that have ended. 155 for (auto Index : IndicesToErase) 156 LiveEntries[Var].erase(Index); 157 } 158 159 /// Add a new debug value for \p Var. Closes all overlapping debug values. 160 static void handleNewDebugValue(InlinedEntity Var, const MachineInstr &DV, 161 RegDescribedVarsMap &RegVars, 162 DbgValueEntriesMap &LiveEntries, 163 DbgValueHistoryMap &HistMap) { 164 EntryIndex NewIndex; 165 if (HistMap.startDbgValue(Var, DV, NewIndex)) { 166 SmallDenseMap<unsigned, bool, 4> TrackedRegs; 167 168 // If we have created a new debug value entry, close all preceding 169 // live entries that overlap. 170 SmallVector<EntryIndex, 4> IndicesToErase; 171 const DIExpression *DIExpr = DV.getDebugExpression(); 172 for (auto Index : LiveEntries[Var]) { 173 auto &Entry = HistMap.getEntry(Var, Index); 174 assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries"); 175 const MachineInstr &DV = *Entry.getInstr(); 176 bool Overlaps = DIExpr->fragmentsOverlap(DV.getDebugExpression()); 177 if (Overlaps) { 178 IndicesToErase.push_back(Index); 179 Entry.endEntry(NewIndex); 180 } 181 if (Register Reg = isDescribedByReg(DV)) 182 TrackedRegs[Reg] |= !Overlaps; 183 } 184 185 // If the new debug value is described by a register, add tracking of 186 // that register if it is not already tracked. 187 if (Register NewReg = isDescribedByReg(DV)) { 188 if (!TrackedRegs.count(NewReg)) 189 addRegDescribedVar(RegVars, NewReg, Var); 190 LiveEntries[Var].insert(NewIndex); 191 TrackedRegs[NewReg] = true; 192 } 193 194 // Drop tracking of registers that are no longer used. 195 for (auto I : TrackedRegs) 196 if (!I.second) 197 dropRegDescribedVar(RegVars, I.first, Var); 198 199 // Drop all entries that have ended, and mark the new entry as live. 200 for (auto Index : IndicesToErase) 201 LiveEntries[Var].erase(Index); 202 LiveEntries[Var].insert(NewIndex); 203 } 204 } 205 206 // Terminate the location range for variables described by register at 207 // @I by inserting @ClobberingInstr to their history. 208 static void clobberRegisterUses(RegDescribedVarsMap &RegVars, 209 RegDescribedVarsMap::iterator I, 210 DbgValueHistoryMap &HistMap, 211 DbgValueEntriesMap &LiveEntries, 212 const MachineInstr &ClobberingInstr) { 213 // Iterate over all variables described by this register and add this 214 // instruction to their history, clobbering it. 215 for (const auto &Var : I->second) 216 clobberRegEntries(Var, I->first, ClobberingInstr, LiveEntries, HistMap); 217 RegVars.erase(I); 218 } 219 220 // Terminate the location range for variables described by register 221 // @RegNo by inserting @ClobberingInstr to their history. 222 static void clobberRegisterUses(RegDescribedVarsMap &RegVars, unsigned RegNo, 223 DbgValueHistoryMap &HistMap, 224 DbgValueEntriesMap &LiveEntries, 225 const MachineInstr &ClobberingInstr) { 226 const auto &I = RegVars.find(RegNo); 227 if (I == RegVars.end()) 228 return; 229 clobberRegisterUses(RegVars, I, HistMap, LiveEntries, ClobberingInstr); 230 } 231 232 void llvm::calculateDbgEntityHistory(const MachineFunction *MF, 233 const TargetRegisterInfo *TRI, 234 DbgValueHistoryMap &DbgValues, 235 DbgLabelInstrMap &DbgLabels) { 236 const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); 237 unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); 238 Register FrameReg = TRI->getFrameRegister(*MF); 239 RegDescribedVarsMap RegVars; 240 DbgValueEntriesMap LiveEntries; 241 for (const auto &MBB : *MF) { 242 for (const auto &MI : MBB) { 243 if (MI.isDebugValue()) { 244 assert(MI.getNumOperands() > 1 && "Invalid DBG_VALUE instruction!"); 245 // Use the base variable (without any DW_OP_piece expressions) 246 // as index into History. The full variables including the 247 // piece expressions are attached to the MI. 248 const DILocalVariable *RawVar = MI.getDebugVariable(); 249 assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) && 250 "Expected inlined-at fields to agree"); 251 InlinedEntity Var(RawVar, MI.getDebugLoc()->getInlinedAt()); 252 253 handleNewDebugValue(Var, MI, RegVars, LiveEntries, DbgValues); 254 } else if (MI.isDebugLabel()) { 255 assert(MI.getNumOperands() == 1 && "Invalid DBG_LABEL instruction!"); 256 const DILabel *RawLabel = MI.getDebugLabel(); 257 assert(RawLabel->isValidLocationForIntrinsic(MI.getDebugLoc()) && 258 "Expected inlined-at fields to agree"); 259 // When collecting debug information for labels, there is no MCSymbol 260 // generated for it. So, we keep MachineInstr in DbgLabels in order 261 // to query MCSymbol afterward. 262 InlinedEntity L(RawLabel, MI.getDebugLoc()->getInlinedAt()); 263 DbgLabels.addInstr(L, MI); 264 } 265 266 // Meta Instructions have no output and do not change any values and so 267 // can be safely ignored. 268 if (MI.isMetaInstruction()) 269 continue; 270 271 // Not a DBG_VALUE instruction. It may clobber registers which describe 272 // some variables. 273 for (const MachineOperand &MO : MI.operands()) { 274 if (MO.isReg() && MO.isDef() && MO.getReg()) { 275 // Ignore call instructions that claim to clobber SP. The AArch64 276 // backend does this for aggregate function arguments. 277 if (MI.isCall() && MO.getReg() == SP) 278 continue; 279 // If this is a virtual register, only clobber it since it doesn't 280 // have aliases. 281 if (Register::isVirtualRegister(MO.getReg())) 282 clobberRegisterUses(RegVars, MO.getReg(), DbgValues, LiveEntries, 283 MI); 284 // If this is a register def operand, it may end a debug value 285 // range. Ignore frame-register defs in the epilogue and prologue, 286 // we expect debuggers to understand that stack-locations are 287 // invalid outside of the function body. 288 else if (MO.getReg() != FrameReg || 289 (!MI.getFlag(MachineInstr::FrameDestroy) && 290 !MI.getFlag(MachineInstr::FrameSetup))) { 291 for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); 292 ++AI) 293 clobberRegisterUses(RegVars, *AI, DbgValues, LiveEntries, MI); 294 } 295 } else if (MO.isRegMask()) { 296 // If this is a register mask operand, clobber all debug values in 297 // non-CSRs. 298 SmallVector<unsigned, 32> RegsToClobber; 299 // Don't consider SP to be clobbered by register masks. 300 for (auto It : RegVars) { 301 unsigned int Reg = It.first; 302 if (Reg != SP && Register::isPhysicalRegister(Reg) && 303 MO.clobbersPhysReg(Reg)) 304 RegsToClobber.push_back(Reg); 305 } 306 307 for (unsigned Reg : RegsToClobber) { 308 clobberRegisterUses(RegVars, Reg, DbgValues, LiveEntries, MI); 309 } 310 } 311 } // End MO loop. 312 } // End instr loop. 313 314 // Make sure locations for all variables are valid only until the end of 315 // the basic block (unless it's the last basic block, in which case let 316 // their liveness run off to the end of the function). 317 if (!MBB.empty() && &MBB != &MF->back()) { 318 // Iterate over all variables that have open debug values. 319 for (auto &Pair : LiveEntries) { 320 if (Pair.second.empty()) 321 continue; 322 323 // Create a clobbering entry. 324 EntryIndex ClobIdx = DbgValues.startClobber(Pair.first, MBB.back()); 325 326 // End all entries. 327 for (EntryIndex Idx : Pair.second) { 328 DbgValueHistoryMap::Entry &Ent = DbgValues.getEntry(Pair.first, Idx); 329 assert(Ent.isDbgValue() && !Ent.isClosed()); 330 Ent.endEntry(ClobIdx); 331 } 332 } 333 334 LiveEntries.clear(); 335 RegVars.clear(); 336 } 337 } 338 } 339 340 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 341 LLVM_DUMP_METHOD void DbgValueHistoryMap::dump() const { 342 dbgs() << "DbgValueHistoryMap:\n"; 343 for (const auto &VarRangePair : *this) { 344 const InlinedEntity &Var = VarRangePair.first; 345 const Entries &Entries = VarRangePair.second; 346 347 const DILocalVariable *LocalVar = cast<DILocalVariable>(Var.first); 348 const DILocation *Location = Var.second; 349 350 dbgs() << " - " << LocalVar->getName() << " at "; 351 352 if (Location) 353 dbgs() << Location->getFilename() << ":" << Location->getLine() << ":" 354 << Location->getColumn(); 355 else 356 dbgs() << "<unknown location>"; 357 358 dbgs() << " --\n"; 359 360 for (const auto &E : enumerate(Entries)) { 361 const auto &Entry = E.value(); 362 dbgs() << " Entry[" << E.index() << "]: "; 363 if (Entry.isDbgValue()) 364 dbgs() << "Debug value\n"; 365 else 366 dbgs() << "Clobber\n"; 367 dbgs() << " Instr: " << *Entry.getInstr(); 368 if (Entry.isDbgValue()) { 369 if (Entry.getEndIndex() == NoEntry) 370 dbgs() << " - Valid until end of function\n"; 371 else 372 dbgs() << " - Closed by Entry[" << Entry.getEndIndex() << "]\n"; 373 } 374 dbgs() << "\n"; 375 } 376 } 377 } 378 #endif 379