LexicalScopes.cpp revision 280031
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" 25using namespace llvm; 26 27#define DEBUG_TYPE "lexicalscopes" 28 29/// reset - Reset the instance so that it's prepared for another function. 30void 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. 40void 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. 54void 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 DebugLoc PrevDL; 63 for (const auto &MInsn : MBB) { 64 // Check if instruction has valid location information. 65 const DebugLoc MIDL = MInsn.getDebugLoc(); 66 if (MIDL.isUnknown()) { 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.isUnknown()) { 100 InsnRange R(RangeBeginMI, PrevMI); 101 MIRanges.push_back(R); 102 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 103 } 104 } 105} 106 107LexicalScope *LexicalScopes::findInlinedScope(DebugLoc DL) { 108 MDNode *Scope = nullptr; 109 MDNode *IA = nullptr; 110 DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext()); 111 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); 112 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 113} 114 115/// findLexicalScope - Find lexical scope, either regular or inlined, for the 116/// given DebugLoc. Return NULL if not found. 117LexicalScope *LexicalScopes::findLexicalScope(DebugLoc DL) { 118 MDNode *Scope = nullptr; 119 MDNode *IA = nullptr; 120 DL.getScopeAndInlinedAt(Scope, IA, MF->getFunction()->getContext()); 121 if (!Scope) 122 return nullptr; 123 124 // The scope that we were created with could have an extra file - which 125 // isn't what we care about in this case. 126 DIDescriptor D = DIDescriptor(Scope); 127 if (D.isLexicalBlockFile()) 128 Scope = DILexicalBlockFile(Scope).getScope(); 129 130 if (IA) { 131 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); 132 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 133 } 134 return findLexicalScope(Scope); 135} 136 137/// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 138/// not available then create new lexical scope. 139LexicalScope *LexicalScopes::getOrCreateLexicalScope(DebugLoc DL) { 140 if (DL.isUnknown()) 141 return nullptr; 142 MDNode *Scope = nullptr; 143 MDNode *InlinedAt = nullptr; 144 DL.getScopeAndInlinedAt(Scope, InlinedAt, MF->getFunction()->getContext()); 145 146 if (InlinedAt) { 147 // Create an abstract scope for inlined function. 148 getOrCreateAbstractScope(Scope); 149 // Create an inlined scope for inlined function. 150 return getOrCreateInlinedScope(Scope, InlinedAt); 151 } 152 153 return getOrCreateRegularScope(Scope); 154} 155 156/// getOrCreateRegularScope - Find or create a regular lexical scope. 157LexicalScope *LexicalScopes::getOrCreateRegularScope(MDNode *Scope) { 158 DIDescriptor D = DIDescriptor(Scope); 159 if (D.isLexicalBlockFile()) { 160 Scope = DILexicalBlockFile(Scope).getScope(); 161 D = DIDescriptor(Scope); 162 } 163 164 auto I = LexicalScopeMap.find(Scope); 165 if (I != LexicalScopeMap.end()) 166 return &I->second; 167 168 LexicalScope *Parent = nullptr; 169 if (D.isLexicalBlock()) 170 Parent = getOrCreateLexicalScope(DebugLoc::getFromDILexicalBlock(Scope)); 171 // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012 172 // compatibility is no longer required. 173 I = LexicalScopeMap.emplace(std::piecewise_construct, std::make_tuple(Scope), 174 std::make_tuple(Parent, DIDescriptor(Scope), 175 nullptr, false)).first; 176 177 if (!Parent) { 178 assert(DIDescriptor(Scope).isSubprogram()); 179 assert(DISubprogram(Scope).describes(MF->getFunction())); 180 assert(!CurrentFnLexicalScope); 181 CurrentFnLexicalScope = &I->second; 182 } 183 184 return &I->second; 185} 186 187/// getOrCreateInlinedScope - Find or create an inlined lexical scope. 188LexicalScope *LexicalScopes::getOrCreateInlinedScope(MDNode *ScopeNode, 189 MDNode *InlinedAt) { 190 std::pair<const MDNode*, const MDNode*> P(ScopeNode, InlinedAt); 191 auto I = InlinedLexicalScopeMap.find(P); 192 if (I != InlinedLexicalScopeMap.end()) 193 return &I->second; 194 195 LexicalScope *Parent; 196 DILexicalBlock Scope(ScopeNode); 197 if (Scope.isSubprogram()) 198 Parent = getOrCreateLexicalScope(DebugLoc::getFromDILocation(InlinedAt)); 199 else 200 Parent = getOrCreateInlinedScope(Scope.getContext(), InlinedAt); 201 202 // FIXME: Use forward_as_tuple instead of make_tuple, once MSVC2012 203 // compatibility is no longer required. 204 I = InlinedLexicalScopeMap.emplace(std::piecewise_construct, 205 std::make_tuple(P), 206 std::make_tuple(Parent, Scope, InlinedAt, 207 false)).first; 208 return &I->second; 209} 210 211/// getOrCreateAbstractScope - Find or create an abstract lexical scope. 212LexicalScope *LexicalScopes::getOrCreateAbstractScope(const MDNode *N) { 213 assert(N && "Invalid Scope encoding!"); 214 215 DIDescriptor Scope(N); 216 if (Scope.isLexicalBlockFile()) 217 Scope = DILexicalBlockFile(Scope).getScope(); 218 auto I = AbstractScopeMap.find(Scope); 219 if (I != AbstractScopeMap.end()) 220 return &I->second; 221 222 LexicalScope *Parent = nullptr; 223 if (Scope.isLexicalBlock()) { 224 DILexicalBlock DB(Scope); 225 DIDescriptor ParentDesc = DB.getContext(); 226 Parent = getOrCreateAbstractScope(ParentDesc); 227 } 228 I = AbstractScopeMap.emplace(std::piecewise_construct, 229 std::forward_as_tuple(Scope), 230 std::forward_as_tuple(Parent, Scope, 231 nullptr, true)).first; 232 if (Scope.isSubprogram()) 233 AbstractScopesList.push_back(&I->second); 234 return &I->second; 235} 236 237/// constructScopeNest 238void LexicalScopes::constructScopeNest(LexicalScope *Scope) { 239 assert(Scope && "Unable to calculate scope dominance graph!"); 240 SmallVector<LexicalScope *, 4> WorkStack; 241 WorkStack.push_back(Scope); 242 unsigned Counter = 0; 243 while (!WorkStack.empty()) { 244 LexicalScope *WS = WorkStack.back(); 245 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren(); 246 bool visitedChildren = false; 247 for (SmallVectorImpl<LexicalScope *>::const_iterator SI = Children.begin(), 248 SE = Children.end(); 249 SI != SE; ++SI) { 250 LexicalScope *ChildScope = *SI; 251 if (!ChildScope->getDFSOut()) { 252 WorkStack.push_back(ChildScope); 253 visitedChildren = true; 254 ChildScope->setDFSIn(++Counter); 255 break; 256 } 257 } 258 if (!visitedChildren) { 259 WorkStack.pop_back(); 260 WS->setDFSOut(++Counter); 261 } 262 } 263} 264 265/// assignInstructionRanges - Find ranges of instructions covered by each 266/// lexical scope. 267void LexicalScopes::assignInstructionRanges( 268 SmallVectorImpl<InsnRange> &MIRanges, 269 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 270 271 LexicalScope *PrevLexicalScope = nullptr; 272 for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(), 273 RE = MIRanges.end(); 274 RI != RE; ++RI) { 275 const InsnRange &R = *RI; 276 LexicalScope *S = MI2ScopeMap.lookup(R.first); 277 assert(S && "Lost LexicalScope for a machine instruction!"); 278 if (PrevLexicalScope && !PrevLexicalScope->dominates(S)) 279 PrevLexicalScope->closeInsnRange(S); 280 S->openInsnRange(R.first); 281 S->extendInsnRange(R.second); 282 PrevLexicalScope = S; 283 } 284 285 if (PrevLexicalScope) 286 PrevLexicalScope->closeInsnRange(); 287} 288 289/// getMachineBasicBlocks - Populate given set using machine basic blocks which 290/// have machine instructions that belong to lexical scope identified by 291/// DebugLoc. 292void LexicalScopes::getMachineBasicBlocks( 293 DebugLoc DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) { 294 MBBs.clear(); 295 LexicalScope *Scope = getOrCreateLexicalScope(DL); 296 if (!Scope) 297 return; 298 299 if (Scope == CurrentFnLexicalScope) { 300 for (const auto &MBB : *MF) 301 MBBs.insert(&MBB); 302 return; 303 } 304 305 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges(); 306 for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(), 307 E = InsnRanges.end(); 308 I != E; ++I) { 309 InsnRange &R = *I; 310 MBBs.insert(R.first->getParent()); 311 } 312} 313 314/// dominates - Return true if DebugLoc's lexical scope dominates at least one 315/// machine instruction's lexical scope in a given machine basic block. 316bool LexicalScopes::dominates(DebugLoc DL, MachineBasicBlock *MBB) { 317 LexicalScope *Scope = getOrCreateLexicalScope(DL); 318 if (!Scope) 319 return false; 320 321 // Current function scope covers all basic blocks in the function. 322 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) 323 return true; 324 325 bool Result = false; 326 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 327 ++I) { 328 DebugLoc IDL = I->getDebugLoc(); 329 if (IDL.isUnknown()) 330 continue; 331 if (LexicalScope *IScope = getOrCreateLexicalScope(IDL)) 332 if (Scope->dominates(IScope)) 333 return true; 334 } 335 return Result; 336} 337 338/// dump - Print data structures. 339void LexicalScope::dump(unsigned Indent) const { 340#ifndef NDEBUG 341 raw_ostream &err = dbgs(); 342 err.indent(Indent); 343 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; 344 const MDNode *N = Desc; 345 err.indent(Indent); 346 N->dump(); 347 if (AbstractScope) 348 err << std::string(Indent, ' ') << "Abstract Scope\n"; 349 350 if (!Children.empty()) 351 err << std::string(Indent + 2, ' ') << "Children ...\n"; 352 for (unsigned i = 0, e = Children.size(); i != e; ++i) 353 if (Children[i] != this) 354 Children[i]->dump(Indent + 2); 355#endif 356} 357