LLVM 19.0.0git
LexicalScopes.cpp
Go to the documentation of this file.
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
17#include "llvm/ADT/DenseMap.h"
22#include "llvm/Config/llvm-config.h"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/Metadata.h"
28#include "llvm/Support/Debug.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.
41 MF = nullptr;
42 CurrentFnLexicalScope = nullptr;
43 LexicalScopeMap.clear();
44 AbstractScopeMap.clear();
45 InlinedLexicalScopeMap.clear();
46 AbstractScopesList.clear();
47 DominatedBlocks.clear();
48}
49
50/// initialize - Scan machine function and constuct lexical scope nest.
52 reset();
53 // Don't attempt any lexical scope creation for a NoDebug compile unit.
54 if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
56 return;
57 MF = &Fn;
60 extractLexicalScopes(MIRanges, MI2ScopeMap);
61 if (CurrentFnLexicalScope) {
62 constructScopeNest(CurrentFnLexicalScope);
63 assignInstructionRanges(MIRanges, MI2ScopeMap);
64 }
65}
66
67/// extractLexicalScopes - Extract instruction ranges for each lexical scopes
68/// for the given machine function.
69void LexicalScopes::extractLexicalScopes(
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 InsnRange R(RangeBeginMI, PrevMI);
101 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
102 MIRanges.push_back(R);
103 }
104
105 // This is a beginning of a new instruction range.
106 RangeBeginMI = &MInsn;
107
108 // Reset previous markers.
109 PrevMI = &MInsn;
110 PrevDL = MIDL;
111 }
112
113 // Create last instruction range.
114 if (RangeBeginMI && PrevMI && PrevDL) {
115 InsnRange R(RangeBeginMI, PrevMI);
116 MIRanges.push_back(R);
117 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
118 }
119 }
120}
121
122/// findLexicalScope - Find lexical scope, either regular or inlined, for the
123/// given DebugLoc. Return NULL if not found.
125 DILocalScope *Scope = DL->getScope();
126 if (!Scope)
127 return nullptr;
128
129 // The scope that we were created with could have an extra file - which
130 // isn't what we care about in this case.
131 Scope = Scope->getNonLexicalBlockFileScope();
132
133 if (auto *IA = DL->getInlinedAt()) {
134 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
135 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
136 }
137 return findLexicalScope(Scope);
138}
139
140/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
141/// not available then create new lexical scope.
142LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
143 const DILocation *IA) {
144 if (IA) {
145 // Skip scopes inlined from a NoDebug compile unit.
146 if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
148 return getOrCreateLexicalScope(IA);
149 // Create an abstract scope for inlined function.
151 // Create an inlined scope for inlined function.
152 return getOrCreateInlinedScope(Scope, IA);
153 }
154
155 return getOrCreateRegularScope(Scope);
156}
157
158/// getOrCreateRegularScope - Find or create a regular lexical scope.
160LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
161 assert(Scope && "Invalid Scope encoding!");
162 Scope = Scope->getNonLexicalBlockFileScope();
163
164 auto I = LexicalScopeMap.find(Scope);
165 if (I != LexicalScopeMap.end())
166 return &I->second;
167
168 // FIXME: Should the following dyn_cast be DILexicalBlock?
169 LexicalScope *Parent = nullptr;
170 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
171 Parent = getOrCreateLexicalScope(Block->getScope());
172 I = LexicalScopeMap.emplace(std::piecewise_construct,
173 std::forward_as_tuple(Scope),
174 std::forward_as_tuple(Parent, Scope, nullptr,
175 false)).first;
176
177 if (!Parent) {
178 assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction()));
179 assert(!CurrentFnLexicalScope);
180 CurrentFnLexicalScope = &I->second;
181 }
182
183 return &I->second;
184}
185
186/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
188LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
189 const DILocation *InlinedAt) {
190 assert(Scope && "Invalid Scope encoding!");
191 Scope = Scope->getNonLexicalBlockFileScope();
192 std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
193 auto I = InlinedLexicalScopeMap.find(P);
194 if (I != InlinedLexicalScopeMap.end())
195 return &I->second;
196
197 LexicalScope *Parent;
198 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
199 Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
200 else
201 Parent = getOrCreateLexicalScope(InlinedAt);
202
203 I = InlinedLexicalScopeMap
204 .emplace(std::piecewise_construct, std::forward_as_tuple(P),
205 std::forward_as_tuple(Parent, Scope, InlinedAt, false))
206 .first;
207 return &I->second;
208}
209
210/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
213 assert(Scope && "Invalid Scope encoding!");
214 Scope = Scope->getNonLexicalBlockFileScope();
215 auto I = AbstractScopeMap.find(Scope);
216 if (I != AbstractScopeMap.end())
217 return &I->second;
218
219 // FIXME: Should the following isa be DILexicalBlock?
220 LexicalScope *Parent = nullptr;
221 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
222 Parent = getOrCreateAbstractScope(Block->getScope());
223
224 I = AbstractScopeMap.emplace(std::piecewise_construct,
225 std::forward_as_tuple(Scope),
226 std::forward_as_tuple(Parent, Scope,
227 nullptr, true)).first;
228 if (isa<DISubprogram>(Scope))
229 AbstractScopesList.push_back(&I->second);
230 return &I->second;
231}
232
233/// constructScopeNest - Traverse the Scope tree depth-first, storing
234/// traversal state in WorkStack and recording the depth-first
235/// numbering (setDFSIn, setDFSOut) for edge classification.
236void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
237 assert(Scope && "Unable to calculate scope dominance graph!");
239 WorkStack.push_back(std::make_pair(Scope, 0));
240 unsigned Counter = 0;
241 while (!WorkStack.empty()) {
242 auto &ScopePosition = WorkStack.back();
243 LexicalScope *WS = ScopePosition.first;
244 size_t ChildNum = ScopePosition.second++;
245 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
246 if (ChildNum < Children.size()) {
247 auto &ChildScope = Children[ChildNum];
248 WorkStack.push_back(std::make_pair(ChildScope, 0));
249 ChildScope->setDFSIn(++Counter);
250 } else {
251 WorkStack.pop_back();
252 WS->setDFSOut(++Counter);
253 }
254 }
255}
256
257/// assignInstructionRanges - Find ranges of instructions covered by each
258/// lexical scope.
259void LexicalScopes::assignInstructionRanges(
262 LexicalScope *PrevLexicalScope = nullptr;
263 for (const auto &R : MIRanges) {
264 LexicalScope *S = MI2ScopeMap.lookup(R.first);
265 assert(S && "Lost LexicalScope for a machine instruction!");
266 if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
267 PrevLexicalScope->closeInsnRange(S);
268 S->openInsnRange(R.first);
269 S->extendInsnRange(R.second);
270 PrevLexicalScope = S;
271 }
272
273 if (PrevLexicalScope)
274 PrevLexicalScope->closeInsnRange();
275}
276
277/// getMachineBasicBlocks - Populate given set using machine basic blocks which
278/// have machine instructions that belong to lexical scope identified by
279/// DebugLoc.
282 assert(MF && "Method called on a uninitialized LexicalScopes object!");
283 MBBs.clear();
284
285 LexicalScope *Scope = getOrCreateLexicalScope(DL);
286 if (!Scope)
287 return;
288
289 if (Scope == CurrentFnLexicalScope) {
290 for (const auto &MBB : *MF)
291 MBBs.insert(&MBB);
292 return;
293 }
294
295 // The scope ranges can cover multiple basic blocks in each span. Iterate over
296 // all blocks (in the order they are in the function) until we reach the one
297 // containing the end of the span.
298 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
299 for (auto &R : InsnRanges)
300 for (auto CurMBBIt = R.first->getParent()->getIterator(),
301 EndBBIt = std::next(R.second->getParent()->getIterator());
302 CurMBBIt != EndBBIt; CurMBBIt++)
303 MBBs.insert(&*CurMBBIt);
304}
305
307 assert(MF && "Unexpected uninitialized LexicalScopes object!");
308 LexicalScope *Scope = getOrCreateLexicalScope(DL);
309 if (!Scope)
310 return false;
311
312 // Current function scope covers all basic blocks in the function.
313 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
314 return true;
315
316 // Fetch all the blocks in DLs scope. Because the range / block list also
317 // contain any subscopes, any instruction that DL dominates can be found in
318 // the block set.
319 //
320 // Cache the set of fetched blocks to avoid repeatedly recomputing the set in
321 // the LiveDebugValues pass.
322 std::unique_ptr<BlockSetT> &Set = DominatedBlocks[DL];
323 if (!Set) {
324 Set = std::make_unique<BlockSetT>();
326 }
327 return Set->contains(MBB);
328}
329
330#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
331LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
332 raw_ostream &err = dbgs();
333 err.indent(Indent);
334 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
335 const MDNode *N = Desc;
336 err.indent(Indent);
337 N->dump();
338 if (AbstractScope)
339 err << std::string(Indent, ' ') << "Abstract Scope\n";
340
341 if (!Children.empty())
342 err << std::string(Indent + 2, ' ') << "Children ...\n";
343 for (unsigned i = 0, e = Children.size(); i != e; ++i)
344 if (Children[i] != this)
345 Children[i]->dump(Indent + 2);
346}
347#endif
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
This file defines the DenseMap class.
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for metadata subclasses.
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
A scope for locals.
Debug location.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1828
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
void extendInsnRange(const MachineInstr *MI)
extendInsnRange - Extend the current instruction range covered by this scope.
Definition: LexicalScopes.h:82
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:65
void setDFSOut(unsigned O)
void openInsnRange(const MachineInstr *MI)
openInsnRange - This scope covers instruction range starting from MI.
Definition: LexicalScopes.h:72
void dump(unsigned Indent=0) const
dump - print lexical scope.
bool dominates(const LexicalScope *S) const
dominates - Return true if current scope dominates given lexical scope.
void closeInsnRange(LexicalScope *NewScope=nullptr)
closeInsnRange - Create a range based on FirstInsn and LastInsn collected until now.
Definition: LexicalScopes.h:92
void reset()
releaseMemory - release memory.
LexicalScope * getOrCreateAbstractScope(const DILocalScope *Scope)
getOrCreateAbstractScope - Find or create an abstract lexical scope.
void initialize(const MachineFunction &)
initialize - Scan machine function and constuct lexical scope nest, resets the instance if necessary.
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
void getMachineBasicBlocks(const DILocation *DL, SmallPtrSetImpl< const MachineBasicBlock * > &MBBs)
getMachineBasicBlocks - Populate given set using machine basic blocks which have machine instructions...
bool dominates(const DILocation *DL, MachineBasicBlock *MBB)
Return true if DebugLoc's lexical scope dominates at least one machine instruction's lexical scope in...
Metadata node.
Definition: Metadata.h:1067
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:69
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
std::pair< const MachineInstr *, const MachineInstr * > InsnRange
InsnRange - This is used to track range of instructions with identical lexical scope.
Definition: LexicalScopes.h:39
#define N
Description of the encoding of one expression Op.