Coverage Report

Created: 2018-07-20 23:04

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/CFG.h
Line
Count
Source (jump to first uncovered line)
1
//===- CFG.h - Classes for representing and building CFGs -------*- 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 defines the CFG and CFGBuilder classes for representing and
11
//  building Control-Flow Graphs (CFGs) from ASTs.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_CLANG_ANALYSIS_CFG_H
16
#define LLVM_CLANG_ANALYSIS_CFG_H
17
18
#include "clang/AST/ExprCXX.h"
19
#include "clang/Analysis/Support/BumpVector.h"
20
#include "clang/Analysis/ConstructionContext.h"
21
#include "clang/Basic/LLVM.h"
22
#include "llvm/ADT/DenseMap.h"
23
#include "llvm/ADT/GraphTraits.h"
24
#include "llvm/ADT/None.h"
25
#include "llvm/ADT/Optional.h"
26
#include "llvm/ADT/PointerIntPair.h"
27
#include "llvm/ADT/iterator_range.h"
28
#include "llvm/Support/Allocator.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include <bitset>
31
#include <cassert>
32
#include <cstddef>
33
#include <iterator>
34
#include <memory>
35
#include <vector>
36
37
namespace clang {
38
39
class ASTContext;
40
class BinaryOperator;
41
class CFG;
42
class CXXBaseSpecifier;
43
class CXXBindTemporaryExpr;
44
class CXXCtorInitializer;
45
class CXXDeleteExpr;
46
class CXXDestructorDecl;
47
class CXXNewExpr;
48
class CXXRecordDecl;
49
class Decl;
50
class FieldDecl;
51
class LangOptions;
52
class VarDecl;
53
54
/// CFGElement - Represents a top-level expression in a basic block.
55
0
class CFGElement {
56
public:
57
  enum Kind {
58
    // main kind
59
    Initializer,
60
    ScopeBegin,
61
    ScopeEnd,
62
    NewAllocator,
63
    LifetimeEnds,
64
    LoopExit,
65
    // stmt kind
66
    Statement,
67
    Constructor,
68
    CXXRecordTypedCall,
69
    STMT_BEGIN = Statement,
70
    STMT_END = CXXRecordTypedCall,
71
    // dtor kind
72
    AutomaticObjectDtor,
73
    DeleteDtor,
74
    BaseDtor,
75
    MemberDtor,
76
    TemporaryDtor,
77
    DTOR_BEGIN = AutomaticObjectDtor,
78
    DTOR_END = TemporaryDtor
79
  };
80
81
protected:
82
  // The int bits are used to mark the kind.
83
  llvm::PointerIntPair<void *, 2> Data1;
84
  llvm::PointerIntPair<void *, 2> Data2;
85
86
  CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr)
87
      : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
88
9.66M
        Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
89
9.66M
    assert(getKind() == kind);
90
9.66M
  }
91
92
20.6M
  CFGElement() = default;
93
94
public:
95
  /// Convert to the specified CFGElement type, asserting that this
96
  /// CFGElement is of the desired type.
97
  template<typename T>
98
2.09M
  T castAs() const {
99
2.09M
    assert(T::isKind(*this));
100
2.09M
    T t;
101
2.09M
    CFGElement& e = t;
102
2.09M
    e = *this;
103
2.09M
    return t;
104
2.09M
  }
clang::CFGStmt clang::CFGElement::castAs<clang::CFGStmt>() const
Line
Count
Source
98
2.08M
  T castAs() const {
99
2.08M
    assert(T::isKind(*this));
100
2.08M
    T t;
101
2.08M
    CFGElement& e = t;
102
2.08M
    e = *this;
103
2.08M
    return t;
104
2.08M
  }
clang::CFGInitializer clang::CFGElement::castAs<clang::CFGInitializer>() const
Line
Count
Source
98
4.19k
  T castAs() const {
99
4.19k
    assert(T::isKind(*this));
100
4.19k
    T t;
101
4.19k
    CFGElement& e = t;
102
4.19k
    e = *this;
103
4.19k
    return t;
104
4.19k
  }
clang::CFGNewAllocator clang::CFGElement::castAs<clang::CFGNewAllocator>() const
Line
Count
Source
98
950
  T castAs() const {
99
950
    assert(T::isKind(*this));
100
950
    T t;
101
950
    CFGElement& e = t;
102
950
    e = *this;
103
950
    return t;
104
950
  }
clang::CFGImplicitDtor clang::CFGElement::castAs<clang::CFGImplicitDtor>() const
Line
Count
Source
98
1.28k
  T castAs() const {
99
1.28k
    assert(T::isKind(*this));
100
1.28k
    T t;
101
1.28k
    CFGElement& e = t;
102
1.28k
    e = *this;
103
1.28k
    return t;
104
1.28k
  }
clang::CFGLoopExit clang::CFGElement::castAs<clang::CFGLoopExit>() const
Line
Count
Source
98
141
  T castAs() const {
99
141
    assert(T::isKind(*this));
100
141
    T t;
101
141
    CFGElement& e = t;
102
141
    e = *this;
103
141
    return t;
104
141
  }
clang::CFGAutomaticObjDtor clang::CFGElement::castAs<clang::CFGAutomaticObjDtor>() const
Line
Count
Source
98
927
  T castAs() const {
99
927
    assert(T::isKind(*this));
100
927
    T t;
101
927
    CFGElement& e = t;
102
927
    e = *this;
103
927
    return t;
104
927
  }
clang::CFGBaseDtor clang::CFGElement::castAs<clang::CFGBaseDtor>() const
Line
Count
Source
98
100
  T castAs() const {
99
100
    assert(T::isKind(*this));
100
100
    T t;
101
100
    CFGElement& e = t;
102
100
    e = *this;
103
100
    return t;
104
100
  }
clang::CFGMemberDtor clang::CFGElement::castAs<clang::CFGMemberDtor>() const
Line
Count
Source
98
23
  T castAs() const {
99
23
    assert(T::isKind(*this));
100
23
    T t;
101
23
    CFGElement& e = t;
102
23
    e = *this;
103
23
    return t;
104
23
  }
clang::CFGTemporaryDtor clang::CFGElement::castAs<clang::CFGTemporaryDtor>() const
Line
Count
Source
98
730
  T castAs() const {
99
730
    assert(T::isKind(*this));
100
730
    T t;
101
730
    CFGElement& e = t;
102
730
    e = *this;
103
730
    return t;
104
730
  }
clang::CFGDeleteDtor clang::CFGElement::castAs<clang::CFGDeleteDtor>() const
Line
Count
Source
98
127
  T castAs() const {
99
127
    assert(T::isKind(*this));
100
127
    T t;
101
127
    CFGElement& e = t;
102
127
    e = *this;
103
127
    return t;
104
127
  }
105
106
  /// Convert to the specified CFGElement type, returning None if this
107
  /// CFGElement is not of the desired type.
108
  template<typename T>
109
18.8M
  Optional<T> getAs() const {
110
18.8M
    if (!T::isKind(*this))
111
363k
      return None;
112
18.5M
    T t;
113
18.5M
    CFGElement& e = t;
114
18.5M
    e = *this;
115
18.5M
    return t;
116
18.5M
  }
llvm::Optional<clang::CFGStmt> clang::CFGElement::getAs<clang::CFGStmt>() const
Line
Count
Source
109
18.5M
  Optional<T> getAs() const {
110
18.5M
    if (!T::isKind(*this))
111
59.4k
      return None;
112
18.5M
    T t;
113
18.5M
    CFGElement& e = t;
114
18.5M
    e = *this;
115
18.5M
    return t;
116
18.5M
  }
