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