Coverage Report

Created: 2022-07-16 07:03

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