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