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