LLVM  13.0.0git
LexicalScopes.cpp
Go to the documentation of this file.
1 //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
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 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Config/llvm-config.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/Support/Casting.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/Support/Debug.h"
30 #include <cassert>
31 #include <string>
32 #include <tuple>
33 #include <utility>
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "lexicalscopes"
38 
39 /// reset - Reset the instance so that it's prepared for another function.
41  MF = nullptr;
42  CurrentFnLexicalScope = nullptr;
43  LexicalScopeMap.clear();
44  AbstractScopeMap.clear();
45  InlinedLexicalScopeMap.clear();
46  AbstractScopesList.clear();
47  DominatedBlocks.clear();
48 }
49 
50 /// initialize - Scan machine function and constuct lexical scope nest.
52  reset();
53  // Don't attempt any lexical scope creation for a NoDebug compile unit.
54  if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
56  return;
57  MF = &Fn;
60  extractLexicalScopes(MIRanges, MI2ScopeMap);
61  if (CurrentFnLexicalScope) {
62  constructScopeNest(CurrentFnLexicalScope);
63  assignInstructionRanges(MIRanges, MI2ScopeMap);
64  }
65 }
66 
67 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
68 /// for the given machine function.
69 void LexicalScopes::extractLexicalScopes(
72  // Scan each instruction and create scopes. First build working set of scopes.
73  for (const auto &MBB : *MF) {
74  const MachineInstr *RangeBeginMI = nullptr;
75  const MachineInstr *PrevMI = nullptr;
76  const DILocation *PrevDL = nullptr;
77  for (const auto &MInsn : MBB) {
78  // Ignore DBG_VALUE and similar instruction that do not contribute to any
79  // instruction in the output.
80  if (MInsn.isMetaInstruction())
81  continue;
82 
83  // Check if instruction has valid location information.
84  const DILocation *MIDL = MInsn.getDebugLoc();
85  if (!MIDL) {
86  PrevMI = &MInsn;
87  continue;
88  }
89 
90  // If scope has not changed then skip this instruction.
91  if (MIDL == PrevDL) {
92  PrevMI = &MInsn;
93  continue;
94  }
95 
96  if (RangeBeginMI) {
97  // If we have already seen a beginning of an instruction range and
98  // current instruction scope does not match scope of first instruction
99  // in this range then create a new instruction range.
100  InsnRange R(RangeBeginMI, PrevMI);
101  MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
102  MIRanges.push_back(R);
103  }
104 
105  // This is a beginning of a new instruction range.
106  RangeBeginMI = &MInsn;
107 
108  // Reset previous markers.
109  PrevMI = &MInsn;
110  PrevDL = MIDL;
111  }
112 
113  // Create last instruction range.
114  if (RangeBeginMI && PrevMI && PrevDL) {
115  InsnRange R(RangeBeginMI, PrevMI);
116  MIRanges.push_back(R);
117  MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
118  }
119  }
120 }
121 
122 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
123 /// given DebugLoc. Return NULL if not found.
125  DILocalScope *Scope = DL->getScope();
126  if (!Scope)
127  return nullptr;
128 
129  // The scope that we were created with could have an extra file - which
130  // isn't what we care about in this case.
131  Scope = Scope->getNonLexicalBlockFileScope();
132 
133  if (auto *IA = DL->getInlinedAt()) {
134  auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
135  return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
136  }
137  return findLexicalScope(Scope);
138 }
139 
140 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
141 /// not available then create new lexical scope.
142 LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
143  const DILocation *IA) {
144  if (IA) {
145  // Skip scopes inlined from a NoDebug compile unit.
146  if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
148  return getOrCreateLexicalScope(IA);
149  // Create an abstract scope for inlined function.
151  // Create an inlined scope for inlined function.
152  return getOrCreateInlinedScope(Scope, IA);
153  }
154 
155  return getOrCreateRegularScope(Scope);
156 }
157 
158 /// getOrCreateRegularScope - Find or create a regular lexical scope.
159 LexicalScope *
160 LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
161  assert(Scope && "Invalid Scope encoding!");
162  Scope = Scope->getNonLexicalBlockFileScope();
163 
164  auto I = LexicalScopeMap.find(Scope);
165  if (I != LexicalScopeMap.end())
166  return &I->second;
167 
168  // FIXME: Should the following dyn_cast be DILexicalBlock?
169  LexicalScope *Parent = nullptr;
170  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
171  Parent = getOrCreateLexicalScope(Block->getScope());
172  I = LexicalScopeMap.emplace(std::piecewise_construct,
173  std::forward_as_tuple(Scope),
174  std::forward_as_tuple(Parent, Scope, nullptr,
175  false)).first;
176 
177  if (!Parent) {
178  assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction()));
179  assert(!CurrentFnLexicalScope);
180  CurrentFnLexicalScope = &I->second;
181  }
182 
183  return &I->second;
184 }
185 
186 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
187 LexicalScope *
188 LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
189  const DILocation *InlinedAt) {
190  assert(Scope && "Invalid Scope encoding!");
191  Scope = Scope->getNonLexicalBlockFileScope();
192  std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
193  auto I = InlinedLexicalScopeMap.find(P);
194  if (I != InlinedLexicalScopeMap.end())
195  return &I->second;
196 
197  LexicalScope *Parent;
198  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
199  Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
200  else
201  Parent = getOrCreateLexicalScope(InlinedAt);
202 
203  I = InlinedLexicalScopeMap
204  .emplace(std::piecewise_construct, std::forward_as_tuple(P),
205  std::forward_as_tuple(Parent, Scope, InlinedAt, false))
206  .first;
207  return &I->second;
208 }
209 
210 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
211 LexicalScope *
213  assert(Scope && "Invalid Scope encoding!");
214  Scope = Scope->getNonLexicalBlockFileScope();
215  auto I = AbstractScopeMap.find(Scope);
216  if (I != AbstractScopeMap.end())
217  return &I->second;
218 
219  // FIXME: Should the following isa be DILexicalBlock?
220  LexicalScope *Parent = nullptr;
221  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
222  Parent = getOrCreateAbstractScope(Block->getScope());
223 
224  I = AbstractScopeMap.emplace(std::piecewise_construct,
225  std::forward_as_tuple(Scope),
226  std::forward_as_tuple(Parent, Scope,
227  nullptr, true)).first;
228  if (isa<DISubprogram>(Scope))
229  AbstractScopesList.push_back(&I->second);
230  return &I->second;
231 }
232 
233 /// constructScopeNest - Traverse the Scope tree depth-first, storing
234 /// traversal state in WorkStack and recording the depth-first
235 /// numbering (setDFSIn, setDFSOut) for edge classification.
236 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
237  assert(Scope && "Unable to calculate scope dominance graph!");
239  WorkStack.push_back(std::make_pair(Scope, 0));
240  unsigned Counter = 0;
241  while (!WorkStack.empty()) {
242  auto &ScopePosition = WorkStack.back();
243  LexicalScope *WS = ScopePosition.first;
244  size_t ChildNum = ScopePosition.second++;
245  const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
246  if (ChildNum < Children.size()) {
247  auto &ChildScope = Children[ChildNum];
248  WorkStack.push_back(std::make_pair(ChildScope, 0));
249  ChildScope->setDFSIn(++Counter);
250  } else {
251  WorkStack.pop_back();
252  WS->setDFSOut(++Counter);
253  }
254  }
255 }
256 
257 /// assignInstructionRanges - Find ranges of instructions covered by each
258 /// lexical scope.
259 void LexicalScopes::assignInstructionRanges(
260  SmallVectorImpl<InsnRange> &MIRanges,
262  LexicalScope *PrevLexicalScope = nullptr;
263  for (const auto &R : MIRanges) {
264  LexicalScope *S = MI2ScopeMap.lookup(R.first);
265  assert(S && "Lost LexicalScope for a machine instruction!");
266  if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
267  PrevLexicalScope->closeInsnRange(S);
268  S->openInsnRange(R.first);
269  S->extendInsnRange(R.second);
270  PrevLexicalScope = S;
271  }
272 
273  if (PrevLexicalScope)
274  PrevLexicalScope->closeInsnRange();
275 }
276 
277 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
278 /// have machine instructions that belong to lexical scope identified by
279 /// DebugLoc.
282  assert(MF && "Method called on a uninitialized LexicalScopes object!");
283  MBBs.clear();
284 
285  LexicalScope *Scope = getOrCreateLexicalScope(DL);
286  if (!Scope)
287  return;
288 
289  if (Scope == CurrentFnLexicalScope) {
290  for (const auto &MBB : *MF)
291  MBBs.insert(&MBB);
292  return;
293  }
294 
295  // The scope ranges can cover multiple basic blocks in each span. Iterate over
296  // all blocks (in the order they are in the function) until we reach the one
297  // containing the end of the span.
298  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
299  for (auto &R : InsnRanges)
300  for (auto CurMBBIt = R.first->getParent()->getIterator(),
301  EndBBIt = std::next(R.second->getParent()->getIterator());
302  CurMBBIt != EndBBIt; CurMBBIt++)
303  MBBs.insert(&*CurMBBIt);
304 }
305 
307  assert(MF && "Unexpected uninitialized LexicalScopes object!");
308  LexicalScope *Scope = getOrCreateLexicalScope(DL);
309  if (!Scope)
310  return false;
311 
312  // Current function scope covers all basic blocks in the function.
313  if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
314  return true;
315 
316  // Fetch all the blocks in DLs scope. Because the range / block list also
317  // contain any subscopes, any instruction that DL dominates can be found in
318  // the block set.
319  //
320  // Cache the set of fetched blocks to avoid repeatedly recomputing the set in
321  // the LiveDebugValues pass.
322  std::unique_ptr<BlockSetT> &Set = DominatedBlocks[DL];
323  if (!Set) {
324  Set = std::make_unique<BlockSetT>();
325  getMachineBasicBlocks(DL, *Set);
326  }
327  return Set->contains(MBB);
328 }
329 
330 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
331 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
332  raw_ostream &err = dbgs();
333  err.indent(Indent);
334  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
335  const MDNode *N = Desc;
336  err.indent(Indent);
337  N->dump();
338  if (AbstractScope)
339  err << std::string(Indent, ' ') << "Abstract Scope\n";
340 
341  if (!Children.empty())
342  err << std::string(Indent + 2, ' ') << "Children ...\n";
343  for (unsigned i = 0, e = Children.size(); i != e; ++i)
344  if (Children[i] != this)
345  Children[i]->dump(Indent + 2);
346 }
347 #endif
i
i
Definition: README.txt:29
MachineInstr.h
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:499
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Metadata.h
DebugInfoMetadata.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
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< InsnRange, 4 >
llvm::LexicalScope
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
llvm::Function::getSubprogram
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1532
MachineBasicBlock.h
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
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::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::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:180
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::LexicalScope::dominates
bool dominates(const LexicalScope *S) const
dominates - Return true if current scope dominates given lexical scope.
Definition: LexicalScopes.h:104
LexicalScopes.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::LexicalScopes::reset
void reset()
releaseMemory - release memory.
Definition: LexicalScopes.cpp:40
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::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::LexicalScope::closeInsnRange
void closeInsnRange(LexicalScope *NewScope=nullptr)
closeInsnRange - Create a range based on FirstInsn and LastInsn collected until now.
Definition: LexicalScopes.h:92
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
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:1323
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::LexicalScope::setDFSOut
void setDFSOut(unsigned O)
Definition: LexicalScopes.h:114
Compiler.h
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::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:588
llvm::LexicalScopes::findLexicalScope
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
Definition: LexicalScopes.cpp:124
Casting.h
Function.h
SmallVector.h
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:497
N
#define N
llvm::SmallVectorImpl< InsnRange >
llvm::SmallPtrSetImpl< const MachineBasicBlock * >
llvm::DILocalScope
A scope for locals.
Definition: DebugInfoMetadata.h:1532
raw_ostream.h
MachineFunction.h
llvm::pdb::PDB_SymType::Block
@ Block
Debug.h
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::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364