CFG.h source code [clang_source_code/include/clang/Analysis/CFG.h]

1	//===- CFG.h - Classes for representing and building CFGs -------- C++ --===//
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	#ifndef LLVM_CLANG_ANALYSIS_CFG_H
15	#define LLVM_CLANG_ANALYSIS_CFG_H
16
17	#include "clang/Analysis/Support/BumpVector.h"
18	#include "clang/Analysis/ConstructionContext.h"
19	#include "clang/AST/ExprCXX.h"
20	#include "clang/AST/ExprObjC.h"
21	#include "clang/Basic/LLVM.h"
22	#include "llvm/ADT/DenseMap.h"
23	#include "llvm/ADT/GraphTraits.h"
24	#include "llvm/ADT/None.h"
25	#include "llvm/ADT/Optional.h"
26	#include "llvm/ADT/PointerIntPair.h"
27	#include "llvm/ADT/iterator_range.h"
28	#include "llvm/Support/Allocator.h"
29	#include "llvm/Support/raw_ostream.h"
30	#include <bitset>
31	#include <cassert>
32	#include <cstddef>
33	#include <iterator>
34	#include <memory>
35	#include <vector>
36
37	namespace clang {
38
39	class ASTContext;
40	class BinaryOperator;
41	class CFG;
42	class CXXBaseSpecifier;
43	class CXXBindTemporaryExpr;
44	class CXXCtorInitializer;
45	class CXXDeleteExpr;
46	class CXXDestructorDecl;
47	class CXXNewExpr;
48	class CXXRecordDecl;
49	class Decl;
50	class FieldDecl;
51	class LangOptions;
52	class VarDecl;
53
54	/// Represents a top-level expression in a basic block.
55	class CFGElement {
56	public:
57	enum Kind {
58	// main kind
59	Initializer,
60	ScopeBegin,
61	ScopeEnd,
62	NewAllocator,
63	LifetimeEnds,
64	LoopExit,
65	// stmt kind
66	Statement,
67	Constructor,
68	CXXRecordTypedCall,
69	STMT_BEGIN = Statement,
70	STMT_END = CXXRecordTypedCall,
71	// dtor kind
72	AutomaticObjectDtor,
73	DeleteDtor,
74	BaseDtor,
75	MemberDtor,
76	TemporaryDtor,
77	DTOR_BEGIN = AutomaticObjectDtor,
78	DTOR_END = TemporaryDtor
79	};
80
81	protected:
82	// The int bits are used to mark the kind.
83	llvm::PointerIntPair<void *, 2> Data1;
84	llvm::PointerIntPair<void *, 2> Data2;
85
86	CFGElement(Kind kind, const void Ptr1, const void Ptr2 = nullptr)
87	: Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
88	Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
89	assert(getKind() == kind);
90	}
91
92	CFGElement() = default;
93
94	public:
95	/// Convert to the specified CFGElement type, asserting that this
96	/// CFGElement is of the desired type.
97	template<typename T>
98	T castAs() const {
99	assert(T::isKind(*this));
100	T t;
101	CFGElement& e = t;
102	e = *this;
103	return t;
104	}
105
106	/// Convert to the specified CFGElement type, returning None if this
107	/// CFGElement is not of the desired type.
108	template<typename T>
109	Optional<T> getAs() const {
110	if (!T::isKind(*this))
111	return None;
112	T t;
113	CFGElement& e = t;
114	e = *this;
115	return t;
116	}
117
118	Kind getKind() const {
119	unsigned x = Data2.getInt();
120	x <<= 2;
121	x \|= Data1.getInt();
122	return (Kind) x;
123	}
124	};
125
126	class CFGStmt : public CFGElement {
127	public:
128	explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) {
129	assert(isKind(*this));
130	}
131
132	const Stmt *getStmt() const {
133	return static_cast<const Stmt *>(Data1.getPointer());
134	}
135
136	private:
137	friend class CFGElement;
138
139	static bool isKind(const CFGElement &E) {
140	return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END;
141	}
142
143	protected:
144	CFGStmt() = default;
145	};
146
147	/// Represents C++ constructor call. Maintains information necessary to figure
148	/// out what memory is being initialized by the constructor expression. For now
149	/// this is only used by the analyzer's CFG.
150	class CFGConstructor : public CFGStmt {
151	public:
152	explicit CFGConstructor(CXXConstructExpr CE, const ConstructionContext C)
153	: CFGStmt(CE, Constructor) {
154	assert(C);
155	Data2.setPointer(const_cast<ConstructionContext *>(C));
156	}
157
158	const ConstructionContext *getConstructionContext() const {
159	return static_cast<ConstructionContext *>(Data2.getPointer());
160	}
161
162	private:
163	friend class CFGElement;
164
165	CFGConstructor() = default;
166
167	static bool isKind(const CFGElement &E) {
168	return E.getKind() == Constructor;
169	}
170	};
171
172	/// Represents a function call that returns a C++ object by value. This, like
173	/// constructor, requires a construction context in order to understand the
174	/// storage of the returned object . In C such tracking is not necessary because
175	/// no additional effort is required for destroying the object or modeling copy
176	/// elision. Like CFGConstructor, this element is for now only used by the
177	/// analyzer's CFG.
178	class CFGCXXRecordTypedCall : public CFGStmt {
179	public:
180	/// Returns true when call expression \p CE needs to be represented
181	/// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt.
182	static bool isCXXRecordTypedCall(Expr *E) {
183	(E) \|\| isa(E)", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 183, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(isa<CallExpr>(E) \|\| isa<ObjCMessageExpr>(E));
184	// There is no such thing as reference-type expression. If the function
185	// returns a reference, it'll return the respective lvalue or xvalue
186	// instead, and we're only interested in objects.
187	return !E->isGLValue() &&
188	E->getType().getCanonicalType()->getAsCXXRecordDecl();
189	}
190
191	explicit CFGCXXRecordTypedCall(Expr E, const ConstructionContext C)
192	: CFGStmt(E, CXXRecordTypedCall) {
193	assert(isCXXRecordTypedCall(E));
194	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(C && (isa<TemporaryObjectConstructionContext>(C) \|\|
195	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> // These are possible in C++17 due to mandatory copy elision.
196	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> isa<ReturnedValueConstructionContext>(C) \|\|
197	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> isa<VariableConstructionContext>(C) \|\|
198	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> isa<ConstructorInitializerConstructionContext>(C) \|\|
199	(C) \|\| isa(C) \|\| isa(C) \|\| isa(C) \|\| isa(C))", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 199, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> isa<ArgumentConstructionContext>(C)));
200	Data2.setPointer(const_cast<ConstructionContext *>(C));
201	}
202
203	const ConstructionContext *getConstructionContext() const {
204	return static_cast<ConstructionContext *>(Data2.getPointer());
205	}
206
207	private:
208	friend class CFGElement;
209
210	CFGCXXRecordTypedCall() = default;
211
212	static bool isKind(const CFGElement &E) {
213	return E.getKind() == CXXRecordTypedCall;
214	}
215	};
216
217	/// Represents C++ base or member initializer from constructor's initialization
218	/// list.
219	class CFGInitializer : public CFGElement {
220	public:
221	explicit CFGInitializer(CXXCtorInitializer *initializer)
222	: CFGElement(Initializer, initializer) {}
223
224	CXXCtorInitializer* getInitializer() const {
225	return static_cast<CXXCtorInitializer*>(Data1.getPointer());
226	}
227
228	private:
229	friend class CFGElement;
230
231	CFGInitializer() = default;
232
233	static bool isKind(const CFGElement &E) {
234	return E.getKind() == Initializer;
235	}
236	};
237
238	/// Represents C++ allocator call.
239	class CFGNewAllocator : public CFGElement {
240	public:
241	explicit CFGNewAllocator(const CXXNewExpr *S)
242	: CFGElement(NewAllocator, S) {}
243
244	// Get the new expression.
245	const CXXNewExpr *getAllocatorExpr() const {
246	return static_cast<CXXNewExpr *>(Data1.getPointer());
247	}
248
249	private:
250	friend class CFGElement;
251
252	CFGNewAllocator() = default;
253
254	static bool isKind(const CFGElement &elem) {
255	return elem.getKind() == NewAllocator;
256	}
257	};
258
259	/// Represents the point where a loop ends.
260	/// This element is is only produced when building the CFG for the static
261	/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
262	///
263	/// Note: a loop exit element can be reached even when the loop body was never
264	/// entered.
265	class CFGLoopExit : public CFGElement {
266	public:
267	explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
268
269	const Stmt *getLoopStmt() const {
270	return static_cast<Stmt *>(Data1.getPointer());
271	}
272
273	private:
274	friend class CFGElement;
275
276	CFGLoopExit() = default;
277
278	static bool isKind(const CFGElement &elem) {
279	return elem.getKind() == LoopExit;
280	}
281	};
282
283	/// Represents the point where the lifetime of an automatic object ends
284	class CFGLifetimeEnds : public CFGElement {
285	public:
286	explicit CFGLifetimeEnds(const VarDecl var, const Stmt stmt)
287	: CFGElement(LifetimeEnds, var, stmt) {}
288
289	const VarDecl *getVarDecl() const {
290	return static_cast<VarDecl *>(Data1.getPointer());
291	}
292
293	const Stmt *getTriggerStmt() const {
294	return static_cast<Stmt *>(Data2.getPointer());
295	}
296
297	private:
298	friend class CFGElement;
299
300	CFGLifetimeEnds() = default;
301
302	static bool isKind(const CFGElement &elem) {
303	return elem.getKind() == LifetimeEnds;
304	}
305	};
306
307	/// Represents beginning of a scope implicitly generated
308	/// by the compiler on encountering a CompoundStmt
309	class CFGScopeBegin : public CFGElement {
310	public:
311	CFGScopeBegin() {}
312	CFGScopeBegin(const VarDecl VD, const Stmt S)
313	: CFGElement(ScopeBegin, VD, S) {}
314
315	// Get statement that triggered a new scope.
316	const Stmt *getTriggerStmt() const {
317	return static_cast<Stmt*>(Data2.getPointer());
318	}
319
320	// Get VD that triggered a new scope.
321	const VarDecl *getVarDecl() const {
322	return static_cast<VarDecl *>(Data1.getPointer());
323	}
324
325	private:
326	friend class CFGElement;
327	static bool isKind(const CFGElement &E) {
328	Kind kind = E.getKind();
329	return kind == ScopeBegin;
330	}
331	};
332
333	/// Represents end of a scope implicitly generated by
334	/// the compiler after the last Stmt in a CompoundStmt's body
335	class CFGScopeEnd : public CFGElement {
336	public:
337	CFGScopeEnd() {}
338	CFGScopeEnd(const VarDecl VD, const Stmt S) : CFGElement(ScopeEnd, VD, S) {}
339
340	const VarDecl *getVarDecl() const {
341	return static_cast<VarDecl *>(Data1.getPointer());
342	}
343
344	const Stmt *getTriggerStmt() const {
345	return static_cast<Stmt *>(Data2.getPointer());
346	}
347
348	private:
349	friend class CFGElement;
350	static bool isKind(const CFGElement &E) {
351	Kind kind = E.getKind();
352	return kind == ScopeEnd;
353	}
354	};
355
356	/// Represents C++ object destructor implicitly generated by compiler on various
357	/// occasions.
358	class CFGImplicitDtor : public CFGElement {
359	protected:
360	CFGImplicitDtor() = default;
361
362	CFGImplicitDtor(Kind kind, const void data1, const void data2 = nullptr)
363	: CFGElement(kind, data1, data2) {
364	= DTOR_BEGIN && kind <= DTOR_END", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 364, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
365	}
366
367	public:
368	const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
369	bool isNoReturn(ASTContext &astContext) const;
370
371	private:
372	friend class CFGElement;
373
374	static bool isKind(const CFGElement &E) {
375	Kind kind = E.getKind();
376	return kind >= DTOR_BEGIN && kind <= DTOR_END;
377	}
378	};
379
380	/// Represents C++ object destructor implicitly generated for automatic object
381	/// or temporary bound to const reference at the point of leaving its local
382	/// scope.
383	class CFGAutomaticObjDtor: public CFGImplicitDtor {
384	public:
385	CFGAutomaticObjDtor(const VarDecl var, const Stmt stmt)
386	: CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
387
388	const VarDecl *getVarDecl() const {
389	return static_cast<VarDecl*>(Data1.getPointer());
390	}
391
392	// Get statement end of which triggered the destructor call.
393	const Stmt *getTriggerStmt() const {
394	return static_cast<Stmt*>(Data2.getPointer());
395	}
396
397	private:
398	friend class CFGElement;
399
400	CFGAutomaticObjDtor() = default;
401
402	static bool isKind(const CFGElement &elem) {
403	return elem.getKind() == AutomaticObjectDtor;
404	}
405	};
406
407	/// Represents C++ object destructor generated from a call to delete.
408	class CFGDeleteDtor : public CFGImplicitDtor {
409	public:
410	CFGDeleteDtor(const CXXRecordDecl RD, const CXXDeleteExpr DE)
411	: CFGImplicitDtor(DeleteDtor, RD, DE) {}
412
413	const CXXRecordDecl *getCXXRecordDecl() const {
414	return static_cast<CXXRecordDecl*>(Data1.getPointer());
415	}
416
417	// Get Delete expression which triggered the destructor call.
418	const CXXDeleteExpr *getDeleteExpr() const {
419	return static_cast<CXXDeleteExpr *>(Data2.getPointer());
420	}
421
422	private:
423	friend class CFGElement;
424
425	CFGDeleteDtor() = default;
426
427	static bool isKind(const CFGElement &elem) {
428	return elem.getKind() == DeleteDtor;
429	}
430	};
431
432	/// Represents C++ object destructor implicitly generated for base object in
433	/// destructor.
434	class CFGBaseDtor : public CFGImplicitDtor {
435	public:
436	CFGBaseDtor(const CXXBaseSpecifier *base)
437	: CFGImplicitDtor(BaseDtor, base) {}
438
439	const CXXBaseSpecifier *getBaseSpecifier() const {
440	return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
441	}
442
443	private:
444	friend class CFGElement;
445
446	CFGBaseDtor() = default;
447
448	static bool isKind(const CFGElement &E) {
449	return E.getKind() == BaseDtor;
450	}
451	};
452
453	/// Represents C++ object destructor implicitly generated for member object in
454	/// destructor.
455	class CFGMemberDtor : public CFGImplicitDtor {
456	public:
457	CFGMemberDtor(const FieldDecl *field)
458	: CFGImplicitDtor(MemberDtor, field, nullptr) {}
459
460	const FieldDecl *getFieldDecl() const {
461	return static_cast<const FieldDecl*>(Data1.getPointer());
462	}
463
464	private:
465	friend class CFGElement;
466
467	CFGMemberDtor() = default;
468
469	static bool isKind(const CFGElement &E) {
470	return E.getKind() == MemberDtor;
471	}
472	};
473
474	/// Represents C++ object destructor implicitly generated at the end of full
475	/// expression for temporary object.
476	class CFGTemporaryDtor : public CFGImplicitDtor {
477	public:
478	CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
479	: CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}
480
481	const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
482	return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
483	}
484
485	private:
486	friend class CFGElement;
487
488	CFGTemporaryDtor() = default;
489
490	static bool isKind(const CFGElement &E) {
491	return E.getKind() == TemporaryDtor;
492	}
493	};
494
495	/// Represents CFGBlock terminator statement.
496	///
497	/// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
498	/// in control flow of destructors of temporaries. In this case terminator
499	/// statement is the same statement that branches control flow in evaluation
500	/// of matching full expression.
501	class CFGTerminator {
502	llvm::PointerIntPair<Stmt *, 1> Data;
503
504	public:
505	CFGTerminator() = default;
506	CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
507	: Data(S, TemporaryDtorsBranch) {}
508
509	Stmt *getStmt() { return Data.getPointer(); }
510	const Stmt *getStmt() const { return Data.getPointer(); }
511
512	bool isTemporaryDtorsBranch() const { return Data.getInt(); }
513
514	operator Stmt *() { return getStmt(); }
515	operator const Stmt *() const { return getStmt(); }
516
517	Stmt *operator->() { return getStmt(); }
518	const Stmt *operator->() const { return getStmt(); }
519
520	Stmt &operator() { return getStmt(); }
521	const Stmt &operator() const { return getStmt(); }
522
523	explicit operator bool() const { return getStmt(); }
524	};
525
526	/// Represents a single basic block in a source-level CFG.
527	/// It consists of:
528	///
529	/// (1) A set of statements/expressions (which may contain subexpressions).
530	/// (2) A "terminator" statement (not in the set of statements).
531	/// (3) A list of successors and predecessors.
532	///
533	/// Terminator: The terminator represents the type of control-flow that occurs
534	/// at the end of the basic block. The terminator is a Stmt* referring to an
535	/// AST node that has control-flow: if-statements, breaks, loops, etc.
536	/// If the control-flow is conditional, the condition expression will appear
537	/// within the set of statements in the block (usually the last statement).
538	///
539	/// Predecessors: the order in the set of predecessors is arbitrary.
540	///
541	/// Successors: the order in the set of successors is NOT arbitrary. We
542	/// currently have the following orderings based on the terminator:
543	///
544	/// Terminator Successor Ordering
545	/// -----------------------------------------------------
546	/// if Then Block; Else Block
547	/// ? operator LHS expression; RHS expression
548	/// &&, \|\| expression that uses result of && or \|\|, RHS
549	///
550	/// But note that any of that may be NULL in case of optimized-out edges.
551	class CFGBlock {
552	class ElementList {
553	using ImplTy = BumpVector<CFGElement>;
554
555	ImplTy Impl;
556
557	public:
558	ElementList(BumpVectorContext &C) : Impl(C, 4) {}
559
560	using iterator = std::reverse_iterator<ImplTy::iterator>;
561	using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
562	using reverse_iterator = ImplTy::iterator;
563	using const_reverse_iterator = ImplTy::const_iterator;
564	using const_reference = ImplTy::const_reference;
565
566	void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
567
568	reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
569	BumpVectorContext &C) {
570	return Impl.insert(I, Cnt, E, C);
571	}
572
573	const_reference front() const { return Impl.back(); }
574	const_reference back() const { return Impl.front(); }
575
576	iterator begin() { return Impl.rbegin(); }
577	iterator end() { return Impl.rend(); }
578	const_iterator begin() const { return Impl.rbegin(); }
579	const_iterator end() const { return Impl.rend(); }
580	reverse_iterator rbegin() { return Impl.begin(); }
581	reverse_iterator rend() { return Impl.end(); }
582	const_reverse_iterator rbegin() const { return Impl.begin(); }
583	const_reverse_iterator rend() const { return Impl.end(); }
584
585	CFGElement operator[](size_t i) const {
586	assert(i < Impl.size());
587	return Impl[Impl.size() - 1 - i];
588	}
589
590	size_t size() const { return Impl.size(); }
591	bool empty() const { return Impl.empty(); }
592	};
593
594	/// The set of statements in the basic block.
595	ElementList Elements;
596
597	/// An (optional) label that prefixes the executable statements in the block.
598	/// When this variable is non-NULL, it is either an instance of LabelStmt,
599	/// SwitchCase or CXXCatchStmt.
600	Stmt *Label = nullptr;
601
602	/// The terminator for a basic block that indicates the type of control-flow
603	/// that occurs between a block and its successors.
604	CFGTerminator Terminator;
605
606	/// Some blocks are used to represent the "loop edge" to the start of a loop
607	/// from within the loop body. This Stmt* will be refer to the loop statement
608	/// for such blocks (and be null otherwise).
609	const Stmt *LoopTarget = nullptr;
610
611	/// A numerical ID assigned to a CFGBlock during construction of the CFG.
612	unsigned BlockID;
613
614	public:
615	/// This class represents a potential adjacent block in the CFG. It encodes
616	/// whether or not the block is actually reachable, or can be proved to be
617	/// trivially unreachable. For some cases it allows one to encode scenarios
618	/// where a block was substituted because the original (now alternate) block
619	/// is unreachable.
620	class AdjacentBlock {
621	enum Kind {
622	AB_Normal,
623	AB_Unreachable,
624	AB_Alternate
625	};
626
627	CFGBlock *ReachableBlock;
628	llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
629
630	public:
631	/// Construct an AdjacentBlock with a possibly unreachable block.
632	AdjacentBlock(CFGBlock *B, bool IsReachable);
633
634	/// Construct an AdjacentBlock with a reachable block and an alternate
635	/// unreachable block.
636	AdjacentBlock(CFGBlock B, CFGBlock AlternateBlock);
637
638	/// Get the reachable block, if one exists.
639	CFGBlock *getReachableBlock() const {
640	return ReachableBlock;
641	}
642
643	/// Get the potentially unreachable block.
644	CFGBlock *getPossiblyUnreachableBlock() const {
645	return UnreachableBlock.getPointer();
646	}
647
648	/// Provide an implicit conversion to CFGBlock* so that
649	/// AdjacentBlock can be substituted for CFGBlock*.
650	operator CFGBlock*() const {
651	return getReachableBlock();
652	}
653
654	CFGBlock& operator *() const {
655	return *getReachableBlock();
656	}
657
658	CFGBlock* operator ->() const {
659	return getReachableBlock();
660	}
661
662	bool isReachable() const {
663	Kind K = (Kind) UnreachableBlock.getInt();
664	return K == AB_Normal \|\| K == AB_Alternate;
665	}
666	};
667
668	private:
669	/// Keep track of the predecessor / successor CFG blocks.
670	using AdjacentBlocks = BumpVector<AdjacentBlock>;
671	AdjacentBlocks Preds;
672	AdjacentBlocks Succs;
673
674	/// This bit is set when the basic block contains a function call
675	/// or implicit destructor that is attributed as 'noreturn'. In that case,
676	/// control cannot technically ever proceed past this block. All such blocks
677	/// will have a single immediate successor: the exit block. This allows them
678	/// to be easily reached from the exit block and using this bit quickly
679	/// recognized without scanning the contents of the block.
680	///
681	/// Optimization Note: This bit could be profitably folded with Terminator's
682	/// storage if the memory usage of CFGBlock becomes an issue.
683	unsigned HasNoReturnElement : 1;
684
685	/// The parent CFG that owns this CFGBlock.
686	CFG *Parent;
687
688	public:
689	explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
690	: Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
691	Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
692
693	// Statement iterators
694	using iterator = ElementList::iterator;
695	using const_iterator = ElementList::const_iterator;
696	using reverse_iterator = ElementList::reverse_iterator;
697	using const_reverse_iterator = ElementList::const_reverse_iterator;
698
699	CFGElement front() const { return Elements.front(); }
700	CFGElement back() const { return Elements.back(); }
701
702	iterator begin() { return Elements.begin(); }
703	iterator end() { return Elements.end(); }
704	const_iterator begin() const { return Elements.begin(); }
705	const_iterator end() const { return Elements.end(); }
706
707	reverse_iterator rbegin() { return Elements.rbegin(); }
708	reverse_iterator rend() { return Elements.rend(); }
709	const_reverse_iterator rbegin() const { return Elements.rbegin(); }
710	const_reverse_iterator rend() const { return Elements.rend(); }
711
712	unsigned size() const { return Elements.size(); }
713	bool empty() const { return Elements.empty(); }
714
715	CFGElement operator[](size_t i) const { return Elements[i]; }
716
717	// CFG iterators
718	using pred_iterator = AdjacentBlocks::iterator;
719	using const_pred_iterator = AdjacentBlocks::const_iterator;
720	using pred_reverse_iterator = AdjacentBlocks::reverse_iterator;
721	using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
722	using pred_range = llvm::iterator_range<pred_iterator>;
723	using pred_const_range = llvm::iterator_range<const_pred_iterator>;
724
725	using succ_iterator = AdjacentBlocks::iterator;
726	using const_succ_iterator = AdjacentBlocks::const_iterator;
727	using succ_reverse_iterator = AdjacentBlocks::reverse_iterator;
728	using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
729	using succ_range = llvm::iterator_range<succ_iterator>;
730	using succ_const_range = llvm::iterator_range<const_succ_iterator>;
731
732	pred_iterator pred_begin() { return Preds.begin(); }
733	pred_iterator pred_end() { return Preds.end(); }
734	const_pred_iterator pred_begin() const { return Preds.begin(); }
735	const_pred_iterator pred_end() const { return Preds.end(); }
736
737	pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); }
738	pred_reverse_iterator pred_rend() { return Preds.rend(); }
739	const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
740	const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
741
742	pred_range preds() {
743	return pred_range(pred_begin(), pred_end());
744	}
745
746	pred_const_range preds() const {
747	return pred_const_range(pred_begin(), pred_end());
748	}
749
750	succ_iterator succ_begin() { return Succs.begin(); }
751	succ_iterator succ_end() { return Succs.end(); }
752	const_succ_iterator succ_begin() const { return Succs.begin(); }
753	const_succ_iterator succ_end() const { return Succs.end(); }
754
755	succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); }
756	succ_reverse_iterator succ_rend() { return Succs.rend(); }
757	const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
758	const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
759
760	succ_range succs() {
761	return succ_range(succ_begin(), succ_end());
762	}
763
764	succ_const_range succs() const {
765	return succ_const_range(succ_begin(), succ_end());
766	}
767
768	unsigned succ_size() const { return Succs.size(); }
769	bool succ_empty() const { return Succs.empty(); }
770
771	unsigned pred_size() const { return Preds.size(); }
772	bool pred_empty() const { return Preds.empty(); }
773
774
775	class FilterOptions {
776	public:
777	unsigned IgnoreNullPredecessors : 1;
778	unsigned IgnoreDefaultsWithCoveredEnums : 1;
779
780	FilterOptions()
781	: IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
782	};
783
784	static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
785	const CFGBlock *Dst);
786
787	template <typename IMPL, bool IsPred>
788	class FilteredCFGBlockIterator {
789	private:
790	IMPL I, E;
791	const FilterOptions F;
792	const CFGBlock *From;
793
794	public:
795	explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
796	const CFGBlock *from,
797	const FilterOptions &f)
798	: I(i), E(e), F(f), From(from) {
799	while (hasMore() && Filter(*I))
800	++I;
801	}
802
803	bool hasMore() const { return I != E; }
804
805	FilteredCFGBlockIterator &operator++() {
806	do { ++I; } while (hasMore() && Filter(*I));
807	return *this;
808	}
809
810	const CFGBlock operator() const { return *I; }
811
812	private:
813	bool Filter(const CFGBlock *To) {
814	return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
815	}
816	};
817
818	using filtered_pred_iterator =
819	FilteredCFGBlockIterator<const_pred_iterator, true>;
820
821	using filtered_succ_iterator =
822	FilteredCFGBlockIterator<const_succ_iterator, false>;
823
824	filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
825	return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
826	}
827
828	filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
829	return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
830	}
831
832	// Manipulation of block contents
833
834	void setTerminator(CFGTerminator Term) { Terminator = Term; }
835	void setLabel(Stmt *Statement) { Label = Statement; }
836	void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
837	void setHasNoReturnElement() { HasNoReturnElement = true; }
838
839	CFGTerminator getTerminator() { return Terminator; }
840	const CFGTerminator getTerminator() const { return Terminator; }
841
842	Stmt *getTerminatorCondition(bool StripParens = true);
843
844	const Stmt *getTerminatorCondition(bool StripParens = true) const {
845	return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
846	}
847
848	const Stmt *getLoopTarget() const { return LoopTarget; }
849
850	Stmt *getLabel() { return Label; }
851	const Stmt *getLabel() const { return Label; }
852
853	bool hasNoReturnElement() const { return HasNoReturnElement; }
854
855	unsigned getBlockID() const { return BlockID; }
856
857	CFG *getParent() const { return Parent; }
858
859	void dump() const;
860
861	void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
862	void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
863	bool ShowColors) const;
864	void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
865	void printAsOperand(raw_ostream &OS, bool /PrintType/) {
866	OS << "BB#" << getBlockID();
867	}
868
869	/// Adds a (potentially unreachable) successor block to the current block.
870	void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
871
872	void appendStmt(Stmt *statement, BumpVectorContext &C) {
873	Elements.push_back(CFGStmt(statement), C);
874	}
875
876	void appendConstructor(CXXConstructExpr CE, const ConstructionContext CC,
877	BumpVectorContext &C) {
878	Elements.push_back(CFGConstructor(CE, CC), C);
879	}
880
881	void appendCXXRecordTypedCall(Expr *E,
882	const ConstructionContext *CC,
883	BumpVectorContext &C) {
884	Elements.push_back(CFGCXXRecordTypedCall(E, CC), C);
885	}
886
887	void appendInitializer(CXXCtorInitializer *initializer,
888	BumpVectorContext &C) {
889	Elements.push_back(CFGInitializer(initializer), C);
890	}
891
892	void appendNewAllocator(CXXNewExpr *NE,
893	BumpVectorContext &C) {
894	Elements.push_back(CFGNewAllocator(NE), C);
895	}
896
897	void appendScopeBegin(const VarDecl VD, const Stmt S,
898	BumpVectorContext &C) {
899	Elements.push_back(CFGScopeBegin(VD, S), C);
900	}
901
902	void prependScopeBegin(const VarDecl VD, const Stmt S,
903	BumpVectorContext &C) {
904	Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
905	}
906
907	void appendScopeEnd(const VarDecl VD, const Stmt S, BumpVectorContext &C) {
908	Elements.push_back(CFGScopeEnd(VD, S), C);
909	}
910
911	void prependScopeEnd(const VarDecl VD, const Stmt S, BumpVectorContext &C) {
912	Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
913	}
914
915	void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
916	Elements.push_back(CFGBaseDtor(BS), C);
917	}
918
919	void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
920	Elements.push_back(CFGMemberDtor(FD), C);
921	}
922
923	void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
924	Elements.push_back(CFGTemporaryDtor(E), C);
925	}
926
927	void appendAutomaticObjDtor(VarDecl VD, Stmt S, BumpVectorContext &C) {
928	Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
929	}
930
931	void appendLifetimeEnds(VarDecl VD, Stmt S, BumpVectorContext &C) {
932	Elements.push_back(CFGLifetimeEnds(VD, S), C);
933	}
934
935	void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
936	Elements.push_back(CFGLoopExit(LoopStmt), C);
937	}
938
939	void appendDeleteDtor(CXXRecordDecl RD, CXXDeleteExpr DE, BumpVectorContext &C) {
940	Elements.push_back(CFGDeleteDtor(RD, DE), C);
941	}
942
943	// Destructors must be inserted in reversed order. So insertion is in two
944	// steps. First we prepare space for some number of elements, then we insert
945	// the elements beginning at the last position in prepared space.
946	iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
947	BumpVectorContext &C) {
948	return iterator(Elements.insert(I.base(), Cnt,
949	CFGAutomaticObjDtor(nullptr, nullptr), C));
950	}
951	iterator insertAutomaticObjDtor(iterator I, VarDecl VD, Stmt S) {
952	*I = CFGAutomaticObjDtor(VD, S);
953	return ++I;
954	}
955
956	// Scope leaving must be performed in reversed order. So insertion is in two
957	// steps. First we prepare space for some number of elements, then we insert
958	// the elements beginning at the last position in prepared space.
959	iterator beginLifetimeEndsInsert(iterator I, size_t Cnt,
960	BumpVectorContext &C) {
961	return iterator(
962	Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
963	}
964	iterator insertLifetimeEnds(iterator I, VarDecl VD, Stmt S) {
965	*I = CFGLifetimeEnds(VD, S);
966	return ++I;
967	}
968
969	// Scope leaving must be performed in reversed order. So insertion is in two
970	// steps. First we prepare space for some number of elements, then we insert
971	// the elements beginning at the last position in prepared space.
972	iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) {
973	return iterator(
974	Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
975	}
976	iterator insertScopeEnd(iterator I, VarDecl VD, Stmt S) {
977	*I = CFGScopeEnd(VD, S);
978	return ++I;
979	}
980
981	};
982
983	/// CFGCallback defines methods that should be called when a logical
984	/// operator error is found when building the CFG.
985	class CFGCallback {
986	public:
987	CFGCallback() = default;
988	virtual ~CFGCallback() = default;
989
990	virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
991	virtual void compareBitwiseEquality(const BinaryOperator *B,
992	bool isAlwaysTrue) {}
993	};
994
995	/// Represents a source-level, intra-procedural CFG that represents the
996	/// control-flow of a Stmt. The Stmt can represent an entire function body,
997	/// or a single expression. A CFG will always contain one empty block that
998	/// represents the Exit point of the CFG. A CFG will also contain a designated
999	/// Entry block. The CFG solely represents control-flow; it consists of
1000	/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
1001	/// was constructed from.
1002	class CFG {
1003	public:
1004	//===--------------------------------------------------------------------===//
1005	// CFG Construction & Manipulation.
1006	//===--------------------------------------------------------------------===//
1007
1008	class BuildOptions {
1009	std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
1010
1011	public:
1012	using ForcedBlkExprs = llvm::DenseMap<const Stmt , const CFGBlock >;
1013
1014	ForcedBlkExprs **forcedBlkExprs = nullptr;
1015	CFGCallback *Observer = nullptr;
1016	bool PruneTriviallyFalseEdges = true;
1017	bool AddEHEdges = false;
1018	bool AddInitializers = false;
1019	bool AddImplicitDtors = false;
1020	bool AddLifetime = false;
1021	bool AddLoopExit = false;
1022	bool AddTemporaryDtors = false;
1023	bool AddScopes = false;
1024	bool AddStaticInitBranches = false;
1025	bool AddCXXNewAllocator = false;
1026	bool AddCXXDefaultInitExprInCtors = false;
1027	bool AddRichCXXConstructors = false;
1028	bool MarkElidedCXXConstructors = false;
1029
1030	BuildOptions() = default;
1031
1032	bool alwaysAdd(const Stmt *stmt) const {
1033	return alwaysAddMask[stmt->getStmtClass()];
1034	}
1035
1036	BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
1037	alwaysAddMask[stmtClass] = val;
1038	return *this;
1039	}
1040
1041	BuildOptions &setAllAlwaysAdd() {
1042	alwaysAddMask.set();
1043	return *this;
1044	}
1045	};
1046
1047	/// Builds a CFG from an AST.
1048	static std::unique_ptr<CFG> buildCFG(const Decl D, Stmt AST, ASTContext *C,
1049	const BuildOptions &BO);
1050
1051	/// Create a new block in the CFG. The CFG owns the block; the caller should
1052	/// not directly free it.
1053	CFGBlock *createBlock();
1054
1055	/// Set the entry block of the CFG. This is typically used only during CFG
1056	/// construction. Most CFG clients expect that the entry block has no
1057	/// predecessors and contains no statements.
1058	void setEntry(CFGBlock *B) { Entry = B; }
1059
1060	/// Set the block used for indirect goto jumps. This is typically used only
1061	/// during CFG construction.
1062	void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
1063
1064	//===--------------------------------------------------------------------===//
1065	// Block Iterators
1066	//===--------------------------------------------------------------------===//
1067
1068	using CFGBlockListTy = BumpVector<CFGBlock *>;
1069	using iterator = CFGBlockListTy::iterator;
1070	using const_iterator = CFGBlockListTy::const_iterator;
1071	using reverse_iterator = std::reverse_iterator<iterator>;
1072	using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1073
1074	CFGBlock & front() { return *Blocks.front(); }
1075	CFGBlock & back() { return *Blocks.back(); }
1076
1077	iterator begin() { return Blocks.begin(); }
1078	iterator end() { return Blocks.end(); }
1079	const_iterator begin() const { return Blocks.begin(); }
1080	const_iterator end() const { return Blocks.end(); }
1081
1082	iterator nodes_begin() { return iterator(Blocks.begin()); }
1083	iterator nodes_end() { return iterator(Blocks.end()); }
1084	const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
1085	const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
1086
1087	reverse_iterator rbegin() { return Blocks.rbegin(); }
1088	reverse_iterator rend() { return Blocks.rend(); }
1089	const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
1090	const_reverse_iterator rend() const { return Blocks.rend(); }
1091
1092	CFGBlock & getEntry() { return *Entry; }
1093	const CFGBlock & getEntry() const { return *Entry; }
1094	CFGBlock & getExit() { return *Exit; }
1095	const CFGBlock & getExit() const { return *Exit; }
1096
1097	CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; }
1098	const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
1099
1100	using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1101
1102	try_block_iterator try_blocks_begin() const {
1103	return TryDispatchBlocks.begin();
1104	}
1105
1106	try_block_iterator try_blocks_end() const {
1107	return TryDispatchBlocks.end();
1108	}
1109
1110	void addTryDispatchBlock(const CFGBlock *block) {
1111	TryDispatchBlocks.push_back(block);
1112	}
1113
1114	/// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
1115	///
1116	/// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
1117	/// multiple decls.
1118	void addSyntheticDeclStmt(const DeclStmt *Synthetic,
1119	const DeclStmt *Source) {
1120	(0) . __assert_fail ("Synthetic->isSingleDecl() && \"Can handle single declarations only\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 1120, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
1121	(0) . __assert_fail ("Synthetic != Source && \"Don't include original DeclStmts in map\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 1121, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(Synthetic != Source && "Don't include original DeclStmts in map");
1122	(0) . __assert_fail ("!SyntheticDeclStmts.count(Synthetic) && \"Already in map\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/CFG.h", 1122, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
1123	SyntheticDeclStmts[Synthetic] = Source;
1124	}
1125
1126	using synthetic_stmt_iterator =
1127	llvm::DenseMap<const DeclStmt , const DeclStmt >::const_iterator;
1128	using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
1129
1130	/// Iterates over synthetic DeclStmts in the CFG.
1131	///
1132	/// Each element is a (synthetic statement, source statement) pair.
1133	///
1134	/// \sa addSyntheticDeclStmt
1135	synthetic_stmt_iterator synthetic_stmt_begin() const {
1136	return SyntheticDeclStmts.begin();
1137	}
1138
1139	/// \sa synthetic_stmt_begin
1140	synthetic_stmt_iterator synthetic_stmt_end() const {
1141	return SyntheticDeclStmts.end();
1142	}
1143
1144	/// \sa synthetic_stmt_begin
1145	synthetic_stmt_range synthetic_stmts() const {
1146	return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
1147	}
1148
1149	//===--------------------------------------------------------------------===//
1150	// Member templates useful for various batch operations over CFGs.
1151	//===--------------------------------------------------------------------===//
1152
1153	template <typename CALLBACK>
1154	void VisitBlockStmts(CALLBACK& O) const {
1155	for (const_iterator I = begin(), E = end(); I != E; ++I)
1156	for (CFGBlock::const_iterator BI = (I)->begin(), BE = (I)->end();
1157	BI != BE; ++BI) {
1158	if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1159	O(const_cast<Stmt*>(stmt->getStmt()));
1160	}
1161	}
1162
1163	//===--------------------------------------------------------------------===//
1164	// CFG Introspection.
1165	//===--------------------------------------------------------------------===//
1166
1167	/// Returns the total number of BlockIDs allocated (which start at 0).
1168	unsigned getNumBlockIDs() const { return NumBlockIDs; }
1169
1170	/// Return the total number of CFGBlocks within the CFG This is simply a
1171	/// renaming of the getNumBlockIDs(). This is necessary because the dominator
1172	/// implementation needs such an interface.
1173	unsigned size() const { return NumBlockIDs; }
1174
1175	//===--------------------------------------------------------------------===//
1176	// CFG Debugging: Pretty-Printing and Visualization.
1177	//===--------------------------------------------------------------------===//
1178
1179	void viewCFG(const LangOptions &LO) const;
1180	void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1181	void dump(const LangOptions &LO, bool ShowColors) const;
1182
1183	//===--------------------------------------------------------------------===//
1184	// Internal: constructors and data.
1185	//===--------------------------------------------------------------------===//
1186
1187	CFG() : Blocks(BlkBVC, 10) {}
1188
1189	llvm::BumpPtrAllocator& getAllocator() {
1190	return BlkBVC.getAllocator();
1191	}
1192
1193	BumpVectorContext &getBumpVectorContext() {
1194	return BlkBVC;
1195	}
1196
1197	private:
1198	CFGBlock *Entry = nullptr;
1199	CFGBlock *Exit = nullptr;
1200
1201	// Special block to contain collective dispatch for indirect gotos
1202	CFGBlock* IndirectGotoBlock = nullptr;
1203
1204	unsigned NumBlockIDs = 0;
1205
1206	BumpVectorContext BlkBVC;
1207
1208	CFGBlockListTy Blocks;
1209
1210	/// C++ 'try' statements are modeled with an indirect dispatch block.
1211	/// This is the collection of such blocks present in the CFG.
1212	std::vector<const CFGBlock *> TryDispatchBlocks;
1213
1214	/// Collects DeclStmts synthesized for this CFG and maps each one back to its
1215	/// source DeclStmt.
1216	llvm::DenseMap<const DeclStmt , const DeclStmt > SyntheticDeclStmts;
1217	};
1218
1219	} // namespace clang
1220
1221	//===----------------------------------------------------------------------===//
1222	// GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1223	//===----------------------------------------------------------------------===//
1224
1225	namespace llvm {
1226
1227	/// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1228	/// CFGTerminator to a specific Stmt class.
1229	template <> struct simplify_type< ::clang::CFGTerminator> {
1230	using SimpleType = ::clang::Stmt *;
1231
1232	static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
1233	return Val.getStmt();
1234	}
1235	};
1236
1237	// Traits for: CFGBlock
1238
1239	template <> struct GraphTraits< ::clang::CFGBlock *> {
1240	using NodeRef = ::clang::CFGBlock *;
1241	using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
1242
1243	static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1244	static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1245	static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1246	};
1247
1248	template <> struct GraphTraits< const ::clang::CFGBlock *> {
1249	using NodeRef = const ::clang::CFGBlock *;
1250	using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
1251
1252	static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1253	static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1254	static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1255	};
1256
1257	template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1258	using NodeRef = ::clang::CFGBlock *;
1259	using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1260
1261	static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1262	return G.Graph;
1263	}
1264
1265	static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1266	static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1267	};
1268
1269	template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1270	using NodeRef = const ::clang::CFGBlock *;
1271	using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1272
1273	static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1274	return G.Graph;
1275	}
1276
1277	static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1278	static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1279	};
1280
1281	// Traits for: CFG
1282
1283	template <> struct GraphTraits< ::clang::CFG* >
1284	: public GraphTraits< ::clang::CFGBlock *> {
1285	using nodes_iterator = ::clang::CFG::iterator;
1286
1287	static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1288	static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1289	static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1290	static unsigned size(::clang::CFG* F) { return F->size(); }
1291	};
1292
1293	template <> struct GraphTraits<const ::clang::CFG* >
1294	: public GraphTraits<const ::clang::CFGBlock *> {
1295	using nodes_iterator = ::clang::CFG::const_iterator;
1296
1297	static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1298
1299	static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1300	return F->nodes_begin();
1301	}
1302
1303	static nodes_iterator nodes_end( const ::clang::CFG* F) {
1304	return F->nodes_end();
1305	}
1306
1307	static unsigned size(const ::clang::CFG* F) {
1308	return F->size();
1309	}
1310	};
1311
1312	template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1313	: public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1314	using nodes_iterator = ::clang::CFG::iterator;
1315
1316	static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1317	static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1318	static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1319	};
1320
1321	template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1322	: public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1323	using nodes_iterator = ::clang::CFG::const_iterator;
1324
1325	static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1326
1327	static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1328	return F->nodes_begin();
1329	}
1330
1331	static nodes_iterator nodes_end(const ::clang::CFG* F) {
1332	return F->nodes_end();
1333	}
1334	};
1335
1336	} // namespace llvm
1337
1338	#endif // LLVM_CLANG_ANALYSIS_CFG_H
1339