Coverage Report

Created: 2021-09-21 08:58

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/CFG.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CFG.cpp - Classes for representing and building CFGs ---------------===//
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
#include "clang/Analysis/CFG.h"
15
#include "clang/AST/ASTContext.h"
16
#include "clang/AST/Attr.h"
17
#include "clang/AST/Decl.h"
18
#include "clang/AST/DeclBase.h"
19
#include "clang/AST/DeclCXX.h"
20
#include "clang/AST/DeclGroup.h"
21
#include "clang/AST/Expr.h"
22
#include "clang/AST/ExprCXX.h"
23
#include "clang/AST/OperationKinds.h"
24
#include "clang/AST/PrettyPrinter.h"
25
#include "clang/AST/Stmt.h"
26
#include "clang/AST/StmtCXX.h"
27
#include "clang/AST/StmtObjC.h"
28
#include "clang/AST/StmtVisitor.h"
29
#include "clang/AST/Type.h"
30
#include "clang/Analysis/ConstructionContext.h"
31
#include "clang/Analysis/Support/BumpVector.h"
32
#include "clang/Basic/Builtins.h"
33
#include "clang/Basic/ExceptionSpecificationType.h"
34
#include "clang/Basic/JsonSupport.h"
35
#include "clang/Basic/LLVM.h"
36
#include "clang/Basic/LangOptions.h"
37
#include "clang/Basic/SourceLocation.h"
38
#include "clang/Basic/Specifiers.h"
39
#include "llvm/ADT/APInt.h"
40
#include "llvm/ADT/APSInt.h"
41
#include "llvm/ADT/ArrayRef.h"
42
#include "llvm/ADT/DenseMap.h"
43
#include "llvm/ADT/Optional.h"
44
#include "llvm/ADT/STLExtras.h"
45
#include "llvm/ADT/SetVector.h"
46
#include "llvm/ADT/SmallPtrSet.h"
47
#include "llvm/ADT/SmallVector.h"
48
#include "llvm/Support/Allocator.h"
49
#include "llvm/Support/Casting.h"
50
#include "llvm/Support/Compiler.h"
51
#include "llvm/Support/DOTGraphTraits.h"
52
#include "llvm/Support/ErrorHandling.h"
53
#include "llvm/Support/Format.h"
54
#include "llvm/Support/GraphWriter.h"
55
#include "llvm/Support/SaveAndRestore.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include <cassert>
58
#include <memory>
59
#include <string>
60
#include <tuple>
61
#include <utility>
62
#include <vector>
63
64
using namespace clang;
65
66
9.71k
static SourceLocation GetEndLoc(Decl *D) {
67
9.71k
  if (VarDecl *VD = dyn_cast<VarDecl>(D))
68
8.99k
    if (Expr *Ex = VD->getInit())
69
4.79k
      return Ex->getSourceRange().getEnd();
70
4.92k
  return D->getLocation();
71
9.71k
}
72
73
/// Returns true on constant values based around a single IntegerLiteral.
74
/// Allow for use of parentheses, integer casts, and negative signs.
75
4.17k
static bool IsIntegerLiteralConstantExpr(const Expr *E) {
76
  // Allow parentheses
77
4.17k
  E = E->IgnoreParens();
78
79
  // Allow conversions to different integer kind.
80
4.17k
  if (const auto *CE = dyn_cast<CastExpr>(E)) {
81
3.19k
    if (CE->getCastKind() != CK_IntegralCast)
82
316
      return false;
83
2.87k
    E = CE->getSubExpr();
84
2.87k
  }
85
86
  // Allow negative numbers.
87
3.85k
  if (const auto *UO = dyn_cast<UnaryOperator>(E)) {
88
71
    if (UO->getOpcode() != UO_Minus)
89
4
      return false;
90
67
    E = UO->getSubExpr();
91
67
  }
92
93
3.85k
  return isa<IntegerLiteral>(E);
94
3.85k
}
95
96
/// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral
97
/// constant expression or EnumConstantDecl from the given Expr. If it fails,
98
/// returns nullptr.
99
4.17k
static const Expr *tryTransformToIntOrEnumConstant(const Expr *E) {
100
4.17k
  E = E->IgnoreParens();
101
4.17k
  if (IsIntegerLiteralConstantExpr(E))
102
3.62k
    return E;
103
544
  if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()))
104
317
    return isa<EnumConstantDecl>(DR->getDecl()) ? 
DR46
:
nullptr271
;
105
227
  return nullptr;
106
544
}
107
108
/// Tries to interpret a binary operator into `Expr Op NumExpr` form, if
109
/// NumExpr is an integer literal or an enum constant.
110
///
111
/// If this fails, at least one of the returned DeclRefExpr or Expr will be
112
/// null.
113
static std::tuple<const Expr *, BinaryOperatorKind, const Expr *>
114
3.86k
tryNormalizeBinaryOperator(const BinaryOperator *B) {
115
3.86k
  BinaryOperatorKind Op = B->getOpcode();
116
117
3.86k
  const Expr *MaybeDecl = B->getLHS();
118
3.86k
  const Expr *Constant = tryTransformToIntOrEnumConstant(B->getRHS());
119
  // Expr looked like `0 == Foo` instead of `Foo == 0`
120
3.86k
  if (Constant == nullptr) {
121
    // Flip the operator
122
257
    if (Op == BO_GT)
123
53
      Op = BO_LT;
124
204
    else if (Op == BO_GE)
125
14
      Op = BO_LE;
126
190
    else if (Op == BO_LT)
127
25
      Op = BO_GT;
128
165
    else if (Op == BO_LE)
129
38
      Op = BO_GE;
130
131
257
    MaybeDecl = B->getRHS();
132
257
    Constant = tryTransformToIntOrEnumConstant(B->getLHS());
133
257
  }
134
135
3.86k
  return std::make_tuple(MaybeDecl, Op, Constant);
136
3.86k
}
137
138
/// For an expression `x == Foo && x == Bar`, this determines whether the
139
/// `Foo` and `Bar` are either of the same enumeration type, or both integer
140
/// literals.
141
///
142
/// It's an error to pass this arguments that are not either IntegerLiterals
143
/// or DeclRefExprs (that have decls of type EnumConstantDecl)
144
1.65k
static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {
145
  // User intent isn't clear if they're mixing int literals with enum
146
  // constants.
147
1.65k
  if (isa<DeclRefExpr>(E1) != isa<DeclRefExpr>(E2))
148
8
    return false;
149
150
  // Integer literal comparisons, regardless of literal type, are acceptable.
151
1.64k
  if (!isa<DeclRefExpr>(E1))
152
1.63k
    return true;
153
154
  // IntegerLiterals are handled above and only EnumConstantDecls are expected
155
  // beyond this point
156
16
  assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));
157
0
  auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl();
158
16
  auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl();
159
160
16
  assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));
161
0
  const DeclContext *DC1 = Decl1->getDeclContext();
162
16
  const DeclContext *DC2 = Decl2->getDeclContext();
163
164
16
  assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));
165
0
  return DC1 == DC2;
166
1.64k
}
167
168
namespace {
169
170
class CFGBuilder;
171
172
/// The CFG builder uses a recursive algorithm to build the CFG.  When
173
///  we process an expression, sometimes we know that we must add the
174
///  subexpressions as block-level expressions.  For example:
175
///
176
///    exp1 || exp2
177
///
178
///  When processing the '||' expression, we know that exp1 and exp2
179
///  need to be added as block-level expressions, even though they
180
///  might not normally need to be.  AddStmtChoice records this
181
///  contextual information.  If AddStmtChoice is 'NotAlwaysAdd', then
182
///  the builder has an option not to add a subexpression as a
183
///  block-level expression.
184
class AddStmtChoice {
185
public:
186
  enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
187
188
5.38M
  AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
189
190
  bool alwaysAdd(CFGBuilder &builder,
191
                 const Stmt *stmt) const;
192
193
  /// Return a copy of this object, except with the 'always-add' bit
194
  ///  set as specified.
195
18.1k
  AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
196
18.1k
    return AddStmtChoice(alwaysAdd ? 
AlwaysAdd11.5k
:
NotAlwaysAdd6.55k
);
197
18.1k
  }
198
199
private:
200
  Kind kind;
201
};
202
203
/// LocalScope - Node in tree of local scopes created for C++ implicit
204
/// destructor calls generation. It contains list of automatic variables
205
/// declared in the scope and link to position in previous scope this scope
206
/// began in.
207
///
208
/// The process of creating local scopes is as follows:
209
/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
210
/// - Before processing statements in scope (e.g. CompoundStmt) create
211
///   LocalScope object using CFGBuilder::ScopePos as link to previous scope
212
///   and set CFGBuilder::ScopePos to the end of new scope,
213
/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
214
///   at this VarDecl,
215
/// - For every normal (without jump) end of scope add to CFGBlock destructors
216
///   for objects in the current scope,
217
/// - For every jump add to CFGBlock destructors for objects
218
///   between CFGBuilder::ScopePos and local scope position saved for jump
219
///   target. Thanks to C++ restrictions on goto jumps we can be sure that
220
///   jump target position will be on the path to root from CFGBuilder::ScopePos
221
///   (adding any variable that doesn't need constructor to be called to
222
///   LocalScope can break this assumption),
223
///
224
class LocalScope {
225
public:
226
  using AutomaticVarsTy = BumpVector<VarDecl *>;
227
228
  /// const_iterator - Iterates local scope backwards and jumps to previous
229
  /// scope on reaching the beginning of currently iterated scope.
230
  class const_iterator {
231
    const LocalScope* Scope = nullptr;
232
233
    /// VarIter is guaranteed to be greater then 0 for every valid iterator.
234
    /// Invalid iterator (with null Scope) has VarIter equal to 0.
235
    unsigned VarIter = 0;
236
237
  public:
238
    /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
239
    /// Incrementing invalid iterator is allowed and will result in invalid
240
    /// iterator.
241
1.51M
    const_iterator() = default;
242
243
    /// Create valid iterator. In case when S.Prev is an invalid iterator and
244
    /// I is equal to 0, this will create invalid iterator.
245
    const_iterator(const LocalScope& S, unsigned I)
246
4.90k
        : Scope(&S), VarIter(I) {
247
      // Iterator to "end" of scope is not allowed. Handle it by going up
248
      // in scopes tree possibly up to invalid iterator in the root.
249
4.90k
      if (VarIter == 0 && 
Scope0
)
250
0
        *this = Scope->Prev;
251
4.90k
    }
252
253
13.3k
    VarDecl *const* operator->() const {
254
13.3k
      assert(Scope && "Dereferencing invalid iterator is not allowed");
255
0
      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
256
0
      return &Scope->Vars[VarIter - 1];
257
13.3k
    }
258
259
7.55k
    const VarDecl *getFirstVarInScope() const {
260
7.55k
      assert(Scope && "Dereferencing invalid iterator is not allowed");
261
0
      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
262
0
      return Scope->Vars[0];
263
7.55k
    }
264
265
13.3k
    VarDecl *operator*() const {
266
13.3k
      return *this->operator->();
267
13.3k
    }
268
269
10.5k
    const_iterator &operator++() {
270
10.5k
      if (!Scope)
271
0
        return *this;
272
273
10.5k
      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
274
0
      --VarIter;
275
10.5k
      if (VarIter == 0)
276
7.18k
        *this = Scope->Prev;
277
10.5k
      return *this;
278
10.5k
    }
279
0
    const_iterator operator++(int) {
280
0
      const_iterator P = *this;
281
0
      ++*this;
282
0
      return P;
283
0
    }
284
285
954k
    bool operator==(const const_iterator &rhs) const {
286
954k
      return Scope == rhs.Scope && 
VarIter == rhs.VarIter925k
;
287
954k
    }
288
363k
    bool operator!=(const const_iterator &rhs) const {
289
363k
      return !(*this == rhs);
290
363k
    }
291
292
349k
    explicit operator bool() const {
293
349k
      return *this != const_iterator();
294
349k
    }
295
296
    int distance(const_iterator L);
297
    const_iterator shared_parent(const_iterator L);
298
202
    bool pointsToFirstDeclaredVar() { return VarIter == 1; }
299
  };
300
301
private:
302
  BumpVectorContext ctx;
303
304
  /// Automatic variables in order of declaration.
305
  AutomaticVarsTy Vars;
306
307
  /// Iterator to variable in previous scope that was declared just before
308
  /// begin of this scope.
309
  const_iterator Prev;
310
311
public:
312
  /// Constructs empty scope linked to previous scope in specified place.
313
  LocalScope(BumpVectorContext ctx, const_iterator P)
314
3.28k
      : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}
315
316
  /// Begin of scope in direction of CFG building (backwards).
317
4.90k
  const_iterator begin() const { return const_iterator(*this, Vars.size()); }
318
319
4.90k
  void addVar(VarDecl *VD) {
320
4.90k
    Vars.push_back(VD, ctx);
321
4.90k
  }
322
};
323
324
} // namespace
325
326
/// distance - Calculates distance from this to L. L must be reachable from this
327
/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
328
/// number of scopes between this and L.
329
3.80k
int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
330
3.80k
  int D = 0;
331
3.80k
  const_iterator F = *this;
332
7.78k
  while (F.Scope != L.Scope) {
333
3.97k
    assert(F != const_iterator() &&
334
3.97k
           "L iterator is not reachable from F iterator.");
335
0
    D += F.VarIter;
336
3.97k
    F = F.Scope->Prev;
337
3.97k
  }
338
3.80k
  D += F.VarIter - L.VarIter;
339
3.80k
  return D;
340
3.80k
}
341
342
/// Calculates the closest parent of this iterator
343
/// that is in a scope reachable through the parents of L.
344
/// I.e. when using 'goto' from this to L, the lifetime of all variables
345
/// between this and shared_parent(L) end.
346
LocalScope::const_iterator
347
222
LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
348
222
  llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL;
349
422
  while (true) {
350
422
    ScopesOfL.insert(L.Scope);
351
422
    if (L == const_iterator())
352
222
      break;
353
200
    L = L.Scope->Prev;
354
200
  }
355
356
222
  const_iterator F = *this;
357
498
  while (true) {
358
498
    if (ScopesOfL.count(F.Scope))
359
222
      return F;
360
276
    assert(F != const_iterator() &&
361
276
           "L iterator is not reachable from F iterator.");
362
0
    F = F.Scope->Prev;
363
276
  }
364
222
}
365
366
namespace {
367
368
/// Structure for specifying position in CFG during its build process. It
369
/// consists of CFGBlock that specifies position in CFG and
370
/// LocalScope::const_iterator that specifies position in LocalScope graph.
371
struct BlockScopePosPair {
372
  CFGBlock *block = nullptr;
373
  LocalScope::const_iterator scopePosition;
374
375
734k
  BlockScopePosPair() = default;
376
  BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
377
55.9k
      : block(b), scopePosition(scopePos) {}
378
};
379
380
/// TryResult - a class representing a variant over the values
381
///  'true', 'false', or 'unknown'.  This is returned by tryEvaluateBool,
382
///  and is used by the CFGBuilder to decide if a branch condition
383
///  can be decided up front during CFG construction.
384
class TryResult {
385
  int X = -1;
386
387
public:
388
524k
  TryResult() = default;
389
67.7k
  TryResult(bool b) : X(b ? 1 : 0) {}
390
391
205k
  bool isTrue() const { return X == 1; }
392
174k
  bool isFalse() const { return X == 0; }
393
196k
  bool isKnown() const { return X >= 0; }
394
395
37
  void negate() {
396
37
    assert(isKnown());
397
0
    X ^= 0x1;
398
37
  }
399
};
400
401
} // namespace
402
403
1.61k
static TryResult bothKnownTrue(TryResult R1, TryResult R2) {
404
1.61k
  if (!R1.isKnown() || 
!R2.isKnown()1.49k
)
405
1.02k
    return TryResult();
406
594
  return TryResult(R1.isTrue() && R2.isTrue());
407
1.61k
}
408
409
namespace {
410
411
class reverse_children {
412
  llvm::SmallVector<Stmt *, 12> childrenBuf;
413
  ArrayRef<Stmt *> children;
414
415
public:
416
  reverse_children(Stmt *S);
417
418
  using iterator = ArrayRef<Stmt *>::reverse_iterator;
419
420
2.34M
  iterator begin() const { return children.rbegin(); }
421
2.34M
  iterator end() const { return children.rend(); }
422
};
423
424
} // namespace
425
426
2.34M
reverse_children::reverse_children(Stmt *S) {
427
2.34M
  if (CallExpr *CE = dyn_cast<CallExpr>(S)) {
428
314k
    children = CE->getRawSubExprs();
429
314k
    return;
430
314k
  }
431
2.03M
  switch (S->getStmtClass()) {
432
    // Note: Fill in this switch with more cases we want to optimize.
433
6.95k
    case Stmt::InitListExprClass: {
434
6.95k
      InitListExpr *IE = cast<InitListExpr>(S);
435
6.95k
      children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()),
436
6.95k
                                    IE->getNumInits());
437
6.95k
      return;
438
0
    }
439
2.02M
    default:
440
2.02M
      break;
441
2.03M
  }
442
443
  // Default case for all other statements.
444
2.02M
  for (Stmt *SubStmt : S->children())
445
409k
    childrenBuf.push_back(SubStmt);
446
447
  // This needs to be done *after* childrenBuf has been populated.
448
2.02M
  children = childrenBuf;
449
2.02M
}
450
451
namespace {
452
453
/// CFGBuilder - This class implements CFG construction from an AST.
454
///   The builder is stateful: an instance of the builder should be used to only
455
///   construct a single CFG.
456
///
457
///   Example usage:
458
///
459
///     CFGBuilder builder;
460
///     std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);
461
///
462
///  CFG construction is done via a recursive walk of an AST.  We actually parse
463
///  the AST in reverse order so that the successor of a basic block is
464
///  constructed prior to its predecessor.  This allows us to nicely capture
465
///  implicit fall-throughs without extra basic blocks.
466
class CFGBuilder {
467
  using JumpTarget = BlockScopePosPair;
468
  using JumpSource = BlockScopePosPair;
469
470
  ASTContext *Context;
471
  std::unique_ptr<CFG> cfg;
472
473
  // Current block.
474
  CFGBlock *Block = nullptr;
475
476
  // Block after the current block.
477
  CFGBlock *Succ = nullptr;
478
479
  JumpTarget ContinueJumpTarget;
480
  JumpTarget BreakJumpTarget;
481
  JumpTarget SEHLeaveJumpTarget;
482
  CFGBlock *SwitchTerminatedBlock = nullptr;
483
  CFGBlock *DefaultCaseBlock = nullptr;
484
485
  // This can point either to a try or a __try block. The frontend forbids
486
  // mixing both kinds in one function, so having one for both is enough.
487
  CFGBlock *TryTerminatedBlock = nullptr;
488
489
  // Current position in local scope.
490
  LocalScope::const_iterator ScopePos;
491
492
  // LabelMap records the mapping from Label expressions to their jump targets.
493
  using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>;
494
  LabelMapTy LabelMap;
495
496
  // A list of blocks that end with a "goto" that must be backpatched to their
497
  // resolved targets upon completion of CFG construction.
498
  using BackpatchBlocksTy = std::vector<JumpSource>;
499
  BackpatchBlocksTy BackpatchBlocks;
500
501
  // A list of labels whose address has been taken (for indirect gotos).
502
  using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;
503
  LabelSetTy AddressTakenLabels;
504
505
  // Information about the currently visited C++ object construction site.
506
  // This is set in the construction trigger and read when the constructor
507
  // or a function that returns an object by value is being visited.
508
  llvm::DenseMap<Expr *, const ConstructionContextLayer *>
509
      ConstructionContextMap;
510
511
  using DeclsWithEndedScopeSetTy = llvm::SmallSetVector<VarDecl *, 16>;
512
  DeclsWithEndedScopeSetTy DeclsWithEndedScope;
513
514
  bool badCFG = false;
515
  const CFG::BuildOptions &BuildOpts;
516
517
  // State to track for building switch statements.
518
  bool switchExclusivelyCovered = false;
519
  Expr::EvalResult *switchCond = nullptr;
520
521
  CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;
522
  const Stmt *lastLookup = nullptr;
523
524
  // Caches boolean evaluations of expressions to avoid multiple re-evaluations
525
  // during construction of branches for chained logical operators.
526
  using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>;
527
  CachedBoolEvalsTy CachedBoolEvals;
528
529
public:
530
  explicit CFGBuilder(ASTContext *astContext,
531
                      const CFG::BuildOptions &buildOpts)
532
      : Context(astContext), cfg(new CFG()), // crew a new CFG
533
244k
        ConstructionContextMap(), BuildOpts(buildOpts) {}
534
535
536
  // buildCFG - Used by external clients to construct the CFG.
537
  std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);
538
539
  bool alwaysAdd(const Stmt *stmt);
540
541
private:
542
  // Visitors to walk an AST and construct the CFG.
543
  CFGBlock *VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc);
544
  CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
545
  CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
546
  CFGBlock *VisitBreakStmt(BreakStmt *B);
547
  CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
548
  CFGBlock *VisitCaseStmt(CaseStmt *C);
549
  CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
550
  CFGBlock *VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed);
551
  CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
552
                                     AddStmtChoice asc);
553
  CFGBlock *VisitContinueStmt(ContinueStmt *C);
554
  CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
555
                                      AddStmtChoice asc);
556
  CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
557
  CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
558
  CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
559
  CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
560
  CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
561
  CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
562
                                       AddStmtChoice asc);
563
  CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
564
                                        AddStmtChoice asc);
565
  CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
566
  CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
567
  CFGBlock *VisitDeclStmt(DeclStmt *DS);
568
  CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
569
  CFGBlock *VisitDefaultStmt(DefaultStmt *D);
570
  CFGBlock *VisitDoStmt(DoStmt *D);
571
  CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,
572
                                  AddStmtChoice asc, bool ExternallyDestructed);
573
  CFGBlock *VisitForStmt(ForStmt *F);
574
  CFGBlock *VisitGotoStmt(GotoStmt *G);
575
  CFGBlock *VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc);
576
  CFGBlock *VisitIfStmt(IfStmt *I);
577
  CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
578
  CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc);
579
  CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
580
  CFGBlock *VisitLabelStmt(LabelStmt *L);
581
  CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
582
  CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);
583
  CFGBlock *VisitLogicalOperator(BinaryOperator *B);
584
  std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,
585
                                                         Stmt *Term,
586
                                                         CFGBlock *TrueBlock,
587
                                                         CFGBlock *FalseBlock);
588
  CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
589
                                          AddStmtChoice asc);
590
  CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
591
  CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
592
  CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
593
  CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
594
  CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
595
  CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
596
  CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
597
  CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc);
598
  CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
599
  CFGBlock *VisitReturnStmt(Stmt *S);
600
  CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S);
601
  CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S);
602
  CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);
603
  CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);
604
  CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
605
  CFGBlock *VisitSwitchStmt(SwitchStmt *S);
606
  CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
607
                                          AddStmtChoice asc);
608
  CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
609
  CFGBlock *VisitWhileStmt(WhileStmt *W);
610
611
  CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd,
612
                  bool ExternallyDestructed = false);
613
  CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
614
  CFGBlock *VisitChildren(Stmt *S);
615
  CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
616
  CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D,
617
                                        AddStmtChoice asc);
618
619
  void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD,
620
174k
                                    const Stmt *S) {
621
174k
    if (ScopePos && 
(VD == ScopePos.getFirstVarInScope())7.55k
)
622
3.27k
      appendScopeBegin(B, VD, S);
623
174k
  }
624
625
  /// When creating the CFG for temporary destructors, we want to mirror the
626
  /// branch structure of the corresponding constructor calls.
627
  /// Thus, while visiting a statement for temporary destructors, we keep a
628
  /// context to keep track of the following information:
629
  /// - whether a subexpression is executed unconditionally
630
  /// - if a subexpression is executed conditionally, the first
631
  ///   CXXBindTemporaryExpr we encounter in that subexpression (which
632
  ///   corresponds to the last temporary destructor we have to call for this
633
  ///   subexpression) and the CFG block at that point (which will become the
634
  ///   successor block when inserting the decision point).
635
  ///
636
  /// That way, we can build the branch structure for temporary destructors as
637
  /// follows:
638
  /// 1. If a subexpression is executed unconditionally, we add the temporary
639
  ///    destructor calls to the current block.
640
  /// 2. If a subexpression is executed conditionally, when we encounter a
641
  ///    CXXBindTemporaryExpr:
642
  ///    a) If it is the first temporary destructor call in the subexpression,
643
  ///       we remember the CXXBindTemporaryExpr and the current block in the
644
  ///       TempDtorContext; we start a new block, and insert the temporary
645
  ///       destructor call.
646
  ///    b) Otherwise, add the temporary destructor call to the current block.
647
  ///  3. When we finished visiting a conditionally executed subexpression,
648
  ///     and we found at least one temporary constructor during the visitation
649
  ///     (2.a has executed), we insert a decision block that uses the
650
  ///     CXXBindTemporaryExpr as terminator, and branches to the current block
651
  ///     if the CXXBindTemporaryExpr was marked executed, and otherwise
652
  ///     branches to the stored successor.
653
  struct TempDtorContext {
654
18.0k
    TempDtorContext() = default;
655
    TempDtorContext(TryResult KnownExecuted)
656
1.61k
        : IsConditional(true), KnownExecuted(KnownExecuted) {}
657
658
    /// Returns whether we need to start a new branch for a temporary destructor
659
    /// call. This is the case when the temporary destructor is
660
    /// conditionally executed, and it is the first one we encounter while
661
    /// visiting a subexpression - other temporary destructors at the same level
662
    /// will be added to the same block and are executed under the same
663
    /// condition.
664
11.1k
    bool needsTempDtorBranch() const {
665
11.1k
      return IsConditional && 
!TerminatorExpr3.24k
;
666
11.1k
    }
667
668
    /// Remember the successor S of a temporary destructor decision branch for
669
    /// the corresponding CXXBindTemporaryExpr E.
670
987
    void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
671
987
      Succ = S;
672
987
      TerminatorExpr = E;
673
987
    }
674
675
    const bool IsConditional = false;
676
    const TryResult KnownExecuted = true;
677
    CFGBlock *Succ = nullptr;
678
    CXXBindTemporaryExpr *TerminatorExpr = nullptr;
679
  };
680
681
  // Visitors to walk an AST and generate destructors of temporaries in
682
  // full expression.
683
  CFGBlock *VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,
684
                                   TempDtorContext &Context);
685
  CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E,  bool ExternallyDestructed,
686
                                           TempDtorContext &Context);
687
  CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E,
688
                                                 bool ExternallyDestructed,
689
                                                 TempDtorContext &Context);
690
  CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(
691
      CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context);
692
  CFGBlock *VisitConditionalOperatorForTemporaryDtors(
693
      AbstractConditionalOperator *E, bool ExternallyDestructed,
694
      TempDtorContext &Context);
695
  void InsertTempDtorDecisionBlock(const TempDtorContext &Context,
696
                                   CFGBlock *FalseSucc = nullptr);
697
698
  // NYS == Not Yet Supported
699
189
  CFGBlock *NYS() {
700
189
    badCFG = true;
701
189
    return Block;
702
189
  }
703
704
  // Remember to apply the construction context based on the current \p Layer
705
  // when constructing the CFG element for \p CE.
706
  void consumeConstructionContext(const ConstructionContextLayer *Layer,
707
                                  Expr *E);
708
709
  // Scan \p Child statement to find constructors in it, while keeping in mind
710
  // that its parent statement is providing a partial construction context
711
  // described by \p Layer. If a constructor is found, it would be assigned
712
  // the context based on the layer. If an additional construction context layer
713
  // is found, the function recurses into that.
714
  void findConstructionContexts(const ConstructionContextLayer *Layer,
715
                                Stmt *Child);
