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