LLVM  13.0.0git
LexicalScopes.h
Go to the documentation of this file.
1 //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements LexicalScopes analysis.
10 //
11 // This pass collects lexical scope information and maps machine instructions
12 // to respective lexical scopes.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_LEXICALSCOPES_H
17 #define LLVM_CODEGEN_LEXICALSCOPES_H
18 
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
24 #include <cassert>
25 #include <unordered_map>
26 #include <utility>
27 
28 namespace llvm {
29 
30 class MachineBasicBlock;
31 class MachineFunction;
32 class MachineInstr;
33 class MDNode;
34 
35 //===----------------------------------------------------------------------===//
36 /// InsnRange - This is used to track range of instructions with identical
37 /// lexical scope.
38 ///
39 using InsnRange = std::pair<const MachineInstr *, const MachineInstr *>;
40 
41 //===----------------------------------------------------------------------===//
42 /// LexicalScope - This class is used to track scope information.
43 ///
44 class LexicalScope {
45 public:
47  bool A)
48  : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
49  assert(D);
50  assert(D->getSubprogram()->getUnit()->getEmissionKind() !=
52  "Don't build lexical scopes for non-debug locations");
53  assert(D->isResolved() && "Expected resolved node");
54  assert((!I || I->isResolved()) && "Expected resolved node");
55  if (Parent)
56  Parent->addChild(this);
57  }
58 
59  // Accessors.
60  LexicalScope *getParent() const { return Parent; }
61  const MDNode *getDesc() const { return Desc; }
62  const DILocation *getInlinedAt() const { return InlinedAtLocation; }
63  const DILocalScope *getScopeNode() const { return Desc; }
64  bool isAbstractScope() const { return AbstractScope; }
66  SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
67 
68  /// addChild - Add a child scope.
69  void addChild(LexicalScope *S) { Children.push_back(S); }
70 
71  /// openInsnRange - This scope covers instruction range starting from MI.
72  void openInsnRange(const MachineInstr *MI) {
73  if (!FirstInsn)
74  FirstInsn = MI;
75 
76  if (Parent)
77  Parent->openInsnRange(MI);
78  }
79 
80  /// extendInsnRange - Extend the current instruction range covered by
81  /// this scope.
83  assert(FirstInsn && "MI Range is not open!");
84  LastInsn = MI;
85  if (Parent)
86  Parent->extendInsnRange(MI);
87  }
88 
89  /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected
90  /// until now. This is used when a new scope is encountered while walking
91  /// machine instructions.
92  void closeInsnRange(LexicalScope *NewScope = nullptr) {
93  assert(LastInsn && "Last insn missing!");
94  Ranges.push_back(InsnRange(FirstInsn, LastInsn));
95  FirstInsn = nullptr;
96  LastInsn = nullptr;
97  // If Parent dominates NewScope then do not close Parent's instruction
98  // range.
99  if (Parent && (!NewScope || !Parent->dominates(NewScope)))
100  Parent->closeInsnRange(NewScope);
101  }
102 
103  /// dominates - Return true if current scope dominates given lexical scope.
104  bool dominates(const LexicalScope *S) const {
105  if (S == this)
106  return true;
107  if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
108  return true;
109  return false;
110  }
111 
112  // Depth First Search support to walk and manipulate LexicalScope hierarchy.
113  unsigned getDFSOut() const { return DFSOut; }
114  void setDFSOut(unsigned O) { DFSOut = O; }
115  unsigned getDFSIn() const { return DFSIn; }
116  void setDFSIn(unsigned I) { DFSIn = I; }
117 
118  /// dump - print lexical scope.
119  void dump(unsigned Indent = 0) const;
120 
121 private:
122  LexicalScope *Parent; // Parent to this scope.
123  const DILocalScope *Desc; // Debug info descriptor.
124  const DILocation *InlinedAtLocation; // Location at which this
125  // scope is inlined.
126  bool AbstractScope; // Abstract Scope
127  SmallVector<LexicalScope *, 4> Children; // Scopes defined in scope.
128  // Contents not owned.
130 
131  const MachineInstr *LastInsn = nullptr; // Last instruction of this scope.
132  const MachineInstr *FirstInsn = nullptr; // First instruction of this scope.
133  unsigned DFSIn = 0; // In & Out Depth use to determine scope nesting.
134  unsigned DFSOut = 0;
135 };
136 
137 //===----------------------------------------------------------------------===//
138 /// LexicalScopes - This class provides interface to collect and use lexical
139 /// scoping information from machine instruction.
140 ///
142 public:
143  LexicalScopes() = default;
144 
145  /// initialize - Scan machine function and constuct lexical scope nest, resets
146  /// the instance if necessary.
147  void initialize(const MachineFunction &);
148 
149  /// releaseMemory - release memory.
150  void reset();
151 
152  /// empty - Return true if there is any lexical scope information available.
153  bool empty() { return CurrentFnLexicalScope == nullptr; }
154 
155  /// getCurrentFunctionScope - Return lexical scope for the current function.
157  return CurrentFnLexicalScope;
158  }
159 
160  /// getMachineBasicBlocks - Populate given set using machine basic blocks
161  /// which have machine instructions that belong to lexical scope identified by
162  /// DebugLoc.
163  void getMachineBasicBlocks(const DILocation *DL,
165 
166  /// Return true if DebugLoc's lexical scope dominates at least one machine
167  /// instruction's lexical scope in a given machine basic block.
169 
170  /// findLexicalScope - Find lexical scope, either regular or inlined, for the
171  /// given DebugLoc. Return NULL if not found.
173 
174  /// getAbstractScopesList - Return a reference to list of abstract scopes.
176  return AbstractScopesList;
177  }
178 
179  /// findAbstractScope - Find an abstract scope or return null.
181  auto I = AbstractScopeMap.find(N);
182  return I != AbstractScopeMap.end() ? &I->second : nullptr;
183  }
184 
185  /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
187  auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
188  return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
189  }
190 
191  /// findLexicalScope - Find regular lexical scope or return null.
193  auto I = LexicalScopeMap.find(N);
194  return I != LexicalScopeMap.end() ? &I->second : nullptr;
195  }
196 
197  /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
199 
200 private:
201  /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If
202  /// not available then create new lexical scope.
203  LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope,
204  const DILocation *IA = nullptr);
205  LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
206  return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
207  : nullptr;
208  }
209 
210  /// getOrCreateRegularScope - Find or create a regular lexical scope.
211  LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope);
212 
213  /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
214  LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope,
215  const DILocation *InlinedAt);
216 
217  /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
218  /// for the given machine function.
219  void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
220  DenseMap<const MachineInstr *, LexicalScope *> &M);
221  void constructScopeNest(LexicalScope *Scope);
222  void
223  assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
224  DenseMap<const MachineInstr *, LexicalScope *> &M);
225 
226  const MachineFunction *MF = nullptr;
227 
228  /// LexicalScopeMap - Tracks the scopes in the current function.
229  // Use an unordered_map to ensure value pointer validity over insertion.
230  std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap;
231 
232  /// InlinedLexicalScopeMap - Tracks inlined function scopes in current
233  /// function.
234  std::unordered_map<std::pair<const DILocalScope *, const DILocation *>,
235  LexicalScope,
236  pair_hash<const DILocalScope *, const DILocation *>>
237  InlinedLexicalScopeMap;
238 
239  /// AbstractScopeMap - These scopes are not included LexicalScopeMap.
240  // Use an unordered_map to ensure value pointer validity over insertion.
241  std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap;
242 
243  /// AbstractScopesList - Tracks abstract scopes constructed while processing
244  /// a function.
245  SmallVector<LexicalScope *, 4> AbstractScopesList;
246 
247  /// CurrentFnLexicalScope - Top level scope for the current function.
248  ///
249  LexicalScope *CurrentFnLexicalScope = nullptr;
250 
251  /// Map a location to the set of basic blocks it dominates. This is a cache
252  /// for \ref LexicalScopes::getMachineBasicBlocks results.
253  using BlockSetT = SmallPtrSet<const MachineBasicBlock *, 4>;
254  DenseMap<const DILocation *, std::unique_ptr<BlockSetT>> DominatedBlocks;
255 };
256 
257 } // end namespace llvm
258 
259 #endif // LLVM_CODEGEN_LEXICALSCOPES_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm
Definition: AllocatorList.h:23
DebugInfoMetadata.h
llvm::LexicalScope::setDFSIn
void setDFSIn(unsigned I)
Definition: LexicalScopes.h:116
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LexicalScope
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
llvm::LexicalScope::getDFSIn
unsigned getDFSIn() const
Definition: LexicalScopes.h:115
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1558
DenseMap.h
llvm::LexicalScopes::getMachineBasicBlocks
void getMachineBasicBlocks(const DILocation *DL, SmallPtrSetImpl< const MachineBasicBlock * > &MBBs)
getMachineBasicBlocks - Populate given set using machine basic blocks which have machine instructions...
Definition: LexicalScopes.cpp:280
llvm::LexicalScopes::initialize
void initialize(const MachineFunction &)
initialize - Scan machine function and constuct lexical scope nest, resets the instance if necessary.
Definition: LexicalScopes.cpp:51
llvm::LexicalScope::getRanges
SmallVectorImpl< InsnRange > & getRanges()
Definition: LexicalScopes.h:66
llvm::LexicalScopes::dominates
bool dominates(const DILocation *DL, MachineBasicBlock *MBB)
Return true if DebugLoc's lexical scope dominates at least one machine instruction's lexical scope in...
Definition: LexicalScopes.cpp:306
llvm::LexicalScope::LexicalScope
LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I, bool A)
Definition: LexicalScopes.h:46
llvm::LexicalScope::dominates
bool dominates(const LexicalScope *S) const
dominates - Return true if current scope dominates given lexical scope.
Definition: LexicalScopes.h:104
llvm::LexicalScope::getParent
LexicalScope * getParent() const
Definition: LexicalScopes.h:60
llvm::LexicalScopes::reset
void reset()
releaseMemory - release memory.
Definition: LexicalScopes.cpp:40
llvm::LexicalScope::getDFSOut
unsigned getDFSOut() const
Definition: LexicalScopes.h:113
SmallPtrSet.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::LexicalScopes::getOrCreateAbstractScope
LexicalScope * getOrCreateAbstractScope(const DILocalScope *Scope)
getOrCreateAbstractScope - Find or create an abstract lexical scope.
Definition: LexicalScopes.cpp:212
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:190
llvm::LexicalScopes::findAbstractScope
LexicalScope * findAbstractScope(const DILocalScope *N)
findAbstractScope - Find an abstract scope or return null.
Definition: LexicalScopes.h:180
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::LexicalScope::closeInsnRange
void closeInsnRange(LexicalScope *NewScope=nullptr)
closeInsnRange - Create a range based on FirstInsn and LastInsn collected until now.
Definition: LexicalScopes.h:92
I
#define I(x, y, z)
Definition: MD5.cpp:59
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LexicalScope::getInlinedAt
const DILocation * getInlinedAt() const
Definition: LexicalScopes.h:62
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
llvm::LexicalScope::openInsnRange
void openInsnRange(const MachineInstr *MI)
openInsnRange - This scope covers instruction range starting from MI.
Definition: LexicalScopes.h:72
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::InsnRange
std::pair< const MachineInstr *, const MachineInstr * > InsnRange
InsnRange - This is used to track range of instructions with identical lexical scope.
Definition: LexicalScopes.h:39
llvm::DICompileUnit::NoDebug
@ NoDebug
Definition: DebugInfoMetadata.h:1319
llvm::LexicalScopes::empty
bool empty()
empty - Return true if there is any lexical scope information available.
Definition: LexicalScopes.h:153
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LexicalScopes::getAbstractScopesList
ArrayRef< LexicalScope * > getAbstractScopesList() const
getAbstractScopesList - Return a reference to list of abstract scopes.
Definition: LexicalScopes.h:175
llvm::LexicalScope::setDFSOut
void setDFSOut(unsigned O)
Definition: LexicalScopes.h:114
llvm::LexicalScopes::findLexicalScope
LexicalScope * findLexicalScope(const DILocalScope *N)
findLexicalScope - Find regular lexical scope or return null.
Definition: LexicalScopes.h:192
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LexicalScope::getScopeNode
const DILocalScope * getScopeNode() const
Definition: LexicalScopes.h:63
llvm::LexicalScopes::findInlinedScope
LexicalScope * findInlinedScope(const DILocalScope *N, const DILocation *IA)
findInlinedScope - Find an inlined scope for the given scope/inlined-at.
Definition: LexicalScopes.h:186
llvm::LexicalScopes::findLexicalScope
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
Definition: LexicalScopes.cpp:124
llvm::LexicalScope::extendInsnRange
void extendInsnRange(const MachineInstr *MI)
extendInsnRange - Extend the current instruction range covered by this scope.
Definition: LexicalScopes.h:82
llvm::LexicalScope::getDesc
const MDNode * getDesc() const
Definition: LexicalScopes.h:61
SmallVector.h
llvm::LexicalScope::addChild
void addChild(LexicalScope *S)
addChild - Add a child scope.
Definition: LexicalScopes.h:69
N
#define N
llvm::LexicalScopes::getCurrentFunctionScope
LexicalScope * getCurrentFunctionScope() const
getCurrentFunctionScope - Return lexical scope for the current function.
Definition: LexicalScopes.h:156
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallPtrSetImpl< const MachineBasicBlock * >
llvm::DILocalScope
A scope for locals.
Definition: DebugInfoMetadata.h:1528
llvm::LexicalScope::isAbstractScope
bool isAbstractScope() const
Definition: LexicalScopes.h:64
llvm::LexicalScopes
LexicalScopes - This class provides interface to collect and use lexical scoping information from mac...
Definition: LexicalScopes.h:141
llvm::LexicalScope::dump
void dump(unsigned Indent=0) const
dump - print lexical scope.
Definition: LexicalScopes.cpp:331
llvm::LexicalScope::getChildren
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:65
llvm::LexicalScopes::LexicalScopes
LexicalScopes()=default