716
717
  // Scan all arguments of a call expression for a construction context.
718
  // These sorts of call expressions don't have a common superclass,
719
  // hence strict duck-typing.
720
  template <typename CallLikeExpr,
721
            typename = std::enable_if_t<
722
                std::is_base_of<CallExpr, CallLikeExpr>::value ||
723
                std::is_base_of<CXXConstructExpr, CallLikeExpr>::value ||
724
                std::is_base_of<ObjCMessageExpr, CallLikeExpr>::value>>
725
299k
  void findConstructionContextsForArguments(CallLikeExpr *E) {
726
772k
    for (unsigned i = 0, e = E->getNumArgs(); i != e; 
++i473k
) {
727
473k
      Expr *Arg = E->getArg(i);
728
473k
      if (Arg->getType()->getAsCXXRecordDecl() && 
!Arg->isGLValue()48.7k
)
729
4.28k
        findConstructionContexts(
730
4.28k
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731
4.28k
                                             ConstructionContextItem(E, i)),
732
4.28k
            Arg);
733
473k
    }
734
299k
  }
CFG.cpp:void (anonymous namespace)::CFGBuilder::findConstructionContextsForArguments<clang::CallExpr, void>(clang::CallExpr*)
Line
Count
Source
725
240k
  void findConstructionContextsForArguments(CallLikeExpr *E) {
726
673k
    for (unsigned i = 0, e = E->getNumArgs(); i != e; 
++i433k
) {
727
433k
      Expr *Arg = E->getArg(i);
728
433k
      if (Arg->getType()->getAsCXXRecordDecl() && 
!Arg->isGLValue()28.2k
)
729
3.42k
        findConstructionContexts(
730
3.42k
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731
3.42k
                                             ConstructionContextItem(E, i)),
732
3.42k
            Arg);
733
433k
    }
734
240k
  }
CFG.cpp:void (anonymous namespace)::CFGBuilder::findConstructionContextsForArguments<clang::CXXConstructExpr, void>(clang::CXXConstructExpr*)
Line
Count
Source
725
36.3k
  void findConstructionContextsForArguments(CallLikeExpr *E) {
726
66.0k
    for (unsigned i = 0, e = E->getNumArgs(); i != e; 
++i29.6k
) {
727
29.6k
      Expr *Arg = E->getArg(i);
728
29.6k
      if (Arg->getType()->getAsCXXRecordDecl() && 
!Arg->isGLValue()20.3k
)
729
804
        findConstructionContexts(
730
804
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731
804
                                             ConstructionContextItem(E, i)),
732
804
            Arg);
733
29.6k
    }
734
36.3k
  }
CFG.cpp:void (anonymous namespace)::CFGBuilder::findConstructionContextsForArguments<clang::CXXTemporaryObjectExpr, void>(clang::CXXTemporaryObjectExpr*)
Line
Count
Source
725
4.64k
  void findConstructionContextsForArguments(CallLikeExpr *E) {
726
6.68k
    for (unsigned i = 0, e = E->getNumArgs(); i != e; 
++i2.03k
) {
727
2.03k
      Expr *Arg = E->getArg(i);
728
2.03k
      if (Arg->getType()->getAsCXXRecordDecl() && 
!Arg->isGLValue()117
)
729
34
        findConstructionContexts(
730
34
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731
34
                                             ConstructionContextItem(E, i)),
732
34
            Arg);
733
2.03k
    }
734
4.64k
  }
CFG.cpp:void (anonymous namespace)::CFGBuilder::findConstructionContextsForArguments<clang::ObjCMessageExpr, void>(clang::ObjCMessageExpr*)
Line
Count
Source
725
17.8k
  void findConstructionContextsForArguments(CallLikeExpr *E) {
726
25.8k
    for (unsigned i = 0, e = E->getNumArgs(); i != e; 
++i8.01k
) {
727
8.01k
      Expr *Arg = E->getArg(i);
728
8.01k
      if (Arg->getType()->getAsCXXRecordDecl() && 
!Arg->isGLValue()37
)
729
29
        findConstructionContexts(
730
29
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731
29
                                             ConstructionContextItem(E, i)),
732
29
            Arg);
733
8.01k
    }
734
17.8k
  }
735
736
  // Unset the construction context after consuming it. This is done immediately
737
  // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so
738
  // there's no need to do this manually in every Visit... function.
739
  void cleanupConstructionContext(Expr *E);
740
741
4.27M
  void autoCreateBlock() { if (!Block) 
Block = createBlock()165k
; }
742
  CFGBlock *createBlock(bool add_successor = true);
743
  CFGBlock *createNoReturnBlock();
744
745
636k
  CFGBlock *addStmt(Stmt *S) {
746
636k
    return Visit(S, AddStmtChoice::AlwaysAdd);
747
636k
  }
748
749
  CFGBlock *addInitializer(CXXCtorInitializer *I);
750
  void addLoopExit(const Stmt *LoopStmt);
751
  void addAutomaticObjDtors(LocalScope::const_iterator B,
752
                            LocalScope::const_iterator E, Stmt *S);
753
  void addLifetimeEnds(LocalScope::const_iterator B,
754
                       LocalScope::const_iterator E, Stmt *S);
755
  void addAutomaticObjHandling(LocalScope::const_iterator B,
756
                               LocalScope::const_iterator E, Stmt *S);
757
  void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
758
  void addScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E,
759
                    Stmt *S);
760
761
  void getDeclsWithEndedScope(LocalScope::const_iterator B,
762
                              LocalScope::const_iterator E, Stmt *S);
763
764
  // Local scopes creation.
765
  LocalScope* createOrReuseLocalScope(LocalScope* Scope);
766
767
  void addLocalScopeForStmt(Stmt *S);
768
  LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
769
                                       LocalScope* Scope = nullptr);
770
  LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
771
772
  void addLocalScopeAndDtors(Stmt *S);
773
774
373k
  const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {
775
373k
    if (!BuildOpts.AddRichCXXConstructors)
776
260k
      return nullptr;
777
778
113k
    const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E);
779
113k
    if (!Layer)
780
80.8k
      return nullptr;
781
782
32.3k
    cleanupConstructionContext(E);
783
32.3k
    return ConstructionContext::createFromLayers(cfg->getBumpVectorContext(),
784
32.3k
                                                 Layer);
785
113k
  }
786
787
  // Interface to CFGBlock - adding CFGElements.
788
789
4.06M
  void appendStmt(CFGBlock *B, const Stmt *S) {
790
4.06M
    if (alwaysAdd(S) && 
cachedEntry3.71M
)
791
14.7k
      cachedEntry->second = B;
792
793
    // All block-level expressions should have already been IgnoreParens()ed.
794
4.06M
    assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
795
0
    B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
796
4.06M
  }
797
798
40.9k
  void appendConstructor(CFGBlock *B, CXXConstructExpr *CE) {
799
40.9k
    if (const ConstructionContext *CC =
800
40.9k
            retrieveAndCleanupConstructionContext(CE)) {
801
24.2k
      B->appendConstructor(CE, CC, cfg->getBumpVectorContext());
802
24.2k
      return;
803
24.2k
    }
804
805
    // No valid construction context found. Fall back to statement.
806
16.6k
    B->appendStmt(CE, cfg->getBumpVectorContext());
807
16.6k
  }
808
809
314k
  void appendCall(CFGBlock *B, CallExpr *CE) {
810
314k
    if (alwaysAdd(CE) && 
cachedEntry87.2k
)
811
342
      cachedEntry->second = B;
812
813
314k
    if (const ConstructionContext *CC =
814
314k
            retrieveAndCleanupConstructionContext(CE)) {
815
8.00k
      B->appendCXXRecordTypedCall(CE, CC, cfg->getBumpVectorContext());
816
8.00k
      return;
817
8.00k
    }
818
819
    // No valid construction context found. Fall back to statement.
820
306k
    B->appendStmt(CE, cfg->getBumpVectorContext());
821
306k
  }
822
823
14.4k
  void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
824
14.4k
    B->appendInitializer(I, cfg->getBumpVectorContext());
825
14.4k
  }
826
827
1.88k
  void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
828
1.88k
    B->appendNewAllocator(NE, cfg->getBumpVectorContext());
829
1.88k
  }
830
831
527
  void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
832
527
    B->appendBaseDtor(BS, cfg->getBumpVectorContext());
833
527
  }
834
835
147
  void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
836
147
    B->appendMemberDtor(FD, cfg->getBumpVectorContext());
837
147
  }
838
839
17.8k
  void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) {
840
17.8k
    if (alwaysAdd(ME) && 
cachedEntry7.92k
)
841
15
      cachedEntry->second = B;
842
843
17.8k
    if (const ConstructionContext *CC =
844
17.8k
            retrieveAndCleanupConstructionContext(ME)) {
845
16
      B->appendCXXRecordTypedCall(ME, CC, cfg->getBumpVectorContext());
846
16
      return;
847
16
    }
848
849
17.8k
    B->appendStmt(const_cast<ObjCMessageExpr *>(ME),
850
17.8k
                  cfg->getBumpVectorContext());
851
17.8k
  }
852
853
5.70k
  void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
854
5.70k
    B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
855
5.70k
  }
856
857
5.27k
  void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
858
5.27k
    B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
859
5.27k
  }
860
861
162
  void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
862
162
    B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
863
162
  }
864
865
254
  void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
866
254
    B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());
867
254
  }
868
869
230
  void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
870
230
    B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
871
230
  }
872
873
  void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
874
      LocalScope::const_iterator B, LocalScope::const_iterator E);
875
876
  void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
877
                                                 LocalScope::const_iterator B,
878
                                                 LocalScope::const_iterator E);
879
880
  const VarDecl *
881
  prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk,
882
                                            LocalScope::const_iterator B,
883
                                            LocalScope::const_iterator E);
884
885
988k
  void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
886
988k
    B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
887
988k
                    cfg->getBumpVectorContext());
888
988k
  }
889
890
  /// Add a reachable successor to a block, with the alternate variant that is
891
  /// unreachable.
892
1.31k
  void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
893
1.31k
    B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
894
1.31k
                    cfg->getBumpVectorContext());
895
1.31k
  }
896
897
3.34k
  void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
898
3.34k
    if (BuildOpts.AddScopes)
899
92
      B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());
900
3.34k
  }
901
902
0
  void prependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
903
0
    if (BuildOpts.AddScopes)
904
0
      B->prependScopeBegin(VD, S, cfg->getBumpVectorContext());
905
0
  }
906
907
154
  void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
908
154
    if (BuildOpts.AddScopes)
909
154
      B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());
910
154
  }
911
912
0
  void prependScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
913
0
    if (BuildOpts.AddScopes)
914
0
      B->prependScopeEnd(VD, S, cfg->getBumpVectorContext());
915
0
  }
916
917
  /// Find a relational comparison with an expression evaluating to a
918
  /// boolean and a constant other than 0 and 1.
919
  /// e.g. if ((x < y) == 10)
920
92.0k
  TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
921
92.0k
    const Expr *LHSExpr = B->getLHS()->IgnoreParens();
922
92.0k
    const Expr *RHSExpr = B->getRHS()->IgnoreParens();
923
924
92.0k
    const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
925
92.0k
    const Expr *BoolExpr = RHSExpr;
926
92.0k
    bool IntFirst = true;
927
92.0k
    if (!IntLiteral) {
928
90.1k
      IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
929
90.1k
      BoolExpr = LHSExpr;
930
90.1k
      IntFirst = false;
931
90.1k
    }
932
933
92.0k
    if (!IntLiteral || 
!BoolExpr->isKnownToHaveBooleanValue()29.2k
)
934
91.8k
      return TryResult();
935
936
220
    llvm::APInt IntValue = IntLiteral->getValue();
937
220
    if ((IntValue == 1) || 
(IntValue == 0)152
)
938
146
      return TryResult();
939
940
74
    bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||
941
74
                     !IntValue.isNegative();
942
943
74
    BinaryOperatorKind Bok = B->getOpcode();
944
74
    if (Bok == BO_GT || 
Bok == BO_GE34
) {
945
      // Always true for 10 > bool and bool > -1
946
      // Always false for -1 > bool and bool > 10
947
50
      return TryResult(IntFirst == IntLarger);
948
50
    } else {
949
      // Always true for -1 < bool and bool < 10
950
      // Always false for 10 < bool and bool < -1
951
24
      return TryResult(IntFirst != IntLarger);
952
24
    }
953
74
  }
954
955
  /// Find an incorrect equality comparison. Either with an expression
956
  /// evaluating to a boolean and a constant other than 0 and 1.
957
  /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to
958
  /// true/false e.q. (x & 8) == 4.
959
31.6k
  TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {
960
31.6k
    const Expr *LHSExpr = B->getLHS()->IgnoreParens();
961
31.6k
    const Expr *RHSExpr = B->getRHS()->IgnoreParens();
962
963
31.6k
    const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
964
31.6k
    const Expr *BoolExpr = RHSExpr;
965
966
31.6k
    if (!IntLiteral) {
967
30.7k
      IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
968
30.7k
      BoolExpr = LHSExpr;
969
30.7k
    }
970
971
31.6k
    if (!IntLiteral)
972
22.2k
      return TryResult();
973
974
9.33k
    const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr);
975
9.33k
    if (BitOp && 
(323
BitOp->getOpcode() == BO_And323
||
976
323
                  
BitOp->getOpcode() == BO_Or286
)) {
977
70
      const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();
978
70
      const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();
979
980
70
      const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2);
981
982
70
      if (!IntLiteral2)
983
56
        IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2);
984
985
70
      if (!IntLiteral2)
986
6
        return TryResult();
987
988
64
      llvm::APInt L1 = IntLiteral->getValue();
989
64
      llvm::APInt L2 = IntLiteral2->getValue();
990
64
      if ((BitOp->getOpcode() == BO_And && 
(L2 & L1) != L137
) ||
991
64
          
(46
BitOp->getOpcode() == BO_Or46
&&
(L2 | L1) != L127
)) {
992
34
        if (BuildOpts.Observer)
993
28
          BuildOpts.Observer->compareBitwiseEquality(B,
994
28
                                                     B->getOpcode() != BO_EQ);
995
34
        TryResult(B->getOpcode() != BO_EQ);
996
34
      }
997
9.26k
    } else if (BoolExpr->isKnownToHaveBooleanValue()) {
998
171
      llvm::APInt IntValue = IntLiteral->getValue();
999
171
      if ((IntValue == 1) || 
(IntValue == 0)55
) {
1000
161
        return TryResult();
1001
161
      }
1002
10
      return TryResult(B->getOpcode() != BO_EQ);
1003
171
    }
1004
1005
9.15k
    return TryResult();
1006
9.33k
  }
1007
1008
  TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,
1009
                                          const llvm::APSInt &Value1,
1010
16.4k
                                          const llvm::APSInt &Value2) {
1011
16.4k
    assert(Value1.isSigned() == Value2.isSigned());
1012
0
    switch (Relation) {
1013
0
      default:
1014
0
        return TryResult();
1015
495
      case BO_EQ:
1016
495
        return TryResult(Value1 == Value2);
1017
170
      case BO_NE:
1018
170
        return TryResult(Value1 != Value2);
1019
625
      case BO_LT:
1020
625
        return TryResult(Value1 <  Value2);
1021
7.26k
      case BO_LE:
1022
7.26k
        return TryResult(Value1 <= Value2);
1023
570
      case BO_GT:
1024
570
        return TryResult(Value1 >  Value2);
1025
7.29k
      case BO_GE:
1026
7.29k
        return TryResult(Value1 >= Value2);
1027
16.4k
    }
1028
16.4k
  }
1029
1030
  /// Find a pair of comparison expressions with or without parentheses
1031
  /// with a shared variable and constants and a logical operator between them
1032
  /// that always evaluates to either true or false.
1033
  /// e.g. if (x != 3 || x != 4)
1034
12.4k
  TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
1035
12.4k
    assert(B->isLogicalOp());
1036
0
    const BinaryOperator *LHS =
1037
12.4k
        dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens());
1038
12.4k
    const BinaryOperator *RHS =
1039
12.4k
        dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens());
1040
12.4k
    if (!LHS || 
!RHS6.77k
)
1041
9.99k
      return {};
1042
1043
2.45k
    if (!LHS->isComparisonOp() || 
!RHS->isComparisonOp()2.03k
)
1044
432
      return {};
1045
1046
2.02k
    const Expr *DeclExpr1;
1047
2.02k
    const Expr *NumExpr1;
1048
2.02k
    BinaryOperatorKind BO1;
1049
2.02k
    std::tie(DeclExpr1, BO1, NumExpr1) = tryNormalizeBinaryOperator(LHS);
1050
1051
2.02k
    if (!DeclExpr1 || !NumExpr1)
1052
185
      return {};
1053
1054
1.83k
    const Expr *DeclExpr2;
1055
1.83k
    const Expr *NumExpr2;
1056
1.83k
    BinaryOperatorKind BO2;
1057
1.83k
    std::tie(DeclExpr2, BO2, NumExpr2) = tryNormalizeBinaryOperator(RHS);
1058
1059
1.83k
    if (!DeclExpr2 || !NumExpr2)
1060
26
      return {};
1061
1062
    // Check that it is the same variable on both sides.
1063
1.81k
    if (!Expr::isSameComparisonOperand(DeclExpr1, DeclExpr2))
1064
155
      return {};
1065
1066
    // Make sure the user's intent is clear (e.g. they're comparing against two
1067
    // int literals, or two things from the same enum)
1068
1.65k
    if (!areExprTypesCompatible(NumExpr1, NumExpr2))
1069
16
      return {};
1070
1071
1.64k
    Expr::EvalResult L1Result, L2Result;
1072
1.64k
    if (!NumExpr1->EvaluateAsInt(L1Result, *Context) ||
1073
1.64k
        !NumExpr2->EvaluateAsInt(L2Result, *Context))
1074
0
      return {};
1075
1076
1.64k
    llvm::APSInt L1 = L1Result.Val.getInt();
1077
1.64k
    llvm::APSInt L2 = L2Result.Val.getInt();
1078
1079
    // Can't compare signed with unsigned or with different bit width.
1080
1.64k
    if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth())
1081
0
      return {};
1082
1083
    // Values that will be used to determine if result of logical
1084
    // operator is always true/false
1085
1.64k
    const llvm::APSInt Values[] = {
1086
      // Value less than both Value1 and Value2
1087
1.64k
      llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()),
1088
      // L1
1089
1.64k
      L1,
1090
      // Value between Value1 and Value2
1091
1.64k
      ((L1 < L2) ? 
L11.55k
:
L282
) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1),
1092
1.64k
                              L1.isUnsigned()),
1093
      // L2
1094
1.64k
      L2,
1095
      // Value greater than both Value1 and Value2
1096
1.64k
      llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()),
1097
1.64k
    };
1098
1099
    // Check whether expression is always true/false by evaluating the following
1100
    // * variable x is less than the smallest literal.
1101
    // * variable x is equal to the smallest literal.
1102
    // * Variable x is between smallest and largest literal.
1103
    // * Variable x is equal to the largest literal.
1104
    // * Variable x is greater than largest literal.
1105
1.64k
    bool AlwaysTrue = true, AlwaysFalse = true;
1106
    // Track value of both subexpressions.  If either side is always
1107
    // true/false, another warning should have already been emitted.
1108
1.64k
    bool LHSAlwaysTrue = true, LHSAlwaysFalse = true;
1109
1.64k
    bool RHSAlwaysTrue = true, RHSAlwaysFalse = true;
1110
8.20k
    for (const llvm::APSInt &Value : Values) {
1111
8.20k
      TryResult Res1, Res2;
1112
8.20k
      Res1 = analyzeLogicOperatorCondition(BO1, Value, L1);
1113
8.20k
      Res2 = analyzeLogicOperatorCondition(BO2, Value, L2);
1114
1115
8.20k
      if (!Res1.isKnown() || !Res2.isKnown())
1116
0
        return {};
1117
1118
8.20k
      if (B->getOpcode() == BO_LAnd) {
1119
7.59k
        AlwaysTrue &= (Res1.isTrue() && 
Res2.isTrue()5.92k
);
1120
7.59k
        AlwaysFalse &= !(Res1.isTrue() && 
Res2.isTrue()5.92k
);
1121
7.59k
      } else {
1122
610
        AlwaysTrue &= (Res1.isTrue() || 
Res2.isTrue()326
);
1123
610
        AlwaysFalse &= !(Res1.isTrue() || 
Res2.isTrue()326
);
1124
610
      }
1125
1126
8.20k
      LHSAlwaysTrue &= Res1.isTrue();
1127
8.20k
      LHSAlwaysFalse &= Res1.isFalse();
1128
8.20k
      RHSAlwaysTrue &= Res2.isTrue();
1129
8.20k
      RHSAlwaysFalse &= Res2.isFalse();
1130
8.20k
    }
1131
1132
1.64k
    if (AlwaysTrue || 
AlwaysFalse1.57k
) {
1133
115
      if (!LHSAlwaysTrue && 
!LHSAlwaysFalse113
&&
!RHSAlwaysTrue111
&&
1134
115
          
!RHSAlwaysFalse111
&&
BuildOpts.Observer111
)
1135
104
        BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue);
1136
115
      return TryResult(AlwaysTrue);
1137
115
    }
1138
1.52k
    return {};
1139
1.64k
  }
1140
1141
  /// A bitwise-or with a non-zero constant always evaluates to true.
1142
27
  TryResult checkIncorrectBitwiseOrOperator(const BinaryOperator *B) {
1143
27
    const Expr *LHSConstant =
1144
27
        tryTransformToIntOrEnumConstant(B->getLHS()->IgnoreParenImpCasts());
1145
27
    const Expr *RHSConstant =
1146
27
        tryTransformToIntOrEnumConstant(B->getRHS()->IgnoreParenImpCasts());
1147
1148
27
    if ((LHSConstant && 
RHSConstant2
) || (!LHSConstant &&
!RHSConstant25
))
1149
3
      return {};
1150
1151
24
    const Expr *Constant = LHSConstant ? 
LHSConstant2
:
RHSConstant22
;
1152
1153
24
    Expr::EvalResult Result;
1154
24
    if (!Constant->EvaluateAsInt(Result, *Context))
1155
0
      return {};
1156
1157
24
    if (Result.Val.getInt() == 0)
1158
8
      return {};
1159
1160
16
    if (BuildOpts.Observer)
1161
16
      BuildOpts.Observer->compareBitwiseOr(B);
1162
1163
16
    return TryResult(true);
1164
24
  }
1165
1166
  /// Try and evaluate an expression to an integer constant.
1167
838
  bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
1168
838
    if (!BuildOpts.PruneTriviallyFalseEdges)
1169
6
      return false;
1170
832
    return !S->isTypeDependent() &&
1171
832
           !S->isValueDependent() &&
1172
832
           S->EvaluateAsRValue(outResult, *Context);
1173
838
  }
1174
1175
  /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
1176
  /// if we can evaluate to a known value, otherwise return -1.
1177
359k
  TryResult tryEvaluateBool(Expr *S) {
1178
359k
    if (!BuildOpts.PruneTriviallyFalseEdges ||
1179
359k
        
S->isTypeDependent()359k
||
S->isValueDependent()359k
)
1180
154
      return {};
1181
1182
359k
    if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) {
1183
166k
      if (Bop->isLogicalOp() || 
Bop->isEqualityOp()148k
) {
1184
        // Check the cache first.
1185
71.1k
        CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S);
1186
71.1k
        if (I != CachedBoolEvals.end())
1187
26.4k
          return I->second; // already in map;
1188
1189
        // Retrieve result at first, or the map might be updated.
1190
44.7k
        TryResult Result = evaluateAsBooleanConditionNoCache(S);
1191
44.7k
        CachedBoolEvals[S] = Result; // update or insert
1192
44.7k
        return Result;
1193
71.1k
      }
1194
95.0k
      else {
1195
95.0k
        switch (Bop->getOpcode()) {
1196
92.5k
          default: break;
1197
          // For 'x & 0' and 'x * 0', we can determine that
1198
          // the value is always false.
1199
92.5k
          case BO_Mul:
1200
2.48k
          case BO_And: {
1201
            // If either operand is zero, we know the value
1202
            // must be false.
1203
2.48k
            Expr::EvalResult LHSResult;
1204
2.48k
            if (Bop->getLHS()->EvaluateAsInt(LHSResult, *Context)) {
1205
9
              llvm::APSInt IntVal = LHSResult.Val.getInt();
1206
9
              if (!IntVal.getBoolValue()) {
1207
4
                return TryResult(false);
1208
4
              }
1209
9
            }
1210
2.47k
            Expr::EvalResult RHSResult;
1211
2.47k
            if (Bop->getRHS()->EvaluateAsInt(RHSResult, *Context)) {
1212
2.45k
              llvm::APSInt IntVal = RHSResult.Val.getInt();
1213
2.45k
              if (!IntVal.getBoolValue()) {
1214
4
                return TryResult(false);
1215
4
              }
1216
2.45k
            }
1217
2.47k
          }
1218
2.47k
          break;
1219
95.0k
        }
1220
95.0k
      }
1221
166k
    }
1222
1223
288k
    return evaluateAsBooleanConditionNoCache(S);
1224
359k
  }
1225
1226
  /// Evaluate as boolean \param E without using the cache.
1227
333k
  TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
1228
333k
    if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) {
1229
139k
      if (Bop->isLogicalOp()) {
1230
13.1k
        TryResult LHS = tryEvaluateBool(Bop->getLHS());
1231
13.1k
        if (LHS.isKnown()) {
1232
          // We were able to evaluate the LHS, see if we can get away with not
1233
          // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1234
675
          if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1235
79
            return LHS.isTrue();
1236
1237
596
          TryResult RHS = tryEvaluateBool(Bop->getRHS());
1238
596
          if (RHS.isKnown()) {
1239
8
            if (Bop->getOpcode() == BO_LOr)
1240
4
              return LHS.isTrue() || RHS.isTrue();
1241
4
            else
1242
4
              return LHS.isTrue() && RHS.isTrue();
1243
8
          }
1244
12.4k
        } else {
1245
12.4k
          TryResult RHS = tryEvaluateBool(Bop->getRHS());
1246
12.4k
          if (RHS.isKnown()) {
1247
            // We can't evaluate the LHS; however, sometimes the result
1248
            // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1249
18
            if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1250
3
              return RHS.isTrue();
1251
12.4k
          } else {
1252
12.4k
            TryResult BopRes = checkIncorrectLogicOperator(Bop);
1253
12.4k
            if (BopRes.isKnown())
1254
115
              return BopRes.isTrue();
1255
12.4k
          }
1256
12.4k
        }
1257
1258
12.9k
        return {};
1259
126k
      } else if (Bop->isEqualityOp()) {
1260
31.6k
          TryResult BopRes = checkIncorrectEqualityOperator(Bop);
1261
31.6k
          if (BopRes.isKnown())
1262
10
            return BopRes.isTrue();
1263
95.0k
      } else if (Bop->isRelationalOp()) {
1264
92.0k
        TryResult BopRes = checkIncorrectRelationalOperator(Bop);
1265
92.0k
        if (BopRes.isKnown())
1266
74
          return BopRes.isTrue();
1267
92.0k
      } else 
if (2.94k
Bop->getOpcode() == BO_Or2.94k
) {
1268
27
        TryResult BopRes = checkIncorrectBitwiseOrOperator(Bop);
1269
27
        if (BopRes.isKnown())
1270
16
          return BopRes.isTrue();
1271
27
      }
1272
139k
    }
1273
1274
320k
    bool Result;
1275
320k
    if (E->EvaluateAsBooleanCondition(Result, *Context))
1276
7.14k
      return Result;
1277
1278
312k
    return {};
1279
320k
  }