llvm::Optional<clang::CFGAutomaticObjDtor> clang::CFGElement::getAs<clang::CFGAutomaticObjDtor>() const
Line
Count
Source
109
261k
  Optional<T> getAs() const {
110
261k
    if (!T::isKind(*this))
111
260k
      return None;
112
1.45k
    T t;
113
1.45k
    CFGElement& e = t;
114
1.45k
    e = *this;
115
1.45k
    return t;
116
1.45k
  }
llvm::Optional<clang::CFGDeleteDtor> clang::CFGElement::getAs<clang::CFGDeleteDtor>() const
Line
Count
Source
109
604
  Optional<T> getAs() const {
110
604
    if (!T::isKind(*this))
111
549
      return None;
112
55
    T t;
113
55
    CFGElement& e = t;
114
55
    e = *this;
115
55
    return t;
116
55
  }
llvm::Optional<clang::CFGBaseDtor> clang::CFGElement::getAs<clang::CFGBaseDtor>() const
Line
Count
Source
109
969
  Optional<T> getAs() const {
110
969
    if (!T::isKind(*this))
111
877
      return None;
112
92
    T t;
113
92
    CFGElement& e = t;
114
92
    e = *this;
115
92
    return t;
116
92
  }
llvm::Optional<clang::CFGCXXRecordTypedCall> clang::CFGElement::getAs<clang::CFGCXXRecordTypedCall>() const
Line
Count
Source
109
28.5k
  Optional<T> getAs() const {
110
28.5k
    if (!T::isKind(*this))
111
28.0k
      return None;
112
507
    T t;
113
507
    CFGElement& e = t;
114
507
    e = *this;
115
507
    return t;
116
507
  }
llvm::Optional<clang::CFGConstructor> clang::CFGElement::getAs<clang::CFGConstructor>() const
Line
Count
Source
109
19.7k
  Optional<T> getAs() const {
110
19.7k
    if (!T::isKind(*this))
111
10.6k
      return None;
112
9.10k
    T t;
113
9.10k
    CFGElement& e = t;
114
9.10k
    e = *this;
115
9.10k
    return t;
116
9.10k
  }
llvm::Optional<clang::CFGNewAllocator> clang::CFGElement::getAs<clang::CFGNewAllocator>() const
Line
Count
Source
109
384
  Optional<T> getAs() const {
110
384
    if (!T::isKind(*this))
111
333
      return None;
112
51
    T t;
113
51
    CFGElement& e = t;
114
51
    e = *this;
115
51
    return t;
116
51
  }
llvm::Optional<clang::CFGInitializer> clang::CFGElement::getAs<clang::CFGInitializer>() const
Line
Count
Source
109
1.23k
  Optional<T> getAs() const {
110
1.23k
    if (!T::isKind(*this))
111
1.16k
      return None;
112
72
    T t;
113
72
    CFGElement& e = t;
114
72
    e = *this;
115
72
    return t;
116
72
  }
llvm::Optional<clang::CFGLifetimeEnds> clang::CFGElement::getAs<clang::CFGLifetimeEnds>() const
Line
Count
Source
109
602
  Optional<T> getAs() const {
110
602
    if (!T::isKind(*this))
111
520
      return None;
112
82
    T t;
113
82
    CFGElement& e = t;
114
82
    e = *this;
115
82
    return t;
116
82
  }
llvm::Optional<clang::CFGLoopExit> clang::CFGElement::getAs<clang::CFGLoopExit>() const
Line
Count
Source
109
520
  Optional<T> getAs() const {
110
520
    if (!T::isKind(*this))
111
507
      return None;
112
13
    T t;
113
13
    CFGElement& e = t;
114
13
    e = *this;
115
13
    return t;
116
13
  }
llvm::Optional<clang::CFGScopeBegin> clang::CFGElement::getAs<clang::CFGScopeBegin>() const
Line
Count
Source
109
507
  Optional<T> getAs() const {
110
507
    if (!T::isKind(*this))
111
461
      return None;
112
46
    T t;
113
46
    CFGElement& e = t;
114
46
    e = *this;
115
46
    return t;
116
46
  }
llvm::Optional<clang::CFGScopeEnd> clang::CFGElement::getAs<clang::CFGScopeEnd>() const
Line
Count
Source
109
461
  Optional<T> getAs() const {
110
461
    if (!T::isKind(*this))
111
383
      return None;
112
78
    T t;
113
78
    CFGElement& e = t;
114
78
    e = *this;
115
78
    return t;
116
78
  }
llvm::Optional<clang::CFGMemberDtor> clang::CFGElement::getAs<clang::CFGMemberDtor>() const
Line
Count
Source
109
324
  Optional<T> getAs() const {
110
324
    if (!T::isKind(*this))
111
322
      return None;
112
2
    T t;
113
2
    CFGElement& e = t;
114
2
    e = *this;
115
2
    return t;
116
2
  }
llvm::Optional<clang::CFGTemporaryDtor> clang::CFGElement::getAs<clang::CFGTemporaryDtor>() const
Line
Count
Source
109
322
  Optional<T> getAs() const {
110
322
    if (!T::isKind(*this))
111
0
      return None;
112
322
    T t;
113
322
    CFGElement& e = t;
114
322
    e = *this;
115
322
    return t;
116
322
  }
117
118
44.8M
  Kind getKind() const {
119
44.8M
    unsigned x = Data2.getInt();
120
44.8M
    x <<= 2;
121
44.8M
    x |= Data1.getInt();
122
44.8M
    return (Kind) x;
123
44.8M
  }
124
};
125
126
class CFGStmt : public CFGElement {
127
public:
128
9.56M
  explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) {
129
9.56M
    assert(isKind(*this));
130
9.56M
  }
131
132
20.0M
  const Stmt *getStmt() const {
133
20.0M
    return static_cast<const Stmt *>(Data1.getPointer());
134
20.0M
  }
135
136
private:
137
  friend class CFGElement;
138
139
18.5M
  static bool isKind(const CFGElement &E) {
140
18.5M
    return E.getKind() >= STMT_BEGIN && 
E.getKind() <= STMT_END18.5M
;
141
18.5M
  }
142
143
protected:
144
20.6M
  CFGStmt() = default;
145
};
146
147
/// CFGConstructor - Represents C++ constructor call. Maintains information
148
/// necessary to figure out what memory is being initialized by the
149
/// constructor expression. For now this is only used by the analyzer's CFG.
150
class CFGConstructor : public CFGStmt {
151
public:
152
  explicit CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C)
153
7.96k
      : CFGStmt(CE, Constructor) {
154
7.96k
    assert(C);
155
7.96k
    Data2.setPointer(const_cast<ConstructionContext *>(C));
156
7.96k
  }
157
158
9.10k
  const ConstructionContext *getConstructionContext() const {
159
9.10k
    return static_cast<ConstructionContext *>(Data2.getPointer());
160
9.10k
  }
161
162
private:
163
  friend class CFGElement;
164
165
9.10k
  CFGConstructor() = default;
166
167
19.7k
  static bool isKind(const CFGElement &E) {
168
19.7k
    return E.getKind() == Constructor;
169
19.7k
  }
