/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/LexicalScopes.h
Line | Count | Source (jump to first uncovered line) |
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 | 1.45M | : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) { |
49 | 1.45M | assert(D); |
50 | 1.45M | assert(D->getSubprogram()->getUnit()->getEmissionKind() != |
51 | 1.45M | DICompileUnit::NoDebug && |
52 | 1.45M | "Don't build lexical scopes for non-debug locations"); |
53 | 1.45M | assert(D->isResolved() && "Expected resolved node"); |
54 | 1.45M | assert((!I || I->isResolved()) && "Expected resolved node"); |
55 | 1.45M | if (Parent) |
56 | 848k | Parent->addChild(this); |
57 | 1.45M | } |
58 | | |
59 | | // Accessors. |
60 | 279k | LexicalScope *getParent() const { return Parent; } |
61 | 0 | const MDNode *getDesc() const { return Desc; } |
62 | 279k | const DILocation *getInlinedAt() const { return InlinedAtLocation; } |
63 | 1.39M | const DILocalScope *getScopeNode() const { return Desc; } |
64 | 318k | bool isAbstractScope() const { return AbstractScope; } |
65 | 2.49M | SmallVectorImpl<LexicalScope *> &getChildren() { return Children; } |
66 | 601k | SmallVectorImpl<InsnRange> &getRanges() { return Ranges; } |
67 | | |
68 | | /// addChild - Add a child scope. |
69 | 848k | void addChild(LexicalScope *S) { Children.push_back(S); } |
70 | | |
71 | | /// openInsnRange - This scope covers instruction range starting from MI. |
72 | 7.07M | void openInsnRange(const MachineInstr *MI) { |
73 | 7.07M | if (!FirstInsn) |
74 | 1.16M | FirstInsn = MI; |
75 | 7.07M | |
76 | 7.07M | if (Parent) |
77 | 4.25M | Parent->openInsnRange(MI); |
78 | 7.07M | } |
79 | | |
80 | | /// extendInsnRange - Extend the current instruction range covered by |
81 | | /// this scope. |
82 | 7.07M | void extendInsnRange(const MachineInstr *MI) { |
83 | 7.07M | assert(FirstInsn && "MI Range is not open!"); |
84 | 7.07M | LastInsn = MI; |
85 | 7.07M | if (Parent) |
86 | 4.25M | Parent->extendInsnRange(MI); |
87 | 7.07M | } |
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 | 1.16M | void closeInsnRange(LexicalScope *NewScope = nullptr) { |
93 | 1.16M | assert(LastInsn && "Last insn missing!"); |
94 | 1.16M | Ranges.push_back(InsnRange(FirstInsn, LastInsn)); |
95 | 1.16M | FirstInsn = nullptr; |
96 | 1.16M | LastInsn = nullptr; |
97 | 1.16M | // If Parent dominates NewScope then do not close Parent's instruction |
98 | 1.16M | // range. |
99 | 1.16M | if (Parent && (1.05M !NewScope1.05M || !Parent->dominates(NewScope)1.03M )) |
100 | 406k | Parent->closeInsnRange(NewScope); |
101 | 1.16M | } |
102 | | |
103 | | /// dominates - Return true if current scope dominates given lexical scope. |
104 | 3.74M | bool dominates(const LexicalScope *S) const { |
105 | 3.74M | if (S == this) |
106 | 2.10M | return true; |
107 | 1.63M | if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut()870k ) |
108 | 607k | return true; |
109 | 1.03M | return false; |
110 | 1.03M | } |
111 | | |
112 | | // Depth First Search support to walk and manipulate LexicalScope hierarchy. |
113 | 5.04M | unsigned getDFSOut() const { return DFSOut; } |
114 | 954k | void setDFSOut(unsigned O) { DFSOut = O; } |
115 | 1.63M | unsigned getDFSIn() const { return DFSIn; } |
116 | 848k | 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 | 107k | 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 | 35.7k | bool empty() { return CurrentFnLexicalScope == nullptr; } |
154 | | |
155 | | /// getCurrentFunctionScope - Return lexical scope for the current function. |
156 | 71.4k | LexicalScope *getCurrentFunctionScope() const { |
157 | 71.4k | return CurrentFnLexicalScope; |
158 | 71.4k | } |
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 | | /// dominates - Return true if DebugLoc's lexical scope dominates at least one |
167 | | /// machine 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 | 69.6k | ArrayRef<LexicalScope *> getAbstractScopesList() const { |
176 | 69.6k | return AbstractScopesList; |
177 | 69.6k | } |
178 | | |
179 | | /// findAbstractScope - Find an abstract scope or return null. |
180 | 1.18k | LexicalScope *findAbstractScope(const DILocalScope *N) { |
181 | 1.18k | auto I = AbstractScopeMap.find(N); |
182 | 1.18k | return I != AbstractScopeMap.end() ? &I->second88 : nullptr1.09k ; |
183 | 1.18k | } |
184 | | |
185 | | /// findInlinedScope - Find an inlined scope for the given scope/inlined-at. |
186 | 79 | LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) { |
187 | 79 | auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA)); |
188 | 79 | return I != InlinedLexicalScopeMap.end() ? &I->second73 : nullptr6 ; |
189 | 79 | } |
190 | | |
191 | | /// findLexicalScope - Find regular lexical scope or return null. |
192 | 6.82k | LexicalScope *findLexicalScope(const DILocalScope *N) { |
193 | 6.82k | auto I = LexicalScopeMap.find(N); |
194 | 6.82k | return I != LexicalScopeMap.end() ? &I->second6.76k : nullptr60 ; |
195 | 6.82k | } |
196 | | |
197 | | /// dump - Print data structures to dbgs(). |
198 | | void dump() const; |
199 | | |
200 | | /// getOrCreateAbstractScope - Find or create an abstract lexical scope. |
201 | | LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope); |
202 | | |
203 | | private: |
204 | | /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If |
205 | | /// not available then create new lexical scope. |
206 | | LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope, |
207 | | const DILocation *IA = nullptr); |
208 | 3.66M | LexicalScope *getOrCreateLexicalScope(const DILocation *DL) { |
209 | 3.66M | return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt()) |
210 | 3.66M | : nullptr0 ; |
211 | 3.66M | } |
212 | | |
213 | | /// getOrCreateRegularScope - Find or create a regular lexical scope. |
214 | | LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope); |
215 | | |
216 | | /// getOrCreateInlinedScope - Find or create an inlined lexical scope. |
217 | | LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope, |
218 | | const DILocation *InlinedAt); |
219 | | |
220 | | /// extractLexicalScopes - Extract instruction ranges for each lexical scopes |
221 | | /// for the given machine function. |
222 | | void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges, |
223 | | DenseMap<const MachineInstr *, LexicalScope *> &M); |
224 | | void constructScopeNest(LexicalScope *Scope); |
225 | | void |
226 | | assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges, |
227 | | DenseMap<const MachineInstr *, LexicalScope *> &M); |
228 | | |
229 | | const MachineFunction *MF = nullptr; |
230 | | |
231 | | /// LexicalScopeMap - Tracks the scopes in the current function. |
232 | | // Use an unordered_map to ensure value pointer validity over insertion. |
233 | | std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap; |
234 | | |
235 | | /// InlinedLexicalScopeMap - Tracks inlined function scopes in current |
236 | | /// function. |
237 | | std::unordered_map<std::pair<const DILocalScope *, const DILocation *>, |
238 | | LexicalScope, |
239 | | pair_hash<const DILocalScope *, const DILocation *>> |
240 | | InlinedLexicalScopeMap; |
241 | | |
242 | | /// AbstractScopeMap - These scopes are not included LexicalScopeMap. |
243 | | // Use an unordered_map to ensure value pointer validity over insertion. |
244 | | std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap; |
245 | | |
246 | | /// AbstractScopesList - Tracks abstract scopes constructed while processing |
247 | | /// a function. |
248 | | SmallVector<LexicalScope *, 4> AbstractScopesList; |
249 | | |
250 | | /// CurrentFnLexicalScope - Top level scope for the current function. |
251 | | /// |
252 | | LexicalScope *CurrentFnLexicalScope = nullptr; |
253 | | }; |
254 | | |
255 | | } // end namespace llvm |
256 | | |
257 | | #endif // LLVM_CODEGEN_LEXICALSCOPES_H |