1280
1281
  bool hasTrivialDestructor(VarDecl *VD);
1282
};
1283
1284
} // namespace
1285
1286
inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
1287
4.15M
                                     const Stmt *stmt) const {
1288
4.15M
  return builder.alwaysAdd(stmt) || 
kind == AlwaysAdd503k
;
1289
4.15M
}
1290
1291
8.54M
bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
1292
8.54M
  bool shouldAdd = BuildOpts.alwaysAdd(stmt);
1293
1294
8.54M
  if (!BuildOpts.forcedBlkExprs)
1295
126
    return shouldAdd;
1296
1297
8.54M
  if (lastLookup == stmt) {
1298
3.69M
    if (cachedEntry) {
1299
14.0k
      assert(cachedEntry->first == stmt);
1300
0
      return true;
1301
14.0k
    }
1302
3.67M
    return shouldAdd;
1303
3.69M
  }
1304
1305
4.85M
  lastLookup = stmt;
1306
1307
  // Perform the lookup!
1308
4.85M
  CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
1309
1310
4.85M
  if (!fb) {
1311
    // No need to update 'cachedEntry', since it will always be null.
1312
4.65M
    assert(!cachedEntry);
1313
0
    return shouldAdd;
1314
4.65M
  }
1315
1316
196k
  CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
1317
196k
  if (itr == fb->end()) {
1318
181k
    cachedEntry = nullptr;
1319
181k
    return shouldAdd;
1320
181k
  }
1321
1322
15.1k
  cachedEntry = &*itr;
1323
15.1k
  return true;
1324
196k
}
1325
1326
// FIXME: Add support for dependent-sized array types in C++?
1327
// Does it even make sense to build a CFG for an uninstantiated template?
1328
184k
static const VariableArrayType *FindVA(const Type *t) {
1329
192k
  while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
1330
11.2k
    if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
1331
2.80k
      if (vat->getSizeExpr())
1332
2.80k
        return vat;
1333
1334
8.42k
    t = vt->getElementType().getTypePtr();
1335
8.42k
  }
1336
1337
181k
  return nullptr;
1338
184k
}
1339
1340
void CFGBuilder::consumeConstructionContext(
1341
44.2k
    const ConstructionContextLayer *Layer, Expr *E) {
1342
44.2k
  assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) ||
1343
44.2k
          isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!");
1344
44.2k
  if (const ConstructionContextLayer *PreviouslyStoredLayer =
1345
44.2k
          ConstructionContextMap.lookup(E)) {
1346
11.9k
    (void)PreviouslyStoredLayer;
1347
    // We might have visited this child when we were finding construction
1348
    // contexts within its parents.
1349
11.9k
    assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) &&
1350
11.9k
           "Already within a different construction context!");
1351
32.3k
  } else {
1352
32.3k
    ConstructionContextMap[E] = Layer;
1353
32.3k
  }
1354
44.2k
}
1355
1356
void CFGBuilder::findConstructionContexts(
1357
443k
    const ConstructionContextLayer *Layer, Stmt *Child) {
1358
443k
  if (!BuildOpts.AddRichCXXConstructors)
1359
317k
    return;
1360
1361
126k
  if (!Child)
1362
9.53k
    return;
1363
1364
116k
  auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) {
1365
23.6k
    return ConstructionContextLayer::create(cfg->getBumpVectorContext(), Item,
1366
23.6k
                                            Layer);
1367
23.6k
  };
1368
1369
116k
  switch(Child->getStmtClass()) {
1370
24.7k
  case Stmt::CXXConstructExprClass:
1371
30.3k
  case Stmt::CXXTemporaryObjectExprClass: {
1372
    // Support pre-C++17 copy elision AST.
1373
30.3k
    auto *CE = cast<CXXConstructExpr>(Child);
1374
30.3k
    if (BuildOpts.MarkElidedCXXConstructors && 
CE->isElidable()29.7k
) {
1375
9.33k
      findConstructionContexts(withExtraLayer(CE), CE->getArg(0));
1376
9.33k
    }
1377
1378
30.3k
    consumeConstructionContext(Layer, CE);
1379
30.3k
    break;
1380
24.7k
  }
1381
  // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr.
1382
  // FIXME: An isa<> would look much better but this whole switch is a
1383
  // workaround for an internal compiler error in MSVC 2015 (see r326021).
1384
6.86k
  case Stmt::CallExprClass:
1385
16.5k
  case Stmt::CXXMemberCallExprClass:
1386
17.9k
  case Stmt::CXXOperatorCallExprClass:
1387
17.9k
  case Stmt::UserDefinedLiteralClass:
1388
19.2k
  case Stmt::ObjCMessageExprClass: {
1389
19.2k
    auto *E = cast<Expr>(Child);
1390
19.2k
    if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E))
1391
13.8k
      consumeConstructionContext(Layer, E);
1392
19.2k
    break;
1393
17.9k
  }
1394
8.93k
  case Stmt::ExprWithCleanupsClass: {
1395
8.93k
    auto *Cleanups = cast<ExprWithCleanups>(Child);
1396
8.93k
    findConstructionContexts(Layer, Cleanups->getSubExpr());
1397
8.93k
    break;
1398
17.9k
  }
1399
3.22k
  case Stmt::CXXFunctionalCastExprClass: {
1400
3.22k
    auto *Cast = cast<CXXFunctionalCastExpr>(Child);
1401
3.22k
    findConstructionContexts(Layer, Cast->getSubExpr());
1402
3.22k
    break;
1403
17.9k
  }
1404
22.3k
  case Stmt::ImplicitCastExprClass: {
1405
22.3k
    auto *Cast = cast<ImplicitCastExpr>(Child);
1406
    // Should we support other implicit cast kinds?
1407
22.3k
    switch (Cast->getCastKind()) {
1408
7.23k
    case CK_NoOp:
1409
7.73k
    case CK_ConstructorConversion:
1410
7.73k
      findConstructionContexts(Layer, Cast->getSubExpr());
1411
7.73k
      break;
1412
14.6k
    default:
1413
14.6k
      break;
1414
22.3k
    }
1415
22.3k
    break;
1416
22.3k
  }
1417
22.3k
  case Stmt::CXXBindTemporaryExprClass: {
1418
5.20k
    auto *BTE = cast<CXXBindTemporaryExpr>(Child);
1419
5.20k
    findConstructionContexts(withExtraLayer(BTE), BTE->getSubExpr());
1420
5.20k
    break;
1421
22.3k
  }
1422
9.58k
  case Stmt::MaterializeTemporaryExprClass: {
1423
    // Normally we don't want to search in MaterializeTemporaryExpr because
1424
    // it indicates the beginning of a temporary object construction context,
1425
    // so it shouldn't be found in the middle. However, if it is the beginning
1426
    // of an elidable copy or move construction context, we need to include it.
1427
9.58k
    if (Layer->getItem().getKind() ==
1428
9.58k
        ConstructionContextItem::ElidableConstructorKind) {
1429
9.15k
      auto *MTE = cast<MaterializeTemporaryExpr>(Child);
1430
9.15k
      findConstructionContexts(withExtraLayer(MTE), MTE->getSubExpr());
1431
9.15k
    }
1432
9.58k
    break;
1433
22.3k
  }
1434
324
  case Stmt::ConditionalOperatorClass: {
1435
324
    auto *CO = cast<ConditionalOperator>(Child);
1436
324
    if (Layer->getItem().getKind() !=
1437
324
        ConstructionContextItem::MaterializationKind) {
1438
      // If the object returned by the conditional operator is not going to be a
1439
      // temporary object that needs to be immediately materialized, then
1440
      // it must be C++17 with its mandatory copy elision. Do not yet promise
1441
      // to support this case.
1442
184
      assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() ||
1443
184
             Context->getLangOpts().CPlusPlus17);
1444
0
      break;
1445
184
    }
1446
140
    findConstructionContexts(Layer, CO->getLHS());
1447
140
    findConstructionContexts(Layer, CO->getRHS());
1448
140
    break;
1449
324
  }
1450
1.49k
  case Stmt::InitListExprClass: {
1451
1.49k
    auto *ILE = cast<InitListExpr>(Child);
1452
1.49k
    if (ILE->isTransparent()) {
1453
22
      findConstructionContexts(Layer, ILE->getInit(0));
1454
22
      break;
1455
22
    }
1456
    // TODO: Handle other cases. For now, fail to find construction contexts.
1457
1.47k
    break;
1458
1.49k
  }
1459
1.47k
  case Stmt::ParenExprClass: {
1460
    // If expression is placed into parenthesis we should propagate the parent
1461
    // construction context to subexpressions.
1462
614
    auto *PE = cast<ParenExpr>(Child);
1463
614
    findConstructionContexts(Layer, PE->getSubExpr());
1464
614
    break;
1465
1.49k
  }
1466
15.1k
  default:
1467
15.1k
    break;
1468
116k
  }
1469
116k
}
1470
1471
32.3k
void CFGBuilder::cleanupConstructionContext(Expr *E) {
1472
32.3k
  assert(BuildOpts.AddRichCXXConstructors &&
1473
32.3k
         "We should not be managing construction contexts!");
1474
0
  assert(ConstructionContextMap.count(E) &&
1475
32.3k
         "Cannot exit construction context without the context!");
1476
0
  ConstructionContextMap.erase(E);
1477
32.3k
}
1478
1479
1480
/// BuildCFG - Constructs a CFG from an AST (a Stmt*).  The AST can represent an
1481
///  arbitrary statement.  Examples include a single expression or a function
1482
///  body (compound statement).  The ownership of the returned CFG is
1483
///  transferred to the caller.  If CFG construction fails, this method returns
1484
///  NULL.
1485
244k
std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
1486
244k
  assert(cfg.get());
1487
244k
  if (!Statement)
1488
504
    return nullptr;
1489
1490
  // Create an empty block that will serve as the exit block for the CFG.  Since
1491
  // this is the first block added to the CFG, it will be implicitly registered
1492
  // as the exit block.
1493
244k
  Succ = createBlock();
1494
244k
  assert(Succ == &cfg->getExit());
1495
0
  Block = nullptr;  // the EXIT block is empty.  Create all other blocks lazily.
1496
1497
244k
  assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
1498
244k
         "AddImplicitDtors and AddLifetime cannot be used at the same time");
1499
1500
244k
  if (BuildOpts.AddImplicitDtors)
1501
244k
    if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
1502
7.10k
      addImplicitDtorsForDestructor(DD);
1503
1504
  // Visit the statements and create the CFG.
1505
244k
  CFGBlock *B = addStmt(Statement);
1506
1507
244k
  if (badCFG)
1508
192
    return nullptr;
1509
1510
  // For C++ constructor add initializers to CFG. Constructors of virtual bases
1511
  // are ignored unless the object is of the most derived class.
1512
  //   class VBase { VBase() = default; VBase(int) {} };
1513
  //   class A : virtual public VBase { A() : VBase(0) {} };
1514
  //   class B : public A {};
1515
  //   B b; // Constructor calls in order: VBase(), A(), B().
1516
  //        // VBase(0) is ignored because A isn't the most derived class.
1517
  // This may result in the virtual base(s) being already initialized at this
1518
  // point, in which case we should jump right onto non-virtual bases and
1519
  // fields. To handle this, make a CFG branch. We only need to add one such
1520
  // branch per constructor, since the Standard states that all virtual bases
1521
  // shall be initialized before non-virtual bases and direct data members.
1522
243k
  if (const auto *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
1523
14.1k
    CFGBlock *VBaseSucc = nullptr;
1524
14.4k
    for (auto *I : llvm::reverse(CD->inits())) {
1525
14.4k
      if (BuildOpts.AddVirtualBaseBranches && 
!VBaseSucc6.58k
&&
1526
14.4k
          
I->isBaseInitializer()6.50k
&&
I->isBaseVirtual()1.09k
) {
1527
        // We've reached the first virtual base init while iterating in reverse
1528
        // order. Make a new block for virtual base initializers so that we
1529
        // could skip them.
1530
257
        VBaseSucc = Succ = B ? 
B122
:
&cfg->getExit()135
;
1531
257
        Block = createBlock();
1532
257
      }
1533
14.4k
      B = addInitializer(I);
1534
14.4k
      if (badCFG)
1535
0
        return nullptr;
1536
14.4k
    }
1537
14.1k
    if (VBaseSucc) {
1538
      // Make a branch block for potentially skipping virtual base initializers.
1539
257
      Succ = VBaseSucc;
1540
257
      B = createBlock();
1541
257
      B->setTerminator(
1542
257
          CFGTerminator(nullptr, CFGTerminator::VirtualBaseBranch));
1543
257
      addSuccessor(B, Block, true);
1544
257
    }
1545
14.1k
  }
1546
1547
243k
  if (B)
1548
234k
    Succ = B;
1549
1550
  // Backpatch the gotos whose label -> block mappings we didn't know when we
1551
  // encountered them.
1552
243k
  for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
1553
244k
                                   E = BackpatchBlocks.end(); I != E; 
++I128
) {
1554
1555
128
    CFGBlock *B = I->block;
1556
128
    if (auto *G = dyn_cast<GotoStmt>(B->getTerminator())) {
1557
68
      LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
1558
      // If there is no target for the goto, then we are looking at an
1559
      // incomplete AST.  Handle this by not registering a successor.
1560
68
      if (LI == LabelMap.end())
1561
0
        continue;
1562
68
      JumpTarget JT = LI->second;
1563
68
      prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition,
1564
68
                                                JT.scopePosition);
1565
68
      prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
1566
68
                                             JT.scopePosition);
1567
68
      const VarDecl *VD = prependAutomaticObjScopeEndWithTerminator(
1568
68
          B, I->scopePosition, JT.scopePosition);
1569
68
      appendScopeBegin(JT.block, VD, G);
1570
68
      addSuccessor(B, JT.block);
1571
128
    };
1572
128
    if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) {
1573
60
      CFGBlock *Successor  = (I+1)->block;
1574
120
      for (auto *L : G->labels()) {
1575
120
        LabelMapTy::iterator LI = LabelMap.find(L->getLabel());
1576
        // If there is no target for the goto, then we are looking at an
1577
        // incomplete AST.  Handle this by not registering a successor.
1578
120
        if (LI == LabelMap.end())
1579
0
          continue;
1580
120
        JumpTarget JT = LI->second;
1581
        // Successor has been added, so skip it.
1582
120
        if (JT.block == Successor)
1583
13
          continue;
1584
107
        addSuccessor(B, JT.block);
1585
107
      }
1586
60
      I++;
1587
60
    }
1588
128
  }
1589
1590
  // Add successors to the Indirect Goto Dispatch block (if we have one).
1591
243k
  if (CFGBlock *B = cfg->getIndirectGotoBlock())
1592
21
    for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
1593
174
                              E = AddressTakenLabels.end(); I != E; 
++I153
) {
1594
      // Lookup the target block.
1595
153
      LabelMapTy::iterator LI = LabelMap.find(*I);
1596
1597
      // If there is no target block that contains label, then we are looking
1598
      // at an incomplete AST.  Handle this by not registering a successor.
1599
153
      if (LI == LabelMap.end()) 
continue0
;
1600
1601
153
      addSuccessor(B, LI->second.block);
1602
153
    }
1603
1604
  // Create an empty entry block that has no predecessors.
1605
243k
  cfg->setEntry(createBlock());
1606
1607
243k
  if (BuildOpts.AddRichCXXConstructors)
1608
45.3k
    assert(ConstructionContextMap.empty() &&
1609
243k
           "Not all construction contexts were cleaned up!");
1610
1611
0
  return std::move(cfg);
1612
243k
}
1613
1614
/// createBlock - Used to lazily create blocks that are connected
1615
///  to the current (global) succcessor.
1616
1.07M
CFGBlock *CFGBuilder::createBlock(bool add_successor) {
1617
1.07M
  CFGBlock *B = cfg->createBlock();
1618
1.07M
  if (add_successor && 
Succ682k
)
1619
438k
    addSuccessor(B, Succ);
1620
1.07M
  return B;
1621
1.07M
}
1622
1623
/// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
1624
/// CFG. It is *not* connected to the current (global) successor, and instead
1625
/// directly tied to the exit block in order to be reachable.
1626
1.31k
CFGBlock *CFGBuilder::createNoReturnBlock() {
1627
1.31k
  CFGBlock *B = createBlock(false);
1628
1.31k
  B->setHasNoReturnElement();
1629
1.31k
  addSuccessor(B, &cfg->getExit(), Succ);
1630
1.31k
  return B;
1631
1.31k
}
1632
1633
/// addInitializer - Add C++ base or member initializer element to CFG.
1634
14.4k
CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1635
14.4k
  if (!BuildOpts.AddInitializers)
1636
0
    return Block;
1637
1638
14.4k
  bool HasTemporaries = false;
1639
1640
  // Destructors of temporaries in initialization expression should be called
1641
  // after initialization finishes.
1642
14.4k
  Expr *Init = I->getInit();
1643
14.4k
  if (Init) {
1644
14.4k
    HasTemporaries = isa<ExprWithCleanups>(Init);
1645
1646
14.4k
    if (BuildOpts.AddTemporaryDtors && 
HasTemporaries14.1k
) {
1647
      // Generate destructors for temporaries in initialization expression.
1648
321
      TempDtorContext Context;
1649
321
      VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1650
321
                             /*ExternallyDestructed=*/false, Context);
1651
321
    }
1652
14.4k
  }
1653
1654
14.4k
  autoCreateBlock();
1655
14.4k
  appendInitializer(Block, I);
1656
1657
14.4k
  if (Init) {
1658
14.4k
    findConstructionContexts(
1659
14.4k
        ConstructionContextLayer::create(cfg->getBumpVectorContext(), I),
1660
14.4k
        Init);
1661
1662
14.4k
    if (HasTemporaries) {
1663
      // For expression with temporaries go directly to subexpression to omit
1664
      // generating destructors for the second time.
1665
321
      return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1666
321
    }
1667
14.0k
    if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1668
7.81k
      if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
1669
        // In general, appending the expression wrapped by a CXXDefaultInitExpr
1670
        // may cause the same Expr to appear more than once in the CFG. Doing it
1671
        // here is safe because there's only one initializer per field.
1672
143
        autoCreateBlock();
1673
143
        appendStmt(Block, Default);
1674
143
        if (Stmt *Child = Default->getExpr())
1675
143
          if (CFGBlock *R = Visit(Child))
1676
143
            Block = R;
1677
143
        return Block;
1678
143
      }
1679
7.81k
    }
1680
13.9k
    return Visit(Init);
1681
14.0k
  }
1682
1683
0
  return Block;
1684
14.4k
}
1685
1686
/// Retrieve the type of the temporary object whose lifetime was
1687
/// extended by a local reference with the given initializer.
1688
static QualType getReferenceInitTemporaryType(const Expr *Init,
1689
2.74k
                                              bool *FoundMTE = nullptr) {
1690
6.98k
  while (true) {
1691
    // Skip parentheses.
1692
6.98k
    Init = Init->IgnoreParens();
1693
1694
    // Skip through cleanups.
1695
6.98k
    if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {
1696
1.45k
      Init = EWC->getSubExpr();
1697
1.45k
      continue;
1698
1.45k
    }
1699
1700
    // Skip through the temporary-materialization expression.
1701
5.52k
    if (const MaterializeTemporaryExpr *MTE
1702
5.52k
          = dyn_cast<MaterializeTemporaryExpr>(Init)) {
1703
1.40k
      Init = MTE->getSubExpr();
1704
1.40k
      if (FoundMTE)
1705
979
        *FoundMTE = true;
1706
1.40k
      continue;
1707
1.40k
    }
1708
1709
    // Skip sub-object accesses into rvalues.
1710
4.12k
    SmallVector<const Expr *, 2> CommaLHSs;
1711
4.12k
    SmallVector<SubobjectAdjustment, 2> Adjustments;
1712
4.12k
    const Expr *SkippedInit =
1713
4.12k
        Init->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments);
1714
4.12k
    if (SkippedInit != Init) {
1715
1.37k
      Init = SkippedInit;
1716
1.37k
      continue;
1717
1.37k
    }
1718
1719
2.74k
    break;
1720
4.12k
  }
1721
1722
2.74k
  return Init->getType();
1723
2.74k
}
1724
1725
// TODO: Support adding LoopExit element to the CFG in case where the loop is
1726
// ended by ReturnStmt, GotoStmt or ThrowExpr.
1727
26.6k
void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
1728
26.6k
  if(!BuildOpts.AddLoopExit)
1729
26.4k
    return;
1730
254
  autoCreateBlock();
1731
254
  appendLoopExit(Block, LoopStmt);
1732
254
}
1733
1734
void CFGBuilder::getDeclsWithEndedScope(LocalScope::const_iterator B,
1735
590k
                                        LocalScope::const_iterator E, Stmt *S) {
1736
590k
  if (!BuildOpts.AddScopes)
1737
590k
    return;
1738
1739
223
  if (B == E)
1740
99
    return;
1741
1742
  // To go from B to E, one first goes up the scopes from B to P
1743
  // then sideways in one scope from P to P' and then down
1744
  // the scopes from P' to E.
1745
  // The lifetime of all objects between B and P end.
1746
124
  LocalScope::const_iterator P = B.shared_parent(E);
1747
124
  int Dist = B.distance(P);
1748
124
  if (Dist <= 0)
1749
0
    return;
1750
1751
326
  
for (LocalScope::const_iterator I = B; 124
I != P;
++I202
)
1752
202
    if (I.pointsToFirstDeclaredVar())
1753
154
      DeclsWithEndedScope.insert(*I);
1754
124
}
1755
1756
void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
1757
                                         LocalScope::const_iterator E,
1758
590k
                                         Stmt *S) {
1759
590k
  getDeclsWithEndedScope(B, E, S);
1760
590k
  if (BuildOpts.AddScopes)
1761
223
    addScopesEnd(B, E, S);
1762
590k
  if (BuildOpts.AddImplicitDtors)
1763
590k
    addAutomaticObjDtors(B, E, S);
1764
590k
  if (BuildOpts.AddLifetime)
1765
160
    addLifetimeEnds(B, E, S);
1766
590k
}
1767
1768
/// Add to current block automatic objects that leave the scope.
1769
void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B,
1770
160
                                 LocalScope::const_iterator E, Stmt *S) {
1771
160
  if (!BuildOpts.AddLifetime)
1772
0
    return;
1773
1774
160
  if (B == E)
1775
62
    return;
1776
1777
  // To go from B to E, one first goes up the scopes from B to P
1778
  // then sideways in one scope from P to P' and then down
1779
  // the scopes from P' to E.
1780
  // The lifetime of all objects between B and P end.
1781
98
  LocalScope::const_iterator P = B.shared_parent(E);
1782
98
  int dist = B.distance(P);
1783
98
  if (dist <= 0)
1784
2
    return;
1785
1786
  // We need to perform the scope leaving in reverse order
1787
96
  SmallVector<VarDecl *, 10> DeclsTrivial;
1788
96
  SmallVector<VarDecl *, 10> DeclsNonTrivial;
1789
96
  DeclsTrivial.reserve(dist);
1790
96
  DeclsNonTrivial.reserve(dist);
1791
1792
258
  for (LocalScope::const_iterator I = B; I != P; 
++I162
)
1793
162
    if (hasTrivialDestructor(*I))
1794
18
      DeclsTrivial.push_back(*I);
1795
144
    else
1796
144
      DeclsNonTrivial.push_back(*I);
1797
1798
96
  autoCreateBlock();
1799
  // object with trivial destructor end their lifetime last (when storage
1800
  // duration ends)
1801
96
  for (SmallVectorImpl<VarDecl *>::reverse_iterator I = DeclsTrivial.rbegin(),
1802
96
                                                    E = DeclsTrivial.rend();
1803
114
       I != E; 
++I18
)
1804
18
    appendLifetimeEnds(Block, *I, S);
1805
1806
96
  for (SmallVectorImpl<VarDecl *>::reverse_iterator
1807
96
           I = DeclsNonTrivial.rbegin(),
1808
96
           E = DeclsNonTrivial.rend();
1809
240
       I != E; 
++I144
)
1810
144
    appendLifetimeEnds(Block, *I, S);
1811
96
}
1812
1813
/// Add to current block markers for ending scopes.
1814
void CFGBuilder::addScopesEnd(LocalScope::const_iterator B,
1815
223
                              LocalScope::const_iterator E, Stmt *S) {
1816
  // If implicit destructors are enabled, we'll add scope ends in
1817
  // addAutomaticObjDtors.
1818
223
  if (BuildOpts.AddImplicitDtors)
1819
223
    return;
1820
1821
0
  autoCreateBlock();
1822
1823
0
  for (auto I = DeclsWithEndedScope.rbegin(), E = DeclsWithEndedScope.rend();
1824
0
       I != E; ++I)
1825
0
    appendScopeEnd(Block, *I, S);
1826
1827
0
  return;
1828
223
}
1829
1830
/// addAutomaticObjDtors - Add to current block automatic objects destructors
1831
/// for objects in range of local scope positions. Use S as trigger statement
1832
/// for destructors.
1833
void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
1834
590k
                                      LocalScope::const_iterator E, Stmt *S) {
1835
590k
  if (!BuildOpts.AddImplicitDtors)
1836
0
    return;
1837
1838
590k
  if (B == E)
1839
586k
    return;
1840
1841
  // We need to append the destructors in reverse order, but any one of them
1842
  // may be a no-return destructor which changes the CFG. As a result, buffer
1843
  // this sequence up and replay them in reverse order when appending onto the
1844
  // CFGBlock(s).
1845
3.51k
  SmallVector<VarDecl*, 10> Decls;
1846
3.51k
  Decls.reserve(B.distance(E));
1847
8.83k
  for (LocalScope::const_iterator I = B; I != E; 
++I5.32k
)
1848
5.32k
    Decls.push_back(*I);
1849
1850
3.51k
  for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
1851
3.51k
                                                   E = Decls.rend();
1852
8.83k
       I != E; 
++I5.32k
) {
1853
5.32k
    if (hasTrivialDestructor(*I)) {
1854
      // If AddScopes is enabled and *I is a first variable in a scope, add a
1855
      // ScopeEnd marker in a Block.
1856
50
      if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I)) {
1857
38
        autoCreateBlock();
1858
38
        appendScopeEnd(Block, *I, S);
1859
38
      }
1860
50
      continue;
1861
50
    }
1862
    // If this destructor is marked as a no-return destructor, we need to
1863
    // create a new block for the destructor which does not have as a successor
1864
    // anything built thus far: control won't flow out of this block.
1865
5.27k
    QualType Ty = (*I)->getType();
1866
5.27k
    if (Ty->isReferenceType()) {
1867
355
      Ty = getReferenceInitTemporaryType((*I)->getInit());
1868
355
    }
1869
5.27k
    Ty = Context->getBaseElementType(Ty);
1870
1871
5.27k
    if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
1872
87
      Block = createNoReturnBlock();
1873
5.18k
    else
1874
5.18k
      autoCreateBlock();
1875
1876
    // Add ScopeEnd just after automatic obj destructor.
1877
5.27k
    if (BuildOpts.AddScopes && 
DeclsWithEndedScope.count(*I)152
)
1878
116
      appendScopeEnd(Block, *I, S);
1879
5.27k
    appendAutomaticObjDtor(Block, *I, S);
1880
5.27k
  }
1881
3.51k
}
1882
1883
/// addImplicitDtorsForDestructor - Add implicit destructors generated for
1884
/// base and member objects in destructor.
1885
7.10k
void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
1886
7.10k
  assert(BuildOpts.AddImplicitDtors &&
1887
7.10k
         "Can be called only when dtors should be added");
1888
0
  const CXXRecordDecl *RD = DD->getParent();
1889
1890
  // At the end destroy virtual base objects.
