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