1 //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===// 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 #ifndef LLVM_CODEGEN_LEXICALSCOPES_H 18 #define LLVM_CODEGEN_LEXICALSCOPES_H 19 20 #include "llvm/ADT/ArrayRef.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/IR/DebugInfoMetadata.h" 25 #include <cassert> 26 #include <unordered_map> 27 #include <utility> 28 29 namespace llvm { 30 31 class MachineBasicBlock; 32 class MachineFunction; 33 class MachineInstr; 34 35 //===----------------------------------------------------------------------===// 36 /// InsnRange - This is used to track range of instructions with identical 37 /// lexical scope. 38 /// 39 typedef std::pair<const MachineInstr *, const MachineInstr *> InsnRange; 40 41 //===----------------------------------------------------------------------===// 42 /// LexicalScope - This class is used to track scope information. 43 /// 44 class LexicalScope { 45 public: 46 LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I, 47 bool A) 48 : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) { 49 assert(D); 50 assert(D->getSubprogram()->getUnit()->getEmissionKind() != 51 DICompileUnit::NoDebug && 52 "Don't build lexical scopes for non-debug locations"); 53 assert(D->isResolved() && "Expected resolved node"); 54 assert((!I || I->isResolved()) && "Expected resolved node"); 55 if (Parent) 56 Parent->addChild(this); 57 } 58 59 // Accessors. 60 LexicalScope *getParent() const { return Parent; } 61 const MDNode *getDesc() const { return Desc; } 62 const DILocation *getInlinedAt() const { return InlinedAtLocation; } 63 const DILocalScope *getScopeNode() const { return Desc; } 64 bool isAbstractScope() const { return AbstractScope; } 65 SmallVectorImpl<LexicalScope *> &getChildren() { return Children; } 66 SmallVectorImpl<InsnRange> &getRanges() { return Ranges; } 67 68 /// addChild - Add a child scope. 69 void addChild(LexicalScope *S) { Children.push_back(S); } 70 71 /// openInsnRange - This scope covers instruction range starting from MI. 72 void openInsnRange(const MachineInstr *MI) { 73 if (!FirstInsn) 74 FirstInsn = MI; 75 76 if (Parent) 77 Parent->openInsnRange(MI); 78 } 79 80 /// extendInsnRange - Extend the current instruction range covered by 81 /// this scope. 82 void extendInsnRange(const MachineInstr *MI) { 83 assert(FirstInsn && "MI Range is not open!"); 84 LastInsn = MI; 85 if (Parent) 86 Parent->extendInsnRange(MI); 87 } 88 89 /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected 90 /// until now. This is used when a new scope is encountered while walking 91 /// machine instructions. 92 void closeInsnRange(LexicalScope *NewScope = nullptr) { 93 assert(LastInsn && "Last insn missing!"); 94 Ranges.push_back(InsnRange(FirstInsn, LastInsn)); 95 FirstInsn = nullptr; 96 LastInsn = nullptr; 97 // If Parent dominates NewScope then do not close Parent's instruction 98 // range. 99 if (Parent && (!NewScope || !Parent->dominates(NewScope))) 100 Parent->closeInsnRange(NewScope); 101 } 102 103 /// dominates - Return true if current scope dominates given lexical scope. 104 bool dominates(const LexicalScope *S) const { 105 if (S == this) 106 return true; 107 if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut()) 108 return true; 109 return false; 110 } 111 112 // Depth First Search support to walk and manipulate LexicalScope hierarchy. 113 unsigned getDFSOut() const { return DFSOut; } 114 void setDFSOut(unsigned O) { DFSOut = O; } 115 unsigned getDFSIn() const { return DFSIn; } 116 void setDFSIn(unsigned I) { DFSIn = I; } 117 118 /// dump - print lexical scope. 119 void dump(unsigned Indent = 0) const; 120 121 private: 122 LexicalScope *Parent; // Parent to this scope. 123 const DILocalScope *Desc; // Debug info descriptor. 124 const DILocation *InlinedAtLocation; // Location at which this 125 // scope is inlined. 126 bool AbstractScope; // Abstract Scope 127 SmallVector<LexicalScope *, 4> Children; // Scopes defined in scope. 128 // Contents not owned. 129 SmallVector<InsnRange, 4> Ranges; 130 131 const MachineInstr *LastInsn = nullptr; // Last instruction of this scope. 132 const MachineInstr *FirstInsn = nullptr; // First instruction of this scope. 133 unsigned DFSIn = 0; // In & Out Depth use to determine scope nesting. 134 unsigned DFSOut = 0; 135 }; 136 137 //===----------------------------------------------------------------------===// 138 /// LexicalScopes - This class provides interface to collect and use lexical 139 /// scoping information from machine instruction. 140 /// 141 class LexicalScopes { 142 public: 143 LexicalScopes() = default; 144 145 /// initialize - Scan machine function and constuct lexical scope nest, resets 146 /// the instance if necessary. 147 void initialize(const MachineFunction &); 148 149 /// releaseMemory - release memory. 150 void reset(); 151 152 /// empty - Return true if there is any lexical scope information available. 153 bool empty() { return CurrentFnLexicalScope == nullptr; } 154 155 /// getCurrentFunctionScope - Return lexical scope for the current function. 156 LexicalScope *getCurrentFunctionScope() const { 157 return CurrentFnLexicalScope; 158 } 159 160 /// getMachineBasicBlocks - Populate given set using machine basic blocks 161 /// which have machine instructions that belong to lexical scope identified by 162 /// DebugLoc. 163 void getMachineBasicBlocks(const DILocation *DL, 164 SmallPtrSetImpl<const MachineBasicBlock *> &MBBs); 165 166 /// dominates - Return true if DebugLoc's lexical scope dominates at least one 167 /// machine instruction's lexical scope in a given machine basic block. 168 bool dominates(const DILocation *DL, MachineBasicBlock *MBB); 169 170 /// findLexicalScope - Find lexical scope, either regular or inlined, for the 171 /// given DebugLoc. Return NULL if not found. 172 LexicalScope *findLexicalScope(const DILocation *DL); 173 174 /// getAbstractScopesList - Return a reference to list of abstract scopes. 175 ArrayRef<LexicalScope *> getAbstractScopesList() const { 176 return AbstractScopesList; 177 } 178 179 /// findAbstractScope - Find an abstract scope or return null. 180 LexicalScope *findAbstractScope(const DILocalScope *N) { 181 auto I = AbstractScopeMap.find(N); 182 return I != AbstractScopeMap.end() ? &I->second : nullptr; 183 } 184 185 /// findInlinedScope - Find an inlined scope for the given scope/inlined-at. 186 LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) { 187 auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA)); 188 return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr; 189 } 190 191 /// findLexicalScope - Find regular lexical scope or return null. 192 LexicalScope *findLexicalScope(const DILocalScope *N) { 193 auto I = LexicalScopeMap.find(N); 194 return I != LexicalScopeMap.end() ? &I->second : nullptr; 195 } 196 197 /// dump - Print data structures to dbgs(). 198 void dump(); 199 200 /// getOrCreateAbstractScope - Find or create an abstract lexical scope. 201 LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope); 202 203 private: 204 /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If 205 /// not available then create new lexical scope. 206 LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope, 207 const DILocation *IA = nullptr); 208 LexicalScope *getOrCreateLexicalScope(const DILocation *DL) { 209 return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt()) 210 : nullptr; 211 } 212 213 /// getOrCreateRegularScope - Find or create a regular lexical scope. 214 LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope); 215 216 /// getOrCreateInlinedScope - Find or create an inlined lexical scope. 217 LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope, 218 const DILocation *InlinedAt); 219 220 /// extractLexicalScopes - Extract instruction ranges for each lexical scopes 221 /// for the given machine function. 222 void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges, 223 DenseMap<const MachineInstr *, LexicalScope *> &M); 224 void constructScopeNest(LexicalScope *Scope); 225 void 226 assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges, 227 DenseMap<const MachineInstr *, LexicalScope *> &M); 228 229 const MachineFunction *MF = nullptr; 230 231 /// LexicalScopeMap - Tracks the scopes in the current function. 232 // Use an unordered_map to ensure value pointer validity over insertion. 233 std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap; 234 235 /// InlinedLexicalScopeMap - Tracks inlined function scopes in current 236 /// function. 237 std::unordered_map<std::pair<const DILocalScope *, const DILocation *>, 238 LexicalScope, 239 pair_hash<const DILocalScope *, const DILocation *>> 240 InlinedLexicalScopeMap; 241 242 /// AbstractScopeMap - These scopes are not included LexicalScopeMap. 243 // Use an unordered_map to ensure value pointer validity over insertion. 244 std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap; 245 246 /// AbstractScopesList - Tracks abstract scopes constructed while processing 247 /// a function. 248 SmallVector<LexicalScope *, 4> AbstractScopesList; 249 250 /// CurrentFnLexicalScope - Top level scope for the current function. 251 /// 252 LexicalScope *CurrentFnLexicalScope = nullptr; 253 }; 254 255 } // end namespace llvm 256 257 #endif // LLVM_CODEGEN_LEXICALSCOPES_H 258
