include/llvm/CodeGen/LexicalScopes.h

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