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