LexicalScopes.cpp revision 4c9d299d80f367a7fa1e97084613565a5956532f 
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
17#define DEBUG_TYPE "lexicalscopes"
18#include "llvm/CodeGen/LexicalScopes.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineInstr.h"
21#include "llvm/DebugInfo.h"
22#include "llvm/IR/Function.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/FormattedStream.h"
26using namespace llvm;
27
28LexicalScopes::~LexicalScopes() {
29  releaseMemory();
30}
31
32/// releaseMemory - release memory.
33void LexicalScopes::releaseMemory() {
34  MF = NULL;
35  CurrentFnLexicalScope = NULL;
36  DeleteContainerSeconds(LexicalScopeMap);
37  DeleteContainerSeconds(AbstractScopeMap);
38  InlinedLexicalScopeMap.clear();
39  AbstractScopesList.clear();
40}
41
42/// initialize - Scan machine function and constuct lexical scope nest.
43void LexicalScopes::initialize(const MachineFunction &Fn) {
44  releaseMemory();
45  MF = &Fn;
46  SmallVector<InsnRange, 4> MIRanges;
47  DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
48  extractLexicalScopes(MIRanges, MI2ScopeMap);
49  if (CurrentFnLexicalScope) {
50    constructScopeNest(CurrentFnLexicalScope);
51    assignInstructionRanges(MIRanges, MI2ScopeMap);
52  }
53}
54
55/// extractLexicalScopes - Extract instruction ranges for each lexical scopes
56/// for the given machine function.
57void LexicalScopes::
58extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
59                  DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
60
61  // Scan each instruction and create scopes. First build working set of scopes.
62  for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
63       I != E; ++I) {
64    const MachineInstr *RangeBeginMI = NULL;
65    const MachineInstr *PrevMI = NULL;
66    DebugLoc PrevDL;
67    for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
68         II != IE; ++II) {
69      const MachineInstr *MInsn = II;
70
71      // Check if instruction has valid location information.
72      const DebugLoc MIDL = MInsn->getDebugLoc();
73      if (MIDL.isUnknown()) {
74        PrevMI = MInsn;
75        continue;
76      }
77
78      // If scope has not changed then skip this instruction.
79      if (MIDL == PrevDL) {
80        PrevMI = MInsn;
81        continue;
82      }
83
84      // Ignore DBG_VALUE. It does not contribute to any instruction in output.
85      if (MInsn->isDebugValue())
86        continue;
87
88      if (RangeBeginMI) {
89        // If we have already seen a beginning of an instruction range and
90        // current instruction scope does not match scope of first instruction
91        // in this range then create a new instruction range.
92        InsnRange R(RangeBeginMI, PrevMI);
93        MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
94        MIRanges.push_back(R);
95      }
96
97      // This is a beginning of a new instruction range.
98      RangeBeginMI = MInsn;
99
100      // Reset previous markers.
101      PrevMI = MInsn;
102      PrevDL = MIDL;
103    }
104
105    // Create last instruction range.
106    if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) {
107      InsnRange R(RangeBeginMI, PrevMI);
108      MIRanges.push_back(R);
109      MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
110    }
111  }
112}
113
114/// findLexicalScope - Find lexical scope, either regular or inlined, for the
115/// given DebugLoc. Return NULL if not found.
116LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
117  MDNode *Scope = NULL;
118  MDNode *IA = NULL;
119  DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
120  if (!Scope) return NULL;
121
122  // The scope that we were created with could have an extra file - which
123  // isn't what we care about in this case.
124  DIDescriptor D = DIDescriptor(Scope);
125  if (D.isLexicalBlockFile())
126    Scope = DILexicalBlockFile(Scope).getScope();
127
128  if (IA)
129    return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA));
130  return LexicalScopeMap.lookup(Scope);
131}
132
133/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
134/// not available then create new lexical scope.
135LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
136  MDNode *Scope = NULL;
137  MDNode *InlinedAt = NULL;
138  DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
139
140  if (InlinedAt) {
141    // Create an abstract scope for inlined function.
142    getOrCreateAbstractScope(Scope);
143    // Create an inlined scope for inlined function.
144    return getOrCreateInlinedScope(Scope, InlinedAt);
145  }
146
147  return getOrCreateRegularScope(Scope);
148}
149
150/// getOrCreateRegularScope - Find or create a regular lexical scope.
151LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
152  DIDescriptor D = DIDescriptor(Scope);
153  if (D.isLexicalBlockFile()) {
154    Scope = DILexicalBlockFile(Scope).getScope();
155    D = DIDescriptor(Scope);
156  }
157
158  LexicalScope *WScope = LexicalScopeMap.lookup(Scope);
159  if (WScope)
160    return WScope;
161
162  LexicalScope *Parent = NULL;
163  if (D.isLexicalBlock())
164    Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
165  WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false);
166  LexicalScopeMap.insert(std::make_pair(Scope, WScope));
167  if (!Parent && DIDescriptor(Scope).isSubprogram()
168      && DISubprogram(Scope).describes(MF->getFunction()))
169    CurrentFnLexicalScope = WScope;
170
171  return WScope;
172}
173
174/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
175LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope,
176                                                     MDNode *InlinedAt) {
177  LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt);
178  if (InlinedScope)
179    return InlinedScope;
180
181  DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt);
182  InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc),
183                                  DIDescriptor(Scope), InlinedAt, false);
184  InlinedLexicalScopeMap[InlinedLoc] = InlinedScope;
185  LexicalScopeMap[InlinedAt] = InlinedScope;
186  return InlinedScope;
187}
188
189/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
190LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
191  assert(N && "Invalid Scope encoding!");
192
193  DIDescriptor Scope(N);
194  if (Scope.isLexicalBlockFile())
195    Scope = DILexicalBlockFile(Scope).getScope();
196  LexicalScope *AScope = AbstractScopeMap.lookup(N);
197  if (AScope)
198    return AScope;
199
200  LexicalScope *Parent = NULL;
201  if (Scope.isLexicalBlock()) {
202    DILexicalBlock DB(N);
203    DIDescriptor ParentDesc = DB.getContext();
204    Parent = getOrCreateAbstractScope(ParentDesc);
205  }
206  AScope = new LexicalScope(Parent, DIDescriptor(N), NULL, true);
207  AbstractScopeMap[N] = AScope;
208  if (DIDescriptor(N).isSubprogram())
209    AbstractScopesList.push_back(AScope);
210  return AScope;
211}
212
213/// constructScopeNest
214void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
215  assert (Scope && "Unable to calculate scope dominance graph!");
216  SmallVector<LexicalScope *, 4> WorkStack;
217  WorkStack.push_back(Scope);
218  unsigned Counter = 0;
219  while (!WorkStack.empty()) {
220    LexicalScope *WS = WorkStack.back();
221    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
222    bool visitedChildren = false;
223    for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
224           SE = Children.end(); SI != SE; ++SI) {
225      LexicalScope *ChildScope = *SI;
226      if (!ChildScope->getDFSOut()) {
227        WorkStack.push_back(ChildScope);
228        visitedChildren = true;
229        ChildScope->setDFSIn(++Counter);
230        break;
231      }
232    }
233    if (!visitedChildren) {
234      WorkStack.pop_back();
235      WS->setDFSOut(++Counter);
236    }
237  }
238}
239
240/// assignInstructionRanges - Find ranges of instructions covered by each
241/// lexical scope.
242void LexicalScopes::
243assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
244                    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap)
245{
246
247  LexicalScope *PrevLexicalScope = NULL;
248  for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
249         RE = MIRanges.end(); RI != RE; ++RI) {
250    const InsnRange &R = *RI;
251    LexicalScope *S = MI2ScopeMap.lookup(R.first);
252    assert (S && "Lost LexicalScope for a machine instruction!");
253    if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
254      PrevLexicalScope->closeInsnRange(S);
255    S->openInsnRange(R.first);
256    S->extendInsnRange(R.second);
257    PrevLexicalScope = S;
258  }
259
260  if (PrevLexicalScope)
261    PrevLexicalScope->closeInsnRange();
262}
263
264/// getMachineBasicBlocks - Populate given set using machine basic blocks which
265/// have machine instructions that belong to lexical scope identified by
266/// DebugLoc.
267void LexicalScopes::
268getMachineBasicBlocks(DebugLoc DL,
269                      SmallPtrSet<const MachineBasicBlock*, 4> &MBBs) {
270  MBBs.clear();
271  LexicalScope *Scope = getOrCreateLexicalScope(DL);
272  if (!Scope)
273    return;
274
275  if (Scope == CurrentFnLexicalScope) {
276    for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
277         I != E; ++I)
278      MBBs.insert(I);
279    return;
280  }
281
282  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
283  for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
284         E = InsnRanges.end(); I != E; ++I) {
285    InsnRange &R = *I;
286    MBBs.insert(R.first->getParent());
287  }
288}
289
290/// dominates - Return true if DebugLoc's lexical scope dominates at least one
291/// machine instruction's lexical scope in a given machine basic block.
292bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
293  LexicalScope *Scope = getOrCreateLexicalScope(DL);
294  if (!Scope)
295    return false;
296
297  // Current function scope covers all basic blocks in the function.
298  if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
299    return true;
300
301  bool Result = false;
302  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
303       I != E; ++I) {
304    DebugLoc IDL = I->getDebugLoc();
305    if (IDL.isUnknown())
306      continue;
307    if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
308      if (Scope->dominates(IScope))
309        return true;
310  }
311  return Result;
312}
313
314void LexicalScope::anchor() { }
315
316/// dump - Print data structures.
317void LexicalScope::dump(unsigned Indent) const {
318#ifndef NDEBUG
319  raw_ostream &err = dbgs();
320  err.indent(Indent);
321  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
322  const MDNode *N = Desc;
323  err.indent(Indent);
324  N->dump();
325  if (AbstractScope)
326    err << std::string(Indent, ' ') << "Abstract Scope\n";
327
328  if (!Children.empty())
329    err << std::string(Indent + 2, ' ') << "Children ...\n";
330  for (unsigned i = 0, e = Children.size(); i != e; ++i)
331    if (Children[i] != this)
332      Children[i]->dump(Indent + 2);
333#endif
334}
335
336