Coverage Report

Created: 2020-11-24 06:42

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