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 
122   // The scope that we were created with could have an extra file - which
123   // isn't what we care about in this case.
124   DIDescriptor D = DIDescriptor(Scope);
125   if (D.isLexicalBlockFile())
126     Scope = DILexicalBlockFile(Scope).getScope();
127 
128   if (IA)
129     return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA));
130   return LexicalScopeMap.lookup(Scope);
131 }
132 
133 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
134 /// not available then create new lexical scope.
135 LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
136   MDNode *Scope = NULL;
137   MDNode *InlinedAt = NULL;
138   DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
139 
140   if (InlinedAt) {
141     // Create an abstract scope for inlined function.
142     getOrCreateAbstractScope(Scope);
143     // Create an inlined scope for inlined function.
144     return getOrCreateInlinedScope(Scope, InlinedAt);
145   }
146 
147   return getOrCreateRegularScope(Scope);
148 }
149 
150 /// getOrCreateRegularScope - Find or create a regular lexical scope.
151 LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
152   DIDescriptor D = DIDescriptor(Scope);
153   if (D.isLexicalBlockFile())
154     Scope = DILexicalBlockFile(Scope).getScope();
155 
156   LexicalScope *WScope = LexicalScopeMap.lookup(Scope);
157   if (WScope)
158     return WScope;
159 
160   LexicalScope *Parent = NULL;
161   if (D.isLexicalBlock())
162     Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
163   WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false);
164   LexicalScopeMap.insert(std::make_pair(Scope, WScope));
165   if (!Parent && DIDescriptor(Scope).isSubprogram()
166       && DISubprogram(Scope).describes(MF->getFunction()))
167     CurrentFnLexicalScope = WScope;
168 
169   return WScope;
170 }
171 
172 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
173 LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope,
174                                                      MDNode *InlinedAt) {
175   LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt);
176   if (InlinedScope)
177     return InlinedScope;
178 
179   DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt);
180   InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc),
181                                   DIDescriptor(Scope), InlinedAt, false);
182   InlinedLexicalScopeMap[InlinedLoc] = InlinedScope;
183   LexicalScopeMap[InlinedAt] = InlinedScope;
184   return InlinedScope;
185 }
186 
187 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
188 LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
189   assert(N && "Invalid Scope encoding!");
190 
191   DIDescriptor Scope(N);
192   if (Scope.isLexicalBlockFile())
193     Scope = DILexicalBlockFile(Scope).getScope();
194   LexicalScope *AScope = AbstractScopeMap.lookup(N);
195   if (AScope)
196     return AScope;
197 
198   LexicalScope *Parent = NULL;
199   if (Scope.isLexicalBlock()) {
200     DILexicalBlock DB(N);
201     DIDescriptor ParentDesc = DB.getContext();
202     Parent = getOrCreateAbstractScope(ParentDesc);
203   }
204   AScope = new LexicalScope(Parent, DIDescriptor(N), NULL, true);
205   AbstractScopeMap[N] = AScope;
206   if (DIDescriptor(N).isSubprogram())
207     AbstractScopesList.push_back(AScope);
208   return AScope;
209 }
210 
211 /// constructScopeNest
212 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
213   assert (Scope && "Unable to calculate scop edominance graph!");
214   SmallVector<LexicalScope *, 4> WorkStack;
215   WorkStack.push_back(Scope);
216   unsigned Counter = 0;
217   while (!WorkStack.empty()) {
218     LexicalScope *WS = WorkStack.back();
219     const SmallVector<LexicalScope *, 4> &Children = WS->getChildren();
220     bool visitedChildren = false;
221     for (SmallVector<LexicalScope *, 4>::const_iterator SI = Children.begin(),
222            SE = Children.end(); SI != SE; ++SI) {
223       LexicalScope *ChildScope = *SI;
224       if (!ChildScope->getDFSOut()) {
225         WorkStack.push_back(ChildScope);
226         visitedChildren = true;
227         ChildScope->setDFSIn(++Counter);
228         break;
229       }
230     }
231     if (!visitedChildren) {
232       WorkStack.pop_back();
233       WS->setDFSOut(++Counter);
234     }
235   }
236 }
237 
238 /// assignInstructionRanges - Find ranges of instructions covered by each
239 /// lexical scope.
240 void LexicalScopes::
241 assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
242                     DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap)
243 {
244 
245   LexicalScope *PrevLexicalScope = NULL;
246   for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
247          RE = MIRanges.end(); RI != RE; ++RI) {
248     const InsnRange &R = *RI;
249     LexicalScope *S = MI2ScopeMap.lookup(R.first);
250     assert (S && "Lost LexicalScope for a machine instruction!");
251     if (PrevLexicalScope && !PrevLexicalScope->dominates(S))
252       PrevLexicalScope->closeInsnRange(S);
253     S->openInsnRange(R.first);
254     S->extendInsnRange(R.second);
255     PrevLexicalScope = S;
256   }
257 
258   if (PrevLexicalScope)
259     PrevLexicalScope->closeInsnRange();
260 }
261 
262 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
263 /// have machine instructions that belong to lexical scope identified by
264 /// DebugLoc.
265 void LexicalScopes::
266 getMachineBasicBlocks(DebugLoc DL,
267                       SmallPtrSet<const MachineBasicBlock*, 4> &MBBs) {
268   MBBs.clear();
269   LexicalScope *Scope = getOrCreateLexicalScope(DL);
270   if (!Scope)
271     return;
272 
273   if (Scope == CurrentFnLexicalScope) {
274     for (MachineFunction::const_iterator I = MF->begin(), E = MF->end();
275          I != E; ++I)
276       MBBs.insert(I);
277     return;
278   }
279 
280   SmallVector<InsnRange, 4> &InsnRanges = Scope->getRanges();
281   for (SmallVector<InsnRange, 4>::iterator I = InsnRanges.begin(),
282          E = InsnRanges.end(); I != E; ++I) {
283     InsnRange &R = *I;
284     MBBs.insert(R.first->getParent());
285   }
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(DebugLoc 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 (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
301        I != E; ++I) {
302     DebugLoc IDL = I->getDebugLoc();
303     if (IDL.isUnknown())
304       continue;
305     if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
306       if (Scope->dominates(IScope))
307         return true;
308   }
309   return Result;
310 }
311 
312 /// dump - Print data structures.
313 void LexicalScope::dump() const {
314 #ifndef NDEBUG
315   raw_ostream &err = dbgs();
316   err.indent(IndentLevel);
317   err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
318   const MDNode *N = Desc;
319   N->dump();
320   if (AbstractScope)
321     err << "Abstract Scope\n";
322 
323   IndentLevel += 2;
324   if (!Children.empty())
325     err << "Children ...\n";
326   for (unsigned i = 0, e = Children.size(); i != e; ++i)
327     if (Children[i] != this)
328       Children[i]->dump();
329 
330   IndentLevel -= 2;
331 #endif
332 }
333 
334