//===- 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_ANALYSIS_ANALYSES_THREADSAFETYTIL_H #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H // All clang include dependencies for this file must be put in // ThreadSafetyUtil.h. #include "ThreadSafetyUtil.h" #include #include #include #include #include namespace clang { namespace threadSafety { namespace til { /// Enum for the different distinct classes of SExpr enum TIL_Opcode { #define TIL_OPCODE_DEF(X) COP_##X, #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF }; /// Opcode for unary arithmetic operations. enum TIL_UnaryOpcode : unsigned char { UOP_Minus, // - UOP_BitNot, // ~ UOP_LogicNot // ! }; /// Opcode for binary arithmetic operations. enum TIL_BinaryOpcode : unsigned char { BOP_Add, // + BOP_Sub, // - BOP_Mul, // * BOP_Div, // / BOP_Rem, // % BOP_Shl, // << BOP_Shr, // >> BOP_BitAnd, // & BOP_BitXor, // ^ BOP_BitOr, // | BOP_Eq, // == BOP_Neq, // != BOP_Lt, // < BOP_Leq, // <= BOP_LogicAnd, // && (no short-circuit) BOP_LogicOr // || (no short-circuit) }; /// Opcode for cast operations. 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 CAST_objToPtr // convert smart pointer to pointer (C++ only) }; 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_Add; const TIL_BinaryOpcode BOP_Max = BOP_LogicOr; const TIL_CastOpcode CAST_Min = CAST_none; const TIL_CastOpcode CAST_Max = CAST_toInt; /// Return the name of a unary opcode. StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); /// Return the name of a binary opcode. StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); /// ValueTypes are data types that can actually be held in registers. /// All variables and expressions must have a value 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 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() { return ValueType(BT_Void, ST_0, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Bool, ST_1, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_8, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_8, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_16, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_16, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_32, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_32, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_64, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Int, ST_64, false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Float, ST_32, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Float, ST_64, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Float, ST_128, true, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); } template<> inline ValueType ValueType::getValueType() { return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); } class BasicBlock; /// Base class for AST nodes in the typed intermediate language. class SExpr { public: TIL_Opcode opcode() const { return static_cast(Opcode); } // Subclasses of SExpr must define the following: // // This(const This& E, ...) { // copy constructor: construct copy of E, with some additional arguments. // } // // template // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { // traverse all subexpressions, following the traversal/rewriter interface. // } // // template 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 *) = delete; /// Returns the instruction ID for this expression. /// All basic block instructions have a unique ID (i.e. virtual register). unsigned id() const { return SExprID; } /// Returns the block, if this is an instruction in a basic block, /// otherwise returns null. BasicBlock* block() const { return Block; } /// Set the basic block and instruction ID for this expression. void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } protected: SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {} SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0), Block(nullptr) {} const unsigned char Opcode; unsigned char Reserved; unsigned short Flags; unsigned SExprID; BasicBlock* Block; private: SExpr() = delete; /// SExpr objects must be created in an arena. void *operator new(size_t) = delete; }; // 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 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; } enum VariableKind { VK_Let, ///< Let-variable VK_Fun, ///< Function parameter VK_SFun ///< SFunction (self) parameter }; Variable(StringRef s, SExpr *D = nullptr) : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) { Flags = VK_Let; } Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr) : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), Definition(D), Cvdecl(Cvd) { Flags = VK_Let; } Variable(const Variable &Vd, SExpr *D) // rewrite constructor : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { Flags = Vd.kind(); } /// Return the kind of variable (let, function param, or self) VariableKind kind() const { return static_cast(Flags); } /// Return the name of the variable, if any. StringRef name() const { return Name; } /// Return the clang declaration for this variable, if any. const clang::ValueDecl *clangDecl() const { return Cvdecl; } /// Return the definition of the variable. /// For let-vars, this is the setting expression. /// For function and self parameters, it is the type of the variable. SExpr *definition() { return Definition; } const SExpr *definition() const { return Definition; } void setName(StringRef S) { Name = S; } void setKind(VariableKind K) { Flags = K; } void setDefinition(SExpr *E) { Definition = E; } void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } template 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 typename C::CType compare(const Variable* E, C& Cmp) const { 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. SExpr* Definition; // The TIL type or definition const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. }; /// 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) {} private: virtual ~Future() = delete; public: // A lazy rewriting strategy should subclass Future and override this method. virtual SExpr *compute() { return nullptr; } // Return the result of this future if it exists, otherwise return null. SExpr *maybeGetResult() const { return Result; } // Return the result of this future; forcing it if necessary. SExpr *result() { switch (Status) { case FS_pending: return force(); case FS_evaluating: return nullptr; // infinite loop; illegal recursion. case FS_done: return Result; } } template 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 typename C::CType compare(const Future* E, C& Cmp) const { if (!Result || !E->Result) return Cmp.comparePointers(this, E); return Cmp.compare(Result, E->Result); } private: SExpr* force(); FutureStatus Status; SExpr *Result; }; /// Placeholder for 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 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceUndefined(*this); } template typename C::CType compare(const Undefined* E, C& Cmp) const { return Cmp.trueResult(); } 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 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceWildcard(*this); } template typename C::CType compare(const Wildcard* E, C& Cmp) const { return Cmp.trueResult(); } }; template 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()), 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 const LiteralT& as() const { return *static_cast*>(this); } template LiteralT& as() { return *static_cast*>(this); } template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); template typename C::CType compare(const Literal* E, C& Cmp) const { // TODO: defer actual comparison to LiteralT return Cmp.trueResult(); } private: const ValueType ValType; const clang::Expr *Cexpr; }; // Derived class for literal values, which stores the actual value. template class LiteralT : public Literal { public: LiteralT(T Dat) : Literal(ValueType::getValueType()), Val(Dat) { } LiteralT(const LiteralT &L) : Literal(L), Val(L.Val) { } T value() const { return Val;} T& value() { return Val; } private: T Val; }; template 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()); case ValueType::BT_Int: { switch (ValType.Size) { case ValueType::ST_8: if (ValType.Signed) return Vs.reduceLiteralT(as()); else return Vs.reduceLiteralT(as()); case ValueType::ST_16: if (ValType.Signed) return Vs.reduceLiteralT(as()); else return Vs.reduceLiteralT(as()); case ValueType::ST_32: if (ValType.Signed) return Vs.reduceLiteralT(as()); else return Vs.reduceLiteralT(as()); case ValueType::ST_64: if (ValType.Signed) return Vs.reduceLiteralT(as()); else return Vs.reduceLiteralT(as()); default: break; } } case ValueType::BT_Float: { switch (ValType.Size) { case ValueType::ST_32: return Vs.reduceLiteralT(as()); case ValueType::ST_64: return Vs.reduceLiteralT(as()); default: break; } } case ValueType::BT_String: return Vs.reduceLiteralT(as()); case ValueType::BT_Pointer: return Vs.reduceLiteralT(as()); case ValueType::BT_ValueRef: break; } return Vs.reduceLiteral(*this); } /// A 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 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceLiteralPtr(*this); } template typename C::CType compare(const LiteralPtr* E, C& Cmp) const { 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) (Code { return 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; } const SExpr *body() const { return Body; } template 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 typename C::CType compare(const Function* E, C& Cmp) const { 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; SExpr* 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 = 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 = this; } Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } SExpr *body() { return Body; } const SExpr *body() const { return Body; } template 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 typename C::CType compare(const SFunction* E, C& Cmp) const { Cmp.enterScope(variableDecl(), E->variableDecl()); typename C::CType Ct = Cmp.compare(body(), E->body()); Cmp.leaveScope(); return Ct; } private: Variable *VarDecl; SExpr* 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; } const SExpr *returnType() const { return ReturnType; } SExpr *body() { return Body; } const SExpr *body() const { return Body; } template 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 typename C::CType compare(const Code* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(body(), E->body()); } private: SExpr* ReturnType; SExpr* 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; } const SExpr *range() const { return Range; } SExpr *body() { return Body; } const SExpr *body() const { return Body; } template 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 typename C::CType compare(const Field* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(range(), E->range()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(body(), E->body()); } private: SExpr* Range; SExpr* Body; }; /// Apply an argument to a function. /// Note that this does not actually call the function. Functions are curried, /// so this returns a closure in which the first parameter has been applied. /// Once all parameters have been applied, Call can be used to invoke the /// 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; } const SExpr *fun() const { return Fun; } SExpr *arg() { return Arg; } const SExpr *arg() const { return Arg; } template 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 typename C::CType compare(const Apply* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(fun(), E->fun()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(arg(), E->arg()); } private: SExpr* Fun; SExpr* 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; } const SExpr *sfun() const { return Sfun; } SExpr *arg() { return Arg ? Arg : Sfun; } const SExpr *arg() const { return Arg ? Arg : Sfun; } bool isDelegation() const { return Arg != nullptr; } template 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 ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) : nullptr; return Vs.reduceSApply(*this, Nf, Na); } template typename C::CType compare(const SApply* E, C& Cmp) const { 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: SExpr* Sfun; SExpr* 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, const 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; } const SExpr *record() const { return Rec; } const clang::ValueDecl *clangDecl() const { return Cvdecl; } bool isArrow() const { return (Flags & 0x01) != 0; } void setArrow(bool b) { if (b) Flags |= 0x01; else Flags &= 0xFFFE; } StringRef slotName() const { if (Cvdecl) return Cvdecl->getName(); else return SlotName; } template 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 typename C::CType compare(const Project* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(record(), E->record()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.comparePointers(Cvdecl, E->Cvdecl); } private: SExpr* Rec; StringRef SlotName; const 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; } const SExpr *target() const { return Target; } const clang::CallExpr *clangCallExpr() const { return Cexpr; } template 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 typename C::CType compare(const Call* E, C& Cmp) const { return Cmp.compare(target(), E->target()); } private: SExpr* 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(Flags); } SExpr *dataType() { return Dtype; } const SExpr *dataType() const { return Dtype; } template 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 typename C::CType compare(const Alloc* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(dataType(), E->dataType()); } private: SExpr* 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; } const SExpr *pointer() const { return Ptr; } template 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 typename C::CType compare(const Load* E, C& Cmp) const { return Cmp.compare(pointer(), E->pointer()); } private: SExpr* Ptr; }; /// Store a value to memory. /// The destination is a pointer to a field, the source 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; } // Address to store to const SExpr *destination() const { return Dest; } SExpr *source() { return Source; } // Value to store const SExpr *source() const { return Source; } template 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 typename C::CType compare(const Store* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(destination(), E->destination()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(source(), E->source()); } private: SExpr* Dest; SExpr* Source; }; /// If p is a reference to an array, then p[i] is a reference to the i'th /// element of the array. 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; } const SExpr *array() const { return Array; } SExpr *index() { return Index; } const SExpr *index() const { return Index; } template 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 typename C::CType compare(const ArrayIndex* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(array(), E->array()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(index(), E->index()); } private: SExpr* Array; SExpr* 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; } const SExpr *array() const { return Array; } SExpr *index() { return Index; } const SExpr *index() const { return Index; } template 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 typename C::CType compare(const ArrayAdd* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(array(), E->array()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(index(), E->index()); } private: SExpr* Array; SExpr* Index; }; /// Simple arithmetic unary operations, e.g. negate and not. /// These operations have no side-effects. 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(Flags); } SExpr *expr() { return Expr0; } const SExpr *expr() const { return Expr0; } template 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 typename C::CType compare(const UnaryOp* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(expr(), E->expr()); } private: SExpr* Expr0; }; /// Simple arithmetic binary operations, e.g. +, -, etc. /// These operations have no side effects. 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(Flags); } SExpr *expr0() { return Expr0; } const SExpr *expr0() const { return Expr0; } SExpr *expr1() { return Expr1; } const SExpr *expr1() const { return Expr1; } template 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 typename C::CType compare(const BinaryOp* E, C& Cmp) const { 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: SExpr* Expr0; SExpr* Expr1; }; /// Cast expressions. /// Cast expressions are essentially unary operations, but we treat them /// as a distinct AST node because they only change the type of the result. 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(Flags); } SExpr *expr() { return Expr0; } const SExpr *expr() const { return Expr0; } template 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 typename C::CType compare(const Cast* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(castOpcode(), E->castOpcode()); if (Cmp.notTrue(Ct)) return Ct; return Cmp.compare(expr(), E->expr()); } private: SExpr* Expr0; }; class SCFG; /// Phi Node, for code in SSA form. /// Each Phi node has an array of possible values that it can take, /// depending on where control flow comes from. class Phi : public SExpr { public: typedef SimpleArray 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), Cvdecl(nullptr) {} Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {} Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {} const ValArray &values() const { return Values; } ValArray &values() { return Values; } Status status() const { return static_cast(Flags); } void setStatus(Status s) { Flags = s; } /// Return the clang declaration of the variable for this Phi node, if any. const clang::ValueDecl *clangDecl() const { return Cvdecl; } /// Set the clang variable associated with this Phi node. void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; } template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { typename V::template Container Nvs(Vs, Values.size()); for (auto *Val : Values) { Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); } return Vs.reducePhi(*this, Nvs); } template typename C::CType compare(const Phi *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: ValArray Values; const clang::ValueDecl* Cvdecl; }; /// Base class for basic block terminators: Branch, Goto, and Return. class Terminator : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; } protected: Terminator(TIL_Opcode Op) : SExpr(Op) {} Terminator(const SExpr &E) : SExpr(E) {} public: /// Return the list of basic blocks that this terminator can branch to. ArrayRef successors(); ArrayRef successors() const { return const_cast(this)->successors(); } }; /// Jump to another basic block. /// A goto instruction is essentially a tail-recursive call into another /// block. In addition to the block pointer, it specifies an index into the /// phi nodes of that block. The index can be used to retrieve the "arguments" /// of the call. class Goto : public Terminator { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } Goto(BasicBlock *B, unsigned I) : Terminator(COP_Goto), TargetBlock(B), Index(I) {} Goto(const Goto &G, BasicBlock *B, unsigned I) : Terminator(COP_Goto), TargetBlock(B), Index(I) {} const BasicBlock *targetBlock() const { return TargetBlock; } BasicBlock *targetBlock() { return TargetBlock; } /// Returns the index into the unsigned index() const { return Index; } /// Return the list of basic blocks that this terminator can branch to. ArrayRef successors() { return ArrayRef(&TargetBlock, 1); } template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); return Vs.reduceGoto(*this, Ntb); } template typename C::CType compare(const Goto *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: BasicBlock *TargetBlock; unsigned Index; }; /// A conditional branch to two other blocks. /// Note that unlike Goto, Branch does not have an index. The target blocks /// must be child-blocks, and cannot have Phi nodes. class Branch : public Terminator { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } Branch(SExpr *C, BasicBlock *T, BasicBlock *E) : Terminator(COP_Branch), Condition(C) { Branches[0] = T; Branches[1] = E; } Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) : Terminator(Br), Condition(C) { Branches[0] = T; Branches[1] = E; } const SExpr *condition() const { return Condition; } SExpr *condition() { return Condition; } const BasicBlock *thenBlock() const { return Branches[0]; } BasicBlock *thenBlock() { return Branches[0]; } const BasicBlock *elseBlock() const { return Branches[1]; } BasicBlock *elseBlock() { return Branches[1]; } /// Return the list of basic blocks that this terminator can branch to. ArrayRef successors() { return ArrayRef(Branches, 2); } template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); return Vs.reduceBranch(*this, Nc, Ntb, Nte); } template typename C::CType compare(const Branch *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: SExpr* Condition; BasicBlock *Branches[2]; }; /// Return from the enclosing function, passing the return value to the caller. /// Only the exit block should end with a return statement. class Return : public Terminator { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} /// Return an empty list. ArrayRef successors() { return ArrayRef(); } SExpr *returnValue() { return Retval; } const SExpr *returnValue() const { return Retval; } template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); return Vs.reduceReturn(*this, Ne); } template typename C::CType compare(const Return *E, C &Cmp) const { return Cmp.compare(Retval, E->Retval); } private: SExpr* Retval; }; inline ArrayRef Terminator::successors() { switch (opcode()) { case COP_Goto: return cast(this)->successors(); case COP_Branch: return cast(this)->successors(); case COP_Return: return cast(this)->successors(); default: return ArrayRef(); } } /// A basic block is part of an SCFG. It can be treated as a function in /// continuation passing style. A block consists of a sequence of phi nodes, /// which are "arguments" to the function, followed by a sequence of /// instructions. It ends with a Terminator, which is a Branch or Goto to /// another basic block in the same SCFG. class BasicBlock : public SExpr { public: typedef SimpleArray InstrArray; typedef SimpleArray BlockArray; // TopologyNodes are used to overlay tree structures on top of the CFG, // such as dominator and postdominator trees. Each block is assigned an // ID in the tree according to a depth-first search. Tree traversals are // always up, towards the parents. struct TopologyNode { TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {} bool isParentOf(const TopologyNode& OtherNode) { return OtherNode.NodeID > NodeID && OtherNode.NodeID < NodeID + SizeOfSubTree; } bool isParentOfOrEqual(const TopologyNode& OtherNode) { return OtherNode.NodeID >= NodeID && OtherNode.NodeID < NodeID + SizeOfSubTree; } int NodeID; int SizeOfSubTree; // Includes this node, so must be > 1. BasicBlock *Parent; // Pointer to parent. }; static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } explicit BasicBlock(MemRegionRef A) : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), Visited(0), TermInstr(nullptr) {} BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, Terminator *T) : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0), Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} /// Returns the block ID. Every block has a unique ID in the CFG. int blockID() const { return BlockID; } /// Returns the number of predecessors. size_t numPredecessors() const { return Predecessors.size(); } size_t numSuccessors() const { return successors().size(); } const SCFG* cfg() const { return CFGPtr; } SCFG* cfg() { return CFGPtr; } const BasicBlock *parent() const { return DominatorNode.Parent; } BasicBlock *parent() { return DominatorNode.Parent; } const InstrArray &arguments() const { return Args; } InstrArray &arguments() { return Args; } InstrArray &instructions() { return Instrs; } const InstrArray &instructions() const { return Instrs; } /// Returns a list of predecessors. /// The order of predecessors in the list is important; each phi node has /// exactly one argument for each precessor, in the same order. BlockArray &predecessors() { return Predecessors; } const BlockArray &predecessors() const { return Predecessors; } ArrayRef successors() { return TermInstr->successors(); } ArrayRef successors() const { return TermInstr->successors(); } const Terminator *terminator() const { return TermInstr; } Terminator *terminator() { return TermInstr; } void setTerminator(Terminator *E) { TermInstr = E; } bool Dominates(const BasicBlock &Other) { return DominatorNode.isParentOfOrEqual(Other.DominatorNode); } bool PostDominates(const BasicBlock &Other) { return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); } /// Add a new argument. void addArgument(Phi *V) { Args.reserveCheck(1, Arena); Args.push_back(V); } /// Add a new instruction. void addInstruction(SExpr *V) { 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); } template typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { typename V::template Container Nas(Vs, Args.size()); typename V::template Container Nis(Vs, Instrs.size()); // Entering the basic block should do any scope initialization. Vs.enterBasicBlock(*this); for (auto *E : Args) { auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); Nas.push_back(Ne); } for (auto *E : Instrs) { auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); Nis.push_back(Ne); } auto Nt = Vs.traverse(TermInstr, Ctx); // Exiting the basic block should handle any scope cleanup. Vs.exitBasicBlock(*this); return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); } template typename C::CType compare(const BasicBlock *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: friend class SCFG; int renumberInstrs(int id); // assign unique ids to all instructions int topologicalSort(SimpleArray& Blocks, int ID); int topologicalFinalSort(SimpleArray& Blocks, int ID); void computeDominator(); void computePostDominator(); private: MemRegionRef Arena; // The arena used to allocate this block. SCFG *CFGPtr; // The CFG that contains this block. int BlockID : 31; // unique id for this BB in the containing CFG. // IDs are in topological order. bool Visited : 1; // Bit to determine if a block has been visited // during a traversal. BlockArray Predecessors; // Predecessor blocks in the CFG. InstrArray Args; // Phi nodes. One argument per predecessor. InstrArray Instrs; // Instructions. Terminator* TermInstr; // Terminating instruction TopologyNode DominatorNode; // The dominator tree TopologyNode PostDominatorNode; // The post-dominator tree }; /// 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 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), NumInstructions(0), Normal(false) { Entry = new (A) BasicBlock(A); Exit = new (A) BasicBlock(A); auto *V = new (A) Phi(); Exit->addArgument(V); Exit->setTerminator(new (A) Return(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), NumInstructions(0), Normal(false) { // TODO: set entry and exit! } /// Return true if this CFG is valid. bool valid() const { return Entry && Exit && Blocks.size() > 0; } /// Return true if this CFG has been normalized. /// After normalization, blocks are in topological order, and block and /// instruction IDs have been assigned. bool normal() const { return Normal; } 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; } /// Return the number of blocks in the CFG. /// Block::blockID() will return a number less than numBlocks(); size_t numBlocks() const { return Blocks.size(); } /// Return the total number of instructions in the CFG. /// This is useful for building instruction side-tables; /// A call to SExpr::id() will return a number less than numInstructions(). unsigned numInstructions() { return NumInstructions; } inline void add(BasicBlock *BB) { assert(BB->CFGPtr == nullptr); BB->CFGPtr = this; Blocks.reserveCheck(1, Arena); Blocks.push_back(BB); } void setEntry(BasicBlock *BB) { Entry = BB; } void setExit(BasicBlock *BB) { Exit = BB; } void computeNormalForm(); template typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { Vs.enterCFG(*this); typename V::template Container 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 typename C::CType compare(const SCFG *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: void renumberInstrs(); // assign unique ids to all instructions private: MemRegionRef Arena; BlockArray Blocks; BasicBlock *Entry; BasicBlock *Exit; unsigned NumInstructions; bool Normal; }; /// 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 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { return Vs.reduceIdentifier(*this); } template typename C::CType compare(const Identifier* E, C& Cmp) const { 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; } // Address to store to const SExpr *condition() const { return Condition; } SExpr *thenExpr() { return ThenExpr; } // Value to store const SExpr *thenExpr() const { return ThenExpr; } SExpr *elseExpr() { return ElseExpr; } // Value to store const SExpr *elseExpr() const { return ElseExpr; } template 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 typename C::CType compare(const IfThenElse* E, C& Cmp) const { 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: SExpr* Condition; SExpr* ThenExpr; SExpr* 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; } const SExpr *body() const { return Body; } template 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 typename C::CType compare(const Let* E, C& Cmp) const { 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; SExpr* Body; }; const SExpr *getCanonicalVal(const SExpr *E); SExpr* simplifyToCanonicalVal(SExpr *E); void simplifyIncompleteArg(til::Phi *Ph); } // end namespace til } // end namespace threadSafety } // end namespace clang #endif