170
};
171
172
/// CFGCXXRecordTypedCall - Represents a function call that returns a C++ object
173
/// by value. This, like constructor, requires a construction context in order
174
/// to understand the storage of the returned object . In C such tracking is not
175
/// necessary because no additional effort is required for destroying the object
176
/// or modeling copy elision. Like CFGConstructor, this element is for now only
177
/// used by the analyzer's CFG.
178
class CFGCXXRecordTypedCall : public CFGStmt {
179
public:
180
  /// Returns true when call expression \p CE needs to be represented
181
  /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt.
182
41.6k
  static bool isCXXRecordTypedCall(CallExpr *CE, const ASTContext &ACtx) {
183
41.6k
    return CE->getCallReturnType(ACtx).getCanonicalType()->getAsCXXRecordDecl();
184
41.6k
  }
185
186
  explicit CFGCXXRecordTypedCall(CallExpr *CE, const ConstructionContext *C)
187
860
      : CFGStmt(CE, CXXRecordTypedCall) {
188
860
    // FIXME: This is not protected against squeezing a non-record-typed-call
189
860
    // into the constructor. An assertion would require passing an ASTContext
190
860
    // which would mean paying for something we don't use.
191
860
    assert(C && (isa<TemporaryObjectConstructionContext>(C) ||
192
860
                 // These are possible in C++17 due to mandatory copy elision.
193
860
                 isa<ReturnedValueConstructionContext>(C) ||
194
860
                 isa<VariableConstructionContext>(C) ||
195
860
                 isa<ConstructorInitializerConstructionContext>(C)));
196
860
    Data2.setPointer(const_cast<ConstructionContext *>(C));
197
860
  }
198
199
507
  const ConstructionContext *getConstructionContext() const {
200
507
    return static_cast<ConstructionContext *>(Data2.getPointer());
201
507
  }
202
203
private:
204
  friend class CFGElement;
205
206
507
  CFGCXXRecordTypedCall() = default;
207
208
28.5k
  static bool isKind(const CFGElement &E) {
209
28.5k
    return E.getKind() == CXXRecordTypedCall;
210
28.5k
  }
211
};
212
213
/// CFGInitializer - Represents C++ base or member initializer from
214
/// constructor's initialization list.
215
class CFGInitializer : public CFGElement {
216
public:
217
  explicit CFGInitializer(CXXCtorInitializer *initializer)
218
72.5k
      : CFGElement(Initializer, initializer) {}
219
220
4.26k
  CXXCtorInitializer* getInitializer() const {
221
4.26k
    return static_cast<CXXCtorInitializer*>(Data1.getPointer());
222
4.26k
  }
223
224
private:
225
  friend class CFGElement;
226
227
4.26k
  CFGInitializer() = default;
228
229
1.23k
  static bool isKind(const CFGElement &E) {
230
1.23k
    return E.getKind() == Initializer;
231
1.23k
  }
232
};
233
234
/// CFGNewAllocator - Represents C++ allocator call.
235
class CFGNewAllocator : public CFGElement {
236
public:
237
  explicit CFGNewAllocator(const CXXNewExpr *S)
238
1.49k
    : CFGElement(NewAllocator, S) {}
239
240
  // Get the new expression.
241
1.00k
  const CXXNewExpr *getAllocatorExpr() const {
242
1.00k
    return static_cast<CXXNewExpr *>(Data1.getPointer());
243
1.00k
  }
244
245
private:
246
  friend class CFGElement;
247
248
1.00k
  CFGNewAllocator() = default;
249
250
384
  static bool isKind(const CFGElement &elem) {
251
384
    return elem.getKind() == NewAllocator;
252
384
  }
253
};
254
255
/// Represents the point where a loop ends.
256
/// This element is is only produced when building the CFG for the static
257
/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
258
///
259
/// Note: a loop exit element can be reached even when the loop body was never
260
/// entered.
261
class CFGLoopExit : public CFGElement {
262
public:
263
238
  explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
264
265
154
  const Stmt *getLoopStmt() const {
266
154
    return static_cast<Stmt *>(Data1.getPointer());
267
154
  }
268
269
private:
270
  friend class CFGElement;
271
272
154
  CFGLoopExit() = default;
273
274
520
  static bool isKind(const CFGElement &elem) {
275
520
    return elem.getKind() == LoopExit;
276
520
  }
277
};
278
279
/// Represents the point where the lifetime of an automatic object ends
280
class CFGLifetimeEnds : public CFGElement {
281
public:
282
  explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
283
166
      : CFGElement(LifetimeEnds, var, stmt) {}
284
285
82
  const VarDecl *getVarDecl() const {
286
82
    return static_cast<VarDecl *>(Data1.getPointer());
287
82
  }
288
289
0
  const Stmt *getTriggerStmt() const {
290
0
    return static_cast<Stmt *>(Data2.getPointer());
291
0
  }
292
293
private:
294
  friend class CFGElement;
295
296
82
  CFGLifetimeEnds() = default;
297
298
602
  static bool isKind(const CFGElement &elem) {
299
602
    return elem.getKind() == LifetimeEnds;
300
602
  }
301
};
302
303
/// Represents beginning of a scope implicitly generated
304
/// by the compiler on encountering a CompoundStmt
305
class CFGScopeBegin : public CFGElement {
306
public:
307
46
  CFGScopeBegin() {}
308
  CFGScopeBegin(const VarDecl *VD, const Stmt *S)
309
92
      : CFGElement(ScopeBegin, VD, S) {}
310
311
  // Get statement that triggered a new scope.
312
0
  const Stmt *getTriggerStmt() const {
313
0
    return static_cast<Stmt*>(Data2.getPointer());
314
0
  }
315
316
  // Get VD that triggered a new scope.
317
46
  const VarDecl *getVarDecl() const {
318
46
    return static_cast<VarDecl *>(Data1.getPointer());
319
46
  }
320
321
private:
322
  friend class CFGElement;
323
507
  static bool isKind(const CFGElement &E) {
324
507
    Kind kind = E.getKind();
325
507
    return kind == ScopeBegin;
326
507
  }
327
};
328
329
/// Represents end of a scope implicitly generated by
330
/// the compiler after the last Stmt in a CompoundStmt's body
331
class CFGScopeEnd : public CFGElement {
332
public:
333
78
  CFGScopeEnd() {}
334
158
  CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {}
335
336
78
  const VarDecl *getVarDecl() const {
337
78
    return static_cast<VarDecl *>(Data1.getPointer());
338
78
  }
339
340
0
  const Stmt *getTriggerStmt() const {
341
0
    return static_cast<Stmt *>(Data2.getPointer());
342
0
  }
343
344
private:
345
  friend class CFGElement;
346
461
  static bool isKind(const CFGElement &E) {
347
461
    Kind kind = E.getKind();
348
461
    return kind == ScopeEnd;
349
461
  }
350
};
351
352
/// CFGImplicitDtor - Represents C++ object destructor implicitly generated
353
/// by compiler on various occasions.
354
class CFGImplicitDtor : public CFGElement {
355
protected:
356
5.11k
  CFGImplicitDtor() = default;
357
358
  CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr)
359
27.8k
    : CFGElement(kind, data1, data2) {
360
27.8k
    assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
361
27.8k
  }
362
363
public:
364
  const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
365
  bool isNoReturn(ASTContext &astContext) const;
366
367
private:
368
  friend class CFGElement;
369
370
0
  static bool isKind(const CFGElement &E) {
371
0
    Kind kind = E.getKind();
372
0
    return kind >= DTOR_BEGIN && kind <= DTOR_END;
373
0
  }
