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_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
48 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
50 // All clang include dependencies for this file must be put in
51 // ThreadSafetyUtil.h.
52 #include "ThreadSafetyUtil.h"
61 namespace threadSafety {
65 /// Enum for the different distinct classes of SExpr
67 #define TIL_OPCODE_DEF(X) COP_##X,
68 #include "ThreadSafetyOps.def"
72 /// Opcode for unary arithmetic operations.
73 enum TIL_UnaryOpcode : unsigned char {
79 /// Opcode for binary arithmetic operations.
80 enum TIL_BinaryOpcode : unsigned char {
95 BOP_LogicAnd, // && (no short-circuit)
96 BOP_LogicOr // || (no short-circuit)
99 /// Opcode for cast operations.
100 enum TIL_CastOpcode : unsigned char {
102 CAST_extendNum, // extend precision of numeric type
103 CAST_truncNum, // truncate precision of numeric type
104 CAST_toFloat, // convert to floating point type
105 CAST_toInt, // convert to integer type
106 CAST_objToPtr // convert smart pointer to pointer (C++ only)
109 const TIL_Opcode COP_Min = COP_Future;
110 const TIL_Opcode COP_Max = COP_Branch;
111 const TIL_UnaryOpcode UOP_Min = UOP_Minus;
112 const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
113 const TIL_BinaryOpcode BOP_Min = BOP_Add;
114 const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
115 const TIL_CastOpcode CAST_Min = CAST_none;
116 const TIL_CastOpcode CAST_Max = CAST_toInt;
118 /// Return the name of a unary opcode.
119 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
121 /// Return the name of a binary opcode.
122 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
125 /// ValueTypes are data types that can actually be held in registers.
126 /// All variables and expressions must have a value type.
127 /// Pointer types are further subdivided into the various heap-allocated
128 /// types, such as functions, records, etc.
129 /// Structured types that are passed by value (e.g. complex numbers)
130 /// require special handling; they use BT_ValueRef, and size ST_0.
132 enum BaseType : unsigned char {
137 BT_String, // String literals
142 enum SizeType : unsigned char {
152 inline static SizeType getSizeType(unsigned nbytes);
155 inline static ValueType getValueType();
157 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
158 : Base(B), Size(Sz), Signed(S), VectSize(VS)
164 unsigned char VectSize; // 0 for scalar, otherwise num elements in vector
168 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
171 case 2: return ST_16;
172 case 4: return ST_32;
173 case 8: return ST_64;
174 case 16: return ST_128;
175 default: return ST_0;
181 inline ValueType ValueType::getValueType<void>() {
182 return ValueType(BT_Void, ST_0, false, 0);
186 inline ValueType ValueType::getValueType<bool>() {
187 return ValueType(BT_Bool, ST_1, false, 0);
191 inline ValueType ValueType::getValueType<int8_t>() {
192 return ValueType(BT_Int, ST_8, true, 0);
196 inline ValueType ValueType::getValueType<uint8_t>() {
197 return ValueType(BT_Int, ST_8, false, 0);
201 inline ValueType ValueType::getValueType<int16_t>() {
202 return ValueType(BT_Int, ST_16, true, 0);
206 inline ValueType ValueType::getValueType<uint16_t>() {
207 return ValueType(BT_Int, ST_16, false, 0);
211 inline ValueType ValueType::getValueType<int32_t>() {
212 return ValueType(BT_Int, ST_32, true, 0);
216 inline ValueType ValueType::getValueType<uint32_t>() {
217 return ValueType(BT_Int, ST_32, false, 0);
221 inline ValueType ValueType::getValueType<int64_t>() {
222 return ValueType(BT_Int, ST_64, true, 0);
226 inline ValueType ValueType::getValueType<uint64_t>() {
227 return ValueType(BT_Int, ST_64, false, 0);
231 inline ValueType ValueType::getValueType<float>() {
232 return ValueType(BT_Float, ST_32, true, 0);
236 inline ValueType ValueType::getValueType<double>() {
237 return ValueType(BT_Float, ST_64, true, 0);
241 inline ValueType ValueType::getValueType<long double>() {
242 return ValueType(BT_Float, ST_128, true, 0);
246 inline ValueType ValueType::getValueType<StringRef>() {
247 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
251 inline ValueType ValueType::getValueType<void*>() {
252 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
259 /// Base class for AST nodes in the typed intermediate language.
262 TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
264 // Subclasses of SExpr must define the following:
266 // This(const This& E, ...) {
267 // copy constructor: construct copy of E, with some additional arguments.
270 // template <class V>
271 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
272 // traverse all subexpressions, following the traversal/rewriter interface.
275 // template <class C> typename C::CType compare(CType* E, C& Cmp) {
276 // compare all subexpressions, following the comparator interface
278 void *operator new(size_t S, MemRegionRef &R) {
279 return ::operator new(S, R);
282 /// SExpr objects cannot be deleted.
283 // This declaration is public to workaround a gcc bug that breaks building
284 // with REQUIRES_EH=1.
285 void operator delete(void *) LLVM_DELETED_FUNCTION;
287 /// Returns the instruction ID for this expression.
288 /// All basic block instructions have a unique ID (i.e. virtual register).
289 unsigned id() const { return SExprID; }
291 /// Returns the block, if this is an instruction in a basic block,
292 /// otherwise returns null.
293 BasicBlock* block() const { return Block; }
295 /// Set the basic block and instruction ID for this expression.
296 void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
300 : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {}
301 SExpr(const SExpr &E)
302 : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0),
305 const unsigned char Opcode;
306 unsigned char Reserved;
307 unsigned short Flags;
312 SExpr() LLVM_DELETED_FUNCTION;
314 /// SExpr objects must be created in an arena.
315 void *operator new(size_t) LLVM_DELETED_FUNCTION;
319 // Contains various helper functions for SExprs.
320 namespace ThreadSafetyTIL {
321 inline bool isTrivial(const SExpr *E) {
322 unsigned Op = E->opcode();
323 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
327 // Nodes which declare variables
333 /// A named variable, e.g. "x".
335 /// There are two distinct places in which a Variable can appear in the AST.
336 /// A variable declaration introduces a new variable, and can occur in 3 places:
337 /// Let-expressions: (Let (x = t) u)
338 /// Functions: (Function (x : t) u)
339 /// Self-applicable functions (SFunction (x) t)
341 /// If a variable occurs in any other location, it is a reference to an existing
342 /// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
343 /// allocate a separate AST node for variable references; a reference is just a
344 /// pointer to the original declaration.
345 class Variable : public SExpr {
347 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
350 VK_Let, ///< Let-variable
351 VK_Fun, ///< Function parameter
352 VK_SFun ///< SFunction (self) parameter
355 Variable(StringRef s, SExpr *D = nullptr)
356 : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) {
359 Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr)
360 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
361 Definition(D), Cvdecl(Cvd) {
364 Variable(const Variable &Vd, SExpr *D) // rewrite constructor
365 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
369 /// Return the kind of variable (let, function param, or self)
370 VariableKind kind() const { return static_cast<VariableKind>(Flags); }
372 /// Return the name of the variable, if any.
373 StringRef name() const { return Name; }
375 /// Return the clang declaration for this variable, if any.
376 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
378 /// Return the definition of the variable.
379 /// For let-vars, this is the setting expression.
380 /// For function and self parameters, it is the type of the variable.
381 SExpr *definition() { return Definition; }
382 const SExpr *definition() const { return Definition; }
384 void setName(StringRef S) { Name = S; }
385 void setKind(VariableKind K) { Flags = K; }
386 void setDefinition(SExpr *E) { Definition = E; }
387 void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
390 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
391 // This routine is only called for variable references.
392 return Vs.reduceVariableRef(this);
396 typename C::CType compare(const Variable* E, C& Cmp) const {
397 return Cmp.compareVariableRefs(this, E);
401 friend class Function;
402 friend class SFunction;
403 friend class BasicBlock;
406 StringRef Name; // The name of the variable.
407 SExpr* Definition; // The TIL type or definition
408 const clang::ValueDecl *Cvdecl; // The clang declaration for this variable.
412 /// Placeholder for an expression that has not yet been created.
413 /// Used to implement lazy copy and rewriting strategies.
414 class Future : public SExpr {
416 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
424 Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {}
427 virtual ~Future() LLVM_DELETED_FUNCTION;
430 // A lazy rewriting strategy should subclass Future and override this method.
431 virtual SExpr *compute() { return nullptr; }
433 // Return the result of this future if it exists, otherwise return null.
434 SExpr *maybeGetResult() const {
438 // Return the result of this future; forcing it if necessary.
444 return nullptr; // infinite loop; illegal recursion.
451 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
452 assert(Result && "Cannot traverse Future that has not been forced.");
453 return Vs.traverse(Result, Ctx);
457 typename C::CType compare(const Future* E, C& Cmp) const {
458 if (!Result || !E->Result)
459 return Cmp.comparePointers(this, E);
460 return Cmp.compare(Result, E->Result);
471 /// Placeholder for expressions that cannot be represented in the TIL.
472 class Undefined : public SExpr {
474 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
476 Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
477 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
480 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
481 return Vs.reduceUndefined(*this);
485 typename C::CType compare(const Undefined* E, C& Cmp) const {
486 return Cmp.trueResult();
490 const clang::Stmt *Cstmt;
494 /// Placeholder for a wildcard that matches any other expression.
495 class Wildcard : public SExpr {
497 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
499 Wildcard() : SExpr(COP_Wildcard) {}
500 Wildcard(const Wildcard &W) : SExpr(W) {}
502 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
503 return Vs.reduceWildcard(*this);
507 typename C::CType compare(const Wildcard* E, C& Cmp) const {
508 return Cmp.trueResult();
513 template <class T> class LiteralT;
515 // Base class for literal values.
516 class Literal : public SExpr {
518 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
520 Literal(const clang::Expr *C)
521 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
523 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
524 Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
526 // The clang expression for this literal.
527 const clang::Expr *clangExpr() const { return Cexpr; }
529 ValueType valueType() const { return ValType; }
531 template<class T> const LiteralT<T>& as() const {
532 return *static_cast<const LiteralT<T>*>(this);
534 template<class T> LiteralT<T>& as() {
535 return *static_cast<LiteralT<T>*>(this);
538 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
541 typename C::CType compare(const Literal* E, C& Cmp) const {
542 // TODO: defer actual comparison to LiteralT
543 return Cmp.trueResult();
547 const ValueType ValType;
548 const clang::Expr *Cexpr;
552 // Derived class for literal values, which stores the actual value.
554 class LiteralT : public Literal {
556 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
557 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
559 T value() const { return Val;}
560 T& value() { return Val; }
569 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
571 return Vs.reduceLiteral(*this);
573 switch (ValType.Base) {
574 case ValueType::BT_Void:
576 case ValueType::BT_Bool:
577 return Vs.reduceLiteralT(as<bool>());
578 case ValueType::BT_Int: {
579 switch (ValType.Size) {
580 case ValueType::ST_8:
582 return Vs.reduceLiteralT(as<int8_t>());
584 return Vs.reduceLiteralT(as<uint8_t>());
585 case ValueType::ST_16:
587 return Vs.reduceLiteralT(as<int16_t>());
589 return Vs.reduceLiteralT(as<uint16_t>());
590 case ValueType::ST_32:
592 return Vs.reduceLiteralT(as<int32_t>());
594 return Vs.reduceLiteralT(as<uint32_t>());
595 case ValueType::ST_64:
597 return Vs.reduceLiteralT(as<int64_t>());
599 return Vs.reduceLiteralT(as<uint64_t>());
604 case ValueType::BT_Float: {
605 switch (ValType.Size) {
606 case ValueType::ST_32:
607 return Vs.reduceLiteralT(as<float>());
608 case ValueType::ST_64:
609 return Vs.reduceLiteralT(as<double>());
614 case ValueType::BT_String:
615 return Vs.reduceLiteralT(as<StringRef>());
616 case ValueType::BT_Pointer:
617 return Vs.reduceLiteralT(as<void*>());
618 case ValueType::BT_ValueRef:
621 return Vs.reduceLiteral(*this);
625 /// A Literal pointer to an object allocated in memory.
626 /// At compile time, pointer literals are represented by symbolic names.
627 class LiteralPtr : public SExpr {
629 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
631 LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
632 LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
634 // The clang declaration for the value that this pointer points to.
635 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
638 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
639 return Vs.reduceLiteralPtr(*this);
643 typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
644 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
648 const clang::ValueDecl *Cvdecl;
652 /// A function -- a.k.a. lambda abstraction.
653 /// Functions with multiple arguments are created by currying,
654 /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
655 class Function : public SExpr {
657 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
659 Function(Variable *Vd, SExpr *Bd)
660 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
661 Vd->setKind(Variable::VK_Fun);
663 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
664 : SExpr(F), VarDecl(Vd), Body(Bd) {
665 Vd->setKind(Variable::VK_Fun);
668 Variable *variableDecl() { return VarDecl; }
669 const Variable *variableDecl() const { return VarDecl; }
671 SExpr *body() { return Body; }
672 const SExpr *body() const { return Body; }
675 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
676 // This is a variable declaration, so traverse the definition.
677 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
678 // Tell the rewriter to enter the scope of the function.
679 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
680 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
681 Vs.exitScope(*VarDecl);
682 return Vs.reduceFunction(*this, Nvd, E1);
686 typename C::CType compare(const Function* E, C& Cmp) const {
687 typename C::CType Ct =
688 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
691 Cmp.enterScope(variableDecl(), E->variableDecl());
692 Ct = Cmp.compare(body(), E->body());
703 /// A self-applicable function.
704 /// A self-applicable function can be applied to itself. It's useful for
705 /// implementing objects and late binding.
706 class SFunction : public SExpr {
708 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
710 SFunction(Variable *Vd, SExpr *B)
711 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
712 assert(Vd->Definition == nullptr);
713 Vd->setKind(Variable::VK_SFun);
714 Vd->Definition = this;
716 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
717 : SExpr(F), VarDecl(Vd), Body(B) {
718 assert(Vd->Definition == nullptr);
719 Vd->setKind(Variable::VK_SFun);
720 Vd->Definition = this;
723 Variable *variableDecl() { return VarDecl; }
724 const Variable *variableDecl() const { return VarDecl; }
726 SExpr *body() { return Body; }
727 const SExpr *body() const { return Body; }
730 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
731 // A self-variable points to the SFunction itself.
732 // A rewrite must introduce the variable with a null definition, and update
733 // it after 'this' has been rewritten.
734 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
735 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
736 Vs.exitScope(*VarDecl);
737 // A rewrite operation will call SFun constructor to set Vvd->Definition.
738 return Vs.reduceSFunction(*this, Nvd, E1);
742 typename C::CType compare(const SFunction* E, C& Cmp) const {
743 Cmp.enterScope(variableDecl(), E->variableDecl());
744 typename C::CType Ct = Cmp.compare(body(), E->body());
755 /// A block of code -- e.g. the body of a function.
756 class Code : public SExpr {
758 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
760 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
761 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
762 : SExpr(C), ReturnType(T), Body(B) {}
764 SExpr *returnType() { return ReturnType; }
765 const SExpr *returnType() const { return ReturnType; }
767 SExpr *body() { return Body; }
768 const SExpr *body() const { return Body; }
771 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
772 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
773 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
774 return Vs.reduceCode(*this, Nt, Nb);
778 typename C::CType compare(const Code* E, C& Cmp) const {
779 typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
782 return Cmp.compare(body(), E->body());
791 /// A typed, writable location in memory
792 class Field : public SExpr {
794 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
796 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
797 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
798 : SExpr(C), Range(R), Body(B) {}
800 SExpr *range() { return Range; }
801 const SExpr *range() const { return Range; }
803 SExpr *body() { return Body; }
804 const SExpr *body() const { return Body; }
807 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
808 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
809 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
810 return Vs.reduceField(*this, Nr, Nb);
814 typename C::CType compare(const Field* E, C& Cmp) const {
815 typename C::CType Ct = Cmp.compare(range(), E->range());
818 return Cmp.compare(body(), E->body());
827 /// Apply an argument to a function.
828 /// Note that this does not actually call the function. Functions are curried,
829 /// so this returns a closure in which the first parameter has been applied.
830 /// Once all parameters have been applied, Call can be used to invoke the
832 class Apply : public SExpr {
834 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
836 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
837 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
838 : SExpr(A), Fun(F), Arg(Ar)
841 SExpr *fun() { return Fun; }
842 const SExpr *fun() const { return Fun; }
844 SExpr *arg() { return Arg; }
845 const SExpr *arg() const { return Arg; }
848 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
849 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
850 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
851 return Vs.reduceApply(*this, Nf, Na);
855 typename C::CType compare(const Apply* E, C& Cmp) const {
856 typename C::CType Ct = Cmp.compare(fun(), E->fun());
859 return Cmp.compare(arg(), E->arg());
868 /// Apply a self-argument to a self-applicable function.
869 class SApply : public SExpr {
871 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
873 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
874 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
875 : SExpr(A), Sfun(Sf), Arg(Ar) {}
877 SExpr *sfun() { return Sfun; }
878 const SExpr *sfun() const { return Sfun; }
880 SExpr *arg() { return Arg ? Arg : Sfun; }
881 const SExpr *arg() const { return Arg ? Arg : Sfun; }
883 bool isDelegation() const { return Arg != nullptr; }
886 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
887 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
888 typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
890 return Vs.reduceSApply(*this, Nf, Na);
894 typename C::CType compare(const SApply* E, C& Cmp) const {
895 typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
896 if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
898 return Cmp.compare(arg(), E->arg());
907 /// Project a named slot from a C++ struct or class.
908 class Project : public SExpr {
910 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
912 Project(SExpr *R, StringRef SName)
913 : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
915 Project(SExpr *R, const clang::ValueDecl *Cvd)
916 : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
918 Project(const Project &P, SExpr *R)
919 : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
922 SExpr *record() { return Rec; }
923 const SExpr *record() const { return Rec; }
925 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
927 bool isArrow() const { return (Flags & 0x01) != 0; }
928 void setArrow(bool b) {
929 if (b) Flags |= 0x01;
930 else Flags &= 0xFFFE;
933 StringRef slotName() const {
935 return Cvdecl->getName();
941 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
942 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
943 return Vs.reduceProject(*this, Nr);
947 typename C::CType compare(const Project* E, C& Cmp) const {
948 typename C::CType Ct = Cmp.compare(record(), E->record());
951 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
957 const clang::ValueDecl *Cvdecl;
961 /// Call a function (after all arguments have been applied).
962 class Call : public SExpr {
964 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
966 Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
967 : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
968 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
970 SExpr *target() { return Target; }
971 const SExpr *target() const { return Target; }
973 const clang::CallExpr *clangCallExpr() const { return Cexpr; }
976 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
977 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
978 return Vs.reduceCall(*this, Nt);
982 typename C::CType compare(const Call* E, C& Cmp) const {
983 return Cmp.compare(target(), E->target());
988 const clang::CallExpr *Cexpr;
992 /// Allocate memory for a new value on the heap or stack.
993 class Alloc : public SExpr {
995 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1002 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1003 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1005 AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1007 SExpr *dataType() { return Dtype; }
1008 const SExpr *dataType() const { return Dtype; }
1011 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1012 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1013 return Vs.reduceAlloc(*this, Nd);
1017 typename C::CType compare(const Alloc* E, C& Cmp) const {
1018 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1019 if (Cmp.notTrue(Ct))
1021 return Cmp.compare(dataType(), E->dataType());
1029 /// Load a value from memory.
1030 class Load : public SExpr {
1032 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1034 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1035 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1037 SExpr *pointer() { return Ptr; }
1038 const SExpr *pointer() const { return Ptr; }
1041 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1042 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1043 return Vs.reduceLoad(*this, Np);
1047 typename C::CType compare(const Load* E, C& Cmp) const {
1048 return Cmp.compare(pointer(), E->pointer());
1056 /// Store a value to memory.
1057 /// The destination is a pointer to a field, the source is the value to store.
1058 class Store : public SExpr {
1060 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1062 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1063 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1065 SExpr *destination() { return Dest; } // Address to store to
1066 const SExpr *destination() const { return Dest; }
1068 SExpr *source() { return Source; } // Value to store
1069 const SExpr *source() const { return Source; }
1072 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1073 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
1074 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1075 return Vs.reduceStore(*this, Np, Nv);
1079 typename C::CType compare(const Store* E, C& Cmp) const {
1080 typename C::CType Ct = Cmp.compare(destination(), E->destination());
1081 if (Cmp.notTrue(Ct))
1083 return Cmp.compare(source(), E->source());
1092 /// If p is a reference to an array, then p[i] is a reference to the i'th
1093 /// element of the array.
1094 class ArrayIndex : public SExpr {
1096 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1098 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1099 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1100 : SExpr(E), Array(A), Index(N) {}
1102 SExpr *array() { return Array; }
1103 const SExpr *array() const { return Array; }
1105 SExpr *index() { return Index; }
1106 const SExpr *index() const { return Index; }
1109 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1110 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1111 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1112 return Vs.reduceArrayIndex(*this, Na, Ni);
1116 typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1117 typename C::CType Ct = Cmp.compare(array(), E->array());
1118 if (Cmp.notTrue(Ct))
1120 return Cmp.compare(index(), E->index());
1129 /// Pointer arithmetic, restricted to arrays only.
1130 /// If p is a reference to an array, then p + n, where n is an integer, is
1131 /// a reference to a subarray.
1132 class ArrayAdd : public SExpr {
1134 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1136 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1137 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1138 : SExpr(E), Array(A), Index(N) {}
1140 SExpr *array() { return Array; }
1141 const SExpr *array() const { return Array; }
1143 SExpr *index() { return Index; }
1144 const SExpr *index() const { return Index; }
1147 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1148 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1149 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1150 return Vs.reduceArrayAdd(*this, Na, Ni);
1154 typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1155 typename C::CType Ct = Cmp.compare(array(), E->array());
1156 if (Cmp.notTrue(Ct))
1158 return Cmp.compare(index(), E->index());
1167 /// Simple arithmetic unary operations, e.g. negate and not.
1168 /// These operations have no side-effects.
1169 class UnaryOp : public SExpr {
1171 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1173 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1176 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1178 TIL_UnaryOpcode unaryOpcode() const {
1179 return static_cast<TIL_UnaryOpcode>(Flags);
1182 SExpr *expr() { return Expr0; }
1183 const SExpr *expr() const { return Expr0; }
1186 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1187 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1188 return Vs.reduceUnaryOp(*this, Ne);
1192 typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1193 typename C::CType Ct =
1194 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1195 if (Cmp.notTrue(Ct))
1197 return Cmp.compare(expr(), E->expr());
1205 /// Simple arithmetic binary operations, e.g. +, -, etc.
1206 /// These operations have no side effects.
1207 class BinaryOp : public SExpr {
1209 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1211 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1212 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1215 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1216 : SExpr(B), Expr0(E0), Expr1(E1) {
1220 TIL_BinaryOpcode binaryOpcode() const {
1221 return static_cast<TIL_BinaryOpcode>(Flags);
1224 SExpr *expr0() { return Expr0; }
1225 const SExpr *expr0() const { return Expr0; }
1227 SExpr *expr1() { return Expr1; }
1228 const SExpr *expr1() const { return Expr1; }
1231 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1232 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1233 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1234 return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1238 typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1239 typename C::CType Ct =
1240 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1241 if (Cmp.notTrue(Ct))
1243 Ct = Cmp.compare(expr0(), E->expr0());
1244 if (Cmp.notTrue(Ct))
1246 return Cmp.compare(expr1(), E->expr1());
1255 /// Cast expressions.
1256 /// Cast expressions are essentially unary operations, but we treat them
1257 /// as a distinct AST node because they only change the type of the result.
1258 class Cast : public SExpr {
1260 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1262 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1263 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1265 TIL_CastOpcode castOpcode() const {
1266 return static_cast<TIL_CastOpcode>(Flags);
1269 SExpr *expr() { return Expr0; }
1270 const SExpr *expr() const { return Expr0; }
1273 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1274 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1275 return Vs.reduceCast(*this, Ne);
1279 typename C::CType compare(const Cast* E, C& Cmp) const {
1280 typename C::CType Ct =
1281 Cmp.compareIntegers(castOpcode(), E->castOpcode());
1282 if (Cmp.notTrue(Ct))
1284 return Cmp.compare(expr(), E->expr());
1295 /// Phi Node, for code in SSA form.
1296 /// Each Phi node has an array of possible values that it can take,
1297 /// depending on where control flow comes from.
1298 class Phi : public SExpr {
1300 typedef SimpleArray<SExpr *> ValArray;
1302 // In minimal SSA form, all Phi nodes are MultiVal.
1303 // During conversion to SSA, incomplete Phi nodes may be introduced, which
1304 // are later determined to be SingleVal, and are thus redundant.
1306 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
1307 PH_SingleVal, // Phi node has one distinct value, and can be eliminated
1308 PH_Incomplete // Phi node is incomplete
1311 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1314 : SExpr(COP_Phi), Cvdecl(nullptr) {}
1315 Phi(MemRegionRef A, unsigned Nvals)
1316 : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {}
1317 Phi(const Phi &P, ValArray &&Vs)
1318 : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {}
1320 const ValArray &values() const { return Values; }
1321 ValArray &values() { return Values; }
1323 Status status() const { return static_cast<Status>(Flags); }
1324 void setStatus(Status s) { Flags = s; }
1326 /// Return the clang declaration of the variable for this Phi node, if any.
1327 const clang::ValueDecl *clangDecl() const { return Cvdecl; }
1329 /// Set the clang variable associated with this Phi node.
1330 void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; }
1333 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1334 typename V::template Container<typename V::R_SExpr>
1335 Nvs(Vs, Values.size());
1337 for (auto *Val : Values) {
1338 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1340 return Vs.reducePhi(*this, Nvs);
1344 typename C::CType compare(const Phi *E, C &Cmp) const {
1345 // TODO: implement CFG comparisons
1346 return Cmp.comparePointers(this, E);
1351 const clang::ValueDecl* Cvdecl;
1355 /// Base class for basic block terminators: Branch, Goto, and Return.
1356 class Terminator : public SExpr {
1358 static bool classof(const SExpr *E) {
1359 return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1363 Terminator(TIL_Opcode Op) : SExpr(Op) {}
1364 Terminator(const SExpr &E) : SExpr(E) {}
1367 /// Return the list of basic blocks that this terminator can branch to.
1368 ArrayRef<BasicBlock*> successors();
1370 ArrayRef<BasicBlock*> successors() const {
1371 return const_cast<Terminator*>(this)->successors();
1376 /// Jump to another basic block.
1377 /// A goto instruction is essentially a tail-recursive call into another
1378 /// block. In addition to the block pointer, it specifies an index into the
1379 /// phi nodes of that block. The index can be used to retrieve the "arguments"
1381 class Goto : public Terminator {
1383 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1385 Goto(BasicBlock *B, unsigned I)
1386 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1387 Goto(const Goto &G, BasicBlock *B, unsigned I)
1388 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1390 const BasicBlock *targetBlock() const { return TargetBlock; }
1391 BasicBlock *targetBlock() { return TargetBlock; }
1393 /// Returns the index into the
1394 unsigned index() const { return Index; }
1396 /// Return the list of basic blocks that this terminator can branch to.
1397 ArrayRef<BasicBlock*> successors() {
1398 return ArrayRef<BasicBlock*>(&TargetBlock, 1);
1402 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1403 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1404 return Vs.reduceGoto(*this, Ntb);
1408 typename C::CType compare(const Goto *E, C &Cmp) const {
1409 // TODO: implement CFG comparisons
1410 return Cmp.comparePointers(this, E);
1414 BasicBlock *TargetBlock;
1419 /// A conditional branch to two other blocks.
1420 /// Note that unlike Goto, Branch does not have an index. The target blocks
1421 /// must be child-blocks, and cannot have Phi nodes.
1422 class Branch : public Terminator {
1424 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1426 Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1427 : Terminator(COP_Branch), Condition(C) {
1431 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1432 : Terminator(Br), Condition(C) {
1437 const SExpr *condition() const { return Condition; }
1438 SExpr *condition() { return Condition; }
1440 const BasicBlock *thenBlock() const { return Branches[0]; }
1441 BasicBlock *thenBlock() { return Branches[0]; }
1443 const BasicBlock *elseBlock() const { return Branches[1]; }
1444 BasicBlock *elseBlock() { return Branches[1]; }
1446 /// Return the list of basic blocks that this terminator can branch to.
1447 ArrayRef<BasicBlock*> successors() {
1448 return ArrayRef<BasicBlock*>(Branches, 2);
1452 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1453 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1454 BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
1455 BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
1456 return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1460 typename C::CType compare(const Branch *E, C &Cmp) const {
1461 // TODO: implement CFG comparisons
1462 return Cmp.comparePointers(this, E);
1467 BasicBlock *Branches[2];
1471 /// Return from the enclosing function, passing the return value to the caller.
1472 /// Only the exit block should end with a return statement.
1473 class Return : public Terminator {
1475 static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1477 Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1478 Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1480 /// Return an empty list.
1481 ArrayRef<BasicBlock*> successors() {
1482 return ArrayRef<BasicBlock*>();
1485 SExpr *returnValue() { return Retval; }
1486 const SExpr *returnValue() const { return Retval; }
1489 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1490 auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
1491 return Vs.reduceReturn(*this, Ne);
1495 typename C::CType compare(const Return *E, C &Cmp) const {
1496 return Cmp.compare(Retval, E->Retval);
1504 inline ArrayRef<BasicBlock*> Terminator::successors() {
1506 case COP_Goto: return cast<Goto>(this)->successors();
1507 case COP_Branch: return cast<Branch>(this)->successors();
1508 case COP_Return: return cast<Return>(this)->successors();
1510 return ArrayRef<BasicBlock*>();
1515 /// A basic block is part of an SCFG. It can be treated as a function in
1516 /// continuation passing style. A block consists of a sequence of phi nodes,
1517 /// which are "arguments" to the function, followed by a sequence of
1518 /// instructions. It ends with a Terminator, which is a Branch or Goto to
1519 /// another basic block in the same SCFG.
1520 class BasicBlock : public SExpr {
1522 typedef SimpleArray<SExpr*> InstrArray;
1523 typedef SimpleArray<BasicBlock*> BlockArray;
1525 // TopologyNodes are used to overlay tree structures on top of the CFG,
1526 // such as dominator and postdominator trees. Each block is assigned an
1527 // ID in the tree according to a depth-first search. Tree traversals are
1528 // always up, towards the parents.
1529 struct TopologyNode {
1530 TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {}
1532 bool isParentOf(const TopologyNode& OtherNode) {
1533 return OtherNode.NodeID > NodeID &&
1534 OtherNode.NodeID < NodeID + SizeOfSubTree;
1537 bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1538 return OtherNode.NodeID >= NodeID &&
1539 OtherNode.NodeID < NodeID + SizeOfSubTree;
1543 int SizeOfSubTree; // Includes this node, so must be > 1.
1544 BasicBlock *Parent; // Pointer to parent.
1547 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1549 explicit BasicBlock(MemRegionRef A)
1550 : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),
1551 Visited(0), TermInstr(nullptr) {}
1552 BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
1554 : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0),
1555 Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1557 /// Returns the block ID. Every block has a unique ID in the CFG.
1558 int blockID() const { return BlockID; }
1560 /// Returns the number of predecessors.
1561 size_t numPredecessors() const { return Predecessors.size(); }
1562 size_t numSuccessors() const { return successors().size(); }
1564 const SCFG* cfg() const { return CFGPtr; }
1565 SCFG* cfg() { return CFGPtr; }
1567 const BasicBlock *parent() const { return DominatorNode.Parent; }
1568 BasicBlock *parent() { return DominatorNode.Parent; }
1570 const InstrArray &arguments() const { return Args; }
1571 InstrArray &arguments() { return Args; }
1573 InstrArray &instructions() { return Instrs; }
1574 const InstrArray &instructions() const { return Instrs; }
1576 /// Returns a list of predecessors.
1577 /// The order of predecessors in the list is important; each phi node has
1578 /// exactly one argument for each precessor, in the same order.
1579 BlockArray &predecessors() { return Predecessors; }
1580 const BlockArray &predecessors() const { return Predecessors; }
1582 ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
1583 ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1585 const Terminator *terminator() const { return TermInstr; }
1586 Terminator *terminator() { return TermInstr; }
1588 void setTerminator(Terminator *E) { TermInstr = E; }
1590 bool Dominates(const BasicBlock &Other) {
1591 return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1594 bool PostDominates(const BasicBlock &Other) {
1595 return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1598 /// Add a new argument.
1599 void addArgument(Phi *V) {
1600 Args.reserveCheck(1, Arena);
1603 /// Add a new instruction.
1604 void addInstruction(SExpr *V) {
1605 Instrs.reserveCheck(1, Arena);
1606 Instrs.push_back(V);
1608 // Add a new predecessor, and return the phi-node index for it.
1609 // Will add an argument to all phi-nodes, initialized to nullptr.
1610 unsigned addPredecessor(BasicBlock *Pred);
1612 // Reserve space for Nargs arguments.
1613 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
1615 // Reserve space for Nins instructions.
1616 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1618 // Reserve space for NumPreds predecessors, including space in phi nodes.
1619 void reservePredecessors(unsigned NumPreds);
1621 /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
1622 unsigned findPredecessorIndex(const BasicBlock *BB) const {
1623 auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB);
1624 return std::distance(Predecessors.cbegin(), I);
1628 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1629 typename V::template Container<SExpr*> Nas(Vs, Args.size());
1630 typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
1632 // Entering the basic block should do any scope initialization.
1633 Vs.enterBasicBlock(*this);
1635 for (auto *E : Args) {
1636 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1639 for (auto *E : Instrs) {
1640 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1643 auto Nt = Vs.traverse(TermInstr, Ctx);
1645 // Exiting the basic block should handle any scope cleanup.
1646 Vs.exitBasicBlock(*this);
1648 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1652 typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1653 // TODO: implement CFG comparisons
1654 return Cmp.comparePointers(this, E);
1660 int renumberInstrs(int id); // assign unique ids to all instructions
1661 int topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID);
1662 int topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID);
1663 void computeDominator();
1664 void computePostDominator();
1667 MemRegionRef Arena; // The arena used to allocate this block.
1668 SCFG *CFGPtr; // The CFG that contains this block.
1669 int BlockID : 31; // unique id for this BB in the containing CFG.
1670 // IDs are in topological order.
1671 bool Visited : 1; // Bit to determine if a block has been visited
1672 // during a traversal.
1673 BlockArray Predecessors; // Predecessor blocks in the CFG.
1674 InstrArray Args; // Phi nodes. One argument per predecessor.
1675 InstrArray Instrs; // Instructions.
1676 Terminator* TermInstr; // Terminating instruction
1678 TopologyNode DominatorNode; // The dominator tree
1679 TopologyNode PostDominatorNode; // The post-dominator tree
1683 /// An SCFG is a control-flow graph. It consists of a set of basic blocks,
1684 /// each of which terminates in a branch to another basic block. There is one
1685 /// entry point, and one exit point.
1686 class SCFG : public SExpr {
1688 typedef SimpleArray<BasicBlock *> BlockArray;
1689 typedef BlockArray::iterator iterator;
1690 typedef BlockArray::const_iterator const_iterator;
1692 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1694 SCFG(MemRegionRef A, unsigned Nblocks)
1695 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks),
1696 Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) {
1697 Entry = new (A) BasicBlock(A);
1698 Exit = new (A) BasicBlock(A);
1699 auto *V = new (A) Phi();
1700 Exit->addArgument(V);
1701 Exit->setTerminator(new (A) Return(V));
1705 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1706 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)),
1707 Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) {
1708 // TODO: set entry and exit!
1711 /// Return true if this CFG is valid.
1712 bool valid() const { return Entry && Exit && Blocks.size() > 0; }
1714 /// Return true if this CFG has been normalized.
1715 /// After normalization, blocks are in topological order, and block and
1716 /// instruction IDs have been assigned.
1717 bool normal() const { return Normal; }
1719 iterator begin() { return Blocks.begin(); }
1720 iterator end() { return Blocks.end(); }
1722 const_iterator begin() const { return cbegin(); }
1723 const_iterator end() const { return cend(); }
1725 const_iterator cbegin() const { return Blocks.cbegin(); }
1726 const_iterator cend() const { return Blocks.cend(); }
1728 const BasicBlock *entry() const { return Entry; }
1729 BasicBlock *entry() { return Entry; }
1730 const BasicBlock *exit() const { return Exit; }
1731 BasicBlock *exit() { return Exit; }
1733 /// Return the number of blocks in the CFG.
1734 /// Block::blockID() will return a number less than numBlocks();
1735 size_t numBlocks() const { return Blocks.size(); }
1737 /// Return the total number of instructions in the CFG.
1738 /// This is useful for building instruction side-tables;
1739 /// A call to SExpr::id() will return a number less than numInstructions().
1740 unsigned numInstructions() { return NumInstructions; }
1742 inline void add(BasicBlock *BB) {
1743 assert(BB->CFGPtr == nullptr);
1745 Blocks.reserveCheck(1, Arena);
1746 Blocks.push_back(BB);
1749 void setEntry(BasicBlock *BB) { Entry = BB; }
1750 void setExit(BasicBlock *BB) { Exit = BB; }
1752 void computeNormalForm();
1755 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1757 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1759 for (auto *B : Blocks) {
1760 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1763 return Vs.reduceSCFG(*this, Bbs);
1767 typename C::CType compare(const SCFG *E, C &Cmp) const {
1768 // TODO: implement CFG comparisons
1769 return Cmp.comparePointers(this, E);
1773 void renumberInstrs(); // assign unique ids to all instructions
1780 unsigned NumInstructions;
1786 /// An identifier, e.g. 'foo' or 'x'.
1787 /// This is a pseduo-term; it will be lowered to a variable or projection.
1788 class Identifier : public SExpr {
1790 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1792 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
1793 Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { }
1795 StringRef name() const { return Name; }
1798 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1799 return Vs.reduceIdentifier(*this);
1803 typename C::CType compare(const Identifier* E, C& Cmp) const {
1804 return Cmp.compareStrings(name(), E->name());
1812 /// An if-then-else expression.
1813 /// This is a pseduo-term; it will be lowered to a branch in a CFG.
1814 class IfThenElse : public SExpr {
1816 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1818 IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1819 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
1821 IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1822 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
1825 SExpr *condition() { return Condition; } // Address to store to
1826 const SExpr *condition() const { return Condition; }
1828 SExpr *thenExpr() { return ThenExpr; } // Value to store
1829 const SExpr *thenExpr() const { return ThenExpr; }
1831 SExpr *elseExpr() { return ElseExpr; } // Value to store
1832 const SExpr *elseExpr() const { return ElseExpr; }
1835 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1836 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1837 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
1838 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
1839 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1843 typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1844 typename C::CType Ct = Cmp.compare(condition(), E->condition());
1845 if (Cmp.notTrue(Ct))
1847 Ct = Cmp.compare(thenExpr(), E->thenExpr());
1848 if (Cmp.notTrue(Ct))
1850 return Cmp.compare(elseExpr(), E->elseExpr());
1860 /// A let-expression, e.g. let x=t; u.
1861 /// This is a pseduo-term; it will be lowered to instructions in a CFG.
1862 class Let : public SExpr {
1864 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1866 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1867 Vd->setKind(Variable::VK_Let);
1869 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1870 Vd->setKind(Variable::VK_Let);
1873 Variable *variableDecl() { return VarDecl; }
1874 const Variable *variableDecl() const { return VarDecl; }
1876 SExpr *body() { return Body; }
1877 const SExpr *body() const { return Body; }
1880 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1881 // This is a variable declaration, so traverse the definition.
1882 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1883 // Tell the rewriter to enter the scope of the let variable.
1884 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1885 auto E1 = Vs.traverse(Body, Ctx);
1886 Vs.exitScope(*VarDecl);
1887 return Vs.reduceLet(*this, Nvd, E1);
1891 typename C::CType compare(const Let* E, C& Cmp) const {
1892 typename C::CType Ct =
1893 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1894 if (Cmp.notTrue(Ct))
1896 Cmp.enterScope(variableDecl(), E->variableDecl());
1897 Ct = Cmp.compare(body(), E->body());
1909 const SExpr *getCanonicalVal(const SExpr *E);
1910 SExpr* simplifyToCanonicalVal(SExpr *E);
1911 void simplifyIncompleteArg(til::Phi *Ph);
1914 } // end namespace til
1915 } // end namespace threadSafety
1916 } // end namespace clang