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 #define DEBUG_TYPE "lexicalscopes"
18 #include "llvm/CodeGen/LexicalScopes.h"
19 #include "llvm/Function.h"
20 #include "llvm/Analysis/DebugInfo.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include "llvm/Support/FormattedStream.h"
26 using namespace llvm;
27 
28 LexicalScopes::~LexicalScopes() {
29   releaseMemory();
30 }
31 
32 /// releaseMemory - release memory.
33 void LexicalScopes::releaseMemory() {
34   MF = NULL;
35   CurrentFnLexicalScope = NULL;
36   DeleteContainerSeconds(LexicalScopeMap);
37   DeleteContainerSeconds(AbstractScopeMap);
38   InlinedLexicalScopeMap.clear();
39   AbstractScopesList.clear();
40 }
41 
42 /// initialize - Scan machine function and constuct lexical scope nest.
43 void LexicalScopes::initialize(const MachineFunction &Fn) {
44   releaseMemory();
45   MF = &Fn;
46   SmallVector<InsnRange, 4> MIRanges;
47   DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
48   extractLexicalScopes(MIRanges, MI2ScopeMap);
49   if (CurrentFnLexicalScope) {
50     constructScopeNest(CurrentFnLexicalScope);
51     assignInstructionRanges(MIRanges, MI2ScopeMap);
52   }
53 }
54 
55 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
56 /// for the given machine function.
57 void LexicalScopes::
58 extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
59                   DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
60 
61   // Scan each instruction and create scopes. First build working set of scopes.
62   for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
63        I != E; ++I) {
64     const MachineInstr *RangeBeginMI = NULL;
65     const MachineInstr *PrevMI = NULL;
66     DebugLoc PrevDL;
67     for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end();
68          II != IE; ++II) {
69       const MachineInstr *MInsn = II;
70 
71       // Check if instruction has valid location information.
72       const DebugLoc MIDL = MInsn->getDebugLoc();
73       if (MIDL.isUnknown()) {
74         PrevMI = MInsn;
75         continue;
76       }
77 
78       // If scope has not changed then skip this instruction.
79       if (MIDL == PrevDL) {
80         PrevMI = MInsn;
81         continue;
82       }
83 
84       // Ignore DBG_VALUE. It does not contribute to any instruction in output.
85       if (MInsn->isDebugValue())
86         continue;
87 
88       if (RangeBeginMI) {
89         // If we have already seen a beginning of an instruction range and
90         // current instruction scope does not match scope of first instruction
91         // in this range then create a new instruction range.
92         InsnRange R(RangeBeginMI, PrevMI);
93         MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
94         MIRanges.push_back(R);
95       }
96 
97       // This is a beginning of a new instruction range.
98       RangeBeginMI = MInsn;
99 
100       // Reset previous markers.
101       PrevMI = MInsn;
102       PrevDL = MIDL;
103     }
104 
105     // Create last instruction range.
106     if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) {
107       InsnRange R(RangeBeginMI, PrevMI);
108       MIRanges.push_back(R);
109       MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
110     }
111   }
112 }
113 
114 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
115 /// given DebugLoc. Return NULL if not found.
116 LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
117   MDNode *Scope = NULL;
118   MDNode *IA = NULL;
119   DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
120   if (!Scope) return NULL;
121   if (IA)
122     return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA));
123   return LexicalScopeMap.lookup(DL.getScope(Scope->getContext()));
124 }
125 
126 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
127 /// not available then create new lexical scope.
128 LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
129   MDNode *Scope = NULL;
130   MDNode *InlinedAt = NULL;
131   DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
132   if (InlinedAt) {
133     // Create an abstract scope for inlined function.
134     getOrCreateAbstractScope(Scope);
135     // Create an inlined scope for inlined function.
136     return getOrCreateInlinedScope(Scope, InlinedAt);
137   }
138 
139   return getOrCreateRegularScope(Scope);
140 }
141 
142 /// getOrCreateRegularScope - Find or create a regular lexical scope.
143 LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
144   LexicalScope *WScope = LexicalScopeMap.lookup(Scope);
145   if (WScope)
146     return WScope;
147 
148   LexicalScope *Parent = NULL;
149   if (DIDescriptor(Scope).isLexicalBlock())
150     Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
151   WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false);
152   LexicalScopeMap.insert(std::make_pair(Scope, WScope));
153   if (!Parent && DIDescriptor(Scope).isSubprogram()
154       && DISubprogram(Scope).describes(MF->getFunction()))
155     CurrentFnLexicalScope = WScope;
156 
157   return WScope;
158 }
159 
160 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
161 LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope,
162                                                      MDNode *InlinedAt) {
163   LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt);
164   if (InlinedScope)
165     return InlinedScope;
166 
167   DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt);
168   InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc),
169                                   DIDescriptor(Scope), InlinedAt, false);
170   InlinedLexicalScopeMap[InlinedLoc] = InlinedScope;
171   LexicalScopeMap[InlinedAt] = InlinedScope;
172   return InlinedScope;
173 }
174 
175 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
176 LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
177   assert(N && "Invalid Scope encoding!");
178 
179   LexicalScope *AScope = AbstractScopeMap.lookup(N);
180   if (AScope)
181     return AScope;
182 
183   LexicalScope *Parent = NULL;
184   DIDescriptor Scope(N);
185   if (Scope.isLexicalBlock()) {
186     DILexicalBlock DB(N);
187     DIDescriptor ParentDesc = DB.getContext();
188     Parent = getOrCreateAbstractScope(ParentDesc);
189   }
190   AScope = new LexicalScope(Parent, DIDescriptor(N), NULL, true);
191   AbstractScopeMap[N] = AScope;
192   if (DIDescriptor(N).isSubprogram())
193     AbstractScopesList.push_back(AScope);
194   return AScope;
195 }
196 
197 /// constructScopeNest
198 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
199   assert (Scope && "Unable to calculate scop edominance graph!");
200   SmallVector<LexicalScope *, 4> WorkStack;
201   WorkStack.push_back(Scope);
202   unsigned Counter = 0;
203   while (!WorkStack.empty()) {
204     LexicalScope *WS = WorkStack.back();
205     const SmallVector<LexicalScope *, 4> &Children = WS->getChildren();
206     bool visitedChildren = false;
207     for (SmallVector<LexicalScope *, 4>::const_iterator SI = Children.begin(),
208            SE = Children.end(); SI != SE; ++SI) {
209       LexicalScope *ChildScope = *SI;
210       if (!ChildScope->getDFSOut()) {
211         WorkStack.push_back(ChildScope);
212         visitedChildren = true;
213         ChildScope->setDFSIn(++Counter);
214         break;
215       }
216     }
217     if (!visitedChildren) {
218       WorkStack.pop_back();
219       WS->setDFSOut(++Counter);
220     }
221   }
222 }
223 
224 /// assignInstructionRanges - Find ranges of instructions covered by each
225 /// lexical scope.
226 void LexicalScopes::
227 assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
228                     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap)
229 {
230 
231   LexicalScope *PrevLexicalScope = NULL;
232   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
233          RE = MIRanges.end(); RI != RE; ++RI) {
234     const InsnRange &R = *RI;
235     LexicalScope *S = MI2ScopeMap.lookup(R.first);
236     assert (S && "Lost LexicalScope for a machine instruction!");
237     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
238       PrevLexicalScope->closeInsnRange(S);
239     S->openInsnRange(R.first);
240     S->extendInsnRange(R.second);
241     PrevLexicalScope = S;
242   }
243 
244   if (PrevLexicalScope)
245     PrevLexicalScope->closeInsnRange();
246 }
247 
248 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
249 /// have machine instructions that belong to lexical scope identified by
250 /// DebugLoc.
251 void LexicalScopes::
252 getMachineBasicBlocks(DebugLoc DL,
253                       SmallPtrSet<const MachineBasicBlock*, 4> &MBBs) {
254   MBBs.clear();
255   LexicalScope *Scope = getOrCreateLexicalScope(DL);
256   if (!Scope)
257     return;
258 
259   if (Scope == CurrentFnLexicalScope) {
260     for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
261          I != E; ++I)
262       MBBs.insert(I);
263     return;
264   }
265 
266   SmallVector<InsnRange, 4> &InsnRanges = Scope->getRanges();
267   for (SmallVector<InsnRange, 4>::iterator I = InsnRanges.begin(),
268          E = InsnRanges.end(); I != E; ++I) {
269     InsnRange &R = *I;
270     MBBs.insert(R.first->getParent());
271   }
272 }
273 
274 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
275 /// machine instruction's lexical scope in a given machine basic block.
276 bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
277   LexicalScope *Scope = getOrCreateLexicalScope(DL);
278   if (!Scope)
279     return false;
280 
281   // Current function scope covers all basic blocks in the function.
282   if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
283     return true;
284 
285   bool Result = false;
286   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
287        I != E; ++I) {
288     DebugLoc IDL = I->getDebugLoc();
289     if (IDL.isUnknown())
290       continue;
291     if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
292       if (Scope->dominates(IScope))
293         return true;
294   }
295   return Result;
296 }
297 
298 /// dump - Print data structures.
299 void LexicalScope::dump() const {
300 #ifndef NDEBUG
301   raw_ostream &err = dbgs();
302   err.indent(IndentLevel);
303   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
304   const MDNode *N = Desc;
305   N->dump();
306   if (AbstractScope)
307     err << "Abstract Scope\n";
308 
309   IndentLevel += 2;
310   if (!Children.empty())
311     err << "Children ...\n";
312   for (unsigned i = 0, e = Children.size(); i != e; ++i)
313     if (Children[i] != this)
314       Children[i]->dump();
315 
316   IndentLevel -= 2;
317 #endif
318 }
319 
320