Line data Source code
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 808211 : : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
50 : assert(D);
51 : assert(D->getSubprogram()->getUnit()->getEmissionKind() !=
52 : DICompileUnit::NoDebug &&
53 : "Don't build lexical scopes for non-debug locations");
54 : assert(D->isResolved() && "Expected resolved node");
55 : assert((!I || I->isResolved()) && "Expected resolved node");
56 808211 : if (Parent)
57 592540 : Parent->addChild(this);
58 : }
59 :
60 : // Accessors.
61 0 : LexicalScope *getParent() const { return Parent; }
62 : const MDNode *getDesc() const { return Desc; }
63 0 : const DILocation *getInlinedAt() const { return InlinedAtLocation; }
64 0 : const DILocalScope *getScopeNode() const { return Desc; }
65 0 : bool isAbstractScope() const { return AbstractScope; }
66 320 : SmallVectorImpl<LexicalScope *> &getChildren() { return Children; }
67 159554 : SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
68 :
69 : /// addChild - Add a child scope.
70 592540 : void addChild(LexicalScope *S) { Children.push_back(S); }
71 :
72 : /// openInsnRange - This scope covers instruction range starting from MI.
73 0 : void openInsnRange(const MachineInstr *MI) {
74 5232159 : if (!FirstInsn)
75 981393 : FirstInsn = MI;
76 :
77 5232159 : if (Parent)
78 3500429 : Parent->openInsnRange(MI);
79 0 : }
80 :
81 : /// extendInsnRange - Extend the current instruction range covered by
82 : /// this scope.
83 0 : void extendInsnRange(const MachineInstr *MI) {
84 : assert(FirstInsn && "MI Range is not open!");
85 5232159 : LastInsn = MI;
86 5232159 : if (Parent)
87 3500429 : Parent->extendInsnRange(MI);
88 0 : }
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 981393 : void closeInsnRange(LexicalScope *NewScope = nullptr) {
94 : assert(LastInsn && "Last insn missing!");
95 1962786 : Ranges.push_back(InsnRange(FirstInsn, LastInsn));
96 981393 : FirstInsn = nullptr;
97 981393 : LastInsn = nullptr;
98 : // If Parent dominates NewScope then do not close Parent's instruction
99 : // range.
100 981393 : if (Parent && (!NewScope || !Parent->dominates(NewScope)))
101 389985 : Parent->closeInsnRange(NewScope);
102 981393 : }
103 :
104 : /// dominates - Return true if current scope dominates given lexical scope.
105 : bool dominates(const LexicalScope *S) const {
106 3620764 : if (S == this)
107 : return true;
108 2552801 : if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
109 : return true;
110 : return false;
111 : }
112 :
113 : // Depth First Search support to walk and manipulate LexicalScope hierarchy.
114 0 : unsigned getDFSOut() const { return DFSOut; }
115 583503 : void setDFSOut(unsigned O) { DFSOut = O; }
116 0 : unsigned getDFSIn() const { return DFSIn; }
117 555116 : 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 126496 : 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 0 : bool empty() { return CurrentFnLexicalScope == nullptr; }
155 :
156 : /// getCurrentFunctionScope - Return lexical scope for the current function.
157 0 : LexicalScope *getCurrentFunctionScope() const {
158 0 : return CurrentFnLexicalScope;
159 : }
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 : ArrayRef<LexicalScope *> getAbstractScopesList() const {
177 : return AbstractScopesList;
178 : }
179 :
180 : /// findAbstractScope - Find an abstract scope or return null.
181 : LexicalScope *findAbstractScope(const DILocalScope *N) {
182 : auto I = AbstractScopeMap.find(N);
183 10180 : return I != AbstractScopeMap.end() ? &I->second : nullptr;
184 : }
185 :
186 : /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
187 : LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) {
188 66368 : auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
189 66368 : return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
190 : }
191 :
192 : /// findLexicalScope - Find regular lexical scope or return null.
193 : LexicalScope *findLexicalScope(const DILocalScope *N) {
194 : auto I = LexicalScopeMap.find(N);
195 31996 : return I != LexicalScopeMap.end() ? &I->second : nullptr;
196 : }
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 3387926 : LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
210 6775852 : return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
211 3387926 : : nullptr;
212 : }
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
|
