1103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel//===- LexicalScopes.cpp - Collecting lexical scope info ------------------===// 2103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 3103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// The LLVM Compiler Infrastructure 4103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 5103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// This file is distributed under the University of Illinois Open Source 6103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// License. See LICENSE.TXT for details. 7103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 8103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel//===----------------------------------------------------------------------===// 9103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 10103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// This file implements LexicalScopes analysis. 11103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 12103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// This pass collects lexical scope information and maps machine instructions 13103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// to respective lexical scopes. 14103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel// 15103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel//===----------------------------------------------------------------------===// 16103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 17103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#define DEBUG_TYPE "lexicalscopes" 18103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/CodeGen/LexicalScopes.h" 19103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/CodeGen/MachineFunction.h" 20103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/CodeGen/MachineInstr.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/DebugInfo.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 23103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/Support/Debug.h" 24103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/Support/ErrorHandling.h" 25103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#include "llvm/Support/FormattedStream.h" 26103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelusing namespace llvm; 27103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 28103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScopes::~LexicalScopes() { 29103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel releaseMemory(); 30103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 31103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 32103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// releaseMemory - release memory. 33103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes::releaseMemory() { 34103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MF = NULL; 35103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel CurrentFnLexicalScope = NULL; 36103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DeleteContainerSeconds(LexicalScopeMap); 37103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DeleteContainerSeconds(AbstractScopeMap); 38103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InlinedLexicalScopeMap.clear(); 39103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel AbstractScopesList.clear(); 40103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 41103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 42103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// initialize - Scan machine function and constuct lexical scope nest. 43103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes::initialize(const MachineFunction &Fn) { 44103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel releaseMemory(); 45103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MF = &Fn; 46103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel SmallVector<InsnRange, 4> MIRanges; 47103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DenseMap<const MachineInstr *, LexicalScope *> MI2ScopeMap; 48103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel extractLexicalScopes(MIRanges, MI2ScopeMap); 49103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (CurrentFnLexicalScope) { 50103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel constructScopeNest(CurrentFnLexicalScope); 51103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel assignInstructionRanges(MIRanges, MI2ScopeMap); 52103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 53103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 54103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 55103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// extractLexicalScopes - Extract instruction ranges for each lexical scopes 56103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// for the given machine function. 57103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes:: 58103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelextractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges, 59103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 60103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 61103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Scan each instruction and create scopes. First build working set of scopes. 62103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 63103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel I != E; ++I) { 64103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const MachineInstr *RangeBeginMI = NULL; 65103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const MachineInstr *PrevMI = NULL; 66103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DebugLoc PrevDL; 67103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (MachineBasicBlock::const_iterator II = I->begin(), IE = I->end(); 68103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel II != IE; ++II) { 69103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const MachineInstr *MInsn = II; 70103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 71103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Check if instruction has valid location information. 72103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const DebugLoc MIDL = MInsn->getDebugLoc(); 73103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (MIDL.isUnknown()) { 74103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevMI = MInsn; 75103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel continue; 76103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 77103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 78103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // If scope has not changed then skip this instruction. 79103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (MIDL == PrevDL) { 80103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevMI = MInsn; 81103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel continue; 82103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 83103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 84103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Ignore DBG_VALUE. It does not contribute to any instruction in output. 85103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (MInsn->isDebugValue()) 86103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel continue; 87103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 88103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (RangeBeginMI) { 89103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // If we have already seen a beginning of an instruction range and 90103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // current instruction scope does not match scope of first instruction 91103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // in this range then create a new instruction range. 92103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InsnRange R(RangeBeginMI, PrevMI); 93103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 94103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MIRanges.push_back(R); 95103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 96103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 97103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // This is a beginning of a new instruction range. 98103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel RangeBeginMI = MInsn; 99103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 100103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Reset previous markers. 101103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevMI = MInsn; 102103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevDL = MIDL; 103103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 104103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 105103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Create last instruction range. 106103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (RangeBeginMI && PrevMI && !PrevDL.isUnknown()) { 107103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InsnRange R(RangeBeginMI, PrevMI); 108103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MIRanges.push_back(R); 109103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 110103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 111103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 112103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 113103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 114103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// findLexicalScope - Find lexical scope, either regular or inlined, for the 115103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// given DebugLoc. Return NULL if not found. 116103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) { 117103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MDNode *Scope = NULL; 118103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MDNode *IA = NULL; 119103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext()); 120103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!Scope) return NULL; 1216618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher 1226618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher // The scope that we were created with could have an extra file - which 1236618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher // isn't what we care about in this case. 1246618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher DIDescriptor D = DIDescriptor(Scope); 1256618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher if (D.isLexicalBlockFile()) 1266618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher Scope = DILexicalBlockFile(Scope).getScope(); 1276618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher 128103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (IA) 129103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return InlinedLexicalScopeMap.lookup(DebugLoc::getFromDILocation(IA)); 1306618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher return LexicalScopeMap.lookup(Scope); 131103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 132103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 133103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 134103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// not available then create new lexical scope. 135103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { 136103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MDNode *Scope = NULL; 137103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MDNode *InlinedAt = NULL; 138103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext()); 1396618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher 140103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (InlinedAt) { 141103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Create an abstract scope for inlined function. 142103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel getOrCreateAbstractScope(Scope); 143103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel // Create an inlined scope for inlined function. 144103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return getOrCreateInlinedScope(Scope, InlinedAt); 145103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 146103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 147103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return getOrCreateRegularScope(Scope); 148103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 149103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 150103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// getOrCreateRegularScope - Find or create a regular lexical scope. 151103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) { 1526618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher DIDescriptor D = DIDescriptor(Scope); 153fe28ef41e34e842e6b77d9aa4bdf2bc2d6f17caeEric Christopher if (D.isLexicalBlockFile()) { 1546618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher Scope = DILexicalBlockFile(Scope).getScope(); 155fe28ef41e34e842e6b77d9aa4bdf2bc2d6f17caeEric Christopher D = DIDescriptor(Scope); 156fe28ef41e34e842e6b77d9aa4bdf2bc2d6f17caeEric Christopher } 1576618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher 158103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *WScope = LexicalScopeMap.lookup(Scope); 159103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (WScope) 160103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return WScope; 161103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 162103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *Parent = NULL; 1636618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher if (D.isLexicalBlock()) 164103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope)); 165103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel WScope = new LexicalScope(Parent, DIDescriptor(Scope), NULL, false); 166103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScopeMap.insert(std::make_pair(Scope, WScope)); 167103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!Parent && DIDescriptor(Scope).isSubprogram() 168103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel && DISubprogram(Scope).describes(MF->getFunction())) 169103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel CurrentFnLexicalScope = WScope; 170103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 171103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return WScope; 172103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 173103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 174103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// getOrCreateInlinedScope - Find or create an inlined lexical scope. 175103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *Scope, 176103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MDNode *InlinedAt) { 177103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *InlinedScope = LexicalScopeMap.lookup(InlinedAt); 178103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (InlinedScope) 179103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return InlinedScope; 180103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 181103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DebugLoc InlinedLoc = DebugLoc::getFromDILocation(InlinedAt); 182103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InlinedScope = new LexicalScope(getOrCreateLexicalScope(InlinedLoc), 183103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DIDescriptor(Scope), InlinedAt, false); 184103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InlinedLexicalScopeMap[InlinedLoc] = InlinedScope; 185103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScopeMap[InlinedAt] = InlinedScope; 186103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return InlinedScope; 187103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 188103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 189103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// getOrCreateAbstractScope - Find or create an abstract lexical scope. 190103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelLexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) { 191103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel assert(N && "Invalid Scope encoding!"); 192103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 1936618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher DIDescriptor Scope(N); 1946618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher if (Scope.isLexicalBlockFile()) 1956618a241f7ba2571a1a55b3733c4441d467baf42Eric Christopher Scope = DILexicalBlockFile(Scope).getScope(); 196103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *AScope = AbstractScopeMap.lookup(N); 197103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (AScope) 198103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return AScope; 199103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 200103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *Parent = NULL; 201103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (Scope.isLexicalBlock()) { 202103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DILexicalBlock DB(N); 203103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DIDescriptor ParentDesc = DB.getContext(); 204103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel Parent = getOrCreateAbstractScope(ParentDesc); 205103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 206103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel AScope = new LexicalScope(Parent, DIDescriptor(N), NULL, true); 207103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel AbstractScopeMap[N] = AScope; 208103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (DIDescriptor(N).isSubprogram()) 209103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel AbstractScopesList.push_back(AScope); 210103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return AScope; 211103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 212103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 213103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// constructScopeNest 214103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes::constructScopeNest(LexicalScope *Scope) { 215103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel assert (Scope && "Unable to calculate scop edominance graph!"); 216103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel SmallVector<LexicalScope *, 4> WorkStack; 217103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel WorkStack.push_back(Scope); 218103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel unsigned Counter = 0; 219103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel while (!WorkStack.empty()) { 220103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *WS = WorkStack.back(); 221103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const SmallVector<LexicalScope *, 4> &Children = WS->getChildren(); 222103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel bool visitedChildren = false; 223103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (SmallVector<LexicalScope *, 4>::const_iterator SI = Children.begin(), 224103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel SE = Children.end(); SI != SE; ++SI) { 225103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *ChildScope = *SI; 226103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!ChildScope->getDFSOut()) { 227103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel WorkStack.push_back(ChildScope); 228103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel visitedChildren = true; 229103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel ChildScope->setDFSIn(++Counter); 230103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel break; 231103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 232103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 233103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!visitedChildren) { 234103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel WorkStack.pop_back(); 235103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel WS->setDFSOut(++Counter); 236103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 237103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 238103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 239103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 2405bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang Patel/// assignInstructionRanges - Find ranges of instructions covered by each 2415bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang Patel/// lexical scope. 242103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes:: 243103b8e653c981fe916b855f1b96cb35e01c4543eDevang PatelassignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges, 2445bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang Patel DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) 2455bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang Patel{ 246103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 247103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *PrevLexicalScope = NULL; 248103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(), 249103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel RE = MIRanges.end(); RI != RE; ++RI) { 250103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const InsnRange &R = *RI; 251103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *S = MI2ScopeMap.lookup(R.first); 252103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel assert (S && "Lost LexicalScope for a machine instruction!"); 253103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) 254103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevLexicalScope->closeInsnRange(S); 255103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel S->openInsnRange(R.first); 256103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel S->extendInsnRange(R.second); 257103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevLexicalScope = S; 258103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 259103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 260103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (PrevLexicalScope) 261103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel PrevLexicalScope->closeInsnRange(); 262103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 263103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 264103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// getMachineBasicBlocks - Populate given set using machine basic blocks which 265103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// have machine instructions that belong to lexical scope identified by 266103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// DebugLoc. 267103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelvoid LexicalScopes:: 2685bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang PatelgetMachineBasicBlocks(DebugLoc DL, 2695bc942cc3cc970836d48d8ad276ef3b2b1120ffcDevang Patel SmallPtrSet<const MachineBasicBlock*, 4> &MBBs) { 270103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MBBs.clear(); 271103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *Scope = getOrCreateLexicalScope(DL); 272103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!Scope) 273103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return; 274103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 2752e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel if (Scope == CurrentFnLexicalScope) { 2762e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); 2772e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel I != E; ++I) 2782e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel MBBs.insert(I); 2792e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel return; 2802e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel } 2812e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel 282103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel SmallVector<InsnRange, 4> &InsnRanges = Scope->getRanges(); 283103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (SmallVector<InsnRange, 4>::iterator I = InsnRanges.begin(), 284103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel E = InsnRanges.end(); I != E; ++I) { 285103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel InsnRange &R = *I; 286103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel MBBs.insert(R.first->getParent()); 287103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 288103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 289103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 290103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// dominates - Return true if DebugLoc's lexical scope dominates at least one 291103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// machine instruction's lexical scope in a given machine basic block. 292103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patelbool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) { 293103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel LexicalScope *Scope = getOrCreateLexicalScope(DL); 294103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!Scope) 295103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return false; 2962e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel 2972e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel // Current function scope covers all basic blocks in the function. 2982e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) 2992e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel return true; 3002e85b1bfa7412577dd61f21ea10a686d3685144bDevang Patel 301103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel bool Result = false; 302103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 303103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel I != E; ++I) { 304103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel DebugLoc IDL = I->getDebugLoc(); 305103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (IDL.isUnknown()) 306103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel continue; 307103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) 308103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (Scope->dominates(IScope)) 309103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return true; 310103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel } 311103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel return Result; 312103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 313103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 3142d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid LexicalScope::anchor() { } 3152d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 316103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel/// dump - Print data structures. 3177650d9b893b83b6261d1bbc892464aa9d61cc23fManman Renvoid LexicalScope::dump(unsigned Indent) const { 318103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#ifndef NDEBUG 319103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel raw_ostream &err = dbgs(); 3207650d9b893b83b6261d1bbc892464aa9d61cc23fManman Ren err.indent(Indent); 321103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; 322103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel const MDNode *N = Desc; 3237650d9b893b83b6261d1bbc892464aa9d61cc23fManman Ren err.indent(Indent); 324103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel N->dump(); 325103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (AbstractScope) 3267650d9b893b83b6261d1bbc892464aa9d61cc23fManman Ren err << std::string(Indent, ' ') << "Abstract Scope\n"; 327103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 328103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (!Children.empty()) 3297650d9b893b83b6261d1bbc892464aa9d61cc23fManman Ren err << std::string(Indent + 2, ' ') << "Children ...\n"; 330103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel for (unsigned i = 0, e = Children.size(); i != e; ++i) 331103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel if (Children[i] != this) 3327650d9b893b83b6261d1bbc892464aa9d61cc23fManman Ren Children[i]->dump(Indent + 2); 333103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel#endif 334103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel} 335103b8e653c981fe916b855f1b96cb35e01c4543eDevang Patel 336