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