1891
7.10k
  for (const auto &VI : RD->vbases()) {
1892
    // TODO: Add a VirtualBaseBranch to see if the most derived class
1893
    // (which is different from the current class) is responsible for
1894
    // destroying them.
1895
111
    const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
1896
111
    if (!CD->hasTrivialDestructor()) {
1897
100
      autoCreateBlock();
1898
100
      appendBaseDtor(Block, &VI);
1899
100
    }
1900
111
  }
1901
1902
  // Before virtual bases destroy direct base objects.
1903
7.10k
  for (const auto &BI : RD->bases()) {
1904
574
    if (!BI.isVirtual()) {
1905
484
      const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
1906
484
      if (!CD->hasTrivialDestructor()) {
1907
427
        autoCreateBlock();
1908
427
        appendBaseDtor(Block, &BI);
1909
427
      }
1910
484
    }
1911
574
  }
1912
1913
  // First destroy member objects.
1914
7.10k
  for (auto *FI : RD->fields()) {
1915
    // Check for constant size array. Set type to array element type.
1916
6.99k
    QualType QT = FI->getType();
1917
6.99k
    if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1918
2.69k
      if (AT->getSize() == 0)
1919
7
        continue;
1920
2.68k
      QT = AT->getElementType();
1921
2.68k
    }
1922
1923
6.98k
    if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1924
168
      if (!CD->hasTrivialDestructor()) {
1925
147
        autoCreateBlock();
1926
147
        appendMemberDtor(Block, FI);
1927
147
      }
1928
6.98k
  }
1929
7.10k
}
1930
1931
/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
1932
/// way return valid LocalScope object.
1933
4.90k
LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
1934
4.90k
  if (Scope)
1935
1.61k
    return Scope;
1936
3.28k
  llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
1937
3.28k
  return new (alloc.Allocate<LocalScope>())
1938
3.28k
      LocalScope(BumpVectorContext(alloc), ScopePos);
1939
4.90k
}
1940
1941
/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
1942
/// that should create implicit scope (e.g. if/else substatements).
1943
449k
void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
1944
449k
  if (!BuildOpts.AddImplicitDtors && 
!BuildOpts.AddLifetime94
&&
1945
449k
      
!BuildOpts.AddScopes2
)
1946
2
    return;
1947
1948
449k
  LocalScope *Scope = nullptr;
1949
1950
  // For compound statement we will be creating explicit scope.
1951
449k
  if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
1952
674k
    for (auto *BI : CS->body()) {
1953
674k
      Stmt *SI = BI->stripLabelLikeStatements();
1954
674k
      if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
1955
154k
        Scope = addLocalScopeForDeclStmt(DS, Scope);
1956
674k
    }
1957
312k
    return;
1958
312k
  }
1959
1960
  // For any other statement scope will be implicit and as such will be
1961
  // interesting only for DeclStmt.
1962
137k
  if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
1963
24.9k
    addLocalScopeForDeclStmt(DS);
1964
137k
}
1965
1966
/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
1967
/// reuse Scope if not NULL.
1968
LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
1969
179k
                                                 LocalScope* Scope) {
1970
179k
  if (!BuildOpts.AddImplicitDtors && 
!BuildOpts.AddLifetime92
&&
1971
179k
      
!BuildOpts.AddScopes0
)
1972
0
    return Scope;
1973
1974
179k
  for (auto *DI : DS->decls())
1975
185k
    if (VarDecl *VD = dyn_cast<VarDecl>(DI))
1976
174k
      Scope = addLocalScopeForVarDecl(VD, Scope);
1977
179k
  return Scope;
1978
179k
}
1979
1980
177k
bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) {
1981
  // Check for const references bound to temporary. Set type to pointee.
1982
177k
  QualType QT = VD->getType();
1983
177k
  if (QT->isReferenceType()) {
1984
    // Attempt to determine whether this declaration lifetime-extends a
1985
    // temporary.
1986
    //
1987
    // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
1988
    // temporaries, and a single declaration can extend multiple temporaries.
1989
    // We should look at the storage duration on each nested
1990
    // MaterializeTemporaryExpr instead.
1991
1992
2.35k
    const Expr *Init = VD->getInit();
1993
2.35k
    if (!Init) {
1994
      // Probably an exception catch-by-reference variable.
1995
      // FIXME: It doesn't really mean that the object has a trivial destructor.
1996
      // Also are there other cases?
1997
28
      return true;
1998
28
    }
1999
2000
    // Lifetime-extending a temporary?
2001
2.32k
    bool FoundMTE = false;
2002
2.32k
    QT = getReferenceInitTemporaryType(Init, &FoundMTE);
2003
2.32k
    if (!FoundMTE)
2004
1.34k
      return true;
2005
2.32k
  }
2006
2007
  // Check for constant size array. Set type to array element type.
2008
185k
  
while (const ConstantArrayType *176k
AT = Context->getAsConstantArrayType(QT)) {
2009
9.16k
    if (AT->getSize() == 0)
2010
23
      return true;
2011
9.13k
    QT = AT->getElementType();
2012
9.13k
  }
2013
2014
  // Check if type is a C++ class with non-trivial destructor.
2015
176k
  if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2016
25.6k
    return !CD->hasDefinition() || 
CD->hasTrivialDestructor()25.6k
;
2017
150k
  return true;
2018
176k
}
2019
2020
/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
2021
/// create add scope for automatic objects and temporary objects bound to
2022
/// const reference. Will reuse Scope if not NULL.
2023
LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
2024
174k
                                                LocalScope* Scope) {
2025
174k
  assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
2026
174k
         "AddImplicitDtors and AddLifetime cannot be used at the same time");
2027
174k
  if (!BuildOpts.AddImplicitDtors && 
!BuildOpts.AddLifetime104
&&
2028
174k
      
!BuildOpts.AddScopes0
)
2029
0
    return Scope;
2030
2031
  // Check if variable is local.
2032
174k
  switch (VD->getStorageClass()) {
2033
171k
  case SC_None:
2034
171k
  case SC_Auto:
2035
172k
  case SC_Register:
2036
172k
    break;
2037
2.60k
  default: return Scope;
2038
174k
  }
2039
2040
172k
  if (BuildOpts.AddImplicitDtors) {
2041
171k
    if (!hasTrivialDestructor(VD) || 
BuildOpts.AddScopes167k
) {
2042
      // Add the variable to scope
2043
4.79k
      Scope = createOrReuseLocalScope(Scope);
2044
4.79k
      Scope->addVar(VD);
2045
4.79k
      ScopePos = Scope->begin();
2046
4.79k
    }
2047
171k
    return Scope;
2048
171k
  }
2049
2050
104
  assert(BuildOpts.AddLifetime);
2051
  // Add the variable to scope
2052
0
  Scope = createOrReuseLocalScope(Scope);
2053
104
  Scope->addVar(VD);
2054
104
  ScopePos = Scope->begin();
2055
104
  return Scope;
2056
172k
}
2057
2058
/// addLocalScopeAndDtors - For given statement add local scope for it and
2059
/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
2060
111k
void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
2061
111k
  LocalScope::const_iterator scopeBeginPos = ScopePos;
2062
111k
  addLocalScopeForStmt(S);
2063
111k
  addAutomaticObjHandling(ScopePos, scopeBeginPos, S);
2064
111k
}
2065
2066
/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
2067
/// variables with automatic storage duration to CFGBlock's elements vector.
2068
/// Elements will be prepended to physical beginning of the vector which
2069
/// happens to be logical end. Use blocks terminator as statement that specifies
2070
/// destructors call site.
2071
/// FIXME: This mechanism for adding automatic destructors doesn't handle
2072
/// no-return destructors properly.
2073
void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
2074
68
    LocalScope::const_iterator B, LocalScope::const_iterator E) {
2075
68
  if (!BuildOpts.AddImplicitDtors)
2076
2
    return;
2077
66
  BumpVectorContext &C = cfg->getBumpVectorContext();
2078
66
  CFGBlock::iterator InsertPos
2079
66
    = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
2080
89
  for (LocalScope::const_iterator I = B; I != E; 
++I23
)
2081
23
    InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
2082
23
                                            Blk->getTerminatorStmt());
2083
66
}
2084
2085
/// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for
2086
/// variables with automatic storage duration to CFGBlock's elements vector.
2087
/// Elements will be prepended to physical beginning of the vector which
2088
/// happens to be logical end. Use blocks terminator as statement that specifies
2089
/// where lifetime ends.
2090
void CFGBuilder::prependAutomaticObjLifetimeWithTerminator(
2091
68
    CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
2092
68
  if (!BuildOpts.AddLifetime)
2093
66
    return;
2094
2
  BumpVectorContext &C = cfg->getBumpVectorContext();
2095
2
  CFGBlock::iterator InsertPos =
2096
2
      Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C);
2097
4
  for (LocalScope::const_iterator I = B; I != E; 
++I2
) {
2098
2
    InsertPos =
2099
2
        Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminatorStmt());
2100
2
  }
2101
2
}
2102
2103
/// prependAutomaticObjScopeEndWithTerminator - Prepend scope end CFGElements for
2104
/// variables with automatic storage duration to CFGBlock's elements vector.
2105
/// Elements will be prepended to physical beginning of the vector which
2106
/// happens to be logical end. Use blocks terminator as statement that specifies
2107
/// where scope ends.
2108
const VarDecl *
2109
CFGBuilder::prependAutomaticObjScopeEndWithTerminator(
2110
68
    CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
2111
68
  if (!BuildOpts.AddScopes)
2112
66
    return nullptr;
2113
2
  BumpVectorContext &C = cfg->getBumpVectorContext();
2114
2
  CFGBlock::iterator InsertPos =
2115
2
      Blk->beginScopeEndInsert(Blk->end(), 1, C);
2116
2
  LocalScope::const_iterator PlaceToInsert = B;
2117
8
  for (LocalScope::const_iterator I = B; I != E; 
++I6
)
2118
6
    PlaceToInsert = I;
2119
2
  Blk->insertScopeEnd(InsertPos, *PlaceToInsert, Blk->getTerminatorStmt());
2120
2
  return *PlaceToInsert;
2121
68
}
2122
2123
/// Visit - Walk the subtree of a statement and add extra
2124
///   blocks for ternary operators, &&, and ||.  We also process "," and
2125
///   DeclStmts (which may contain nested control-flow).
2126
CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
2127
5.39M
                            bool ExternallyDestructed) {
2128
5.39M
  if (!S) {
2129
1
    badCFG = true;
2130
1
    return nullptr;
2131
1
  }
2132
2133
5.39M
  if (Expr *E = dyn_cast<Expr>(S))
2134
4.52M
    S = E->IgnoreParens();
2135
2136
5.39M
  if (Context->getLangOpts().OpenMP)
2137
497k
    if (auto *D = dyn_cast<OMPExecutableDirective>(S))
2138
20.9k
      return VisitOMPExecutableDirective(D, asc);
2139
2140
5.37M
  switch (S->getStmtClass()) {
2141
1.94M
    default:
2142
1.94M
      return VisitStmt(S, asc);
2143
2144
2.28k
    case Stmt::ImplicitValueInitExprClass:
2145
2.28k
      if (BuildOpts.OmitImplicitValueInitializers)
2146
189
        return Block;
2147
2.09k
      return VisitStmt(S, asc);
2148
2149
6.95k
    case Stmt::InitListExprClass:
2150
6.95k
      return VisitInitListExpr(cast<InitListExpr>(S), asc);
2151
2152
254
    case Stmt::AddrLabelExprClass:
2153
254
      return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
2154
2155
185
    case Stmt::BinaryConditionalOperatorClass:
2156
185
      return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
2157
2158
226k
    case Stmt::BinaryOperatorClass:
2159
226k
      return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
2160
2161
1.68k
    case Stmt::BlockExprClass:
2162
1.68k
      return VisitBlockExpr(cast<BlockExpr>(S), asc);
2163
2164
6.52k
    case Stmt::BreakStmtClass:
2165
6.52k
      return VisitBreakStmt(cast<BreakStmt>(S));
2166
2167
283k
    case Stmt::CallExprClass:
2168
291k
    case Stmt::CXXOperatorCallExprClass:
2169
315k
    case Stmt::CXXMemberCallExprClass:
2170
315k
    case Stmt::UserDefinedLiteralClass:
2171
315k
      return VisitCallExpr(cast<CallExpr>(S), asc);
2172
2173
2.02k
    case Stmt::CaseStmtClass:
2174
2.02k
      return VisitCaseStmt(cast<CaseStmt>(S));
2175
2176
0
    case Stmt::ChooseExprClass:
2177
0
      return VisitChooseExpr(cast<ChooseExpr>(S), asc);
2178
2179
308k
    case Stmt::CompoundStmtClass:
2180
308k
      return VisitCompoundStmt(cast<CompoundStmt>(S), ExternallyDestructed);
2181
2182
2.70k
    case Stmt::ConditionalOperatorClass:
2183
2.70k
      return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
2184
2185
10.9k
    case Stmt::ContinueStmtClass:
2186
10.9k
      return VisitContinueStmt(cast<ContinueStmt>(S));
2187
2188
0
    case Stmt::CXXCatchStmtClass:
2189
0
      return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
2190
2191
8.86k
    case Stmt::ExprWithCleanupsClass:
2192
8.86k
      return VisitExprWithCleanups(cast<ExprWithCleanups>(S),
2193
8.86k
                                   asc, ExternallyDestructed);
2194
2195
5.05k
    case Stmt::CXXDefaultArgExprClass:
2196
5.37k
    case Stmt::CXXDefaultInitExprClass:
2197
      // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
2198
      // called function's declaration, not by the caller. If we simply add
2199
      // this expression to the CFG, we could end up with the same Expr
2200
      // appearing multiple times.
2201
      // PR13385 / <rdar://problem/12156507>
2202
      //
2203
      // It's likewise possible for multiple CXXDefaultInitExprs for the same
2204
      // expression to be used in the same function (through aggregate
2205
      // initialization).
2206
5.37k
      return VisitStmt(S, asc);
2207
2208
6.03k
    case Stmt::CXXBindTemporaryExprClass:
2209
6.03k
      return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
2210
2211
36.3k
    case Stmt::CXXConstructExprClass:
2212
36.3k
      return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
2213
2214
2.45k
    case Stmt::CXXNewExprClass:
2215
2.45k
      return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);
2216
2217
1.14k
    case Stmt::CXXDeleteExprClass:
2218
1.14k
      return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);
2219
2220
3.24k
    case Stmt::CXXFunctionalCastExprClass:
2221
3.24k
      return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
2222
2223
4.64k
    case Stmt::CXXTemporaryObjectExprClass:
2224
4.64k
      return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
2225
2226
194
    case Stmt::CXXThrowExprClass:
2227
194
      return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
2228
2229
185
    case Stmt::CXXTryStmtClass:
2230
185
      return VisitCXXTryStmt(cast<CXXTryStmt>(S));
2231
2232
213
    case Stmt::CXXForRangeStmtClass:
2233
213
      return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
2234
2235
179k
    case Stmt::DeclStmtClass:
2236
179k
      return VisitDeclStmt(cast<DeclStmt>(S));
2237
2238
382
    case Stmt::DefaultStmtClass:
2239
382
      return VisitDefaultStmt(cast<DefaultStmt>(S));
2240
2241
593
    case Stmt::DoStmtClass:
2242
593
      return VisitDoStmt(cast<DoStmt>(S));
2243
2244
24.8k
    case Stmt::ForStmtClass:
2245
24.8k
      return VisitForStmt(cast<ForStmt>(S));
2246
2247
222
    case Stmt::GotoStmtClass:
2248
222
      return VisitGotoStmt(cast<GotoStmt>(S));
2249
2250
366
    case Stmt::GCCAsmStmtClass:
2251
366
      return VisitGCCAsmStmt(cast<GCCAsmStmt>(S), asc);
2252
2253
113k
    case Stmt::IfStmtClass:
2254
113k
      return VisitIfStmt(cast<IfStmt>(S));
2255
2256
1.66M
    case Stmt::ImplicitCastExprClass:
2257
1.66M
      return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
2258
2259
71
    case Stmt::ConstantExprClass:
2260
71
      return VisitConstantExpr(cast<ConstantExpr>(S), asc);
2261
2262
24
    case Stmt::IndirectGotoStmtClass:
2263
24
      return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
2264
2265
585
    case Stmt::LabelStmtClass:
2266
585
      return VisitLabelStmt(cast<LabelStmt>(S));
2267
2268
1.25k
    case Stmt::LambdaExprClass:
2269
1.25k
      return VisitLambdaExpr(cast<LambdaExpr>(S), asc);
2270
2271
18.5k
    case Stmt::MaterializeTemporaryExprClass:
2272
18.5k
      return VisitMaterializeTemporaryExpr(cast<MaterializeTemporaryExpr>(S),
2273
18.5k
                                           asc);
2274
2275
149k
    case Stmt::MemberExprClass:
2276
149k
      return VisitMemberExpr(cast<MemberExpr>(S), asc);
2277
2278
10.8k
    case Stmt::NullStmtClass:
2279
10.8k
      return Block;
2280
2281
0
    case Stmt::ObjCAtCatchStmtClass:
2282
0
      return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
2283
2284
190
    case Stmt::ObjCAutoreleasePoolStmtClass:
2285
190
    return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S));
2286
2287
75
    case Stmt::ObjCAtSynchronizedStmtClass:
2288
75
      return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
2289
2290
13
    case Stmt::ObjCAtThrowStmtClass:
2291
13
      return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
2292
2293
167
    case Stmt::ObjCAtTryStmtClass:
2294
167
      return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
2295
2296
230
    case Stmt::ObjCForCollectionStmtClass:
2297
230
      return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
2298
2299
17.8k
    case Stmt::ObjCMessageExprClass:
2300
17.8k
      return VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), asc);
2301
2302
3.52k
    case Stmt::OpaqueValueExprClass:
2303
3.52k
      return Block;
2304
2305
2.28k
    case Stmt::PseudoObjectExprClass:
2306
2.28k
      return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));
2307
2308
181k
    case Stmt::ReturnStmtClass:
2309
181k
    case Stmt::CoreturnStmtClass:
2310
181k
      return VisitReturnStmt(S);
2311
2312
0
    case Stmt::SEHExceptStmtClass:
2313
0
      return VisitSEHExceptStmt(cast<SEHExceptStmt>(S));
2314
2315
0
    case Stmt::SEHFinallyStmtClass:
2316
0
      return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S));
2317
2318
10
    case Stmt::SEHLeaveStmtClass:
2319
10
      return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S));
2320
2321
70
    case Stmt::SEHTryStmtClass:
2322
70
      return VisitSEHTryStmt(cast<SEHTryStmt>(S));
2323
2324
7.55k
    case Stmt::UnaryExprOrTypeTraitExprClass:
2325
7.55k
      return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
2326
7.55k
                                           asc);
2327
2328
3.73k
    case Stmt::StmtExprClass:
2329
3.73k
      return VisitStmtExpr(cast<StmtExpr>(S), asc);
2330
2331
838
    case Stmt::SwitchStmtClass:
2332
838
      return VisitSwitchStmt(cast<SwitchStmt>(S));
2333
2334
98.4k
    case Stmt::UnaryOperatorClass:
2335
98.4k
      return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
2336
2337
1.28k
    case Stmt::WhileStmtClass:
2338
1.28k
      return VisitWhileStmt(cast<WhileStmt>(S));
2339
5.37M
  }
2340
5.37M
}
2341
2342
1.96M
CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
2343
1.96M
  if (asc.alwaysAdd(*this, S)) {
2344
1.63M
    autoCreateBlock();
2345
1.63M
    appendStmt(Block, S);
2346
1.63M
  }
2347
2348
1.96M
  return VisitChildren(S);
2349
1.96M
}
2350
2351
/// VisitChildren - Visit the children of a Stmt.
2352
2.34M
CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
2353
2.34M
  CFGBlock *B = Block;
2354
2355
  // Visit the children in their reverse order so that they appear in
2356
  // left-to-right (natural) order in the CFG.
2357
2.34M
  reverse_children RChildren(S);
2358
2.34M
  for (Stmt *Child : RChildren) {
2359
1.30M
    if (Child)
2360
1.30M
      if (CFGBlock *R = Visit(Child))
2361
1.30M
        B = R;
2362
1.30M
  }
2363
2.34M
  return B;
2364
2.34M
}
2365
2366
6.95k
CFGBlock *CFGBuilder::VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc) {
2367
6.95k
  if (asc.alwaysAdd(*this, ILE)) {
2368
2.49k
    autoCreateBlock();
2369
2.49k
    appendStmt(Block, ILE);
2370
2.49k
  }
2371
6.95k
  CFGBlock *B = Block;
2372
2373
6.95k
  reverse_children RChildren(ILE);
2374
15.1k
  for (Stmt *Child : RChildren) {
2375
15.1k
    if (!Child)
2376
0
      continue;
2377
15.1k
    if (CFGBlock *R = Visit(Child))
2378
15.1k
      B = R;
2379
15.1k
    if (BuildOpts.AddCXXDefaultInitExprInAggregates) {
2380
4
      if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Child))
2381
2
        if (Stmt *Child = DIE->getExpr())
2382
2
          if (CFGBlock *R = Visit(Child))
2383
2
            B = R;
2384
4
    }
2385
15.1k
  }
2386
6.95k
  return B;
2387
6.95k
}
2388
2389
CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
2390
254
                                         AddStmtChoice asc) {
2391
254
  AddressTakenLabels.insert(A->getLabel());
2392
2393
254
  if (asc.alwaysAdd(*this, A)) {
2394
166
    autoCreateBlock();
2395
166
    appendStmt(Block, A);
2396
166
  }
2397
2398
254
  return Block;
2399
254
}
2400
2401
CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
2402
98.4k
           AddStmtChoice asc) {
2403
98.4k
  if (asc.alwaysAdd(*this, U)) {
2404
98.4k
    autoCreateBlock();
2405
98.4k
    appendStmt(Block, U);
2406
98.4k
  }
2407
2408
98.4k
  if (U->getOpcode() == UO_LNot)
2409
2.71k
    tryEvaluateBool(U->getSubExpr()->IgnoreParens());
2410
2411
98.4k
  return Visit(U->getSubExpr(), AddStmtChoice());
2412
98.4k
}
2413
2414
1.67k
CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
2415
1.67k
  CFGBlock *ConfluenceBlock = Block ? 
Block1.62k
:
createBlock()50
;
2416
1.67k
  appendStmt(ConfluenceBlock, B);
2417
2418
1.67k
  if (badCFG)
2419
0
    return nullptr;
2420
2421
1.67k
  return VisitLogicalOperator(B, nullptr, ConfluenceBlock,
2422
1.67k
                              ConfluenceBlock).first;
2423
1.67k
}
2424
2425
std::pair<CFGBlock*, CFGBlock*>
2426
CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
2427
                                 Stmt *Term,
2428
                                 CFGBlock *TrueBlock,
2429
13.4k
                                 CFGBlock *FalseBlock) {
2430
  // Introspect the RHS.  If it is a nested logical operation, we recursively
2431
  // build the CFG using this function.  Otherwise, resort to default
2432
  // CFG construction behavior.
2433
13.4k
  Expr *RHS = B->getRHS()->IgnoreParens();
2434
13.4k
  CFGBlock *RHSBlock, *ExitBlock;
2435
2436
13.4k
  do {
2437
13.4k
    if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS))
2438
7.69k
      if (B_RHS->isLogicalOp()) {
2439
295
        std::tie(RHSBlock, ExitBlock) =
2440
295
          VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock);
2441
295
        break;
2442
295
      }
2443
2444
    // The RHS is not a nested logical operation.  Don't push the terminator
2445
    // down further, but instead visit RHS and construct the respective
2446
    // pieces of the CFG, and link up the RHSBlock with the terminator
2447
    // we have been provided.
2448
13.1k
    ExitBlock = RHSBlock = createBlock(false);
2449
2450
    // Even though KnownVal is only used in the else branch of the next
2451
    // conditional, tryEvaluateBool performs additional checking on the
2452
    // Expr, so it should be called unconditionally.
2453
13.1k
    TryResult KnownVal = tryEvaluateBool(RHS);
2454
13.1k
    if (!KnownVal.isKnown())
2455
12.9k
      KnownVal = tryEvaluateBool(B);
2456
2457
13.1k
    if (!Term) {
2458
1.67k
      assert(TrueBlock == FalseBlock);
2459
0
      addSuccessor(RHSBlock, TrueBlock);
2460
1.67k
    }
2461
11.5k
    else {
2462
11.5k
      RHSBlock->setTerminator(Term);
2463
11.5k
      addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse());
2464
11.5k
      addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue());
2465
11.5k
    }
2466
2467
0
    Block = RHSBlock;
2468
13.1k
    RHSBlock = addStmt(RHS);
2469
13.1k
  }
2470
13.4k
  while (
false13.1k
);
2471
2472
13.4k
  if (badCFG)
2473
0
    return std::make_pair(nullptr, nullptr);
2474
2475
  // Generate the blocks for evaluating the LHS.
2476
13.4k
  Expr *LHS = B->getLHS()->IgnoreParens();
2477
2478
13.4k
  if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS))
2479
6.99k
    if (B_LHS->isLogicalOp()) {
2480
4.71k
      if (B->getOpcode() == BO_LOr)
2481
481
        FalseBlock = RHSBlock;
2482
4.23k
      else
2483
4.23k
        TrueBlock = RHSBlock;
2484
2485
      // For the LHS, treat 'B' as the terminator that we want to sink
2486
      // into the nested branch.  The RHS always gets the top-most
2487
      // terminator.
2488
4.71k
      return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock);
2489
4.71k
    }
2490
2491
  // Create the block evaluating the LHS.
2492
  // This contains the '&&' or '||' as the terminator.
2493
8.77k
  CFGBlock *LHSBlock = createBlock(false);
2494
8.77k
  LHSBlock->setTerminator(B);
2495
2496
8.77k
  Block = LHSBlock;
2497
8.77k
  CFGBlock *EntryLHSBlock = addStmt(LHS);
2498
2499
8.77k
  if (badCFG)
2500
0
    return std::make_pair(nullptr, nullptr);
2501
2502
  // See if this is a known constant.
2503
8.77k
  TryResult KnownVal = tryEvaluateBool(LHS);
2504
2505
  // Now link the LHSBlock with RHSBlock.
2506
8.77k
  if (B->getOpcode() == BO_LOr) {
2507
775
    addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse());
2508
775
    addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue());
2509
7.99k
  } else {
2510
7.99k
    assert(B->getOpcode() == BO_LAnd);
2511
0
    addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse());
2512
7.99k
    addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue());
2513
7.99k
  }
2514
2515
0
  return std::make_pair(EntryLHSBlock, ExitBlock);
2516
8.77k
}
2517
2518
CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
2519
226k
                                          AddStmtChoice asc) {
2520
   // && or ||
2521
226k
  if (B->isLogicalOp())
2522
1.67k
    return VisitLogicalOperator(B);
2523
2524
225k
  if (B->getOpcode() == BO_Comma) { // ,
2525
1.02k
    autoCreateBlock();
2526
1.02k
    appendStmt(Block, B);
2527
1.02k
    addStmt(B->getRHS());
2528
1.02k
    return addStmt(B->getLHS());
2529
1.02k
  }
2530
2531
224k
  if (B->isAssignmentOp()) {
2532
78.1k
    if (asc.alwaysAdd(*this, B)) {
2533
78.1k
      autoCreateBlock();
2534
78.1k
      appendStmt(Block, B);
2535
78.1k
    }
2536
78.1k
    Visit(B->getLHS());
2537
78.1k
    return Visit(B->getRHS());
2538
78.1k
  }
2539
2540
145k
  if (asc.alwaysAdd(*this, B)) {
2541
145k
    autoCreateBlock();
2542
145k
    appendStmt(Block, B);
2543
145k
  }
2544
2545
145k
  if (B->isEqualityOp() || 
B->isRelationalOp()114k
)
2546
76.6k
    tryEvaluateBool(B);
2547
2548
145k
  CFGBlock *RBlock = Visit(B->getRHS());
2549
145k
  CFGBlock *LBlock = Visit(B->getLHS());
2550
  // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
2551
  // containing a DoStmt, and the LHS doesn't create a new block, then we should
2552
  // return RBlock.  Otherwise we'll incorrectly return NULL.
2553
145k
  return (LBlock ? LBlock : 
RBlock0
);
2554
224k
}
2555
2556
2.93k
CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
2557
2.93k
  if (asc.alwaysAdd(*this, E)) {
2558
2.33k
    autoCreateBlock();
2559
2.33k
    appendStmt(Block, E);
2560
2.33k
  }
