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