LexicalScopes.cpp revision 355940 
1//===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements LexicalScopes analysis.
10//
11// This pass collects lexical scope information and maps machine instructions
12// to respective lexical scopes.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/CodeGen/LexicalScopes.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/CodeGen/MachineBasicBlock.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/Config/llvm-config.h"
23#include "llvm/IR/DebugInfoMetadata.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"
28#include "llvm/Support/raw_ostream.h"
29#include <cassert>
30#include <string>
31#include <tuple>
32#include <utility>
33
34using namespace llvm;
35
36#define DEBUG_TYPE "lexicalscopes"
37
38/// reset - Reset the instance so that it's prepared for another function.
39void LexicalScopes::reset() {
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.
49void LexicalScopes::initialize(const MachineFunction &Fn) {
50  reset();
51  // Don't attempt any lexical scope creation for a NoDebug compile unit.
52  if (Fn.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
53      DICompileUnit::NoDebug)
54    return;
55  MF = &Fn;
56  SmallVector<InsnRange, 4> MIRanges;
57  DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
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.
67void LexicalScopes::extractLexicalScopes(
68    SmallVectorImpl<InsnRange> &MIRanges,
69    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
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.
122LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) {
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.
140LexicalScope *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() ==
145        DICompileUnit::NoDebug)
146      return getOrCreateLexicalScope(IA);
147    // Create an abstract scope for inlined function.
148    getOrCreateAbstractScope(Scope);
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.
157LexicalScope *
158LexicalScopes::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.
185LexicalScope *
186LexicalScopes::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.
209LexicalScope *
210LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) {
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
232void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
233  assert(Scope && "Unable to calculate scope dominance graph!");
234  SmallVector<LexicalScope *, 4> WorkStack;
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.
257void LexicalScopes::assignInstructionRanges(
258    SmallVectorImpl<InsnRange> &MIRanges,
259    DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
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.
278void LexicalScopes::getMachineBasicBlocks(
279    const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) {
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.
300bool LexicalScopes::dominates(const DILocation *DL, MachineBasicBlock *MBB) {
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)
321LLVM_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
338