374
};
375
376
/// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated
377
/// for automatic object or temporary bound to const reference at the point
378
/// of leaving its local scope.
379
class CFGAutomaticObjDtor: public CFGImplicitDtor {
380
public:
381
  CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
382
21.2k
      : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
383
384
1.96k
  const VarDecl *getVarDecl() const {
385
1.96k
    return static_cast<VarDecl*>(Data1.getPointer());
386
1.96k
  }
387
388
  // Get statement end of which triggered the destructor call.
389
1.05k
  const Stmt *getTriggerStmt() const {
390
1.05k
    return static_cast<Stmt*>(Data2.getPointer());
391
1.05k
  }
392
393
private:
394
  friend class CFGElement;
395
396
2.38k
  CFGAutomaticObjDtor() = default;
397
398
261k
  static bool isKind(const CFGElement &elem) {
399
261k
    return elem.getKind() == AutomaticObjectDtor;
400
261k
  }
401
};
402
403
/// CFGDeleteDtor - Represents C++ object destructor generated
404
/// from a call to delete.
405
class CFGDeleteDtor : public CFGImplicitDtor {
406
public:
407
  CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)
408
250
      : CFGImplicitDtor(DeleteDtor, RD, DE) {}
409
410
4
  const CXXRecordDecl *getCXXRecordDecl() const {
411
4
    return static_cast<CXXRecordDecl*>(Data1.getPointer());
412
4
  }
413
414
  // Get Delete expression which triggered the destructor call.
415
182
  const CXXDeleteExpr *getDeleteExpr() const {
416
182
    return static_cast<CXXDeleteExpr *>(Data2.getPointer());
417
182
  }
418
419
private:
420
  friend class CFGElement;
421
422
182
  CFGDeleteDtor() = default;
423
424
604
  static bool isKind(const CFGElement &elem) {
425
604
    return elem.getKind() == DeleteDtor;
426
604
  }
427
};
428
429
/// CFGBaseDtor - Represents C++ object destructor implicitly generated for
430
/// base object in destructor.
431
class CFGBaseDtor : public CFGImplicitDtor {
432
public:
433
  CFGBaseDtor(const CXXBaseSpecifier *base)
434
333
      : CFGImplicitDtor(BaseDtor, base) {}
435
436
105
  const CXXBaseSpecifier *getBaseSpecifier() const {
437
105
    return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
438
105
  }
439
440
private:
441
  friend class CFGElement;
442
443
192
  CFGBaseDtor() = default;
444
445
969
  static bool isKind(const CFGElement &E) {
446
969
    return E.getKind() == BaseDtor;
447
969
  }
448
};
449
450
/// CFGMemberDtor - Represents C++ object destructor implicitly generated for
451
/// member object in destructor.
452
class CFGMemberDtor : public CFGImplicitDtor {
453
public:
454
  CFGMemberDtor(const FieldDecl *field)
455
477
      : CFGImplicitDtor(MemberDtor, field, nullptr) {}
456
457
25
  const FieldDecl *getFieldDecl() const {
458
25
    return static_cast<const FieldDecl*>(Data1.getPointer());
459
25
  }
460
461
private:
462
  friend class CFGElement;
463
464
25
  CFGMemberDtor() = default;
465
466
324
  static bool isKind(const CFGElement &E) {
467
324
    return E.getKind() == MemberDtor;
468
324
  }
469
};
470
471
/// CFGTemporaryDtor - Represents C++ object destructor implicitly generated
472
/// at the end of full expression for temporary object.
473
class CFGTemporaryDtor : public CFGImplicitDtor {
474
public:
475
  CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
476
5.51k
      : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}
477
478
3.42k
  const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
479
3.42k
    return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
480
3.42k
  }
481
482
private:
483
  friend class CFGElement;
484
485
1.05k
  CFGTemporaryDtor() = default;
486
487
322
  static bool isKind(const CFGElement &E) {
488
322
    return E.getKind() == TemporaryDtor;
489
322
  }
490
};
491
492
/// CFGTerminator - Represents CFGBlock terminator statement.
493
///
494
/// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
495
/// in control flow of destructors of temporaries. In this case terminator
496
/// statement is the same statement that branches control flow in evaluation
497
/// of matching full expression.
498
0
class CFGTerminator {
499
  llvm::PointerIntPair<Stmt *, 1> Data;
500
501
public:
502
  CFGTerminator() = default;
503
  CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
504
2.54M
      : Data(S, TemporaryDtorsBranch) {}
505
506
14.6k
  Stmt *getStmt() { return Data.getPointer(); }
507
652k
  const Stmt *getStmt() const { return Data.getPointer(); }
508
509
669
  bool isTemporaryDtorsBranch() const { return Data.getInt(); }
510
511
12.9k
  operator Stmt *() { return getStmt(); }
512
257k
  operator const Stmt *() const { return getStmt(); }
513
514
0
  Stmt *operator->() { return getStmt(); }
515
0
  const Stmt *operator->() const { return getStmt(); }
516
517
0
  Stmt &operator*() { return *getStmt(); }
518
0
  const Stmt &operator*() const { return *getStmt(); }
519
520
39.0k
  explicit operator bool() const { return getStmt(); }
521
};
522
523
/// CFGBlock - Represents a single basic block in a source-level CFG.
524
///  It consists of:
525
///
526
///  (1) A set of statements/expressions (which may contain subexpressions).
527
///  (2) A "terminator" statement (not in the set of statements).
528
///  (3) A list of successors and predecessors.
529
///
530
/// Terminator: The terminator represents the type of control-flow that occurs
531
/// at the end of the basic block.  The terminator is a Stmt* referring to an
532
/// AST node that has control-flow: if-statements, breaks, loops, etc.
533
/// If the control-flow is conditional, the condition expression will appear
534
/// within the set of statements in the block (usually the last statement).
535
///
536
/// Predecessors: the order in the set of predecessors is arbitrary.
537
///
538
/// Successors: the order in the set of successors is NOT arbitrary.  We
539
///  currently have the following orderings based on the terminator:
540
///
541
///     Terminator       Successor Ordering
542
///  -----------------------------------------------------
543
///       if            Then Block;  Else Block
544
///     ? operator      LHS expression;  RHS expression
545
///     &&, ||          expression that uses result of && or ||, RHS
546
///
547
/// But note that any of that may be NULL in case of optimized-out edges.
548
class CFGBlock {
549
  class ElementList {
550
    using ImplTy = BumpVector<CFGElement>;
551
552
    ImplTy Impl;
553
554
  public:
555
2.11M
    ElementList(BumpVectorContext &C) : Impl(C, 4) {}
556
557
    using iterator = std::reverse_iterator<ImplTy::iterator>;
558
    using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
559
    using reverse_iterator = ImplTy::iterator;
560
    using const_reverse_iterator = ImplTy::const_iterator;
561
    using const_reference = ImplTy::const_reference;
562
563
9.66M
    void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
564
565
    reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
566
98
        BumpVectorContext &C) {
567
98
      return Impl.insert(I, Cnt, E, C);
568
98
    }
569
570
85.9k
    const_reference front() const { return Impl.back(); }
571
45.0k
    const_reference back() const { return Impl.front(); }
572
573
1.68M
    iterator begin() { return Impl.rbegin(); }
574
1.68M
    iterator end() { return Impl.rend(); }
575
806k
    const_iterator begin() const { return Impl.rbegin(); }
576
806k
    const_iterator end() const { return Impl.rend(); }
577
0
    reverse_iterator rbegin() { return Impl.begin(); }
578
0
    reverse_iterator rend() { return Impl.end(); }
579
347k
    const_reverse_iterator rbegin() const { return Impl.begin(); }
580
346k
    const_reverse_iterator rend() const { return Impl.end(); }
581
582
2.19M
    CFGElement operator[](size_t i) const  {
583
2.19M
      assert(i < Impl.size());
584
2.19M
      return Impl[Impl.size() - 1 - i];
585
2.19M
    }
586
587
765k
    size_t size() const { return Impl.size(); }
588
147k
    bool empty() const { return Impl.empty(); }
589
  };
