Home | History | Annotate | Download | only in CodeGen 
      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:
     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.
     57   bool empty() { return CurrentFnLexicalScope == NULL; }
     58 
     59   /// isCurrentFunctionScope - Return true if given lexical scope represents
     60   /// current function.
     61   bool isCurrentFunctionScope(const LexicalScope *LS) {
     62     return LS == CurrentFnLexicalScope;
     63   }
     64 
     65   /// getCurrentFunctionScope - Return lexical scope for the current function.
     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.
     83   ArrayRef<LexicalScope *> getAbstractScopesList() const {
     84     return AbstractScopesList;
     85   }
     86 
     87   /// findAbstractScope - Find an abstract scope or return NULL.
     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.
     94   LexicalScope *findInlinedScope(DebugLoc DL) {
     95     return InlinedLexicalScopeMap.lookup(DL);
     96   }
     97 
     98   /// findLexicalScope - Find regular lexical scope or return NULL.
     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:
    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 
    165   virtual ~LexicalScope() {}
    166 
    167   // Accessors.
    168   LexicalScope *getParent() const               { return Parent; }
    169   const MDNode *getDesc() const                 { return Desc; }
    170   const MDNode *getInlinedAt() const            { return InlinedAtLocation; }
    171   const MDNode *getScopeNode() const            { return Desc; }
    172   bool isAbstractScope() const                  { return AbstractScope; }
    173   SmallVector<LexicalScope *, 4> &getChildren() { return Children; }
    174   SmallVector<InsnRange, 4> &getRanges()        { return Ranges; }
    175 
    176   /// addChild - Add a child scope.
    177   void addChild(LexicalScope *S) { Children.push_back(S); }
    178 
    179   /// openInsnRange - This scope covers instruction range starting from 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.
    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.
    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.
    221   unsigned getDFSOut() const            { return DFSOut; }
    222   void setDFSOut(unsigned O)            { DFSOut = O; }
    223   unsigned getDFSIn() const             { return DFSIn; }
    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