WebSVN – QNX 8.QNX8 LLVM/Clang compiler suite – Blame – /llvm-build/x86_64/include/clang/Analysis/Analyses/ThreadSafetyTIL.h

Rev	Author	Line No.	Line
14	pmbaty	1	//===- ThreadSafetyTIL.h ----------------------------------------- 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 a simple Typed Intermediate Language, or TIL, that is used
		10	// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended
		11	// to be largely independent of clang, in the hope that the analysis can be
		12	// reused for other non-C++ languages. All dependencies on clang/llvm should
		13	// go in ThreadSafetyUtil.h.
		14	//
		15	// Thread safety analysis works by comparing mutex expressions, e.g.
		16	//
		17	// class A { Mutex mu; int dat GUARDED_BY(this->mu); }
		18	// class B { A a; }
		19	//
		20	// void foo(B* b) {
		21	// (b).a.mu.lock(); // locks (b).a.mu
		22	// b->a.dat = 0; // substitute &b->a for 'this';
		23	// // requires lock on (&b->a)->mu
		24	// (b->a.mu).unlock(); // unlocks (b->a.mu)
		25	// }
		26	//
		27	// As illustrated by the above example, clang Exprs are not well-suited to
		28	// represent mutex expressions directly, since there is no easy way to compare
		29	// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs
		30	// into a simple intermediate language (IL). The IL supports:
		31	//
		32	// (1) comparisons for semantic equality of expressions
		33	// (2) SSA renaming of variables
		34	// (3) wildcards and pattern matching over expressions
		35	// (4) hash-based expression lookup
		36	//
		37	// The TIL is currently very experimental, is intended only for use within
		38	// the thread safety analysis, and is subject to change without notice.
		39	// After the API stabilizes and matures, it may be appropriate to make this
		40	// more generally available to other analyses.
		41	//
		42	// UNDER CONSTRUCTION. USE AT YOUR OWN RISK.
		43	//
		44	//===----------------------------------------------------------------------===//
		45
		46	#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
		47	#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
		48
		49	#include "clang/AST/Decl.h"
		50	#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
		51	#include "clang/Basic/LLVM.h"
		52	#include "llvm/ADT/ArrayRef.h"
		53	#include "llvm/ADT/StringRef.h"
		54	#include "llvm/Support/Casting.h"
		55	#include "llvm/Support/raw_ostream.h"
		56	#include <algorithm>
		57	#include <cassert>
		58	#include <cstddef>
		59	#include <cstdint>
		60	#include <iterator>
		61	#include <optional>
		62	#include <string>
		63	#include <utility>
		64
		65	namespace clang {
		66
		67	class CallExpr;
		68	class Expr;
		69	class Stmt;
		70
		71	namespace threadSafety {
		72	namespace til {
		73
		74	class BasicBlock;
		75
		76	/// Enum for the different distinct classes of SExpr
		77	enum TIL_Opcode : unsigned char {
		78	#define TIL_OPCODE_DEF(X) COP_##X,
		79	#include "ThreadSafetyOps.def"
		80	#undef TIL_OPCODE_DEF
		81	};
		82
		83	/// Opcode for unary arithmetic operations.
		84	enum TIL_UnaryOpcode : unsigned char {
		85	UOP_Minus, // -
		86	UOP_BitNot, // ~
		87	UOP_LogicNot // !
		88	};
		89
		90	/// Opcode for binary arithmetic operations.
		91	enum TIL_BinaryOpcode : unsigned char {
		92	BOP_Add, // +
		93	BOP_Sub, // -
		94	BOP_Mul, // *
		95	BOP_Div, // /
		96	BOP_Rem, // %
		97	BOP_Shl, // <<
		98	BOP_Shr, // >>
		99	BOP_BitAnd, // &
		100	BOP_BitXor, // ^
		101	BOP_BitOr, // \|
		102	BOP_Eq, // ==
		103	BOP_Neq, // !=
		104	BOP_Lt, // <
		105	BOP_Leq, // <=
		106	BOP_Cmp, // <=>
		107	BOP_LogicAnd, // && (no short-circuit)
		108	BOP_LogicOr // \|\| (no short-circuit)
		109	};
		110
		111	/// Opcode for cast operations.
		112	enum TIL_CastOpcode : unsigned char {
		113	CAST_none = 0,
		114
		115	// Extend precision of numeric type
		116	CAST_extendNum,
		117
		118	// Truncate precision of numeric type
		119	CAST_truncNum,
		120
		121	// Convert to floating point type
		122	CAST_toFloat,
		123
		124	// Convert to integer type
		125	CAST_toInt,
		126
		127	// Convert smart pointer to pointer (C++ only)
		128	CAST_objToPtr
		129	};
		130
		131	const TIL_Opcode COP_Min = COP_Future;
		132	const TIL_Opcode COP_Max = COP_Branch;
		133	const TIL_UnaryOpcode UOP_Min = UOP_Minus;
		134	const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
		135	const TIL_BinaryOpcode BOP_Min = BOP_Add;
		136	const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
		137	const TIL_CastOpcode CAST_Min = CAST_none;
		138	const TIL_CastOpcode CAST_Max = CAST_toInt;
		139
		140	/// Return the name of a unary opcode.
		141	StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
		142
		143	/// Return the name of a binary opcode.
		144	StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
		145
		146	/// ValueTypes are data types that can actually be held in registers.
		147	/// All variables and expressions must have a value type.
		148	/// Pointer types are further subdivided into the various heap-allocated
		149	/// types, such as functions, records, etc.
		150	/// Structured types that are passed by value (e.g. complex numbers)
		151	/// require special handling; they use BT_ValueRef, and size ST_0.
		152	struct ValueType {
		153	enum BaseType : unsigned char {
		154	BT_Void = 0,
		155	BT_Bool,
		156	BT_Int,
		157	BT_Float,
		158	BT_String, // String literals
		159	BT_Pointer,
		160	BT_ValueRef
		161	};
		162
		163	enum SizeType : unsigned char {
		164	ST_0 = 0,
		165	ST_1,
		166	ST_8,
		167	ST_16,
		168	ST_32,
		169	ST_64,
		170	ST_128
		171	};
		172
		173	ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
		174	: Base(B), Size(Sz), Signed(S), VectSize(VS) {}
		175
		176	inline static SizeType getSizeType(unsigned nbytes);
		177
		178	template <class T>
		179	inline static ValueType getValueType();
		180
		181	BaseType Base;
		182	SizeType Size;
		183	bool Signed;
		184
		185	// 0 for scalar, otherwise num elements in vector
		186	unsigned char VectSize;
		187	};
		188
		189	inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
		190	switch (nbytes) {
		191	case 1: return ST_8;
		192	case 2: return ST_16;
		193	case 4: return ST_32;
		194	case 8: return ST_64;
		195	case 16: return ST_128;
		196	default: return ST_0;
		197	}
		198	}
		199
		200	template<>
		201	inline ValueType ValueType::getValueType<void>() {
		202	return ValueType(BT_Void, ST_0, false, 0);
		203	}
		204
		205	template<>
		206	inline ValueType ValueType::getValueType<bool>() {
		207	return ValueType(BT_Bool, ST_1, false, 0);
		208	}
		209
		210	template<>
		211	inline ValueType ValueType::getValueType<int8_t>() {
		212	return ValueType(BT_Int, ST_8, true, 0);
		213	}
		214
		215	template<>
		216	inline ValueType ValueType::getValueType<uint8_t>() {
		217	return ValueType(BT_Int, ST_8, false, 0);
		218	}
		219
		220	template<>
		221	inline ValueType ValueType::getValueType<int16_t>() {
		222	return ValueType(BT_Int, ST_16, true, 0);
		223	}
		224
		225	template<>
		226	inline ValueType ValueType::getValueType<uint16_t>() {
		227	return ValueType(BT_Int, ST_16, false, 0);
		228	}
		229
		230	template<>
		231	inline ValueType ValueType::getValueType<int32_t>() {
		232	return ValueType(BT_Int, ST_32, true, 0);
		233	}
		234
		235	template<>
		236	inline ValueType ValueType::getValueType<uint32_t>() {
		237	return ValueType(BT_Int, ST_32, false, 0);
		238	}
		239
		240	template<>
		241	inline ValueType ValueType::getValueType<int64_t>() {
		242	return ValueType(BT_Int, ST_64, true, 0);
		243	}
		244
		245	template<>
		246	inline ValueType ValueType::getValueType<uint64_t>() {
		247	return ValueType(BT_Int, ST_64, false, 0);
		248	}
		249
		250	template<>
		251	inline ValueType ValueType::getValueType<float>() {
		252	return ValueType(BT_Float, ST_32, true, 0);
		253	}
		254
		255	template<>
		256	inline ValueType ValueType::getValueType<double>() {
		257	return ValueType(BT_Float, ST_64, true, 0);
		258	}
		259
		260	template<>
		261	inline ValueType ValueType::getValueType<long double>() {
		262	return ValueType(BT_Float, ST_128, true, 0);
		263	}
		264
		265	template<>
		266	inline ValueType ValueType::getValueType<StringRef>() {
		267	return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
		268	}
		269
		270	template<>
		271	inline ValueType ValueType::getValueType<void*>() {
		272	return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
		273	}
		274
		275	/// Base class for AST nodes in the typed intermediate language.
		276	class SExpr {
		277	public:
		278	SExpr() = delete;
		279
		280	TIL_Opcode opcode() const { return Opcode; }
		281
		282	// Subclasses of SExpr must define the following:
		283	//
		284	// This(const This& E, ...) {
		285	// copy constructor: construct copy of E, with some additional arguments.
		286	// }
		287	//
		288	// template <class V>
		289	// typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		290	// traverse all subexpressions, following the traversal/rewriter interface.
		291	// }
		292	//
		293	// template <class C> typename C::CType compare(CType* E, C& Cmp) {
		294	// compare all subexpressions, following the comparator interface
		295	// }
		296	void *operator new(size_t S, MemRegionRef &R) {
		297	return ::operator new(S, R);
		298	}
		299
		300	/// SExpr objects must be created in an arena.
		301	void *operator new(size_t) = delete;
		302
		303	/// SExpr objects cannot be deleted.
		304	// This declaration is public to workaround a gcc bug that breaks building
		305	// with REQUIRES_EH=1.
		306	void operator delete(void *) = delete;
		307
		308	/// Returns the instruction ID for this expression.
		309	/// All basic block instructions have a unique ID (i.e. virtual register).
		310	unsigned id() const { return SExprID; }
		311
		312	/// Returns the block, if this is an instruction in a basic block,
		313	/// otherwise returns null.
		314	BasicBlock *block() const { return Block; }
		315
		316	/// Set the basic block and instruction ID for this expression.
		317	void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
		318
		319	protected:
		320	SExpr(TIL_Opcode Op) : Opcode(Op) {}
		321	SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
		322
		323	const TIL_Opcode Opcode;
		324	unsigned char Reserved = 0;
		325	unsigned short Flags = 0;
		326	unsigned SExprID = 0;
		327	BasicBlock *Block = nullptr;
		328	};
		329
		330	// Contains various helper functions for SExprs.
		331	namespace ThreadSafetyTIL {
		332
		333	inline bool isTrivial(const SExpr *E) {
		334	TIL_Opcode Op = E->opcode();
		335	return Op == COP_Variable \|\| Op == COP_Literal \|\| Op == COP_LiteralPtr;
		336	}
		337
		338	} // namespace ThreadSafetyTIL
		339
		340	// Nodes which declare variables
		341
		342	/// A named variable, e.g. "x".
		343	///
		344	/// There are two distinct places in which a Variable can appear in the AST.
		345	/// A variable declaration introduces a new variable, and can occur in 3 places:
		346	/// Let-expressions: (Let (x = t) u)
		347	/// Functions: (Function (x : t) u)
		348	/// Self-applicable functions (SFunction (x) t)
		349	///
		350	/// If a variable occurs in any other location, it is a reference to an existing
		351	/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
		352	/// allocate a separate AST node for variable references; a reference is just a
		353	/// pointer to the original declaration.
		354	class Variable : public SExpr {
		355	public:
		356	enum VariableKind {
		357	/// Let-variable
		358	VK_Let,
		359
		360	/// Function parameter
		361	VK_Fun,
		362
		363	/// SFunction (self) parameter
		364	VK_SFun
		365	};
		366
		367	Variable(StringRef s, SExpr *D = nullptr)
		368	: SExpr(COP_Variable), Name(s), Definition(D) {
		369	Flags = VK_Let;
		370	}
		371
		372	Variable(SExpr D, const ValueDecl Cvd = nullptr)
		373	: SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
		374	Definition(D), Cvdecl(Cvd) {
		375	Flags = VK_Let;
		376	}
		377
		378	Variable(const Variable &Vd, SExpr *D) // rewrite constructor
		379	: SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
		380	Flags = Vd.kind();
		381	}
		382
		383	static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
		384
		385	/// Return the kind of variable (let, function param, or self)
		386	VariableKind kind() const { return static_cast<VariableKind>(Flags); }
		387
		388	/// Return the name of the variable, if any.
		389	StringRef name() const { return Name; }
		390
		391	/// Return the clang declaration for this variable, if any.
		392	const ValueDecl *clangDecl() const { return Cvdecl; }
		393
		394	/// Return the definition of the variable.
		395	/// For let-vars, this is the setting expression.
		396	/// For function and self parameters, it is the type of the variable.
		397	SExpr *definition() { return Definition; }
		398	const SExpr *definition() const { return Definition; }
		399
		400	void setName(StringRef S) { Name = S; }
		401	void setKind(VariableKind K) { Flags = K; }
		402	void setDefinition(SExpr *E) { Definition = E; }
		403	void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
		404
		405	template <class V>
		406	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		407	// This routine is only called for variable references.
		408	return Vs.reduceVariableRef(this);
		409	}
		410
		411	template <class C>
		412	typename C::CType compare(const Variable* E, C& Cmp) const {
		413	return Cmp.compareVariableRefs(this, E);
		414	}
		415
		416	private:
		417	friend class BasicBlock;
		418	friend class Function;
		419	friend class Let;
		420	friend class SFunction;
		421
		422	// The name of the variable.
		423	StringRef Name;
		424
		425	// The TIL type or definition.
		426	SExpr *Definition;
		427
		428	// The clang declaration for this variable.
		429	const ValueDecl *Cvdecl = nullptr;
		430	};
		431
		432	/// Placeholder for an expression that has not yet been created.
		433	/// Used to implement lazy copy and rewriting strategies.
		434	class Future : public SExpr {
		435	public:
		436	enum FutureStatus {
		437	FS_pending,
		438	FS_evaluating,
		439	FS_done
		440	};
		441
		442	Future() : SExpr(COP_Future) {}
		443	virtual ~Future() = delete;
		444
		445	static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
		446
		447	// A lazy rewriting strategy should subclass Future and override this method.
		448	virtual SExpr *compute() { return nullptr; }
		449
		450	// Return the result of this future if it exists, otherwise return null.
		451	SExpr *maybeGetResult() const { return Result; }
		452
		453	// Return the result of this future; forcing it if necessary.
		454	SExpr *result() {
		455	switch (Status) {
		456	case FS_pending:
		457	return force();
		458	case FS_evaluating:
		459	return nullptr; // infinite loop; illegal recursion.
		460	case FS_done:
		461	return Result;
		462	}
		463	}
		464
		465	template <class V>
		466	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		467	assert(Result && "Cannot traverse Future that has not been forced.");
		468	return Vs.traverse(Result, Ctx);
		469	}
		470
		471	template <class C>
		472	typename C::CType compare(const Future* E, C& Cmp) const {
		473	if (!Result \|\| !E->Result)
		474	return Cmp.comparePointers(this, E);
		475	return Cmp.compare(Result, E->Result);
		476	}
		477
		478	private:
		479	SExpr* force();
		480
		481	FutureStatus Status = FS_pending;
		482	SExpr *Result = nullptr;
		483	};
		484
		485	/// Placeholder for expressions that cannot be represented in the TIL.
		486	class Undefined : public SExpr {
		487	public:
		488	Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
		489	Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
		490
		491	static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
		492
		493	template <class V>
		494	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		495	return Vs.reduceUndefined(*this);
		496	}
		497
		498	template <class C>
		499	typename C::CType compare(const Undefined* E, C& Cmp) const {
		500	return Cmp.trueResult();
		501	}
		502
		503	private:
		504	const Stmt *Cstmt;
		505	};
		506
		507	/// Placeholder for a wildcard that matches any other expression.
		508	class Wildcard : public SExpr {
		509	public:
		510	Wildcard() : SExpr(COP_Wildcard) {}
		511	Wildcard(const Wildcard &) = default;
		512
		513	static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
		514
		515	template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		516	return Vs.reduceWildcard(*this);
		517	}
		518
		519	template <class C>
		520	typename C::CType compare(const Wildcard* E, C& Cmp) const {
		521	return Cmp.trueResult();
		522	}
		523	};
		524
		525	template <class T> class LiteralT;
		526
		527	// Base class for literal values.
		528	class Literal : public SExpr {
		529	public:
		530	Literal(const Expr *C)
		531	: SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
		532	Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
		533	Literal(const Literal &) = default;
		534
		535	static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
		536
		537	// The clang expression for this literal.
		538	const Expr *clangExpr() const { return Cexpr; }
		539
		540	ValueType valueType() const { return ValType; }
		541
		542	template<class T> const LiteralT<T>& as() const {
		543	return static_cast<const LiteralT<T>>(this);
		544	}
		545	template<class T> LiteralT<T>& as() {
		546	return static_cast<LiteralT<T>>(this);
		547	}
		548
		549	template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
		550
		551	template <class C>
		552	typename C::CType compare(const Literal* E, C& Cmp) const {
		553	// TODO: defer actual comparison to LiteralT
		554	return Cmp.trueResult();
		555	}
		556
		557	private:
		558	const ValueType ValType;
		559	const Expr *Cexpr = nullptr;
		560	};
		561
		562	// Derived class for literal values, which stores the actual value.
		563	template<class T>
		564	class LiteralT : public Literal {
		565	public:
		566	LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
		567	LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
		568
		569	T value() const { return Val;}
		570	T& value() { return Val; }
		571
		572	private:
		573	T Val;
		574	};
		575
		576	template <class V>
		577	typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
		578	if (Cexpr)
		579	return Vs.reduceLiteral(*this);
		580
		581	switch (ValType.Base) {
		582	case ValueType::BT_Void:
		583	break;
		584	case ValueType::BT_Bool:
		585	return Vs.reduceLiteralT(as<bool>());
		586	case ValueType::BT_Int: {
		587	switch (ValType.Size) {
		588	case ValueType::ST_8:
		589	if (ValType.Signed)
		590	return Vs.reduceLiteralT(as<int8_t>());
		591	else
		592	return Vs.reduceLiteralT(as<uint8_t>());
		593	case ValueType::ST_16:
		594	if (ValType.Signed)
		595	return Vs.reduceLiteralT(as<int16_t>());
		596	else
		597	return Vs.reduceLiteralT(as<uint16_t>());
		598	case ValueType::ST_32:
		599	if (ValType.Signed)
		600	return Vs.reduceLiteralT(as<int32_t>());
		601	else
		602	return Vs.reduceLiteralT(as<uint32_t>());
		603	case ValueType::ST_64:
		604	if (ValType.Signed)
		605	return Vs.reduceLiteralT(as<int64_t>());
		606	else
		607	return Vs.reduceLiteralT(as<uint64_t>());
		608	default:
		609	break;
		610	}
		611	}
		612	case ValueType::BT_Float: {
		613	switch (ValType.Size) {
		614	case ValueType::ST_32:
		615	return Vs.reduceLiteralT(as<float>());
		616	case ValueType::ST_64:
		617	return Vs.reduceLiteralT(as<double>());
		618	default:
		619	break;
		620	}
		621	}
		622	case ValueType::BT_String:
		623	return Vs.reduceLiteralT(as<StringRef>());
		624	case ValueType::BT_Pointer:
		625	return Vs.reduceLiteralT(as<void*>());
		626	case ValueType::BT_ValueRef:
		627	break;
		628	}
		629	return Vs.reduceLiteral(*this);
		630	}
		631
		632	/// A Literal pointer to an object allocated in memory.
		633	/// At compile time, pointer literals are represented by symbolic names.
		634	class LiteralPtr : public SExpr {
		635	public:
		636	LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
		637	LiteralPtr(const LiteralPtr &) = default;
		638
		639	static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
		640
		641	// The clang declaration for the value that this pointer points to.
		642	const ValueDecl *clangDecl() const { return Cvdecl; }
		643	void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
		644
		645	template <class V>
		646	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		647	return Vs.reduceLiteralPtr(*this);
		648	}
		649
		650	template <class C>
		651	typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
		652	if (!Cvdecl \|\| !E->Cvdecl)
		653	return Cmp.comparePointers(this, E);
		654	return Cmp.comparePointers(Cvdecl, E->Cvdecl);
		655	}
		656
		657	private:
		658	const ValueDecl *Cvdecl;
		659	};
		660
		661	/// A function -- a.k.a. lambda abstraction.
		662	/// Functions with multiple arguments are created by currying,
		663	/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
		664	class Function : public SExpr {
		665	public:
		666	Function(Variable Vd, SExpr Bd)
		667	: SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
		668	Vd->setKind(Variable::VK_Fun);
		669	}
		670
		671	Function(const Function &F, Variable Vd, SExpr Bd) // rewrite constructor
		672	: SExpr(F), VarDecl(Vd), Body(Bd) {
		673	Vd->setKind(Variable::VK_Fun);
		674	}
		675
		676	static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
		677
		678	Variable *variableDecl() { return VarDecl; }
		679	const Variable *variableDecl() const { return VarDecl; }
		680
		681	SExpr *body() { return Body; }
		682	const SExpr *body() const { return Body; }
		683
		684	template <class V>
		685	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		686	// This is a variable declaration, so traverse the definition.
		687	auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
		688	// Tell the rewriter to enter the scope of the function.
		689	Variable Nvd = Vs.enterScope(VarDecl, E0);
		690	auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
		691	Vs.exitScope(*VarDecl);
		692	return Vs.reduceFunction(*this, Nvd, E1);
		693	}
		694
		695	template <class C>
		696	typename C::CType compare(const Function* E, C& Cmp) const {
		697	typename C::CType Ct =
		698	Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
		699	if (Cmp.notTrue(Ct))
		700	return Ct;
		701	Cmp.enterScope(variableDecl(), E->variableDecl());
		702	Ct = Cmp.compare(body(), E->body());
		703	Cmp.leaveScope();
		704	return Ct;
		705	}
		706
		707	private:
		708	Variable *VarDecl;
		709	SExpr* Body;
		710	};
		711
		712	/// A self-applicable function.
		713	/// A self-applicable function can be applied to itself. It's useful for
		714	/// implementing objects and late binding.
		715	class SFunction : public SExpr {
		716	public:
		717	SFunction(Variable Vd, SExpr B)
		718	: SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
		719	assert(Vd->Definition == nullptr);
		720	Vd->setKind(Variable::VK_SFun);
		721	Vd->Definition = this;
		722	}
		723
		724	SFunction(const SFunction &F, Variable Vd, SExpr B) // rewrite constructor
		725	: SExpr(F), VarDecl(Vd), Body(B) {
		726	assert(Vd->Definition == nullptr);
		727	Vd->setKind(Variable::VK_SFun);
		728	Vd->Definition = this;
		729	}
		730
		731	static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
		732
		733	Variable *variableDecl() { return VarDecl; }
		734	const Variable *variableDecl() const { return VarDecl; }
		735
		736	SExpr *body() { return Body; }
		737	const SExpr *body() const { return Body; }
		738
		739	template <class V>
		740	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		741	// A self-variable points to the SFunction itself.
		742	// A rewrite must introduce the variable with a null definition, and update
		743	// it after 'this' has been rewritten.
		744	Variable Nvd = Vs.enterScope(VarDecl, nullptr);
		745	auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
		746	Vs.exitScope(*VarDecl);
		747	// A rewrite operation will call SFun constructor to set Vvd->Definition.
		748	return Vs.reduceSFunction(*this, Nvd, E1);
		749	}
		750
		751	template <class C>
		752	typename C::CType compare(const SFunction* E, C& Cmp) const {
		753	Cmp.enterScope(variableDecl(), E->variableDecl());
		754	typename C::CType Ct = Cmp.compare(body(), E->body());
		755	Cmp.leaveScope();
		756	return Ct;
		757	}
		758
		759	private:
		760	Variable *VarDecl;
		761	SExpr* Body;
		762	};
		763
		764	/// A block of code -- e.g. the body of a function.
		765	class Code : public SExpr {
		766	public:
		767	Code(SExpr T, SExpr B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
		768	Code(const Code &C, SExpr T, SExpr B) // rewrite constructor
		769	: SExpr(C), ReturnType(T), Body(B) {}
		770
		771	static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
		772
		773	SExpr *returnType() { return ReturnType; }
		774	const SExpr *returnType() const { return ReturnType; }
		775
		776	SExpr *body() { return Body; }
		777	const SExpr *body() const { return Body; }
		778
		779	template <class V>
		780	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		781	auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
		782	auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
		783	return Vs.reduceCode(*this, Nt, Nb);
		784	}
		785
		786	template <class C>
		787	typename C::CType compare(const Code* E, C& Cmp) const {
		788	typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
		789	if (Cmp.notTrue(Ct))
		790	return Ct;
		791	return Cmp.compare(body(), E->body());
		792	}
		793
		794	private:
		795	SExpr* ReturnType;
		796	SExpr* Body;
		797	};
		798
		799	/// A typed, writable location in memory
		800	class Field : public SExpr {
		801	public:
		802	Field(SExpr R, SExpr B) : SExpr(COP_Field), Range(R), Body(B) {}
		803	Field(const Field &C, SExpr R, SExpr B) // rewrite constructor
		804	: SExpr(C), Range(R), Body(B) {}
		805
		806	static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
		807
		808	SExpr *range() { return Range; }
		809	const SExpr *range() const { return Range; }
		810
		811	SExpr *body() { return Body; }
		812	const SExpr *body() const { return Body; }
		813
		814	template <class V>
		815	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		816	auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
		817	auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
		818	return Vs.reduceField(*this, Nr, Nb);
		819	}
		820
		821	template <class C>
		822	typename C::CType compare(const Field* E, C& Cmp) const {
		823	typename C::CType Ct = Cmp.compare(range(), E->range());
		824	if (Cmp.notTrue(Ct))
		825	return Ct;
		826	return Cmp.compare(body(), E->body());
		827	}
		828
		829	private:
		830	SExpr* Range;
		831	SExpr* Body;
		832	};
		833
		834	/// Apply an argument to a function.
		835	/// Note that this does not actually call the function. Functions are curried,
		836	/// so this returns a closure in which the first parameter has been applied.
		837	/// Once all parameters have been applied, Call can be used to invoke the
		838	/// function.
		839	class Apply : public SExpr {
		840	public:
		841	Apply(SExpr F, SExpr A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
		842	Apply(const Apply &A, SExpr F, SExpr Ar) // rewrite constructor
		843	: SExpr(A), Fun(F), Arg(Ar) {}
		844
		845	static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
		846
		847	SExpr *fun() { return Fun; }
		848	const SExpr *fun() const { return Fun; }
		849
		850	SExpr *arg() { return Arg; }
		851	const SExpr *arg() const { return Arg; }
		852
		853	template <class V>
		854	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		855	auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
		856	auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
		857	return Vs.reduceApply(*this, Nf, Na);
		858	}
		859
		860	template <class C>
		861	typename C::CType compare(const Apply* E, C& Cmp) const {
		862	typename C::CType Ct = Cmp.compare(fun(), E->fun());
		863	if (Cmp.notTrue(Ct))
		864	return Ct;
		865	return Cmp.compare(arg(), E->arg());
		866	}
		867
		868	private:
		869	SExpr* Fun;
		870	SExpr* Arg;
		871	};
		872
		873	/// Apply a self-argument to a self-applicable function.
		874	class SApply : public SExpr {
		875	public:
		876	SApply(SExpr Sf, SExpr A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
		877	SApply(SApply &A, SExpr Sf, SExpr Ar = nullptr) // rewrite constructor
		878	: SExpr(A), Sfun(Sf), Arg(Ar) {}
		879
		880	static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
		881
		882	SExpr *sfun() { return Sfun; }
		883	const SExpr *sfun() const { return Sfun; }
		884
		885	SExpr *arg() { return Arg ? Arg : Sfun; }
		886	const SExpr *arg() const { return Arg ? Arg : Sfun; }
		887
		888	bool isDelegation() const { return Arg != nullptr; }
		889
		890	template <class V>
		891	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		892	auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
		893	typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
		894	: nullptr;
		895	return Vs.reduceSApply(*this, Nf, Na);
		896	}
		897
		898	template <class C>
		899	typename C::CType compare(const SApply* E, C& Cmp) const {
		900	typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
		901	if (Cmp.notTrue(Ct) \|\| (!arg() && !E->arg()))
		902	return Ct;
		903	return Cmp.compare(arg(), E->arg());
		904	}
		905
		906	private:
		907	SExpr* Sfun;
		908	SExpr* Arg;
		909	};
		910
		911	/// Project a named slot from a C++ struct or class.
		912	class Project : public SExpr {
		913	public:
		914	Project(SExpr R, const ValueDecl Cvd)
		915	: SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
		916	assert(Cvd && "ValueDecl must not be null");
		917	}
		918
		919	static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
		920
		921	SExpr *record() { return Rec; }
		922	const SExpr *record() const { return Rec; }
		923
		924	const ValueDecl *clangDecl() const { return Cvdecl; }
		925
		926	bool isArrow() const { return (Flags & 0x01) != 0; }
		927
		928	void setArrow(bool b) {
		929	if (b) Flags \|= 0x01;
		930	else Flags &= 0xFFFE;
		931	}
		932
		933	StringRef slotName() const {
		934	if (Cvdecl->getDeclName().isIdentifier())
		935	return Cvdecl->getName();
		936	if (!SlotName) {
		937	SlotName = "";
		938	llvm::raw_string_ostream OS(*SlotName);
		939	Cvdecl->printName(OS);
		940	}
		941	return *SlotName;
		942	}
		943
		944	template <class V>
		945	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		946	auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
		947	return Vs.reduceProject(*this, Nr);
		948	}
		949
		950	template <class C>
		951	typename C::CType compare(const Project* E, C& Cmp) const {
		952	typename C::CType Ct = Cmp.compare(record(), E->record());
		953	if (Cmp.notTrue(Ct))
		954	return Ct;
		955	return Cmp.comparePointers(Cvdecl, E->Cvdecl);
		956	}
		957
		958	private:
		959	SExpr* Rec;
		960	mutable std::optional<std::string> SlotName;
		961	const ValueDecl *Cvdecl;
		962	};
		963
		964	/// Call a function (after all arguments have been applied).
		965	class Call : public SExpr {
		966	public:
		967	Call(SExpr T, const CallExpr Ce = nullptr)
		968	: SExpr(COP_Call), Target(T), Cexpr(Ce) {}
		969	Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
		970
		971	static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
		972
		973	SExpr *target() { return Target; }
		974	const SExpr *target() const { return Target; }
		975
		976	const CallExpr *clangCallExpr() const { return Cexpr; }
		977
		978	template <class V>
		979	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		980	auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
		981	return Vs.reduceCall(*this, Nt);
		982	}
		983
		984	template <class C>
		985	typename C::CType compare(const Call* E, C& Cmp) const {
		986	return Cmp.compare(target(), E->target());
		987	}
		988
		989	private:
		990	SExpr* Target;
		991	const CallExpr *Cexpr;
		992	};
		993
		994	/// Allocate memory for a new value on the heap or stack.
		995	class Alloc : public SExpr {
		996	public:
		997	enum AllocKind {
		998	AK_Stack,
		999	AK_Heap
		1000	};
		1001
		1002	Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
		1003	Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
		1004
		1005	static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
		1006
		1007	AllocKind kind() const { return static_cast<AllocKind>(Flags); }
		1008
		1009	SExpr *dataType() { return Dtype; }
		1010	const SExpr *dataType() const { return Dtype; }
		1011
		1012	template <class V>
		1013	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1014	auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
		1015	return Vs.reduceAlloc(*this, Nd);
		1016	}
		1017
		1018	template <class C>
		1019	typename C::CType compare(const Alloc* E, C& Cmp) const {
		1020	typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
		1021	if (Cmp.notTrue(Ct))
		1022	return Ct;
		1023	return Cmp.compare(dataType(), E->dataType());
		1024	}
		1025
		1026	private:
		1027	SExpr* Dtype;
		1028	};
		1029
		1030	/// Load a value from memory.
		1031	class Load : public SExpr {
		1032	public:
		1033	Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
		1034	Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
		1035
		1036	static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
		1037
		1038	SExpr *pointer() { return Ptr; }
		1039	const SExpr *pointer() const { return Ptr; }
		1040
		1041	template <class V>
		1042	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1043	auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
		1044	return Vs.reduceLoad(*this, Np);
		1045	}
		1046
		1047	template <class C>
		1048	typename C::CType compare(const Load* E, C& Cmp) const {
		1049	return Cmp.compare(pointer(), E->pointer());
		1050	}
		1051
		1052	private:
		1053	SExpr* Ptr;
		1054	};
		1055
		1056	/// Store a value to memory.
		1057	/// The destination is a pointer to a field, the source is the value to store.
		1058	class Store : public SExpr {
		1059	public:
		1060	Store(SExpr P, SExpr V) : SExpr(COP_Store), Dest(P), Source(V) {}
		1061	Store(const Store &S, SExpr P, SExpr V) : SExpr(S), Dest(P), Source(V) {}
		1062
		1063	static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
		1064
		1065	SExpr *destination() { return Dest; } // Address to store to
		1066	const SExpr *destination() const { return Dest; }
		1067
		1068	SExpr *source() { return Source; } // Value to store
		1069	const SExpr *source() const { return Source; }
		1070
		1071	template <class V>
		1072	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1073	auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
		1074	auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
		1075	return Vs.reduceStore(*this, Np, Nv);
		1076	}
		1077
		1078	template <class C>
		1079	typename C::CType compare(const Store* E, C& Cmp) const {
		1080	typename C::CType Ct = Cmp.compare(destination(), E->destination());
		1081	if (Cmp.notTrue(Ct))
		1082	return Ct;
		1083	return Cmp.compare(source(), E->source());
		1084	}
		1085
		1086	private:
		1087	SExpr* Dest;
		1088	SExpr* Source;
		1089	};
		1090
		1091	/// If p is a reference to an array, then p[i] is a reference to the i'th
		1092	/// element of the array.
		1093	class ArrayIndex : public SExpr {
		1094	public:
		1095	ArrayIndex(SExpr A, SExpr N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
		1096	ArrayIndex(const ArrayIndex &E, SExpr A, SExpr N)
		1097	: SExpr(E), Array(A), Index(N) {}
		1098
		1099	static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
		1100
		1101	SExpr *array() { return Array; }
		1102	const SExpr *array() const { return Array; }
		1103
		1104	SExpr *index() { return Index; }
		1105	const SExpr *index() const { return Index; }
		1106
		1107	template <class V>
		1108	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1109	auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
		1110	auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
		1111	return Vs.reduceArrayIndex(*this, Na, Ni);
		1112	}
		1113
		1114	template <class C>
		1115	typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
		1116	typename C::CType Ct = Cmp.compare(array(), E->array());
		1117	if (Cmp.notTrue(Ct))
		1118	return Ct;
		1119	return Cmp.compare(index(), E->index());
		1120	}
		1121
		1122	private:
		1123	SExpr* Array;
		1124	SExpr* Index;
		1125	};
		1126
		1127	/// Pointer arithmetic, restricted to arrays only.
		1128	/// If p is a reference to an array, then p + n, where n is an integer, is
		1129	/// a reference to a subarray.
		1130	class ArrayAdd : public SExpr {
		1131	public:
		1132	ArrayAdd(SExpr A, SExpr N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
		1133	ArrayAdd(const ArrayAdd &E, SExpr A, SExpr N)
		1134	: SExpr(E), Array(A), Index(N) {}
		1135
		1136	static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
		1137
		1138	SExpr *array() { return Array; }
		1139	const SExpr *array() const { return Array; }
		1140
		1141	SExpr *index() { return Index; }
		1142	const SExpr *index() const { return Index; }
		1143
		1144	template <class V>
		1145	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1146	auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
		1147	auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
		1148	return Vs.reduceArrayAdd(*this, Na, Ni);
		1149	}
		1150
		1151	template <class C>
		1152	typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
		1153	typename C::CType Ct = Cmp.compare(array(), E->array());
		1154	if (Cmp.notTrue(Ct))
		1155	return Ct;
		1156	return Cmp.compare(index(), E->index());
		1157	}
		1158
		1159	private:
		1160	SExpr* Array;
		1161	SExpr* Index;
		1162	};
		1163
		1164	/// Simple arithmetic unary operations, e.g. negate and not.
		1165	/// These operations have no side-effects.
		1166	class UnaryOp : public SExpr {
		1167	public:
		1168	UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
		1169	Flags = Op;
		1170	}
		1171
		1172	UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
		1173
		1174	static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
		1175
		1176	TIL_UnaryOpcode unaryOpcode() const {
		1177	return static_cast<TIL_UnaryOpcode>(Flags);
		1178	}
		1179
		1180	SExpr *expr() { return Expr0; }
		1181	const SExpr *expr() const { return Expr0; }
		1182
		1183	template <class V>
		1184	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1185	auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
		1186	return Vs.reduceUnaryOp(*this, Ne);
		1187	}
		1188
		1189	template <class C>
		1190	typename C::CType compare(const UnaryOp* E, C& Cmp) const {
		1191	typename C::CType Ct =
		1192	Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
		1193	if (Cmp.notTrue(Ct))
		1194	return Ct;
		1195	return Cmp.compare(expr(), E->expr());
		1196	}
		1197
		1198	private:
		1199	SExpr* Expr0;
		1200	};
		1201
		1202	/// Simple arithmetic binary operations, e.g. +, -, etc.
		1203	/// These operations have no side effects.
		1204	class BinaryOp : public SExpr {
		1205	public:
		1206	BinaryOp(TIL_BinaryOpcode Op, SExpr E0, SExpr E1)
		1207	: SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
		1208	Flags = Op;
		1209	}
		1210
		1211	BinaryOp(const BinaryOp &B, SExpr E0, SExpr E1)
		1212	: SExpr(B), Expr0(E0), Expr1(E1) {
		1213	Flags = B.Flags;
		1214	}
		1215
		1216	static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
		1217
		1218	TIL_BinaryOpcode binaryOpcode() const {
		1219	return static_cast<TIL_BinaryOpcode>(Flags);
		1220	}
		1221
		1222	SExpr *expr0() { return Expr0; }
		1223	const SExpr *expr0() const { return Expr0; }
		1224
		1225	SExpr *expr1() { return Expr1; }
		1226	const SExpr *expr1() const { return Expr1; }
		1227
		1228	template <class V>
		1229	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1230	auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
		1231	auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
		1232	return Vs.reduceBinaryOp(*this, Ne0, Ne1);
		1233	}
		1234
		1235	template <class C>
		1236	typename C::CType compare(const BinaryOp* E, C& Cmp) const {
		1237	typename C::CType Ct =
		1238	Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
		1239	if (Cmp.notTrue(Ct))
		1240	return Ct;
		1241	Ct = Cmp.compare(expr0(), E->expr0());
		1242	if (Cmp.notTrue(Ct))
		1243	return Ct;
		1244	return Cmp.compare(expr1(), E->expr1());
		1245	}
		1246
		1247	private:
		1248	SExpr* Expr0;
		1249	SExpr* Expr1;
		1250	};
		1251
		1252	/// Cast expressions.
		1253	/// Cast expressions are essentially unary operations, but we treat them
		1254	/// as a distinct AST node because they only change the type of the result.
		1255	class Cast : public SExpr {
		1256	public:
		1257	Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
		1258	Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
		1259
		1260	static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
		1261
		1262	TIL_CastOpcode castOpcode() const {
		1263	return static_cast<TIL_CastOpcode>(Flags);
		1264	}
		1265
		1266	SExpr *expr() { return Expr0; }
		1267	const SExpr *expr() const { return Expr0; }
		1268
		1269	template <class V>
		1270	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1271	auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
		1272	return Vs.reduceCast(*this, Ne);
		1273	}
		1274
		1275	template <class C>
		1276	typename C::CType compare(const Cast* E, C& Cmp) const {
		1277	typename C::CType Ct =
		1278	Cmp.compareIntegers(castOpcode(), E->castOpcode());
		1279	if (Cmp.notTrue(Ct))
		1280	return Ct;
		1281	return Cmp.compare(expr(), E->expr());
		1282	}
		1283
		1284	private:
		1285	SExpr* Expr0;
		1286	};
		1287
		1288	class SCFG;
		1289
		1290	/// Phi Node, for code in SSA form.
		1291	/// Each Phi node has an array of possible values that it can take,
		1292	/// depending on where control flow comes from.
		1293	class Phi : public SExpr {
		1294	public:
		1295	using ValArray = SimpleArray<SExpr *>;
		1296
		1297	// In minimal SSA form, all Phi nodes are MultiVal.
		1298	// During conversion to SSA, incomplete Phi nodes may be introduced, which
		1299	// are later determined to be SingleVal, and are thus redundant.
		1300	enum Status {
		1301	PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
		1302	PH_SingleVal, // Phi node has one distinct value, and can be eliminated
		1303	PH_Incomplete // Phi node is incomplete
		1304	};
		1305
		1306	Phi() : SExpr(COP_Phi) {}
		1307	Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
		1308	Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
		1309
		1310	static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
		1311
		1312	const ValArray &values() const { return Values; }
		1313	ValArray &values() { return Values; }
		1314
		1315	Status status() const { return static_cast<Status>(Flags); }
		1316	void setStatus(Status s) { Flags = s; }
		1317
		1318	/// Return the clang declaration of the variable for this Phi node, if any.
		1319	const ValueDecl *clangDecl() const { return Cvdecl; }
		1320
		1321	/// Set the clang variable associated with this Phi node.
		1322	void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
		1323
		1324	template <class V>
		1325	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1326	typename V::template Container<typename V::R_SExpr>
		1327	Nvs(Vs, Values.size());
		1328
		1329	for (const auto *Val : Values)
		1330	Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
		1331	return Vs.reducePhi(*this, Nvs);
		1332	}
		1333
		1334	template <class C>
		1335	typename C::CType compare(const Phi *E, C &Cmp) const {
		1336	// TODO: implement CFG comparisons
		1337	return Cmp.comparePointers(this, E);
		1338	}
		1339
		1340	private:
		1341	ValArray Values;
		1342	const ValueDecl* Cvdecl = nullptr;
		1343	};
		1344
		1345	/// Base class for basic block terminators: Branch, Goto, and Return.
		1346	class Terminator : public SExpr {
		1347	protected:
		1348	Terminator(TIL_Opcode Op) : SExpr(Op) {}
		1349	Terminator(const SExpr &E) : SExpr(E) {}
		1350
		1351	public:
		1352	static bool classof(const SExpr *E) {
		1353	return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
		1354	}
		1355
		1356	/// Return the list of basic blocks that this terminator can branch to.
		1357	ArrayRef<BasicBlock *> successors();
		1358
		1359	ArrayRef<BasicBlock *> successors() const {
		1360	return const_cast<Terminator*>(this)->successors();
		1361	}
		1362	};
		1363
		1364	/// Jump to another basic block.
		1365	/// A goto instruction is essentially a tail-recursive call into another
		1366	/// block. In addition to the block pointer, it specifies an index into the
		1367	/// phi nodes of that block. The index can be used to retrieve the "arguments"
		1368	/// of the call.
		1369	class Goto : public Terminator {
		1370	public:
		1371	Goto(BasicBlock *B, unsigned I)
		1372	: Terminator(COP_Goto), TargetBlock(B), Index(I) {}
		1373	Goto(const Goto &G, BasicBlock *B, unsigned I)
		1374	: Terminator(COP_Goto), TargetBlock(B), Index(I) {}
		1375
		1376	static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
		1377
		1378	const BasicBlock *targetBlock() const { return TargetBlock; }
		1379	BasicBlock *targetBlock() { return TargetBlock; }
		1380
		1381	/// Returns the index into the
		1382	unsigned index() const { return Index; }
		1383
		1384	/// Return the list of basic blocks that this terminator can branch to.
		1385	ArrayRef<BasicBlock *> successors() { return TargetBlock; }
		1386
		1387	template <class V>
		1388	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1389	BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
		1390	return Vs.reduceGoto(*this, Ntb);
		1391	}
		1392
		1393	template <class C>
		1394	typename C::CType compare(const Goto *E, C &Cmp) const {
		1395	// TODO: implement CFG comparisons
		1396	return Cmp.comparePointers(this, E);
		1397	}
		1398
		1399	private:
		1400	BasicBlock *TargetBlock;
		1401	unsigned Index;
		1402	};
		1403
		1404	/// A conditional branch to two other blocks.
		1405	/// Note that unlike Goto, Branch does not have an index. The target blocks
		1406	/// must be child-blocks, and cannot have Phi nodes.
		1407	class Branch : public Terminator {
		1408	public:
		1409	Branch(SExpr C, BasicBlock T, BasicBlock *E)
		1410	: Terminator(COP_Branch), Condition(C) {
		1411	Branches[0] = T;
		1412	Branches[1] = E;
		1413	}
		1414
		1415	Branch(const Branch &Br, SExpr C, BasicBlock T, BasicBlock *E)
		1416	: Terminator(Br), Condition(C) {
		1417	Branches[0] = T;
		1418	Branches[1] = E;
		1419	}
		1420
		1421	static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
		1422
		1423	const SExpr *condition() const { return Condition; }
		1424	SExpr *condition() { return Condition; }
		1425
		1426	const BasicBlock *thenBlock() const { return Branches[0]; }
		1427	BasicBlock *thenBlock() { return Branches[0]; }
		1428
		1429	const BasicBlock *elseBlock() const { return Branches[1]; }
		1430	BasicBlock *elseBlock() { return Branches[1]; }
		1431
		1432	/// Return the list of basic blocks that this terminator can branch to.
		1433	ArrayRef<BasicBlock *> successors() { return llvm::ArrayRef(Branches); }
		1434
		1435	template <class V>
		1436	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1437	auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
		1438	BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
		1439	BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
		1440	return Vs.reduceBranch(*this, Nc, Ntb, Nte);
		1441	}
		1442
		1443	template <class C>
		1444	typename C::CType compare(const Branch *E, C &Cmp) const {
		1445	// TODO: implement CFG comparisons
		1446	return Cmp.comparePointers(this, E);
		1447	}
		1448
		1449	private:
		1450	SExpr *Condition;
		1451	BasicBlock *Branches[2];
		1452	};
		1453
		1454	/// Return from the enclosing function, passing the return value to the caller.
		1455	/// Only the exit block should end with a return statement.
		1456	class Return : public Terminator {
		1457	public:
		1458	Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
		1459	Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
		1460
		1461	static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
		1462
		1463	/// Return an empty list.
		1464	ArrayRef<BasicBlock *> successors() { return std::nullopt; }
		1465
		1466	SExpr *returnValue() { return Retval; }
		1467	const SExpr *returnValue() const { return Retval; }
		1468
		1469	template <class V>
		1470	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1471	auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
		1472	return Vs.reduceReturn(*this, Ne);
		1473	}
		1474
		1475	template <class C>
		1476	typename C::CType compare(const Return *E, C &Cmp) const {
		1477	return Cmp.compare(Retval, E->Retval);
		1478	}
		1479
		1480	private:
		1481	SExpr* Retval;
		1482	};
		1483
		1484	inline ArrayRef<BasicBlock*> Terminator::successors() {
		1485	switch (opcode()) {
		1486	case COP_Goto: return cast<Goto>(this)->successors();
		1487	case COP_Branch: return cast<Branch>(this)->successors();
		1488	case COP_Return: return cast<Return>(this)->successors();
		1489	default:
		1490	return std::nullopt;
		1491	}
		1492	}
		1493
		1494	/// A basic block is part of an SCFG. It can be treated as a function in
		1495	/// continuation passing style. A block consists of a sequence of phi nodes,
		1496	/// which are "arguments" to the function, followed by a sequence of
		1497	/// instructions. It ends with a Terminator, which is a Branch or Goto to
		1498	/// another basic block in the same SCFG.
		1499	class BasicBlock : public SExpr {
		1500	public:
		1501	using InstrArray = SimpleArray<SExpr *>;
		1502	using BlockArray = SimpleArray<BasicBlock *>;
		1503
		1504	// TopologyNodes are used to overlay tree structures on top of the CFG,
		1505	// such as dominator and postdominator trees. Each block is assigned an
		1506	// ID in the tree according to a depth-first search. Tree traversals are
		1507	// always up, towards the parents.
		1508	struct TopologyNode {
		1509	int NodeID = 0;
		1510
		1511	// Includes this node, so must be > 1.
		1512	int SizeOfSubTree = 0;
		1513
		1514	// Pointer to parent.
		1515	BasicBlock *Parent = nullptr;
		1516
		1517	TopologyNode() = default;
		1518
		1519	bool isParentOf(const TopologyNode& OtherNode) {
		1520	return OtherNode.NodeID > NodeID &&
		1521	OtherNode.NodeID < NodeID + SizeOfSubTree;
		1522	}
		1523
		1524	bool isParentOfOrEqual(const TopologyNode& OtherNode) {
		1525	return OtherNode.NodeID >= NodeID &&
		1526	OtherNode.NodeID < NodeID + SizeOfSubTree;
		1527	}
		1528	};
		1529
		1530	explicit BasicBlock(MemRegionRef A)
		1531	: SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
		1532	BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
		1533	Terminator *T)
		1534	: SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
		1535	Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
		1536
		1537	static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
		1538
		1539	/// Returns the block ID. Every block has a unique ID in the CFG.
		1540	int blockID() const { return BlockID; }
		1541
		1542	/// Returns the number of predecessors.
		1543	size_t numPredecessors() const { return Predecessors.size(); }
		1544	size_t numSuccessors() const { return successors().size(); }
		1545
		1546	const SCFG* cfg() const { return CFGPtr; }
		1547	SCFG* cfg() { return CFGPtr; }
		1548
		1549	const BasicBlock *parent() const { return DominatorNode.Parent; }
		1550	BasicBlock *parent() { return DominatorNode.Parent; }
		1551
		1552	const InstrArray &arguments() const { return Args; }
		1553	InstrArray &arguments() { return Args; }
		1554
		1555	InstrArray &instructions() { return Instrs; }
		1556	const InstrArray &instructions() const { return Instrs; }
		1557
		1558	/// Returns a list of predecessors.
		1559	/// The order of predecessors in the list is important; each phi node has
		1560	/// exactly one argument for each precessor, in the same order.
		1561	BlockArray &predecessors() { return Predecessors; }
		1562	const BlockArray &predecessors() const { return Predecessors; }
		1563
		1564	ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
		1565	ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
		1566
		1567	const Terminator *terminator() const { return TermInstr; }
		1568	Terminator *terminator() { return TermInstr; }
		1569
		1570	void setTerminator(Terminator *E) { TermInstr = E; }
		1571
		1572	bool Dominates(const BasicBlock &Other) {
		1573	return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
		1574	}
		1575
		1576	bool PostDominates(const BasicBlock &Other) {
		1577	return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
		1578	}
		1579
		1580	/// Add a new argument.
		1581	void addArgument(Phi *V) {
		1582	Args.reserveCheck(1, Arena);
		1583	Args.push_back(V);
		1584	}
		1585
		1586	/// Add a new instruction.
		1587	void addInstruction(SExpr *V) {
		1588	Instrs.reserveCheck(1, Arena);
		1589	Instrs.push_back(V);
		1590	}
		1591
		1592	// Add a new predecessor, and return the phi-node index for it.
		1593	// Will add an argument to all phi-nodes, initialized to nullptr.
		1594	unsigned addPredecessor(BasicBlock *Pred);
		1595
		1596	// Reserve space for Nargs arguments.
		1597	void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
		1598
		1599	// Reserve space for Nins instructions.
		1600	void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
		1601
		1602	// Reserve space for NumPreds predecessors, including space in phi nodes.
		1603	void reservePredecessors(unsigned NumPreds);
		1604
		1605	/// Return the index of BB, or Predecessors.size if BB is not a predecessor.
		1606	unsigned findPredecessorIndex(const BasicBlock *BB) const {
		1607	auto I = llvm::find(Predecessors, BB);
		1608	return std::distance(Predecessors.cbegin(), I);
		1609	}
		1610
		1611	template <class V>
		1612	typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
		1613	typename V::template Container<SExpr*> Nas(Vs, Args.size());
		1614	typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
		1615
		1616	// Entering the basic block should do any scope initialization.
		1617	Vs.enterBasicBlock(*this);
		1618
		1619	for (const auto *E : Args) {
		1620	auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
		1621	Nas.push_back(Ne);
		1622	}
		1623	for (const auto *E : Instrs) {
		1624	auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
		1625	Nis.push_back(Ne);
		1626	}
		1627	auto Nt = Vs.traverse(TermInstr, Ctx);
		1628
		1629	// Exiting the basic block should handle any scope cleanup.
		1630	Vs.exitBasicBlock(*this);
		1631
		1632	return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
		1633	}
		1634
		1635	template <class C>
		1636	typename C::CType compare(const BasicBlock *E, C &Cmp) const {
		1637	// TODO: implement CFG comparisons
		1638	return Cmp.comparePointers(this, E);
		1639	}
		1640
		1641	private:
		1642	friend class SCFG;
		1643
		1644	// assign unique ids to all instructions
		1645	unsigned renumberInstrs(unsigned id);
		1646
		1647	unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
		1648	unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
		1649	void computeDominator();
		1650	void computePostDominator();
		1651
		1652	// The arena used to allocate this block.
		1653	MemRegionRef Arena;
		1654
		1655	// The CFG that contains this block.
		1656	SCFG *CFGPtr = nullptr;
		1657
		1658	// Unique ID for this BB in the containing CFG. IDs are in topological order.
		1659	unsigned BlockID : 31;
		1660
		1661	// Bit to determine if a block has been visited during a traversal.
		1662	bool Visited : 1;
		1663
		1664	// Predecessor blocks in the CFG.
		1665	BlockArray Predecessors;
		1666
		1667	// Phi nodes. One argument per predecessor.
		1668	InstrArray Args;
		1669
		1670	// Instructions.
		1671	InstrArray Instrs;
		1672
		1673	// Terminating instruction.
		1674	Terminator *TermInstr = nullptr;
		1675
		1676	// The dominator tree.
		1677	TopologyNode DominatorNode;
		1678
		1679	// The post-dominator tree.
		1680	TopologyNode PostDominatorNode;
		1681	};
		1682
		1683	/// An SCFG is a control-flow graph. It consists of a set of basic blocks,
		1684	/// each of which terminates in a branch to another basic block. There is one
		1685	/// entry point, and one exit point.
		1686	class SCFG : public SExpr {
		1687	public:
		1688	using BlockArray = SimpleArray<BasicBlock *>;
		1689	using iterator = BlockArray::iterator;
		1690	using const_iterator = BlockArray::const_iterator;
		1691
		1692	SCFG(MemRegionRef A, unsigned Nblocks)
		1693	: SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
		1694	Entry = new (A) BasicBlock(A);
		1695	Exit = new (A) BasicBlock(A);
		1696	auto *V = new (A) Phi();
		1697	Exit->addArgument(V);
		1698	Exit->setTerminator(new (A) Return(V));
		1699	add(Entry);
		1700	add(Exit);
		1701	}
		1702
		1703	SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
		1704	: SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
		1705	// TODO: set entry and exit!
		1706	}
		1707
		1708	static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
		1709
		1710	/// Return true if this CFG is valid.
		1711	bool valid() const { return Entry && Exit && Blocks.size() > 0; }
		1712
		1713	/// Return true if this CFG has been normalized.
		1714	/// After normalization, blocks are in topological order, and block and
		1715	/// instruction IDs have been assigned.
		1716	bool normal() const { return Normal; }
		1717
		1718	iterator begin() { return Blocks.begin(); }
		1719	iterator end() { return Blocks.end(); }
		1720
		1721	const_iterator begin() const { return cbegin(); }
		1722	const_iterator end() const { return cend(); }
		1723
		1724	const_iterator cbegin() const { return Blocks.cbegin(); }
		1725	const_iterator cend() const { return Blocks.cend(); }
		1726
		1727	const BasicBlock *entry() const { return Entry; }
		1728	BasicBlock *entry() { return Entry; }
		1729	const BasicBlock *exit() const { return Exit; }
		1730	BasicBlock *exit() { return Exit; }
		1731
		1732	/// Return the number of blocks in the CFG.
		1733	/// Block::blockID() will return a number less than numBlocks();
		1734	size_t numBlocks() const { return Blocks.size(); }
		1735
		1736	/// Return the total number of instructions in the CFG.
		1737	/// This is useful for building instruction side-tables;
		1738	/// A call to SExpr::id() will return a number less than numInstructions().
		1739	unsigned numInstructions() { return NumInstructions; }
		1740
		1741	inline void add(BasicBlock *BB) {
		1742	assert(BB->CFGPtr == nullptr);
		1743	BB->CFGPtr = this;
		1744	Blocks.reserveCheck(1, Arena);
		1745	Blocks.push_back(BB);
		1746	}
		1747
		1748	void setEntry(BasicBlock *BB) { Entry = BB; }
		1749	void setExit(BasicBlock *BB) { Exit = BB; }
		1750
		1751	void computeNormalForm();
		1752
		1753	template <class V>
		1754	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1755	Vs.enterCFG(*this);
		1756	typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
		1757
		1758	for (const auto *B : Blocks) {
		1759	Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
		1760	}
		1761	Vs.exitCFG(*this);
		1762	return Vs.reduceSCFG(*this, Bbs);
		1763	}
		1764
		1765	template <class C>
		1766	typename C::CType compare(const SCFG *E, C &Cmp) const {
		1767	// TODO: implement CFG comparisons
		1768	return Cmp.comparePointers(this, E);
		1769	}
		1770
		1771	private:
		1772	// assign unique ids to all instructions
		1773	void renumberInstrs();
		1774
		1775	MemRegionRef Arena;
		1776	BlockArray Blocks;
		1777	BasicBlock *Entry = nullptr;
		1778	BasicBlock *Exit = nullptr;
		1779	unsigned NumInstructions = 0;
		1780	bool Normal = false;
		1781	};
		1782
		1783	/// An identifier, e.g. 'foo' or 'x'.
		1784	/// This is a pseduo-term; it will be lowered to a variable or projection.
		1785	class Identifier : public SExpr {
		1786	public:
		1787	Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
		1788	Identifier(const Identifier &) = default;
		1789
		1790	static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
		1791
		1792	StringRef name() const { return Name; }
		1793
		1794	template <class V>
		1795	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1796	return Vs.reduceIdentifier(*this);
		1797	}
		1798
		1799	template <class C>
		1800	typename C::CType compare(const Identifier* E, C& Cmp) const {
		1801	return Cmp.compareStrings(name(), E->name());
		1802	}
		1803
		1804	private:
		1805	StringRef Name;
		1806	};
		1807
		1808	/// An if-then-else expression.
		1809	/// This is a pseduo-term; it will be lowered to a branch in a CFG.
		1810	class IfThenElse : public SExpr {
		1811	public:
		1812	IfThenElse(SExpr C, SExpr T, SExpr *E)
		1813	: SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
		1814	IfThenElse(const IfThenElse &I, SExpr C, SExpr T, SExpr *E)
		1815	: SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
		1816
		1817	static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
		1818
		1819	SExpr *condition() { return Condition; } // Address to store to
		1820	const SExpr *condition() const { return Condition; }
		1821
		1822	SExpr *thenExpr() { return ThenExpr; } // Value to store
		1823	const SExpr *thenExpr() const { return ThenExpr; }
		1824
		1825	SExpr *elseExpr() { return ElseExpr; } // Value to store
		1826	const SExpr *elseExpr() const { return ElseExpr; }
		1827
		1828	template <class V>
		1829	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1830	auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
		1831	auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
		1832	auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
		1833	return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
		1834	}
		1835
		1836	template <class C>
		1837	typename C::CType compare(const IfThenElse* E, C& Cmp) const {
		1838	typename C::CType Ct = Cmp.compare(condition(), E->condition());
		1839	if (Cmp.notTrue(Ct))
		1840	return Ct;
		1841	Ct = Cmp.compare(thenExpr(), E->thenExpr());
		1842	if (Cmp.notTrue(Ct))
		1843	return Ct;
		1844	return Cmp.compare(elseExpr(), E->elseExpr());
		1845	}
		1846
		1847	private:
		1848	SExpr* Condition;
		1849	SExpr* ThenExpr;
		1850	SExpr* ElseExpr;
		1851	};
		1852
		1853	/// A let-expression, e.g. let x=t; u.
		1854	/// This is a pseduo-term; it will be lowered to instructions in a CFG.
		1855	class Let : public SExpr {
		1856	public:
		1857	Let(Variable Vd, SExpr Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
		1858	Vd->setKind(Variable::VK_Let);
		1859	}
		1860
		1861	Let(const Let &L, Variable Vd, SExpr Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
		1862	Vd->setKind(Variable::VK_Let);
		1863	}
		1864
		1865	static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
		1866
		1867	Variable *variableDecl() { return VarDecl; }
		1868	const Variable *variableDecl() const { return VarDecl; }
		1869
		1870	SExpr *body() { return Body; }
		1871	const SExpr *body() const { return Body; }
		1872
		1873	template <class V>
		1874	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
		1875	// This is a variable declaration, so traverse the definition.
		1876	auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
		1877	// Tell the rewriter to enter the scope of the let variable.
		1878	Variable Nvd = Vs.enterScope(VarDecl, E0);
		1879	auto E1 = Vs.traverse(Body, Ctx);
		1880	Vs.exitScope(*VarDecl);
		1881	return Vs.reduceLet(*this, Nvd, E1);
		1882	}
		1883
		1884	template <class C>
		1885	typename C::CType compare(const Let* E, C& Cmp) const {
		1886	typename C::CType Ct =
		1887	Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
		1888	if (Cmp.notTrue(Ct))
		1889	return Ct;
		1890	Cmp.enterScope(variableDecl(), E->variableDecl());
		1891	Ct = Cmp.compare(body(), E->body());
		1892	Cmp.leaveScope();
		1893	return Ct;
		1894	}
		1895
		1896	private:
		1897	Variable *VarDecl;
		1898	SExpr* Body;
		1899	};
		1900
		1901	const SExpr getCanonicalVal(const SExpr E);
		1902	SExpr* simplifyToCanonicalVal(SExpr *E);
		1903	void simplifyIncompleteArg(til::Phi *Ph);
		1904
		1905	} // namespace til
		1906	} // namespace threadSafety
		1907
		1908	} // namespace clang
		1909
		1910	#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H

Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

QNX 8.QNX8 LLVM/Clang compiler suite/llvm-build/x86_64/include/clang/Analysis/Analyses/ThreadSafetyTIL.h – Rev 14