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