2561
2.93k
  return Block;
2562
2.93k
}
2563
2564
6.52k
CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
2565
  // "break" is a control-flow statement.  Thus we stop processing the current
2566
  // block.
2567
6.52k
  if (badCFG)
2568
0
    return nullptr;
2569
2570
  // Now create a new block that ends with the break statement.
2571
6.52k
  Block = createBlock(false);
2572
6.52k
  Block->setTerminator(B);
2573
2574
  // If there is no target for the break, then we are looking at an incomplete
2575
  // AST.  This means that the CFG cannot be constructed.
2576
6.52k
  if (BreakJumpTarget.block) {
2577
6.52k
    addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B);
2578
6.52k
    addSuccessor(Block, BreakJumpTarget.block);
2579
6.52k
  } else
2580
0
    badCFG = true;
2581
2582
6.52k
  return Block;
2583
6.52k
}
2584
2585
315k
static bool CanThrow(Expr *E, ASTContext &Ctx) {
2586
315k
  QualType Ty = E->getType();
2587
315k
  if (Ty->isFunctionPointerType() || 
Ty->isBlockPointerType()24.9k
)
2588
291k
    Ty = Ty->getPointeeType();
2589
2590
315k
  const FunctionType *FT = Ty->getAs<FunctionType>();
2591
315k
  if (FT) {
2592
291k
    if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
2593
286k
      if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) &&
2594
286k
          Proto->isNothrow())
2595
6.51k
        return false;
2596
291k
  }
2597
308k
  return true;
2598
315k
}
2599
2600
315k
CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
2601
  // Compute the callee type.
2602
315k
  QualType calleeType = C->getCallee()->getType();
2603
315k
  if (calleeType == Context->BoundMemberTy) {
2604
24.1k
    QualType boundType = Expr::findBoundMemberType(C->getCallee());
2605
2606
    // We should only get a null bound type if processing a dependent
2607
    // CFG.  Recover by assuming nothing.
2608
24.1k
    if (!boundType.isNull()) 
calleeType = boundType24.1k
;
2609
24.1k
  }
2610
2611
  // If this is a call to a no-return function, this stops the block here.
2612
315k
  bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
2613
2614
315k
  bool AddEHEdge = false;
2615
2616
  // Languages without exceptions are assumed to not throw.
2617
315k
  if (Context->getLangOpts().Exceptions) {
2618
8.39k
    if (BuildOpts.AddEHEdges)
2619
0
      AddEHEdge = true;
2620
8.39k
  }
2621
2622
  // If this is a call to a builtin function, it might not actually evaluate
2623
  // its arguments. Don't add them to the CFG if this is the case.
2624
315k
  bool OmitArguments = false;
2625
2626
315k
  if (FunctionDecl *FD = C->getDirectCallee()) {
2627
    // TODO: Support construction contexts for variadic function arguments.
2628
    // These are a bit problematic and not very useful because passing
2629
    // C++ objects as C-style variadic arguments doesn't work in general
2630
    // (see [expr.call]).
2631
309k
    if (!FD->isVariadic())
2632
240k
      findConstructionContextsForArguments(C);
2633
2634
309k
    if (FD->isNoReturn() || 
C->isBuiltinAssumeFalse(*Context)308k
)
2635
945
      NoReturn = true;
2636
309k
    if (FD->hasAttr<NoThrowAttr>())
2637
78.5k
      AddEHEdge = false;
2638
309k
    if (FD->getBuiltinID() == Builtin::BI__builtin_object_size ||
2639
309k
        
FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size308k
)
2640
388
      OmitArguments = true;
2641
309k
  }
2642
2643
315k
  if (!CanThrow(C->getCallee(), *Context))
2644
6.51k
    AddEHEdge = false;
2645
2646
315k
  if (OmitArguments) {
2647
388
    assert(!NoReturn && "noreturn calls with unevaluated args not implemented");
2648
0
    assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
2649
0
    autoCreateBlock();
2650
388
    appendStmt(Block, C);
2651
388
    return Visit(C->getCallee());
2652
388
  }
2653
2654
314k
  if (!NoReturn && 
!AddEHEdge313k
) {
2655
313k
    autoCreateBlock();
2656
313k
    appendCall(Block, C);
2657
2658
313k
    return VisitChildren(C);
2659
313k
  }
2660
2661
947
  if (Block) {
2662
166
    Succ = Block;
2663
166
    if (badCFG)
2664
0
      return nullptr;
2665
166
  }
2666
2667
947
  if (NoReturn)
2668
947
    Block = createNoReturnBlock();
2669
0
  else
2670
0
    Block = createBlock();
2671
2672
947
  appendCall(Block, C);
2673
2674
947
  if (AddEHEdge) {
2675
    // Add exceptional edges.
2676
0
    if (TryTerminatedBlock)
2677
0
      addSuccessor(Block, TryTerminatedBlock);
2678
0
    else
2679
0
      addSuccessor(Block, &cfg->getExit());
2680
0
  }
2681
2682
947
  return VisitChildren(C);
2683
947
}
2684
2685
CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
2686
0
                                      AddStmtChoice asc) {
2687
0
  CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2688
0
  appendStmt(ConfluenceBlock, C);
2689
0
  if (badCFG)
2690
0
    return nullptr;
2691
2692
0
  AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2693
0
  Succ = ConfluenceBlock;
2694
0
  Block = nullptr;
2695
0
  CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
2696
0
  if (badCFG)
2697
0
    return nullptr;
2698
2699
0
  Succ = ConfluenceBlock;
2700
0
  Block = nullptr;
2701
0
  CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
2702
0
  if (badCFG)
2703
0
    return nullptr;
2704
2705
0
  Block = createBlock(false);
2706
  // See if this is a known constant.
2707
0
  const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2708
0
  addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock);
2709
0
  addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock);
2710
0
  Block->setTerminator(C);
2711
0
  return addStmt(C->getCond());
2712
0
}
2713
2714
312k
CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed) {
2715
312k
  LocalScope::const_iterator scopeBeginPos = ScopePos;
2716
312k
  addLocalScopeForStmt(C);
2717
2718
312k
  if (!C->body_empty() && 
!isa<ReturnStmt>(*C->body_rbegin())286k
) {
2719
    // If the body ends with a ReturnStmt, the dtors will be added in
2720
    // VisitReturnStmt.
2721
113k
    addAutomaticObjHandling(ScopePos, scopeBeginPos, C);
2722
113k
  }
2723
2724
312k
  CFGBlock *LastBlock = Block;
2725
2726
312k
  for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
2727
986k
       I != E; 
++I674k
) {
2728
    // If we hit a segment of code just containing ';' (NullStmts), we can
2729
    // get a null block back.  In such cases, just use the LastBlock
2730
674k
    CFGBlock *newBlock = Visit(*I, AddStmtChoice::AlwaysAdd,
2731
674k
                               ExternallyDestructed);
2732
2733
674k
    if (newBlock)
2734
673k
      LastBlock = newBlock;
2735
2736
674k
    if (badCFG)
2737
202
      return nullptr;
2738
2739
674k
    ExternallyDestructed = false;
2740
674k
  }
2741
2742
311k
  return LastBlock;
2743
312k
}
2744
2745
CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
2746
2.88k
                                               AddStmtChoice asc) {
2747
2.88k
  const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
2748
2.88k
  const OpaqueValueExpr *opaqueValue = (BCO ? 
BCO->getOpaqueValue()185
:
nullptr2.70k
);
2749
2750
  // Create the confluence block that will "merge" the results of the ternary
2751
  // expression.
2752
2.88k
  CFGBlock *ConfluenceBlock = Block ? 
Block2.22k
:
createBlock()664
;
2753
2.88k
  appendStmt(ConfluenceBlock, C);
2754
2.88k
  if (badCFG)
2755
0
    return nullptr;
2756
2757
2.88k
  AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2758
2759
  // Create a block for the LHS expression if there is an LHS expression.  A
2760
  // GCC extension allows LHS to be NULL, causing the condition to be the
2761
  // value that is returned instead.
2762
  //  e.g: x ?: y is shorthand for: x ? x : y;
2763
2.88k
  Succ = ConfluenceBlock;
2764
2.88k
  Block = nullptr;
2765
2.88k
  CFGBlock *LHSBlock = nullptr;
2766
2.88k
  const Expr *trueExpr = C->getTrueExpr();
2767
2.88k
  if (trueExpr != opaqueValue) {
2768
2.76k
    LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
2769
2.76k
    if (badCFG)
2770
0
      return nullptr;
2771
2.76k
    Block = nullptr;
2772
2.76k
  }
2773
119
  else
2774
119
    LHSBlock = ConfluenceBlock;
2775
2776
  // Create the block for the RHS expression.
2777
2.88k
  Succ = ConfluenceBlock;
2778
2.88k
  CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
2779
2.88k
  if (badCFG)
2780
0
    return nullptr;
2781
2782
  // If the condition is a logical '&&' or '||', build a more accurate CFG.
2783
2.88k
  if (BinaryOperator *Cond =
2784
2.88k
        dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens()))
2785
1.20k
    if (Cond->isLogicalOp())
2786
71
      return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first;
2787
2788
  // Create the block that will contain the condition.
2789
2.81k
  Block = createBlock(false);
2790
2791
  // See if this is a known constant.
2792
2.81k
  const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2793
2.81k
  addSuccessor(Block, LHSBlock, !KnownVal.isFalse());
2794
2.81k
  addSuccessor(Block, RHSBlock, !KnownVal.isTrue());
2795
2.81k
  Block->setTerminator(C);
2796
2.81k
  Expr *condExpr = C->getCond();
2797
2798
2.81k
  if (opaqueValue) {
2799
    // Run the condition expression if it's not trivially expressed in
2800
    // terms of the opaque value (or if there is no opaque value).
2801
185
    if (condExpr != opaqueValue)
2802
103
      addStmt(condExpr);
2803
2804
    // Before that, run the common subexpression if there was one.
2805
    // At least one of this or the above will be run.
2806
185
    return addStmt(BCO->getCommon());
2807
185
  }
2808
2809
2.62k
  return addStmt(condExpr);
2810
2.81k
}
2811
2812
179k
CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
2813
  // Check if the Decl is for an __label__.  If so, elide it from the
2814
  // CFG entirely.
2815
179k
  if (isa<LabelDecl>(*DS->decl_begin()))
2816
6
    return Block;
2817
2818
  // This case also handles static_asserts.
2819
179k
  if (DS->isSingleDecl())
2820
176k
    return VisitDeclSubExpr(DS);
2821
2822
3.40k
  CFGBlock *B = nullptr;
2823
2824
  // Build an individual DeclStmt for each decl.
2825
3.40k
  for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
2826
3.40k
                                       E = DS->decl_rend();
2827
13.1k
       I != E; 
++I9.71k
) {
2828
2829
    // Allocate the DeclStmt using the BumpPtrAllocator.  It will get
2830
    // automatically freed with the CFG.
2831
9.71k
    DeclGroupRef DG(*I);
2832
9.71k
    Decl *D = *I;
2833
9.71k
    DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
2834
9.71k
    cfg->addSyntheticDeclStmt(DSNew, DS);
2835
2836
    // Append the fake DeclStmt to block.
2837
9.71k
    B = VisitDeclSubExpr(DSNew);
2838
9.71k
  }
2839
2840
3.40k
  return B;
2841
179k
}
2842
2843
/// VisitDeclSubExpr - Utility method to add block-level expressions for
2844
/// DeclStmts and initializers in them.
2845
185k
CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
2846
185k
  assert(DS->isSingleDecl() && "Can handle single declarations only.");
2847
2848
185k
  if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl())) {
2849
    // If we encounter a VLA, process its size expressions.
2850
1.50k
    const Type *T = TND->getUnderlyingType().getTypePtr();
2851
1.50k
    if (!T->isVariablyModifiedType())
2852
1.44k
      return Block;
2853
2854
63
    autoCreateBlock();
2855
63
    appendStmt(Block, DS);
2856
2857
63
    CFGBlock *LastBlock = Block;
2858
142
    for (const VariableArrayType *VA = FindVA(T); VA != nullptr;
2859
79
         VA = FindVA(VA->getElementType().getTypePtr())) {
2860
79
      if (CFGBlock *NewBlock = addStmt(VA->getSizeExpr()))
2861
79
        LastBlock = NewBlock;
2862
79
    }
2863
63
    return LastBlock;
2864
1.50k
  }
2865
2866
184k
  VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
2867
2868
184k
  if (!VD) {
2869
    // Of everything that can be declared in a DeclStmt, only VarDecls and the
2870
    // exceptions above impact runtime semantics.
2871
9.80k
    return Block;
2872
9.80k
  }
2873
2874
174k
  bool HasTemporaries = false;
2875
2876
  // Guard static initializers under a branch.
2877
174k
  CFGBlock *blockAfterStaticInit = nullptr;
2878
2879
174k
  if (BuildOpts.AddStaticInitBranches && 
VD->isStaticLocal()40.0k
) {
2880
    // For static variables, we need to create a branch to track
2881
    // whether or not they are initialized.
2882
396
    if (Block) {
2883
380
      Succ = Block;
2884
380
      Block = nullptr;
2885
380
      if (badCFG)
2886
0
        return nullptr;
2887
380
    }
2888
396
    blockAfterStaticInit = Succ;
2889
396
  }
2890
2891
  // Destructors of temporaries in initialization expression should be called
2892
  // after initialization finishes.
2893
174k
  Expr *Init = VD->getInit();
2894
174k
  if (Init) {
2895
150k
    HasTemporaries = isa<ExprWithCleanups>(Init);
2896
2897
150k
    if (BuildOpts.AddTemporaryDtors && 
HasTemporaries150k
) {
2898
      // Generate destructors for temporaries in initialization expression.
2899
9.08k
      TempDtorContext Context;
2900
9.08k
      VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
2901
9.08k
                             /*ExternallyDestructed=*/true, Context);
2902
9.08k
    }
2903
150k
  }
2904
2905
174k
  autoCreateBlock();
2906
174k
  appendStmt(Block, DS);
2907
2908
174k
  findConstructionContexts(
2909
174k
      ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
2910
174k
      Init);
2911
2912
  // Keep track of the last non-null block, as 'Block' can be nulled out
2913
  // if the initializer expression is something like a 'while' in a
2914
  // statement-expression.
2915
174k
  CFGBlock *LastBlock = Block;
2916
2917
174k
  if (Init) {
2918
150k
    if (HasTemporaries) {
2919
      // For expression with temporaries go directly to subexpression to omit
2920
      // generating destructors for the second time.
2921
9.28k
      ExprWithCleanups *EC = cast<ExprWithCleanups>(Init);
2922
9.28k
      if (CFGBlock *newBlock = Visit(EC->getSubExpr()))
2923
9.28k
        LastBlock = newBlock;
2924
9.28k
    }
2925
141k
    else {
2926
141k
      if (CFGBlock *newBlock = Visit(Init))
2927
141k
        LastBlock = newBlock;
2928
141k
    }
2929
150k
  }
2930
2931
  // If the type of VD is a VLA, then we must process its size expressions.
2932
  // FIXME: This does not find the VLA if it is embedded in other types,
2933
  // like here: `int (*p_vla)[x];`
2934
174k
  for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
2935
177k
       VA != nullptr; 
VA = FindVA(VA->getElementType().getTypePtr())2.68k
) {
2936
2.68k
    if (CFGBlock *newBlock = addStmt(VA->getSizeExpr()))
2937
2.68k
      LastBlock = newBlock;
2938
2.68k
  }
2939
2940
174k
  maybeAddScopeBeginForVarDecl(Block, VD, DS);
2941
2942
  // Remove variable from local scope.
2943
174k
  if (ScopePos && 
VD == *ScopePos7.48k
)
2944
4.81k
    ++ScopePos;
2945
2946
174k
  CFGBlock *B = LastBlock;
2947
174k
  if (blockAfterStaticInit) {
2948
396
    Succ = B;
2949
396
    Block = createBlock(false);
2950
396
    Block->setTerminator(DS);
2951
396
    addSuccessor(Block, blockAfterStaticInit);
2952
396
    addSuccessor(Block, B);
2953
396
    B = Block;
2954
396
  }
2955
2956
174k
  return B;
2957
174k
}
2958
2959
113k
CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
2960
  // We may see an if statement in the middle of a basic block, or it may be the
2961
  // first statement we are processing.  In either case, we create a new basic
2962
  // block.  First, we create the blocks for the then...else statements, and
2963
  // then we create the block containing the if statement.  If we were in the
2964
  // middle of a block, we stop processing that block.  That block is then the
2965
  // implicit successor for the "then" and "else" clauses.
2966
2967
  // Save local scope position because in case of condition variable ScopePos
2968
  // won't be restored when traversing AST.
2969
113k
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2970
2971
  // Create local scope for C++17 if init-stmt if one exists.
2972
113k
  if (Stmt *Init = I->getInit())
2973
13
    addLocalScopeForStmt(Init);
2974
2975
  // Create local scope for possible condition variable.
2976
  // Store scope position. Add implicit destructor.
2977
113k
  if (VarDecl *VD = I->getConditionVariable())
2978
168
    addLocalScopeForVarDecl(VD);
2979
2980
113k
  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), I);
2981
2982
  // The block we were processing is now finished.  Make it the successor
2983
  // block.
2984
113k
  if (Block) {
2985
93.3k
    Succ = Block;
2986
93.3k
    if (badCFG)
2987
0
      return nullptr;
2988
93.3k
  }
2989
2990
  // Process the false branch.
2991
113k
  CFGBlock *ElseBlock = Succ;
2992
2993
113k
  if (Stmt *Else = I->getElse()) {
2994
11.8k
    SaveAndRestore<CFGBlock*> sv(Succ);
2995
2996
    // NULL out Block so that the recursive call to Visit will
2997
    // create a new basic block.
2998
11.8k
    Block = nullptr;
2999
3000
    // If branch is not a compound statement create implicit scope
3001
    // and add destructors.
3002
11.8k
    if (!isa<CompoundStmt>(Else))
3003
7.30k
      addLocalScopeAndDtors(Else);
3004
3005
11.8k
    ElseBlock = addStmt(Else);
3006
3007
11.8k
    if (!ElseBlock) // Can occur when the Else body has all NullStmts.
3008
12
      ElseBlock = sv.get();
3009
11.8k
    else if (Block) {
3010
11.8k
      if (badCFG)
3011
0
        return nullptr;
3012
11.8k
    }
3013
11.8k
  }
3014
3015
  // Process the true branch.
3016
113k
  CFGBlock *ThenBlock;
3017
113k
  {
3018
113k
    Stmt *Then = I->getThen();
3019
113k
    assert(Then);
3020
0
    SaveAndRestore<CFGBlock*> sv(Succ);
3021
113k
    Block = nullptr;
3022
3023
    // If branch is not a compound statement create implicit scope
3024
    // and add destructors.
3025
113k
    if (!isa<CompoundStmt>(Then))
3026
81.6k
      addLocalScopeAndDtors(Then);
3027
3028
113k
    ThenBlock = addStmt(Then);
3029
3030
113k
    if (!ThenBlock) {
3031
      // We can reach here if the "then" body has all NullStmts.
3032
      // Create an empty block so we can distinguish between true and false
3033
      // branches in path-sensitive analyses.
3034
2.30k
      ThenBlock = createBlock(false);
3035
2.30k
      addSuccessor(ThenBlock, sv.get());
3036
111k
    } else if (Block) {
3037
111k
      if (badCFG)
3038
0
        return nullptr;
3039
111k
    }
3040
113k
  }
3041
3042
  // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
3043
  // having these handle the actual control-flow jump.  Note that
3044
  // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
3045
  // we resort to the old control-flow behavior.  This special handling
3046
  // removes infeasible paths from the control-flow graph by having the
3047
  // control-flow transfer of '&&' or '||' go directly into the then/else
3048
  // blocks directly.
3049
113k
  BinaryOperator *Cond =
3050
113k
      I->getConditionVariable()
3051
113k
          ? 
nullptr168
3052
113k
          : 
dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens())113k
;
3053
113k
  CFGBlock *LastBlock;
3054
113k
  if (Cond && 
Cond->isLogicalOp()36.1k
)
3055
6.68k
    LastBlock = VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first;
3056
107k
  else {
3057
    // Now create a new block containing the if statement.
3058
107k
    Block = createBlock(false);
3059
3060
    // Set the terminator of the new block to the If statement.
3061
107k
    Block->setTerminator(I);
3062
3063
    // See if this is a known constant.
3064
107k
    const TryResult &KnownVal = tryEvaluateBool(I->getCond());
3065
3066
    // Add the successors.  If we know that specific branches are
3067
    // unreachable, inform addSuccessor() of that knowledge.
3068
107k
    addSuccessor(Block, ThenBlock, /* IsReachable = */ !KnownVal.isFalse());
3069
107k
    addSuccessor(Block, ElseBlock, /* IsReachable = */ !KnownVal.isTrue());
3070
3071
    // Add the condition as the last statement in the new block.  This may
3072
    // create new blocks as the condition may contain control-flow.  Any newly
3073
    // created blocks will be pointed to be "Block".
3074
107k
    LastBlock = addStmt(I->getCond());
3075
3076
    // If the IfStmt contains a condition variable, add it and its
3077
    // initializer to the CFG.
3078
107k
    if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
3079
168
      autoCreateBlock();
3080
168
      LastBlock = addStmt(const_cast<DeclStmt *>(DS));
3081
168
    }
3082
107k
  }
3083
3084
  // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
3085
113k
  if (Stmt *Init = I->getInit()) {
3086
13
    autoCreateBlock();
3087
13
    LastBlock = addStmt(Init);
3088
13
  }
3089
3090
113k
  return LastBlock;
3091
113k
}
3092
3093
181k
CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {
3094
  // If we were in the middle of a block we stop processing that block.
3095
  //
3096
  // NOTE: If a "return" or "co_return" appears in the middle of a block, this
3097
  //       means that the code afterwards is DEAD (unreachable).  We still keep
3098
  //       a basic block for that code; a simple "mark-and-sweep" from the entry
3099
  //       block will be able to report such dead blocks.
3100
181k
  assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));
3101
3102
  // Create the new block.
3103
0
  Block = createBlock(false);
3104
3105
181k
  addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), S);
3106
3107
181k
  if (auto *R = dyn_cast<ReturnStmt>(S))
3108
181k
    findConstructionContexts(
3109
181k
        ConstructionContextLayer::create(cfg->getBumpVectorContext(), R),
3110
181k
        R->getRetValue());
3111
3112
  // If the one of the destructors does not return, we already have the Exit
3113
  // block as a successor.
3114
181k
  if (!Block->hasNoReturnElement())
3115
181k
    addSuccessor(Block, &cfg->getExit());
3116
3117
  // Add the return statement to the block.
3118
181k
  appendStmt(Block, S);
3119
3120
  // Visit children
3121
181k
  if (ReturnStmt *RS = dyn_cast<ReturnStmt>(S)) {
3122
181k
    if (Expr *O = RS->getRetValue())
3123
178k
      return Visit(O, AddStmtChoice::AlwaysAdd, /*ExternallyDestructed=*/true);
3124
2.63k
    return Block;
3125
181k
  } else { // co_return
3126
22
    return VisitChildren(S);
3127
22
  }
3128
181k
}
3129
3130
48
CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
3131
  // SEHExceptStmt are treated like labels, so they are the first statement in a
3132
  // block.
3133
3134
  // Save local scope position because in case of exception variable ScopePos
3135
  // won't be restored when traversing AST.
3136
48
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3137
3138
48
  addStmt(ES->getBlock());
3139
48
  CFGBlock *SEHExceptBlock = Block;
3140
48
  if (!SEHExceptBlock)
3141
10
    SEHExceptBlock = createBlock();
3142
3143
48
  appendStmt(SEHExceptBlock, ES);
3144
3145
  // Also add the SEHExceptBlock as a label, like with regular labels.
3146
48
  SEHExceptBlock->setLabel(ES);
3147
3148
  // Bail out if the CFG is bad.
3149
48
  if (badCFG)
3150
0
    return nullptr;
3151
3152
  // We set Block to NULL to allow lazy creation of a new block (if necessary).
3153
48
  Block = nullptr;
3154
3155
48
  return SEHExceptBlock;
3156
48
}
3157
3158
0
CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {
3159
0
  return VisitCompoundStmt(FS->getBlock(), /*ExternallyDestructed=*/false);
3160
0
}
3161
3162
10
CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {
3163
  // "__leave" is a control-flow statement.  Thus we stop processing the current
3164
  // block.
3165
10
  if (badCFG)
3166
0
    return nullptr;
3167
3168
  // Now create a new block that ends with the __leave statement.
3169
10
  Block = createBlock(false);
3170
10
  Block->setTerminator(LS);
3171
3172
  // If there is no target for the __leave, then we are looking at an incomplete
3173
  // AST.  This means that the CFG cannot be constructed.
3174
10
  if (SEHLeaveJumpTarget.block) {
3175
10
    addAutomaticObjHandling(ScopePos, SEHLeaveJumpTarget.scopePosition, LS);
3176
10
    addSuccessor(Block, SEHLeaveJumpTarget.block);
3177
10
  } else
3178
0
    badCFG = true;
3179
3180
10
  return Block;
3181
10
}
3182
3183
70
CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {
3184
  // "__try"/"__except"/"__finally" is a control-flow statement.  Thus we stop
3185
  // processing the current block.
3186
70
  CFGBlock *SEHTrySuccessor = nullptr;
3187
3188
70
  if (Block) {
3189
46
    if (badCFG)
3190
0
      return nullptr;
3191
46
    SEHTrySuccessor = Block;
3192
46
  } else 
SEHTrySuccessor = Succ24
;
3193
3194
  // FIXME: Implement __finally support.
3195
70
  if (Terminator->getFinallyHandler())
3196
22
    return NYS();
3197
3198
48
  CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;
3199
3200
  // Create a new block that will contain the __try statement.
3201
48
  CFGBlock *NewTryTerminatedBlock = createBlock(false);
3202
3203
  // Add the terminator in the __try block.
3204
48
  NewTryTerminatedBlock->setTerminator(Terminator);
3205
3206
48
  if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {
3207
    // The code after the try is the implicit successor if there's an __except.
3208
48
    Succ = SEHTrySuccessor;
3209
48
    Block = nullptr;
3210
48
    CFGBlock *ExceptBlock = VisitSEHExceptStmt(Except);
3211
48
    if (!ExceptBlock)
3212
0
      return nullptr;
3213
    // Add this block to the list of successors for the block with the try
3214
    // statement.
3215
48
    addSuccessor(NewTryTerminatedBlock, ExceptBlock);
3216
48
  }
3217
48
  if (PrevSEHTryTerminatedBlock)
3218
8
    addSuccessor(NewTryTerminatedBlock, PrevSEHTryTerminatedBlock);
3219
40
  else
3220
40
    addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
3221
3222
  // The code after the try is the implicit successor.
3223
48
  Succ = SEHTrySuccessor;
3224
3225
  // Save the current "__try" context.
3226
48
  SaveAndRestore<CFGBlock *> save_try(TryTerminatedBlock,
3227
48
                                      NewTryTerminatedBlock);
3228
48
  cfg->addTryDispatchBlock(TryTerminatedBlock);
3229
3230
  // Save the current value for the __leave target.
3231
  // All __leaves should go to the code following the __try
3232
  // (FIXME: or if the __try has a __finally, to the __finally.)
3233
48
  SaveAndRestore<JumpTarget> save_break(SEHLeaveJumpTarget);
3234
48
  SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);
