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