1 //===- LexicalScopes.cpp - Collecting lexical scope info ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements LexicalScopes analysis.
12 // This pass collects lexical scope information and maps machine instructions
13 // to respective lexical scopes.
15 //===----------------------------------------------------------------------===//
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"
27 #define DEBUG_TYPE "lexicalscopes"
29 /// ~LexicalScopes - final cleanup after ourselves.
30 LexicalScopes::~LexicalScopes() { reset(); }
32 /// reset - Reset the instance so that it's prepared for another function.
33 void LexicalScopes::reset() {
35 CurrentFnLexicalScope = nullptr;
36 InlinedLexicalScopeMap.clear();
37 AbstractScopesList.clear();
40 /// initialize - Scan machine function and constuct lexical scope nest.
41 void LexicalScopes::initialize(const MachineFunction &Fn) {
44 SmallVector<InsnRange, 4> MIRanges;
45 DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap;
46 extractLexicalScopes(MIRanges, MI2ScopeMap);
47 if (CurrentFnLexicalScope) {
48 constructScopeNest(CurrentFnLexicalScope);
49 assignInstructionRanges(MIRanges, MI2ScopeMap);
53 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
54 /// for the given machine function.
55 void LexicalScopes::extractLexicalScopes(
56 SmallVectorImpl<InsnRange> &MIRanges,
57 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
59 // Scan each instruction and create scopes. First build working set of scopes.
60 for (const auto &MBB : *MF) {
61 const MachineInstr *RangeBeginMI = nullptr;
62 const MachineInstr *PrevMI = nullptr;
64 for (const auto &MInsn : MBB) {
65 // Check if instruction has valid location information.
66 const DebugLoc MIDL = MInsn.getDebugLoc();
67 if (MIDL.isUnknown()) {
72 // If scope has not changed then skip this instruction.
78 // Ignore DBG_VALUE. It does not contribute to any instruction in output.
79 if (MInsn.isDebugValue())
83 // If we have already seen a beginning of an instruction range and
84 // current instruction scope does not match scope of first instruction
85 // in this range then create a new instruction range.
86 InsnRange R(RangeBeginMI, PrevMI);
87 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
88 MIRanges.push_back(R);
91 // This is a beginning of a new instruction range.
92 RangeBeginMI = &MInsn;
94 // Reset previous markers.
99 // Create last instruction range.
100 if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) {
101 InsnRange R(RangeBeginMI, PrevMI);
102 MIRanges.push_back(R);
103 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL);
108 /// findLexicalScope - Find lexical scope, either regular or inlined, for the
109 /// given DebugLoc. Return NULL if not found.
110 LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) {
111 MDNode *Scope = nullptr;
112 MDNode *IA = nullptr;
113 DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext());
117 // The scope that we were created with could have an extra file - which
118 // isn't what we care about in this case.
119 DIDescriptor D = DIDescriptor(Scope);
120 if (D.isLexicalBlockFile())
121 Scope = DILexicalBlockFile(Scope).getScope();
124 return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA));
125 auto I = LexicalScopeMap.find(Scope);
126 return I != LexicalScopeMap.end() ? I->second.get() : nullptr;
129 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If
130 /// not available then create new lexical scope.
131 LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) {
132 MDNode *Scope = nullptr;
133 MDNode *InlinedAt = nullptr;
134 DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext());
137 // Create an abstract scope for inlined function.
138 getOrCreateAbstractScope(Scope);
139 // Create an inlined scope for inlined function.
140 return getOrCreateInlinedScope(Scope, InlinedAt);
143 return getOrCreateRegularScope(Scope);
146 /// getOrCreateRegularScope - Find or create a regular lexical scope.
147 LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) {
148 DIDescriptor D = DIDescriptor(Scope);
149 if (D.isLexicalBlockFile()) {
150 Scope = DILexicalBlockFile(Scope).getScope();
151 D = DIDescriptor(Scope);
154 auto IterBool = LexicalScopeMap.insert(
155 std::make_pair(Scope, std::unique_ptr<LexicalScope>()));
156 auto &MapValue = *IterBool.first;
157 if (!IterBool.second)
158 return MapValue.second.get();
160 LexicalScope *Parent = nullptr;
161 if (D.isLexicalBlock())
162 Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope));
164 make_unique<LexicalScope>(Parent, DIDescriptor(Scope), nullptr, false);
165 if (!Parent && DIDescriptor(Scope).isSubprogram() &&
166 DISubprogram(Scope).describes(MF->getFunction()))
167 CurrentFnLexicalScope = MapValue.second.get();
169 return MapValue.second.get();
172 /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
173 LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope,
175 auto IterBool = LexicalScopeMap.insert(
176 std::make_pair(InlinedAt, std::unique_ptr<LexicalScope>()));
177 auto &MapValue = *IterBool.first;
178 if (!IterBool.second)
179 return MapValue.second.get();
181 DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt);
183 make_unique<LexicalScope>(getOrCreateLexicalScope(InlinedLoc),
184 DIDescriptor(Scope), InlinedAt, false);
185 InlinedLexicalScopeMap[InlinedLoc] = MapValue.second.get();
186 return MapValue.second.get();
189 /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
190 LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) {
191 assert(N && "Invalid Scope encoding!");
193 DIDescriptor Scope(N);
194 if (Scope.isLexicalBlockFile())
195 Scope = DILexicalBlockFile(Scope).getScope();
196 auto IterBool = AbstractScopeMap.insert(
197 std::make_pair(N, std::unique_ptr<LexicalScope>()));
198 auto &MapEntry = *IterBool.first;
199 if (!IterBool.second)
200 return MapEntry.second.get();
202 LexicalScope *Parent = nullptr;
203 if (Scope.isLexicalBlock()) {
204 DILexicalBlock DB(N);
205 DIDescriptor ParentDesc = DB.getContext();
206 Parent = getOrCreateAbstractScope(ParentDesc);
209 make_unique<LexicalScope>(Parent, DIDescriptor(N), nullptr, true);
210 if (DIDescriptor(N).isSubprogram())
211 AbstractScopesList.push_back(MapEntry.second.get());
212 return MapEntry.second.get();
215 /// constructScopeNest
216 void LexicalScopes::constructScopeNest(LexicalScope *Scope) {
217 assert(Scope && "Unable to calculate scope dominance graph!");
218 SmallVector<LexicalScope *, 4> WorkStack;
219 WorkStack.push_back(Scope);
220 unsigned Counter = 0;
221 while (!WorkStack.empty()) {
222 LexicalScope *WS = WorkStack.back();
223 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
224 bool visitedChildren = false;
225 for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(),
228 LexicalScope *ChildScope = *SI;
229 if (!ChildScope->getDFSOut()) {
230 WorkStack.push_back(ChildScope);
231 visitedChildren = true;
232 ChildScope->setDFSIn(++Counter);
236 if (!visitedChildren) {
237 WorkStack.pop_back();
238 WS->setDFSOut(++Counter);
243 /// assignInstructionRanges - Find ranges of instructions covered by each
245 void LexicalScopes::assignInstructionRanges(
246 SmallVectorImpl<InsnRange> &MIRanges,
247 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) {
249 LexicalScope *PrevLexicalScope = nullptr;
250 for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(),
253 const InsnRange &R = *RI;
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;
263 if (PrevLexicalScope)
264 PrevLexicalScope->closeInsnRange();
267 /// getMachineBasicBlocks - Populate given set using machine basic blocks which
268 /// have machine instructions that belong to lexical scope identified by
270 void LexicalScopes::getMachineBasicBlocks(
271 DebugLoc DL, SmallPtrSet<const MachineBasicBlock *, 4> &MBBs) {
273 LexicalScope *Scope = getOrCreateLexicalScope(DL);
277 if (Scope == CurrentFnLexicalScope) {
278 for (const auto &MBB : *MF)
283 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges();
284 for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(),
285 E = InsnRanges.end();
288 MBBs.insert(R.first->getParent());
292 /// dominates - Return true if DebugLoc's lexical scope dominates at least one
293 /// machine instruction's lexical scope in a given machine basic block.
294 bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) {
295 LexicalScope *Scope = getOrCreateLexicalScope(DL);
299 // Current function scope covers all basic blocks in the function.
300 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF)
304 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E;
306 DebugLoc IDL = I->getDebugLoc();
309 if (LexicalScope *IScope = getOrCreateLexicalScope(IDL))
310 if (Scope->dominates(IScope))
316 /// dump - Print data structures.
317 void LexicalScope::dump(unsigned Indent) const {
319 raw_ostream &err = dbgs();
321 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n";
322 const MDNode *N = Desc;
326 err << std::string(Indent, ' ') << "Abstract Scope\n";
328 if (!Children.empty())
329 err << std::string(Indent + 2, ' ') << "Children ...\n";
330 for (unsigned i = 0, e = Children.size(); i != e; ++i)
331 if (Children[i] != this)
332 Children[i]->dump(Indent + 2);