LLVM  6.0.0svn
LexicalScopes.h
Go to the documentation of this file.
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"
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:
48  bool A)
49  : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
50  assert(D);
51  assert(D->getSubprogram()->getUnit()->getEmissionKind() !=
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  if (Parent)
57  Parent->addChild(this);
58  }
59 
60  // Accessors.
61  LexicalScope *getParent() const { return Parent; }
62  const MDNode *getDesc() const { return Desc; }
63  const DILocation *getInlinedAt() const { return InlinedAtLocation; }
64  const DILocalScope *getScopeNode() const { return Desc; }
65  bool isAbstractScope() const { return AbstractScope; }
67  SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
68 
69  /// addChild - Add a child scope.
70  void addChild(LexicalScope *S) { Children.push_back(S); }
71 
72  /// openInsnRange - This scope covers instruction range starting from MI.
73  void openInsnRange(const MachineInstr *MI) {
74  if (!FirstInsn)
75  FirstInsn = MI;
76 
77  if (Parent)
78  Parent->openInsnRange(MI);
79  }
80 
81  /// extendInsnRange - Extend the current instruction range covered by
82  /// this scope.
84  assert(FirstInsn && "MI Range is not open!");
85  LastInsn = MI;
86  if (Parent)
87  Parent->extendInsnRange(MI);
88  }
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  void closeInsnRange(LexicalScope *NewScope = nullptr) {
94  assert(LastInsn && "Last insn missing!");
95  Ranges.push_back(InsnRange(FirstInsn, LastInsn));
96  FirstInsn = nullptr;
97  LastInsn = nullptr;
98  // If Parent dominates NewScope then do not close Parent's instruction
99  // range.
100  if (Parent && (!NewScope || !Parent->dominates(NewScope)))
101  Parent->closeInsnRange(NewScope);
102  }
103 
104  /// dominates - Return true if current scope dominates given lexical scope.
105  bool dominates(const LexicalScope *S) const {
106  if (S == this)
107  return true;
108  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  unsigned getDFSOut() const { return DFSOut; }
115  void setDFSOut(unsigned O) { DFSOut = O; }
116  unsigned getDFSIn() const { return DFSIn; }
117  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.
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 ///
143 public:
144  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  bool empty() { return CurrentFnLexicalScope == nullptr; }
155 
156  /// getCurrentFunctionScope - Return lexical scope for the current function.
158  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,
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.
177  return AbstractScopesList;
178  }
179 
180  /// findAbstractScope - Find an abstract scope or return null.
182  auto I = AbstractScopeMap.find(N);
183  return I != AbstractScopeMap.end() ? &I->second : nullptr;
184  }
185 
186  /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
188  auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
189  return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
190  }
191 
192  /// findLexicalScope - Find regular lexical scope or return null.
194  auto I = LexicalScopeMap.find(N);
195  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  LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
210  return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
211  : 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,
225  void constructScopeNest(LexicalScope *Scope);
226  void
227  assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
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,
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
void push_back(const T &Elt)
Definition: SmallVector.h:212
void openInsnRange(const MachineInstr *MI)
openInsnRange - This scope covers instruction range starting from MI.
Definition: LexicalScopes.h:73
const DILocalScope * getScopeNode() const
Definition: LexicalScopes.h:64
void extendInsnRange(const MachineInstr *MI)
extendInsnRange - Extend the current instruction range covered by this scope.
Definition: LexicalScopes.h:83
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool isAbstractScope() const
Definition: LexicalScopes.h:65
void dump(unsigned Indent=0) const
dump - print lexical scope.
const MDNode * getDesc() const
Definition: LexicalScopes.h:62
SmallVectorImpl< InsnRange > & getRanges()
Definition: LexicalScopes.h:67
Metadata node.
Definition: Metadata.h:862
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:45
A scope for locals.
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:66
LexicalScope * getParent() const
Definition: LexicalScopes.h:61
bool isResolved() const
Check if node is fully resolved.
Definition: Metadata.h:938
void setDFSOut(unsigned O)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Debug location.
LexicalScope * findAbstractScope(const DILocalScope *N)
findAbstractScope - Find an abstract scope or return null.
#define P(N)
const DILocation * getInlinedAt() const
Definition: LexicalScopes.h:63
LexicalScope * findLexicalScope(const DILocalScope *N)
findLexicalScope - Find regular lexical scope or return null.
void setDFSIn(unsigned I)
LexicalScope * findInlinedScope(const DILocalScope *N, const DILocation *IA)
findInlinedScope - Find an inlined scope for the given scope/inlined-at.
unsigned getDFSOut() const
unsigned getDFSIn() const
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I, bool A)
Definition: LexicalScopes.h:47
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
initialize - Initialize the set of available library functions based on the specified target triple...
Representation of each machine instruction.
Definition: MachineInstr.h:59
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
void closeInsnRange(LexicalScope *NewScope=nullptr)
closeInsnRange - Create a range based on FirstInsn and LastInsn collected until now.
Definition: LexicalScopes.h:93
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
void addChild(LexicalScope *S)
addChild - Add a child scope.
Definition: LexicalScopes.h:70
ArrayRef< LexicalScope * > getAbstractScopesList() const
getAbstractScopesList - Return a reference to list of abstract scopes.
bool dominates(const LexicalScope *S) const
dominates - Return true if current scope dominates given lexical scope.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
std::pair< const MachineInstr *, const MachineInstr * > InsnRange
InsnRange - This is used to track range of instructions with identical lexical scope.
Definition: LexicalScopes.h:40
bool empty()
empty - Return true if there is any lexical scope information available.
LexicalScope * getCurrentFunctionScope() const
getCurrentFunctionScope - Return lexical scope for the current function.