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