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