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