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