Coverage Report

Created: 2017-10-03 07:32

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