1226584Sdim//===- LexicalScopes.cpp - Collecting lexical scope info -*- C++ -*--------===// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim// 10226584Sdim// This file implements LexicalScopes analysis. 11226584Sdim// 12226584Sdim// This pass collects lexical scope information and maps machine instructions 13226584Sdim// to respective lexical scopes. 14226584Sdim// 15226584Sdim//===----------------------------------------------------------------------===// 16226584Sdim 17226584Sdim#ifndef LLVM_CODEGEN_LEXICALSCOPES_H 18226584Sdim#define LLVM_CODEGEN_LEXICALSCOPES_H 19226584Sdim 20226584Sdim#include "llvm/ADT/ArrayRef.h" 21226584Sdim#include "llvm/ADT/DenseMap.h" 22226584Sdim#include "llvm/ADT/SmallPtrSet.h" 23226584Sdim#include "llvm/ADT/SmallVector.h" 24249423Sdim#include "llvm/IR/Metadata.h" 25226584Sdim#include "llvm/Support/DebugLoc.h" 26226584Sdim#include "llvm/Support/ValueHandle.h" 27226584Sdim#include <utility> 28226584Sdimnamespace llvm { 29226584Sdim 30226584Sdimclass MachineInstr; 31226584Sdimclass MachineBasicBlock; 32226584Sdimclass MachineFunction; 33226584Sdimclass LexicalScope; 34226584Sdim 35226584Sdim//===----------------------------------------------------------------------===// 36226584Sdim/// InsnRange - This is used to track range of instructions with identical 37226584Sdim/// lexical scope. 38226584Sdim/// 39226584Sdimtypedef std::pair<const MachineInstr *, const MachineInstr *> InsnRange; 40226584Sdim 41226584Sdim//===----------------------------------------------------------------------===// 42226584Sdim/// LexicalScopes - This class provides interface to collect and use lexical 43226584Sdim/// scoping information from machine instruction. 44226584Sdim/// 45226584Sdimclass LexicalScopes { 46226584Sdimpublic: 47226584Sdim LexicalScopes() : MF(NULL), CurrentFnLexicalScope(NULL) { } 48226584Sdim virtual ~LexicalScopes(); 49226584Sdim 50226584Sdim /// initialize - Scan machine function and constuct lexical scope nest. 51226584Sdim virtual void initialize(const MachineFunction &); 52226584Sdim 53226584Sdim /// releaseMemory - release memory. 54226584Sdim virtual void releaseMemory(); 55226584Sdim 56226584Sdim /// empty - Return true if there is any lexical scope information available. 57226584Sdim bool empty() { return CurrentFnLexicalScope == NULL; } 58226584Sdim 59226584Sdim /// isCurrentFunctionScope - Return true if given lexical scope represents 60226584Sdim /// current function. 61226584Sdim bool isCurrentFunctionScope(const LexicalScope *LS) { 62226584Sdim return LS == CurrentFnLexicalScope; 63226584Sdim } 64226584Sdim 65226584Sdim /// getCurrentFunctionScope - Return lexical scope for the current function. 66226584Sdim LexicalScope *getCurrentFunctionScope() const { return CurrentFnLexicalScope;} 67226584Sdim 68226584Sdim /// getMachineBasicBlocks - Populate given set using machine basic blocks 69226584Sdim /// which have machine instructions that belong to lexical scope identified by 70226584Sdim /// DebugLoc. 71226584Sdim void getMachineBasicBlocks(DebugLoc DL, 72226584Sdim SmallPtrSet<const MachineBasicBlock*, 4> &MBBs); 73226584Sdim 74226584Sdim /// dominates - Return true if DebugLoc's lexical scope dominates at least one 75226584Sdim /// machine instruction's lexical scope in a given machine basic block. 76226584Sdim bool dominates(DebugLoc DL, MachineBasicBlock *MBB); 77226584Sdim 78226584Sdim /// findLexicalScope - Find lexical scope, either regular or inlined, for the 79226584Sdim /// given DebugLoc. Return NULL if not found. 80226584Sdim LexicalScope *findLexicalScope(DebugLoc DL); 81226584Sdim 82226584Sdim /// getAbstractScopesList - Return a reference to list of abstract scopes. 83226584Sdim ArrayRef<LexicalScope *> getAbstractScopesList() const { 84226584Sdim return AbstractScopesList; 85226584Sdim } 86226584Sdim 87226584Sdim /// findAbstractScope - Find an abstract scope or return NULL. 88226584Sdim LexicalScope *findAbstractScope(const MDNode *N) { 89226584Sdim return AbstractScopeMap.lookup(N); 90226584Sdim } 91226584Sdim 92226584Sdim /// findInlinedScope - Find an inlined scope for the given DebugLoc or return 93226584Sdim /// NULL. 94226584Sdim LexicalScope *findInlinedScope(DebugLoc DL) { 95226584Sdim return InlinedLexicalScopeMap.lookup(DL); 96226584Sdim } 97226584Sdim 98226584Sdim /// findLexicalScope - Find regular lexical scope or return NULL. 99226584Sdim LexicalScope *findLexicalScope(const MDNode *N) { 100226584Sdim return LexicalScopeMap.lookup(N); 101226584Sdim } 102226584Sdim 103226584Sdim /// dump - Print data structures to dbgs(). 104226584Sdim void dump(); 105226584Sdim 106226584Sdimprivate: 107226584Sdim 108226584Sdim /// getOrCreateLexicalScope - Find lexical scope for the given DebugLoc. If 109226584Sdim /// not available then create new lexical scope. 110226584Sdim LexicalScope *getOrCreateLexicalScope(DebugLoc DL); 111226584Sdim 112226584Sdim /// getOrCreateRegularScope - Find or create a regular lexical scope. 113226584Sdim LexicalScope *getOrCreateRegularScope(MDNode *Scope); 114226584Sdim 115226584Sdim /// getOrCreateInlinedScope - Find or create an inlined lexical scope. 116226584Sdim LexicalScope *getOrCreateInlinedScope(MDNode *Scope, MDNode *InlinedAt); 117226584Sdim 118226584Sdim /// getOrCreateAbstractScope - Find or create an abstract lexical scope. 119226584Sdim LexicalScope *getOrCreateAbstractScope(const MDNode *N); 120226584Sdim 121226584Sdim /// extractLexicalScopes - Extract instruction ranges for each lexical scopes 122226584Sdim /// for the given machine function. 123226584Sdim void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges, 124226584Sdim DenseMap<const MachineInstr *, LexicalScope *> &M); 125226584Sdim void constructScopeNest(LexicalScope *Scope); 126226584Sdim void assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges, 127226584Sdim DenseMap<const MachineInstr *, LexicalScope *> &M); 128226584Sdim 129226584Sdimprivate: 130226584Sdim const MachineFunction *MF; 131226584Sdim 132226584Sdim /// LexicalScopeMap - Tracks the scopes in the current function. Owns the 133226584Sdim /// contained LexicalScope*s. 134226584Sdim DenseMap<const MDNode *, LexicalScope *> LexicalScopeMap; 135226584Sdim 136226584Sdim /// InlinedLexicalScopeMap - Tracks inlined function scopes in current function. 137226584Sdim DenseMap<DebugLoc, LexicalScope *> InlinedLexicalScopeMap; 138226584Sdim 139226584Sdim /// AbstractScopeMap - These scopes are not included LexicalScopeMap. 140226584Sdim /// AbstractScopes owns its LexicalScope*s. 141226584Sdim DenseMap<const MDNode *, LexicalScope *> AbstractScopeMap; 142226584Sdim 143226584Sdim /// AbstractScopesList - Tracks abstract scopes constructed while processing 144263508Sdim /// a function. 145263508Sdim SmallVector<LexicalScope *, 4> AbstractScopesList; 146226584Sdim 147226584Sdim /// CurrentFnLexicalScope - Top level scope for the current function. 148226584Sdim /// 149226584Sdim LexicalScope *CurrentFnLexicalScope; 150226584Sdim}; 151226584Sdim 152226584Sdim//===----------------------------------------------------------------------===// 153226584Sdim/// LexicalScope - This class is used to track scope information. 154226584Sdim/// 155226584Sdimclass LexicalScope { 156234353Sdim virtual void anchor(); 157226584Sdim 158226584Sdimpublic: 159226584Sdim LexicalScope(LexicalScope *P, const MDNode *D, const MDNode *I, bool A) 160226584Sdim : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A), 161239462Sdim LastInsn(0), FirstInsn(0), DFSIn(0), DFSOut(0) { 162226584Sdim if (Parent) 163226584Sdim Parent->addChild(this); 164226584Sdim } 165226584Sdim 166226584Sdim virtual ~LexicalScope() {} 167226584Sdim 168226584Sdim // Accessors. 169263508Sdim LexicalScope *getParent() const { return Parent; } 170263508Sdim const MDNode *getDesc() const { return Desc; } 171263508Sdim const MDNode *getInlinedAt() const { return InlinedAtLocation; } 172263508Sdim const MDNode *getScopeNode() const { return Desc; } 173263508Sdim bool isAbstractScope() const { return AbstractScope; } 174263508Sdim SmallVectorImpl<LexicalScope *> &getChildren() { return Children; } 175263508Sdim SmallVectorImpl<InsnRange> &getRanges() { return Ranges; } 176226584Sdim 177226584Sdim /// addChild - Add a child scope. 178226584Sdim void addChild(LexicalScope *S) { Children.push_back(S); } 179226584Sdim 180226584Sdim /// openInsnRange - This scope covers instruction range starting from MI. 181226584Sdim void openInsnRange(const MachineInstr *MI) { 182226584Sdim if (!FirstInsn) 183226584Sdim FirstInsn = MI; 184226584Sdim 185226584Sdim if (Parent) 186226584Sdim Parent->openInsnRange(MI); 187226584Sdim } 188226584Sdim 189226584Sdim /// extendInsnRange - Extend the current instruction range covered by 190226584Sdim /// this scope. 191226584Sdim void extendInsnRange(const MachineInstr *MI) { 192226584Sdim assert (FirstInsn && "MI Range is not open!"); 193226584Sdim LastInsn = MI; 194226584Sdim if (Parent) 195226584Sdim Parent->extendInsnRange(MI); 196226584Sdim } 197226584Sdim 198226584Sdim /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected 199226584Sdim /// until now. This is used when a new scope is encountered while walking 200226584Sdim /// machine instructions. 201226584Sdim void closeInsnRange(LexicalScope *NewScope = NULL) { 202226584Sdim assert (LastInsn && "Last insn missing!"); 203226584Sdim Ranges.push_back(InsnRange(FirstInsn, LastInsn)); 204226584Sdim FirstInsn = NULL; 205226584Sdim LastInsn = NULL; 206226584Sdim // If Parent dominates NewScope then do not close Parent's instruction 207226584Sdim // range. 208226584Sdim if (Parent && (!NewScope || !Parent->dominates(NewScope))) 209226584Sdim Parent->closeInsnRange(NewScope); 210226584Sdim } 211226584Sdim 212234353Sdim /// dominates - Return true if current scope dominates given lexical scope. 213226584Sdim bool dominates(const LexicalScope *S) const { 214226584Sdim if (S == this) 215226584Sdim return true; 216226584Sdim if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut()) 217226584Sdim return true; 218226584Sdim return false; 219226584Sdim } 220226584Sdim 221226584Sdim // Depth First Search support to walk and manipulate LexicalScope hierarchy. 222226584Sdim unsigned getDFSOut() const { return DFSOut; } 223226584Sdim void setDFSOut(unsigned O) { DFSOut = O; } 224226584Sdim unsigned getDFSIn() const { return DFSIn; } 225226584Sdim void setDFSIn(unsigned I) { DFSIn = I; } 226226584Sdim 227226584Sdim /// dump - print lexical scope. 228249423Sdim void dump(unsigned Indent = 0) const; 229226584Sdim 230226584Sdimprivate: 231226584Sdim LexicalScope *Parent; // Parent to this scope. 232226584Sdim AssertingVH<const MDNode> Desc; // Debug info descriptor. 233226584Sdim AssertingVH<const MDNode> InlinedAtLocation; // Location at which this 234226584Sdim // scope is inlined. 235226584Sdim bool AbstractScope; // Abstract Scope 236226584Sdim SmallVector<LexicalScope *, 4> Children; // Scopes defined in scope. 237226584Sdim // Contents not owned. 238226584Sdim SmallVector<InsnRange, 4> Ranges; 239226584Sdim 240226584Sdim const MachineInstr *LastInsn; // Last instruction of this scope. 241226584Sdim const MachineInstr *FirstInsn; // First instruction of this scope. 242226584Sdim unsigned DFSIn, DFSOut; // In & Out Depth use to determine 243226584Sdim // scope nesting. 244226584Sdim}; 245226584Sdim 246226584Sdim} // end llvm namespace 247226584Sdim 248226584Sdim#endif 249