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