Coverage Report

Created: 2020-09-19 12:23

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