Coverage Report

Created: 2020-02-15 09:57

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