1 //===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT in the llvm repository for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a simple Typed Intermediate Language, or TIL, that is used
11 // by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended
12 // to be largely independent of clang, in the hope that the analysis can be
13 // reused for other non-C++ languages. All dependencies on clang/llvm should
14 // go in ThreadSafetyUtil.h.
16 // Thread safety analysis works by comparing mutex expressions, e.g.
18 // class A { Mutex mu; int dat GUARDED_BY(this->mu); }
22 // (*b).a.mu.lock(); // locks (*b).a.mu
23 // b->a.dat = 0; // substitute &b->a for 'this';
24 // // requires lock on (&b->a)->mu
25 // (b->a.mu).unlock(); // unlocks (b->a.mu)
28 // As illustrated by the above example, clang Exprs are not well-suited to
29 // represent mutex expressions directly, since there is no easy way to compare
30 // Exprs for equivalence. The thread safety analysis thus lowers clang Exprs
31 // into a simple intermediate language (IL). The IL supports:
33 // (1) comparisons for semantic equality of expressions
34 // (2) SSA renaming of variables
35 // (3) wildcards and pattern matching over expressions
36 // (4) hash-based expression lookup
38 // The TIL is currently very experimental, is intended only for use within
39 // the thread safety analysis, and is subject to change without notice.
40 // After the API stabilizes and matures, it may be appropriate to make this
41 // more generally available to other analyses.
43 // UNDER CONSTRUCTION. USE AT YOUR OWN RISK.
45 //===----------------------------------------------------------------------===//
47 #ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H
48 #define LLVM_CLANG_THREAD_SAFETY_TIL_H
50 // All clang include dependencies for this file must be put in
51 // ThreadSafetyUtil.h.
52 #include "ThreadSafetyUtil.h"
62 namespace threadSafety {
67 #define TIL_OPCODE_DEF(X) COP_##X,
68 #include "ThreadSafetyOps.def"
72 enum TIL_UnaryOpcode : unsigned char {
78 enum TIL_BinaryOpcode : unsigned char {
97 enum TIL_CastOpcode : unsigned char {
99 CAST_extendNum, // extend precision of numeric type
100 CAST_truncNum, // truncate precision of numeric type
101 CAST_toFloat, // convert to floating point type
102 CAST_toInt, // convert to integer type
105 const TIL_Opcode COP_Min = COP_Future;
106 const TIL_Opcode COP_Max = COP_Branch;
107 const TIL_UnaryOpcode UOP_Min = UOP_Minus;
108 const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
109 const TIL_BinaryOpcode BOP_Min = BOP_Mul;
110 const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
111 const TIL_CastOpcode CAST_Min = CAST_none;
112 const TIL_CastOpcode CAST_Max = CAST_toInt;
114 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
115 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
118 // ValueTypes are data types that can actually be held in registers.
119 // All variables and expressions must have a vBNF_Nonealue type.
120 // Pointer types are further subdivided into the various heap-allocated
121 // types, such as functions, records, etc.
122 // Structured types that are passed by value (e.g. complex numbers)
123 // require special handling; they use BT_ValueRef, and size ST_0.
125 enum BaseType : unsigned char {
130 BT_String, // String literals
135 enum SizeType : unsigned char {
145 inline static SizeType getSizeType(unsigned nbytes);
148 inline static ValueType getValueType();
150 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
151 : Base(B), Size(Sz), Signed(S), VectSize(VS)
157 unsigned char VectSize; // 0 for scalar, otherwise num elements in vector
161 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
164 case 2: return ST_16;
165 case 4: return ST_32;
166 case 8: return ST_64;
167 case 16: return ST_128;
168 default: return ST_0;
174 inline ValueType ValueType::getValueType<void>() {
175 return ValueType(BT_Void, ST_0, false, 0);
179 inline ValueType ValueType::getValueType<bool>() {
180 return ValueType(BT_Bool, ST_1, false, 0);
184 inline ValueType ValueType::getValueType<int8_t>() {
185 return ValueType(BT_Int, ST_8, true, 0);
189 inline ValueType ValueType::getValueType<uint8_t>() {
190 return ValueType(BT_Int, ST_8, false, 0);
194 inline ValueType ValueType::getValueType<int16_t>() {
195 return ValueType(BT_Int, ST_16, true, 0);
199 inline ValueType ValueType::getValueType<uint16_t>() {
200 return ValueType(BT_Int, ST_16, false, 0);
204 inline ValueType ValueType::getValueType<int32_t>() {
205 return ValueType(BT_Int, ST_32, true, 0);
209 inline ValueType ValueType::getValueType<uint32_t>() {
210 return ValueType(BT_Int, ST_32, false, 0);
214 inline ValueType ValueType::getValueType<int64_t>() {
215 return ValueType(BT_Int, ST_64, true, 0);
219 inline ValueType ValueType::getValueType<uint64_t>() {
220 return ValueType(BT_Int, ST_64, false, 0);
224 inline ValueType ValueType::getValueType<float>() {
225 return ValueType(BT_Float, ST_32, true, 0);
229 inline ValueType ValueType::getValueType<double>() {
230 return ValueType(BT_Float, ST_64, true, 0);
234 inline ValueType ValueType::getValueType<long double>() {
235 return ValueType(BT_Float, ST_128, true, 0);
239 inline ValueType ValueType::getValueType<StringRef>() {
240 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
244 inline ValueType ValueType::getValueType<void*>() {
245 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
250 // Base class for AST nodes in the typed intermediate language.
253 TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
255 // Subclasses of SExpr must define the following:
257 // This(const This& E, ...) {
258 // copy constructor: construct copy of E, with some additional arguments.
261 // template <class V>
262 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
263 // traverse all subexpressions, following the traversal/rewriter interface.
266 // template <class C> typename C::CType compare(CType* E, C& Cmp) {
267 // compare all subexpressions, following the comparator interface
270 void *operator new(size_t S, MemRegionRef &R) {
271 return ::operator new(S, R);
274 // SExpr objects cannot be deleted.
275 // This declaration is public to workaround a gcc bug that breaks building
276 // with REQUIRES_EH=1.
277 void operator delete(void *) LLVM_DELETED_FUNCTION;
280 SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {}
281 SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {}
283 const unsigned char Opcode;
284 unsigned char Reserved;
285 unsigned short Flags;
288 SExpr() LLVM_DELETED_FUNCTION;
290 // SExpr objects must be created in an arena.
291 void *operator new(size_t) LLVM_DELETED_FUNCTION;
295 // Class for owning references to SExprs.
296 // Includes attach/detach logic for counting variable references and lazy
297 // rewriting strategies.
300 SExprRef() : Ptr(nullptr) { }
301 SExprRef(std::nullptr_t P) : Ptr(nullptr) { }
302 SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; }
304 // Defined after Variable and Future, below.
305 inline SExprRef(SExpr *P);
308 SExpr *get() { return Ptr; }
309 const SExpr *get() const { return Ptr; }
311 SExpr *operator->() { return get(); }
312 const SExpr *operator->() const { return get(); }
314 SExpr &operator*() { return *Ptr; }
315 const SExpr &operator*() const { return *Ptr; }
317 bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; }
318 bool operator!=(const SExprRef &R) const { return !operator==(R); }
319 bool operator==(const SExpr *P) const { return Ptr == P; }
320 bool operator!=(const SExpr *P) const { return !operator==(P); }
321 bool operator==(std::nullptr_t) const { return Ptr == nullptr; }
322 bool operator!=(std::nullptr_t) const { return Ptr != nullptr; }
324 inline void reset(SExpr *E);
327 inline void attach();
328 inline void detach();
334 // Contains various helper functions for SExprs.
335 namespace ThreadSafetyTIL {
336 inline bool isTrivial(const SExpr *E) {
337 unsigned Op = E->opcode();
338 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
342 // Nodes which declare variables
349 // A named variable, e.g. "x".
351 // There are two distinct places in which a Variable can appear in the AST.
352 // A variable declaration introduces a new variable, and can occur in 3 places:
353 // Let-expressions: (Let (x = t) u)
354 // Functions: (Function (x : t) u)
355 // Self-applicable functions (SFunction (x) t)
357 // If a variable occurs in any other location, it is a reference to an existing
358 // variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
359 // allocate a separate AST node for variable references; a reference is just a
360 // pointer to the original declaration.
361 class Variable : public SExpr {
363 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
365 // Let-variable, function parameter, or self-variable
373 // These are defined after SExprRef contructor, below
374 inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr);
375 inline Variable(StringRef s, SExpr *D = nullptr);
376 inline Variable(const Variable &Vd, SExpr *D);
378 VariableKind kind() const { return static_cast<VariableKind>(Flags); }
380 const StringRef name() const { return Name; }
381 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
383 // Returns the definition (for let vars) or type (for parameter & self vars)
384 SExpr *definition() { return Definition.get(); }
385 const SExpr *definition() const { return Definition.get(); }
387 void attachVar() const { ++NumUses; }
388 void detachVar() const { assert(NumUses > 0); --NumUses; }
390 unsigned getID() const { return Id; }
391 unsigned getBlockID() const { return BlockID; }
393 void setName(StringRef S) { Name = S; }
394 void setID(unsigned Bid, unsigned I) {
395 BlockID = static_cast<unsigned short>(Bid);
396 Id = static_cast<unsigned short>(I);
398 void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
399 void setDefinition(SExpr *E);
400 void setKind(VariableKind K) { Flags = K; }
403 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
404 // This routine is only called for variable references.
405 return Vs.reduceVariableRef(this);
408 template <class C> typename C::CType compare(Variable* E, C& Cmp) {
409 return Cmp.compareVariableRefs(this, E);
413 friend class Function;
414 friend class SFunction;
415 friend class BasicBlock;
418 StringRef Name; // The name of the variable.
419 SExprRef Definition; // The TIL type or definition
420 const clang::ValueDecl *Cvdecl; // The clang declaration for this variable.
422 unsigned short BlockID;
424 mutable unsigned NumUses;
428 // Placeholder for an expression that has not yet been created.
429 // Used to implement lazy copy and rewriting strategies.
430 class Future : public SExpr {
432 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
441 SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr)
444 virtual ~Future() LLVM_DELETED_FUNCTION;
447 // Registers the location in the AST where this future is stored.
448 // Forcing the future will automatically update the AST.
449 static inline void registerLocation(SExprRef *Member) {
450 if (Future *F = dyn_cast_or_null<Future>(Member->get()))
451 F->Location = Member;
454 // A lazy rewriting strategy should subclass Future and override this method.
455 virtual SExpr *create() { return nullptr; }
457 // Return the result of this future if it exists, otherwise return null.
458 SExpr *maybeGetResult() {
462 // Return the result of this future; forcing it if necessary.
469 return nullptr; // infinite loop; illegal recursion.
476 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
477 assert(Result && "Cannot traverse Future that has not been forced.");
478 return Vs.traverse(Result, Ctx);
481 template <class C> typename C::CType compare(Future* E, C& Cmp) {
482 if (!Result || !E->Result)
483 return Cmp.comparePointers(this, E);
484 return Cmp.compare(Result, E->Result);
497 inline void SExprRef::attach() {
501 TIL_Opcode Op = Ptr->opcode();
502 if (Op == COP_Variable) {
503 cast<Variable>(Ptr)->attachVar();
504 } else if (Op == COP_Future) {
505 cast<Future>(Ptr)->registerLocation(this);
509 inline void SExprRef::detach() {
510 if (Ptr && Ptr->opcode() == COP_Variable) {
511 cast<Variable>(Ptr)->detachVar();
515 inline SExprRef::SExprRef(SExpr *P) : Ptr(P) {
519 inline SExprRef::~SExprRef() {
523 inline void SExprRef::reset(SExpr *P) {
530 inline Variable::Variable(StringRef s, SExpr *D)
531 : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr),
532 BlockID(0), Id(0), NumUses(0) {
536 inline Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd)
537 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
538 Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) {
542 inline Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor
543 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl),
544 BlockID(0), Id(0), NumUses(0) {
548 inline void Variable::setDefinition(SExpr *E) {
552 void Future::force() {
553 Status = FS_evaluating;
562 // Placeholder for C++ expressions that cannot be represented in the TIL.
563 class Undefined : public SExpr {
565 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
567 Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
568 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
571 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
572 return Vs.reduceUndefined(*this);
575 template <class C> typename C::CType compare(Undefined* E, C& Cmp) {
576 return Cmp.comparePointers(Cstmt, E->Cstmt);
580 const clang::Stmt *Cstmt;
584 // Placeholder for a wildcard that matches any other expression.
585 class Wildcard : public SExpr {
587 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
589 Wildcard() : SExpr(COP_Wildcard) {}
590 Wildcard(const Wildcard &W) : SExpr(W) {}
592 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
593 return Vs.reduceWildcard(*this);
596 template <class C> typename C::CType compare(Wildcard* E, C& Cmp) {
597 return Cmp.trueResult();
602 template <class T> class LiteralT;
604 // Base class for literal values.
605 class Literal : public SExpr {
607 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
609 Literal(const clang::Expr *C)
610 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
612 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
613 Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
615 // The clang expression for this literal.
616 const clang::Expr *clangExpr() const { return Cexpr; }
618 ValueType valueType() const { return ValType; }
620 template<class T> const LiteralT<T>& as() const {
621 return *static_cast<const LiteralT<T>*>(this);
623 template<class T> LiteralT<T>& as() {
624 return *static_cast<LiteralT<T>*>(this);
627 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
629 template <class C> typename C::CType compare(Literal* E, C& Cmp) {
630 // TODO -- use value, not pointer equality
631 return Cmp.comparePointers(Cexpr, E->Cexpr);
635 const ValueType ValType;
636 const clang::Expr *Cexpr;
640 // Derived class for literal values, which stores the actual value.
642 class LiteralT : public Literal {
644 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
645 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
647 T value() const { return Val;}
648 T& value() { return Val; }
657 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
659 return Vs.reduceLiteral(*this);
661 switch (ValType.Base) {
662 case ValueType::BT_Void:
664 case ValueType::BT_Bool:
665 return Vs.reduceLiteralT(as<bool>());
666 case ValueType::BT_Int: {
667 switch (ValType.Size) {
668 case ValueType::ST_8:
670 return Vs.reduceLiteralT(as<int8_t>());
672 return Vs.reduceLiteralT(as<uint8_t>());
673 case ValueType::ST_16:
675 return Vs.reduceLiteralT(as<int16_t>());
677 return Vs.reduceLiteralT(as<uint16_t>());
678 case ValueType::ST_32:
680 return Vs.reduceLiteralT(as<int32_t>());
682 return Vs.reduceLiteralT(as<uint32_t>());
683 case ValueType::ST_64:
685 return Vs.reduceLiteralT(as<int64_t>());
687 return Vs.reduceLiteralT(as<uint64_t>());
692 case ValueType::BT_Float: {
693 switch (ValType.Size) {
694 case ValueType::ST_32:
695 return Vs.reduceLiteralT(as<float>());
696 case ValueType::ST_64:
697 return Vs.reduceLiteralT(as<double>());
702 case ValueType::BT_String:
703 return Vs.reduceLiteralT(as<StringRef>());
704 case ValueType::BT_Pointer:
705 return Vs.reduceLiteralT(as<void*>());
706 case ValueType::BT_ValueRef:
709 return Vs.reduceLiteral(*this);
713 // Literal pointer to an object allocated in memory.
714 // At compile time, pointer literals are represented by symbolic names.
715 class LiteralPtr : public SExpr {
717 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
719 LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
720 LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
722 // The clang declaration for the value that this pointer points to.
723 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
726 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
727 return Vs.reduceLiteralPtr(*this);
730 template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) {
731 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
735 const clang::ValueDecl *Cvdecl;
739 // A function -- a.k.a. lambda abstraction.
740 // Functions with multiple arguments are created by currying,
741 // e.g. (function (x: Int) (function (y: Int) (add x y)))
742 class Function : public SExpr {
744 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
746 Function(Variable *Vd, SExpr *Bd)
747 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
748 Vd->setKind(Variable::VK_Fun);
750 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
751 : SExpr(F), VarDecl(Vd), Body(Bd) {
752 Vd->setKind(Variable::VK_Fun);
755 Variable *variableDecl() { return VarDecl; }
756 const Variable *variableDecl() const { return VarDecl; }
758 SExpr *body() { return Body.get(); }
759 const SExpr *body() const { return Body.get(); }
762 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
763 // This is a variable declaration, so traverse the definition.
764 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
765 // Tell the rewriter to enter the scope of the function.
766 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
767 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
768 Vs.exitScope(*VarDecl);
769 return Vs.reduceFunction(*this, Nvd, E1);
772 template <class C> typename C::CType compare(Function* E, C& Cmp) {
773 typename C::CType Ct =
774 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
777 Cmp.enterScope(variableDecl(), E->variableDecl());
778 Ct = Cmp.compare(body(), E->body());
789 // A self-applicable function.
790 // A self-applicable function can be applied to itself. It's useful for
791 // implementing objects and late binding
792 class SFunction : public SExpr {
794 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
796 SFunction(Variable *Vd, SExpr *B)
797 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
798 assert(Vd->Definition == nullptr);
799 Vd->setKind(Variable::VK_SFun);
800 Vd->Definition.reset(this);
802 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
803 : SExpr(F), VarDecl(Vd), Body(B) {
804 assert(Vd->Definition == nullptr);
805 Vd->setKind(Variable::VK_SFun);
806 Vd->Definition.reset(this);
809 Variable *variableDecl() { return VarDecl; }
810 const Variable *variableDecl() const { return VarDecl; }
812 SExpr *body() { return Body.get(); }
813 const SExpr *body() const { return Body.get(); }
816 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
817 // A self-variable points to the SFunction itself.
818 // A rewrite must introduce the variable with a null definition, and update
819 // it after 'this' has been rewritten.
820 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
821 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
822 Vs.exitScope(*VarDecl);
823 // A rewrite operation will call SFun constructor to set Vvd->Definition.
824 return Vs.reduceSFunction(*this, Nvd, E1);
827 template <class C> typename C::CType compare(SFunction* E, C& Cmp) {
828 Cmp.enterScope(variableDecl(), E->variableDecl());
829 typename C::CType Ct = Cmp.compare(body(), E->body());
840 // A block of code -- e.g. the body of a function.
841 class Code : public SExpr {
843 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
845 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
846 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
847 : SExpr(C), ReturnType(T), Body(B) {}
849 SExpr *returnType() { return ReturnType.get(); }
850 const SExpr *returnType() const { return ReturnType.get(); }
852 SExpr *body() { return Body.get(); }
853 const SExpr *body() const { return Body.get(); }
856 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
857 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
858 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
859 return Vs.reduceCode(*this, Nt, Nb);
862 template <class C> typename C::CType compare(Code* E, C& Cmp) {
863 typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
866 return Cmp.compare(body(), E->body());
875 // A typed, writable location in memory
876 class Field : public SExpr {
878 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
880 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
881 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
882 : SExpr(C), Range(R), Body(B) {}
884 SExpr *range() { return Range.get(); }
885 const SExpr *range() const { return Range.get(); }
887 SExpr *body() { return Body.get(); }
888 const SExpr *body() const { return Body.get(); }
891 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
892 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
893 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
894 return Vs.reduceField(*this, Nr, Nb);
897 template <class C> typename C::CType compare(Field* E, C& Cmp) {
898 typename C::CType Ct = Cmp.compare(range(), E->range());
901 return Cmp.compare(body(), E->body());
910 // Apply an argument to a function
911 class Apply : public SExpr {
913 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
915 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
916 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
917 : SExpr(A), Fun(F), Arg(Ar)
920 SExpr *fun() { return Fun.get(); }
921 const SExpr *fun() const { return Fun.get(); }
923 SExpr *arg() { return Arg.get(); }
924 const SExpr *arg() const { return Arg.get(); }
927 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
928 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
929 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
930 return Vs.reduceApply(*this, Nf, Na);
933 template <class C> typename C::CType compare(Apply* E, C& Cmp) {
934 typename C::CType Ct = Cmp.compare(fun(), E->fun());
937 return Cmp.compare(arg(), E->arg());
946 // Apply a self-argument to a self-applicable function
947 class SApply : public SExpr {
949 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
951 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
952 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
953 : SExpr(A), Sfun(Sf), Arg(Ar) {}
955 SExpr *sfun() { return Sfun.get(); }
956 const SExpr *sfun() const { return Sfun.get(); }
958 SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); }
959 const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); }
961 bool isDelegation() const { return Arg == nullptr; }
964 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
965 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
966 typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
968 return Vs.reduceSApply(*this, Nf, Na);
971 template <class C> typename C::CType compare(SApply* E, C& Cmp) {
972 typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
973 if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
975 return Cmp.compare(arg(), E->arg());
984 // Project a named slot from a C++ struct or class.
985 class Project : public SExpr {
987 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
989 Project(SExpr *R, StringRef SName)
990 : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
992 Project(SExpr *R, clang::ValueDecl *Cvd)
993 : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
995 Project(const Project &P, SExpr *R)
996 : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
999 SExpr *record() { return Rec.get(); }
1000 const SExpr *record() const { return Rec.get(); }
1002 const clang::ValueDecl *clangValueDecl() const { return Cvdecl; }
1004 StringRef slotName() const {
1006 return Cvdecl->getName();
1012 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1013 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
1014 return Vs.reduceProject(*this, Nr);
1017 template <class C> typename C::CType compare(Project* E, C& Cmp) {
1018 typename C::CType Ct = Cmp.compare(record(), E->record());
1019 if (Cmp.notTrue(Ct))
1021 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
1027 clang::ValueDecl *Cvdecl;
1031 // Call a function (after all arguments have been applied).
1032 class Call : public SExpr {
1034 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1036 Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
1037 : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
1038 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
1040 SExpr *target() { return Target.get(); }
1041 const SExpr *target() const { return Target.get(); }
1043 const clang::CallExpr *clangCallExpr() const { return Cexpr; }
1046 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1047 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
1048 return Vs.reduceCall(*this, Nt);
1051 template <class C> typename C::CType compare(Call* E, C& Cmp) {
1052 return Cmp.compare(target(), E->target());
1057 const clang::CallExpr *Cexpr;
1061 // Allocate memory for a new value on the heap or stack.
1062 class Alloc : public SExpr {
1064 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1071 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1072 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1074 AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1076 SExpr *dataType() { return Dtype.get(); }
1077 const SExpr *dataType() const { return Dtype.get(); }
1080 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1081 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1082 return Vs.reduceAlloc(*this, Nd);
1085 template <class C> typename C::CType compare(Alloc* E, C& Cmp) {
1086 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1087 if (Cmp.notTrue(Ct))
1089 return Cmp.compare(dataType(), E->dataType());
1097 // Load a value from memory.
1098 class Load : public SExpr {
1100 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1102 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1103 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1105 SExpr *pointer() { return Ptr.get(); }
1106 const SExpr *pointer() const { return Ptr.get(); }
1109 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1110 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1111 return Vs.reduceLoad(*this, Np);
1114 template <class C> typename C::CType compare(Load* E, C& Cmp) {
1115 return Cmp.compare(pointer(), E->pointer());
1123 // Store a value to memory.
1124 // Source is a pointer, destination is the value to store.
1125 class Store : public SExpr {
1127 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1129 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1130 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1132 SExpr *destination() { return Dest.get(); } // Address to store to
1133 const SExpr *destination() const { return Dest.get(); }
1135 SExpr *source() { return Source.get(); } // Value to store
1136 const SExpr *source() const { return Source.get(); }
1139 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1140 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
1141 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1142 return Vs.reduceStore(*this, Np, Nv);
1145 template <class C> typename C::CType compare(Store* E, C& Cmp) {
1146 typename C::CType Ct = Cmp.compare(destination(), E->destination());
1147 if (Cmp.notTrue(Ct))
1149 return Cmp.compare(source(), E->source());
1158 // If p is a reference to an array, then first(p) is a reference to the first
1159 // element. The usual array notation p[i] becomes first(p + i).
1160 class ArrayIndex : public SExpr {
1162 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1164 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1165 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1166 : SExpr(E), Array(A), Index(N) {}
1168 SExpr *array() { return Array.get(); }
1169 const SExpr *array() const { return Array.get(); }
1171 SExpr *index() { return Index.get(); }
1172 const SExpr *index() const { return Index.get(); }
1175 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1176 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1177 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1178 return Vs.reduceArrayIndex(*this, Na, Ni);
1181 template <class C> typename C::CType compare(ArrayIndex* E, C& Cmp) {
1182 typename C::CType Ct = Cmp.compare(array(), E->array());
1183 if (Cmp.notTrue(Ct))
1185 return Cmp.compare(index(), E->index());
1194 // Pointer arithmetic, restricted to arrays only.
1195 // If p is a reference to an array, then p + n, where n is an integer, is
1196 // a reference to a subarray.
1197 class ArrayAdd : public SExpr {
1199 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1201 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1202 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1203 : SExpr(E), Array(A), Index(N) {}
1205 SExpr *array() { return Array.get(); }
1206 const SExpr *array() const { return Array.get(); }
1208 SExpr *index() { return Index.get(); }
1209 const SExpr *index() const { return Index.get(); }
1212 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1213 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1214 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1215 return Vs.reduceArrayAdd(*this, Na, Ni);
1218 template <class C> typename C::CType compare(ArrayAdd* E, C& Cmp) {
1219 typename C::CType Ct = Cmp.compare(array(), E->array());
1220 if (Cmp.notTrue(Ct))
1222 return Cmp.compare(index(), E->index());
1231 // Simple unary operation -- e.g. !, ~, etc.
1232 class UnaryOp : public SExpr {
1234 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1236 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1239 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1241 TIL_UnaryOpcode unaryOpcode() const {
1242 return static_cast<TIL_UnaryOpcode>(Flags);
1245 SExpr *expr() { return Expr0.get(); }
1246 const SExpr *expr() const { return Expr0.get(); }
1249 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1250 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1251 return Vs.reduceUnaryOp(*this, Ne);
1254 template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) {
1255 typename C::CType Ct =
1256 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1257 if (Cmp.notTrue(Ct))
1259 return Cmp.compare(expr(), E->expr());
1267 // Simple binary operation -- e.g. +, -, etc.
1268 class BinaryOp : public SExpr {
1270 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1272 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1273 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1276 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1277 : SExpr(B), Expr0(E0), Expr1(E1) {
1281 TIL_BinaryOpcode binaryOpcode() const {
1282 return static_cast<TIL_BinaryOpcode>(Flags);
1285 SExpr *expr0() { return Expr0.get(); }
1286 const SExpr *expr0() const { return Expr0.get(); }
1288 SExpr *expr1() { return Expr1.get(); }
1289 const SExpr *expr1() const { return Expr1.get(); }
1292 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1293 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1294 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1295 return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1298 template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) {
1299 typename C::CType Ct =
1300 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1301 if (Cmp.notTrue(Ct))
1303 Ct = Cmp.compare(expr0(), E->expr0());
1304 if (Cmp.notTrue(Ct))
1306 return Cmp.compare(expr1(), E->expr1());
1316 class Cast : public SExpr {
1318 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1320 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1321 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1323 TIL_CastOpcode castOpcode() const {
1324 return static_cast<TIL_CastOpcode>(Flags);
1327 SExpr *expr() { return Expr0.get(); }
1328 const SExpr *expr() const { return Expr0.get(); }
1331 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1332 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1333 return Vs.reduceCast(*this, Ne);
1336 template <class C> typename C::CType compare(Cast* E, C& Cmp) {
1337 typename C::CType Ct =
1338 Cmp.compareIntegers(castOpcode(), E->castOpcode());
1339 if (Cmp.notTrue(Ct))
1341 return Cmp.compare(expr(), E->expr());
1352 class Phi : public SExpr {
1354 // TODO: change to SExprRef
1355 typedef SimpleArray<SExpr *> ValArray;
1357 // In minimal SSA form, all Phi nodes are MultiVal.
1358 // During conversion to SSA, incomplete Phi nodes may be introduced, which
1359 // are later determined to be SingleVal, and are thus redundant.
1361 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
1362 PH_SingleVal, // Phi node has one distinct value, and can be eliminated
1363 PH_Incomplete // Phi node is incomplete
1366 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1368 Phi() : SExpr(COP_Phi) {}
1369 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1370 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1372 const ValArray &values() const { return Values; }
1373 ValArray &values() { return Values; }
1375 Status status() const { return static_cast<Status>(Flags); }
1376 void setStatus(Status s) { Flags = s; }
1379 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1380 typename V::template Container<typename V::R_SExpr>
1381 Nvs(Vs, Values.size());
1383 for (auto *Val : Values) {
1384 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1386 return Vs.reducePhi(*this, Nvs);
1389 template <class C> typename C::CType compare(Phi *E, C &Cmp) {
1390 // TODO: implement CFG comparisons
1391 return Cmp.comparePointers(this, E);
1399 // A basic block is part of an SCFG, and can be treated as a function in
1400 // continuation passing style. It consists of a sequence of phi nodes, which
1401 // are "arguments" to the function, followed by a sequence of instructions.
1402 // Both arguments and instructions define new variables. It ends with a
1403 // branch or goto to another basic block in the same SCFG.
1404 class BasicBlock : public SExpr {
1406 typedef SimpleArray<Variable*> VarArray;
1407 typedef SimpleArray<BasicBlock*> BlockArray;
1409 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1411 explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr)
1412 : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),
1413 Parent(P), Terminator(nullptr)
1415 BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T)
1416 : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0),
1417 Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)),
1421 unsigned blockID() const { return BlockID; }
1422 unsigned numPredecessors() const { return Predecessors.size(); }
1424 const SCFG* cfg() const { return CFGPtr; }
1425 SCFG* cfg() { return CFGPtr; }
1427 const BasicBlock *parent() const { return Parent; }
1428 BasicBlock *parent() { return Parent; }
1430 const VarArray &arguments() const { return Args; }
1431 VarArray &arguments() { return Args; }
1433 const VarArray &instructions() const { return Instrs; }
1434 VarArray &instructions() { return Instrs; }
1436 const BlockArray &predecessors() const { return Predecessors; }
1437 BlockArray &predecessors() { return Predecessors; }
1439 const SExpr *terminator() const { return Terminator.get(); }
1440 SExpr *terminator() { return Terminator.get(); }
1442 void setBlockID(unsigned i) { BlockID = i; }
1443 void setParent(BasicBlock *P) { Parent = P; }
1444 void setTerminator(SExpr *E) { Terminator.reset(E); }
1446 // Add a new argument. V must define a phi-node.
1447 void addArgument(Variable *V) {
1448 V->setKind(Variable::VK_LetBB);
1449 Args.reserveCheck(1, Arena);
1452 // Add a new instruction.
1453 void addInstruction(Variable *V) {
1454 V->setKind(Variable::VK_LetBB);
1455 Instrs.reserveCheck(1, Arena);
1456 Instrs.push_back(V);
1458 // Add a new predecessor, and return the phi-node index for it.
1459 // Will add an argument to all phi-nodes, initialized to nullptr.
1460 unsigned addPredecessor(BasicBlock *Pred);
1462 // Reserve space for Nargs arguments.
1463 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
1465 // Reserve space for Nins instructions.
1466 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1468 // Reserve space for NumPreds predecessors, including space in phi nodes.
1469 void reservePredecessors(unsigned NumPreds);
1471 // Return the index of BB, or Predecessors.size if BB is not a predecessor.
1472 unsigned findPredecessorIndex(const BasicBlock *BB) const {
1473 auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB);
1474 return std::distance(Predecessors.cbegin(), I);
1477 // Set id numbers for variables.
1478 void renumberVars();
1481 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1482 typename V::template Container<Variable*> Nas(Vs, Args.size());
1483 typename V::template Container<Variable*> Nis(Vs, Instrs.size());
1485 // Entering the basic block should do any scope initialization.
1486 Vs.enterBasicBlock(*this);
1488 for (auto *A : Args) {
1489 auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx));
1490 Variable *Nvd = Vs.enterScope(*A, Ne);
1493 for (auto *I : Instrs) {
1494 auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx));
1495 Variable *Nvd = Vs.enterScope(*I, Ne);
1498 auto Nt = Vs.traverse(Terminator, Ctx);
1500 // Exiting the basic block should handle any scope cleanup.
1501 Vs.exitBasicBlock(*this);
1503 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1506 template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) {
1507 // TODO: implement CFG comparisons
1508 return Cmp.comparePointers(this, E);
1516 SCFG *CFGPtr; // The CFG that contains this block.
1517 unsigned BlockID; // unique id for this BB in the containing CFG
1518 BasicBlock *Parent; // The parent block is the enclosing lexical scope.
1519 // The parent dominates this block.
1520 BlockArray Predecessors; // Predecessor blocks in the CFG.
1521 VarArray Args; // Phi nodes. One argument per predecessor.
1522 VarArray Instrs; // Instructions.
1523 SExprRef Terminator; // Branch or Goto
1527 // An SCFG is a control-flow graph. It consists of a set of basic blocks, each
1528 // of which terminates in a branch to another basic block. There is one
1529 // entry point, and one exit point.
1530 class SCFG : public SExpr {
1532 typedef SimpleArray<BasicBlock *> BlockArray;
1533 typedef BlockArray::iterator iterator;
1534 typedef BlockArray::const_iterator const_iterator;
1536 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1538 SCFG(MemRegionRef A, unsigned Nblocks)
1539 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks),
1540 Entry(nullptr), Exit(nullptr) {
1541 Entry = new (A) BasicBlock(A, nullptr);
1542 Exit = new (A) BasicBlock(A, Entry);
1543 auto *V = new (A) Variable(new (A) Phi());
1544 Exit->addArgument(V);
1548 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1549 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)),
1550 Entry(nullptr), Exit(nullptr) {
1551 // TODO: set entry and exit!
1554 iterator begin() { return Blocks.begin(); }
1555 iterator end() { return Blocks.end(); }
1557 const_iterator begin() const { return cbegin(); }
1558 const_iterator end() const { return cend(); }
1560 const_iterator cbegin() const { return Blocks.cbegin(); }
1561 const_iterator cend() const { return Blocks.cend(); }
1563 const BasicBlock *entry() const { return Entry; }
1564 BasicBlock *entry() { return Entry; }
1565 const BasicBlock *exit() const { return Exit; }
1566 BasicBlock *exit() { return Exit; }
1568 inline void add(BasicBlock *BB) {
1569 assert(BB->CFGPtr == nullptr || BB->CFGPtr == this);
1570 BB->setBlockID(Blocks.size());
1572 Blocks.reserveCheck(1, Arena);
1573 Blocks.push_back(BB);
1576 void setEntry(BasicBlock *BB) { Entry = BB; }
1577 void setExit(BasicBlock *BB) { Exit = BB; }
1579 // Set varable ids in all blocks.
1580 void renumberVars();
1583 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1585 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1586 for (auto *B : Blocks) {
1587 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1590 return Vs.reduceSCFG(*this, Bbs);
1593 template <class C> typename C::CType compare(SCFG *E, C &Cmp) {
1594 // TODO -- implement CFG comparisons
1595 return Cmp.comparePointers(this, E);
1606 class Goto : public SExpr {
1608 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1610 Goto(BasicBlock *B, unsigned I)
1611 : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1612 Goto(const Goto &G, BasicBlock *B, unsigned I)
1613 : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1615 const BasicBlock *targetBlock() const { return TargetBlock; }
1616 BasicBlock *targetBlock() { return TargetBlock; }
1618 unsigned index() const { return Index; }
1621 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1622 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1623 return Vs.reduceGoto(*this, Ntb);
1626 template <class C> typename C::CType compare(Goto *E, C &Cmp) {
1627 // TODO -- implement CFG comparisons
1628 return Cmp.comparePointers(this, E);
1632 BasicBlock *TargetBlock;
1633 unsigned Index; // Index into Phi nodes of target block.
1637 class Branch : public SExpr {
1639 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1641 Branch(SExpr *C, BasicBlock *T, BasicBlock *E, unsigned TI, unsigned EI)
1642 : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1643 ThenIndex(TI), ElseIndex(EI)
1645 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E,
1646 unsigned TI, unsigned EI)
1647 : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1648 ThenIndex(TI), ElseIndex(EI)
1651 const SExpr *condition() const { return Condition; }
1652 SExpr *condition() { return Condition; }
1654 const BasicBlock *thenBlock() const { return ThenBlock; }
1655 BasicBlock *thenBlock() { return ThenBlock; }
1657 const BasicBlock *elseBlock() const { return ElseBlock; }
1658 BasicBlock *elseBlock() { return ElseBlock; }
1660 unsigned thenIndex() const { return ThenIndex; }
1661 unsigned elseIndex() const { return ElseIndex; }
1664 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1665 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1666 BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock);
1667 BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock);
1668 return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1671 template <class C> typename C::CType compare(Branch *E, C &Cmp) {
1672 // TODO -- implement CFG comparisons
1673 return Cmp.comparePointers(this, E);
1678 BasicBlock *ThenBlock;
1679 BasicBlock *ElseBlock;
1685 // An identifier, e.g. 'foo' or 'x'.
1686 // This is a pseduo-term; it will be lowered to a variable or projection.
1687 class Identifier : public SExpr {
1689 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1691 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
1692 Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { }
1694 StringRef name() const { return Name; }
1697 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1698 return Vs.reduceIdentifier(*this);
1701 template <class C> typename C::CType compare(Identifier* E, C& Cmp) {
1702 return Cmp.compareStrings(name(), E->name());
1710 // An if-then-else expression.
1711 // This is a pseduo-term; it will be lowered to a branch in a CFG.
1712 class IfThenElse : public SExpr {
1714 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1716 IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1717 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
1719 IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1720 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
1723 SExpr *condition() { return Condition.get(); } // Address to store to
1724 const SExpr *condition() const { return Condition.get(); }
1726 SExpr *thenExpr() { return ThenExpr.get(); } // Value to store
1727 const SExpr *thenExpr() const { return ThenExpr.get(); }
1729 SExpr *elseExpr() { return ElseExpr.get(); } // Value to store
1730 const SExpr *elseExpr() const { return ElseExpr.get(); }
1733 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1734 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1735 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
1736 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
1737 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1740 template <class C> typename C::CType compare(IfThenElse* E, C& Cmp) {
1741 typename C::CType Ct = Cmp.compare(condition(), E->condition());
1742 if (Cmp.notTrue(Ct))
1744 Ct = Cmp.compare(thenExpr(), E->thenExpr());
1745 if (Cmp.notTrue(Ct))
1747 return Cmp.compare(elseExpr(), E->elseExpr());
1757 // A let-expression, e.g. let x=t; u.
1758 // This is a pseduo-term; it will be lowered to instructions in a CFG.
1759 class Let : public SExpr {
1761 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1763 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1764 Vd->setKind(Variable::VK_Let);
1766 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1767 Vd->setKind(Variable::VK_Let);
1770 Variable *variableDecl() { return VarDecl; }
1771 const Variable *variableDecl() const { return VarDecl; }
1773 SExpr *body() { return Body.get(); }
1774 const SExpr *body() const { return Body.get(); }
1777 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1778 // This is a variable declaration, so traverse the definition.
1779 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1780 // Tell the rewriter to enter the scope of the let variable.
1781 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1782 auto E1 = Vs.traverse(Body, Ctx);
1783 Vs.exitScope(*VarDecl);
1784 return Vs.reduceLet(*this, Nvd, E1);
1787 template <class C> typename C::CType compare(Let* E, C& Cmp) {
1788 typename C::CType Ct =
1789 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1790 if (Cmp.notTrue(Ct))
1792 Cmp.enterScope(variableDecl(), E->variableDecl());
1793 Ct = Cmp.compare(body(), E->body());
1805 SExpr *getCanonicalVal(SExpr *E);
1806 void simplifyIncompleteArg(Variable *V, til::Phi *Ph);
1809 } // end namespace til
1810 } // end namespace threadSafety
1811 } // end namespace clang
1813 #endif // LLVM_CLANG_THREAD_SAFETY_TIL_H