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