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 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "lexicalscopes"
38 
39 /// reset - Reset the instance so that it's prepared for another function.
40 void 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.
51 void 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.
69 void 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.
124 LexicalScope *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.
142 LexicalScope *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.
159 LexicalScope *
160 LexicalScopes::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.
187 LexicalScope *
188 LexicalScopes::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.
211 LexicalScope *
212 LexicalScopes::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.
236 void 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.
259 void 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.
280 void 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 
306 bool 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)
331 LLVM_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