Coverage Report

Created: 2022-01-18 06:27

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