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