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