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