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