include/llvm/CodeGen/LexicalScopes.h

   1 //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements LexicalScopes analysis.
  10 //
  11 // This pass collects lexical scope information and maps machine instructions
  12 // to respective lexical scopes.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_CODEGEN_LEXICALSCOPES_H
  17 #define LLVM_CODEGEN_LEXICALSCOPES_H
  18
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/IR/DebugInfoMetadata.h"
  24 #include <cassert>
  25 #include <unordered_map>
  26 #include <utility>
  27
  28 namespace llvm {
  29
  30 class MachineBasicBlock;
  31 class MachineFunction;
  32 class MachineInstr;
  33 class MDNode;
  34
  35 //===----------------------------------------------------------------------===//
  36 /// InsnRange - This is used to track range of instructions with identical
  37 /// lexical scope.
  38 ///
  39 using InsnRange = std::pair<const MachineInstr *, const MachineInstr *>;
  40
  41 //===----------------------------------------------------------------------===//
  42 /// LexicalScope - This class is used to track scope information.
  43 ///
  44 class LexicalScope {
  45 public:
  46   LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I,
  47                bool A)
  48       : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
  49     assert(D);
  50     assert(D->getSubprogram()->getUnit()->getEmissionKind() !=
  51            DICompileUnit::NoDebug &&
  52            "Don't build lexical scopes for non-debug locations");
  53     assert(D->isResolved() && "Expected resolved node");
  54     assert((!I || I->isResolved()) && "Expected resolved node");
  55     if (Parent)
  56       Parent->addChild(this);
  57   }
  58
  59   // Accessors.
  60   LexicalScope *getParent() const { return Parent; }
  61   const MDNode *getDesc() const { return Desc; }
  62   const DILocation *getInlinedAt() const { return InlinedAtLocation; }
  63   const DILocalScope *getScopeNode() const { return Desc; }
  64   bool isAbstractScope() const { return AbstractScope; }
  65   SmallVectorImpl<LexicalScope *> &getChildren() { return Children; }
  66   SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
  67
  68   /// addChild - Add a child scope.
  69   void addChild(LexicalScope *S) { Children.push_back(S); }
  70
  71   /// openInsnRange - This scope covers instruction range starting from MI.
  72   void openInsnRange(const MachineInstr *MI) {
  73     if (!FirstInsn)
  74       FirstInsn = MI;
  75
  76     if (Parent)
  77       Parent->openInsnRange(MI);
  78   }
  79
  80   /// extendInsnRange - Extend the current instruction range covered by
  81   /// this scope.
  82   void extendInsnRange(const MachineInstr *MI) {
  83     assert(FirstInsn && "MI Range is not open!");
  84     LastInsn = MI;
  85     if (Parent)
  86       Parent->extendInsnRange(MI);
  87   }
  88
  89   /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected
  90   /// until now. This is used when a new scope is encountered while walking
  91   /// machine instructions.
  92   void closeInsnRange(LexicalScope *NewScope = nullptr) {
  93     assert(LastInsn && "Last insn missing!");
  94     Ranges.push_back(InsnRange(FirstInsn, LastInsn));
  95     FirstInsn = nullptr;
  96     LastInsn = nullptr;
  97     // If Parent dominates NewScope then do not close Parent's instruction
  98     // range.
  99     if (Parent && (!NewScope || !Parent->dominates(NewScope)))
 100       Parent->closeInsnRange(NewScope);
 101   }
 102
 103   /// dominates - Return true if current scope dominates given lexical scope.
 104   bool dominates(const LexicalScope *S) const {
 105     if (S == this)
 106       return true;
 107     if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
 108       return true;
 109     return false;
 110   }
 111
 112   // Depth First Search support to walk and manipulate LexicalScope hierarchy.
 113   unsigned getDFSOut() const { return DFSOut; }
 114   void setDFSOut(unsigned O) { DFSOut = O; }
 115   unsigned getDFSIn() const { return DFSIn; }
 116   void setDFSIn(unsigned I) { DFSIn = I; }
 117
 118   /// dump - print lexical scope.
 119   void dump(unsigned Indent = 0) const;
 120
 121 private:
 122   LexicalScope *Parent;                        // Parent to this scope.
 123   const DILocalScope *Desc;                    // Debug info descriptor.
 124   const DILocation *InlinedAtLocation;         // Location at which this
 125                                                // scope is inlined.
 126   bool AbstractScope;                          // Abstract Scope
 127   SmallVector<LexicalScope *, 4> Children;     // Scopes defined in scope.
 128                                                // Contents not owned.
 129   SmallVector<InsnRange, 4> Ranges;
 130
 131   const MachineInstr *LastInsn = nullptr;  // Last instruction of this scope.
 132   const MachineInstr *FirstInsn = nullptr; // First instruction of this scope.
 133   unsigned DFSIn = 0; // In & Out Depth use to determine scope nesting.
 134   unsigned DFSOut = 0;
 135 };
 136
 137 //===----------------------------------------------------------------------===//
 138 /// LexicalScopes -  This class provides interface to collect and use lexical
 139 /// scoping information from machine instruction.
 140 ///
 141 class LexicalScopes {
 142 public:
 143   LexicalScopes() = default;
 144
 145   /// initialize - Scan machine function and constuct lexical scope nest, resets
 146   /// the instance if necessary.
 147   void initialize(const MachineFunction &);
 148
 149   /// releaseMemory - release memory.
 150   void reset();
 151
 152   /// empty - Return true if there is any lexical scope information available.
 153   bool empty() { return CurrentFnLexicalScope == nullptr; }
 154
 155   /// getCurrentFunctionScope - Return lexical scope for the current function.
 156   LexicalScope *getCurrentFunctionScope() const {
 157     return CurrentFnLexicalScope;
 158   }
 159
 160   /// getMachineBasicBlocks - Populate given set using machine basic blocks
 161   /// which have machine instructions that belong to lexical scope identified by
 162   /// DebugLoc.
 163   void getMachineBasicBlocks(const DILocation *DL,
 164                              SmallPtrSetImpl<const MachineBasicBlock *> &MBBs);
 165
 166   /// dominates - Return true if DebugLoc's lexical scope dominates at least one
 167   /// machine instruction's lexical scope in a given machine basic block.
 168   bool dominates(const DILocation *DL, MachineBasicBlock *MBB);
 169
 170   /// findLexicalScope - Find lexical scope, either regular or inlined, for the
 171   /// given DebugLoc. Return NULL if not found.
 172   LexicalScope *findLexicalScope(const DILocation *DL);
 173
 174   /// getAbstractScopesList - Return a reference to list of abstract scopes.
 175   ArrayRef<LexicalScope *> getAbstractScopesList() const {
 176     return AbstractScopesList;
 177   }
 178
 179   /// findAbstractScope - Find an abstract scope or return null.
 180   LexicalScope *findAbstractScope(const DILocalScope *N) {
 181     auto I = AbstractScopeMap.find(N);
 182     return I != AbstractScopeMap.end() ? &I->second : nullptr;
 183   }
 184
 185   /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
 186   LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) {
 187     auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
 188     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
 189   }
 190
 191   /// findLexicalScope - Find regular lexical scope or return null.
 192   LexicalScope *findLexicalScope(const DILocalScope *N) {
 193     auto I = LexicalScopeMap.find(N);
 194     return I != LexicalScopeMap.end() ? &I->second : nullptr;
 195   }
 196
 197   /// dump - Print data structures to dbgs().
 198   void dump() const;
 199
 200   /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
 201   LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope);
 202
 203 private:
 204   /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If
 205   /// not available then create new lexical scope.
 206   LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope,
 207                                         const DILocation *IA = nullptr);
 208   LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
 209     return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
 210               : nullptr;
 211   }
 212
 213   /// getOrCreateRegularScope - Find or create a regular lexical scope.
 214   LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope);
 215
 216   /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
 217   LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope,
 218                                         const DILocation *InlinedAt);
 219
 220   /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
 221   /// for the given machine function.
 222   void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
 223                             DenseMap<const MachineInstr *, LexicalScope *> &M);
 224   void constructScopeNest(LexicalScope *Scope);
 225   void
 226   assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
 227                           DenseMap<const MachineInstr *, LexicalScope *> &M);
 228
 229   const MachineFunction *MF = nullptr;
 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 = nullptr;
 253 };
 254
 255 } // end namespace llvm
 256
 257 #endif // LLVM_CODEGEN_LEXICALSCOPES_H