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" 25 using namespace llvm; 26 27 #define DEBUG_TYPE "lexicalscopes" 28 29 /// reset - Reset the instance so that it's prepared for another function. 30 void 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. 40 void 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. 54 void 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 const DILocation *PrevDL = nullptr; 63 for (const auto &MInsn : MBB) { 64 // Check if instruction has valid location information. 65 const DILocation *MIDL = MInsn.getDebugLoc(); 66 if (!MIDL) { 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) { 100 InsnRange R(RangeBeginMI, PrevMI); 101 MIRanges.push_back(R); 102 MI2ScopeMap[RangeBeginMI] = getOrCreateLexicalScope(PrevDL); 103 } 104 } 105 } 106 107 /// findLexicalScope - Find lexical scope, either regular or inlined, for the 108 /// given DebugLoc. Return NULL if not found. 109 LexicalScope *LexicalScopes::findLexicalScope(const DILocation *DL) { 110 DILocalScope *Scope = DL->getScope(); 111 if (!Scope) 112 return nullptr; 113 114 // The scope that we were created with could have an extra file - which 115 // isn't what we care about in this case. 116 Scope = Scope->getNonLexicalBlockFileScope(); 117 118 if (auto *IA = DL->getInlinedAt()) { 119 auto I = InlinedLexicalScopeMap.find(std::make_pair(Scope, IA)); 120 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 121 } 122 return findLexicalScope(Scope); 123 } 124 125 /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 126 /// not available then create new lexical scope. 127 LexicalScope *LexicalScopes::getOrCreateLexicalScope(const DILocalScope *Scope, 128 const DILocation *IA) { 129 if (IA) { 130 // Create an abstract scope for inlined function. 131 getOrCreateAbstractScope(Scope); 132 // Create an inlined scope for inlined function. 133 return getOrCreateInlinedScope(Scope, IA); 134 } 135 136 return getOrCreateRegularScope(Scope); 137 } 138 139 /// getOrCreateRegularScope - Find or create a regular lexical scope. 140 LexicalScope * 141 LexicalScopes::getOrCreateRegularScope(const DILocalScope *Scope) { 142 assert(Scope && "Invalid Scope encoding!"); 143 Scope = Scope->getNonLexicalBlockFileScope(); 144 145 auto I = LexicalScopeMap.find(Scope); 146 if (I != LexicalScopeMap.end()) 147 return &I->second; 148 149 // FIXME: Should the following dyn_cast be DILexicalBlock? 150 LexicalScope *Parent = nullptr; 151 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 152 Parent = getOrCreateLexicalScope(Block->getScope()); 153 I = LexicalScopeMap.emplace(std::piecewise_construct, 154 std::forward_as_tuple(Scope), 155 std::forward_as_tuple(Parent, Scope, nullptr, 156 false)).first; 157 158 if (!Parent) { 159 assert(cast<DISubprogram>(Scope)->describes(MF->getFunction())); 160 assert(!CurrentFnLexicalScope); 161 CurrentFnLexicalScope = &I->second; 162 } 163 164 return &I->second; 165 } 166 167 /// getOrCreateInlinedScope - Find or create an inlined lexical scope. 168 LexicalScope * 169 LexicalScopes::getOrCreateInlinedScope(const DILocalScope *Scope, 170 const DILocation *InlinedAt) { 171 assert(Scope && "Invalid Scope encoding!"); 172 Scope = Scope->getNonLexicalBlockFileScope(); 173 std::pair<const DILocalScope *, const DILocation *> P(Scope, InlinedAt); 174 auto I = InlinedLexicalScopeMap.find(P); 175 if (I != InlinedLexicalScopeMap.end()) 176 return &I->second; 177 178 LexicalScope *Parent; 179 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 180 Parent = getOrCreateInlinedScope(Block->getScope(), InlinedAt); 181 else 182 Parent = getOrCreateLexicalScope(InlinedAt); 183 184 I = InlinedLexicalScopeMap.emplace(std::piecewise_construct, 185 std::forward_as_tuple(P), 186 std::forward_as_tuple(Parent, Scope, 187 InlinedAt, false)) 188 .first; 189 return &I->second; 190 } 191 192 /// getOrCreateAbstractScope - Find or create an abstract lexical scope. 193 LexicalScope * 194 LexicalScopes::getOrCreateAbstractScope(const DILocalScope *Scope) { 195 assert(Scope && "Invalid Scope encoding!"); 196 Scope = Scope->getNonLexicalBlockFileScope(); 197 auto I = AbstractScopeMap.find(Scope); 198 if (I != AbstractScopeMap.end()) 199 return &I->second; 200 201 // FIXME: Should the following isa be DILexicalBlock? 202 LexicalScope *Parent = nullptr; 203 if (auto *Block = dyn_cast<DILexicalBlockBase>(Scope)) 204 Parent = getOrCreateAbstractScope(Block->getScope()); 205 206 I = AbstractScopeMap.emplace(std::piecewise_construct, 207 std::forward_as_tuple(Scope), 208 std::forward_as_tuple(Parent, Scope, 209 nullptr, true)).first; 210 if (isa<DISubprogram>(Scope)) 211 AbstractScopesList.push_back(&I->second); 212 return &I->second; 213 } 214 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(), 226 SE = Children.end(); 227 SI != SE; ++SI) { 228 LexicalScope *ChildScope = *SI; 229 if (!ChildScope->getDFSOut()) { 230 WorkStack.push_back(ChildScope); 231 visitedChildren = true; 232 ChildScope->setDFSIn(++Counter); 233 break; 234 } 235 } 236 if (!visitedChildren) { 237 WorkStack.pop_back(); 238 WS->setDFSOut(++Counter); 239 } 240 } 241 } 242 243 /// assignInstructionRanges - Find ranges of instructions covered by each 244 /// lexical scope. 245 void LexicalScopes::assignInstructionRanges( 246 SmallVectorImpl<InsnRange> &MIRanges, 247 DenseMap<const MachineInstr *, LexicalScope *> &MI2ScopeMap) { 248 249 LexicalScope *PrevLexicalScope = nullptr; 250 for (SmallVectorImpl<InsnRange>::const_iterator RI = MIRanges.begin(), 251 RE = MIRanges.end(); 252 RI != RE; ++RI) { 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; 261 } 262 263 if (PrevLexicalScope) 264 PrevLexicalScope->closeInsnRange(); 265 } 266 267 /// getMachineBasicBlocks - Populate given set using machine basic blocks which 268 /// have machine instructions that belong to lexical scope identified by 269 /// DebugLoc. 270 void LexicalScopes::getMachineBasicBlocks( 271 const DILocation *DL, SmallPtrSetImpl<const MachineBasicBlock *> &MBBs) { 272 MBBs.clear(); 273 LexicalScope *Scope = getOrCreateLexicalScope(DL); 274 if (!Scope) 275 return; 276 277 if (Scope == CurrentFnLexicalScope) { 278 for (const auto &MBB : *MF) 279 MBBs.insert(&MBB); 280 return; 281 } 282 283 SmallVectorImpl<InsnRange> &InsnRanges = Scope->getRanges(); 284 for (SmallVectorImpl<InsnRange>::iterator I = InsnRanges.begin(), 285 E = InsnRanges.end(); 286 I != E; ++I) { 287 InsnRange &R = *I; 288 MBBs.insert(R.first->getParent()); 289 } 290 } 291 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(const DILocation *DL, MachineBasicBlock *MBB) { 295 LexicalScope *Scope = getOrCreateLexicalScope(DL); 296 if (!Scope) 297 return false; 298 299 // Current function scope covers all basic blocks in the function. 300 if (Scope == CurrentFnLexicalScope && MBB->getParent() == MF) 301 return true; 302 303 bool Result = false; 304 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; 305 ++I) { 306 if (const DILocation *IDL = I->getDebugLoc()) 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(unsigned Indent) const { 316 #ifndef NDEBUG 317 raw_ostream &err = dbgs(); 318 err.indent(Indent); 319 err << "DFSIn: " << DFSIn << " DFSOut: " << DFSOut << "\n"; 320 const MDNode *N = Desc; 321 err.indent(Indent); 322 N->dump(); 323 if (AbstractScope) 324 err << std::string(Indent, ' ') << "Abstract Scope\n"; 325 326 if (!Children.empty()) 327 err << std::string(Indent + 2, ' ') << "Children ...\n"; 328 for (unsigned i = 0, e = Children.size(); i != e; ++i) 329 if (Children[i] != this) 330 Children[i]->dump(Indent + 2); 331 #endif 332 } 333