1 //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===// 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 LexicalScopes analysis. 10 // 11 // This pass collects lexical scope information and maps machine instructions 12 // to respective lexical scopes. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/CodeGen/LexicalScopes.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineInstr.h" 22 #include "llvm/Config/llvm-config.h" 23 #include "llvm/IR/DebugInfoMetadata.h" 24 #include "llvm/IR/Function.h" 25 #include "llvm/IR/Metadata.h" 26 #include "llvm/Support/Casting.h" 27 #include "llvm/Support/Compiler.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include <cassert> 31 #include <string> 32 #include <tuple> 33 #include <utility> 34 35 using namespace llvm; 36 37 #define DEBUG_TYPE "lexicalscopes" 38 39 /// reset - Reset the instance so that it's prepared for another function. 40 void LexicalScopes::reset() { 41 MF = nullptr; 42 CurrentFnLexicalScope = nullptr; 43 LexicalScopeMap.clear(); 44 AbstractScopeMap.clear(); 45 InlinedLexicalScopeMap.clear(); 46 AbstractScopesList.clear(); 47 } 48 49 /// initialize - Scan machine function and constuct lexical scope nest. 50 void LexicalScopes::initialize(const MachineFunction &Fn) { 51 reset(); 52 // Don't attempt any lexical scope creation for a NoDebug compile unit. 53 if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() == 54 DICompileUnit::NoDebug) 55 return; 56 MF = &Fn; 57 SmallVector<InsnRange, 4> MIRanges; 58 DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap; 59 extractLexicalScopes(MIRanges, MI2ScopeMap); 60 if (CurrentFnLexicalScope) { 61 constructScopeNest(CurrentFnLexicalScope); 62 assignInstructionRanges(MIRanges, MI2ScopeMap); 63 } 64 } 65 66 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes 67 /// for the given machine function. 68 void LexicalScopes::extractLexicalScopes( 69 SmallVectorImpl<InsnRange> &MIRanges, 70 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 71 // Scan each instruction and create scopes. First build working set of scopes. 72 for (const auto &MBB : *MF) { 73 const MachineInstr *RangeBeginMI = nullptr; 74 const MachineInstr *PrevMI = nullptr; 75 const DILocation *PrevDL = nullptr; 76 for (const auto &MInsn : MBB) { 77 // Check if instruction has valid location information. 78 const DILocation *MIDL = MInsn.getDebugLoc(); 79 if (!MIDL) { 80 PrevMI = &MInsn; 81 continue; 82 } 83 84 // If scope has not changed then skip this instruction. 85 if (MIDL == PrevDL) { 86 PrevMI = &MInsn; 87 continue; 88 } 89 90 // Ignore DBG_VALUE and similar instruction that do not contribute to any 91 // instruction in the output. 92 if (MInsn.isMetaInstruction()) 93 continue; 94 95 if (RangeBeginMI) { 96 // If we have already seen a beginning of an instruction range and 97 // current instruction scope does not match scope of first instruction 98 // in this range then create a new instruction range. 99 InsnRange R(RangeBeginMI, PrevMI); 100 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 101 MIRanges.push_back(R); 102 } 103 104 // This is a beginning of a new instruction range. 105 RangeBeginMI = &MInsn; 106 107 // Reset previous markers. 108 PrevMI = &MInsn; 109 PrevDL = MIDL; 110 } 111 112 // Create last instruction range. 113 if (RangeBeginMI && PrevMI && PrevDL) { 114 InsnRange R(RangeBeginMI, PrevMI); 115 MIRanges.push_back(R); 116 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 117 } 118 } 119 } 120 121 /// findLexicalScope - Find lexical scope, either regular or inlined, for the 122 /// given DebugLoc. Return NULL if not found. 123 LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) { 124 DILocalScope *Scope = DL->getScope(); 125 if (!Scope) 126 return nullptr; 127 128 // The scope that we were created with could have an extra file - which 129 // isn't what we care about in this case. 130 Scope = Scope->getNonLexicalBlockFileScope(); 131 132 if (auto *IA = DL->getInlinedAt()) { 133 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); 134 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 135 } 136 return findLexicalScope(Scope); 137 } 138 139 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 140 /// not available then create new lexical scope. 141 LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope, 142 const DILocation *IA) { 143 if (IA) { 144 // Skip scopes inlined from a NoDebug compile unit. 145 if (Scope->getSubprogram()->getUnit()->getEmissionKind() == 146 DICompileUnit::NoDebug) 147 return getOrCreateLexicalScope(IA); 148 // Create an abstract scope for inlined function. 149 getOrCreateAbstractScope(Scope); 150 // Create an inlined scope for inlined function. 151 return getOrCreateInlinedScope(Scope, IA); 152 } 153 154 return getOrCreateRegularScope(Scope); 155 } 156 157 /// getOrCreateRegularScope - Find or create a regular lexical scope. 158 LexicalScope * 159 LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) { 160 assert(Scope && "Invalid Scope encoding!"); 161 Scope = Scope->getNonLexicalBlockFileScope(); 162 163 auto I = LexicalScopeMap.find(Scope); 164 if (I != LexicalScopeMap.end()) 165 return &I->second; 166 167 // FIXME: Should the following dyn_cast be DILexicalBlock? 168 LexicalScope *Parent = nullptr; 169 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 170 Parent = getOrCreateLexicalScope(Block->getScope()); 171 I = LexicalScopeMap.emplace(std::piecewise_construct, 172 std::forward_as_tuple(Scope), 173 std::forward_as_tuple(Parent, Scope, nullptr, 174 false)).first; 175 176 if (!Parent) { 177 assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction())); 178 assert(!CurrentFnLexicalScope); 179 CurrentFnLexicalScope = &I->second; 180 } 181 182 return &I->second; 183 } 184 185 /// getOrCreateInlinedScope - Find or create an inlined lexical scope. 186 LexicalScope * 187 LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope, 188 const DILocation *InlinedAt) { 189 assert(Scope && "Invalid Scope encoding!"); 190 Scope = Scope->getNonLexicalBlockFileScope(); 191 std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt); 192 auto I = InlinedLexicalScopeMap.find(P); 193 if (I != InlinedLexicalScopeMap.end()) 194 return &I->second; 195 196 LexicalScope *Parent; 197 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 198 Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt); 199 else 200 Parent = getOrCreateLexicalScope(InlinedAt); 201 202 I = InlinedLexicalScopeMap 203 .emplace(std::piecewise_construct, std::forward_as_tuple(P), 204 std::forward_as_tuple(Parent, Scope, InlinedAt, false)) 205 .first; 206 return &I->second; 207 } 208 209 /// getOrCreateAbstractScope - Find or create an abstract lexical scope. 210 LexicalScope * 211 LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) { 212 assert(Scope && "Invalid Scope encoding!"); 213 Scope = Scope->getNonLexicalBlockFileScope(); 214 auto I = AbstractScopeMap.find(Scope); 215 if (I != AbstractScopeMap.end()) 216 return &I->second; 217 218 // FIXME: Should the following isa be DILexicalBlock? 219 LexicalScope *Parent = nullptr; 220 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 221 Parent = getOrCreateAbstractScope(Block->getScope()); 222 223 I = AbstractScopeMap.emplace(std::piecewise_construct, 224 std::forward_as_tuple(Scope), 225 std::forward_as_tuple(Parent, Scope, 226 nullptr, true)).first; 227 if (isa<DISubprogram>(Scope)) 228 AbstractScopesList.push_back(&I->second); 229 return &I->second; 230 } 231 232 /// constructScopeNest 233 void LexicalScopes::constructScopeNest(LexicalScope *Scope) { 234 assert(Scope && "Unable to calculate scope dominance graph!"); 235 SmallVector<LexicalScope *, 4> WorkStack; 236 WorkStack.push_back(Scope); 237 unsigned Counter = 0; 238 while (!WorkStack.empty()) { 239 LexicalScope *WS = WorkStack.back(); 240 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren(); 241 bool visitedChildren = false; 242 for (auto &ChildScope : Children) 243 if (!ChildScope->getDFSOut()) { 244 WorkStack.push_back(ChildScope); 245 visitedChildren = true; 246 ChildScope->setDFSIn(++Counter); 247 break; 248 } 249 if (!visitedChildren) { 250 WorkStack.pop_back(); 251 WS->setDFSOut(++Counter); 252 } 253 } 254 } 255 256 /// assignInstructionRanges - Find ranges of instructions covered by each 257 /// lexical scope. 258 void LexicalScopes::assignInstructionRanges( 259 SmallVectorImpl<InsnRange> &MIRanges, 260 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 261 LexicalScope *PrevLexicalScope = nullptr; 262 for (const auto &R : MIRanges) { 263 LexicalScope *S = MI2ScopeMap.lookup(R.first); 264 assert(S && "Lost LexicalScope for a machine instruction!"); 265 if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) 266 PrevLexicalScope->closeInsnRange(S); 267 S->openInsnRange(R.first); 268 S->extendInsnRange(R.second); 269 PrevLexicalScope = S; 270 } 271 272 if (PrevLexicalScope) 273 PrevLexicalScope->closeInsnRange(); 274 } 275 276 /// getMachineBasicBlocks - Populate given set using machine basic blocks which 277 /// have machine instructions that belong to lexical scope identified by 278 /// DebugLoc. 279 void LexicalScopes::getMachineBasicBlocks( 280 const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) { 281 assert(MF && "Method called on a uninitialized LexicalScopes object!"); 282 MBBs.clear(); 283 284 LexicalScope *Scope = getOrCreateLexicalScope(DL); 285 if (!Scope) 286 return; 287 288 if (Scope == CurrentFnLexicalScope) { 289 for (const auto &MBB : *MF) 290 MBBs.insert(&MBB); 291 return; 292 } 293 294 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges(); 295 for (auto &R : InsnRanges) 296 MBBs.insert(R.first->getParent()); 297 } 298 299 /// dominates - Return true if DebugLoc's lexical scope dominates at least one 300 /// machine instruction's lexical scope in a given machine basic block. 301 bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) { 302 assert(MF && "Unexpected uninitialized LexicalScopes object!"); 303 LexicalScope *Scope = getOrCreateLexicalScope(DL); 304 if (!Scope) 305 return false; 306 307 // Current function scope covers all basic blocks in the function. 308 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) 309 return true; 310 311 bool Result = false; 312 for (auto &I : *MBB) { 313 if (const DILocation *IDL = I.getDebugLoc()) 314 if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) 315 if (Scope->dominates(IScope)) 316 return true; 317 } 318 return Result; 319 } 320 321 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 322 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const { 323 raw_ostream &err = dbgs(); 324 err.indent(Indent); 325 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; 326 const MDNode *N = Desc; 327 err.indent(Indent); 328 N->dump(); 329 if (AbstractScope) 330 err << std::string(Indent, ' ') << "Abstract Scope\n"; 331 332 if (!Children.empty()) 333 err << std::string(Indent + 2, ' ') << "Children ...\n"; 334 for (unsigned i = 0, e = Children.size(); i != e; ++i) 335 if (Children[i] != this) 336 Children[i]->dump(Indent + 2); 337 } 338 #endif 339