1 | //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===// |
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 | #ifndef LLVM_CODEGEN_LEXICALSCOPES_H |
17 | #define LLVM_CODEGEN_LEXICALSCOPES_H |
18 | |
19 | #include "llvm/ADT/ArrayRef.h" |
20 | #include "llvm/ADT/DenseMap.h" |
21 | #include "llvm/ADT/SmallPtrSet.h" |
22 | #include "llvm/ADT/SmallVector.h" |
23 | #include "llvm/IR/DebugInfoMetadata.h" |
24 | #include <cassert> |
25 | #include <unordered_map> |
26 | #include <utility> |
27 | |
28 | namespace llvm { |
29 | |
30 | class MachineBasicBlock; |
31 | class MachineFunction; |
32 | class MachineInstr; |
33 | class MDNode; |
34 | |
35 | //===----------------------------------------------------------------------===// |
36 | /// InsnRange - This is used to track range of instructions with identical |
37 | /// lexical scope. |
38 | /// |
39 | using InsnRange = std::pair<const MachineInstr *, const MachineInstr *>; |
40 | |
41 | //===----------------------------------------------------------------------===// |
42 | /// LexicalScope - This class is used to track scope information. |
43 | /// |
44 | class LexicalScope { |
45 | public: |
46 | LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I, |
47 | bool A) |
48 | : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) { |
49 | assert(D); |
50 | assert(D->getSubprogram()->getUnit()->getEmissionKind() != |
51 | DICompileUnit::NoDebug && |
52 | "Don't build lexical scopes for non-debug locations" ); |
53 | assert(D->isResolved() && "Expected resolved node" ); |
54 | assert((!I || I->isResolved()) && "Expected resolved node" ); |
55 | if (Parent) |
56 | Parent->addChild(S: this); |
57 | } |
58 | |
59 | // Accessors. |
60 | LexicalScope *getParent() const { return Parent; } |
61 | const MDNode *getDesc() const { return Desc; } |
62 | const DILocation *getInlinedAt() const { return InlinedAtLocation; } |
63 | const DILocalScope *getScopeNode() const { return Desc; } |
64 | bool isAbstractScope() const { return AbstractScope; } |
65 | SmallVectorImpl<LexicalScope *> &getChildren() { return Children; } |
66 | SmallVectorImpl<InsnRange> &getRanges() { return Ranges; } |
67 | |
68 | /// addChild - Add a child scope. |
69 | void addChild(LexicalScope *S) { Children.push_back(Elt: S); } |
70 | |
71 | /// openInsnRange - This scope covers instruction range starting from MI. |
72 | void openInsnRange(const MachineInstr *MI) { |
73 | if (!FirstInsn) |
74 | FirstInsn = MI; |
75 | |
76 | if (Parent) |
77 | Parent->openInsnRange(MI); |
78 | } |
79 | |
80 | /// extendInsnRange - Extend the current instruction range covered by |
81 | /// this scope. |
82 | void extendInsnRange(const MachineInstr *MI) { |
83 | assert(FirstInsn && "MI Range is not open!" ); |
84 | LastInsn = MI; |
85 | if (Parent) |
86 | Parent->extendInsnRange(MI); |
87 | } |
88 | |
89 | /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected |
90 | /// until now. This is used when a new scope is encountered while walking |
91 | /// machine instructions. |
92 | void closeInsnRange(LexicalScope *NewScope = nullptr) { |
93 | assert(LastInsn && "Last insn missing!" ); |
94 | Ranges.push_back(Elt: InsnRange(FirstInsn, LastInsn)); |
95 | FirstInsn = nullptr; |
96 | LastInsn = nullptr; |
97 | // If Parent dominates NewScope then do not close Parent's instruction |
98 | // range. |
99 | if (Parent && (!NewScope || !Parent->dominates(S: NewScope))) |
100 | Parent->closeInsnRange(NewScope); |
101 | } |
102 | |
103 | /// dominates - Return true if current scope dominates given lexical scope. |
104 | bool dominates(const LexicalScope *S) const { |
105 | if (S == this) |
106 | return true; |
107 | if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut()) |
108 | return true; |
109 | return false; |
110 | } |
111 | |
112 | // Depth First Search support to walk and manipulate LexicalScope hierarchy. |
113 | unsigned getDFSOut() const { return DFSOut; } |
114 | void setDFSOut(unsigned O) { DFSOut = O; } |
115 | unsigned getDFSIn() const { return DFSIn; } |
116 | void setDFSIn(unsigned I) { DFSIn = I; } |
117 | |
118 | /// dump - print lexical scope. |
119 | void dump(unsigned Indent = 0) const; |
120 | |
121 | private: |
122 | LexicalScope *Parent; // Parent to this scope. |
123 | const DILocalScope *Desc; // Debug info descriptor. |
124 | const DILocation *InlinedAtLocation; // Location at which this |
125 | // scope is inlined. |
126 | bool AbstractScope; // Abstract Scope |
127 | SmallVector<LexicalScope *, 4> Children; // Scopes defined in scope. |
128 | // Contents not owned. |
129 | SmallVector<InsnRange, 4> Ranges; |
130 | |
131 | const MachineInstr *LastInsn = nullptr; // Last instruction of this scope. |
132 | const MachineInstr *FirstInsn = nullptr; // First instruction of this scope. |
133 | unsigned DFSIn = 0; // In & Out Depth use to determine scope nesting. |
134 | unsigned DFSOut = 0; |
135 | }; |
136 | |
137 | //===----------------------------------------------------------------------===// |
138 | /// LexicalScopes - This class provides interface to collect and use lexical |
139 | /// scoping information from machine instruction. |
140 | /// |
141 | class LexicalScopes { |
142 | public: |
143 | LexicalScopes() = default; |
144 | |
145 | /// initialize - Scan machine function and constuct lexical scope nest, resets |
146 | /// the instance if necessary. |
147 | void initialize(const MachineFunction &); |
148 | |
149 | /// releaseMemory - release memory. |
150 | void reset(); |
151 | |
152 | /// empty - Return true if there is any lexical scope information available. |
153 | bool empty() { return CurrentFnLexicalScope == nullptr; } |
154 | |
155 | /// getCurrentFunctionScope - Return lexical scope for the current function. |
156 | LexicalScope *getCurrentFunctionScope() const { |
157 | return CurrentFnLexicalScope; |
158 | } |
159 | |
160 | /// getMachineBasicBlocks - Populate given set using machine basic blocks |
161 | /// which have machine instructions that belong to lexical scope identified by |
162 | /// DebugLoc. |
163 | void getMachineBasicBlocks(const DILocation *DL, |
164 | SmallPtrSetImpl<const MachineBasicBlock *> &MBBs); |
165 | |
166 | /// Return true if DebugLoc's lexical scope dominates at least one machine |
167 | /// instruction's lexical scope in a given machine basic block. |
168 | bool dominates(const DILocation *DL, MachineBasicBlock *MBB); |
169 | |
170 | /// findLexicalScope - Find lexical scope, either regular or inlined, for the |
171 | /// given DebugLoc. Return NULL if not found. |
172 | LexicalScope *findLexicalScope(const DILocation *DL); |
173 | |
174 | /// getAbstractScopesList - Return a reference to list of abstract scopes. |
175 | ArrayRef<LexicalScope *> getAbstractScopesList() const { |
176 | return AbstractScopesList; |
177 | } |
178 | |
179 | /// findAbstractScope - Find an abstract scope or return null. |
180 | LexicalScope *findAbstractScope(const DILocalScope *N) { |
181 | auto I = AbstractScopeMap.find(x: N); |
182 | return I != AbstractScopeMap.end() ? &I->second : nullptr; |
183 | } |
184 | |
185 | /// findInlinedScope - Find an inlined scope for the given scope/inlined-at. |
186 | LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) { |
187 | auto I = InlinedLexicalScopeMap.find(x: std::make_pair(x&: N, y&: IA)); |
188 | return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; |
189 | } |
190 | |
191 | /// findLexicalScope - Find regular lexical scope or return null. |
192 | LexicalScope *findLexicalScope(const DILocalScope *N) { |
193 | auto I = LexicalScopeMap.find(x: N); |
194 | return I != LexicalScopeMap.end() ? &I->second : nullptr; |
195 | } |
196 | |
197 | /// getOrCreateAbstractScope - Find or create an abstract lexical scope. |
198 | LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope); |
199 | |
200 | private: |
201 | /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If |
202 | /// not available then create new lexical scope. |
203 | LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope, |
204 | const DILocation *IA = nullptr); |
205 | LexicalScope *getOrCreateLexicalScope(const DILocation *DL) { |
206 | return DL ? getOrCreateLexicalScope(Scope: DL->getScope(), IA: DL->getInlinedAt()) |
207 | : nullptr; |
208 | } |
209 | |
210 | /// getOrCreateRegularScope - Find or create a regular lexical scope. |
211 | LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope); |
212 | |
213 | /// getOrCreateInlinedScope - Find or create an inlined lexical scope. |
214 | LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope, |
215 | const DILocation *InlinedAt); |
216 | |
217 | /// extractLexicalScopes - Extract instruction ranges for each lexical scopes |
218 | /// for the given machine function. |
219 | void (SmallVectorImpl<InsnRange> &MIRanges, |
220 | DenseMap<const MachineInstr *, LexicalScope *> &M); |
221 | void constructScopeNest(LexicalScope *Scope); |
222 | void |
223 | assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges, |
224 | DenseMap<const MachineInstr *, LexicalScope *> &M); |
225 | |
226 | const MachineFunction *MF = nullptr; |
227 | |
228 | /// LexicalScopeMap - Tracks the scopes in the current function. |
229 | // Use an unordered_map to ensure value pointer validity over insertion. |
230 | std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap; |
231 | |
232 | /// InlinedLexicalScopeMap - Tracks inlined function scopes in current |
233 | /// function. |
234 | std::unordered_map<std::pair<const DILocalScope *, const DILocation *>, |
235 | LexicalScope, |
236 | pair_hash<const DILocalScope *, const DILocation *>> |
237 | InlinedLexicalScopeMap; |
238 | |
239 | /// AbstractScopeMap - These scopes are not included LexicalScopeMap. |
240 | // Use an unordered_map to ensure value pointer validity over insertion. |
241 | std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap; |
242 | |
243 | /// AbstractScopesList - Tracks abstract scopes constructed while processing |
244 | /// a function. |
245 | SmallVector<LexicalScope *, 4> AbstractScopesList; |
246 | |
247 | /// CurrentFnLexicalScope - Top level scope for the current function. |
248 | /// |
249 | LexicalScope *CurrentFnLexicalScope = nullptr; |
250 | |
251 | /// Map a location to the set of basic blocks it dominates. This is a cache |
252 | /// for \ref LexicalScopes::getMachineBasicBlocks results. |
253 | using BlockSetT = SmallPtrSet<const MachineBasicBlock *, 4>; |
254 | DenseMap<const DILocation *, std::unique_ptr<BlockSetT>> DominatedBlocks; |
255 | }; |
256 | |
257 | } // end namespace llvm |
258 | |
259 | #endif // LLVM_CODEGEN_LEXICALSCOPES_H |
260 | |