ThreadSafetyTIL.h source code [clang_source_code/include/clang/Analysis/Analyses/ThreadSafetyTIL.h]

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/None.h"
54	#include "llvm/ADT/Optional.h"
55	#include "llvm/ADT/StringRef.h"
56	#include "llvm/Support/Casting.h"
57	#include "llvm/Support/raw_ostream.h"
58	#include <algorithm>
59	#include <cassert>
60	#include <cstddef>
61	#include <cstdint>
62	#include <iterator>
63	#include <string>
64	#include <utility>
65
66	namespace clang {
67
68	class CallExpr;
69	class Expr;
70	class Stmt;
71
72	namespace threadSafety {
73	namespace til {
74
75	class BasicBlock;
76
77	/// Enum for the different distinct classes of SExpr
78	enum TIL_Opcode {
79	#define TIL_OPCODE_DEF(X) COP_##X,
80	#include "ThreadSafetyOps.def"
81	#undef TIL_OPCODE_DEF
82	};
83
84	/// Opcode for unary arithmetic operations.
85	enum TIL_UnaryOpcode : unsigned char {
86	UOP_Minus, // -
87	UOP_BitNot, // ~
88	UOP_LogicNot // !
89	};
90
91	/// Opcode for binary arithmetic operations.
92	enum TIL_BinaryOpcode : unsigned char {
93	BOP_Add, // +
94	BOP_Sub, // -
95	BOP_Mul, // *
96	BOP_Div, // /
97	BOP_Rem, // %
98	BOP_Shl, // <<
99	BOP_Shr, // >>
100	BOP_BitAnd, // &
101	BOP_BitXor, // ^
102	BOP_BitOr, // \|
103	BOP_Eq, // ==
104	BOP_Neq, // !=
105	BOP_Lt, // <
106	BOP_Leq, // <=
107	BOP_Cmp, // <=>
108	BOP_LogicAnd, // && (no short-circuit)
109	BOP_LogicOr // \|\| (no short-circuit)
110	};
111
112	/// Opcode for cast operations.
113	enum TIL_CastOpcode : unsigned char {
114	CAST_none = 0,
115
116	// Extend precision of numeric type
117	CAST_extendNum,
118
119	// Truncate precision of numeric type
120	CAST_truncNum,
121
122	// Convert to floating point type
123	CAST_toFloat,
124
125	// Convert to integer type
126	CAST_toInt,
127
128	// Convert smart pointer to pointer (C++ only)
129	CAST_objToPtr
130	};
131
132	const TIL_Opcode COP_Min = COP_Future;
133	const TIL_Opcode COP_Max = COP_Branch;
134	const TIL_UnaryOpcode UOP_Min = UOP_Minus;
135	const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
136	const TIL_BinaryOpcode BOP_Min = BOP_Add;
137	const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
138	const TIL_CastOpcode CAST_Min = CAST_none;
139	const TIL_CastOpcode CAST_Max = CAST_toInt;
140
141	/// Return the name of a unary opcode.
142	StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
143
144	/// Return the name of a binary opcode.
145	StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
146
147	/// ValueTypes are data types that can actually be held in registers.
148	/// All variables and expressions must have a value type.
149	/// Pointer types are further subdivided into the various heap-allocated
150	/// types, such as functions, records, etc.
151	/// Structured types that are passed by value (e.g. complex numbers)
152	/// require special handling; they use BT_ValueRef, and size ST_0.
153	struct ValueType {
154	enum BaseType : unsigned char {
155	BT_Void = 0,
156	BT_Bool,
157	BT_Int,
158	BT_Float,
159	BT_String, // String literals
160	BT_Pointer,
161	BT_ValueRef
162	};
163
164	enum SizeType : unsigned char {
165	ST_0 = 0,
166	ST_1,
167	ST_8,
168	ST_16,
169	ST_32,
170	ST_64,
171	ST_128
172	};
173
174	ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
175	: Base(B), Size(Sz), Signed(S), VectSize(VS) {}
176
177	inline static SizeType getSizeType(unsigned nbytes);
178
179	template <class T>
180	inline static ValueType getValueType();
181
182	BaseType Base;
183	SizeType Size;
184	bool Signed;
185
186	// 0 for scalar, otherwise num elements in vector
187	unsigned char VectSize;
188	};
189
190	inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
191	switch (nbytes) {
192	case 1: return ST_8;
193	case 2: return ST_16;
194	case 4: return ST_32;
195	case 8: return ST_64;
196	case 16: return ST_128;
197	default: return ST_0;
198	}
199	}
200
201	template<>
202	inline ValueType ValueType::getValueType<void>() {
203	return ValueType(BT_Void, ST_0, false, 0);
204	}
205
206	template<>
207	inline ValueType ValueType::getValueType<bool>() {
208	return ValueType(BT_Bool, ST_1, false, 0);
209	}
210
211	template<>
212	inline ValueType ValueType::getValueType<int8_t>() {
213	return ValueType(BT_Int, ST_8, true, 0);
214	}
215
216	template<>
217	inline ValueType ValueType::getValueType<uint8_t>() {
218	return ValueType(BT_Int, ST_8, false, 0);
219	}
220
221	template<>
222	inline ValueType ValueType::getValueType<int16_t>() {
223	return ValueType(BT_Int, ST_16, true, 0);
224	}
225
226	template<>
227	inline ValueType ValueType::getValueType<uint16_t>() {
228	return ValueType(BT_Int, ST_16, false, 0);
229	}
230
231	template<>
232	inline ValueType ValueType::getValueType<int32_t>() {
233	return ValueType(BT_Int, ST_32, true, 0);
234	}
235
236	template<>
237	inline ValueType ValueType::getValueType<uint32_t>() {
238	return ValueType(BT_Int, ST_32, false, 0);
239	}
240
241	template<>
242	inline ValueType ValueType::getValueType<int64_t>() {
243	return ValueType(BT_Int, ST_64, true, 0);
244	}
245
246	template<>
247	inline ValueType ValueType::getValueType<uint64_t>() {
248	return ValueType(BT_Int, ST_64, false, 0);
249	}
250
251	template<>
252	inline ValueType ValueType::getValueType<float>() {
253	return ValueType(BT_Float, ST_32, true, 0);
254	}
255
256	template<>
257	inline ValueType ValueType::getValueType<double>() {
258	return ValueType(BT_Float, ST_64, true, 0);
259	}
260
261	template<>
262	inline ValueType ValueType::getValueType<long double>() {
263	return ValueType(BT_Float, ST_128, true, 0);
264	}
265
266	template<>
267	inline ValueType ValueType::getValueType<StringRef>() {
268	return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
269	}
270
271	template<>
272	inline ValueType ValueType::getValueType<void*>() {
273	return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
274	}
275
276	/// Base class for AST nodes in the typed intermediate language.
277	class SExpr {
278	public:
279	SExpr() = delete;
280
281	TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
282
283	// Subclasses of SExpr must define the following:
284	//
285	// This(const This& E, ...) {
286	// copy constructor: construct copy of E, with some additional arguments.
287	// }
288	//
289	// template <class V>
290	// typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
291	// traverse all subexpressions, following the traversal/rewriter interface.
292	// }
293	//
294	// template <class C> typename C::CType compare(CType* E, C& Cmp) {
295	// compare all subexpressions, following the comparator interface
296	// }
297	void *operator new(size_t S, MemRegionRef &R) {
298	return ::operator new(S, R);
299	}
300
301	/// SExpr objects must be created in an arena.
302	void *operator new(size_t) = delete;
303
304	/// SExpr objects cannot be deleted.
305	// This declaration is public to workaround a gcc bug that breaks building
306	// with REQUIRES_EH=1.
307	void operator delete(void *) = delete;
308
309	/// Returns the instruction ID for this expression.
310	/// All basic block instructions have a unique ID (i.e. virtual register).
311	unsigned id() const { return SExprID; }
312
313	/// Returns the block, if this is an instruction in a basic block,
314	/// otherwise returns null.
315	BasicBlock *block() const { return Block; }
316
317	/// Set the basic block and instruction ID for this expression.
318	void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
319
320	protected:
321	SExpr(TIL_Opcode Op) : Opcode(Op) {}
322	SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
323
324	const unsigned char Opcode;
325	unsigned char Reserved = 0;
326	unsigned short Flags = 0;
327	unsigned SExprID = 0;
328	BasicBlock *Block = nullptr;
329	};
330
331	// Contains various helper functions for SExprs.
332	namespace ThreadSafetyTIL {
333
334	inline bool isTrivial(const SExpr *E) {
335	unsigned Op = E->opcode();
336	return Op == COP_Variable \|\| Op == COP_Literal \|\| Op == COP_LiteralPtr;
337	}
338
339	} // namespace ThreadSafetyTIL
340
341	// Nodes which declare variables
342
343	/// A named variable, e.g. "x".
344	///
345	/// There are two distinct places in which a Variable can appear in the AST.
346	/// A variable declaration introduces a new variable, and can occur in 3 places:
347	/// Let-expressions: (Let (x = t) u)
348	/// Functions: (Function (x : t) u)
349	/// Self-applicable functions (SFunction (x) t)
350	///
351	/// If a variable occurs in any other location, it is a reference to an existing
352	/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
353	/// allocate a separate AST node for variable references; a reference is just a
354	/// pointer to the original declaration.
355	class Variable : public SExpr {
356	public:
357	enum VariableKind {
358	/// Let-variable
359	VK_Let,
360
361	/// Function parameter
362	VK_Fun,
363
364	/// SFunction (self) parameter
365	VK_SFun
366	};
367
368	Variable(StringRef s, SExpr *D = nullptr)
369	: SExpr(COP_Variable), Name(s), Definition(D) {
370	Flags = VK_Let;
371	}
372
373	Variable(SExpr D, const ValueDecl Cvd = nullptr)
374	: SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
375	Definition(D), Cvdecl(Cvd) {
376	Flags = VK_Let;
377	}
378
379	Variable(const Variable &Vd, SExpr *D) // rewrite constructor
380	: SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
381	Flags = Vd.kind();
382	}
383
384	static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
385
386	/// Return the kind of variable (let, function param, or self)
387	VariableKind kind() const { return static_cast<VariableKind>(Flags); }
388
389	/// Return the name of the variable, if any.
390	StringRef name() const { return Name; }
391
392	/// Return the clang declaration for this variable, if any.
393	const ValueDecl *clangDecl() const { return Cvdecl; }
394
395	/// Return the definition of the variable.
396	/// For let-vars, this is the setting expression.
397	/// For function and self parameters, it is the type of the variable.
398	SExpr *definition() { return Definition; }
399	const SExpr *definition() const { return Definition; }
400
401	void setName(StringRef S) { Name = S; }
402	void setKind(VariableKind K) { Flags = K; }
403	void setDefinition(SExpr *E) { Definition = E; }
404	void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
405
406	template <class V>
407	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
408	// This routine is only called for variable references.
409	return Vs.reduceVariableRef(this);
410	}
411
412	template <class C>
413	typename C::CType compare(const Variable* E, C& Cmp) const {
414	return Cmp.compareVariableRefs(this, E);
415	}
416
417	private:
418	friend class BasicBlock;
419	friend class Function;
420	friend class Let;
421	friend class SFunction;
422
423	// The name of the variable.
424	StringRef Name;
425
426	// The TIL type or definition.
427	SExpr *Definition;
428
429	// The clang declaration for this variable.
430	const ValueDecl *Cvdecl = nullptr;
431	};
432
433	/// Placeholder for an expression that has not yet been created.
434	/// Used to implement lazy copy and rewriting strategies.
435	class Future : public SExpr {
436	public:
437	enum FutureStatus {
438	FS_pending,
439	FS_evaluating,
440	FS_done
441	};
442
443	Future() : SExpr(COP_Future) {}
444	virtual ~Future() = delete;
445
446	static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
447
448	// A lazy rewriting strategy should subclass Future and override this method.
449	virtual SExpr *compute() { return nullptr; }
450
451	// Return the result of this future if it exists, otherwise return null.
452	SExpr *maybeGetResult() const { return Result; }
453
454	// Return the result of this future; forcing it if necessary.
455	SExpr *result() {
456	switch (Status) {
457	case FS_pending:
458	return force();
459	case FS_evaluating:
460	return nullptr; // infinite loop; illegal recursion.
461	case FS_done:
462	return Result;
463	}
464	}
465
466	template <class V>
467	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
468	(0) . __assert_fail ("Result && \"Cannot traverse Future that has not been forced.\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h", 468, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Result && "Cannot traverse Future that has not been forced.");
469	return Vs.traverse(Result, Ctx);
470	}
471
472	template <class C>
473	typename C::CType compare(const Future* E, C& Cmp) const {
474	if (!Result \|\| !E->Result)
475	return Cmp.comparePointers(this, E);
476	return Cmp.compare(Result, E->Result);
477	}
478
479	private:
480	SExpr* force();
481
482	FutureStatus Status = FS_pending;
483	SExpr *Result = nullptr;
484	};
485
486	/// Placeholder for expressions that cannot be represented in the TIL.
487	class Undefined : public SExpr {
488	public:
489	Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
490	Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
491
492	static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
493
494	template <class V>
495	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
496	return Vs.reduceUndefined(*this);
497	}
498
499	template <class C>
500	typename C::CType compare(const Undefined* E, C& Cmp) const {
501	return Cmp.trueResult();
502	}
503
504	private:
505	const Stmt *Cstmt;
506	};
507
508	/// Placeholder for a wildcard that matches any other expression.
509	class Wildcard : public SExpr {
510	public:
511	Wildcard() : SExpr(COP_Wildcard) {}
512	Wildcard(const Wildcard &) = default;
513
514	static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
515
516	template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
517	return Vs.reduceWildcard(*this);
518	}
519
520	template <class C>
521	typename C::CType compare(const Wildcard* E, C& Cmp) const {
522	return Cmp.trueResult();
523	}
524	};
525
526	template <class T> class LiteralT;
527
528	// Base class for literal values.
529	class Literal : public SExpr {
530	public:
531	Literal(const Expr *C)
532	: SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
533	Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
534	Literal(const Literal &) = default;
535
536	static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
537
538	// The clang expression for this literal.
539	const Expr *clangExpr() const { return Cexpr; }
540
541	ValueType valueType() const { return ValType; }
542
543	template<class T> const LiteralT<T>& as() const {
544	return static_cast<const LiteralT<T>>(this);
545	}
546	template<class T> LiteralT<T>& as() {
547	return static_cast<LiteralT<T>>(this);
548	}
549
550	template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
551
552	template <class C>
553	typename C::CType compare(const Literal* E, C& Cmp) const {
554	// TODO: defer actual comparison to LiteralT
555	return Cmp.trueResult();
556	}
557
558	private:
559	const ValueType ValType;
560	const Expr *Cexpr = nullptr;
561	};
562
563	// Derived class for literal values, which stores the actual value.
564	template<class T>
565	class LiteralT : public Literal {
566	public:
567	LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
568	LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
569
570	T value() const { return Val;}
571	T& value() { return Val; }
572
573	private:
574	T Val;
575	};
576
577	template <class V>
578	typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
579	if (Cexpr)
580	return Vs.reduceLiteral(*this);
581
582	switch (ValType.Base) {
583	case ValueType::BT_Void:
584	break;
585	case ValueType::BT_Bool:
586	return Vs.reduceLiteralT(as<bool>());
587	case ValueType::BT_Int: {
588	switch (ValType.Size) {
589	case ValueType::ST_8:
590	if (ValType.Signed)
591	return Vs.reduceLiteralT(as<int8_t>());
592	else
593	return Vs.reduceLiteralT(as<uint8_t>());
594	case ValueType::ST_16:
595	if (ValType.Signed)
596	return Vs.reduceLiteralT(as<int16_t>());
597	else
598	return Vs.reduceLiteralT(as<uint16_t>());
599	case ValueType::ST_32:
600	if (ValType.Signed)
601	return Vs.reduceLiteralT(as<int32_t>());
602	else
603	return Vs.reduceLiteralT(as<uint32_t>());
604	case ValueType::ST_64:
605	if (ValType.Signed)
606	return Vs.reduceLiteralT(as<int64_t>());
607	else
608	return Vs.reduceLiteralT(as<uint64_t>());
609	default:
610	break;
611	}
612	}
613	case ValueType::BT_Float: {
614	switch (ValType.Size) {
615	case ValueType::ST_32:
616	return Vs.reduceLiteralT(as<float>());
617	case ValueType::ST_64:
618	return Vs.reduceLiteralT(as<double>());
619	default:
620	break;
621	}
622	}
623	case ValueType::BT_String:
624	return Vs.reduceLiteralT(as<StringRef>());
625	case ValueType::BT_Pointer:
626	return Vs.reduceLiteralT(as<void*>());
627	case ValueType::BT_ValueRef:
628	break;
629	}
630	return Vs.reduceLiteral(*this);
631	}
632
633	/// A Literal pointer to an object allocated in memory.
634	/// At compile time, pointer literals are represented by symbolic names.
635	class LiteralPtr : public SExpr {
636	public:
637	LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
638	LiteralPtr(const LiteralPtr &) = default;
639
640	static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
641
642	// The clang declaration for the value that this pointer points to.
643	const ValueDecl *clangDecl() const { return Cvdecl; }
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	return Cmp.comparePointers(Cvdecl, E->Cvdecl);
653	}
654
655	private:
656	const ValueDecl *Cvdecl;
657	};
658
659	/// A function -- a.k.a. lambda abstraction.
660	/// Functions with multiple arguments are created by currying,
661	/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
662	class Function : public SExpr {
663	public:
664	Function(Variable Vd, SExpr Bd)
665	: SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
666	Vd->setKind(Variable::VK_Fun);
667	}
668
669	Function(const Function &F, Variable Vd, SExpr Bd) // rewrite constructor
670	: SExpr(F), VarDecl(Vd), Body(Bd) {
671	Vd->setKind(Variable::VK_Fun);
672	}
673
674	static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
675
676	Variable *variableDecl() { return VarDecl; }
677	const Variable *variableDecl() const { return VarDecl; }
678
679	SExpr *body() { return Body; }
680	const SExpr *body() const { return Body; }
681
682	template <class V>
683	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
684	// This is a variable declaration, so traverse the definition.
685	auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
686	// Tell the rewriter to enter the scope of the function.
687	Variable Nvd = Vs.enterScope(VarDecl, E0);
688	auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
689	Vs.exitScope(*VarDecl);
690	return Vs.reduceFunction(*this, Nvd, E1);
691	}
692
693	template <class C>
694	typename C::CType compare(const Function* E, C& Cmp) const {
695	typename C::CType Ct =
696	Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
697	if (Cmp.notTrue(Ct))
698	return Ct;
699	Cmp.enterScope(variableDecl(), E->variableDecl());
700	Ct = Cmp.compare(body(), E->body());
701	Cmp.leaveScope();
702	return Ct;
703	}
704
705	private:
706	Variable *VarDecl;
707	SExpr* Body;
708	};
709
710	/// A self-applicable function.
711	/// A self-applicable function can be applied to itself. It's useful for
712	/// implementing objects and late binding.
713	class SFunction : public SExpr {
714	public:
715	SFunction(Variable Vd, SExpr B)
716	: SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
717	Definition == nullptr", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h", 717, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Vd->Definition == nullptr);
718	Vd->setKind(Variable::VK_SFun);
719	Vd->Definition = this;
720	}
721
722	SFunction(const SFunction &F, Variable Vd, SExpr B) // rewrite constructor
723	: SExpr(F), VarDecl(Vd), Body(B) {
724	Definition == nullptr", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h", 724, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Vd->Definition == nullptr);
725	Vd->setKind(Variable::VK_SFun);
726	Vd->Definition = this;
727	}
728
729	static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
730
731	Variable *variableDecl() { return VarDecl; }
732	const Variable *variableDecl() const { return VarDecl; }
733
734	SExpr *body() { return Body; }
735	const SExpr *body() const { return Body; }
736
737	template <class V>
738	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
739	// A self-variable points to the SFunction itself.
740	// A rewrite must introduce the variable with a null definition, and update
741	// it after 'this' has been rewritten.
742	Variable Nvd = Vs.enterScope(VarDecl, nullptr);
743	auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
744	Vs.exitScope(*VarDecl);
745	// A rewrite operation will call SFun constructor to set Vvd->Definition.
746	return Vs.reduceSFunction(*this, Nvd, E1);
747	}
748
749	template <class C>
750	typename C::CType compare(const SFunction* E, C& Cmp) const {
751	Cmp.enterScope(variableDecl(), E->variableDecl());
752	typename C::CType Ct = Cmp.compare(body(), E->body());
753	Cmp.leaveScope();
754	return Ct;
755	}
756
757	private:
758	Variable *VarDecl;
759	SExpr* Body;
760	};
761
762	/// A block of code -- e.g. the body of a function.
763	class Code : public SExpr {
764	public:
765	Code(SExpr T, SExpr B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
766	Code(const Code &C, SExpr T, SExpr B) // rewrite constructor
767	: SExpr(C), ReturnType(T), Body(B) {}
768
769	static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
770
771	SExpr *returnType() { return ReturnType; }
772	const SExpr *returnType() const { return ReturnType; }
773
774	SExpr *body() { return Body; }
775	const SExpr *body() const { return Body; }
776
777	template <class V>
778	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
779	auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
780	auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
781	return Vs.reduceCode(*this, Nt, Nb);
782	}
783
784	template <class C>
785	typename C::CType compare(const Code* E, C& Cmp) const {
786	typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
787	if (Cmp.notTrue(Ct))
788	return Ct;
789	return Cmp.compare(body(), E->body());
790	}
791
792	private:
793	SExpr* ReturnType;
794	SExpr* Body;
795	};
796
797	/// A typed, writable location in memory
798	class Field : public SExpr {
799	public:
800	Field(SExpr R, SExpr B) : SExpr(COP_Field), Range(R), Body(B) {}
801	Field(const Field &C, SExpr R, SExpr B) // rewrite constructor
802	: SExpr(C), Range(R), Body(B) {}
803
804	static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
805
806	SExpr *range() { return Range; }
807	const SExpr *range() const { return Range; }
808
809	SExpr *body() { return Body; }
810	const SExpr *body() const { return Body; }
811
812	template <class V>
813	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
814	auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
815	auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
816	return Vs.reduceField(*this, Nr, Nb);
817	}
818
819	template <class C>
820	typename C::CType compare(const Field* E, C& Cmp) const {
821	typename C::CType Ct = Cmp.compare(range(), E->range());
822	if (Cmp.notTrue(Ct))
823	return Ct;
824	return Cmp.compare(body(), E->body());
825	}
826
827	private:
828	SExpr* Range;
829	SExpr* Body;
830	};
831
832	/// Apply an argument to a function.
833	/// Note that this does not actually call the function. Functions are curried,
834	/// so this returns a closure in which the first parameter has been applied.
835	/// Once all parameters have been applied, Call can be used to invoke the
836	/// function.
837	class Apply : public SExpr {
838	public:
839	Apply(SExpr F, SExpr A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
840	Apply(const Apply &A, SExpr F, SExpr Ar) // rewrite constructor
841	: SExpr(A), Fun(F), Arg(Ar) {}
842
843	static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
844
845	SExpr *fun() { return Fun; }
846	const SExpr *fun() const { return Fun; }
847
848	SExpr *arg() { return Arg; }
849	const SExpr *arg() const { return Arg; }
850
851	template <class V>
852	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
853	auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
854	auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
855	return Vs.reduceApply(*this, Nf, Na);
856	}
857
858	template <class C>
859	typename C::CType compare(const Apply* E, C& Cmp) const {
860	typename C::CType Ct = Cmp.compare(fun(), E->fun());
861	if (Cmp.notTrue(Ct))
862	return Ct;
863	return Cmp.compare(arg(), E->arg());
864	}
865
866	private:
867	SExpr* Fun;
868	SExpr* Arg;
869	};
870
871	/// Apply a self-argument to a self-applicable function.
872	class SApply : public SExpr {
873	public:
874	SApply(SExpr Sf, SExpr A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
875	SApply(SApply &A, SExpr Sf, SExpr Ar = nullptr) // rewrite constructor
876	: SExpr(A), Sfun(Sf), Arg(Ar) {}
877
878	static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
879
880	SExpr *sfun() { return Sfun; }
881	const SExpr *sfun() const { return Sfun; }
882
883	SExpr *arg() { return Arg ? Arg : Sfun; }
884	const SExpr *arg() const { return Arg ? Arg : Sfun; }
885
886	bool isDelegation() const { return Arg != nullptr; }
887
888	template <class V>
889	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
890	auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
891	typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
892	: nullptr;
893	return Vs.reduceSApply(*this, Nf, Na);
894	}
895
896	template <class C>
897	typename C::CType compare(const SApply* E, C& Cmp) const {
898	typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899	if (Cmp.notTrue(Ct) \|\| (!arg() && !E->arg()))
900	return Ct;
901	return Cmp.compare(arg(), E->arg());
902	}
903
904	private:
905	SExpr* Sfun;
906	SExpr* Arg;
907	};
908
909	/// Project a named slot from a C++ struct or class.
910	class Project : public SExpr {
911	public:
912	Project(SExpr R, const ValueDecl Cvd)
913	: SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
914	(0) . __assert_fail ("Cvd && \"ValueDecl must not be null\"", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h", 914, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">assert(Cvd && "ValueDecl must not be null");
915	}
916
917	static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
918
919	SExpr *record() { return Rec; }
920	const SExpr *record() const { return Rec; }
921
922	const ValueDecl *clangDecl() const { return Cvdecl; }
923
924	bool isArrow() const { return (Flags & 0x01) != 0; }
925
926	void setArrow(bool b) {
927	if (b) Flags \|= 0x01;
928	else Flags &= 0xFFFE;
929	}
930
931	StringRef slotName() const {
932	if (Cvdecl->getDeclName().isIdentifier())
933	return Cvdecl->getName();
934	if (!SlotName) {
935	SlotName = "";
936	llvm::raw_string_ostream OS(*SlotName);
937	Cvdecl->printName(OS);
938	}
939	return *SlotName;
940	}
941
942	template <class V>
943	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
944	auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
945	return Vs.reduceProject(*this, Nr);
946	}
947
948	template <class C>
949	typename C::CType compare(const Project* E, C& Cmp) const {
950	typename C::CType Ct = Cmp.compare(record(), E->record());
951	if (Cmp.notTrue(Ct))
952	return Ct;
953	return Cmp.comparePointers(Cvdecl, E->Cvdecl);
954	}
955
956	private:
957	SExpr* Rec;
958	mutable llvm::Optional<std::string> SlotName;
959	const ValueDecl *Cvdecl;
960	};
961
962	/// Call a function (after all arguments have been applied).
963	class Call : public SExpr {
964	public:
965	Call(SExpr T, const CallExpr Ce = nullptr)
966	: SExpr(COP_Call), Target(T), Cexpr(Ce) {}
967	Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
968
969	static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
970
971	SExpr *target() { return Target; }
972	const SExpr *target() const { return Target; }
973
974	const CallExpr *clangCallExpr() const { return Cexpr; }
975
976	template <class V>
977	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
978	auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
979	return Vs.reduceCall(*this, Nt);
980	}
981
982	template <class C>
983	typename C::CType compare(const Call* E, C& Cmp) const {
984	return Cmp.compare(target(), E->target());
985	}
986
987	private:
988	SExpr* Target;
989	const CallExpr *Cexpr;
990	};
991
992	/// Allocate memory for a new value on the heap or stack.
993	class Alloc : public SExpr {
994	public:
995	enum AllocKind {
996	AK_Stack,
997	AK_Heap
998	};
999
1000	Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1001	Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1002
1003	static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1004
1005	AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1006
1007	SExpr *dataType() { return Dtype; }
1008	const SExpr *dataType() const { return Dtype; }
1009
1010	template <class V>
1011	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1012	auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1013	return Vs.reduceAlloc(*this, Nd);
1014	}
1015
1016	template <class C>
1017	typename C::CType compare(const Alloc* E, C& Cmp) const {
1018	typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1019	if (Cmp.notTrue(Ct))
1020	return Ct;
1021	return Cmp.compare(dataType(), E->dataType());
1022	}
1023
1024	private:
1025	SExpr* Dtype;
1026	};
1027
1028	/// Load a value from memory.
1029	class Load : public SExpr {
1030	public:
1031	Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1032	Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1033
1034	static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1035
1036	SExpr *pointer() { return Ptr; }
1037	const SExpr *pointer() const { return Ptr; }
1038
1039	template <class V>
1040	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1041	auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1042	return Vs.reduceLoad(*this, Np);
1043	}
1044
1045	template <class C>
1046	typename C::CType compare(const Load* E, C& Cmp) const {
1047	return Cmp.compare(pointer(), E->pointer());
1048	}
1049
1050	private:
1051	SExpr* Ptr;
1052	};
1053
1054	/// Store a value to memory.
1055	/// The destination is a pointer to a field, the source is the value to store.
1056	class Store : public SExpr {
1057	public:
1058	Store(SExpr P, SExpr V) : SExpr(COP_Store), Dest(P), Source(V) {}
1059	Store(const Store &S, SExpr P, SExpr V) : SExpr(S), Dest(P), Source(V) {}
1060
1061	static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1062
1063	SExpr *destination() { return Dest; } // Address to store to
1064	const SExpr *destination() const { return Dest; }
1065
1066	SExpr *source() { return Source; } // Value to store
1067	const SExpr *source() const { return Source; }
1068
1069	template <class V>
1070	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1071	auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
1072	auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1073	return Vs.reduceStore(*this, Np, Nv);
1074	}
1075
1076	template <class C>
1077	typename C::CType compare(const Store* E, C& Cmp) const {
1078	typename C::CType Ct = Cmp.compare(destination(), E->destination());
1079	if (Cmp.notTrue(Ct))
1080	return Ct;
1081	return Cmp.compare(source(), E->source());
1082	}
1083
1084	private:
1085	SExpr* Dest;
1086	SExpr* Source;
1087	};
1088
1089	/// If p is a reference to an array, then p[i] is a reference to the i'th
1090	/// element of the array.
1091	class ArrayIndex : public SExpr {
1092	public:
1093	ArrayIndex(SExpr A, SExpr N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1094	ArrayIndex(const ArrayIndex &E, SExpr A, SExpr N)
1095	: SExpr(E), Array(A), Index(N) {}
1096
1097	static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1098
1099	SExpr *array() { return Array; }
1100	const SExpr *array() const { return Array; }
1101
1102	SExpr *index() { return Index; }
1103	const SExpr *index() const { return Index; }
1104
1105	template <class V>
1106	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1107	auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1108	auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1109	return Vs.reduceArrayIndex(*this, Na, Ni);
1110	}
1111
1112	template <class C>
1113	typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1114	typename C::CType Ct = Cmp.compare(array(), E->array());
1115	if (Cmp.notTrue(Ct))
1116	return Ct;
1117	return Cmp.compare(index(), E->index());
1118	}
1119
1120	private:
1121	SExpr* Array;
1122	SExpr* Index;
1123	};
1124
1125	/// Pointer arithmetic, restricted to arrays only.
1126	/// If p is a reference to an array, then p + n, where n is an integer, is
1127	/// a reference to a subarray.
1128	class ArrayAdd : public SExpr {
1129	public:
1130	ArrayAdd(SExpr A, SExpr N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1131	ArrayAdd(const ArrayAdd &E, SExpr A, SExpr N)
1132	: SExpr(E), Array(A), Index(N) {}
1133
1134	static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1135
1136	SExpr *array() { return Array; }
1137	const SExpr *array() const { return Array; }
1138
1139	SExpr *index() { return Index; }
1140	const SExpr *index() const { return Index; }
1141
1142	template <class V>
1143	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1144	auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1145	auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1146	return Vs.reduceArrayAdd(*this, Na, Ni);
1147	}
1148
1149	template <class C>
1150	typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1151	typename C::CType Ct = Cmp.compare(array(), E->array());
1152	if (Cmp.notTrue(Ct))
1153	return Ct;
1154	return Cmp.compare(index(), E->index());
1155	}
1156
1157	private:
1158	SExpr* Array;
1159	SExpr* Index;
1160	};
1161
1162	/// Simple arithmetic unary operations, e.g. negate and not.
1163	/// These operations have no side-effects.
1164	class UnaryOp : public SExpr {
1165	public:
1166	UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1167	Flags = Op;
1168	}
1169
1170	UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1171
1172	static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1173
1174	TIL_UnaryOpcode unaryOpcode() const {
1175	return static_cast<TIL_UnaryOpcode>(Flags);
1176	}
1177
1178	SExpr *expr() { return Expr0; }
1179	const SExpr *expr() const { return Expr0; }
1180
1181	template <class V>
1182	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1183	auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1184	return Vs.reduceUnaryOp(*this, Ne);
1185	}
1186
1187	template <class C>
1188	typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1189	typename C::CType Ct =
1190	Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1191	if (Cmp.notTrue(Ct))
1192	return Ct;
1193	return Cmp.compare(expr(), E->expr());
1194	}
1195
1196	private:
1197	SExpr* Expr0;
1198	};
1199
1200	/// Simple arithmetic binary operations, e.g. +, -, etc.
1201	/// These operations have no side effects.
1202	class BinaryOp : public SExpr {
1203	public:
1204	BinaryOp(TIL_BinaryOpcode Op, SExpr E0, SExpr E1)
1205	: SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1206	Flags = Op;
1207	}
1208
1209	BinaryOp(const BinaryOp &B, SExpr E0, SExpr E1)
1210	: SExpr(B), Expr0(E0), Expr1(E1) {
1211	Flags = B.Flags;
1212	}
1213
1214	static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1215
1216	TIL_BinaryOpcode binaryOpcode() const {
1217	return static_cast<TIL_BinaryOpcode>(Flags);
1218	}
1219
1220	SExpr *expr0() { return Expr0; }
1221	const SExpr *expr0() const { return Expr0; }
1222
1223	SExpr *expr1() { return Expr1; }
1224	const SExpr *expr1() const { return Expr1; }
1225
1226	template <class V>
1227	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1228	auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1229	auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1230	return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1231	}
1232
1233	template <class C>
1234	typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1235	typename C::CType Ct =
1236	Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1237	if (Cmp.notTrue(Ct))
1238	return Ct;
1239	Ct = Cmp.compare(expr0(), E->expr0());
1240	if (Cmp.notTrue(Ct))
1241	return Ct;
1242	return Cmp.compare(expr1(), E->expr1());
1243	}
1244
1245	private:
1246	SExpr* Expr0;
1247	SExpr* Expr1;
1248	};
1249
1250	/// Cast expressions.
1251	/// Cast expressions are essentially unary operations, but we treat them
1252	/// as a distinct AST node because they only change the type of the result.
1253	class Cast : public SExpr {
1254	public:
1255	Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1256	Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1257
1258	static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1259
1260	TIL_CastOpcode castOpcode() const {
1261	return static_cast<TIL_CastOpcode>(Flags);
1262	}
1263
1264	SExpr *expr() { return Expr0; }
1265	const SExpr *expr() const { return Expr0; }
1266
1267	template <class V>
1268	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1269	auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1270	return Vs.reduceCast(*this, Ne);
1271	}
1272
1273	template <class C>
1274	typename C::CType compare(const Cast* E, C& Cmp) const {
1275	typename C::CType Ct =
1276	Cmp.compareIntegers(castOpcode(), E->castOpcode());
1277	if (Cmp.notTrue(Ct))
1278	return Ct;
1279	return Cmp.compare(expr(), E->expr());
1280	}
1281
1282	private:
1283	SExpr* Expr0;
1284	};
1285
1286	class SCFG;
1287
1288	/// Phi Node, for code in SSA form.
1289	/// Each Phi node has an array of possible values that it can take,
1290	/// depending on where control flow comes from.
1291	class Phi : public SExpr {
1292	public:
1293	using ValArray = SimpleArray<SExpr *>;
1294
1295	// In minimal SSA form, all Phi nodes are MultiVal.
1296	// During conversion to SSA, incomplete Phi nodes may be introduced, which
1297	// are later determined to be SingleVal, and are thus redundant.
1298	enum Status {
1299	PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
1300	PH_SingleVal, // Phi node has one distinct value, and can be eliminated
1301	PH_Incomplete // Phi node is incomplete
1302	};
1303
1304	Phi() : SExpr(COP_Phi) {}
1305	Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1306	Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1307
1308	static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1309
1310	const ValArray &values() const { return Values; }
1311	ValArray &values() { return Values; }
1312
1313	Status status() const { return static_cast<Status>(Flags); }
1314	void setStatus(Status s) { Flags = s; }
1315
1316	/// Return the clang declaration of the variable for this Phi node, if any.
1317	const ValueDecl *clangDecl() const { return Cvdecl; }
1318
1319	/// Set the clang variable associated with this Phi node.
1320	void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
1321
1322	template <class V>
1323	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1324	typename V::template Container<typename V::R_SExpr>
1325	Nvs(Vs, Values.size());
1326
1327	for (const auto *Val : Values)
1328	Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1329	return Vs.reducePhi(*this, Nvs);
1330	}
1331
1332	template <class C>
1333	typename C::CType compare(const Phi *E, C &Cmp) const {
1334	// TODO: implement CFG comparisons
1335	return Cmp.comparePointers(this, E);
1336	}
1337
1338	private:
1339	ValArray Values;
1340	const ValueDecl* Cvdecl = nullptr;
1341	};
1342
1343	/// Base class for basic block terminators: Branch, Goto, and Return.
1344	class Terminator : public SExpr {
1345	protected:
1346	Terminator(TIL_Opcode Op) : SExpr(Op) {}
1347	Terminator(const SExpr &E) : SExpr(E) {}
1348
1349	public:
1350	static bool classof(const SExpr *E) {
1351	return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1352	}
1353
1354	/// Return the list of basic blocks that this terminator can branch to.
1355	ArrayRef<BasicBlock *> successors();
1356
1357	ArrayRef<BasicBlock *> successors() const {
1358	return const_cast<Terminator*>(this)->successors();
1359	}
1360	};
1361
1362	/// Jump to another basic block.
1363	/// A goto instruction is essentially a tail-recursive call into another
1364	/// block. In addition to the block pointer, it specifies an index into the
1365	/// phi nodes of that block. The index can be used to retrieve the "arguments"
1366	/// of the call.
1367	class Goto : public Terminator {
1368	public:
1369	Goto(BasicBlock *B, unsigned I)
1370	: Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1371	Goto(const Goto &G, BasicBlock *B, unsigned I)
1372	: Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1373
1374	static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1375
1376	const BasicBlock *targetBlock() const { return TargetBlock; }
1377	BasicBlock *targetBlock() { return TargetBlock; }
1378
1379	/// Returns the index into the
1380	unsigned index() const { return Index; }
1381
1382	/// Return the list of basic blocks that this terminator can branch to.
1383	ArrayRef<BasicBlock *> successors() { return TargetBlock; }
1384
1385	template <class V>
1386	typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1387	BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1388	return Vs.reduceGoto(*this, Ntb);
1389	}
1390
1391	template <class C>
1392	typename C::CType compare(const Goto *E, C &Cmp) const {
1393	// TODO: implement CFG comparisons
1394	return Cmp.comparePointers(this, E);
1395	}
1396
1397	private:
1398	BasicBlock *TargetBlock;
1399	unsigned Index;
1400	};
1401
1402	/// A conditional branch to two other blocks.
1403	/// Note that unlike Goto, Branch does not have an index. The target blocks
1404	/// must be child-blocks, and cannot have Phi nodes.
1405	class Branch : public Terminator {
1406	public:
1407	Branch(SExpr C, BasicBlock T, BasicBlock *E)
1408	: Terminator(COP_Branch), Condition(C) {
1409	Branches[0] = T;
1410	Branches[1] = E;
1411	}
1412
1413	Branch(const Branch &Br, SExpr C, BasicBlock T, BasicBlock *E)
1414	: Terminator(Br), Condition(C) {
1415	Branches[0] = T;
1416	Branches[1] = E;
1417	}
1418
1419	static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1420
1421	const SExpr *condition() const { return Condition; }
1422	SExpr *condition() { return Condition; }
1423
1424	const BasicBlock *thenBlock() const { return Branches[0]; }
1425	BasicBlock *thenBlock() { return Branches[0]; }
1426
1427	const BasicBlock *elseBlock() const { return Branches[1]; }
1428	BasicBlock *elseBlock() { return Branches[1]; }
1429
1430	/// Return the list of basic blocks that this terminator can branch to.
1431	ArrayRef<BasicBlock*> successors() {
1432	return llvm::makeArrayRef(Branches);
1433	}
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 None; }
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 None;
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 = std::find(Predecessors.cbegin(), Predecessors.cend(), 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	CFGPtr == nullptr", "/home/seafit/code_projects/clang_source/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h", 1742, __PRETTY_FUNCTION__))" file_link="../../../../../include/assert.h.html#88" macro="true">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
1911