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   virtual void anchor();
    157 
    158 public:
    159   LexicalScope(LexicalScope *P, const MDNode *D, const MDNode *I, bool A)
    160     : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A),
    161       LastInsn(0), FirstInsn(0), DFSIn(0), DFSOut(0), IndentLevel(0) {
    162     if (Parent)
    163       Parent->addChild(this);
    164   }
    165 
    166   virtual ~LexicalScope() {}
    167 
    168   // Accessors.
    169   LexicalScope *getParent() const               { return Parent; }
    170   const MDNode *getDesc() const                 { return Desc; }
    171   const MDNode *getInlinedAt() const            { return InlinedAtLocation; }
    172   const MDNode *getScopeNode() const            { return Desc; }
    173   bool isAbstractScope() const                  { return AbstractScope; }
    174   SmallVector<LexicalScope *, 4> &getChildren() { return Children; }
    175   SmallVector<InsnRange, 4> &getRanges()        { return Ranges; }
    176 
    177   /// addChild - Add a child scope.
    178   void addChild(LexicalScope *S) { Children.push_back(S); }
    179 
    180   /// openInsnRange - This scope covers instruction range starting from MI.
    181   void openInsnRange(const MachineInstr *MI) {
    182     if (!FirstInsn)
    183       FirstInsn = MI;
    184 
    185     if (Parent)
    186       Parent->openInsnRange(MI);
    187   }
    188 
    189   /// extendInsnRange - Extend the current instruction range covered by
    190   /// this scope.
    191   void extendInsnRange(const MachineInstr *MI) {
    192     assert (FirstInsn && "MI Range is not open!");
    193     LastInsn = MI;
    194     if (Parent)
    195       Parent->extendInsnRange(MI);
    196   }
    197 
    198   /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected
    199   /// until now. This is used when a new scope is encountered while walking
    200   /// machine instructions.
    201   void closeInsnRange(LexicalScope *NewScope = NULL) {
    202     assert (LastInsn && "Last insn missing!");
    203     Ranges.push_back(InsnRange(FirstInsn, LastInsn));
    204     FirstInsn = NULL;
    205     LastInsn = NULL;
    206     // If Parent dominates NewScope then do not close Parent's instruction
    207     // range.
    208     if (Parent && (!NewScope || !Parent->dominates(NewScope)))
    209       Parent->closeInsnRange(NewScope);
    210   }
    211 
    212   /// dominates - Return true if current scope dominates given lexical scope.
    213   bool dominates(const LexicalScope *S) const {
    214     if (S == this)
    215       return true;
    216     if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
    217       return true;
    218     return false;
    219   }
    220 
    221   // Depth First Search support to walk and manipulate LexicalScope hierarchy.
    222   unsigned getDFSOut() const            { return DFSOut; }
    223   void setDFSOut(unsigned O)            { DFSOut = O; }
    224   unsigned getDFSIn() const             { return DFSIn; }
    225   void setDFSIn(unsigned I)             { DFSIn = I; }
    226 
    227   /// dump - print lexical scope.
    228   void dump() const;
    229 
    230 private:
    231   LexicalScope *Parent;                          // Parent to this scope.
    232   AssertingVH<const MDNode> Desc;                // Debug info descriptor.
    233   AssertingVH<const MDNode> InlinedAtLocation;   // Location at which this
    234                                                  // scope is inlined.
    235   bool AbstractScope;                            // Abstract Scope
    236   SmallVector<LexicalScope *, 4> Children;       // Scopes defined in scope.
    237                                                  // Contents not owned.
    238   SmallVector<InsnRange, 4> Ranges;
    239 
    240   const MachineInstr *LastInsn;       // Last instruction of this scope.
    241   const MachineInstr *FirstInsn;      // First instruction of this scope.
    242   unsigned DFSIn, DFSOut;             // In & Out Depth use to determine
    243                                       // scope nesting.
    244   mutable unsigned IndentLevel;       // Private state for dump()
    245 };
    246 
    247 } // end llvm namespace
    248 
    249 #endif
    250