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