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