Coverage Report

Created: 2019-07-24 05:18

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