LLVM  7.0.0svn
LexicalScopes.cpp
Go to the documentation of this file.
1 //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
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 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Config/llvm-config.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 }
48 
49 /// initialize - Scan machine function and constuct lexical scope nest.
51  reset();
52  // Don't attempt any lexical scope creation for a NoDebug compile unit.
53  if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
55  return;
56  MF = &Fn;
59  extractLexicalScopes(MIRanges, MI2ScopeMap);
60  if (CurrentFnLexicalScope) {
61  constructScopeNest(CurrentFnLexicalScope);
62  assignInstructionRanges(MIRanges, MI2ScopeMap);
63  }
64 }
65 
66 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
67 /// for the given machine function.
68 void LexicalScopes::extractLexicalScopes(
71  // Scan each instruction and create scopes. First build working set of scopes.
72  for (const auto &MBB : *MF) {
73  const MachineInstr *RangeBeginMI = nullptr;
74  const MachineInstr *PrevMI = nullptr;
75  const DILocation *PrevDL = nullptr;
76  for (const auto &MInsn : MBB) {
77  // Check if instruction has valid location information.
78  const DILocation *MIDL = MInsn.getDebugLoc();
79  if (!MIDL) {
80  PrevMI = &MInsn;
81  continue;
82  }
83 
84  // If scope has not changed then skip this instruction.
85  if (MIDL == PrevDL) {
86  PrevMI = &MInsn;
87  continue;
88  }
89 
90  // Ignore DBG_VALUE and similar instruction that do not contribute to any
91  // instruction in the output.
92  if (MInsn.isMetaInstruction())
93  continue;
94 
95  if (RangeBeginMI) {
96  // If we have already seen a beginning of an instruction range and
97  // current instruction scope does not match scope of first instruction
98  // in this range then create a new instruction range.
99  InsnRange R(RangeBeginMI, PrevMI);
100  MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
101  MIRanges.push_back(R);
102  }
103 
104  // This is a beginning of a new instruction range.
105  RangeBeginMI = &MInsn;
106 
107  // Reset previous markers.
108  PrevMI = &MInsn;
109  PrevDL = MIDL;
110  }
111 
112  // Create last instruction range.
113  if (RangeBeginMI && PrevMI && PrevDL) {
114  InsnRange R(RangeBeginMI, PrevMI);
115  MIRanges.push_back(R);
116  MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
117  }
118  }
119 }
120 
121 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
122 /// given DebugLoc. Return NULL if not found.
124  DILocalScope *Scope = DL->getScope();
125  if (!Scope)
126  return nullptr;
127 
128  // The scope that we were created with could have an extra file - which
129  // isn't what we care about in this case.
130  Scope = Scope->getNonLexicalBlockFileScope();
131 
132  if (auto *IA = DL->getInlinedAt()) {
133  auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
134  return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
135  }
136  return findLexicalScope(Scope);
137 }
138 
139 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
140 /// not available then create new lexical scope.
141 LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope,
142  const DILocation *IA) {
143  if (IA) {
144  // Skip scopes inlined from a NoDebug compile unit.
145  if (Scope->getSubprogram()->getUnit()->getEmissionKind() ==
147  return getOrCreateLexicalScope(IA);
148  // Create an abstract scope for inlined function.
150  // Create an inlined scope for inlined function.
151  return getOrCreateInlinedScope(Scope, IA);
152  }
153 
154  return getOrCreateRegularScope(Scope);
155 }
156 
157 /// getOrCreateRegularScope - Find or create a regular lexical scope.
158 LexicalScope *
159 LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) {
160  assert(Scope && "Invalid Scope encoding!");
161  Scope = Scope->getNonLexicalBlockFileScope();
162 
163  auto I = LexicalScopeMap.find(Scope);
164  if (I != LexicalScopeMap.end())
165  return &I->second;
166 
167  // FIXME: Should the following dyn_cast be DILexicalBlock?
168  LexicalScope *Parent = nullptr;
169  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
170  Parent = getOrCreateLexicalScope(Block->getScope());
171  I = LexicalScopeMap.emplace(std::piecewise_construct,
172  std::forward_as_tuple(Scope),
173  std::forward_as_tuple(Parent, Scope, nullptr,
174  false)).first;
175 
176  if (!Parent) {
177  assert(cast<DISubprogram>(Scope)->describes(&MF->getFunction()));
178  assert(!CurrentFnLexicalScope);
179  CurrentFnLexicalScope = &I->second;
180  }
181 
182  return &I->second;
183 }
184 
185 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
186 LexicalScope *
187 LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope,
188  const DILocation *InlinedAt) {
189  assert(Scope && "Invalid Scope encoding!");
190  Scope = Scope->getNonLexicalBlockFileScope();
191  std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt);
192  auto I = InlinedLexicalScopeMap.find(P);
193  if (I != InlinedLexicalScopeMap.end())
194  return &I->second;
195 
196  LexicalScope *Parent;
197  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
198  Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
199  else
200  Parent = getOrCreateLexicalScope(InlinedAt);
201 
202  I = InlinedLexicalScopeMap
203  .emplace(std::piecewise_construct, std::forward_as_tuple(P),
204  std::forward_as_tuple(Parent, Scope, InlinedAt, false))
205  .first;
206  return &I->second;
207 }
208 
209 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
210 LexicalScope *
212  assert(Scope && "Invalid Scope encoding!");
213  Scope = Scope->getNonLexicalBlockFileScope();
214  auto I = AbstractScopeMap.find(Scope);
215  if (I != AbstractScopeMap.end())
216  return &I->second;
217 
218  // FIXME: Should the following isa be DILexicalBlock?
219  LexicalScope *Parent = nullptr;
220  if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope))
221  Parent = getOrCreateAbstractScope(Block->getScope());
222 
223  I = AbstractScopeMap.emplace(std::piecewise_construct,
224  std::forward_as_tuple(Scope),
225  std::forward_as_tuple(Parent, Scope,
226  nullptr, true)).first;
227  if (isa<DISubprogram>(Scope))
228  AbstractScopesList.push_back(&I->second);
229  return &I->second;
230 }
231 
232 /// constructScopeNest
233 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
234  assert(Scope && "Unable to calculate scope dominance graph!");
236  WorkStack.push_back(Scope);
237  unsigned Counter = 0;
238  while (!WorkStack.empty()) {
239  LexicalScope *WS = WorkStack.back();
240  const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
241  bool visitedChildren = false;
242  for (auto &ChildScope : Children)
243  if (!ChildScope->getDFSOut()) {
244  WorkStack.push_back(ChildScope);
245  visitedChildren = true;
246  ChildScope->setDFSIn(++Counter);
247  break;
248  }
249  if (!visitedChildren) {
250  WorkStack.pop_back();
251  WS->setDFSOut(++Counter);
252  }
253  }
254 }
255 
256 /// assignInstructionRanges - Find ranges of instructions covered by each
257 /// lexical scope.
258 void LexicalScopes::assignInstructionRanges(
259  SmallVectorImpl<InsnRange> &MIRanges,
261  LexicalScope *PrevLexicalScope = nullptr;
262  for (const auto &R : MIRanges) {
263  LexicalScope *S = MI2ScopeMap.lookup(R.first);
264  assert(S && "Lost LexicalScope for a machine instruction!");
265  if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
266  PrevLexicalScope->closeInsnRange(S);
267  S->openInsnRange(R.first);
268  S->extendInsnRange(R.second);
269  PrevLexicalScope = S;
270  }
271 
272  if (PrevLexicalScope)
273  PrevLexicalScope->closeInsnRange();
274 }
275 
276 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
277 /// have machine instructions that belong to lexical scope identified by
278 /// DebugLoc.
281  assert(MF && "Method called on a uninitialized LexicalScopes object!");
282  MBBs.clear();
283 
284  LexicalScope *Scope = getOrCreateLexicalScope(DL);
285  if (!Scope)
286  return;
287 
288  if (Scope == CurrentFnLexicalScope) {
289  for (const auto &MBB : *MF)
290  MBBs.insert(&MBB);
291  return;
292  }
293 
294  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
295  for (auto &R : InsnRanges)
296  MBBs.insert(R.first->getParent());
297 }
298 
299 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
300 /// machine instruction's lexical scope in a given machine basic block.
302  assert(MF && "Unexpected uninitialized LexicalScopes object!");
303  LexicalScope *Scope = getOrCreateLexicalScope(DL);
304  if (!Scope)
305  return false;
306 
307  // Current function scope covers all basic blocks in the function.
308  if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
309  return true;
310 
311  bool Result = false;
312  for (auto &I : *MBB) {
313  if (const DILocation *IDL = I.getDebugLoc())
314  if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
315  if (Scope->dominates(IScope))
316  return true;
317  }
318  return Result;
319 }
320 
321 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
322 LLVM_DUMP_METHOD void LexicalScope::dump(unsigned Indent) const {
323  raw_ostream &err = dbgs();
324  err.indent(Indent);
325  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
326  const MDNode *N = Desc;
327  err.indent(Indent);
328  N->dump();
329  if (AbstractScope)
330  err << std::string(Indent, ' ') << "Abstract Scope\n";
331 
332  if (!Children.empty())
333  err << std::string(Indent + 2, ' ') << "Children ...\n";
334  for (unsigned i = 0, e = Children.size(); i != e; ++i)
335  if (Children[i] != this)
336  Children[i]->dump(Indent + 2);
337 }
338 #endif
void push_back(const T &Elt)
Definition: SmallVector.h:213
void openInsnRange(const MachineInstr *MI)
openInsnRange - This scope covers instruction range starting from MI.
Definition: LexicalScopes.h:73
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
void dump(unsigned Indent=0) const
dump - print lexical scope.
bool dominates(const DILocation *DL, MachineBasicBlock *MBB)
dominates - Return true if DebugLoc&#39;s lexical scope dominates at least one machine instruction&#39;s lexi...
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:67
Metadata node.
Definition: Metadata.h:862
LexicalScope - This class is used to track scope information.
Definition: LexicalScopes.h:45
A scope for locals.
LexicalScope * getOrCreateAbstractScope(const DILocalScope *Scope)
getOrCreateAbstractScope - Find or create an abstract lexical scope.
SmallVectorImpl< LexicalScope * > & getChildren()
Definition: LexicalScopes.h:66
void setDFSOut(unsigned O)
void reset()
releaseMemory - release memory.
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:1508
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:371
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.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
DISubprogram * getSubprogram() const
Get the subprogram for this scope.
Representation of each machine instruction.
Definition: MachineInstr.h:60
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
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 dump() const
User-friendly dump.
Definition: AsmWriter.cpp:4207
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:181
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:40