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 MDLocation *PrevDL = nullptr;
63    for (const auto &MInsn : MBB) {
64      // Check if instruction has valid location information.
65      const MDLocation *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 MDLocation *DL) {
110  MDLocalScope *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  if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
117    Scope = File->getScope();
118
119  if (auto *IA = DL->getInlinedAt()) {
120    auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA));
121    return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
122  }
123  return findLexicalScope(Scope);
124}
125
126/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
127/// not available then create new lexical scope.
128LexicalScope *LexicalScopes::getOrCreateLexicalScope(const MDLocalScope *Scope,
129                                                     const MDLocation *IA) {
130  if (IA) {
131    // Create an abstract scope for inlined function.
132    getOrCreateAbstractScope(Scope);
133    // Create an inlined scope for inlined function.
134    return getOrCreateInlinedScope(Scope, IA);
135  }
136
137  return getOrCreateRegularScope(Scope);
138}
139
140/// getOrCreateRegularScope - Find or create a regular lexical scope.
141LexicalScope *
142LexicalScopes::getOrCreateRegularScope(const MDLocalScope *Scope) {
143  if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
144    Scope = File->getScope();
145
146  auto I = LexicalScopeMap.find(Scope);
147  if (I != LexicalScopeMap.end())
148    return &I->second;
149
150  // FIXME: Should the following dyn_cast be MDLexicalBlock?
151  LexicalScope *Parent = nullptr;
152  if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
153    Parent = getOrCreateLexicalScope(Block->getScope());
154  I = LexicalScopeMap.emplace(std::piecewise_construct,
155                              std::forward_as_tuple(Scope),
156                              std::forward_as_tuple(Parent, Scope, nullptr,
157                                                    false)).first;
158
159  if (!Parent) {
160    assert(cast<MDSubprogram>(Scope)->describes(MF->getFunction()));
161    assert(!CurrentFnLexicalScope);
162    CurrentFnLexicalScope = &I->second;
163  }
164
165  return &I->second;
166}
167
168/// getOrCreateInlinedScope - Find or create an inlined lexical scope.
169LexicalScope *
170LexicalScopes::getOrCreateInlinedScope(const MDLocalScope *Scope,
171                                       const MDLocation *InlinedAt) {
172  std::pair<const MDLocalScope *, const MDLocation *> P(Scope, InlinedAt);
173  auto I = InlinedLexicalScopeMap.find(P);
174  if (I != InlinedLexicalScopeMap.end())
175    return &I->second;
176
177  LexicalScope *Parent;
178  if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
179    Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt);
180  else
181    Parent = getOrCreateLexicalScope(InlinedAt);
182
183  I = InlinedLexicalScopeMap.emplace(std::piecewise_construct,
184                                     std::forward_as_tuple(P),
185                                     std::forward_as_tuple(Parent, Scope,
186                                                           InlinedAt, false))
187          .first;
188  return &I->second;
189}
190
191/// getOrCreateAbstractScope - Find or create an abstract lexical scope.
192LexicalScope *
193LexicalScopes::getOrCreateAbstractScope(const MDLocalScope *Scope) {
194  assert(Scope && "Invalid Scope encoding!");
195
196  if (auto *File = dyn_cast<MDLexicalBlockFile>(Scope))
197    Scope = File->getScope();
198  auto I = AbstractScopeMap.find(Scope);
199  if (I != AbstractScopeMap.end())
200    return &I->second;
201
202  // FIXME: Should the following isa be MDLexicalBlock?
203  LexicalScope *Parent = nullptr;
204  if (auto *Block = dyn_cast<MDLexicalBlockBase>(Scope))
205    Parent = getOrCreateAbstractScope(Block->getScope());
206
207  I = AbstractScopeMap.emplace(std::piecewise_construct,
208                               std::forward_as_tuple(Scope),
209                               std::forward_as_tuple(Parent, Scope,
210                                                     nullptr, true)).first;
211  if (isa<MDSubprogram>(Scope))
212    AbstractScopesList.push_back(&I->second);
213  return &I->second;
214}
215
216/// constructScopeNest
217void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
218  assert(Scope && "Unable to calculate scope dominance graph!");
219  SmallVector<LexicalScope *, 4> WorkStack;
220  WorkStack.push_back(Scope);
221  unsigned Counter = 0;
222  while (!WorkStack.empty()) {
223    LexicalScope *WS = WorkStack.back();
224    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
225    bool visitedChildren = false;
226    for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
227                                                         SE = Children.end();
228         SI != SE; ++SI) {
229      LexicalScope *ChildScope = *SI;
230      if (!ChildScope->getDFSOut()) {
231        WorkStack.push_back(ChildScope);
232        visitedChildren = true;
233        ChildScope->setDFSIn(++Counter);
234        break;
235      }
236    }
237    if (!visitedChildren) {
238      WorkStack.pop_back();
239      WS->setDFSOut(++Counter);
240    }
241  }
242}
243
244/// assignInstructionRanges - Find ranges of instructions covered by each
245/// lexical scope.
246void LexicalScopes::assignInstructionRanges(
247    SmallVectorImpl<InsnRange> &MIRanges,
248    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
249
250  LexicalScope *PrevLexicalScope = nullptr;
251  for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
252                                                  RE = MIRanges.end();
253       RI != RE; ++RI) {
254    const InsnRange &R = *RI;
255    LexicalScope *S = MI2ScopeMap.lookup(R.first);
256    assert(S && "Lost LexicalScope for a machine instruction!");
257    if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
258      PrevLexicalScope->closeInsnRange(S);
259    S->openInsnRange(R.first);
260    S->extendInsnRange(R.second);
261    PrevLexicalScope = S;
262  }
263
264  if (PrevLexicalScope)
265    PrevLexicalScope->closeInsnRange();
266}
267
268/// getMachineBasicBlocks - Populate given set using machine basic blocks which
269/// have machine instructions that belong to lexical scope identified by
270/// DebugLoc.
271void LexicalScopes::getMachineBasicBlocks(
272    const MDLocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
273  MBBs.clear();
274  LexicalScope *Scope = getOrCreateLexicalScope(DL);
275  if (!Scope)
276    return;
277
278  if (Scope == CurrentFnLexicalScope) {
279    for (const auto &MBB : *MF)
280      MBBs.insert(&MBB);
281    return;
282  }
283
284  SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
285  for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
286                                            E = InsnRanges.end();
287       I != E; ++I) {
288    InsnRange &R = *I;
289    MBBs.insert(R.first->getParent());
290  }
291}
292
293/// dominates - Return true if DebugLoc's lexical scope dominates at least one
294/// machine instruction's lexical scope in a given machine basic block.
295bool LexicalScopes::dominates(const MDLocation *DL, MachineBasicBlock *MBB) {
296  LexicalScope *Scope = getOrCreateLexicalScope(DL);
297  if (!Scope)
298    return false;
299
300  // Current function scope covers all basic blocks in the function.
301  if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
302    return true;
303
304  bool Result = false;
305  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
306       ++I) {
307    if (const MDLocation *IDL = I->getDebugLoc())
308      if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
309        if (Scope->dominates(IScope))
310          return true;
311  }
312  return Result;
313}
314
315/// dump - Print data structures.
316void LexicalScope::dump(unsigned Indent) const {
317#ifndef NDEBUG
318  raw_ostream &err = dbgs();
319  err.indent(Indent);
320  err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
321  const MDNode *N = Desc;
322  err.indent(Indent);
323  N->dump();
324  if (AbstractScope)
325    err << std::string(Indent, ' ') << "Abstract Scope\n";
326
327  if (!Children.empty())
328    err << std::string(Indent + 2, ' ') << "Children ...\n";
329  for (unsigned i = 0, e = Children.size(); i != e; ++i)
330    if (Children[i] != this)
331      Children[i]->dump(Indent + 2);
332#endif
333}
334