Coverage Report

Created: 2019-07-24 05:18

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