llvm/CodeGen/LexicalScopes.h

0001 //===- LexicalScopes.cpp - Collecting lexical scope info --------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file implements LexicalScopes analysis.
0010 //
0011 // This pass collects lexical scope information and maps machine instructions
0012 // to respective lexical scopes.
0013 //
0014 //===----------------------------------------------------------------------===//
0015
0016 #ifndef LLVM_CODEGEN_LEXICALSCOPES_H
0017 #define LLVM_CODEGEN_LEXICALSCOPES_H
0018
0019 #include "llvm/ADT/ArrayRef.h"
0020 #include "llvm/ADT/DenseMap.h"
0021 #include "llvm/ADT/SmallPtrSet.h"
0022 #include "llvm/ADT/SmallVector.h"
0023 #include "llvm/IR/DebugInfoMetadata.h"
0024 #include <cassert>
0025 #include <unordered_map>
0026 #include <utility>
0027
0028 namespace llvm {
0029
0030 class MachineBasicBlock;
0031 class MachineFunction;
0032 class MachineInstr;
0033 class MDNode;
0034
0035 //===----------------------------------------------------------------------===//
0036 /// InsnRange - This is used to track range of instructions with identical
0037 /// lexical scope.
0038 ///
0039 using InsnRange = std::pair<const MachineInstr *, const MachineInstr *>;
0040
0041 //===----------------------------------------------------------------------===//
0042 /// LexicalScope - This class is used to track scope information.
0043 ///
0044 class LexicalScope {
0045 public:
0046   LexicalScope(LexicalScope *P, const DILocalScope *D, const DILocation *I,
0047                bool A)
0048       : Parent(P), Desc(D), InlinedAtLocation(I), AbstractScope(A) {
0049     assert(D);
0050     assert(D->getSubprogram()->getUnit()->getEmissionKind() !=
0051            DICompileUnit::NoDebug &&
0052            "Don't build lexical scopes for non-debug locations");
0053     assert(D->isResolved() && "Expected resolved node");
0054     assert((!I || I->isResolved()) && "Expected resolved node");
0055     if (Parent)
0056       Parent->addChild(this);
0057   }
0058
0059   // Accessors.
0060   LexicalScope *getParent() const { return Parent; }
0061   const MDNode *getDesc() const { return Desc; }
0062   const DILocation *getInlinedAt() const { return InlinedAtLocation; }
0063   const DILocalScope *getScopeNode() const { return Desc; }
0064   bool isAbstractScope() const { return AbstractScope; }
0065   SmallVectorImpl<LexicalScope *> &getChildren() { return Children; }
0066   SmallVectorImpl<InsnRange> &getRanges() { return Ranges; }
0067
0068   /// addChild - Add a child scope.
0069   void addChild(LexicalScope *S) { Children.push_back(S); }
0070
0071   /// openInsnRange - This scope covers instruction range starting from MI.
0072   void openInsnRange(const MachineInstr *MI) {
0073     if (!FirstInsn)
0074       FirstInsn = MI;
0075
0076     if (Parent)
0077       Parent->openInsnRange(MI);
0078   }
0079
0080   /// extendInsnRange - Extend the current instruction range covered by
0081   /// this scope.
0082   void extendInsnRange(const MachineInstr *MI) {
0083     assert(FirstInsn && "MI Range is not open!");
0084     LastInsn = MI;
0085     if (Parent)
0086       Parent->extendInsnRange(MI);
0087   }
0088
0089   /// closeInsnRange - Create a range based on FirstInsn and LastInsn collected
0090   /// until now. This is used when a new scope is encountered while walking
0091   /// machine instructions.
0092   void closeInsnRange(LexicalScope *NewScope = nullptr) {
0093     assert(LastInsn && "Last insn missing!");
0094     Ranges.push_back(InsnRange(FirstInsn, LastInsn));
0095     FirstInsn = nullptr;
0096     LastInsn = nullptr;
0097     // If Parent dominates NewScope then do not close Parent's instruction
0098     // range.
0099     if (Parent && (!NewScope || !Parent->dominates(NewScope)))
0100       Parent->closeInsnRange(NewScope);
0101   }
0102
0103   /// dominates - Return true if current scope dominates given lexical scope.
0104   bool dominates(const LexicalScope *S) const {
0105     if (S == this)
0106       return true;
0107     if (DFSIn < S->getDFSIn() && DFSOut > S->getDFSOut())
0108       return true;
0109     return false;
0110   }
0111
0112   // Depth First Search support to walk and manipulate LexicalScope hierarchy.
0113   unsigned getDFSOut() const { return DFSOut; }
0114   void setDFSOut(unsigned O) { DFSOut = O; }
0115   unsigned getDFSIn() const { return DFSIn; }
0116   void setDFSIn(unsigned I) { DFSIn = I; }
0117
0118   /// dump - print lexical scope.
0119   void dump(unsigned Indent = 0) const;
0120
0121 private:
0122   LexicalScope *Parent;                        // Parent to this scope.
0123   const DILocalScope *Desc;                    // Debug info descriptor.
0124   const DILocation *InlinedAtLocation;         // Location at which this
0125                                                // scope is inlined.
0126   bool AbstractScope;                          // Abstract Scope
0127   SmallVector<LexicalScope *, 4> Children;     // Scopes defined in scope.
0128                                                // Contents not owned.
0129   SmallVector<InsnRange, 4> Ranges;
0130
0131   const MachineInstr *LastInsn = nullptr;  // Last instruction of this scope.
0132   const MachineInstr *FirstInsn = nullptr; // First instruction of this scope.
0133   unsigned DFSIn = 0; // In & Out Depth use to determine scope nesting.
0134   unsigned DFSOut = 0;
0135 };
0136
0137 //===----------------------------------------------------------------------===//
0138 /// LexicalScopes -  This class provides interface to collect and use lexical
0139 /// scoping information from machine instruction.
0140 ///
0141 class LexicalScopes {
0142 public:
0143   LexicalScopes() = default;
0144
0145   /// initialize - Scan machine function and constuct lexical scope nest, resets
0146   /// the instance if necessary.
0147   void initialize(const MachineFunction &);
0148
0149   /// releaseMemory - release memory.
0150   void reset();
0151
0152   /// empty - Return true if there is any lexical scope information available.
0153   bool empty() { return CurrentFnLexicalScope == nullptr; }
0154
0155   /// getCurrentFunctionScope - Return lexical scope for the current function.
0156   LexicalScope *getCurrentFunctionScope() const {
0157     return CurrentFnLexicalScope;
0158   }
0159
0160   /// getMachineBasicBlocks - Populate given set using machine basic blocks
0161   /// which have machine instructions that belong to lexical scope identified by
0162   /// DebugLoc.
0163   void getMachineBasicBlocks(const DILocation *DL,
0164                              SmallPtrSetImpl<const MachineBasicBlock *> &MBBs);
0165
0166   /// Return true if DebugLoc's lexical scope dominates at least one machine
0167   /// instruction's lexical scope in a given machine basic block.
0168   bool dominates(const DILocation *DL, MachineBasicBlock *MBB);
0169
0170   /// findLexicalScope - Find lexical scope, either regular or inlined, for the
0171   /// given DebugLoc. Return NULL if not found.
0172   LexicalScope *findLexicalScope(const DILocation *DL);
0173
0174   /// getAbstractScopesList - Return a reference to list of abstract scopes.
0175   ArrayRef<LexicalScope *> getAbstractScopesList() const {
0176     return AbstractScopesList;
0177   }
0178
0179   /// findAbstractScope - Find an abstract scope or return null.
0180   LexicalScope *findAbstractScope(const DILocalScope *N) {
0181     auto I = AbstractScopeMap.find(N);
0182     return I != AbstractScopeMap.end() ? &I->second : nullptr;
0183   }
0184
0185   /// findInlinedScope - Find an inlined scope for the given scope/inlined-at.
0186   LexicalScope *findInlinedScope(const DILocalScope *N, const DILocation *IA) {
0187     auto I = InlinedLexicalScopeMap.find(std::make_pair(N, IA));
0188     return I != InlinedLexicalScopeMap.end() ? &I->second : nullptr;
0189   }
0190
0191   /// findLexicalScope - Find regular lexical scope or return null.
0192   LexicalScope *findLexicalScope(const DILocalScope *N) {
0193     auto I = LexicalScopeMap.find(N);
0194     return I != LexicalScopeMap.end() ? &I->second : nullptr;
0195   }
0196
0197   /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
0198   LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope);
0199
0200 private:
0201   /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If
0202   /// not available then create new lexical scope.
0203   LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope,
0204                                         const DILocation *IA = nullptr);
0205   LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
0206     return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
0207               : nullptr;
0208   }
0209
0210   /// getOrCreateRegularScope - Find or create a regular lexical scope.
0211   LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope);
0212
0213   /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
0214   LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope,
0215                                         const DILocation *InlinedAt);
0216
0217   /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
0218   /// for the given machine function.
0219   void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
0220                             DenseMap<const MachineInstr *, LexicalScope *> &M);
0221   void constructScopeNest(LexicalScope *Scope);
0222   void
0223   assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
0224                           DenseMap<const MachineInstr *, LexicalScope *> &M);
0225
0226   const MachineFunction *MF = nullptr;
0227
0228   /// LexicalScopeMap - Tracks the scopes in the current function.
0229   // Use an unordered_map to ensure value pointer validity over insertion.
0230   std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap;
0231
0232   /// InlinedLexicalScopeMap - Tracks inlined function scopes in current
0233   /// function.
0234   std::unordered_map<std::pair<const DILocalScope *, const DILocation *>,
0235                      LexicalScope,
0236                      pair_hash<const DILocalScope *, const DILocation *>>
0237       InlinedLexicalScopeMap;
0238
0239   /// AbstractScopeMap - These scopes are  not included LexicalScopeMap.
0240   // Use an unordered_map to ensure value pointer validity over insertion.
0241   std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap;
0242
0243   /// AbstractScopesList - Tracks abstract scopes constructed while processing
0244   /// a function.
0245   SmallVector<LexicalScope *, 4> AbstractScopesList;
0246
0247   /// CurrentFnLexicalScope - Top level scope for the current function.
0248   ///
0249   LexicalScope *CurrentFnLexicalScope = nullptr;
0250
0251   /// Map a location to the set of basic blocks it dominates. This is a cache
0252   /// for \ref LexicalScopes::getMachineBasicBlocks results.
0253   using BlockSetT = SmallPtrSet<const MachineBasicBlock *, 4>;
0254   DenseMap<const DILocation *, std::unique_ptr<BlockSetT>> DominatedBlocks;
0255 };
0256
0257 } // end namespace llvm
0258
0259 #endif // LLVM_CODEGEN_LEXICALSCOPES_H