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 35using namespace llvm; 36 37#define DEBUG_TYPE "lexicalscopes" 38 39/// reset - Reset the instance so that it's prepared for another function. 40void 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. 50void 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. 68void 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. 123LexicalScope *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. 141LexicalScope *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. 158LexicalScope * 159LexicalScopes::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. 186LexicalScope * 187LexicalScopes::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. 210LexicalScope * 211LexicalScopes::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 233void 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. 258void 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. 279void 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. 301bool 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) 322LLVM_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