590
591
  /// Stmts - The set of statements in the basic block.
592
  ElementList Elements;
593
594
  /// Label - An (optional) label that prefixes the executable
595
  ///  statements in the block.  When this variable is non-NULL, it is
596
  ///  either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
597
  Stmt *Label = nullptr;
598
599
  /// Terminator - The terminator for a basic block that
600
  ///  indicates the type of control-flow that occurs between a block
601
  ///  and its successors.
602
  CFGTerminator Terminator;
603
604
  /// LoopTarget - Some blocks are used to represent the "loop edge" to
605
  ///  the start of a loop from within the loop body.  This Stmt* will be
606
  ///  refer to the loop statement for such blocks (and be null otherwise).
607
  const Stmt *LoopTarget = nullptr;
608
609
  /// BlockID - A numerical ID assigned to a CFGBlock during construction
610
  ///   of the CFG.
611
  unsigned BlockID;
612
613
public:
614
  /// This class represents a potential adjacent block in the CFG.  It encodes
615
  /// whether or not the block is actually reachable, or can be proved to be
616
  /// trivially unreachable.  For some cases it allows one to encode scenarios
617
  /// where a block was substituted because the original (now alternate) block
618
  /// is unreachable.
619
  class AdjacentBlock {
620
    enum Kind {
621
      AB_Normal,
622
      AB_Unreachable,
623
      AB_Alternate
624
    };
625
626
    CFGBlock *ReachableBlock;
627
    llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
628
629
  public:
630
    /// Construct an AdjacentBlock with a possibly unreachable block.
631
    AdjacentBlock(CFGBlock *B, bool IsReachable);
632
    
633
    /// Construct an AdjacentBlock with a reachable block and an alternate
634
    /// unreachable block.
635
    AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock);
636
637
    /// Get the reachable block, if one exists.
638
9.15M
    CFGBlock *getReachableBlock() const {
639
9.15M
      return ReachableBlock;
640
9.15M
    }
641
642
    /// Get the potentially unreachable block.
643
2.29M
    CFGBlock *getPossiblyUnreachableBlock() const {
644
2.29M
      return UnreachableBlock.getPointer();
645
2.29M
    }
646
647
    /// Provide an implicit conversion to CFGBlock* so that
648
    /// AdjacentBlock can be substituted for CFGBlock*.
649
6.94M
    operator CFGBlock*() const {
650
6.94M
      return getReachableBlock();
651
6.94M
    }
652
653
0
    CFGBlock& operator *() const {
654
0
      return *getReachableBlock();
655
0
    }
656
657
17.3k
    CFGBlock* operator ->() const {
658
17.3k
      return getReachableBlock();
659
17.3k
    }
660
661
2.02M
    bool isReachable() const {
662
2.02M
      Kind K = (Kind) UnreachableBlock.getInt();
663
2.02M
      return K == AB_Normal || 
K == AB_Alternate2.63k
;
664
2.02M
    }
665
  };
666
667
private:
668
  /// Predecessors/Successors - Keep track of the predecessor / successor
669
  /// CFG blocks.
670
  using AdjacentBlocks = BumpVector<AdjacentBlock>;
671
  AdjacentBlocks Preds;
672
  AdjacentBlocks Succs;
673
674
  /// NoReturn - This bit is set when the basic block contains a function call
675
  /// or implicit destructor that is attributed as 'noreturn'. In that case,
676
  /// control cannot technically ever proceed past this block. All such blocks
677
  /// will have a single immediate successor: the exit block. This allows them
678
  /// to be easily reached from the exit block and using this bit quickly
679
  /// recognized without scanning the contents of the block.
680
  ///
681
  /// Optimization Note: This bit could be profitably folded with Terminator's
682
  /// storage if the memory usage of CFGBlock becomes an issue.
683
  unsigned HasNoReturnElement : 1;
684
685
  /// Parent - The parent CFG that owns this CFGBlock.
686
  CFG *Parent;
687
688
public:
689
  explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
690
      : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
691
2.11M
        Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
692
693
  // Statement iterators
694
  using iterator = ElementList::iterator;
695
  using const_iterator = ElementList::const_iterator;
696
  using reverse_iterator = ElementList::reverse_iterator;
697
  using const_reverse_iterator = ElementList::const_reverse_iterator;
698
699
85.9k
  CFGElement                 front()       const { return Elements.front();   }
700
45.0k
  CFGElement                 back()        const { return Elements.back();    }
701
702
1.68M
  iterator                   begin()             { return Elements.begin();   }
703
1.68M
  iterator                   end()               { return Elements.end();     }
704
806k
  const_iterator             begin()       const { return Elements.begin();   }
705
806k
  const_iterator             end()         const { return Elements.end();     }
706
707
0
  reverse_iterator           rbegin()            { return Elements.rbegin();  }
708
0
  reverse_iterator           rend()              { return Elements.rend();    }
709
347k
  const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
710
346k
  const_reverse_iterator     rend()        const { return Elements.rend();    }
711
712
765k
  unsigned                   size()        const { return Elements.size();    }
713
147k
  bool                       empty()       const { return Elements.empty();   }
714
715
2.19M
  CFGElement operator[](size_t i) const  { return Elements[i]; }
716
717
  // CFG iterators
718
  using pred_iterator = AdjacentBlocks::iterator;
719
  using const_pred_iterator = AdjacentBlocks::const_iterator;
720
  using pred_reverse_iterator = AdjacentBlocks::reverse_iterator;
721
  using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
722
  using pred_range = llvm::iterator_range<pred_iterator>;
723
  using pred_const_range = llvm::iterator_range<const_pred_iterator>;
724
725
  using succ_iterator = AdjacentBlocks::iterator;
726
  using const_succ_iterator = AdjacentBlocks::const_iterator;
727
  using succ_reverse_iterator = AdjacentBlocks::reverse_iterator;
728
  using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
729
  using succ_range = llvm::iterator_range<succ_iterator>;
730
  using succ_const_range = llvm::iterator_range<const_succ_iterator>;
731
732
0
  pred_iterator                pred_begin()        { return Preds.begin();   }
733
0
  pred_iterator                pred_end()          { return Preds.end();     }
734
1.29M
  const_pred_iterator          pred_begin()  const { return Preds.begin();   }
735
1.29M
  const_pred_iterator          pred_end()    const { return Preds.end();     }
736
737
  pred_reverse_iterator        pred_rbegin()       { return Preds.rbegin();  }
738
  pred_reverse_iterator        pred_rend()         { return Preds.rend();    }
739
  const_pred_reverse_iterator  pred_rbegin() const { return Preds.rbegin();  }
740
  const_pred_reverse_iterator  pred_rend()   const { return Preds.rend();    }
741
742
  pred_range preds() {
743
    return pred_range(pred_begin(), pred_end());
744
  }
745
746
  pred_const_range preds() const {
747
    return pred_const_range(pred_begin(), pred_end());
748
  }
749
750
871k
  succ_iterator                succ_begin()        { return Succs.begin();   }
751
871k
  succ_iterator                succ_end()          { return Succs.end();     }
