LLVM  12.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  // Check if instruction has valid location information.
79  const DILocation *MIDL = MInsn.getDebugLoc();
80  if (!MIDL) {
81  PrevMI = &MInsn;
82  continue;
83  }
84 
85  // If scope has not changed then skip this instruction.
86  if (MIDL == PrevDL) {
87  PrevMI = &MInsn;
88  continue;
89  }
90 
91  // Ignore DBG_VALUE and similar instruction that do not contribute to any
92  // instruction in the output.
93  if (MInsn.isMetaInstruction())
94  continue;
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->count(MBB) != 0;
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
void openInsnRange(const MachineInstr *MI)
openInsnRange - This scope covers instruction range starting from MI.
Definition: LexicalScopes.h:72
void extendInsnRange(const MachineInstr *MI)
extendInsnRange - Extend the current instruction range covered by this scope.
Definition: LexicalScopes.h:82
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:508
void dump(unsigned Indent=0) const
dump - print lexical scope.
bool dominates(const DILocation *DL, MachineBasicBlock *MBB)
Return true if DebugLoc&#39;s lexical scope dominates at least one machine instruction&#39;s lexical scope in...
This file contains the declarations for metadata subclasses.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
SmallVectorImpl< InsnRange > & getRanges()
Definition: LexicalScopes.h:66
Metadata node.
Definition: Metadata.h:870
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:44
A scope for locals.
Function & getFunction()
Return the LLVM function that this machine code represents.
MachineBasicBlock & MBB
LexicalScope * getOrCreateAbstractScope(const DILocalScope *Scope)
getOrCreateAbstractScope - Find or create an abstract lexical scope.
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:65
void setDFSOut(unsigned O)
void reset()
releaseMemory - release memory.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
void initialize(const MachineFunction &)
initialize - Scan machine function and constuct lexical scope nest, resets the instance if necessary...
LexicalScope * findLexicalScope(const DILocation *DL)
findLexicalScope - Find lexical scope, either regular or inlined, for the given DebugLoc.
Debug location.
#define P(N)
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1528
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
constexpr double e
Definition: MathExtras.h:58
void getMachineBasicBlocks(const DILocation *DL, SmallPtrSetImpl< const MachineBasicBlock *> &MBBs)
getMachineBasicBlocks - Populate given set using machine basic blocks which have machine instructions...
DILocalScope * getNonLexicalBlockFileScope() const
Get the first non DILexicalBlockFile scope of this scope.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Representation of each machine instruction.
Definition: MachineInstr.h:62
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void closeInsnRange(LexicalScope *NewScope=nullptr)
closeInsnRange - Create a range based on FirstInsn and LastInsn collected until now.
Definition: LexicalScopes.h:92
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
void dump() const
User-friendly dump.
Definition: AsmWriter.cpp:4632
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
bool dominates(const LexicalScope *S) const
dominates - Return true if current scope dominates given lexical scope.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
std::pair< const MachineInstr *, const MachineInstr * > InsnRange
InsnRange - This is used to track range of instructions with identical lexical scope.
Definition: LexicalScopes.h:39
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL