Home | History | Annotate | Download | only in Analyses
      1 //===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT in the llvm repository for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     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.
     15 //
     16 // Thread safety analysis works by comparing mutex expressions, e.g.
     17 //
     18 // class A { Mutex mu; int dat GUARDED_BY(this->mu); }
     19 // class B { A a; }
     20 //
     21 // void foo(B* b) {
     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)
     26 // }
     27 //
     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:
     32 //
     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
     37 //
     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.
     42 //
     43 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
     44 //
     45 //===----------------------------------------------------------------------===//
     46 
     47 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
     48 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
     49 
     50 // All clang include dependencies for this file must be put in
     51 // ThreadSafetyUtil.h.
     52 #include "ThreadSafetyUtil.h"
     53 #include <algorithm>
     54 #include <cassert>
     55 #include <cstddef>
     56 #include <stdint.h>
     57 #include <utility>
     58 
     59 
     60 namespace clang {
     61 namespace threadSafety {
     62 namespace til {
     63 
     64 
     65 /// Enum for the different distinct classes of SExpr
     66 enum TIL_Opcode {
     67 #define TIL_OPCODE_DEF(X) COP_##X,
     68 #include "ThreadSafetyOps.def"
     69 #undef TIL_OPCODE_DEF
     70 };
     71 
     72 /// Opcode for unary arithmetic operations.
     73 enum TIL_UnaryOpcode : unsigned char {
     74   UOP_Minus,        //  -
     75   UOP_BitNot,       //  ~
     76   UOP_LogicNot      //  !
     77 };
     78 
     79 /// Opcode for binary arithmetic operations.
     80 enum TIL_BinaryOpcode : unsigned char {
     81   BOP_Add,          //  +
     82   BOP_Sub,          //  -
     83   BOP_Mul,          //  *
     84   BOP_Div,          //  /
     85   BOP_Rem,          //  %
     86   BOP_Shl,          //  <<
     87   BOP_Shr,          //  >>
     88   BOP_BitAnd,       //  &
     89   BOP_BitXor,       //  ^
     90   BOP_BitOr,        //  |
     91   BOP_Eq,           //  ==
     92   BOP_Neq,          //  !=
     93   BOP_Lt,           //  <
     94   BOP_Leq,          //  <=
     95   BOP_LogicAnd,     //  &&  (no short-circuit)
     96   BOP_LogicOr       //  ||  (no short-circuit)
     97 };
     98 
     99 /// Opcode for cast operations.
    100 enum TIL_CastOpcode : unsigned char {
    101   CAST_none = 0,
    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)
    107 };
    108 
    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;
    117 
    118 /// Return the name of a unary opcode.
    119 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
    120 
    121 /// Return the name of a binary opcode.
    122 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
    123 
    124 
    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.
    131 struct ValueType {
    132   enum BaseType : unsigned char {
    133     BT_Void = 0,
    134     BT_Bool,
    135     BT_Int,
    136     BT_Float,
    137     BT_String,    // String literals
    138     BT_Pointer,
    139     BT_ValueRef
    140   };
    141 
    142   enum SizeType : unsigned char {
    143     ST_0 = 0,
    144     ST_1,
    145     ST_8,
    146     ST_16,
    147     ST_32,
    148     ST_64,
    149     ST_128
    150   };
    151 
    152   inline static SizeType getSizeType(unsigned nbytes);
    153 
    154   template <class T>
    155   inline static ValueType getValueType();
    156 
    157   ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
    158       : Base(B), Size(Sz), Signed(S), VectSize(VS)
    159   { }
    160 
    161   BaseType      Base;
    162   SizeType      Size;
    163   bool          Signed;
    164   unsigned char VectSize;  // 0 for scalar, otherwise num elements in vector
    165 };
    166 
    167 
    168 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
    169   switch (nbytes) {
    170     case 1: return ST_8;
    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;
    176   }
    177 }
    178 
    179 
    180 template<>
    181 inline ValueType ValueType::getValueType<void>() {
    182   return ValueType(BT_Void, ST_0, false, 0);
    183 }
    184 
    185 template<>
    186 inline ValueType ValueType::getValueType<bool>() {
    187   return ValueType(BT_Bool, ST_1, false, 0);
    188 }
    189 
    190 template<>
    191 inline ValueType ValueType::getValueType<int8_t>() {
    192   return ValueType(BT_Int, ST_8, true, 0);
    193 }
    194 
    195 template<>
    196 inline ValueType ValueType::getValueType<uint8_t>() {
    197   return ValueType(BT_Int, ST_8, false, 0);
    198 }
    199 
    200 template<>
    201 inline ValueType ValueType::getValueType<int16_t>() {
    202   return ValueType(BT_Int, ST_16, true, 0);
    203 }
    204 
    205 template<>
    206 inline ValueType ValueType::getValueType<uint16_t>() {
    207   return ValueType(BT_Int, ST_16, false, 0);
    208 }
    209 
    210 template<>
    211 inline ValueType ValueType::getValueType<int32_t>() {
    212   return ValueType(BT_Int, ST_32, true, 0);
    213 }
    214 
    215 template<>
    216 inline ValueType ValueType::getValueType<uint32_t>() {
    217   return ValueType(BT_Int, ST_32, false, 0);
    218 }
    219 
    220 template<>
    221 inline ValueType ValueType::getValueType<int64_t>() {
    222   return ValueType(BT_Int, ST_64, true, 0);
    223 }
    224 
    225 template<>
    226 inline ValueType ValueType::getValueType<uint64_t>() {
    227   return ValueType(BT_Int, ST_64, false, 0);
    228 }
    229 
    230 template<>
    231 inline ValueType ValueType::getValueType<float>() {
    232   return ValueType(BT_Float, ST_32, true, 0);
    233 }
    234 
    235 template<>
    236 inline ValueType ValueType::getValueType<double>() {
    237   return ValueType(BT_Float, ST_64, true, 0);
    238 }
    239 
    240 template<>
    241 inline ValueType ValueType::getValueType<long double>() {
    242   return ValueType(BT_Float, ST_128, true, 0);
    243 }
    244 
    245 template<>
    246 inline ValueType ValueType::getValueType<StringRef>() {
    247   return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
    248 }
    249 
    250 template<>
    251 inline ValueType ValueType::getValueType<void*>() {
    252   return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
    253 }
    254 
    255 
    256 class BasicBlock;
    257 
    258 
    259 /// Base class for AST nodes in the typed intermediate language.
    260 class SExpr {
    261 public:
    262   TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
    263 
    264   // Subclasses of SExpr must define the following:
    265   //
    266   // This(const This& E, ...) {
    267   //   copy constructor: construct copy of E, with some additional arguments.
    268   // }
    269   //
    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.
    273   // }
    274   //
    275   // template <class C> typename C::CType compare(CType* E, C& Cmp) {
    276   //   compare all subexpressions, following the comparator interface
    277   // }
    278   void *operator new(size_t S, MemRegionRef &R) {
    279     return ::operator new(S, R);
    280   }
    281 
    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 *) = delete;
    286 
    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; }
    290 
    291   /// Returns the block, if this is an instruction in a basic block,
    292   /// otherwise returns null.
    293   BasicBlock* block() const { return Block; }
    294 
    295   /// Set the basic block and instruction ID for this expression.
    296   void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
    297 
    298 protected:
    299   SExpr(TIL_Opcode Op)
    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),
    303       Block(nullptr) {}
    304 
    305   const unsigned char Opcode;
    306   unsigned char Reserved;
    307   unsigned short Flags;
    308   unsigned SExprID;
    309   BasicBlock* Block;
    310 
    311 private:
    312   SExpr() = delete;
    313 
    314   /// SExpr objects must be created in an arena.
    315   void *operator new(size_t) = delete;
    316 };
    317 
    318 
    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;
    324   }
    325 }
    326 
    327 // Nodes which declare variables
    328 class Function;
    329 class SFunction;
    330 class Let;
    331 
    332 
    333 /// A named variable, e.g. "x".
    334 ///
    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)
    340 ///
    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 {
    346 public:
    347   static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
    348 
    349   enum VariableKind {
    350     VK_Let,  ///< Let-variable
    351     VK_Fun,  ///< Function parameter
    352     VK_SFun  ///< SFunction (self) parameter
    353   };
    354 
    355   Variable(StringRef s, SExpr *D = nullptr)
    356       : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) {
    357     Flags = VK_Let;
    358   }
    359   Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr)
    360       : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
    361         Definition(D), Cvdecl(Cvd) {
    362     Flags = VK_Let;
    363   }
    364   Variable(const Variable &Vd, SExpr *D)  // rewrite constructor
    365       : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
    366     Flags = Vd.kind();
    367   }
    368 
    369   /// Return the kind of variable (let, function param, or self)
    370   VariableKind kind() const { return static_cast<VariableKind>(Flags); }
    371 
    372   /// Return the name of the variable, if any.
    373   StringRef name() const { return Name; }
    374 
    375   /// Return the clang declaration for this variable, if any.
    376   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
    377 
    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; }
    383 
    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; }
    388 
    389   template <class V>
    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);
    393   }
    394 
    395   template <class C>
    396   typename C::CType compare(const Variable* E, C& Cmp) const {
    397     return Cmp.compareVariableRefs(this, E);
    398   }
    399 
    400 private:
    401   friend class Function;
    402   friend class SFunction;
    403   friend class BasicBlock;
    404   friend class Let;
    405 
    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.
    409 };
    410 
    411 
    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 {
    415 public:
    416   static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
    417 
    418   enum FutureStatus {
    419     FS_pending,
    420     FS_evaluating,
    421     FS_done
    422   };
    423 
    424   Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {}
    425 
    426 private:
    427   virtual ~Future() = delete;
    428 
    429 public:
    430   // A lazy rewriting strategy should subclass Future and override this method.
    431   virtual SExpr *compute() { return nullptr; }
    432 
    433   // Return the result of this future if it exists, otherwise return null.
    434   SExpr *maybeGetResult() const {
    435     return Result;
    436   }
    437 
    438   // Return the result of this future; forcing it if necessary.
    439   SExpr *result() {
    440     switch (Status) {
    441     case FS_pending:
    442       return force();
    443     case FS_evaluating:
    444       return nullptr; // infinite loop; illegal recursion.
    445     case FS_done:
    446       return Result;
    447     }
    448   }
    449 
    450   template <class V>
    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);
    454   }
    455 
    456   template <class C>
    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);
    461   }
    462 
    463 private:
    464   SExpr* force();
    465 
    466   FutureStatus Status;
    467   SExpr *Result;
    468 };
    469 
    470 
    471 /// Placeholder for expressions that cannot be represented in the TIL.
    472 class Undefined : public SExpr {
    473 public:
    474   static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
    475 
    476   Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
    477   Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
    478 
    479   template <class V>
    480   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
    481     return Vs.reduceUndefined(*this);
    482   }
    483 
    484   template <class C>
    485   typename C::CType compare(const Undefined* E, C& Cmp) const {
    486     return Cmp.trueResult();
    487   }
    488 
    489 private:
    490   const clang::Stmt *Cstmt;
    491 };
    492 
    493 
    494 /// Placeholder for a wildcard that matches any other expression.
    495 class Wildcard : public SExpr {
    496 public:
    497   static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
    498 
    499   Wildcard() : SExpr(COP_Wildcard) {}
    500   Wildcard(const Wildcard &W) : SExpr(W) {}
    501 
    502   template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
    503     return Vs.reduceWildcard(*this);
    504   }
    505 
    506   template <class C>
    507   typename C::CType compare(const Wildcard* E, C& Cmp) const {
    508     return Cmp.trueResult();
    509   }
    510 };
    511 
    512 
    513 template <class T> class LiteralT;
    514 
    515 // Base class for literal values.
    516 class Literal : public SExpr {
    517 public:
    518   static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
    519 
    520   Literal(const clang::Expr *C)
    521      : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
    522   { }
    523   Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
    524   Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
    525 
    526   // The clang expression for this literal.
    527   const clang::Expr *clangExpr() const { return Cexpr; }
    528 
    529   ValueType valueType() const { return ValType; }
    530 
    531   template<class T> const LiteralT<T>& as() const {
    532     return *static_cast<const LiteralT<T>*>(this);
    533   }
    534   template<class T> LiteralT<T>& as() {
    535     return *static_cast<LiteralT<T>*>(this);
    536   }
    537 
    538   template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
    539 
    540   template <class C>
    541   typename C::CType compare(const Literal* E, C& Cmp) const {
    542     // TODO: defer actual comparison to LiteralT
    543     return Cmp.trueResult();
    544   }
    545 
    546 private:
    547   const ValueType ValType;
    548   const clang::Expr *Cexpr;
    549 };
    550 
    551 
    552 // Derived class for literal values, which stores the actual value.
    553 template<class T>
    554 class LiteralT : public Literal {
    555 public:
    556   LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
    557   LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
    558 
    559   T  value() const { return Val;}
    560   T& value() { return Val; }
    561 
    562 private:
    563   T Val;
    564 };
    565 
    566 
    567 
    568 template <class V>
    569 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
    570   if (Cexpr)
    571     return Vs.reduceLiteral(*this);
    572 
    573   switch (ValType.Base) {
    574   case ValueType::BT_Void:
    575     break;
    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:
    581       if (ValType.Signed)
    582         return Vs.reduceLiteralT(as<int8_t>());
    583       else
    584         return Vs.reduceLiteralT(as<uint8_t>());
    585     case ValueType::ST_16:
    586       if (ValType.Signed)
    587         return Vs.reduceLiteralT(as<int16_t>());
    588       else
    589         return Vs.reduceLiteralT(as<uint16_t>());
    590     case ValueType::ST_32:
    591       if (ValType.Signed)
    592         return Vs.reduceLiteralT(as<int32_t>());
    593       else
    594         return Vs.reduceLiteralT(as<uint32_t>());
    595     case ValueType::ST_64:
    596       if (ValType.Signed)
    597         return Vs.reduceLiteralT(as<int64_t>());
    598       else
    599         return Vs.reduceLiteralT(as<uint64_t>());
    600     default:
    601       break;
    602     }
    603   }
    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>());
    610     default:
    611       break;
    612     }
    613   }
    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:
    619     break;
    620   }
    621   return Vs.reduceLiteral(*this);
    622 }
    623 
    624 
    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 {
    628 public:
    629   static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
    630 
    631   LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
    632   LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
    633 
    634   // The clang declaration for the value that this pointer points to.
    635   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
    636 
    637   template <class V>
    638   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
    639     return Vs.reduceLiteralPtr(*this);
    640   }
    641 
    642   template <class C>
    643   typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
    644     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
    645   }
    646 
    647 private:
    648   const clang::ValueDecl *Cvdecl;
    649 };
    650 
    651 
    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 {
    656 public:
    657   static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
    658 
    659   Function(Variable *Vd, SExpr *Bd)
    660       : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
    661     Vd->setKind(Variable::VK_Fun);
    662   }
    663   Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
    664       : SExpr(F), VarDecl(Vd), Body(Bd) {
    665     Vd->setKind(Variable::VK_Fun);
    666   }
    667 
    668   Variable *variableDecl()  { return VarDecl; }
    669   const Variable *variableDecl() const { return VarDecl; }
    670 
    671   SExpr *body() { return Body; }
    672   const SExpr *body() const { return Body; }
    673 
    674   template <class V>
    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);
    683   }
    684 
    685   template <class C>
    686   typename C::CType compare(const Function* E, C& Cmp) const {
    687     typename C::CType Ct =
    688       Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
    689     if (Cmp.notTrue(Ct))
    690       return Ct;
    691     Cmp.enterScope(variableDecl(), E->variableDecl());
    692     Ct = Cmp.compare(body(), E->body());
    693     Cmp.leaveScope();
    694     return Ct;
    695   }
    696 
    697 private:
    698   Variable *VarDecl;
    699   SExpr* Body;
    700 };
    701 
    702 
    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 {
    707 public:
    708   static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
    709 
    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;
    715   }
    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;
    721   }
    722 
    723   Variable *variableDecl() { return VarDecl; }
    724   const Variable *variableDecl() const { return VarDecl; }
    725 
    726   SExpr *body() { return Body; }
    727   const SExpr *body() const { return Body; }
    728 
    729   template <class V>
    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);
    739   }
    740 
    741   template <class C>
    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());
    745     Cmp.leaveScope();
    746     return Ct;
    747   }
    748 
    749 private:
    750   Variable *VarDecl;
    751   SExpr* Body;
    752 };
    753 
    754 
    755 /// A block of code -- e.g. the body of a function.
    756 class Code : public SExpr {
    757 public:
    758   static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
    759 
    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) {}
    763 
    764   SExpr *returnType() { return ReturnType; }
    765   const SExpr *returnType() const { return ReturnType; }
    766 
    767   SExpr *body() { return Body; }
    768   const SExpr *body() const { return Body; }
    769 
    770   template <class V>
    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);
    775   }
    776 
    777   template <class C>
    778   typename C::CType compare(const Code* E, C& Cmp) const {
    779     typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
    780     if (Cmp.notTrue(Ct))
    781       return Ct;
    782     return Cmp.compare(body(), E->body());
    783   }
    784 
    785 private:
    786   SExpr* ReturnType;
    787   SExpr* Body;
    788 };
    789 
    790 
    791 /// A typed, writable location in memory
    792 class Field : public SExpr {
    793 public:
    794   static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
    795 
    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) {}
    799 
    800   SExpr *range() { return Range; }
    801   const SExpr *range() const { return Range; }
    802 
    803   SExpr *body() { return Body; }
    804   const SExpr *body() const { return Body; }
    805 
    806   template <class V>
    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);
    811   }
    812 
    813   template <class C>
    814   typename C::CType compare(const Field* E, C& Cmp) const {
    815     typename C::CType Ct = Cmp.compare(range(), E->range());
    816     if (Cmp.notTrue(Ct))
    817       return Ct;
    818     return Cmp.compare(body(), E->body());
    819   }
    820 
    821 private:
    822   SExpr* Range;
    823   SExpr* Body;
    824 };
    825 
    826 
    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
    831 /// function.
    832 class Apply : public SExpr {
    833 public:
    834   static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
    835 
    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)
    839   {}
    840 
    841   SExpr *fun() { return Fun; }
    842   const SExpr *fun() const { return Fun; }
    843 
    844   SExpr *arg() { return Arg; }
    845   const SExpr *arg() const { return Arg; }
    846 
    847   template <class V>
    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);
    852   }
    853 
    854   template <class C>
    855   typename C::CType compare(const Apply* E, C& Cmp) const {
    856     typename C::CType Ct = Cmp.compare(fun(), E->fun());
    857     if (Cmp.notTrue(Ct))
    858       return Ct;
    859     return Cmp.compare(arg(), E->arg());
    860   }
    861 
    862 private:
    863   SExpr* Fun;
    864   SExpr* Arg;
    865 };
    866 
    867 
    868 /// Apply a self-argument to a self-applicable function.
    869 class SApply : public SExpr {
    870 public:
    871   static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
    872 
    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) {}
    876 
    877   SExpr *sfun() { return Sfun; }
    878   const SExpr *sfun() const { return Sfun; }
    879 
    880   SExpr *arg() { return Arg ? Arg : Sfun; }
    881   const SExpr *arg() const { return Arg ? Arg : Sfun; }
    882 
    883   bool isDelegation() const { return Arg != nullptr; }
    884 
    885   template <class V>
    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))
    889                                        : nullptr;
    890     return Vs.reduceSApply(*this, Nf, Na);
    891   }
    892 
    893   template <class C>
    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()))
    897       return Ct;
    898     return Cmp.compare(arg(), E->arg());
    899   }
    900 
    901 private:
    902   SExpr* Sfun;
    903   SExpr* Arg;
    904 };
    905 
    906 
    907 /// Project a named slot from a C++ struct or class.
    908 class Project : public SExpr {
    909 public:
    910   static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
    911 
    912   Project(SExpr *R, StringRef SName)
    913       : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
    914   { }
    915   Project(SExpr *R, const clang::ValueDecl *Cvd)
    916       : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
    917   { }
    918   Project(const Project &P, SExpr *R)
    919       : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
    920   { }
    921 
    922   SExpr *record() { return Rec; }
    923   const SExpr *record() const { return Rec; }
    924 
    925   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
    926 
    927   bool isArrow() const { return (Flags & 0x01) != 0; }
    928   void setArrow(bool b) {
    929     if (b) Flags |= 0x01;
    930     else Flags &= 0xFFFE;
    931   }
    932 
    933   StringRef slotName() const {
    934     if (Cvdecl)
    935       return Cvdecl->getName();
    936     else
    937       return SlotName;
    938   }
    939 
    940   template <class V>
    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);
    944   }
    945 
    946   template <class C>
    947   typename C::CType compare(const Project* E, C& Cmp) const {
    948     typename C::CType Ct = Cmp.compare(record(), E->record());
    949     if (Cmp.notTrue(Ct))
    950       return Ct;
    951     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
    952   }
    953 
    954 private:
    955   SExpr* Rec;
    956   StringRef SlotName;
    957   const clang::ValueDecl *Cvdecl;
    958 };
    959 
    960 
    961 /// Call a function (after all arguments have been applied).
    962 class Call : public SExpr {
    963 public:
    964   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
    965 
    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) {}
    969 
    970   SExpr *target() { return Target; }
    971   const SExpr *target() const { return Target; }
    972 
    973   const clang::CallExpr *clangCallExpr() const { return Cexpr; }
    974 
    975   template <class V>
    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);
    979   }
    980 
    981   template <class C>
    982   typename C::CType compare(const Call* E, C& Cmp) const {
    983     return Cmp.compare(target(), E->target());
    984   }
    985 
    986 private:
    987   SExpr* Target;
    988   const clang::CallExpr *Cexpr;
    989 };
    990 
    991 
    992 /// Allocate memory for a new value on the heap or stack.
    993 class Alloc : public SExpr {
    994 public:
    995   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
    996 
    997   enum AllocKind {
    998     AK_Stack,
    999     AK_Heap
   1000   };
   1001 
   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(); }
   1004 
   1005   AllocKind kind() const { return static_cast<AllocKind>(Flags); }
   1006 
   1007   SExpr *dataType() { return Dtype; }
   1008   const SExpr *dataType() const { return Dtype; }
   1009 
   1010   template <class V>
   1011   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
   1012     auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
   1013     return Vs.reduceAlloc(*this, Nd);
   1014   }
   1015 
   1016   template <class C>
   1017   typename C::CType compare(const Alloc* E, C& Cmp) const {
   1018     typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
   1019     if (Cmp.notTrue(Ct))
   1020       return Ct;
   1021     return Cmp.compare(dataType(), E->dataType());
   1022   }
   1023 
   1024 private:
   1025   SExpr* Dtype;
   1026 };
   1027 
   1028 
   1029 /// Load a value from memory.
   1030 class Load : public SExpr {
   1031 public:
   1032   static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
   1033 
   1034   Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
   1035   Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
   1036 
   1037   SExpr *pointer() { return Ptr; }
   1038   const SExpr *pointer() const { return Ptr; }
   1039 
   1040   template <class V>
   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);
   1044   }
   1045 
   1046   template <class C>
   1047   typename C::CType compare(const Load* E, C& Cmp) const {
   1048     return Cmp.compare(pointer(), E->pointer());
   1049   }
   1050 
   1051 private:
   1052   SExpr* Ptr;
   1053 };
   1054 
   1055 
   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 {
   1059 public:
   1060   static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
   1061 
   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) {}
   1064 
   1065   SExpr *destination() { return Dest; }  // Address to store to
   1066   const SExpr *destination() const { return Dest; }
   1067 
   1068   SExpr *source() { return Source; }     // Value to store
   1069   const SExpr *source() const { return Source; }
   1070 
   1071   template <class V>
   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);
   1076   }
   1077 
   1078   template <class C>
   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))
   1082       return Ct;
   1083     return Cmp.compare(source(), E->source());
   1084   }
   1085 
   1086 private:
   1087   SExpr* Dest;
   1088   SExpr* Source;
   1089 };
   1090 
   1091 
   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 {
   1095 public:
   1096   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
   1097 
   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) {}
   1101 
   1102   SExpr *array() { return Array; }
   1103   const SExpr *array() const { return Array; }
   1104 
   1105   SExpr *index() { return Index; }
   1106   const SExpr *index() const { return Index; }
   1107 
   1108   template <class V>
   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);
   1113   }
   1114 
   1115   template <class C>
   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))
   1119       return Ct;
   1120     return Cmp.compare(index(), E->index());
   1121   }
   1122 
   1123 private:
   1124   SExpr* Array;
   1125   SExpr* Index;
   1126 };
   1127 
   1128 
   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 {
   1133 public:
   1134   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
   1135 
   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) {}
   1139 
   1140   SExpr *array() { return Array; }
   1141   const SExpr *array() const { return Array; }
   1142 
   1143   SExpr *index() { return Index; }
   1144   const SExpr *index() const { return Index; }
   1145 
   1146   template <class V>
   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);
   1151   }
   1152 
   1153   template <class C>
   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))
   1157       return Ct;
   1158     return Cmp.compare(index(), E->index());
   1159   }
   1160 
   1161 private:
   1162   SExpr* Array;
   1163   SExpr* Index;
   1164 };
   1165 
   1166 
   1167 /// Simple arithmetic unary operations, e.g. negate and not.
   1168 /// These operations have no side-effects.
   1169 class UnaryOp : public SExpr {
   1170 public:
   1171   static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
   1172 
   1173   UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
   1174     Flags = Op;
   1175   }
   1176   UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
   1177 
   1178   TIL_UnaryOpcode unaryOpcode() const {
   1179     return static_cast<TIL_UnaryOpcode>(Flags);
   1180   }
   1181 
   1182   SExpr *expr() { return Expr0; }
   1183   const SExpr *expr() const { return Expr0; }
   1184 
   1185   template <class V>
   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);
   1189   }
   1190 
   1191   template <class C>
   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))
   1196       return Ct;
   1197     return Cmp.compare(expr(), E->expr());
   1198   }
   1199 
   1200 private:
   1201   SExpr* Expr0;
   1202 };
   1203 
   1204 
   1205 /// Simple arithmetic binary operations, e.g. +, -, etc.
   1206 /// These operations have no side effects.
   1207 class BinaryOp : public SExpr {
   1208 public:
   1209   static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
   1210 
   1211   BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
   1212       : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
   1213     Flags = Op;
   1214   }
   1215   BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
   1216       : SExpr(B), Expr0(E0), Expr1(E1) {
   1217     Flags = B.Flags;
   1218   }
   1219 
   1220   TIL_BinaryOpcode binaryOpcode() const {
   1221     return static_cast<TIL_BinaryOpcode>(Flags);
   1222   }
   1223 
   1224   SExpr *expr0() { return Expr0; }
   1225   const SExpr *expr0() const { return Expr0; }
   1226 
   1227   SExpr *expr1() { return Expr1; }
   1228   const SExpr *expr1() const { return Expr1; }
   1229 
   1230   template <class V>
   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);
   1235   }
   1236 
   1237   template <class C>
   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))
   1242       return Ct;
   1243     Ct = Cmp.compare(expr0(), E->expr0());
   1244     if (Cmp.notTrue(Ct))
   1245       return Ct;
   1246     return Cmp.compare(expr1(), E->expr1());
   1247   }
   1248 
   1249 private:
   1250   SExpr* Expr0;
   1251   SExpr* Expr1;
   1252 };
   1253 
   1254 
   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 {
   1259 public:
   1260   static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
   1261 
   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; }
   1264 
   1265   TIL_CastOpcode castOpcode() const {
   1266     return static_cast<TIL_CastOpcode>(Flags);
   1267   }
   1268 
   1269   SExpr *expr() { return Expr0; }
   1270   const SExpr *expr() const { return Expr0; }
   1271 
   1272   template <class V>
   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);
   1276   }
   1277 
   1278   template <class C>
   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))
   1283       return Ct;
   1284     return Cmp.compare(expr(), E->expr());
   1285   }
   1286 
   1287 private:
   1288   SExpr* Expr0;
   1289 };
   1290 
   1291 
   1292 class SCFG;
   1293 
   1294 
   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 {
   1299 public:
   1300   typedef SimpleArray<SExpr *> ValArray;
   1301 
   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.
   1305   enum Status {
   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
   1309   };
   1310 
   1311   static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
   1312 
   1313   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) {}
   1319 
   1320   const ValArray &values() const { return Values; }
   1321   ValArray &values() { return Values; }
   1322 
   1323   Status status() const { return static_cast<Status>(Flags); }
   1324   void setStatus(Status s) { Flags = s; }
   1325 
   1326   /// Return the clang declaration of the variable for this Phi node, if any.
   1327   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
   1328 
   1329   /// Set the clang variable associated with this Phi node.
   1330   void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; }
   1331 
   1332   template <class V>
   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());
   1336 
   1337     for (auto *Val : Values) {
   1338       Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
   1339     }
   1340     return Vs.reducePhi(*this, Nvs);
   1341   }
   1342 
   1343   template <class C>
   1344   typename C::CType compare(const Phi *E, C &Cmp) const {
   1345     // TODO: implement CFG comparisons
   1346     return Cmp.comparePointers(this, E);
   1347   }
   1348 
   1349 private:
   1350   ValArray Values;
   1351   const clang::ValueDecl* Cvdecl;
   1352 };
   1353 
   1354 
   1355 /// Base class for basic block terminators:  Branch, Goto, and Return.
   1356 class Terminator : public SExpr {
   1357 public:
   1358   static bool classof(const SExpr *E) {
   1359     return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
   1360   }
   1361 
   1362 protected:
   1363   Terminator(TIL_Opcode Op)  : SExpr(Op) {}
   1364   Terminator(const SExpr &E) : SExpr(E)  {}
   1365 
   1366 public:
   1367   /// Return the list of basic blocks that this terminator can branch to.
   1368   ArrayRef<BasicBlock*> successors();
   1369 
   1370   ArrayRef<BasicBlock*> successors() const {
   1371     return const_cast<Terminator*>(this)->successors();
   1372   }
   1373 };
   1374 
   1375 
   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"
   1380 /// of the call.
   1381 class Goto : public Terminator {
   1382 public:
   1383   static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
   1384 
   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) {}
   1389 
   1390   const BasicBlock *targetBlock() const { return TargetBlock; }
   1391   BasicBlock *targetBlock() { return TargetBlock; }
   1392 
   1393   /// Returns the index into the
   1394   unsigned index() const { return Index; }
   1395 
   1396   /// Return the list of basic blocks that this terminator can branch to.
   1397   ArrayRef<BasicBlock*> successors() {
   1398     return ArrayRef<BasicBlock*>(&TargetBlock, 1);
   1399   }
   1400 
   1401   template <class V>
   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);
   1405   }
   1406 
   1407   template <class C>
   1408   typename C::CType compare(const Goto *E, C &Cmp) const {
   1409     // TODO: implement CFG comparisons
   1410     return Cmp.comparePointers(this, E);
   1411   }
   1412 
   1413 private:
   1414   BasicBlock *TargetBlock;
   1415   unsigned Index;
   1416 };
   1417 
   1418 
   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 {
   1423 public:
   1424   static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
   1425 
   1426   Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
   1427       : Terminator(COP_Branch), Condition(C) {
   1428     Branches[0] = T;
   1429     Branches[1] = E;
   1430   }
   1431   Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
   1432       : Terminator(Br), Condition(C) {
   1433     Branches[0] = T;
   1434     Branches[1] = E;
   1435   }
   1436 
   1437   const SExpr *condition() const { return Condition; }
   1438   SExpr *condition() { return Condition; }
   1439 
   1440   const BasicBlock *thenBlock() const { return Branches[0]; }
   1441   BasicBlock *thenBlock() { return Branches[0]; }
   1442 
   1443   const BasicBlock *elseBlock() const { return Branches[1]; }
   1444   BasicBlock *elseBlock() { return Branches[1]; }
   1445 
   1446   /// Return the list of basic blocks that this terminator can branch to.
   1447   ArrayRef<BasicBlock*> successors() {
   1448     return ArrayRef<BasicBlock*>(Branches, 2);
   1449   }
   1450 
   1451   template <class V>
   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);
   1457   }
   1458 
   1459   template <class C>
   1460   typename C::CType compare(const Branch *E, C &Cmp) const {
   1461     // TODO: implement CFG comparisons
   1462     return Cmp.comparePointers(this, E);
   1463   }
   1464 
   1465 private:
   1466   SExpr*     Condition;
   1467   BasicBlock *Branches[2];
   1468 };
   1469 
   1470 
   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 {
   1474 public:
   1475   static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
   1476 
   1477   Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
   1478   Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
   1479 
   1480   /// Return an empty list.
   1481   ArrayRef<BasicBlock*> successors() {
   1482     return ArrayRef<BasicBlock*>();
   1483   }
   1484 
   1485   SExpr *returnValue() { return Retval; }
   1486   const SExpr *returnValue() const { return Retval; }
   1487 
   1488   template <class V>
   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);
   1492   }
   1493 
   1494   template <class C>
   1495   typename C::CType compare(const Return *E, C &Cmp) const {
   1496     return Cmp.compare(Retval, E->Retval);
   1497   }
   1498 
   1499 private:
   1500   SExpr* Retval;
   1501 };
   1502 
   1503 
   1504 inline ArrayRef<BasicBlock*> Terminator::successors() {
   1505   switch (opcode()) {
   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();
   1509     default:
   1510       return ArrayRef<BasicBlock*>();
   1511   }
   1512 }
   1513 
   1514 
   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 {
   1521 public:
   1522   typedef SimpleArray<SExpr*>      InstrArray;
   1523   typedef SimpleArray<BasicBlock*> BlockArray;
   1524 
   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) {}
   1531 
   1532     bool isParentOf(const TopologyNode& OtherNode) {
   1533       return OtherNode.NodeID > NodeID &&
   1534              OtherNode.NodeID < NodeID + SizeOfSubTree;
   1535     }
   1536 
   1537     bool isParentOfOrEqual(const TopologyNode& OtherNode) {
   1538       return OtherNode.NodeID >= NodeID &&
   1539              OtherNode.NodeID < NodeID + SizeOfSubTree;
   1540     }
   1541 
   1542     int NodeID;
   1543     int SizeOfSubTree;    // Includes this node, so must be > 1.
   1544     BasicBlock *Parent;   // Pointer to parent.
   1545   };
   1546 
   1547   static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
   1548 
   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,
   1553              Terminator *T)
   1554       : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0),
   1555         Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
   1556 
   1557   /// Returns the block ID.  Every block has a unique ID in the CFG.
   1558   int blockID() const { return BlockID; }
   1559 
   1560   /// Returns the number of predecessors.
   1561   size_t numPredecessors() const { return Predecessors.size(); }
   1562   size_t numSuccessors() const { return successors().size(); }
   1563 
   1564   const SCFG* cfg() const { return CFGPtr; }
   1565   SCFG* cfg() { return CFGPtr; }
   1566 
   1567   const BasicBlock *parent() const { return DominatorNode.Parent; }
   1568   BasicBlock *parent() { return DominatorNode.Parent; }
   1569 
   1570   const InstrArray &arguments() const { return Args; }
   1571   InstrArray &arguments() { return Args; }
   1572 
   1573   InstrArray &instructions() { return Instrs; }
   1574   const InstrArray &instructions() const { return Instrs; }
   1575 
   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; }
   1581 
   1582   ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
   1583   ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
   1584 
   1585   const Terminator *terminator() const { return TermInstr; }
   1586   Terminator *terminator() { return TermInstr; }
   1587 
   1588   void setTerminator(Terminator *E) { TermInstr = E; }
   1589 
   1590   bool Dominates(const BasicBlock &Other) {
   1591     return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
   1592   }
   1593 
   1594   bool PostDominates(const BasicBlock &Other) {
   1595     return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
   1596   }
   1597 
   1598   /// Add a new argument.
   1599   void addArgument(Phi *V) {
   1600     Args.reserveCheck(1, Arena);
   1601     Args.push_back(V);
   1602   }
   1603   /// Add a new instruction.
   1604   void addInstruction(SExpr *V) {
   1605     Instrs.reserveCheck(1, Arena);
   1606     Instrs.push_back(V);
   1607   }
   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);
   1611 
   1612   // Reserve space for Nargs arguments.
   1613   void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
   1614 
   1615   // Reserve space for Nins instructions.
   1616   void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
   1617 
   1618   // Reserve space for NumPreds predecessors, including space in phi nodes.
   1619   void reservePredecessors(unsigned NumPreds);
   1620 
   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);
   1625   }
   1626 
   1627   template <class V>
   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());
   1631 
   1632     // Entering the basic block should do any scope initialization.
   1633     Vs.enterBasicBlock(*this);
   1634 
   1635     for (auto *E : Args) {
   1636       auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
   1637       Nas.push_back(Ne);
   1638     }
   1639     for (auto *E : Instrs) {
   1640       auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
   1641       Nis.push_back(Ne);
   1642     }
   1643     auto Nt = Vs.traverse(TermInstr, Ctx);
   1644 
   1645     // Exiting the basic block should handle any scope cleanup.
   1646     Vs.exitBasicBlock(*this);
   1647 
   1648     return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
   1649   }
   1650 
   1651   template <class C>
   1652   typename C::CType compare(const BasicBlock *E, C &Cmp) const {
   1653     // TODO: implement CFG comparisons
   1654     return Cmp.comparePointers(this, E);
   1655   }
   1656 
   1657 private:
   1658   friend class SCFG;
   1659 
   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();
   1665 
   1666 private:
   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
   1677 
   1678   TopologyNode DominatorNode;       // The dominator tree
   1679   TopologyNode PostDominatorNode;   // The post-dominator tree
   1680 };
   1681 
   1682 
   1683 /// An SCFG is a control-flow graph.  It consists of a set of basic blocks,
   1684 /// each of which terminates in a branch to another basic block.  There is one
   1685 /// entry point, and one exit point.
   1686 class SCFG : public SExpr {
   1687 public:
   1688   typedef SimpleArray<BasicBlock *> BlockArray;
   1689   typedef BlockArray::iterator iterator;
   1690   typedef BlockArray::const_iterator const_iterator;
   1691 
   1692   static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
   1693 
   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));
   1702     add(Entry);
   1703     add(Exit);
   1704   }
   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!
   1709   }
   1710 
   1711   /// Return true if this CFG is valid.
   1712   bool valid() const { return Entry && Exit && Blocks.size() > 0; }
   1713 
   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; }
   1718 
   1719   iterator begin() { return Blocks.begin(); }
   1720   iterator end() { return Blocks.end(); }
   1721 
   1722   const_iterator begin() const { return cbegin(); }
   1723   const_iterator end() const { return cend(); }
   1724 
   1725   const_iterator cbegin() const { return Blocks.cbegin(); }
   1726   const_iterator cend() const { return Blocks.cend(); }
   1727 
   1728   const BasicBlock *entry() const { return Entry; }
   1729   BasicBlock *entry() { return Entry; }
   1730   const BasicBlock *exit() const { return Exit; }
   1731   BasicBlock *exit() { return Exit; }
   1732 
   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(); }
   1736 
   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; }
   1741 
   1742   inline void add(BasicBlock *BB) {
   1743     assert(BB->CFGPtr == nullptr);
   1744     BB->CFGPtr = this;
   1745     Blocks.reserveCheck(1, Arena);
   1746     Blocks.push_back(BB);
   1747   }
   1748 
   1749   void setEntry(BasicBlock *BB) { Entry = BB; }
   1750   void setExit(BasicBlock *BB)  { Exit = BB;  }
   1751 
   1752   void computeNormalForm();
   1753 
   1754   template <class V>
   1755   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
   1756     Vs.enterCFG(*this);
   1757     typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
   1758 
   1759     for (auto *B : Blocks) {
   1760       Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
   1761     }
   1762     Vs.exitCFG(*this);
   1763     return Vs.reduceSCFG(*this, Bbs);
   1764   }
   1765 
   1766   template <class C>
   1767   typename C::CType compare(const SCFG *E, C &Cmp) const {
   1768     // TODO: implement CFG comparisons
   1769     return Cmp.comparePointers(this, E);
   1770   }
   1771 
   1772 private:
   1773   void renumberInstrs();       // assign unique ids to all instructions
   1774 
   1775 private:
   1776   MemRegionRef Arena;
   1777   BlockArray   Blocks;
   1778   BasicBlock   *Entry;
   1779   BasicBlock   *Exit;
   1780   unsigned     NumInstructions;
   1781   bool         Normal;
   1782 };
   1783 
   1784 
   1785 
   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 {
   1789 public:
   1790   static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
   1791 
   1792   Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
   1793   Identifier(const Identifier& I) : SExpr(I), Name(I.Name)  { }
   1794 
   1795   StringRef name() const { return Name; }
   1796 
   1797   template <class V>
   1798   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
   1799     return Vs.reduceIdentifier(*this);
   1800   }
   1801 
   1802   template <class C>
   1803   typename C::CType compare(const Identifier* E, C& Cmp) const {
   1804     return Cmp.compareStrings(name(), E->name());
   1805   }
   1806 
   1807 private:
   1808   StringRef Name;
   1809 };
   1810 
   1811 
   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 {
   1815 public:
   1816   static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
   1817 
   1818   IfThenElse(SExpr *C, SExpr *T, SExpr *E)
   1819     : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
   1820   { }
   1821   IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
   1822     : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
   1823   { }
   1824 
   1825   SExpr *condition() { return Condition; }   // Address to store to
   1826   const SExpr *condition() const { return Condition; }
   1827 
   1828   SExpr *thenExpr() { return ThenExpr; }     // Value to store
   1829   const SExpr *thenExpr() const { return ThenExpr; }
   1830 
   1831   SExpr *elseExpr() { return ElseExpr; }     // Value to store
   1832   const SExpr *elseExpr() const { return ElseExpr; }
   1833 
   1834   template <class V>
   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);
   1840   }
   1841 
   1842   template <class C>
   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))
   1846       return Ct;
   1847     Ct = Cmp.compare(thenExpr(), E->thenExpr());
   1848     if (Cmp.notTrue(Ct))
   1849       return Ct;
   1850     return Cmp.compare(elseExpr(), E->elseExpr());
   1851   }
   1852 
   1853 private:
   1854   SExpr* Condition;
   1855   SExpr* ThenExpr;
   1856   SExpr* ElseExpr;
   1857 };
   1858 
   1859 
   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 {
   1863 public:
   1864   static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
   1865 
   1866   Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
   1867     Vd->setKind(Variable::VK_Let);
   1868   }
   1869   Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
   1870     Vd->setKind(Variable::VK_Let);
   1871   }
   1872 
   1873   Variable *variableDecl()  { return VarDecl; }
   1874   const Variable *variableDecl() const { return VarDecl; }
   1875 
   1876   SExpr *body() { return Body; }
   1877   const SExpr *body() const { return Body; }
   1878 
   1879   template <class V>
   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);
   1888   }
   1889 
   1890   template <class C>
   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))
   1895       return Ct;
   1896     Cmp.enterScope(variableDecl(), E->variableDecl());
   1897     Ct = Cmp.compare(body(), E->body());
   1898     Cmp.leaveScope();
   1899     return Ct;
   1900   }
   1901 
   1902 private:
   1903   Variable *VarDecl;
   1904   SExpr* Body;
   1905 };
   1906 
   1907 
   1908 
   1909 const SExpr *getCanonicalVal(const SExpr *E);
   1910 SExpr* simplifyToCanonicalVal(SExpr *E);
   1911 void simplifyIncompleteArg(til::Phi *Ph);
   1912 
   1913 
   1914 } // end namespace til
   1915 } // end namespace threadSafety
   1916 } // end namespace clang
   1917 
   1918 #endif
   1919