752
3.08M
  const_succ_iterator          succ_begin()  const { return Succs.begin();   }
753
3.97M
  const_succ_iterator          succ_end()    const { return Succs.end();     }
754
755
0
  succ_reverse_iterator        succ_rbegin()       { return Succs.rbegin();  }
756
0
  succ_reverse_iterator        succ_rend()         { return Succs.rend();    }
757
227
  const_succ_reverse_iterator  succ_rbegin() const { return Succs.rbegin();  }
758
137
  const_succ_reverse_iterator  succ_rend()   const { return Succs.rend();    }
759
760
138
  succ_range succs() {
761
138
    return succ_range(succ_begin(), succ_end());
762
138
  }
763
764
419
  succ_const_range succs() const {
765
419
    return succ_const_range(succ_begin(), succ_end());
766
419
  }
767
768
7.98k
  unsigned                     succ_size()   const { return Succs.size();    }
769
2.85k
  bool                         succ_empty()  const { return Succs.empty();   }
770
771
6.42k
  unsigned                     pred_size()   const { return Preds.size();    }
772
17.1k
  bool                         pred_empty()  const { return Preds.empty();   }
773
774
775
  class FilterOptions {
776
  public:
777
    unsigned IgnoreNullPredecessors : 1;
778
    unsigned IgnoreDefaultsWithCoveredEnums : 1;
779
780
    FilterOptions()
781
223k
        : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
782
  };
783
784
  static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
785
       const CFGBlock *Dst);
786
787
  template <typename IMPL, bool IsPred>
788
  class FilteredCFGBlockIterator {
789
  private:
790
    IMPL I, E;
791
    const FilterOptions F;
792
    const CFGBlock *From;
793
794
  public:
795
    explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
796
                                      const CFGBlock *from,
797
                                      const FilterOptions &f)
798
223k
        : I(i), E(e), F(f), From(from) {
799
223k
      while (hasMore() && 
Filter(*I)223k
)
800
1
        ++I;
801
223k
    }
802
803
1.15M
    bool hasMore() const { return I != E; }
804
805
354k
    FilteredCFGBlockIterator &operator++() {
806
358k
      do { ++I; } while (hasMore() && 
Filter(*I)135k
);
807
354k
      return *this;
808
354k
    }
809
810
354k
    const CFGBlock *operator*() const { return *I; }
811
812
  private:
813
358k
    bool Filter(const CFGBlock *To) {
814
358k
      return IsPred ? FilterEdge(F, To, From) : 
FilterEdge(F, From, To)0
;
815
358k
    }
816
  };
817
818
  using filtered_pred_iterator =
819
      FilteredCFGBlockIterator<const_pred_iterator, true>;
820
821
  using filtered_succ_iterator =
822
      FilteredCFGBlockIterator<const_succ_iterator, false>;
823
824
223k
  filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
825
223k
    return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
826
223k
  }
827
828
  filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
829
    return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
830
  }
831
832
  // Manipulation of block contents
833
834
439k
  void setTerminator(CFGTerminator Term) { Terminator = Term; }
835
73.4k
  void setLabel(Stmt *Statement) { Label = Statement; }
836
98.3k
  void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
837
55.9k
  void setHasNoReturnElement() { HasNoReturnElement = true; }
838
839
7.17k
  CFGTerminator getTerminator() { return Terminator; }
840
654k
  const CFGTerminator getTerminator() const { return Terminator; }
841
842
  Stmt *getTerminatorCondition(bool StripParens = true);
843
844
5.82k
  const Stmt *getTerminatorCondition(bool StripParens = true) const {
845
5.82k
    return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
846
5.82k
  }
847
848
1.73k
  const Stmt *getLoopTarget() const { return LoopTarget; }
849
850
2.16k
  Stmt *getLabel() { return Label; }
851
4.96k
  const Stmt *getLabel() const { return Label; }
852
853
656k
  bool hasNoReturnElement() const { return HasNoReturnElement; }
854
855
14.5M
  unsigned getBlockID() const { return BlockID; }
856
857
0
  CFG *getParent() const { return Parent; }
858
859
  void dump() const;
860
861
  void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
862
  void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
863
             bool ShowColors) const;
864
  void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
865
0
  void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
866
0
    OS << "BB#" << getBlockID();
867
0
  }
868
869
  /// Adds a (potentially unreachable) successor block to the current block.
870
  void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
871
872
9.55M
  void appendStmt(Stmt *statement, BumpVectorContext &C) {
873
9.55M
    Elements.push_back(CFGStmt(statement), C);
874
9.55M
  }
875
876
  void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC,
877
7.96k
                         BumpVectorContext &C) {
878
7.96k
    Elements.push_back(CFGConstructor(CE, CC), C);
879
7.96k
  }
880
881
  void appendCXXRecordTypedCall(CallExpr *CE,
882
                                const ConstructionContext *CC,
883
860
                                BumpVectorContext &C) {
884
860
    Elements.push_back(CFGCXXRecordTypedCall(CE, CC), C);
885
860
  }
886
887
  void appendInitializer(CXXCtorInitializer *initializer,
888
72.5k
                        BumpVectorContext &C) {
889
72.5k
    Elements.push_back(CFGInitializer(initializer), C);
890
72.5k
  }
891
892
  void appendNewAllocator(CXXNewExpr *NE,
893
1.49k
                          BumpVectorContext &C) {
894
1.49k
    Elements.push_back(CFGNewAllocator(NE), C);
895
1.49k
  }
896
897
  void appendScopeBegin(const VarDecl *VD, const Stmt *S,
898
92
                        BumpVectorContext &C) {
899
92
    Elements.push_back(CFGScopeBegin(VD, S), C);
900
92
  }
901
902
  void prependScopeBegin(const VarDecl *VD, const Stmt *S,
903
0
                         BumpVectorContext &C) {
904
0
    Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
905
0
  }
906
907
154
  void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
908
154
    Elements.push_back(CFGScopeEnd(VD, S), C);
909
154
  }
910
911
0
  void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
912
0
    Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
913
0
  }
914
915
333
  void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
916
333
    Elements.push_back(CFGBaseDtor(BS), C);
917
333
  }
918
919
477
  void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
920
477
    Elements.push_back(CFGMemberDtor(FD), C);
921
477
  }
922
923
5.51k
  void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
924
5.51k
    Elements.push_back(CFGTemporaryDtor(E), C);
925
5.51k
  }
926
927
21.1k
  void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
928
21.1k
    Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
929
21.1k
  }
930
931
162
  void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
932
162
    Elements.push_back(CFGLifetimeEnds(VD, S), C);
933
162
  }
934
935
238
  void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
936
238
    Elements.push_back(CFGLoopExit(LoopStmt), C);
937
238
  }
938
939
250
  void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
940
250
    Elements.push_back(CFGDeleteDtor(RD, DE), C);
941
250
  }
942
943
  // Destructors must be inserted in reversed order. So insertion is in two
944
  // steps. First we prepare space for some number of elements, then we insert
945
  // the elements beginning at the last position in prepared space.
946
  iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
947
94
      BumpVectorContext &C) {
948
94
    return iterator(Elements.insert(I.base(), Cnt,
949
94
                                    CFGAutomaticObjDtor(nullptr, nullptr), C));
950
94
  }
951
23
  iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) {
952
23
    *I = CFGAutomaticObjDtor(VD, S);
953
23
    return ++I;
954
23
  }
955
956
  // Scope leaving must be performed in reversed order. So insertion is in two
957
  // steps. First we prepare space for some number of elements, then we insert
