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