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