958
  // the elements beginning at the last position in prepared space.
959
  iterator beginLifetimeEndsInsert(iterator I, size_t Cnt,
960
2
                                   BumpVectorContext &C) {
961
2
    return iterator(
962
2
        Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
963
2
  }
964
2
  iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) {
965
2
    *I = CFGLifetimeEnds(VD, S);
966
2
    return ++I;
967
2
  }
968
969
  // Scope leaving must be performed in reversed order. So insertion is in two
970
  // steps. First we prepare space for some number of elements, then we insert
971
  // the elements beginning at the last position in prepared space.
972
2
  iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) {
973
2
    return iterator(
974
2
        Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
975
2
  }
976
2
  iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) {
977
2
    *I = CFGScopeEnd(VD, S);
978
2
    return ++I;
979
2
  }
980
981
};
982
983
/// CFGCallback defines methods that should be called when a logical
984
/// operator error is found when building the CFG.
985
class CFGCallback {
986
public:
987
42
  CFGCallback() = default;
988
42
  virtual ~CFGCallback() = default;
989
990
0
  virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
991
  virtual void compareBitwiseEquality(const BinaryOperator *B,
992
0
                                      bool isAlwaysTrue) {}
993
};
994
995
/// CFG - Represents a source-level, intra-procedural CFG that represents the
996
///  control-flow of a Stmt.  The Stmt can represent an entire function body,
997
///  or a single expression.  A CFG will always contain one empty block that
998
///  represents the Exit point of the CFG.  A CFG will also contain a designated
999
///  Entry block.  The CFG solely represents control-flow; it consists of
1000
///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
1001
///  was constructed from.
1002
class CFG {
1003
public:
1004
  //===--------------------------------------------------------------------===//
1005
  // CFG Construction & Manipulation.
1006
  //===--------------------------------------------------------------------===//
1007
1008
  class BuildOptions {
1009
    std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
1010
1011
  public:
1012
    using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
1013
1014
    ForcedBlkExprs **forcedBlkExprs = nullptr;
1015
    CFGCallback *Observer = nullptr;
1016
    bool PruneTriviallyFalseEdges = true;
1017
    bool AddEHEdges = false;
1018
    bool AddInitializers = false;
1019
    bool AddImplicitDtors = false;
1020
    bool AddLifetime = false;
1021
    bool AddLoopExit = false;
1022
    bool AddTemporaryDtors = false;
1023
    bool AddScopes = false;
1024
    bool AddStaticInitBranches = false;
1025
    bool AddCXXNewAllocator = false;
1026
    bool AddCXXDefaultInitExprInCtors = false;
1027
    bool AddRichCXXConstructors = false;
1028
    bool MarkElidedCXXConstructors = false;
1029
1030
439k
    BuildOptions() = default;
1031
1032
19.9M
    bool alwaysAdd(const Stmt *stmt) const {
1033
19.9M
      return alwaysAddMask[stmt->getStmtClass()];
1034
19.9M
    }
1035
1036
3.49M
    BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
1037
3.49M
      alwaysAddMask[stmtClass] = val;
1038
3.49M
      return *this;
1039
3.49M
    }
1040
1041
2.86k
    BuildOptions &setAllAlwaysAdd() {
1042
2.86k
      alwaysAddMask.set();
1043
2.86k
      return *this;
1044
2.86k
    }
1045
  };
1046
1047
  /// buildCFG - Builds a CFG from an AST.
1048
  static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
1049
                                       const BuildOptions &BO);
1050
1051
  /// createBlock - Create a new block in the CFG.  The CFG owns the block;
1052
  ///  the caller should not directly free it.
1053
  CFGBlock *createBlock();
1054
1055
  /// setEntry - Set the entry block of the CFG.  This is typically used
1056
  ///  only during CFG construction.  Most CFG clients expect that the
1057
  ///  entry block has no predecessors and contains no statements.
1058
412k
  void setEntry(CFGBlock *B) { Entry = B; }
1059
1060
  /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
1061
  ///  This is typically used only during CFG construction.
1062
14
  void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
1063
1064
  //===--------------------------------------------------------------------===//
1065
  // Block Iterators
1066
  //===--------------------------------------------------------------------===//
1067
1068
  using CFGBlockListTy = BumpVector<CFGBlock *>;
1069
  using iterator = CFGBlockListTy::iterator;
1070
  using const_iterator = CFGBlockListTy::const_iterator;
1071
  using reverse_iterator = std::reverse_iterator<iterator>;
1072
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1073
1074
  CFGBlock &                front()                { return *Blocks.front(); }
1075
2.52M
  CFGBlock &                back()                 { return *Blocks.back(); }
1076
1077
2.17M
  iterator                  begin()                { return Blocks.begin(); }
1078
2.17M
  iterator                  end()                  { return Blocks.end(); }
1079
93.1k
  const_iterator            begin()       const    { return Blocks.begin(); }
1080
93.2k
  const_iterator            end()         const    { return Blocks.end(); }
1081
1082
  iterator nodes_begin() { return iterator(Blocks.begin()); }
1083
  iterator nodes_end() { return iterator(Blocks.end()); }
1084
  const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
1085
  const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
1086
1087
64
  reverse_iterator          rbegin()               { return Blocks.rbegin(); }
1088
64
  reverse_iterator          rend()                 { return Blocks.rend(); }
1089
0
  const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
1090
0
  const_reverse_iterator    rend()        const    { return Blocks.rend(); }
1091
1092
566k
  CFGBlock &                getEntry()             { return *Entry; }
1093
425k
  const CFGBlock &          getEntry()    const    { return *Entry; }
1094
1.11M
  CFGBlock &                getExit()              { return *Exit; }
1095
5.55k
  const CFGBlock &          getExit()     const    { return *Exit; }
1096
1097
412k
  CFGBlock *       getIndirectGotoBlock() { return IndirectGotoBlock; }
1098
1.60k
  const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
1099
1100
  using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1101
1102
105
  try_block_iterator try_blocks_begin() const {
1103
105
    return TryDispatchBlocks.begin();
1104
105
  }
1105
1106
105
  try_block_iterator try_blocks_end() const {
1107
105
    return TryDispatchBlocks.end();
1108
105
  }
1109
1110
231
  void addTryDispatchBlock(const CFGBlock *block) {
1111
231
    TryDispatchBlocks.push_back(block);
1112
231
  }
1113
1114
  /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
1115
  ///
1116
  /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
1117
  /// multiple decls.
1118
  void addSyntheticDeclStmt(const DeclStmt *Synthetic,
1119
12.5k
                            const DeclStmt *Source) {
1120
12.5k
    assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
1121
12.5k
    assert(Synthetic != Source && "Don't include original DeclStmts in map");
1122
12.5k
    assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
1123
12.5k
    SyntheticDeclStmts[Synthetic] = Source;
1124
12.5k
  }
1125
1126
  using synthetic_stmt_iterator =
1127
      llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
1128
  using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
1129
1130
  /// Iterates over synthetic DeclStmts in the CFG.
1131
  ///
1132
  /// Each element is a (synthetic statement, source statement) pair.
1133
  ///
1134
  /// \sa addSyntheticDeclStmt
1135
14.2k
  synthetic_stmt_iterator synthetic_stmt_begin() const {
1136
14.2k
    return SyntheticDeclStmts.begin();
1137
14.2k
  }
1138
1139
  /// \sa synthetic_stmt_begin
1140
14.2k
  synthetic_stmt_iterator synthetic_stmt_end() const {
1141
14.2k
    return SyntheticDeclStmts.end();
1142
14.2k
  }
