summaryrefslogtreecommitdiffstats
path: root/contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h')
-rw-r--r--contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h1813
1 files changed, 1813 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
new file mode 100644
index 0000000..8e4299e
--- /dev/null
+++ b/contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
@@ -0,0 +1,1813 @@
+//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT in the llvm repository for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a simple Typed Intermediate Language, or TIL, that is used
+// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended
+// to be largely independent of clang, in the hope that the analysis can be
+// reused for other non-C++ languages. All dependencies on clang/llvm should
+// go in ThreadSafetyUtil.h.
+//
+// Thread safety analysis works by comparing mutex expressions, e.g.
+//
+// class A { Mutex mu; int dat GUARDED_BY(this->mu); }
+// class B { A a; }
+//
+// void foo(B* b) {
+// (*b).a.mu.lock(); // locks (*b).a.mu
+// b->a.dat = 0; // substitute &b->a for 'this';
+// // requires lock on (&b->a)->mu
+// (b->a.mu).unlock(); // unlocks (b->a.mu)
+// }
+//
+// As illustrated by the above example, clang Exprs are not well-suited to
+// represent mutex expressions directly, since there is no easy way to compare
+// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs
+// into a simple intermediate language (IL). The IL supports:
+//
+// (1) comparisons for semantic equality of expressions
+// (2) SSA renaming of variables
+// (3) wildcards and pattern matching over expressions
+// (4) hash-based expression lookup
+//
+// The TIL is currently very experimental, is intended only for use within
+// the thread safety analysis, and is subject to change without notice.
+// After the API stabilizes and matures, it may be appropriate to make this
+// more generally available to other analyses.
+//
+// UNDER CONSTRUCTION. USE AT YOUR OWN RISK.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H
+#define LLVM_CLANG_THREAD_SAFETY_TIL_H
+
+// All clang include dependencies for this file must be put in
+// ThreadSafetyUtil.h.
+#include "ThreadSafetyUtil.h"
+
+#include <stdint.h>
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <utility>
+
+
+namespace clang {
+namespace threadSafety {
+namespace til {
+
+
+enum TIL_Opcode {
+#define TIL_OPCODE_DEF(X) COP_##X,
+#include "ThreadSafetyOps.def"
+#undef TIL_OPCODE_DEF
+};
+
+enum TIL_UnaryOpcode : unsigned char {
+ UOP_Minus, // -
+ UOP_BitNot, // ~
+ UOP_LogicNot // !
+};
+
+enum TIL_BinaryOpcode : unsigned char {
+ BOP_Mul, // *
+ BOP_Div, // /
+ BOP_Rem, // %
+ BOP_Add, // +
+ BOP_Sub, // -
+ BOP_Shl, // <<
+ BOP_Shr, // >>
+ BOP_BitAnd, // &
+ BOP_BitXor, // ^
+ BOP_BitOr, // |
+ BOP_Eq, // ==
+ BOP_Neq, // !=
+ BOP_Lt, // <
+ BOP_Leq, // <=
+ BOP_LogicAnd, // &&
+ BOP_LogicOr // ||
+};
+
+enum TIL_CastOpcode : unsigned char {
+ CAST_none = 0,
+ CAST_extendNum, // extend precision of numeric type
+ CAST_truncNum, // truncate precision of numeric type
+ CAST_toFloat, // convert to floating point type
+ CAST_toInt, // convert to integer type
+};
+
+const TIL_Opcode COP_Min = COP_Future;
+const TIL_Opcode COP_Max = COP_Branch;
+const TIL_UnaryOpcode UOP_Min = UOP_Minus;
+const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
+const TIL_BinaryOpcode BOP_Min = BOP_Mul;
+const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
+const TIL_CastOpcode CAST_Min = CAST_none;
+const TIL_CastOpcode CAST_Max = CAST_toInt;
+
+StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
+StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
+
+
+// ValueTypes are data types that can actually be held in registers.
+// All variables and expressions must have a vBNF_Nonealue type.
+// Pointer types are further subdivided into the various heap-allocated
+// types, such as functions, records, etc.
+// Structured types that are passed by value (e.g. complex numbers)
+// require special handling; they use BT_ValueRef, and size ST_0.
+struct ValueType {
+ enum BaseType : unsigned char {
+ BT_Void = 0,
+ BT_Bool,
+ BT_Int,
+ BT_Float,
+ BT_String, // String literals
+ BT_Pointer,
+ BT_ValueRef
+ };
+
+ enum SizeType : unsigned char {
+ ST_0 = 0,
+ ST_1,
+ ST_8,
+ ST_16,
+ ST_32,
+ ST_64,
+ ST_128
+ };
+
+ inline static SizeType getSizeType(unsigned nbytes);
+
+ template <class T>
+ inline static ValueType getValueType();
+
+ ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
+ : Base(B), Size(Sz), Signed(S), VectSize(VS)
+ { }
+
+ BaseType Base;
+ SizeType Size;
+ bool Signed;
+ unsigned char VectSize; // 0 for scalar, otherwise num elements in vector
+};
+
+
+inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
+ switch (nbytes) {
+ case 1: return ST_8;
+ case 2: return ST_16;
+ case 4: return ST_32;
+ case 8: return ST_64;
+ case 16: return ST_128;
+ default: return ST_0;
+ }
+}
+
+
+template<>
+inline ValueType ValueType::getValueType<void>() {
+ return ValueType(BT_Void, ST_0, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<bool>() {
+ return ValueType(BT_Bool, ST_1, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int8_t>() {
+ return ValueType(BT_Int, ST_8, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint8_t>() {
+ return ValueType(BT_Int, ST_8, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int16_t>() {
+ return ValueType(BT_Int, ST_16, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint16_t>() {
+ return ValueType(BT_Int, ST_16, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int32_t>() {
+ return ValueType(BT_Int, ST_32, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint32_t>() {
+ return ValueType(BT_Int, ST_32, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<int64_t>() {
+ return ValueType(BT_Int, ST_64, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<uint64_t>() {
+ return ValueType(BT_Int, ST_64, false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<float>() {
+ return ValueType(BT_Float, ST_32, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<double>() {
+ return ValueType(BT_Float, ST_64, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<long double>() {
+ return ValueType(BT_Float, ST_128, true, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<StringRef>() {
+ return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
+}
+
+template<>
+inline ValueType ValueType::getValueType<void*>() {
+ return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
+}
+
+
+
+// Base class for AST nodes in the typed intermediate language.
+class SExpr {
+public:
+ TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
+
+ // Subclasses of SExpr must define the following:
+ //
+ // This(const This& E, ...) {
+ // copy constructor: construct copy of E, with some additional arguments.
+ // }
+ //
+ // template <class V>
+ // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ // traverse all subexpressions, following the traversal/rewriter interface.
+ // }
+ //
+ // template <class C> typename C::CType compare(CType* E, C& Cmp) {
+ // compare all subexpressions, following the comparator interface
+ // }
+
+ void *operator new(size_t S, MemRegionRef &R) {
+ return ::operator new(S, R);
+ }
+
+ // SExpr objects cannot be deleted.
+ // This declaration is public to workaround a gcc bug that breaks building
+ // with REQUIRES_EH=1.
+ void operator delete(void *) LLVM_DELETED_FUNCTION;
+
+protected:
+ SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {}
+ SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {}
+
+ const unsigned char Opcode;
+ unsigned char Reserved;
+ unsigned short Flags;
+
+private:
+ SExpr() LLVM_DELETED_FUNCTION;
+
+ // SExpr objects must be created in an arena.
+ void *operator new(size_t) LLVM_DELETED_FUNCTION;
+};
+
+
+// Class for owning references to SExprs.
+// Includes attach/detach logic for counting variable references and lazy
+// rewriting strategies.
+class SExprRef {
+public:
+ SExprRef() : Ptr(nullptr) { }
+ SExprRef(std::nullptr_t P) : Ptr(nullptr) { }
+ SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; }
+
+ // Defined after Variable and Future, below.
+ inline SExprRef(SExpr *P);
+ inline ~SExprRef();
+
+ SExpr *get() { return Ptr; }
+ const SExpr *get() const { return Ptr; }
+
+ SExpr *operator->() { return get(); }
+ const SExpr *operator->() const { return get(); }
+
+ SExpr &operator*() { return *Ptr; }
+ const SExpr &operator*() const { return *Ptr; }
+
+ bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; }
+ bool operator!=(const SExprRef &R) const { return !operator==(R); }
+ bool operator==(const SExpr *P) const { return Ptr == P; }
+ bool operator!=(const SExpr *P) const { return !operator==(P); }
+ bool operator==(std::nullptr_t) const { return Ptr == nullptr; }
+ bool operator!=(std::nullptr_t) const { return Ptr != nullptr; }
+
+ inline void reset(SExpr *E);
+
+private:
+ inline void attach();
+ inline void detach();
+
+ SExpr *Ptr;
+};
+
+
+// Contains various helper functions for SExprs.
+namespace ThreadSafetyTIL {
+ inline bool isTrivial(const SExpr *E) {
+ unsigned Op = E->opcode();
+ return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
+ }
+}
+
+// Nodes which declare variables
+class Function;
+class SFunction;
+class BasicBlock;
+class Let;
+
+
+// A named variable, e.g. "x".
+//
+// There are two distinct places in which a Variable can appear in the AST.
+// A variable declaration introduces a new variable, and can occur in 3 places:
+// Let-expressions: (Let (x = t) u)
+// Functions: (Function (x : t) u)
+// Self-applicable functions (SFunction (x) t)
+//
+// If a variable occurs in any other location, it is a reference to an existing
+// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
+// allocate a separate AST node for variable references; a reference is just a
+// pointer to the original declaration.
+class Variable : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
+
+ // Let-variable, function parameter, or self-variable
+ enum VariableKind {
+ VK_Let,
+ VK_LetBB,
+ VK_Fun,
+ VK_SFun
+ };
+
+ // These are defined after SExprRef contructor, below
+ inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr);
+ inline Variable(StringRef s, SExpr *D = nullptr);
+ inline Variable(const Variable &Vd, SExpr *D);
+
+ VariableKind kind() const { return static_cast<VariableKind>(Flags); }
+
+ const StringRef name() const { return Name; }
+ const clang::ValueDecl *clangDecl() const { return Cvdecl; }
+
+ // Returns the definition (for let vars) or type (for parameter & self vars)
+ SExpr *definition() { return Definition.get(); }
+ const SExpr *definition() const { return Definition.get(); }
+
+ void attachVar() const { ++NumUses; }
+ void detachVar() const { assert(NumUses > 0); --NumUses; }
+
+ unsigned getID() const { return Id; }
+ unsigned getBlockID() const { return BlockID; }
+
+ void setName(StringRef S) { Name = S; }
+ void setID(unsigned Bid, unsigned I) {
+ BlockID = static_cast<unsigned short>(Bid);
+ Id = static_cast<unsigned short>(I);
+ }
+ void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
+ void setDefinition(SExpr *E);
+ void setKind(VariableKind K) { Flags = K; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ // This routine is only called for variable references.
+ return Vs.reduceVariableRef(this);
+ }
+
+ template <class C> typename C::CType compare(Variable* E, C& Cmp) {
+ return Cmp.compareVariableRefs(this, E);
+ }
+
+private:
+ friend class Function;
+ friend class SFunction;
+ friend class BasicBlock;
+ friend class Let;
+
+ StringRef Name; // The name of the variable.
+ SExprRef Definition; // The TIL type or definition
+ const clang::ValueDecl *Cvdecl; // The clang declaration for this variable.
+
+ unsigned short BlockID;
+ unsigned short Id;
+ mutable unsigned NumUses;
+};
+
+
+// Placeholder for an expression that has not yet been created.
+// Used to implement lazy copy and rewriting strategies.
+class Future : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
+
+ enum FutureStatus {
+ FS_pending,
+ FS_evaluating,
+ FS_done
+ };
+
+ Future() :
+ SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr)
+ {}
+private:
+ virtual ~Future() LLVM_DELETED_FUNCTION;
+public:
+
+ // Registers the location in the AST where this future is stored.
+ // Forcing the future will automatically update the AST.
+ static inline void registerLocation(SExprRef *Member) {
+ if (Future *F = dyn_cast_or_null<Future>(Member->get()))
+ F->Location = Member;
+ }
+
+ // A lazy rewriting strategy should subclass Future and override this method.
+ virtual SExpr *create() { return nullptr; }
+
+ // Return the result of this future if it exists, otherwise return null.
+ SExpr *maybeGetResult() {
+ return Result;
+ }
+
+ // Return the result of this future; forcing it if necessary.
+ SExpr *result() {
+ switch (Status) {
+ case FS_pending:
+ force();
+ return Result;
+ case FS_evaluating:
+ return nullptr; // infinite loop; illegal recursion.
+ case FS_done:
+ return Result;
+ }
+ }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ assert(Result && "Cannot traverse Future that has not been forced.");
+ return Vs.traverse(Result, Ctx);
+ }
+
+ template <class C> typename C::CType compare(Future* E, C& Cmp) {
+ if (!Result || !E->Result)
+ return Cmp.comparePointers(this, E);
+ return Cmp.compare(Result, E->Result);
+ }
+
+private:
+ // Force the future.
+ inline void force();
+
+ FutureStatus Status;
+ SExpr *Result;
+ SExprRef *Location;
+};
+
+
+inline void SExprRef::attach() {
+ if (!Ptr)
+ return;
+
+ TIL_Opcode Op = Ptr->opcode();
+ if (Op == COP_Variable) {
+ cast<Variable>(Ptr)->attachVar();
+ } else if (Op == COP_Future) {
+ cast<Future>(Ptr)->registerLocation(this);
+ }
+}
+
+inline void SExprRef::detach() {
+ if (Ptr && Ptr->opcode() == COP_Variable) {
+ cast<Variable>(Ptr)->detachVar();
+ }
+}
+
+inline SExprRef::SExprRef(SExpr *P) : Ptr(P) {
+ attach();
+}
+
+inline SExprRef::~SExprRef() {
+ detach();
+}
+
+inline void SExprRef::reset(SExpr *P) {
+ detach();
+ Ptr = P;
+ attach();
+}
+
+
+inline Variable::Variable(StringRef s, SExpr *D)
+ : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr),
+ BlockID(0), Id(0), NumUses(0) {
+ Flags = VK_Let;
+}
+
+inline Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd)
+ : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
+ Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) {
+ Flags = VK_Let;
+}
+
+inline Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor
+ : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl),
+ BlockID(0), Id(0), NumUses(0) {
+ Flags = Vd.kind();
+}
+
+inline void Variable::setDefinition(SExpr *E) {
+ Definition.reset(E);
+}
+
+void Future::force() {
+ Status = FS_evaluating;
+ SExpr *R = create();
+ Result = R;
+ if (Location)
+ Location->reset(R);
+ Status = FS_done;
+}
+
+
+// Placeholder for C++ expressions that cannot be represented in the TIL.
+class Undefined : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
+
+ Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
+ Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ return Vs.reduceUndefined(*this);
+ }
+
+ template <class C> typename C::CType compare(Undefined* E, C& Cmp) {
+ return Cmp.comparePointers(Cstmt, E->Cstmt);
+ }
+
+private:
+ const clang::Stmt *Cstmt;
+};
+
+
+// Placeholder for a wildcard that matches any other expression.
+class Wildcard : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
+
+ Wildcard() : SExpr(COP_Wildcard) {}
+ Wildcard(const Wildcard &W) : SExpr(W) {}
+
+ template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ return Vs.reduceWildcard(*this);
+ }
+
+ template <class C> typename C::CType compare(Wildcard* E, C& Cmp) {
+ return Cmp.trueResult();
+ }
+};
+
+
+template <class T> class LiteralT;
+
+// Base class for literal values.
+class Literal : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
+
+ Literal(const clang::Expr *C)
+ : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
+ { }
+ Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
+ Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
+
+ // The clang expression for this literal.
+ const clang::Expr *clangExpr() const { return Cexpr; }
+
+ ValueType valueType() const { return ValType; }
+
+ template<class T> const LiteralT<T>& as() const {
+ return *static_cast<const LiteralT<T>*>(this);
+ }
+ template<class T> LiteralT<T>& as() {
+ return *static_cast<LiteralT<T>*>(this);
+ }
+
+ template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
+
+ template <class C> typename C::CType compare(Literal* E, C& Cmp) {
+ // TODO -- use value, not pointer equality
+ return Cmp.comparePointers(Cexpr, E->Cexpr);
+ }
+
+private:
+ const ValueType ValType;
+ const clang::Expr *Cexpr;
+};
+
+
+// Derived class for literal values, which stores the actual value.
+template<class T>
+class LiteralT : public Literal {
+public:
+ LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
+ LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
+
+ T value() const { return Val;}
+ T& value() { return Val; }
+
+private:
+ T Val;
+};
+
+
+
+template <class V>
+typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
+ if (Cexpr)
+ return Vs.reduceLiteral(*this);
+
+ switch (ValType.Base) {
+ case ValueType::BT_Void:
+ break;
+ case ValueType::BT_Bool:
+ return Vs.reduceLiteralT(as<bool>());
+ case ValueType::BT_Int: {
+ switch (ValType.Size) {
+ case ValueType::ST_8:
+ if (ValType.Signed)
+ return Vs.reduceLiteralT(as<int8_t>());
+ else
+ return Vs.reduceLiteralT(as<uint8_t>());
+ case ValueType::ST_16:
+ if (ValType.Signed)
+ return Vs.reduceLiteralT(as<int16_t>());
+ else
+ return Vs.reduceLiteralT(as<uint16_t>());
+ case ValueType::ST_32:
+ if (ValType.Signed)
+ return Vs.reduceLiteralT(as<int32_t>());
+ else
+ return Vs.reduceLiteralT(as<uint32_t>());
+ case ValueType::ST_64:
+ if (ValType.Signed)
+ return Vs.reduceLiteralT(as<int64_t>());
+ else
+ return Vs.reduceLiteralT(as<uint64_t>());
+ default:
+ break;
+ }
+ }
+ case ValueType::BT_Float: {
+ switch (ValType.Size) {
+ case ValueType::ST_32:
+ return Vs.reduceLiteralT(as<float>());
+ case ValueType::ST_64:
+ return Vs.reduceLiteralT(as<double>());
+ default:
+ break;
+ }
+ }
+ case ValueType::BT_String:
+ return Vs.reduceLiteralT(as<StringRef>());
+ case ValueType::BT_Pointer:
+ return Vs.reduceLiteralT(as<void*>());
+ case ValueType::BT_ValueRef:
+ break;
+ }
+ return Vs.reduceLiteral(*this);
+}
+
+
+// Literal pointer to an object allocated in memory.
+// At compile time, pointer literals are represented by symbolic names.
+class LiteralPtr : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
+
+ LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
+ LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
+
+ // The clang declaration for the value that this pointer points to.
+ const clang::ValueDecl *clangDecl() const { return Cvdecl; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ return Vs.reduceLiteralPtr(*this);
+ }
+
+ template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) {
+ return Cmp.comparePointers(Cvdecl, E->Cvdecl);
+ }
+
+private:
+ const clang::ValueDecl *Cvdecl;
+};
+
+
+// A function -- a.k.a. lambda abstraction.
+// Functions with multiple arguments are created by currying,
+// e.g. (function (x: Int) (function (y: Int) (add x y)))
+class Function : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
+
+ Function(Variable *Vd, SExpr *Bd)
+ : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
+ Vd->setKind(Variable::VK_Fun);
+ }
+ Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
+ : SExpr(F), VarDecl(Vd), Body(Bd) {
+ Vd->setKind(Variable::VK_Fun);
+ }
+
+ Variable *variableDecl() { return VarDecl; }
+ const Variable *variableDecl() const { return VarDecl; }
+
+ SExpr *body() { return Body.get(); }
+ const SExpr *body() const { return Body.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ // This is a variable declaration, so traverse the definition.
+ auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
+ // Tell the rewriter to enter the scope of the function.
+ Variable *Nvd = Vs.enterScope(*VarDecl, E0);
+ auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
+ Vs.exitScope(*VarDecl);
+ return Vs.reduceFunction(*this, Nvd, E1);
+ }
+
+ template <class C> typename C::CType compare(Function* E, C& Cmp) {
+ typename C::CType Ct =
+ Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ Cmp.enterScope(variableDecl(), E->variableDecl());
+ Ct = Cmp.compare(body(), E->body());
+ Cmp.leaveScope();
+ return Ct;
+ }
+
+private:
+ Variable *VarDecl;
+ SExprRef Body;
+};
+
+
+// A self-applicable function.
+// A self-applicable function can be applied to itself. It's useful for
+// implementing objects and late binding
+class SFunction : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
+
+ SFunction(Variable *Vd, SExpr *B)
+ : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
+ assert(Vd->Definition == nullptr);
+ Vd->setKind(Variable::VK_SFun);
+ Vd->Definition.reset(this);
+ }
+ SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
+ : SExpr(F), VarDecl(Vd), Body(B) {
+ assert(Vd->Definition == nullptr);
+ Vd->setKind(Variable::VK_SFun);
+ Vd->Definition.reset(this);
+ }
+
+ Variable *variableDecl() { return VarDecl; }
+ const Variable *variableDecl() const { return VarDecl; }
+
+ SExpr *body() { return Body.get(); }
+ const SExpr *body() const { return Body.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ // A self-variable points to the SFunction itself.
+ // A rewrite must introduce the variable with a null definition, and update
+ // it after 'this' has been rewritten.
+ Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
+ auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
+ Vs.exitScope(*VarDecl);
+ // A rewrite operation will call SFun constructor to set Vvd->Definition.
+ return Vs.reduceSFunction(*this, Nvd, E1);
+ }
+
+ template <class C> typename C::CType compare(SFunction* E, C& Cmp) {
+ Cmp.enterScope(variableDecl(), E->variableDecl());
+ typename C::CType Ct = Cmp.compare(body(), E->body());
+ Cmp.leaveScope();
+ return Ct;
+ }
+
+private:
+ Variable *VarDecl;
+ SExprRef Body;
+};
+
+
+// A block of code -- e.g. the body of a function.
+class Code : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
+
+ Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
+ Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
+ : SExpr(C), ReturnType(T), Body(B) {}
+
+ SExpr *returnType() { return ReturnType.get(); }
+ const SExpr *returnType() const { return ReturnType.get(); }
+
+ SExpr *body() { return Body.get(); }
+ const SExpr *body() const { return Body.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
+ auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
+ return Vs.reduceCode(*this, Nt, Nb);
+ }
+
+ template <class C> typename C::CType compare(Code* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(body(), E->body());
+ }
+
+private:
+ SExprRef ReturnType;
+ SExprRef Body;
+};
+
+
+// A typed, writable location in memory
+class Field : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
+
+ Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
+ Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
+ : SExpr(C), Range(R), Body(B) {}
+
+ SExpr *range() { return Range.get(); }
+ const SExpr *range() const { return Range.get(); }
+
+ SExpr *body() { return Body.get(); }
+ const SExpr *body() const { return Body.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
+ auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
+ return Vs.reduceField(*this, Nr, Nb);
+ }
+
+ template <class C> typename C::CType compare(Field* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(range(), E->range());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(body(), E->body());
+ }
+
+private:
+ SExprRef Range;
+ SExprRef Body;
+};
+
+
+// Apply an argument to a function
+class Apply : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
+
+ Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
+ Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
+ : SExpr(A), Fun(F), Arg(Ar)
+ {}
+
+ SExpr *fun() { return Fun.get(); }
+ const SExpr *fun() const { return Fun.get(); }
+
+ SExpr *arg() { return Arg.get(); }
+ const SExpr *arg() const { return Arg.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
+ auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
+ return Vs.reduceApply(*this, Nf, Na);
+ }
+
+ template <class C> typename C::CType compare(Apply* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(fun(), E->fun());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(arg(), E->arg());
+ }
+
+private:
+ SExprRef Fun;
+ SExprRef Arg;
+};
+
+
+// Apply a self-argument to a self-applicable function
+class SApply : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
+
+ SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
+ SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
+ : SExpr(A), Sfun(Sf), Arg(Ar) {}
+
+ SExpr *sfun() { return Sfun.get(); }
+ const SExpr *sfun() const { return Sfun.get(); }
+
+ SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); }
+ const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); }
+
+ bool isDelegation() const { return Arg == nullptr; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
+ typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
+ : nullptr;
+ return Vs.reduceSApply(*this, Nf, Na);
+ }
+
+ template <class C> typename C::CType compare(SApply* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
+ if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
+ return Ct;
+ return Cmp.compare(arg(), E->arg());
+ }
+
+private:
+ SExprRef Sfun;
+ SExprRef Arg;
+};
+
+
+// Project a named slot from a C++ struct or class.
+class Project : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
+
+ Project(SExpr *R, StringRef SName)
+ : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
+ { }
+ Project(SExpr *R, clang::ValueDecl *Cvd)
+ : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
+ { }
+ Project(const Project &P, SExpr *R)
+ : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
+ { }
+
+ SExpr *record() { return Rec.get(); }
+ const SExpr *record() const { return Rec.get(); }
+
+ const clang::ValueDecl *clangValueDecl() const { return Cvdecl; }
+
+ StringRef slotName() const {
+ if (Cvdecl)
+ return Cvdecl->getName();
+ else
+ return SlotName;
+ }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
+ return Vs.reduceProject(*this, Nr);
+ }
+
+ template <class C> typename C::CType compare(Project* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(record(), E->record());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.comparePointers(Cvdecl, E->Cvdecl);
+ }
+
+private:
+ SExprRef Rec;
+ StringRef SlotName;
+ clang::ValueDecl *Cvdecl;
+};
+
+
+// Call a function (after all arguments have been applied).
+class Call : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
+
+ Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
+ : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
+ Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
+
+ SExpr *target() { return Target.get(); }
+ const SExpr *target() const { return Target.get(); }
+
+ const clang::CallExpr *clangCallExpr() const { return Cexpr; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
+ return Vs.reduceCall(*this, Nt);
+ }
+
+ template <class C> typename C::CType compare(Call* E, C& Cmp) {
+ return Cmp.compare(target(), E->target());
+ }
+
+private:
+ SExprRef Target;
+ const clang::CallExpr *Cexpr;
+};
+
+
+// Allocate memory for a new value on the heap or stack.
+class Alloc : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
+
+ enum AllocKind {
+ AK_Stack,
+ AK_Heap
+ };
+
+ Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
+ Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
+
+ AllocKind kind() const { return static_cast<AllocKind>(Flags); }
+
+ SExpr *dataType() { return Dtype.get(); }
+ const SExpr *dataType() const { return Dtype.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
+ return Vs.reduceAlloc(*this, Nd);
+ }
+
+ template <class C> typename C::CType compare(Alloc* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(dataType(), E->dataType());
+ }
+
+private:
+ SExprRef Dtype;
+};
+
+
+// Load a value from memory.
+class Load : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
+
+ Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
+ Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
+
+ SExpr *pointer() { return Ptr.get(); }
+ const SExpr *pointer() const { return Ptr.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
+ return Vs.reduceLoad(*this, Np);
+ }
+
+ template <class C> typename C::CType compare(Load* E, C& Cmp) {
+ return Cmp.compare(pointer(), E->pointer());
+ }
+
+private:
+ SExprRef Ptr;
+};
+
+
+// Store a value to memory.
+// Source is a pointer, destination is the value to store.
+class Store : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
+
+ Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
+ Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
+
+ SExpr *destination() { return Dest.get(); } // Address to store to
+ const SExpr *destination() const { return Dest.get(); }
+
+ SExpr *source() { return Source.get(); } // Value to store
+ const SExpr *source() const { return Source.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
+ auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
+ return Vs.reduceStore(*this, Np, Nv);
+ }
+
+ template <class C> typename C::CType compare(Store* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(destination(), E->destination());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(source(), E->source());
+ }
+
+private:
+ SExprRef Dest;
+ SExprRef Source;
+};
+
+
+// If p is a reference to an array, then first(p) is a reference to the first
+// element. The usual array notation p[i] becomes first(p + i).
+class ArrayIndex : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
+
+ ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
+ ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
+ : SExpr(E), Array(A), Index(N) {}
+
+ SExpr *array() { return Array.get(); }
+ const SExpr *array() const { return Array.get(); }
+
+ SExpr *index() { return Index.get(); }
+ const SExpr *index() const { return Index.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
+ auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
+ return Vs.reduceArrayIndex(*this, Na, Ni);
+ }
+
+ template <class C> typename C::CType compare(ArrayIndex* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(array(), E->array());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(index(), E->index());
+ }
+
+private:
+ SExprRef Array;
+ SExprRef Index;
+};
+
+
+// Pointer arithmetic, restricted to arrays only.
+// If p is a reference to an array, then p + n, where n is an integer, is
+// a reference to a subarray.
+class ArrayAdd : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
+
+ ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
+ ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
+ : SExpr(E), Array(A), Index(N) {}
+
+ SExpr *array() { return Array.get(); }
+ const SExpr *array() const { return Array.get(); }
+
+ SExpr *index() { return Index.get(); }
+ const SExpr *index() const { return Index.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
+ auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
+ return Vs.reduceArrayAdd(*this, Na, Ni);
+ }
+
+ template <class C> typename C::CType compare(ArrayAdd* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(array(), E->array());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(index(), E->index());
+ }
+
+private:
+ SExprRef Array;
+ SExprRef Index;
+};
+
+
+// Simple unary operation -- e.g. !, ~, etc.
+class UnaryOp : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
+
+ UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
+ Flags = Op;
+ }
+ UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
+
+ TIL_UnaryOpcode unaryOpcode() const {
+ return static_cast<TIL_UnaryOpcode>(Flags);
+ }
+
+ SExpr *expr() { return Expr0.get(); }
+ const SExpr *expr() const { return Expr0.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+ return Vs.reduceUnaryOp(*this, Ne);
+ }
+
+ template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) {
+ typename C::CType Ct =
+ Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(expr(), E->expr());
+ }
+
+private:
+ SExprRef Expr0;
+};
+
+
+// Simple binary operation -- e.g. +, -, etc.
+class BinaryOp : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
+
+ BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
+ : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
+ Flags = Op;
+ }
+ BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
+ : SExpr(B), Expr0(E0), Expr1(E1) {
+ Flags = B.Flags;
+ }
+
+ TIL_BinaryOpcode binaryOpcode() const {
+ return static_cast<TIL_BinaryOpcode>(Flags);
+ }
+
+ SExpr *expr0() { return Expr0.get(); }
+ const SExpr *expr0() const { return Expr0.get(); }
+
+ SExpr *expr1() { return Expr1.get(); }
+ const SExpr *expr1() const { return Expr1.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+ auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
+ return Vs.reduceBinaryOp(*this, Ne0, Ne1);
+ }
+
+ template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) {
+ typename C::CType Ct =
+ Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ Ct = Cmp.compare(expr0(), E->expr0());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(expr1(), E->expr1());
+ }
+
+private:
+ SExprRef Expr0;
+ SExprRef Expr1;
+};
+
+
+// Cast expression
+class Cast : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
+
+ Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
+ Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
+
+ TIL_CastOpcode castOpcode() const {
+ return static_cast<TIL_CastOpcode>(Flags);
+ }
+
+ SExpr *expr() { return Expr0.get(); }
+ const SExpr *expr() const { return Expr0.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
+ return Vs.reduceCast(*this, Ne);
+ }
+
+ template <class C> typename C::CType compare(Cast* E, C& Cmp) {
+ typename C::CType Ct =
+ Cmp.compareIntegers(castOpcode(), E->castOpcode());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(expr(), E->expr());
+ }
+
+private:
+ SExprRef Expr0;
+};
+
+
+class SCFG;
+
+
+class Phi : public SExpr {
+public:
+ // TODO: change to SExprRef
+ typedef SimpleArray<SExpr *> ValArray;
+
+ // In minimal SSA form, all Phi nodes are MultiVal.
+ // During conversion to SSA, incomplete Phi nodes may be introduced, which
+ // are later determined to be SingleVal, and are thus redundant.
+ enum Status {
+ PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
+ PH_SingleVal, // Phi node has one distinct value, and can be eliminated
+ PH_Incomplete // Phi node is incomplete
+ };
+
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
+
+ Phi() : SExpr(COP_Phi) {}
+ Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
+ Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
+
+ const ValArray &values() const { return Values; }
+ ValArray &values() { return Values; }
+
+ Status status() const { return static_cast<Status>(Flags); }
+ void setStatus(Status s) { Flags = s; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ typename V::template Container<typename V::R_SExpr>
+ Nvs(Vs, Values.size());
+
+ for (auto *Val : Values) {
+ Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
+ }
+ return Vs.reducePhi(*this, Nvs);
+ }
+
+ template <class C> typename C::CType compare(Phi *E, C &Cmp) {
+ // TODO: implement CFG comparisons
+ return Cmp.comparePointers(this, E);
+ }
+
+private:
+ ValArray Values;
+};
+
+
+// A basic block is part of an SCFG, and can be treated as a function in
+// continuation passing style. It consists of a sequence of phi nodes, which
+// are "arguments" to the function, followed by a sequence of instructions.
+// Both arguments and instructions define new variables. It ends with a
+// branch or goto to another basic block in the same SCFG.
+class BasicBlock : public SExpr {
+public:
+ typedef SimpleArray<Variable*> VarArray;
+ typedef SimpleArray<BasicBlock*> BlockArray;
+
+ static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
+
+ explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr)
+ : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),
+ Parent(P), Terminator(nullptr)
+ { }
+ BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T)
+ : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0),
+ Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)),
+ Terminator(T)
+ { }
+
+ unsigned blockID() const { return BlockID; }
+ unsigned numPredecessors() const { return Predecessors.size(); }
+
+ const SCFG* cfg() const { return CFGPtr; }
+ SCFG* cfg() { return CFGPtr; }
+
+ const BasicBlock *parent() const { return Parent; }
+ BasicBlock *parent() { return Parent; }
+
+ const VarArray &arguments() const { return Args; }
+ VarArray &arguments() { return Args; }
+
+ const VarArray &instructions() const { return Instrs; }
+ VarArray &instructions() { return Instrs; }
+
+ const BlockArray &predecessors() const { return Predecessors; }
+ BlockArray &predecessors() { return Predecessors; }
+
+ const SExpr *terminator() const { return Terminator.get(); }
+ SExpr *terminator() { return Terminator.get(); }
+
+ void setBlockID(unsigned i) { BlockID = i; }
+ void setParent(BasicBlock *P) { Parent = P; }
+ void setTerminator(SExpr *E) { Terminator.reset(E); }
+
+ // Add a new argument. V must define a phi-node.
+ void addArgument(Variable *V) {
+ V->setKind(Variable::VK_LetBB);
+ Args.reserveCheck(1, Arena);
+ Args.push_back(V);
+ }
+ // Add a new instruction.
+ void addInstruction(Variable *V) {
+ V->setKind(Variable::VK_LetBB);
+ Instrs.reserveCheck(1, Arena);
+ Instrs.push_back(V);
+ }
+ // Add a new predecessor, and return the phi-node index for it.
+ // Will add an argument to all phi-nodes, initialized to nullptr.
+ unsigned addPredecessor(BasicBlock *Pred);
+
+ // Reserve space for Nargs arguments.
+ void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
+
+ // Reserve space for Nins instructions.
+ void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
+
+ // Reserve space for NumPreds predecessors, including space in phi nodes.
+ void reservePredecessors(unsigned NumPreds);
+
+ // Return the index of BB, or Predecessors.size if BB is not a predecessor.
+ unsigned findPredecessorIndex(const BasicBlock *BB) const {
+ auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB);
+ return std::distance(Predecessors.cbegin(), I);
+ }
+
+ // Set id numbers for variables.
+ void renumberVars();
+
+ template <class V>
+ typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
+ typename V::template Container<Variable*> Nas(Vs, Args.size());
+ typename V::template Container<Variable*> Nis(Vs, Instrs.size());
+
+ // Entering the basic block should do any scope initialization.
+ Vs.enterBasicBlock(*this);
+
+ for (auto *A : Args) {
+ auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx));
+ Variable *Nvd = Vs.enterScope(*A, Ne);
+ Nas.push_back(Nvd);
+ }
+ for (auto *I : Instrs) {
+ auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx));
+ Variable *Nvd = Vs.enterScope(*I, Ne);
+ Nis.push_back(Nvd);
+ }
+ auto Nt = Vs.traverse(Terminator, Ctx);
+
+ // Exiting the basic block should handle any scope cleanup.
+ Vs.exitBasicBlock(*this);
+
+ return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
+ }
+
+ template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) {
+ // TODO: implement CFG comparisons
+ return Cmp.comparePointers(this, E);
+ }
+
+private:
+ friend class SCFG;
+
+ MemRegionRef Arena;
+
+ SCFG *CFGPtr; // The CFG that contains this block.
+ unsigned BlockID; // unique id for this BB in the containing CFG
+ BasicBlock *Parent; // The parent block is the enclosing lexical scope.
+ // The parent dominates this block.
+ BlockArray Predecessors; // Predecessor blocks in the CFG.
+ VarArray Args; // Phi nodes. One argument per predecessor.
+ VarArray Instrs; // Instructions.
+ SExprRef Terminator; // Branch or Goto
+};
+
+
+// An SCFG is a control-flow graph. It consists of a set of basic blocks, each
+// of which terminates in a branch to another basic block. There is one
+// entry point, and one exit point.
+class SCFG : public SExpr {
+public:
+ typedef SimpleArray<BasicBlock *> BlockArray;
+ typedef BlockArray::iterator iterator;
+ typedef BlockArray::const_iterator const_iterator;
+
+ static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
+
+ SCFG(MemRegionRef A, unsigned Nblocks)
+ : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks),
+ Entry(nullptr), Exit(nullptr) {
+ Entry = new (A) BasicBlock(A, nullptr);
+ Exit = new (A) BasicBlock(A, Entry);
+ auto *V = new (A) Variable(new (A) Phi());
+ Exit->addArgument(V);
+ add(Entry);
+ add(Exit);
+ }
+ SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
+ : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)),
+ Entry(nullptr), Exit(nullptr) {
+ // TODO: set entry and exit!
+ }
+
+ iterator begin() { return Blocks.begin(); }
+ iterator end() { return Blocks.end(); }
+
+ const_iterator begin() const { return cbegin(); }
+ const_iterator end() const { return cend(); }
+
+ const_iterator cbegin() const { return Blocks.cbegin(); }
+ const_iterator cend() const { return Blocks.cend(); }
+
+ const BasicBlock *entry() const { return Entry; }
+ BasicBlock *entry() { return Entry; }
+ const BasicBlock *exit() const { return Exit; }
+ BasicBlock *exit() { return Exit; }
+
+ inline void add(BasicBlock *BB) {
+ assert(BB->CFGPtr == nullptr || BB->CFGPtr == this);
+ BB->setBlockID(Blocks.size());
+ BB->CFGPtr = this;
+ Blocks.reserveCheck(1, Arena);
+ Blocks.push_back(BB);
+ }
+
+ void setEntry(BasicBlock *BB) { Entry = BB; }
+ void setExit(BasicBlock *BB) { Exit = BB; }
+
+ // Set varable ids in all blocks.
+ void renumberVars();
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ Vs.enterCFG(*this);
+ typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
+ for (auto *B : Blocks) {
+ Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
+ }
+ Vs.exitCFG(*this);
+ return Vs.reduceSCFG(*this, Bbs);
+ }
+
+ template <class C> typename C::CType compare(SCFG *E, C &Cmp) {
+ // TODO -- implement CFG comparisons
+ return Cmp.comparePointers(this, E);
+ }
+
+private:
+ MemRegionRef Arena;
+ BlockArray Blocks;
+ BasicBlock *Entry;
+ BasicBlock *Exit;
+};
+
+
+class Goto : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
+
+ Goto(BasicBlock *B, unsigned I)
+ : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
+ Goto(const Goto &G, BasicBlock *B, unsigned I)
+ : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
+
+ const BasicBlock *targetBlock() const { return TargetBlock; }
+ BasicBlock *targetBlock() { return TargetBlock; }
+
+ unsigned index() const { return Index; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
+ return Vs.reduceGoto(*this, Ntb);
+ }
+
+ template <class C> typename C::CType compare(Goto *E, C &Cmp) {
+ // TODO -- implement CFG comparisons
+ return Cmp.comparePointers(this, E);
+ }
+
+private:
+ BasicBlock *TargetBlock;
+ unsigned Index; // Index into Phi nodes of target block.
+};
+
+
+class Branch : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
+
+ Branch(SExpr *C, BasicBlock *T, BasicBlock *E, unsigned TI, unsigned EI)
+ : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
+ ThenIndex(TI), ElseIndex(EI)
+ {}
+ Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E,
+ unsigned TI, unsigned EI)
+ : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
+ ThenIndex(TI), ElseIndex(EI)
+ {}
+
+ const SExpr *condition() const { return Condition; }
+ SExpr *condition() { return Condition; }
+
+ const BasicBlock *thenBlock() const { return ThenBlock; }
+ BasicBlock *thenBlock() { return ThenBlock; }
+
+ const BasicBlock *elseBlock() const { return ElseBlock; }
+ BasicBlock *elseBlock() { return ElseBlock; }
+
+ unsigned thenIndex() const { return ThenIndex; }
+ unsigned elseIndex() const { return ElseIndex; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
+ BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock);
+ BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock);
+ return Vs.reduceBranch(*this, Nc, Ntb, Nte);
+ }
+
+ template <class C> typename C::CType compare(Branch *E, C &Cmp) {
+ // TODO -- implement CFG comparisons
+ return Cmp.comparePointers(this, E);
+ }
+
+private:
+ SExpr *Condition;
+ BasicBlock *ThenBlock;
+ BasicBlock *ElseBlock;
+ unsigned ThenIndex;
+ unsigned ElseIndex;
+};
+
+
+// An identifier, e.g. 'foo' or 'x'.
+// This is a pseduo-term; it will be lowered to a variable or projection.
+class Identifier : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
+
+ Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
+ Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { }
+
+ StringRef name() const { return Name; }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ return Vs.reduceIdentifier(*this);
+ }
+
+ template <class C> typename C::CType compare(Identifier* E, C& Cmp) {
+ return Cmp.compareStrings(name(), E->name());
+ }
+
+private:
+ StringRef Name;
+};
+
+
+// An if-then-else expression.
+// This is a pseduo-term; it will be lowered to a branch in a CFG.
+class IfThenElse : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
+
+ IfThenElse(SExpr *C, SExpr *T, SExpr *E)
+ : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
+ { }
+ IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
+ : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
+ { }
+
+ SExpr *condition() { return Condition.get(); } // Address to store to
+ const SExpr *condition() const { return Condition.get(); }
+
+ SExpr *thenExpr() { return ThenExpr.get(); } // Value to store
+ const SExpr *thenExpr() const { return ThenExpr.get(); }
+
+ SExpr *elseExpr() { return ElseExpr.get(); } // Value to store
+ const SExpr *elseExpr() const { return ElseExpr.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
+ auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
+ auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
+ return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
+ }
+
+ template <class C> typename C::CType compare(IfThenElse* E, C& Cmp) {
+ typename C::CType Ct = Cmp.compare(condition(), E->condition());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ Ct = Cmp.compare(thenExpr(), E->thenExpr());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ return Cmp.compare(elseExpr(), E->elseExpr());
+ }
+
+private:
+ SExprRef Condition;
+ SExprRef ThenExpr;
+ SExprRef ElseExpr;
+};
+
+
+// A let-expression, e.g. let x=t; u.
+// This is a pseduo-term; it will be lowered to instructions in a CFG.
+class Let : public SExpr {
+public:
+ static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
+
+ Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
+ Vd->setKind(Variable::VK_Let);
+ }
+ Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
+ Vd->setKind(Variable::VK_Let);
+ }
+
+ Variable *variableDecl() { return VarDecl; }
+ const Variable *variableDecl() const { return VarDecl; }
+
+ SExpr *body() { return Body.get(); }
+ const SExpr *body() const { return Body.get(); }
+
+ template <class V>
+ typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
+ // This is a variable declaration, so traverse the definition.
+ auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
+ // Tell the rewriter to enter the scope of the let variable.
+ Variable *Nvd = Vs.enterScope(*VarDecl, E0);
+ auto E1 = Vs.traverse(Body, Ctx);
+ Vs.exitScope(*VarDecl);
+ return Vs.reduceLet(*this, Nvd, E1);
+ }
+
+ template <class C> typename C::CType compare(Let* E, C& Cmp) {
+ typename C::CType Ct =
+ Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
+ if (Cmp.notTrue(Ct))
+ return Ct;
+ Cmp.enterScope(variableDecl(), E->variableDecl());
+ Ct = Cmp.compare(body(), E->body());
+ Cmp.leaveScope();
+ return Ct;
+ }
+
+private:
+ Variable *VarDecl;
+ SExprRef Body;
+};
+
+
+
+SExpr *getCanonicalVal(SExpr *E);
+void simplifyIncompleteArg(Variable *V, til::Phi *Ph);
+
+
+} // end namespace til
+} // end namespace threadSafety
+} // end namespace clang
+
+#endif // LLVM_CLANG_THREAD_SAFETY_TIL_H
OpenPOWER on IntegriCloud