3235
3236
48
  assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");
3237
0
  Block = nullptr;
3238
48
  return addStmt(Terminator->getTryBlock());
3239
48
}
3240
3241
585
CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
3242
  // Get the block of the labeled statement.  Add it to our map.
3243
585
  addStmt(L->getSubStmt());
3244
585
  CFGBlock *LabelBlock = Block;
3245
3246
585
  if (!LabelBlock)              // This can happen when the body is empty, i.e.
3247
216
    LabelBlock = createBlock(); // scopes that only contains NullStmts.
3248
3249
585
  assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
3250
585
         "label already in map");
3251
0
  LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
3252
3253
  // Labels partition blocks, so this is the end of the basic block we were
3254
  // processing (L is the block's label).  Because this is label (and we have
3255
  // already processed the substatement) there is no extra control-flow to worry
3256
  // about.
3257
585
  LabelBlock->setLabel(L);
3258
585
  if (badCFG)
3259
0
    return nullptr;
3260
3261
  // We set Block to NULL to allow lazy creation of a new block (if necessary);
3262
585
  Block = nullptr;
3263
3264
  // This block is now the implicit successor of other blocks.
3265
585
  Succ = LabelBlock;
3266
3267
585
  return LabelBlock;
3268
585
}
3269
3270
1.68k
CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
3271
1.68k
  CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3272
1.68k
  for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
3273
1.54k
    if (Expr *CopyExpr = CI.getCopyExpr()) {
3274
28
      CFGBlock *Tmp = Visit(CopyExpr);
3275
28
      if (Tmp)
3276
28
        LastBlock = Tmp;
3277
28
    }
3278
1.54k
  }
3279
1.68k
  return LastBlock;
3280
1.68k
}
3281
3282
1.25k
CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
3283
1.25k
  CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3284
1.25k
  for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
3285
2.35k
       et = E->capture_init_end(); it != et; 
++it1.10k
) {
3286
1.10k
    if (Expr *Init = *it) {
3287
1.07k
      CFGBlock *Tmp = Visit(Init);
3288
1.07k
      if (Tmp)
3289
1.07k
        LastBlock = Tmp;
3290
1.07k
    }
3291
1.10k
  }
3292
1.25k
  return LastBlock;
3293
1.25k
}
3294
3295
222
CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
3296
  // Goto is a control-flow statement.  Thus we stop processing the current
3297
  // block and create a new one.
3298
3299
222
  Block = createBlock(false);
3300
222
  Block->setTerminator(G);
3301
3302
  // If we already know the mapping to the label block add the successor now.
3303
222
  LabelMapTy::iterator I = LabelMap.find(G->getLabel());
3304
3305
222
  if (I == LabelMap.end())
3306
    // We will need to backpatch this block later.
3307
68
    BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
3308
154
  else {
3309
154
    JumpTarget JT = I->second;
3310
154
    addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
3311
154
    addSuccessor(Block, JT.block);
3312
154
  }
3313
3314
222
  return Block;
3315
222
}
3316
3317
366
CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {
3318
  // Goto is a control-flow statement.  Thus we stop processing the current
3319
  // block and create a new one.
3320
3321
366
  if (!G->isAsmGoto())
3322
306
    return VisitStmt(G, asc);
3323
3324
60
  if (Block) {
3325
32
    Succ = Block;
3326
32
    if (badCFG)
3327
0
      return nullptr;
3328
32
  }
3329
60
  Block = createBlock();
3330
60
  Block->setTerminator(G);
3331
  // We will backpatch this block later for all the labels.
3332
60
  BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
3333
  // Save "Succ" in BackpatchBlocks. In the backpatch processing, "Succ" is
3334
  // used to avoid adding "Succ" again.
3335
60
  BackpatchBlocks.push_back(JumpSource(Succ, ScopePos));
3336
60
  return Block;
3337
60
}
3338
3339
24.8k
CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
3340
24.8k
  CFGBlock *LoopSuccessor = nullptr;
3341
3342
  // Save local scope position because in case of condition variable ScopePos
3343
  // won't be restored when traversing AST.
3344
24.8k
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3345
3346
  // Create local scope for init statement and possible condition variable.
3347
  // Add destructor for init statement and condition variable.
3348
  // Store scope position for continue statement.
3349
24.8k
  if (Stmt *Init = F->getInit())
3350
24.5k
    addLocalScopeForStmt(Init);
3351
24.8k
  LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3352
3353
24.8k
  if (VarDecl *VD = F->getConditionVariable())
3354
40
    addLocalScopeForVarDecl(VD);
3355
24.8k
  LocalScope::const_iterator ContinueScopePos = ScopePos;
3356
3357
24.8k
  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
3358
3359
24.8k
  addLoopExit(F);
3360
3361
  // "for" is a control-flow statement.  Thus we stop processing the current
3362
  // block.
3363
24.8k
  if (Block) {
3364
20.3k
    if (badCFG)
3365
0
      return nullptr;
3366
20.3k
    LoopSuccessor = Block;
3367
20.3k
  } else
3368
4.49k
    LoopSuccessor = Succ;
3369
3370
  // Save the current value for the break targets.
3371
  // All breaks should go to the code following the loop.
3372
24.8k
  SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3373
24.8k
  BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3374
3375
24.8k
  CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3376
3377
  // Now create the loop body.
3378
24.8k
  {
3379
24.8k
    assert(F->getBody());
3380
3381
    // Save the current values for Block, Succ, continue and break targets.
3382
0
    SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3383
24.8k
    SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
3384
3385
    // Create an empty block to represent the transition block for looping back
3386
    // to the head of the loop.  If we have increment code, it will
3387
    // go in this block as well.
3388
24.8k
    Block = Succ = TransitionBlock = createBlock(false);
3389
24.8k
    TransitionBlock->setLoopTarget(F);
3390
3391
24.8k
    if (Stmt *I = F->getInc()) {
3392
      // Generate increment code in its own basic block.  This is the target of
3393
      // continue statements.
3394
24.5k
      Succ = addStmt(I);
3395
24.5k
    }
3396
3397
    // Finish up the increment (or empty) block if it hasn't been already.
3398
24.8k
    if (Block) {
3399
24.8k
      assert(Block == Succ);
3400
24.8k
      if (badCFG)
3401
0
        return nullptr;
3402
24.8k
      Block = nullptr;
3403
24.8k
    }
3404
3405
   // The starting block for the loop increment is the block that should
3406
   // represent the 'loop target' for looping back to the start of the loop.
3407
24.8k
   ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3408
24.8k
   ContinueJumpTarget.block->setLoopTarget(F);
3409
3410
    // Loop body should end with destructor of Condition variable (if any).
3411
24.8k
   addAutomaticObjHandling(ScopePos, LoopBeginScopePos, F);
3412
3413
    // If body is not a compound statement create implicit scope
3414
    // and add destructors.
3415
24.8k
    if (!isa<CompoundStmt>(F->getBody()))
3416
7.03k
      addLocalScopeAndDtors(F->getBody());
3417
3418
    // Now populate the body block, and in the process create new blocks as we
3419
    // walk the body of the loop.
3420
24.8k
    BodyBlock = addStmt(F->getBody());
3421
3422
24.8k
    if (!BodyBlock) {
3423
      // In the case of "for (...;...;...);" we can have a null BodyBlock.
3424
      // Use the continue jump target as the proxy for the body.
3425
2.35k
      BodyBlock = ContinueJumpTarget.block;
3426
2.35k
    }
3427
22.4k
    else if (badCFG)
3428
0
      return nullptr;
3429
24.8k
  }
3430
3431
  // Because of short-circuit evaluation, the condition of the loop can span
3432
  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
3433
  // evaluate the condition.
3434
24.8k
  CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3435
3436
24.8k
  do {
3437
24.8k
    Expr *C = F->getCond();
3438
24.8k
    SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3439
3440
    // Specially handle logical operators, which have a slightly
3441
    // more optimal CFG representation.
3442
24.8k
    if (BinaryOperator *Cond =
3443
24.8k
            dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr))
3444
18.4k
      if (Cond->isLogicalOp()) {
3445
14
        std::tie(EntryConditionBlock, ExitConditionBlock) =
3446
14
          VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor);
3447
14
        break;
3448
14
      }
3449
3450
    // The default case when not handling logical operators.
3451
24.7k
    EntryConditionBlock = ExitConditionBlock = createBlock(false);
3452
24.7k
    ExitConditionBlock->setTerminator(F);
3453
3454
    // See if this is a known constant.
3455
24.7k
    TryResult KnownVal(true);
3456
3457
24.7k
    if (C) {
3458
      // Now add the actual condition to the condition block.
3459
      // Because the condition itself may contain control-flow, new blocks may
3460
      // be created.  Thus we update "Succ" after adding the condition.
3461
24.6k
      Block = ExitConditionBlock;
3462
24.6k
      EntryConditionBlock = addStmt(C);
3463
3464
      // If this block contains a condition variable, add both the condition
3465
      // variable and initializer to the CFG.
3466
24.6k
      if (VarDecl *VD = F->getConditionVariable()) {
3467
40
        if (Expr *Init = VD->getInit()) {
3468
40
          autoCreateBlock();
3469
40
          const DeclStmt *DS = F->getConditionVariableDeclStmt();
3470
40
          assert(DS->isSingleDecl());
3471
0
          findConstructionContexts(
3472
40
              ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
3473
40
              Init);
3474
40
          appendStmt(Block, DS);
3475
40
          EntryConditionBlock = addStmt(Init);
3476
40
          assert(Block == EntryConditionBlock);
3477
0
          maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3478
40
        }
3479
40
      }
3480
3481
24.6k
      if (Block && 
badCFG24.6k
)
3482
2
        return nullptr;
3483
3484
24.6k
      KnownVal = tryEvaluateBool(C);
3485
24.6k
    }
3486
3487
    // Add the loop body entry as a successor to the condition.
3488
24.7k
    addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? 
nullptr13
:
BodyBlock24.7k
);
3489
    // Link up the condition block with the code that follows the loop.  (the
3490
    // false branch).
3491
24.7k
    addSuccessor(ExitConditionBlock,
3492
24.7k
                 KnownVal.isTrue() ? 
nullptr129
:
LoopSuccessor24.6k
);
3493
24.7k
  } while (false);
3494
3495
  // Link up the loop-back block to the entry condition block.
3496
24.8k
  addSuccessor(TransitionBlock, EntryConditionBlock);
3497
3498
  // The condition block is the implicit successor for any code above the loop.
3499
24.8k
  Succ = EntryConditionBlock;
3500
3501
  // If the loop contains initialization, create a new block for those
3502
  // statements.  This block can also contain statements that precede the loop.
3503
24.8k
  if (Stmt *I = F->getInit()) {
3504
24.5k
    SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3505
24.5k
    ScopePos = LoopBeginScopePos;
3506
24.5k
    Block = createBlock();
3507
24.5k
    return addStmt(I);
3508
24.5k
  }
3509
3510
  // There is no loop initialization.  We are thus basically a while loop.
3511
  // NULL out Block to force lazy block construction.
3512
236
  Block = nullptr;
3513
236
  Succ = EntryConditionBlock;
3514
236
  return EntryConditionBlock;
3515
24.8k
}
3516
3517
CFGBlock *
3518
CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
3519
18.5k
                                          AddStmtChoice asc) {
3520
18.5k
  findConstructionContexts(
3521
18.5k
      ConstructionContextLayer::create(cfg->getBumpVectorContext(), MTE),
3522
18.5k
      MTE->getSubExpr());
3523
3524
18.5k
  return VisitStmt(MTE, asc);
3525
18.5k
}
3526
3527
149k
CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
3528
149k
  if (asc.alwaysAdd(*this, M)) {
3529
40.9k
    autoCreateBlock();
3530
40.9k
    appendStmt(Block, M);
3531
40.9k
  }
3532
149k
  return Visit(M->getBase());
3533
149k
}
3534
3535
230
CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
3536
  // Objective-C fast enumeration 'for' statements:
3537
  //  http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
3538
  //
3539
  //  for ( Type newVariable in collection_expression ) { statements }
3540
  //
3541
  //  becomes:
3542
  //
3543
  //   prologue:
3544
  //     1. collection_expression
3545
  //     T. jump to loop_entry
3546
  //   loop_entry:
3547
  //     1. side-effects of element expression
3548
  //     1. ObjCForCollectionStmt [performs binding to newVariable]
3549
  //     T. ObjCForCollectionStmt  TB, FB  [jumps to TB if newVariable != nil]
3550
  //   TB:
3551
  //     statements
3552
  //     T. jump to loop_entry
3553
  //   FB:
3554
  //     what comes after
3555
  //
3556
  //  and
3557
  //
3558
  //  Type existingItem;
3559
  //  for ( existingItem in expression ) { statements }
3560
  //
3561
  //  becomes:
3562
  //
3563
  //   the same with newVariable replaced with existingItem; the binding works
3564
  //   the same except that for one ObjCForCollectionStmt::getElement() returns
3565
  //   a DeclStmt and the other returns a DeclRefExpr.
3566
3567
230
  CFGBlock *LoopSuccessor = nullptr;
3568
3569
230
  if (Block) {
3570
152
    if (badCFG)
3571
0
      return nullptr;
3572
152
    LoopSuccessor = Block;
3573
152
    Block = nullptr;
3574
152
  } else
3575
78
    LoopSuccessor = Succ;
3576
3577
  // Build the condition blocks.
3578
230
  CFGBlock *ExitConditionBlock = createBlock(false);
3579
3580
  // Set the terminator for the "exit" condition block.
3581
230
  ExitConditionBlock->setTerminator(S);
3582
3583
  // The last statement in the block should be the ObjCForCollectionStmt, which
3584
  // performs the actual binding to 'element' and determines if there are any
3585
  // more items in the collection.
3586
230
  appendStmt(ExitConditionBlock, S);
3587
230
  Block = ExitConditionBlock;
3588
3589
  // Walk the 'element' expression to see if there are any side-effects.  We
3590
  // generate new blocks as necessary.  We DON'T add the statement by default to
3591
  // the CFG unless it contains control-flow.
3592
230
  CFGBlock *EntryConditionBlock = Visit(S->getElement(),
3593
230
                                        AddStmtChoice::NotAlwaysAdd);
3594
230
  if (Block) {
3595
230
    if (badCFG)
3596
0
      return nullptr;
3597
230
    Block = nullptr;
3598
230
  }
3599
3600
  // The condition block is the implicit successor for the loop body as well as
3601
  // any code above the loop.
3602
230
  Succ = EntryConditionBlock;
3603
3604
  // Now create the true branch.
3605
230
  {
3606
    // Save the current values for Succ, continue and break targets.
3607
230
    SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3608
230
    SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3609
230
                               save_break(BreakJumpTarget);
3610
3611
    // Add an intermediate block between the BodyBlock and the
3612
    // EntryConditionBlock to represent the "loop back" transition, for looping
3613
    // back to the head of the loop.
3614
230
    CFGBlock *LoopBackBlock = nullptr;
3615
230
    Succ = LoopBackBlock = createBlock();
3616
230
    LoopBackBlock->setLoopTarget(S);
3617
3618
230
    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3619
230
    ContinueJumpTarget = JumpTarget(Succ, ScopePos);
3620
3621
230
    CFGBlock *BodyBlock = addStmt(S->getBody());
3622
3623
230
    if (!BodyBlock)
3624
19
      BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
3625
211
    else if (Block) {
3626
211
      if (badCFG)
3627
0
        return nullptr;
3628
211
    }
3629
3630
    // This new body block is a successor to our "exit" condition block.
3631
230
    addSuccessor(ExitConditionBlock, BodyBlock);
3632
230
  }
3633
3634
  // Link up the condition block with the code that follows the loop.
3635
  // (the false branch).
3636
0
  addSuccessor(ExitConditionBlock, LoopSuccessor);
3637
3638
  // Now create a prologue block to contain the collection expression.
3639
230
  Block = createBlock();
3640
230
  return addStmt(S->getCollection());
3641
230
}
3642
3643
190
CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
3644
  // Inline the body.
3645
190
  return addStmt(S->getSubStmt());
3646
  // TODO: consider adding cleanups for the end of @autoreleasepool scope.
3647
190
}
3648
3649
75
CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
3650
  // FIXME: Add locking 'primitives' to CFG for @synchronized.
3651
3652
  // Inline the body.
3653
75
  CFGBlock *SyncBlock = addStmt(S->getSynchBody());
3654
3655
  // The sync body starts its own basic block.  This makes it a little easier
3656
  // for diagnostic clients.
3657
75
  if (SyncBlock) {
3658
36
    if (badCFG)
3659
0
      return nullptr;
3660
3661
36
    Block = nullptr;
3662
36
    Succ = SyncBlock;
3663
36
  }
3664
3665
  // Add the @synchronized to the CFG.
3666
75
  autoCreateBlock();
3667
75
  appendStmt(Block, S);
3668
3669
  // Inline the sync expression.
3670
75
  return addStmt(S->getSynchExpr());
3671
75
}
3672
3673
167
CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
3674
  // FIXME
3675
167
  return NYS();
3676
167
}
3677
3678
2.28k
CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
3679
2.28k
  autoCreateBlock();
3680
3681
  // Add the PseudoObject as the last thing.
3682
2.28k
  appendStmt(Block, E);
3683
3684
2.28k
  CFGBlock *lastBlock = Block;
3685
3686
  // Before that, evaluate all of the semantics in order.  In
3687
  // CFG-land, that means appending them in reverse order.
3688
7.74k
  for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
3689
5.45k
    Expr *Semantic = E->getSemanticExpr(--i);
3690
3691
    // If the semantic is an opaque value, we're being asked to bind
3692
    // it to its source expression.
3693
5.45k
    if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
3694
3.16k
      Semantic = OVE->getSourceExpr();
3695
3696
5.45k
    if (CFGBlock *B = Visit(Semantic))
3697
5.45k
      lastBlock = B;
3698
5.45k
  }
3699
3700
2.28k
  return lastBlock;
3701
2.28k
}
3702
3703
1.28k
CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
3704
1.28k
  CFGBlock *LoopSuccessor = nullptr;
3705
3706
  // Save local scope position because in case of condition variable ScopePos
3707
  // won't be restored when traversing AST.
3708
1.28k
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3709
3710
  // Create local scope for possible condition variable.
3711
  // Store scope position for continue statement.
3712
1.28k
  LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3713
1.28k
  if (VarDecl *VD = W->getConditionVariable()) {
3714
40
    addLocalScopeForVarDecl(VD);
3715
40
    addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3716
40
  }
3717
1.28k
  addLoopExit(W);
3718
3719
  // "while" is a control-flow statement.  Thus we stop processing the current
3720
  // block.
3721
1.28k
  if (Block) {
3722
397
    if (badCFG)
3723
0
      return nullptr;
3724
397
    LoopSuccessor = Block;
3725
397
    Block = nullptr;
3726
886
  } else {
3727
886
    LoopSuccessor = Succ;
3728
886
  }
3729
3730
1.28k
  CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3731
3732
  // Process the loop body.
3733
1.28k
  {
3734
1.28k
    assert(W->getBody());
3735
3736
    // Save the current values for Block, Succ, continue and break targets.
3737
0
    SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3738
1.28k
    SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3739
1.28k
                               save_break(BreakJumpTarget);
3740
3741
    // Create an empty block to represent the transition block for looping back
3742
    // to the head of the loop.
3743
1.28k
    Succ = TransitionBlock = createBlock(false);
3744
1.28k
    TransitionBlock->setLoopTarget(W);
3745
1.28k
    ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
3746
3747
    // All breaks should go to the code following the loop.
3748
1.28k
    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3749
3750
    // Loop body should end with destructor of Condition variable (if any).
3751
1.28k
    addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3752
3753
    // If body is not a compound statement create implicit scope
3754
    // and add destructors.
3755
1.28k
    if (!isa<CompoundStmt>(W->getBody()))
3756
651
      addLocalScopeAndDtors(W->getBody());
3757
3758
    // Create the body.  The returned block is the entry to the loop body.
3759
1.28k
    BodyBlock = addStmt(W->getBody());
3760
3761
1.28k
    if (!BodyBlock)
3762
570
      BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
3763
713
    else if (Block && 
badCFG705
)
3764
0
      return nullptr;
3765
1.28k
  }
3766
3767
  // Because of short-circuit evaluation, the condition of the loop can span
3768
  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
3769
  // evaluate the condition.
3770
1.28k
  CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3771
3772
1.28k
  do {
3773
1.28k
    Expr *C = W->getCond();
3774
3775
    // Specially handle logical operators, which have a slightly
3776
    // more optimal CFG representation.
3777
1.28k
    if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens()))
3778
647
      if (Cond->isLogicalOp()) {
3779
30
        std::tie(EntryConditionBlock, ExitConditionBlock) =
3780
30
            VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor);
3781
30
        break;
3782
30
      }
3783
3784
    // The default case when not handling logical operators.
3785
1.25k
    ExitConditionBlock = createBlock(false);
3786
1.25k
    ExitConditionBlock->setTerminator(W);
3787
3788
    // Now add the actual condition to the condition block.
3789
    // Because the condition itself may contain control-flow, new blocks may
3790
    // be created.  Thus we update "Succ" after adding the condition.
3791
1.25k
    Block = ExitConditionBlock;
3792
1.25k
    Block = EntryConditionBlock = addStmt(C);
3793
3794
    // If this block contains a condition variable, add both the condition
3795
    // variable and initializer to the CFG.
3796
1.25k
    if (VarDecl *VD = W->getConditionVariable()) {
3797
40
      if (Expr *Init = VD->getInit()) {
3798
40
        autoCreateBlock();
3799
40
        const DeclStmt *DS = W->getConditionVariableDeclStmt();
3800
40
        assert(DS->isSingleDecl());
3801
0
        findConstructionContexts(
3802
40
            ConstructionContextLayer::create(cfg->getBumpVectorContext(),
3803
40
                                             const_cast<DeclStmt *>(DS)),
3804
40
            Init);
3805
40
        appendStmt(Block, DS);
3806
40
        EntryConditionBlock = addStmt(Init);
3807
40
        assert(Block == EntryConditionBlock);
3808
0
        maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3809
40
      }
3810
40
    }
3811
3812
1.25k
    if (Block && badCFG)
3813
1
      return nullptr;
3814
3815
    // See if this is a known constant.
3816
1.25k
    const TryResult& KnownVal = tryEvaluateBool(C);
3817
3818
    // Add the loop body entry as a successor to the condition.
3819
1.25k
    addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? 
nullptr62
:
BodyBlock1.19k
);
3820
    // Link up the condition block with the code that follows the loop.  (the
3821
    // false branch).
3822
1.25k
    addSuccessor(ExitConditionBlock,
3823
1.25k
                 KnownVal.isTrue() ? 
nullptr247
:
LoopSuccessor1.00k
);
3824
1.25k
  } while(false);
3825
3826
  // Link up the loop-back block to the entry condition block.
3827
1.28k
  addSuccessor(TransitionBlock, EntryConditionBlock);
3828
3829
  // There can be no more statements in the condition block since we loop back
3830
  // to this block.  NULL out Block to force lazy creation of another block.
3831
1.28k
  Block = nullptr;
3832
3833
  // Return the condition block, which is the dominating block for the loop.
3834
1.28k
  Succ = EntryConditionBlock;
3835
1.28k
  return EntryConditionBlock;
3836
1.28k
}
3837
3838
0
CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
3839
  // FIXME: For now we pretend that @catch and the code it contains does not
3840
  //  exit.
3841
0
  return Block;
3842
0
}
3843
3844
13
CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
3845
  // FIXME: This isn't complete.  We basically treat @throw like a return
3846
  //  statement.
3847
3848
  // If we were in the middle of a block we stop processing that block.
3849
13
  if (badCFG)
3850
0
    return nullptr;
3851
3852
  // Create the new block.
3853
13
  Block = createBlock(false);
3854
3855
  // The Exit block is the only successor.
3856
13
  addSuccessor(Block, &cfg->getExit());
3857
3858
  // Add the statement to the block.  This may create new blocks if S contains
3859
  // control-flow (short-circuit operations).
3860
13
  return VisitStmt(S, AddStmtChoice::AlwaysAdd);
3861
13
}
3862
3863
CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,
3864
17.8k
                                           AddStmtChoice asc) {
3865
17.8k
  findConstructionContextsForArguments(ME);
3866
3867
17.8k
  autoCreateBlock();
3868
17.8k
  appendObjCMessage(Block, ME);
3869
3870
17.8k
  return VisitChildren(ME);
3871
17.8k
}
3872
3873
194
CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
3874
  // If we were in the middle of a block we stop processing that block.
3875
194
  if (badCFG)
3876
0
    return nullptr;
3877
3878
  // Create the new block.
3879
194
  Block = createBlock(false);
3880
3881
194
  if (TryTerminatedBlock)
3882
    // The current try statement is the only successor.
3883
84
    addSuccessor(Block, TryTerminatedBlock);
3884
110
  else
3885
    // otherwise the Exit block is the only successor.
3886
110
    addSuccessor(Block, &cfg->getExit());
3887
3888
  // Add the statement to the block.  This may create new blocks if S contains
3889
  // control-flow (short-circuit operations).
3890
194
  return VisitStmt(T, AddStmtChoice::AlwaysAdd);
3891
194
}
3892
3893
593
CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
3894
593
  CFGBlock *LoopSuccessor = nullptr;
3895
3896
593
  addLoopExit(D);
3897
3898
  // "do...while" is a control-flow statement.  Thus we stop processing the
3899
  // current block.
3900
593
  if (Block) {
3901
443
    if (badCFG)
3902
0
      return nullptr;
3903
443
    LoopSuccessor = Block;
3904
443
  } else
3905
150
    LoopSuccessor = Succ;
3906
3907
  // Because of short-circuit evaluation, the condition of the loop can span
3908
  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
3909
  // evaluate the condition.
3910
593
  CFGBlock *ExitConditionBlock = createBlock(false);
3911
593
  CFGBlock *EntryConditionBlock = ExitConditionBlock;
3912
3913
  // Set the terminator for the "exit" condition block.
3914
593
  ExitConditionBlock->setTerminator(D);
3915
3916
  // Now add the actual condition to the condition block.  Because the condition
3917
  // itself may contain control-flow, new blocks may be created.
3918
593
  if (Stmt *C = D->getCond()) {
3919
593
    Block = ExitConditionBlock;
3920
593
    EntryConditionBlock = addStmt(C);
3921
593
    if (Block) {
3922
593
      if (badCFG)
3923
0
        return nullptr;
3924
593
    }
3925
593
  }
3926
3927
  // The condition block is the implicit successor for the loop body.
3928
593
  Succ = EntryConditionBlock;
3929
3930
  // See if this is a known constant.
3931
593
  const TryResult &KnownVal = tryEvaluateBool(D->getCond());
3932
3933
  // Process the loop body.
3934
593
  CFGBlock *BodyBlock = nullptr;