1143
1144
  /// \sa synthetic_stmt_begin
1145
  synthetic_stmt_range synthetic_stmts() const {
1146
    return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
1147
  }
1148
1149
  //===--------------------------------------------------------------------===//
1150
  // Member templates useful for various batch operations over CFGs.
1151
  //===--------------------------------------------------------------------===//
1152
1153
  template <typename CALLBACK>
1154
91.4k
  void VisitBlockStmts(CALLBACK& O) const {
1155
1.00M
    for (const_iterator I=begin(), E=end(); I != E; 
++I910k
)
1156
910k
      for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
1157
6.87M
           BI != BE; 
++BI5.96M
) {
1158
5.96M
        if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1159
5.94M
          O(const_cast<Stmt*>(stmt->getStmt()));
1160
5.96M
      }
1161
91.4k
  }
DeadStoresChecker.cpp:void clang::CFG::VisitBlockStmts<(anonymous namespace)::FindEscaped>((anonymous namespace)::FindEscaped&) const
Line
Count
Source
1154
435
  void VisitBlockStmts(CALLBACK& O) const {
1155
2.61k
    for (const_iterator I=begin(), E=end(); I != E; 
++I2.18k
)
1156
2.18k
      for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
1157
9.97k
           BI != BE; 
++BI7.79k
) {
1158
7.79k
        if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1159
7.78k
          O(const_cast<Stmt*>(stmt->getStmt()));
1160
7.79k
      }
1161
435
  }
UninitializedValues.cpp:void clang::CFG::VisitBlockStmts<(anonymous namespace)::ClassifyRefs>((anonymous namespace)::ClassifyRefs&) const
Line
Count
Source
1154
90.9k
  void VisitBlockStmts(CALLBACK& O) const {
1155
999k
    for (const_iterator I=begin(), E=end(); I != E; 
++I908k
)
1156
908k
      for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
1157
6.86M
           BI != BE; 
++BI5.95M
) {
1158
5.95M
        if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1159
5.94M
          O(const_cast<Stmt*>(stmt->getStmt()));
1160
5.95M
      }
1161
90.9k
  }
1162
1163
  //===--------------------------------------------------------------------===//
1164
  // CFG Introspection.
1165
  //===--------------------------------------------------------------------===//
1166
1167
  /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
1168
  /// start at 0).
1169
1.64M
  unsigned getNumBlockIDs() const { return NumBlockIDs; }
1170
1171
  /// size - Return the total number of CFGBlocks within the CFG
1172
  /// This is simply a renaming of the getNumBlockIDs(). This is necessary 
1173
  /// because the dominator implementation needs such an interface.
1174
23.0k
  unsigned size() const { return NumBlockIDs; }
1175
1176
  //===--------------------------------------------------------------------===//
1177
  // CFG Debugging: Pretty-Printing and Visualization.
1178
  //===--------------------------------------------------------------------===//
1179
1180
  void viewCFG(const LangOptions &LO) const;
1181
  void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1182
  void dump(const LangOptions &LO, bool ShowColors) const;
1183
1184
  //===--------------------------------------------------------------------===//
1185
  // Internal: constructors and data.
1186
  //===--------------------------------------------------------------------===//
1187
1188
412k
  CFG() : Blocks(BlkBVC, 10) {}
1189
1190
2.13M
  llvm::BumpPtrAllocator& getAllocator() {
1191
2.13M
    return BlkBVC.getAllocator();
1192
2.13M
  }
1193
1194
13.8M
  BumpVectorContext &getBumpVectorContext() {
1195
13.8M
    return BlkBVC;
1196
13.8M
  }
1197
1198
private:
1199
  CFGBlock *Entry = nullptr;
1200
  CFGBlock *Exit = nullptr;
1201
1202
  // Special block to contain collective dispatch for indirect gotos
1203
  CFGBlock* IndirectGotoBlock = nullptr;
1204
1205
  unsigned  NumBlockIDs = 0;
1206
1207
  BumpVectorContext BlkBVC;
1208
1209
  CFGBlockListTy Blocks;
1210
1211
  /// C++ 'try' statements are modeled with an indirect dispatch block.
1212
  /// This is the collection of such blocks present in the CFG.
1213
  std::vector<const CFGBlock *> TryDispatchBlocks;
1214
1215
  /// Collects DeclStmts synthesized for this CFG and maps each one back to its
1216
  /// source DeclStmt.
1217
  llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
1218
};
1219
1220
} // namespace clang
1221
1222
//===----------------------------------------------------------------------===//
1223
// GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1224
//===----------------------------------------------------------------------===//
1225
1226
namespace llvm {
1227
1228
/// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1229
/// CFGTerminator to a specific Stmt class.
1230
template <> struct simplify_type< ::clang::CFGTerminator> {
1231
  using SimpleType = ::clang::Stmt *;
1232
1233
443
  static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
1234
443
    return Val.getStmt();
1235
443
  }
1236
};
1237
1238
// Traits for: CFGBlock
1239
1240
template <> struct GraphTraits< ::clang::CFGBlock *> {
1241
  using NodeRef = ::clang::CFGBlock *;
1242
  using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
1243
1244
  static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1245
52
  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1246
52
  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1247
};
1248
1249
template <> struct GraphTraits< const ::clang::CFGBlock *> {
1250
  using NodeRef = const ::clang::CFGBlock *;
1251
  using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
1252
1253
  static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1254
857k
  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1255
1.91M
  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1256
};
1257
1258
template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1259
  using NodeRef = ::clang::CFGBlock *;
1260
  using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1261
1262
  static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1263
    return G.Graph;
1264
  }
1265
1266
  static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1267
  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1268
};
1269
1270
template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1271
  using NodeRef = const ::clang::CFGBlock *;
1272
  using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1273
1274
  static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1275
    return G.Graph;
1276
  }
1277
1278
  static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1279
  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1280
};
1281
1282
// Traits for: CFG
1283
1284
template <> struct GraphTraits< ::clang::CFG* >
1285
    : public GraphTraits< ::clang::CFGBlock *>  {
1286
  using nodes_iterator = ::clang::CFG::iterator;
1287
1288
5
  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1289
  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1290
  static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1291
  static unsigned              size(::clang::CFG* F) { return F->size(); }
1292
};
1293
1294
template <> struct GraphTraits<const ::clang::CFG* >
1295
    : public GraphTraits<const ::clang::CFGBlock *>  {
1296
  using nodes_iterator = ::clang::CFG::const_iterator;
1297
1298
107k
  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1299
1300
  static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1301
    return F->nodes_begin();
1302
  }
1303
1304
  static nodes_iterator nodes_end( const ::clang::CFG* F) {
1305
    return F->nodes_end();
1306
  }
1307
1308
  static unsigned size(const ::clang::CFG* F) {
1309
    return F->size();
1310
  }
1311
};
1312
1313
template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1314
  : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1315
  using nodes_iterator = ::clang::CFG::iterator;
1316
1317
  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1318
  static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1319
  static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1320
};
1321
1322
template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1323
  : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1324
  using nodes_iterator = ::clang::CFG::const_iterator;
1325
1326
  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1327
1328
  static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1329
    return F->nodes_begin();
1330
  }
1331
1332
  static nodes_iterator nodes_end(const ::clang::CFG* F) {
1333
    return F->nodes_end();
1334
  }
1335
};
1336
1337
} // namespace llvm
1338
1339
#endif // LLVM_CLANG_ANALYSIS_CFG_H