Coverage Report

Created: 2018-11-16 02:38

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