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