Coverage Report

Created: 2023-11-11 10:31

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