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   /// Return true if DebugLoc's lexical scope dominates at least one machine
167   /// 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   /// getOrCreateAbstractScope - Find or create an abstract lexical scope.
198   LexicalScope *getOrCreateAbstractScope(const DILocalScope *Scope);
199 
200 private:
201   /// getOrCreateLexicalScope - Find lexical scope for the given Scope/IA. If
202   /// not available then create new lexical scope.
203   LexicalScope *getOrCreateLexicalScope(const DILocalScope *Scope,
204                                         const DILocation *IA = nullptr);
205   LexicalScope *getOrCreateLexicalScope(const DILocation *DL) {
206     return DL ? getOrCreateLexicalScope(DL->getScope(), DL->getInlinedAt())
207               : nullptr;
208   }
209 
210   /// getOrCreateRegularScope - Find or create a regular lexical scope.
211   LexicalScope *getOrCreateRegularScope(const DILocalScope *Scope);
212 
213   /// getOrCreateInlinedScope - Find or create an inlined lexical scope.
214   LexicalScope *getOrCreateInlinedScope(const DILocalScope *Scope,
215                                         const DILocation *InlinedAt);
216 
217   /// extractLexicalScopes - Extract instruction ranges for each lexical scopes
218   /// for the given machine function.
219   void extractLexicalScopes(SmallVectorImpl<InsnRange> &MIRanges,
220                             DenseMap<const MachineInstr *, LexicalScope *> &M);
221   void constructScopeNest(LexicalScope *Scope);
222   void
223   assignInstructionRanges(SmallVectorImpl<InsnRange> &MIRanges,
224                           DenseMap<const MachineInstr *, LexicalScope *> &M);
225 
226   const MachineFunction *MF = nullptr;
227 
228   /// LexicalScopeMap - Tracks the scopes in the current function.
229   // Use an unordered_map to ensure value pointer validity over insertion.
230   std::unordered_map<const DILocalScope *, LexicalScope> LexicalScopeMap;
231 
232   /// InlinedLexicalScopeMap - Tracks inlined function scopes in current
233   /// function.
234   std::unordered_map<std::pair<const DILocalScope *, const DILocation *>,
235                      LexicalScope,
236                      pair_hash<const DILocalScope *, const DILocation *>>
237       InlinedLexicalScopeMap;
238 
239   /// AbstractScopeMap - These scopes are  not included LexicalScopeMap.
240   // Use an unordered_map to ensure value pointer validity over insertion.
241   std::unordered_map<const DILocalScope *, LexicalScope> AbstractScopeMap;
242 
243   /// AbstractScopesList - Tracks abstract scopes constructed while processing
244   /// a function.
245   SmallVector<LexicalScope *, 4> AbstractScopesList;
246 
247   /// CurrentFnLexicalScope - Top level scope for the current function.
248   ///
249   LexicalScope *CurrentFnLexicalScope = nullptr;
250 
251   /// Map a location to the set of basic blocks it dominates. This is a cache
252   /// for \ref LexicalScopes::getMachineBasicBlocks results.
253   using BlockSetT = SmallPtrSet<const MachineBasicBlock *, 4>;
254   DenseMap<const DILocation *, std::unique_ptr<BlockSetT>> DominatedBlocks;
255 };
256 
257 } // end namespace llvm
258 
259 #endif // LLVM_CODEGEN_LEXICALSCOPES_H
260