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