3935
593
  {
3936
593
    assert(D->getBody());
3937
3938
    // Save the current values for Block, Succ, and continue and break targets
3939
0
    SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3940
593
    SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3941
593
        save_break(BreakJumpTarget);
3942
3943
    // All continues within this loop should go to the condition block
3944
593
    ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
3945
3946
    // All breaks should go to the code following the loop.
3947
593
    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3948
3949
    // NULL out Block to force lazy instantiation of blocks for the body.
3950
593
    Block = nullptr;
3951
3952
    // If body is not a compound statement create implicit scope
3953
    // and add destructors.
3954
593
    if (!isa<CompoundStmt>(D->getBody()))
3955
64
      addLocalScopeAndDtors(D->getBody());
3956
3957
    // Create the body.  The returned block is the entry to the loop body.
3958
593
    BodyBlock = addStmt(D->getBody());
3959
3960
593
    if (!BodyBlock)
3961
49
      BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
3962
544
    else if (Block) {
3963
537
      if (badCFG)
3964
0
        return nullptr;
3965
537
    }
3966
3967
    // Add an intermediate block between the BodyBlock and the
3968
    // ExitConditionBlock to represent the "loop back" transition.  Create an
3969
    // empty block to represent the transition block for looping back to the
3970
    // head of the loop.
3971
    // FIXME: Can we do this more efficiently without adding another block?
3972
593
    Block = nullptr;
3973
593
    Succ = BodyBlock;
3974
593
    CFGBlock *LoopBackBlock = createBlock();
3975
593
    LoopBackBlock->setLoopTarget(D);
3976
3977
593
    if (!KnownVal.isFalse())
3978
      // Add the loop body entry as a successor to the condition.
3979
198
      addSuccessor(ExitConditionBlock, LoopBackBlock);
3980
395
    else
3981
395
      addSuccessor(ExitConditionBlock, nullptr);
3982
593
  }
3983
3984
  // Link up the condition block with the code that follows the loop.
3985
  // (the false branch).
3986
593
  addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? 
nullptr35
:
LoopSuccessor558
);
3987
3988
  // There can be no more statements in the body block(s) since we loop back to
3989
  // the body.  NULL out Block to force lazy creation of another block.
3990
593
  Block = nullptr;
3991
3992
  // Return the loop body, which is the dominating block for the loop.
3993
593
  Succ = BodyBlock;
3994
593
  return BodyBlock;
3995
593
}
3996
3997
10.9k
CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
3998
  // "continue" is a control-flow statement.  Thus we stop processing the
3999
  // current block.
4000
10.9k
  if (badCFG)
4001
0
    return nullptr;
4002
4003
  // Now create a new block that ends with the continue statement.
4004
10.9k
  Block = createBlock(false);
4005
10.9k
  Block->setTerminator(C);
4006
4007
  // If there is no target for the continue, then we are looking at an
4008
  // incomplete AST.  This means the CFG cannot be constructed.
4009
10.9k
  if (ContinueJumpTarget.block) {
4010
10.9k
    addAutomaticObjHandling(ScopePos, ContinueJumpTarget.scopePosition, C);
4011
10.9k
    addSuccessor(Block, ContinueJumpTarget.block);
4012
10.9k
  } else
4013
2
    badCFG = true;
4014
4015
10.9k
  return Block;
4016
10.9k
}
4017
4018
CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
4019
7.55k
                                                    AddStmtChoice asc) {
4020
7.55k
  if (asc.alwaysAdd(*this, E)) {
4021
1.91k
    autoCreateBlock();
4022
1.91k
    appendStmt(Block, E);
4023
1.91k
  }
4024
4025
  // VLA types have expressions that must be evaluated.
4026
  // Evaluation is done only for `sizeof`.
4027
4028
7.55k
  if (E->getKind() != UETT_SizeOf)
4029
43
    return Block;
4030
4031
7.51k
  CFGBlock *lastBlock = Block;
4032
4033
7.51k
  if (E->isArgumentType()) {
4034
6.61k
    for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
4035
6.65k
         VA != nullptr; 
VA = FindVA(VA->getElementType().getTypePtr())44
)
4036
44
      lastBlock = addStmt(VA->getSizeExpr());
4037
6.61k
  }
4038
7.51k
  return lastBlock;
4039
7.55k
}
4040
4041
/// VisitStmtExpr - Utility method to handle (nested) statement
4042
///  expressions (a GCC extension).
4043
3.73k
CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
4044
3.73k
  if (asc.alwaysAdd(*this, SE)) {
4045
2.47k
    autoCreateBlock();
4046
2.47k
    appendStmt(Block, SE);
4047
2.47k
  }
4048
3.73k
  return VisitCompoundStmt(SE->getSubStmt(), /*ExternallyDestructed=*/true);
4049
3.73k
}
4050
4051
838
CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
4052
  // "switch" is a control-flow statement.  Thus we stop processing the current
4053
  // block.
4054
838
  CFGBlock *SwitchSuccessor = nullptr;
4055
4056
  // Save local scope position because in case of condition variable ScopePos
4057
  // won't be restored when traversing AST.
4058
838
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4059
4060
  // Create local scope for C++17 switch init-stmt if one exists.
4061
838
  if (Stmt *Init = Terminator->getInit())
4062
11
    addLocalScopeForStmt(Init);
4063
4064
  // Create local scope for possible condition variable.
4065
  // Store scope position. Add implicit destructor.
4066
838
  if (VarDecl *VD = Terminator->getConditionVariable())
4067
29
    addLocalScopeForVarDecl(VD);
4068
4069
838
  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), Terminator);
4070
4071
838
  if (Block) {
4072
487
    if (badCFG)
4073
0
      return nullptr;
4074
487
    SwitchSuccessor = Block;
4075
487
  } else 
SwitchSuccessor = Succ351
;
4076
4077
  // Save the current "switch" context.
4078
838
  SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
4079
838
                            save_default(DefaultCaseBlock);
4080
838
  SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
4081
4082
  // Set the "default" case to be the block after the switch statement.  If the
4083
  // switch statement contains a "default:", this value will be overwritten with
4084
  // the block for that code.
4085
838
  DefaultCaseBlock = SwitchSuccessor;
4086
4087
  // Create a new block that will contain the switch statement.
4088
838
  SwitchTerminatedBlock = createBlock(false);
4089
4090
  // Now process the switch body.  The code after the switch is the implicit
4091
  // successor.
4092
838
  Succ = SwitchSuccessor;
4093
838
  BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
4094
4095
  // When visiting the body, the case statements should automatically get linked
4096
  // up to the switch.  We also don't keep a pointer to the body, since all
4097
  // control-flow from the switch goes to case/default statements.
4098
838
  assert(Terminator->getBody() && "switch must contain a non-NULL body");
4099
0
  Block = nullptr;
4100
4101
  // For pruning unreachable case statements, save the current state
4102
  // for tracking the condition value.
4103
838
  SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
4104
838
                                                     false);
4105
4106
  // Determine if the switch condition can be explicitly evaluated.
4107
838
  assert(Terminator->getCond() && "switch condition must be non-NULL");
4108
0
  Expr::EvalResult result;
4109
838
  bool b = tryEvaluate(Terminator->getCond(), result);
4110
838
  SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
4111
838
                                                    b ? 
&result120
:
nullptr718
);
4112
4113
  // If body is not a compound statement create implicit scope
4114
  // and add destructors.
4115
838
  if (!isa<CompoundStmt>(Terminator->getBody()))
4116
70
    addLocalScopeAndDtors(Terminator->getBody());
4117
4118
838
  addStmt(Terminator->getBody());
4119
838
  if (Block) {
4120
27
    if (badCFG)
4121
0
      return nullptr;
4122
27
  }
4123
4124
  // If we have no "default:" case, the default transition is to the code
4125
  // following the switch body.  Moreover, take into account if all the
4126
  // cases of a switch are covered (e.g., switching on an enum value).
4127
  //
4128
  // Note: We add a successor to a switch that is considered covered yet has no
4129
  //       case statements if the enumeration has no enumerators.
4130
838
  bool SwitchAlwaysHasSuccessor = false;
4131
838
  SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
4132
838
  SwitchAlwaysHasSuccessor |= Terminator->isAllEnumCasesCovered() &&
4133
838
                              
Terminator->getSwitchCaseList()107
;
4134
838
  addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock,
4135
838
               !SwitchAlwaysHasSuccessor);
4136
4137
  // Add the terminator and condition in the switch block.
4138
838
  SwitchTerminatedBlock->setTerminator(Terminator);
4139
838
  Block = SwitchTerminatedBlock;
4140
838
  CFGBlock *LastBlock = addStmt(Terminator->getCond());
4141
4142
  // If the SwitchStmt contains a condition variable, add both the
4143
  // SwitchStmt and the condition variable initialization to the CFG.
4144
838
  if (VarDecl *VD = Terminator->getConditionVariable()) {
4145
29
    if (Expr *Init = VD->getInit()) {
4146
29
      autoCreateBlock();
4147
29
      appendStmt(Block, Terminator->getConditionVariableDeclStmt());
4148
29
      LastBlock = addStmt(Init);
4149
29
      maybeAddScopeBeginForVarDecl(LastBlock, VD, Init);
4150
29
    }
4151
29
  }
4152
4153
  // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
4154
838
  if (Stmt *Init = Terminator->getInit()) {
4155
11
    autoCreateBlock();
4156
11
    LastBlock = addStmt(Init);
4157
11
  }
4158
4159
838
  return LastBlock;
4160
838
}
4161
4162
static bool shouldAddCase(bool &switchExclusivelyCovered,
4163
                          const Expr::EvalResult *switchCond,
4164
                          const CaseStmt *CS,
4165
2.09k
                          ASTContext &Ctx) {
4166
2.09k
  if (!switchCond)
4167
1.89k
    return true;
4168
4169
198
  bool addCase = false;
4170
4171
198
  if (!switchExclusivelyCovered) {
4172
167
    if (switchCond->Val.isInt()) {
4173
      // Evaluate the LHS of the case value.
4174
167
      const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
4175
167
      const llvm::APSInt &condInt = switchCond->Val.getInt();
4176
4177
167
      if (condInt == lhsInt) {
4178
99
        addCase = true;
4179
99
        switchExclusivelyCovered = true;
4180
99
      }
4181
68
      else if (condInt > lhsInt) {
4182
39
        if (const Expr *RHS = CS->getRHS()) {
4183
          // Evaluate the RHS of the case value.
4184
2
          const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
4185
2
          if (V2 >= condInt) {
4186
2
            addCase = true;
4187
2
            switchExclusivelyCovered = true;
4188
2
          }
4189
2
        }
4190
39
      }
4191
167
    }
4192
0
    else
4193
0
      addCase = true;
4194
167
  }
4195
198
  return addCase;
4196
2.09k
}
4197
4198
2.02k
CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
4199
  // CaseStmts are essentially labels, so they are the first statement in a
4200
  // block.
4201
2.02k
  CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
4202
4203
2.02k
  if (Stmt *Sub = CS->getSubStmt()) {
4204
    // For deeply nested chains of CaseStmts, instead of doing a recursion
4205
    // (which can blow out the stack), manually unroll and create blocks
4206
    // along the way.
4207
2.09k
    while (isa<CaseStmt>(Sub)) {
4208
68
      CFGBlock *currentBlock = createBlock(false);
4209
68
      currentBlock->setLabel(CS);
4210
4211
68
      if (TopBlock)
4212
29
        addSuccessor(LastBlock, currentBlock);
4213
39
      else
4214
39
        TopBlock = currentBlock;
4215
4216
68
      addSuccessor(SwitchTerminatedBlock,
4217
68
                   shouldAddCase(switchExclusivelyCovered, switchCond,
4218
68
                                 CS, *Context)
4219
68
                   ? currentBlock : 
nullptr0
);
4220
4221
68
      LastBlock = currentBlock;
4222
68
      CS = cast<CaseStmt>(Sub);
4223
68
      Sub = CS->getSubStmt();
4224
68
    }
4225
4226
2.02k
    addStmt(Sub);
4227
2.02k
  }
4228
4229
2.02k
  CFGBlock *CaseBlock = Block;
4230
2.02k
  if (!CaseBlock)
4231
167
    CaseBlock = createBlock();
4232
4233
  // Cases statements partition blocks, so this is the top of the basic block we
4234
  // were processing (the "case XXX:" is the label).
4235
2.02k
  CaseBlock->setLabel(CS);
4236
4237
2.02k
  if (badCFG)
4238
0
    return nullptr;
4239
4240
  // Add this block to the list of successors for the block with the switch
4241
  // statement.
4242
2.02k
  assert(SwitchTerminatedBlock);
4243
0
  addSuccessor(SwitchTerminatedBlock, CaseBlock,
4244
2.02k
               shouldAddCase(switchExclusivelyCovered, switchCond,
4245
2.02k
                             CS, *Context));
4246
4247
  // We set Block to NULL to allow lazy creation of a new block (if necessary)
4248
2.02k
  Block = nullptr;
4249
4250
2.02k
  if (TopBlock) {
4251
39
    addSuccessor(LastBlock, CaseBlock);
4252
39
    Succ = TopBlock;
4253
1.98k
  } else {
4254
    // This block is now the implicit successor of other blocks.
4255
1.98k
    Succ = CaseBlock;
4256
1.98k
  }
4257
4258
2.02k
  return Succ;
4259
2.02k
}
4260
4261
382
CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
4262
382
  if (Terminator->getSubStmt())
4263
382
    addStmt(Terminator->getSubStmt());
4264
4265
382
  DefaultCaseBlock = Block;
4266
4267
382
  if (!DefaultCaseBlock)
4268
42
    DefaultCaseBlock = createBlock();
4269
4270
  // Default statements partition blocks, so this is the top of the basic block
4271
  // we were processing (the "default:" is the label).
4272
382
  DefaultCaseBlock->setLabel(Terminator);
4273
4274
382
  if (badCFG)
4275
0
    return nullptr;
4276
4277
  // Unlike case statements, we don't add the default block to the successors
4278
  // for the switch statement immediately.  This is done when we finish
4279
  // processing the switch statement.  This allows for the default case
4280
  // (including a fall-through to the code after the switch statement) to always
4281
  // be the last successor of a switch-terminated block.
4282
4283
  // We set Block to NULL to allow lazy creation of a new block (if necessary)
4284
382
  Block = nullptr;
4285
4286
  // This block is now the implicit successor of other blocks.
4287
382
  Succ = DefaultCaseBlock;
4288
4289
382
  return DefaultCaseBlock;
4290
382
}
4291
4292
185
CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
4293
  // "try"/"catch" is a control-flow statement.  Thus we stop processing the
4294
  // current block.
4295
185
  CFGBlock *TrySuccessor = nullptr;
4296
4297
185
  if (Block) {
4298
62
    if (badCFG)
4299
0
      return nullptr;
4300
62
    TrySuccessor = Block;
4301
123
  } else TrySuccessor = Succ;
4302
4303
185
  CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4304
4305
  // Create a new block that will contain the try statement.
4306
185
  CFGBlock *NewTryTerminatedBlock = createBlock(false);
4307
  // Add the terminator in the try block.
4308
185
  NewTryTerminatedBlock->setTerminator(Terminator);
4309
4310
185
  bool HasCatchAll = false;
4311
373
  for (unsigned h = 0; h <Terminator->getNumHandlers(); 
++h188
) {
4312
    // The code after the try is the implicit successor.
4313
188
    Succ = TrySuccessor;
4314
188
    CXXCatchStmt *CS = Terminator->getHandler(h);
4315
188
    if (CS->getExceptionDecl() == nullptr) {
4316
57
      HasCatchAll = true;
4317
57
    }
4318
188
    Block = nullptr;
4319
188
    CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
4320
188
    if (!CatchBlock)
4321
0
      return nullptr;
4322
    // Add this block to the list of successors for the block with the try
4323
    // statement.
4324
188
    addSuccessor(NewTryTerminatedBlock, CatchBlock);
4325
188
  }
4326
185
  if (!HasCatchAll) {
4327
128
    if (PrevTryTerminatedBlock)
4328
7
      addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
4329
121
    else
4330
121
      addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
4331
128
  }
4332
4333
  // The code after the try is the implicit successor.
4334
185
  Succ = TrySuccessor;
4335
4336
  // Save the current "try" context.
4337
185
  SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
4338
185
  cfg->addTryDispatchBlock(TryTerminatedBlock);
4339
4340
185
  assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
4341
0
  Block = nullptr;
4342
185
  return addStmt(Terminator->getTryBlock());
4343
185
}
4344
4345
188
CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
4346
  // CXXCatchStmt are treated like labels, so they are the first statement in a
4347
  // block.
4348
4349
  // Save local scope position because in case of exception variable ScopePos
4350
  // won't be restored when traversing AST.
4351
188
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4352
4353
  // Create local scope for possible exception variable.
4354
  // Store scope position. Add implicit destructor.
4355
188
  if (VarDecl *VD = CS->getExceptionDecl()) {
4356
131
    LocalScope::const_iterator BeginScopePos = ScopePos;
4357
131
    addLocalScopeForVarDecl(VD);
4358
131
    addAutomaticObjHandling(ScopePos, BeginScopePos, CS);
4359
131
  }
4360
4361
188
  if (CS->getHandlerBlock())
4362
188
    addStmt(CS->getHandlerBlock());
4363
4364
188
  CFGBlock *CatchBlock = Block;
4365
188
  if (!CatchBlock)
4366
103
    CatchBlock = createBlock();
4367
4368
  // CXXCatchStmt is more than just a label.  They have semantic meaning
4369
  // as well, as they implicitly "initialize" the catch variable.  Add
4370
  // it to the CFG as a CFGElement so that the control-flow of these
4371
  // semantics gets captured.
4372
188
  appendStmt(CatchBlock, CS);
4373
4374
  // Also add the CXXCatchStmt as a label, to mirror handling of regular
4375
  // labels.
4376
188
  CatchBlock->setLabel(CS);
4377
4378
  // Bail out if the CFG is bad.
4379
188
  if (badCFG)
4380
0
    return nullptr;
4381
4382
  // We set Block to NULL to allow lazy creation of a new block (if necessary)
4383
188
  Block = nullptr;
4384
4385
188
  return CatchBlock;
4386
188
}
4387
4388
213
CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
4389
  // C++0x for-range statements are specified as [stmt.ranged]:
4390
  //
4391
  // {
4392
  //   auto && __range = range-init;
4393
  //   for ( auto __begin = begin-expr,
4394
  //         __end = end-expr;
4395
  //         __begin != __end;
4396
  //         ++__begin ) {
4397
  //     for-range-declaration = *__begin;
4398
  //     statement
4399
  //   }
4400
  // }
4401
4402
  // Save local scope position before the addition of the implicit variables.
4403
213
  SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4404
4405
  // Create local scopes and destructors for range, begin and end variables.
4406
213
  if (Stmt *Range = S->getRangeStmt())
4407
213
    addLocalScopeForStmt(Range);
4408
213
  if (Stmt *Begin = S->getBeginStmt())
4409
212
    addLocalScopeForStmt(Begin);
4410
213
  if (Stmt *End = S->getEndStmt())
4411
212
    addLocalScopeForStmt(End);
4412
213
  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), S);
4413
4414
213
  LocalScope::const_iterator ContinueScopePos = ScopePos;
4415
4416
  // "for" is a control-flow statement.  Thus we stop processing the current
4417
  // block.
4418
213
  CFGBlock *LoopSuccessor = nullptr;
4419
213
  if (Block) {
4420
142
    if (badCFG)
4421
0
      return nullptr;
4422
142
    LoopSuccessor = Block;
4423
142
  } else
4424
71
    LoopSuccessor = Succ;
4425
4426
  // Save the current value for the break targets.
4427
  // All breaks should go to the code following the loop.
4428
213
  SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
4429
213
  BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4430
4431
  // The block for the __begin != __end expression.
4432
213
  CFGBlock *ConditionBlock = createBlock(false);
4433
213
  ConditionBlock->setTerminator(S);
4434
4435
  // Now add the actual condition to the condition block.
4436
213
  if (Expr *C = S->getCond()) {
4437
212
    Block = ConditionBlock;
4438
212
    CFGBlock *BeginConditionBlock = addStmt(C);
4439
212
    if (badCFG)
4440
0
      return nullptr;
4441
212
    assert(BeginConditionBlock == ConditionBlock &&
4442
212
           "condition block in for-range was unexpectedly complex");
4443
0
    (void)BeginConditionBlock;
4444
212
  }
4445
4446
  // The condition block is the implicit successor for the loop body as well as
4447
  // any code above the loop.
4448
213
  Succ = ConditionBlock;
4449
4450
  // See if this is a known constant.
4451
213
  TryResult KnownVal(true);
4452
4453
213
  if (S->getCond())
4454
212
    KnownVal = tryEvaluateBool(S->getCond());
4455
4456
  // Now create the loop body.
4457
213
  {
4458
213
    assert(S->getBody());
4459
4460
    // Save the current values for Block, Succ, and continue targets.
4461
0
    SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
4462
213
    SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
4463
4464
    // Generate increment code in its own basic block.  This is the target of
4465
    // continue statements.
4466
213
    Block = nullptr;
4467
213
    Succ = addStmt(S->getInc());
4468
213
    if (badCFG)
4469
1
      return nullptr;
4470
212
    ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
4471
4472
    // The starting block for the loop increment is the block that should
4473
    // represent the 'loop target' for looping back to the start of the loop.
4474
212
    ContinueJumpTarget.block->setLoopTarget(S);
4475
4476
    // Finish up the increment block and prepare to start the loop body.
4477
212
    assert(Block);
4478
212
    if (badCFG)
4479
0
      return nullptr;
4480
212
    Block = nullptr;
4481
4482
    // Add implicit scope and dtors for loop variable.
4483
212
    addLocalScopeAndDtors(S->getLoopVarStmt());
4484
4485
    // If body is not a compound statement create implicit scope
4486
    // and add destructors.
4487
212
    if (!isa<CompoundStmt>(S->getBody()))
4488
48
      addLocalScopeAndDtors(S->getBody());
4489
4490
    // Populate a new block to contain the loop body and loop variable.
4491
212
    addStmt(S->getBody());
4492
4493
212
    if (badCFG)
4494
0
      return nullptr;
4495
212
    CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt());
4496
212
    if (badCFG)
4497
0
      return nullptr;
4498
4499
    // This new body block is a successor to our condition block.
4500
212
    addSuccessor(ConditionBlock,
4501
212
                 KnownVal.isFalse() ? 
nullptr0
: LoopVarStmtBlock);
4502
212
  }
4503
4504
  // Link up the condition block with the code that follows the loop (the
4505
  // false branch).
4506
212
  addSuccessor(ConditionBlock, KnownVal.isTrue() ? 
nullptr0
: LoopSuccessor);
4507
4508
  // Add the initialization statements.
4509
212
  Block = createBlock();
4510
212
  addStmt(S->getBeginStmt());
4511
212
  addStmt(S->getEndStmt());
4512
212
  CFGBlock *Head = addStmt(S->getRangeStmt());
4513
212
  if (S->getInit())
4514
2
    Head = addStmt(S->getInit());
4515
212
  return Head;
4516
212
}
4517
4518
CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
4519
8.86k
    AddStmtChoice asc, bool ExternallyDestructed) {
4520
8.86k
  if (BuildOpts.AddTemporaryDtors) {
4521
    // If adding implicit destructors visit the full expression for adding
4522
    // destructors of temporaries.
4523
8.66k
    TempDtorContext Context;
4524
8.66k
    VisitForTemporaryDtors(E->getSubExpr(), ExternallyDestructed, Context);
4525
4526
    // Full expression has to be added as CFGStmt so it will be sequenced
4527
    // before destructors of it's temporaries.
4528
8.66k
    asc = asc.withAlwaysAdd(true);
4529
8.66k
  }
4530
8.86k
  return Visit(E->getSubExpr(), asc);
4531
8.86k
}
4532
4533
CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
4534
6.03k
                                                AddStmtChoice asc) {
4535
6.03k
  if (asc.alwaysAdd(*this, E)) {
4536
4.02k
    autoCreateBlock();
4537
4.02k
    appendStmt(Block, E);
4538
4539
4.02k
    findConstructionContexts(
4540
4.02k
        ConstructionContextLayer::create(cfg->getBumpVectorContext(), E),
4541
4.02k
        E->getSubExpr());
4542
4543
    // We do not want to propagate the AlwaysAdd property.
4544
4.02k
    asc = asc.withAlwaysAdd(false);
4545
4.02k
  }
4546
6.03k
  return Visit(E->getSubExpr(), asc);
4547
6.03k
}
4548
4549
CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
4550
36.3k
                                            AddStmtChoice asc) {
4551
  // If the constructor takes objects as arguments by value, we need to properly
4552
  // construct these objects. Construction contexts we find here aren't for the
4553
  // constructor C, they're for its arguments only.
4554
36.3k
  findConstructionContextsForArguments(C);
4555
4556
36.3k
  autoCreateBlock();
4557
36.3k
  appendConstructor(Block, C);
4558
4559
36.3k
  return VisitChildren(C);
4560
36.3k
}
4561
4562
CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
4563
2.45k
                                      AddStmtChoice asc) {
4564
2.45k
  autoCreateBlock();
4565
2.45k
  appendStmt(Block, NE);
4566
4567
2.45k
  findConstructionContexts(
4568
2.45k
      ConstructionContextLayer::create(cfg->getBumpVectorContext(), NE),
4569
2.45k
      const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
4570
4571
2.45k
  if (NE->getInitializer())
4572
1.54k
    Block = Visit(NE->getInitializer());
4573
4574
2.45k
  if (BuildOpts.AddCXXNewAllocator)
4575
1.88k
    appendNewAllocator(Block, NE);
4576
4577
2.45k
  if (NE->isArray() && 
*NE->getArraySize()433
)
4578
433
    Block = Visit(*NE->getArraySize());
4579
4580
2.45k
  for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
4581
2.95k
       E = NE->placement_arg_end(); I != E; 
++I502
)
4582
502
    Block = Visit(*I);
4583
4584
2.45k
  return Block;
4585
2.45k
}
4586
4587
CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
4588
1.14k
                                         AddStmtChoice asc) {
4589
1.14k
  autoCreateBlock();
4590
1.14k
  appendStmt(Block, DE);
4591
1.14k
  QualType DTy = DE->getDestroyedType();
4592
1.14k
  if (!DTy.isNull()) {
4593
1.14k
    DTy = DTy.getNonReferenceType();
4594
1.14k
    CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
4595
1.14k
    if (RD) {
4596
411
      if (RD->isCompleteDefinition() && 
!RD->hasTrivialDestructor()408
)
4597
230
        appendDeleteDtor(Block, RD, DE);
4598
411
    }
4599
1.14k
  }
4600
4601
1.14k
  return VisitChildren(DE);
4602
1.14k
}
4603
4604
CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
4605
3.24k
                                                 AddStmtChoice asc) {
4606
3.24k
  if (asc.alwaysAdd(*this, E)) {
4607
2.53k
    autoCreateBlock();
4608
2.53k
    appendStmt(Block, E);
4609
    // We do not want to propagate the AlwaysAdd property.
4610
2.53k
    asc = asc.withAlwaysAdd(false);
4611
2.53k
  }
4612
3.24k
  return Visit(E->getSubExpr(), asc);
4613
3.24k
}
4614
4615
CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
4616
4.64k
                                                  AddStmtChoice asc) {
4617
  // If the constructor takes objects as arguments by value, we need to properly
4618
  // construct these objects. Construction contexts we find here aren't for the
4619
  // constructor C, they're for its arguments only.
4620
4.64k
  findConstructionContextsForArguments(C);
4621
4622
4.64k
  autoCreateBlock();
4623
4.64k
  appendConstructor(Block, C);
4624
4.64k
  return VisitChildren(C);
4625
4.64k
}
4626
4627
CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
4628
1.66M
                                            AddStmtChoice asc) {
4629
1.66M
  if (asc.alwaysAdd(*this, E)) {
4630
1.66M
    autoCreateBlock();
4631
1.66M
    appendStmt(Block, E);
4632
1.66M
  }
4633
4634
1.66M
  if (E->getCastKind() == CK_IntegralToBoolean)
4635
81.5k
    tryEvaluateBool(E->getSubExpr()->IgnoreParens());
4636
4637
1.66M
  return Visit(E->getSubExpr(), AddStmtChoice());
4638
1.66M
}
4639
4640
71
CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {
4641
71
  return Visit(E->getSubExpr(), AddStmtChoice());
4642
71
}
4643
4644
24
CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
4645
  // Lazily create the indirect-goto dispatch block if there isn't one already.
