Coverage Report

Created: 2021-01-26 06:56

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