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