4646
24
  CFGBlock *IBlock = cfg->getIndirectGotoBlock();
4647
4648
24
  if (!IBlock) {
4649
21
    IBlock = createBlock(false);
4650
21
    cfg->setIndirectGotoBlock(IBlock);
4651
21
  }
4652
4653
  // IndirectGoto is a control-flow statement.  Thus we stop processing the
4654
  // current block and create a new one.
4655
24
  if (badCFG)
4656
0
    return nullptr;
4657
4658
24
  Block = createBlock(false);
4659
24
  Block->setTerminator(I);
4660
24
  addSuccessor(Block, IBlock);
4661
24
  return addStmt(I->getTarget());
4662
24
}
4663
4664
CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,
4665
96.5k
                                             TempDtorContext &Context) {
4666
96.5k
  assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors);
4667
4668
145k
tryAgain:
4669
145k
  if (!E) {
4670
0
    badCFG = true;
4671
0
    return nullptr;
4672
0
  }
4673
145k
  switch (E->getStmtClass()) {
4674
83.6k
    default:
4675
83.6k
      return VisitChildrenForTemporaryDtors(E, false, Context);
4676
4677
1.29k
    case Stmt::InitListExprClass:
4678
1.29k
      return VisitChildrenForTemporaryDtors(E, ExternallyDestructed, Context);
4679
4680
2.65k
    case Stmt::BinaryOperatorClass:
4681
2.65k
      return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E),
4682
2.65k
                                                  ExternallyDestructed,
4683
2.65k
                                                  Context);
4684
4685
6.43k
    case Stmt::CXXBindTemporaryExprClass:
4686
6.43k
      return VisitCXXBindTemporaryExprForTemporaryDtors(
4687
6.43k
          cast<CXXBindTemporaryExpr>(E), ExternallyDestructed, Context);
4688
4689
36
    case Stmt::BinaryConditionalOperatorClass:
4690
293
    case Stmt::ConditionalOperatorClass:
4691
293
      return VisitConditionalOperatorForTemporaryDtors(
4692
293
          cast<AbstractConditionalOperator>(E), ExternallyDestructed, Context);
4693
4694
26.5k
    case Stmt::ImplicitCastExprClass:
4695
      // For implicit cast we want ExternallyDestructed to be passed further.
4696
26.5k
      E = cast<CastExpr>(E)->getSubExpr();
4697
26.5k
      goto tryAgain;
4698
4699
2.16k
    case Stmt::CXXFunctionalCastExprClass:
4700
      // For functional cast we want ExternallyDestructed to be passed further.
4701
2.16k
      E = cast<CXXFunctionalCastExpr>(E)->getSubExpr();
4702
2.16k
      goto tryAgain;
4703
4704
6
    case Stmt::ConstantExprClass:
4705
6
      E = cast<ConstantExpr>(E)->getSubExpr();
4706
6
      goto tryAgain;
4707
4708
443
    case Stmt::ParenExprClass:
4709
443
      E = cast<ParenExpr>(E)->getSubExpr();
4710
443
      goto tryAgain;
4711
4712
18.5k
    case Stmt::MaterializeTemporaryExprClass: {
4713
18.5k
      const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E);
4714
18.5k
      ExternallyDestructed = (MTE->getStorageDuration() != SD_FullExpression);
4715
18.5k
      SmallVector<const Expr *, 2> CommaLHSs;
4716
18.5k
      SmallVector<SubobjectAdjustment, 2> Adjustments;
4717
      // Find the expression whose lifetime needs to be extended.
4718
18.5k
      E = const_cast<Expr *>(
4719
18.5k
          cast<MaterializeTemporaryExpr>(E)
4720
18.5k
              ->getSubExpr()
4721
18.5k
              ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments));
4722
      // Visit the skipped comma operator left-hand sides for other temporaries.
4723
18.5k
      for (const Expr *CommaLHS : CommaLHSs) {
4724
40
        VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS),
4725
40
                               /*ExternallyDestructed=*/false, Context);
4726
40
      }
4727
18.5k
      goto tryAgain;
4728
36
    }
4729
4730
1.05k
    case Stmt::BlockExprClass:
4731
      // Don't recurse into blocks; their subexpressions don't get evaluated
4732
      // here.
4733
1.05k
      return Block;
4734
4735
1.02k
    case Stmt::LambdaExprClass: {
4736
      // For lambda expressions, only recurse into the capture initializers,
4737
      // and not the body.
4738
1.02k
      auto *LE = cast<LambdaExpr>(E);
4739
1.02k
      CFGBlock *B = Block;
4740
1.02k
      for (Expr *Init : LE->capture_inits()) {
4741
885
        if (Init) {
4742
869
          if (CFGBlock *R = VisitForTemporaryDtors(
4743
869
                  Init, /*ExternallyDestructed=*/true, Context))
4744
703
            B = R;
4745
869
        }
4746
885
      }
4747
1.02k
      return B;
4748
36
    }
4749
4750
68
    case Stmt::StmtExprClass:
4751
      // Don't recurse into statement expressions; any cleanups inside them
4752
      // will be wrapped in their own ExprWithCleanups.
4753
68
      return Block;
4754
4755
1.59k
    case Stmt::CXXDefaultArgExprClass:
4756
1.59k
      E = cast<CXXDefaultArgExpr>(E)->getExpr();
4757
1.59k
      goto tryAgain;
4758
4759
12
    case Stmt::CXXDefaultInitExprClass:
4760
12
      E = cast<CXXDefaultInitExpr>(E)->getExpr();
4761
12
      goto tryAgain;
4762
145k
  }
4763
145k
}
4764
4765
CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E,
4766
                                                     bool ExternallyDestructed,
4767
86.1k
                                                     TempDtorContext &Context) {
4768
86.1k
  if (isa<LambdaExpr>(E)) {
4769
    // Do not visit the children of lambdas; they have their own CFGs.
4770
0
    return Block;
4771
0
  }
4772
4773
  // When visiting children for destructors we want to visit them in reverse
4774
  // order that they will appear in the CFG.  Because the CFG is built
4775
  // bottom-up, this means we visit them in their natural order, which
4776
  // reverses them in the CFG.
4777
86.1k
  CFGBlock *B = Block;
4778
86.1k
  for (Stmt *Child : E->children())
4779
67.1k
    if (Child)
4780
67.1k
      if (CFGBlock *R = VisitForTemporaryDtors(Child, ExternallyDestructed, Context))
4781
58.4k
        B = R;
4782
4783
86.1k
  return B;
4784
86.1k
}
4785
4786
CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(
4787
2.65k
    BinaryOperator *E, bool ExternallyDestructed, TempDtorContext &Context) {
4788
2.65k
  if (E->isCommaOp()) {
4789
    // For the comma operator, the LHS expression is evaluated before the RHS
4790
    // expression, so prepend temporary destructors for the LHS first.
4791
103
    CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4792
103
    CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), ExternallyDestructed, Context);
4793
103
    return RHSBlock ? 
RHSBlock102
:
LHSBlock1
;
4794
103
  }
4795
4796
2.55k
  if (E->isLogicalOp()) {
4797
1.03k
    VisitForTemporaryDtors(E->getLHS(), false, Context);
4798
1.03k
    TryResult RHSExecuted = tryEvaluateBool(E->getLHS());
4799
1.03k
    if (RHSExecuted.isKnown() && 
E->getOpcode() == BO_LOr554
)
4800
11
      RHSExecuted.negate();
4801
4802
    // We do not know at CFG-construction time whether the right-hand-side was
4803
    // executed, thus we add a branch node that depends on the temporary
4804
    // constructor call.
4805
1.03k
    TempDtorContext RHSContext(
4806
1.03k
        bothKnownTrue(Context.KnownExecuted, RHSExecuted));
4807
1.03k
    VisitForTemporaryDtors(E->getRHS(), false, RHSContext);
4808
1.03k
    InsertTempDtorDecisionBlock(RHSContext);
4809
4810
1.03k
    return Block;
4811
1.03k
  }
4812
4813
1.51k
  if (E->isAssignmentOp()) {
4814
    // For assignment operators, the RHS expression is evaluated before the LHS
4815
    // expression, so prepend temporary destructors for the RHS first.
4816
390
    CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
4817
390
    CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4818
390
    return LHSBlock ? 
LHSBlock159
:
RHSBlock231
;
4819
390
  }
4820
4821
  // Any other operator is visited normally.
4822
1.12k
  return VisitChildrenForTemporaryDtors(E, ExternallyDestructed, Context);
4823
1.51k
}
4824
4825
CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
4826
6.43k
    CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context) {
4827
  // First add destructors for temporaries in subexpression.
4828
  // Because VisitCXXBindTemporaryExpr calls setDestructed:
4829
6.43k
  CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), true, Context);
4830
6.43k
  if (!ExternallyDestructed) {
4831
    // If lifetime of temporary is not prolonged (by assigning to constant
4832
    // reference) add destructor for it.
4833
4834
5.70k
    const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
4835
4836
5.70k
    if (Dtor->getParent()->isAnyDestructorNoReturn()) {
4837
      // If the destructor is marked as a no-return destructor, we need to
4838
      // create a new block for the destructor which does not have as a
4839
      // successor anything built thus far. Control won't flow out of this
4840
      // block.
4841
280
      if (B) 
Succ = B194
;
4842
280
      Block = createNoReturnBlock();
4843
5.42k
    } else if (Context.needsTempDtorBranch()) {
4844
      // If we need to introduce a branch, we add a new block that we will hook
4845
      // up to a decision block later.
4846
807
      if (B) 
Succ = B775
;
4847
807
      Block = createBlock();
4848
4.61k
    } else {
4849
4.61k
      autoCreateBlock();
4850
4.61k
    }
4851
5.70k
    if (Context.needsTempDtorBranch()) {
4852
987
      Context.setDecisionPoint(Succ, E);
4853
987
    }
4854
5.70k
    appendTemporaryDtor(Block, E);
4855
4856
5.70k
    B = Block;
4857
5.70k
  }
4858
6.43k
  return B;
4859
6.43k
}
4860
4861
void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context,
4862
1.32k
                                             CFGBlock *FalseSucc) {
4863
1.32k
  if (!Context.TerminatorExpr) {
4864
    // If no temporary was found, we do not need to insert a decision point.
4865
440
    return;
4866
440
  }
4867
885
  assert(Context.TerminatorExpr);
4868
0
  CFGBlock *Decision = createBlock(false);
4869
885
  Decision->setTerminator(CFGTerminator(Context.TerminatorExpr,
4870
885
                                        CFGTerminator::TemporaryDtorsBranch));
4871
885
  addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse());
4872
885
  addSuccessor(Decision, FalseSucc ? 
FalseSucc102
:
Context.Succ783
,
4873
885
               !Context.KnownExecuted.isTrue());
4874
885
  Block = Decision;
4875
885
}
4876
4877
CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
4878
    AbstractConditionalOperator *E, bool ExternallyDestructed,
4879
293
    TempDtorContext &Context) {
4880
293
  VisitForTemporaryDtors(E->getCond(), false, Context);
4881
293
  CFGBlock *ConditionBlock = Block;
4882
293
  CFGBlock *ConditionSucc = Succ;
4883
293
  TryResult ConditionVal = tryEvaluateBool(E->getCond());
4884
293
  TryResult NegatedVal = ConditionVal;
4885
293
  if (NegatedVal.isKnown()) 
NegatedVal.negate()26
;
4886
4887
293
  TempDtorContext TrueContext(
4888
293
      bothKnownTrue(Context.KnownExecuted, ConditionVal));
4889
293
  VisitForTemporaryDtors(E->getTrueExpr(), ExternallyDestructed, TrueContext);
4890
293
  CFGBlock *TrueBlock = Block;
4891
4892
293
  Block = ConditionBlock;
4893
293
  Succ = ConditionSucc;
4894
293
  TempDtorContext FalseContext(
4895
293
      bothKnownTrue(Context.KnownExecuted, NegatedVal));
4896
293
  VisitForTemporaryDtors(E->getFalseExpr(), ExternallyDestructed, FalseContext);
4897
4898
293
  if (TrueContext.TerminatorExpr && 
FalseContext.TerminatorExpr134
) {
4899
102
    InsertTempDtorDecisionBlock(FalseContext, TrueBlock);
4900
191
  } else if (TrueContext.TerminatorExpr) {
4901
32
    Block = TrueBlock;
4902
32
    InsertTempDtorDecisionBlock(TrueContext);
4903
159
  } else {
4904
159
    InsertTempDtorDecisionBlock(FalseContext);
4905
159
  }
4906
293
  return Block;
4907
293
}
4908
4909
CFGBlock *CFGBuilder::VisitOMPExecutableDirective(OMPExecutableDirective *D,
4910
20.9k
                                                  AddStmtChoice asc) {
4911
20.9k
  if (asc.alwaysAdd(*this, D)) {
4912
20.9k
    autoCreateBlock();
4913
20.9k
    appendStmt(Block, D);
4914
20.9k
  }
4915
4916
  // Iterate over all used expression in clauses.
4917
20.9k
  CFGBlock *B = Block;
4918
4919
  // Reverse the elements to process them in natural order. Iterators are not
4920
  // bidirectional, so we need to create temp vector.
4921
20.9k
  SmallVector<Stmt *, 8> Used(
4922
20.9k
      OMPExecutableDirective::used_clauses_children(D->clauses()));
4923
27.6k
  for (Stmt *S : llvm::reverse(Used)) {
4924
27.6k
    assert(S && "Expected non-null used-in-clause child.");
4925
27.6k
    if (CFGBlock *R = Visit(S))
4926
27.6k
      B = R;
4927
27.6k
  }
4928
  // Visit associated structured block if any.
4929
20.9k
  if (!D->isStandaloneDirective()) {
4930
19.3k
    Stmt *S = D->getRawStmt();
4931
19.3k
    if (!isa<CompoundStmt>(S))
4932
14.9k
      addLocalScopeAndDtors(S);
4933
19.3k
    if (CFGBlock *R = addStmt(S))
4934
19.3k
      B = R;
4935
19.3k
  }
4936
4937
20.9k
  return B;
4938
20.9k
}
4939
4940
/// createBlock - Constructs and adds a new CFGBlock to the CFG.  The block has
4941
///  no successors or predecessors.  If this is the first block created in the
4942
///  CFG, it is automatically set to be the Entry and Exit of the CFG.
4943
1.07M
CFGBlock *CFG::createBlock() {
4944
1.07M
  bool first_block = begin() == end();
4945
4946
  // Create the block.
4947
1.07M
  CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
4948
1.07M
  new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this);
4949
1.07M
  Blocks.push_back(Mem, BlkBVC);
4950
4951
  // If this is the first block, set it as the Entry and Exit.
4952
1.07M
  if (first_block)
4953
244k
    Entry = Exit = &back();
4954
4955
  // Return the block.
4956
1.07M
  return &back();
4957
1.07M
}
4958
4959
/// buildCFG - Constructs a CFG from an AST.
4960
std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
4961
244k
                                   ASTContext *C, const BuildOptions &BO) {
4962
244k
  CFGBuilder Builder(C, BO);
4963
244k
  return Builder.buildCFG(D, Statement);
4964
244k
}
4965
4966
67.5k
bool CFG::isLinear() const {
4967
  // Quick path: if we only have the ENTRY block, the EXIT block, and some code
4968
  // in between, then we have no room for control flow.
4969
67.5k
  if (size() <= 3)
4970
48.3k
    return true;
4971
4972
  // Traverse the CFG until we find a branch.
4973
  // TODO: While this should still be very fast,
4974
  // maybe we should cache the answer.
4975
19.1k
  llvm::SmallPtrSet<const CFGBlock *, 4> Visited;
4976
19.1k
  const CFGBlock *B = Entry;
4977
45.1k
  while (B != Exit) {
4978
44.9k
    auto IteratorAndFlag = Visited.insert(B);
4979
44.9k
    if (!IteratorAndFlag.second) {
4980
      // We looped back to a block that we've already visited. Not linear.
4981
40
      return false;
4982
40
    }
4983
4984
    // Iterate over reachable successors.
4985
44.9k
    const CFGBlock *FirstReachableB = nullptr;
4986
64.6k
    for (const CFGBlock::AdjacentBlock &AB : B->succs()) {
4987
64.6k
      if (!AB.isReachable())
4988
756
        continue;
4989
4990
63.8k
      if (FirstReachableB == nullptr) {
4991
44.9k
        FirstReachableB = &*AB;
4992
44.9k
      } else {
4993
        // We've encountered a branch. It's not a linear CFG.
4994
18.9k
        return false;
4995
18.9k
      }
4996
63.8k
    }
4997
4998
26.0k
    if (!FirstReachableB) {
4999
      // We reached a dead end. EXIT is unreachable. This is linear enough.
5000
0
      return true;
5001
0
    }
5002
5003
    // There's only one way to move forward. Proceed.
5004
26.0k
    B = FirstReachableB;
5005
26.0k
  }
5006
5007
  // We reached EXIT and found no branches.
5008
219
  return true;
5009
19.1k
}
5010
5011
const CXXDestructorDecl *
5012
855
CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
5013
855
  switch (getKind()) {
5014
0
    case CFGElement::Initializer:
5015
0
    case CFGElement::NewAllocator:
5016
0
    case CFGElement::LoopExit:
5017
0
    case CFGElement::LifetimeEnds:
5018
0
    case CFGElement::Statement:
5019
0
    case CFGElement::Constructor:
5020
0
    case CFGElement::CXXRecordTypedCall:
5021
0
    case CFGElement::ScopeBegin:
5022
0
    case CFGElement::ScopeEnd:
5023
0
      llvm_unreachable("getDestructorDecl should only be used with "
5024
0
                       "ImplicitDtors");
5025
390
    case CFGElement::AutomaticObjectDtor: {
5026
390
      const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
5027
390
      QualType ty = var->getType();
5028
5029
      // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
5030
      //
5031
      // Lifetime-extending constructs are handled here. This works for a single
5032
      // temporary in an initializer expression.
5033
390
      if (ty->isReferenceType()) {
5034
5
        if (const Expr *Init = var->getInit()) {
5035
5
          ty = getReferenceInitTemporaryType(Init);
5036
5
        }
5037
5
      }
5038
5039
394
      while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
5040
4
        ty = arrayType->getElementType();
5041
4
      }
5042
5043
      // The situation when the type of the lifetime-extending reference
5044
      // does not correspond to the type of the object is supposed
5045
      // to be handled by now. In particular, 'ty' is now the unwrapped
5046
      // record type.
5047
390
      const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5048
390
      assert(classDecl);
5049
0
      return classDecl->getDestructor();
5050
0
    }
5051
0
    case CFGElement::DeleteDtor: {
5052
0
      const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
5053
0
      QualType DTy = DE->getDestroyedType();
5054
0
      DTy = DTy.getNonReferenceType();
5055
0
      const CXXRecordDecl *classDecl =
5056
0
          astContext.getBaseElementType(DTy)->getAsCXXRecordDecl();
5057
0
      return classDecl->getDestructor();
5058
0
    }
5059
465
    case CFGElement::TemporaryDtor: {
5060
465
      const CXXBindTemporaryExpr *bindExpr =
5061
465
        castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
5062
465
      const CXXTemporary *temp = bindExpr->getTemporary();
5063
465
      return temp->getDestructor();
5064
0
    }
5065
0
    case CFGElement::BaseDtor:
5066
0
    case CFGElement::MemberDtor:
5067
      // Not yet supported.
5068
0
      return nullptr;
5069
855
  }
5070
0
  llvm_unreachable("getKind() returned bogus value");
5071
0
}
5072
5073
//===----------------------------------------------------------------------===//
5074
// CFGBlock operations.
5075
//===----------------------------------------------------------------------===//
5076
5077
CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
5078
    : ReachableBlock(IsReachable ? B : nullptr),
5079
      UnreachableBlock(!IsReachable ? B : nullptr,
5080
1.97M
                       B && IsReachable ? AB_Normal : AB_Unreachable) {}
5081
5082
CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
5083
    : ReachableBlock(B),
5084
      UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
5085
1.31k
                       B == AlternateBlock ? AB_Alternate : AB_Normal) {}
5086
5087
void CFGBlock::addSuccessor(AdjacentBlock Succ,
5088
989k
                            BumpVectorContext &C) {
5089
989k
  if (CFGBlock *B = Succ.getReachableBlock())
5090
985k
    B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C);
5091
5092
989k
  if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
5093
4.25k
    UnreachableB->Preds.push_back(AdjacentBlock(this, false), C);
5094
5095
989k
  Succs.push_back(Succ, C);
5096
989k
}
5097
5098
bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
5099
162k
        const CFGBlock *From, const CFGBlock *To) {
5100
162k
  if (F.IgnoreNullPredecessors && !From)
5101
45
    return true;
5102
5103
162k
  if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
5104
    // If the 'To' has no label or is labeled but the label isn't a
5105
    // CaseStmt then filter this edge.
5106
162k
    if (const SwitchStmt *S =
5107
162k
        dyn_cast_or_null<SwitchStmt>(From->getTerminatorStmt())) {
5108
6
      if (S->isAllEnumCasesCovered()) {
5109
0
        const Stmt *L = To->getLabel();
5110
0
        if (!L || !isa<CaseStmt>(L))
5111
0
          return true;
5112
0
      }
5113
6
    }
5114
162k
  }
5115
5116
162k
  return false;
5117
162k
}
5118
5119
//===----------------------------------------------------------------------===//
5120
// CFG pretty printing
5121
//===----------------------------------------------------------------------===//
5122
5123
namespace {
5124
5125
class StmtPrinterHelper : public PrinterHelper  {
5126
  using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;
5127
  using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;
5128
5129
  StmtMapTy StmtMap;
5130
  DeclMapTy DeclMap;
5131
  signed currentBlock = 0;
5132
  unsigned currStmt = 0;
5133
  const LangOptions &LangOpts;
5134
5135
public:
5136
  StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
5137
764
      : LangOpts(LO) {
5138
764
    if (!cfg)
5139
0
      return;
5140
4.18k
    
for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); 764
I != E;
++I3.42k
) {
5141
3.42k
      unsigned j = 1;
5142
3.42k
      for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
5143
13.0k
           BI != BEnd; 
++BI, ++j9.58k
) {
5144
9.58k
        if (Optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
5145
8.21k
          const Stmt *stmt= SE->getStmt();
5146
8.21k
          std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
5147
8.21k
          StmtMap[stmt] = P;
5148
5149
8.21k
          switch (stmt->getStmtClass()) {
5150
990
            case Stmt::DeclStmtClass:
5151
990
              DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
5152
990
              break;
5153
0
            case Stmt::IfStmtClass: {
5154
0
              const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
5155
0
              if (var)
5156
0
                DeclMap[var] = P;
5157
0
              break;
5158
0
            }
5159
0
            case Stmt::ForStmtClass: {
5160
0
              const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
5161
0
              if (var)
5162
0
                DeclMap[var] = P;
5163
0
              break;
5164
0
            }
5165
0
            case Stmt::WhileStmtClass: {
5166
0
              const VarDecl *var =
5167
0
                cast<WhileStmt>(stmt)->getConditionVariable();
5168
0
              if (var)
5169
0
                DeclMap[var] = P;
5170
0
              break;
5171
0
            }
5172
0
            case Stmt::SwitchStmtClass: {
5173
0
              const VarDecl *var =
5174
0
                cast<SwitchStmt>(stmt)->getConditionVariable();
5175
0
              if (var)
5176
0
                DeclMap[var] = P;
5177
0
              break;
5178
0
            }
5179
8
            case Stmt::CXXCatchStmtClass: {
5180
8
              const VarDecl *var =
5181
8
                cast<CXXCatchStmt>(stmt)->getExceptionDecl();
5182
8
              if (var)
5183
8
                DeclMap[var] = P;
5184
8
              break;
5185
0
            }
5186
7.21k
            default:
5187
7.21k
              break;
5188
8.21k
          }
5189
8.21k
        }
5190
9.58k
      }
5191
3.42k
    }
5192
764
  }
5193
5194
764
  ~StmtPrinterHelper() override = default;
5195
5196
9.97k
  const LangOptions &getLangOpts() const { return LangOpts; }
5197
3.97k
  void setBlockID(signed i) { currentBlock = i; }
5198
9.58k
  void setStmtID(unsigned i) { currStmt = i; }
5199
5200
16.0k
  bool handledStmt(Stmt *S, raw_ostream &OS) override {
5201
16.0k
    StmtMapTy::iterator I = StmtMap.find(S);
5202
5203
16.0k
    if (I == StmtMap.end())
5204
810
      return false;
5205
5206
15.2k
    if (currentBlock >= 0 && 
I->second.first == (unsigned) currentBlock14.7k
5207
15.2k
                          && 
I->second.second == currStmt14.4k
) {
5208
8.18k
      return false;
5209
8.18k
    }
5210
5211
7.03k
    OS << "[B" << I->second.first << "." << I->second.second << "]";
5212
7.03k
    return true;
5213
15.2k
  }
5214
5215
684
  bool handleDecl(const Decl *D, raw_ostream &OS) {
5216
684
    DeclMapTy::iterator I = DeclMap.find(D);
5217
5218
684
    if (I == DeclMap.end())
5219
0
      return false;
5220
5221
684
    if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5222
684
                          && 
I->second.second == currStmt276
) {
5223
0
      return false;
5224
0
    }
5225
5226
684
    OS << "[B" << I->second.first << "." << I->second.second << "]";
5227
684
    return true;
5228
684
  }
5229
};
5230
5231
class CFGBlockTerminatorPrint
5232
    : public StmtVisitor<CFGBlockTerminatorPrint,void> {
5233
  raw_ostream &OS;
5234
  StmtPrinterHelper* Helper;
5235
  PrintingPolicy Policy;
5236
5237
public:
5238
  CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
5239
                          const PrintingPolicy &Policy)
5240
551
      : OS(os), Helper(helper), Policy(Policy) {
5241
551
    this->Policy.IncludeNewlines = false;
5242
551
  }
5243
5244
169
  void VisitIfStmt(IfStmt *I) {
5245
169
    OS << "if ";
5246
169
    if (Stmt *C = I->getCond())
5247
169
      C->printPretty(OS, Helper, Policy);
5248
169
  }
5249
5250
  // Default case.
5251
114
  void VisitStmt(Stmt *Terminator) {
5252
114
    Terminator->printPretty(OS, Helper, Policy);
5253
114
  }
5254
5255
1
  void VisitDeclStmt(DeclStmt *DS) {
5256
1
    VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
5257
1
    OS << "static init " << VD->getName();
5258
1
  }
5259
5260
44
  void VisitForStmt(ForStmt *F) {
5261
44
    OS << "for (" ;
5262
44
    if (F->getInit())
5263
43
      OS << "...";
5264
44
    OS << "; ";
5265
44
    if (Stmt *C = F->getCond())
5266
43
      C->printPretty(OS, Helper, Policy);
5267
44
    OS << "; ";
5268
44
    if (F->getInc())
5269
27
      OS << "...";
5270
44
    OS << ")";
5271
44
  }
5272
5273
23
  void VisitWhileStmt(WhileStmt *W) {
5274
23
    OS << "while " ;
5275
23
    if (Stmt *C = W->getCond())
5276
23
      C->printPretty(OS, Helper, Policy);
5277
23
  }