1 //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements LexicalScopes analysis.
12 // This pass collects lexical scope information and maps machine instructions
13 // to respective lexical scopes.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CODEGEN_LEXICALSCOPES_H
18 #define LLVM_CODEGEN_LEXICALSCOPES_H
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"
26 #include <unordered_map>
31 class MachineBasicBlock;
32 class MachineFunction;
36 //===----------------------------------------------------------------------===//
37 /// InsnRange - This is used to track range of instructions with identical
40 using InsnRange = std::pair<const MachineInstr *, const MachineInstr *>;
42 //===----------------------------------------------------------------------===//
43 /// LexicalScope - This class is used to track scope information.
47 LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I,
49 : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
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");
57 Parent->addChild(this);
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; }
66 SmallVectorImpl<LexicalScope *> &getChildren() { return Children; }
67 SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
69 /// addChild - Add a child scope.
70 void addChild(LexicalScope *S) { Children.push_back(S); }
72 /// openInsnRange - This scope covers instruction range starting from MI.
73 void openInsnRange(const MachineInstr *MI) {
78 Parent->openInsnRange(MI);
81 /// extendInsnRange - Extend the current instruction range covered by
83 void extendInsnRange(const MachineInstr *MI) {
84 assert(FirstInsn && "MI Range is not open!");
87 Parent->extendInsnRange(MI);
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));
98 // If Parent dominates NewScope then do not close Parent's instruction
100 if (Parent && (!NewScope || !Parent->dominates(NewScope)))
101 Parent->closeInsnRange(NewScope);
104 /// dominates - Return true if current scope dominates given lexical scope.
105 bool dominates(const LexicalScope *S) const {
108 if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
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; }
119 /// dump - print lexical scope.
120 void dump(unsigned Indent = 0) const;
123 LexicalScope *Parent; // Parent to this scope.
124 const DILocalScope *Desc; // Debug info descriptor.
125 const DILocation *InlinedAtLocation; // Location at which this
127 bool AbstractScope; // Abstract Scope
128 SmallVector<LexicalScope *, 4> Children; // Scopes defined in scope.
129 // Contents not owned.
130 SmallVector<InsnRange, 4> Ranges;
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.
138 //===----------------------------------------------------------------------===//
139 /// LexicalScopes - This class provides interface to collect and use lexical
140 /// scoping information from machine instruction.
142 class LexicalScopes {
144 LexicalScopes() = default;
146 /// initialize - Scan machine function and constuct lexical scope nest, resets
147 /// the instance if necessary.
148 void initialize(const MachineFunction &);
150 /// releaseMemory - release memory.
153 /// empty - Return true if there is any lexical scope information available.
154 bool empty() { return CurrentFnLexicalScope == nullptr; }
156 /// getCurrentFunctionScope - Return lexical scope for the current function.
157 LexicalScope *getCurrentFunctionScope() const {
158 return CurrentFnLexicalScope;
161 /// getMachineBasicBlocks - Populate given set using machine basic blocks
162 /// which have machine instructions that belong to lexical scope identified by
164 void getMachineBasicBlocks(const DILocation *DL,
165 SmallPtrSetImpl<const MachineBasicBlock *> &MBBs);
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);
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);
175 /// getAbstractScopesList - Return a reference to list of abstract scopes.
176 ArrayRef<LexicalScope *> getAbstractScopesList() const {
177 return AbstractScopesList;
180 /// findAbstractScope - Find an abstract scope or return null.
181 LexicalScope *findAbstractScope(const DILocalScope *N) {
182 auto I = AbstractScopeMap.find(N);
183 return I != AbstractScopeMap.end() ? &I->second : nullptr;
186 /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
187 LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) {
188 auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
189 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
192 /// findLexicalScope - Find regular lexical scope or return null.
193 LexicalScope *findLexicalScope(const DILocalScope *N) {
194 auto I = LexicalScopeMap.find(N);
195 return I != LexicalScopeMap.end() ? &I->second : nullptr;
198 /// dump - Print data structures to dbgs().
201 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
202 LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope);
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())
214 /// getOrCreateRegularScope - Find or create a regular lexical scope.
215 LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope);
217 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
218 LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope,
219 const DILocation *InlinedAt);
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);
227 assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
228 DenseMap<const MachineInstr *, LexicalScope *> &M);
230 const MachineFunction *MF = nullptr;
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;
236 /// InlinedLexicalScopeMap - Tracks inlined function scopes in current
238 std::unordered_map<std::pair<const DILocalScope *, const DILocation *>,
240 pair_hash<const DILocalScope *, const DILocation *>>
241 InlinedLexicalScopeMap;
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;
247 /// AbstractScopesList - Tracks abstract scopes constructed while processing
249 SmallVector<LexicalScope *, 4> AbstractScopesList;
251 /// CurrentFnLexicalScope - Top level scope for the current function.
253 LexicalScope *CurrentFnLexicalScope = nullptr;
256 } // end namespace llvm
258 #endif // LLVM_CODEGEN_LEXICALSCOPES_H