contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h

   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_THREAD_SAFETY_TIL_H
  48 #define LLVM_CLANG_THREAD_SAFETY_TIL_H
  49
  50 // All clang include dependencies for this file must be put in
  51 // ThreadSafetyUtil.h.
  52 #include "ThreadSafetyUtil.h"
  53
  54 #include <stdint.h>
  55 #include <algorithm>
  56 #include <cassert>
  57 #include <cstddef>
  58 #include <utility>
  59
  60
  61 namespace clang {
  62 namespace threadSafety {
  63 namespace til {
  64
  65
  66 enum TIL_Opcode {
  67 #define TIL_OPCODE_DEF(X) COP_##X,
  68 #include "ThreadSafetyOps.def"
  69 #undef TIL_OPCODE_DEF
  70 };
  71
  72 enum TIL_UnaryOpcode : unsigned char {
  73   UOP_Minus,        //  -
  74   UOP_BitNot,       //  ~
  75   UOP_LogicNot      //  !
  76 };
  77
  78 enum TIL_BinaryOpcode : unsigned char {
  79   BOP_Mul,          //  *
  80   BOP_Div,          //  /
  81   BOP_Rem,          //  %
  82   BOP_Add,          //  +
  83   BOP_Sub,          //  -
  84   BOP_Shl,          //  <<
  85   BOP_Shr,          //  >>
  86   BOP_BitAnd,       //  &
  87   BOP_BitXor,       //  ^
  88   BOP_BitOr,        //  |
  89   BOP_Eq,           //  ==
  90   BOP_Neq,          //  !=
  91   BOP_Lt,           //  <
  92   BOP_Leq,          //  <=
  93   BOP_LogicAnd,     //  &&
  94   BOP_LogicOr       //  ||
  95 };
  96
  97 enum TIL_CastOpcode : unsigned char {
  98   CAST_none = 0,
  99   CAST_extendNum,   // extend precision of numeric type
 100   CAST_truncNum,    // truncate precision of numeric type
 101   CAST_toFloat,     // convert to floating point type
 102   CAST_toInt,       // convert to integer type
 103 };
 104
 105 const TIL_Opcode       COP_Min  = COP_Future;
 106 const TIL_Opcode       COP_Max  = COP_Branch;
 107 const TIL_UnaryOpcode  UOP_Min  = UOP_Minus;
 108 const TIL_UnaryOpcode  UOP_Max  = UOP_LogicNot;
 109 const TIL_BinaryOpcode BOP_Min  = BOP_Mul;
 110 const TIL_BinaryOpcode BOP_Max  = BOP_LogicOr;
 111 const TIL_CastOpcode   CAST_Min = CAST_none;
 112 const TIL_CastOpcode   CAST_Max = CAST_toInt;
 113
 114 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
 115 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
 116
 117
 118 // ValueTypes are data types that can actually be held in registers.
 119 // All variables and expressions must have a vBNF_Nonealue type.
 120 // Pointer types are further subdivided into the various heap-allocated
 121 // types, such as functions, records, etc.
 122 // Structured types that are passed by value (e.g. complex numbers)
 123 // require special handling; they use BT_ValueRef, and size ST_0.
 124 struct ValueType {
 125   enum BaseType : unsigned char {
 126     BT_Void = 0,
 127     BT_Bool,
 128     BT_Int,
 129     BT_Float,
 130     BT_String,    // String literals
 131     BT_Pointer,
 132     BT_ValueRef
 133   };
 134
 135   enum SizeType : unsigned char {
 136     ST_0 = 0,
 137     ST_1,
 138     ST_8,
 139     ST_16,
 140     ST_32,
 141     ST_64,
 142     ST_128
 143   };
 144
 145   inline static SizeType getSizeType(unsigned nbytes);
 146
 147   template <class T>
 148   inline static ValueType getValueType();
 149
 150   ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
 151       : Base(B), Size(Sz), Signed(S), VectSize(VS)
 152   { }
 153
 154   BaseType      Base;
 155   SizeType      Size;
 156   bool          Signed;
 157   unsigned char VectSize;  // 0 for scalar, otherwise num elements in vector
 158 };
 159
 160
 161 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
 162   switch (nbytes) {
 163     case 1: return ST_8;
 164     case 2: return ST_16;
 165     case 4: return ST_32;
 166     case 8: return ST_64;
 167     case 16: return ST_128;
 168     default: return ST_0;
 169   }
 170 }
 171
 172
 173 template<>
 174 inline ValueType ValueType::getValueType<void>() {
 175   return ValueType(BT_Void, ST_0, false, 0);
 176 }
 177
 178 template<>
 179 inline ValueType ValueType::getValueType<bool>() {
 180   return ValueType(BT_Bool, ST_1, false, 0);
 181 }
 182
 183 template<>
 184 inline ValueType ValueType::getValueType<int8_t>() {
 185   return ValueType(BT_Int, ST_8, true, 0);
 186 }
 187
 188 template<>
 189 inline ValueType ValueType::getValueType<uint8_t>() {
 190   return ValueType(BT_Int, ST_8, false, 0);
 191 }
 192
 193 template<>
 194 inline ValueType ValueType::getValueType<int16_t>() {
 195   return ValueType(BT_Int, ST_16, true, 0);
 196 }
 197
 198 template<>
 199 inline ValueType ValueType::getValueType<uint16_t>() {
 200   return ValueType(BT_Int, ST_16, false, 0);
 201 }
 202
 203 template<>
 204 inline ValueType ValueType::getValueType<int32_t>() {
 205   return ValueType(BT_Int, ST_32, true, 0);
 206 }
 207
 208 template<>
 209 inline ValueType ValueType::getValueType<uint32_t>() {
 210   return ValueType(BT_Int, ST_32, false, 0);
 211 }
 212
 213 template<>
 214 inline ValueType ValueType::getValueType<int64_t>() {
 215   return ValueType(BT_Int, ST_64, true, 0);
 216 }
 217
 218 template<>
 219 inline ValueType ValueType::getValueType<uint64_t>() {
 220   return ValueType(BT_Int, ST_64, false, 0);
 221 }
 222
 223 template<>
 224 inline ValueType ValueType::getValueType<float>() {
 225   return ValueType(BT_Float, ST_32, true, 0);
 226 }
 227
 228 template<>
 229 inline ValueType ValueType::getValueType<double>() {
 230   return ValueType(BT_Float, ST_64, true, 0);
 231 }
 232
 233 template<>
 234 inline ValueType ValueType::getValueType<long double>() {
 235   return ValueType(BT_Float, ST_128, true, 0);
 236 }
 237
 238 template<>
 239 inline ValueType ValueType::getValueType<StringRef>() {
 240   return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
 241 }
 242
 243 template<>
 244 inline ValueType ValueType::getValueType<void*>() {
 245   return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
 246 }
 247
 248
 249
 250 // Base class for AST nodes in the typed intermediate language.
 251 class SExpr {
 252 public:
 253   TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
 254
 255   // Subclasses of SExpr must define the following:
 256   //
 257   // This(const This& E, ...) {
 258   //   copy constructor: construct copy of E, with some additional arguments.
 259   // }
 260   //
 261   // template <class V>
 262   // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 263   //   traverse all subexpressions, following the traversal/rewriter interface.
 264   // }
 265   //
 266   // template <class C> typename C::CType compare(CType* E, C& Cmp) {
 267   //   compare all subexpressions, following the comparator interface
 268   // }
 269
 270   void *operator new(size_t S, MemRegionRef &R) {
 271     return ::operator new(S, R);
 272   }
 273
 274   // SExpr objects cannot be deleted.
 275   // This declaration is public to workaround a gcc bug that breaks building
 276   // with REQUIRES_EH=1.
 277   void operator delete(void *) LLVM_DELETED_FUNCTION;
 278
 279 protected:
 280   SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {}
 281   SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {}
 282
 283   const unsigned char Opcode;
 284   unsigned char Reserved;
 285   unsigned short Flags;
 286
 287 private:
 288   SExpr() LLVM_DELETED_FUNCTION;
 289
 290   // SExpr objects must be created in an arena.
 291   void *operator new(size_t) LLVM_DELETED_FUNCTION;
 292 };
 293
 294
 295 // Class for owning references to SExprs.
 296 // Includes attach/detach logic for counting variable references and lazy
 297 // rewriting strategies.
 298 class SExprRef {
 299 public:
 300   SExprRef() : Ptr(nullptr) { }
 301   SExprRef(std::nullptr_t P) : Ptr(nullptr) { }
 302   SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; }
 303
 304   // Defined after Variable and Future, below.
 305   inline SExprRef(SExpr *P);
 306   inline ~SExprRef();
 307
 308   SExpr       *get()       { return Ptr; }
 309   const SExpr *get() const { return Ptr; }
 310
 311   SExpr       *operator->()       { return get(); }
 312   const SExpr *operator->() const { return get(); }
 313
 314   SExpr       &operator*()        { return *Ptr; }
 315   const SExpr &operator*() const  { return *Ptr; }
 316
 317   bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; }
 318   bool operator!=(const SExprRef &R) const { return !operator==(R); }
 319   bool operator==(const SExpr *P)    const { return Ptr == P; }
 320   bool operator!=(const SExpr *P)    const { return !operator==(P); }
 321   bool operator==(std::nullptr_t)    const { return Ptr == nullptr; }
 322   bool operator!=(std::nullptr_t)    const { return Ptr != nullptr; }
 323
 324   inline void reset(SExpr *E);
 325
 326 private:
 327   inline void attach();
 328   inline void detach();
 329
 330   SExpr *Ptr;
 331 };
 332
 333
 334 // Contains various helper functions for SExprs.
 335 namespace ThreadSafetyTIL {
 336   inline bool isTrivial(const SExpr *E) {
 337     unsigned Op = E->opcode();
 338     return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
 339   }
 340 }
 341
 342 // Nodes which declare variables
 343 class Function;
 344 class SFunction;
 345 class BasicBlock;
 346 class Let;
 347
 348
 349 // A named variable, e.g. "x".
 350 //
 351 // There are two distinct places in which a Variable can appear in the AST.
 352 // A variable declaration introduces a new variable, and can occur in 3 places:
 353 //   Let-expressions:           (Let (x = t) u)
 354 //   Functions:                 (Function (x : t) u)
 355 //   Self-applicable functions  (SFunction (x) t)
 356 //
 357 // If a variable occurs in any other location, it is a reference to an existing
 358 // variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
 359 // allocate a separate AST node for variable references; a reference is just a
 360 // pointer to the original declaration.
 361 class Variable : public SExpr {
 362 public:
 363   static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
 364
 365   // Let-variable, function parameter, or self-variable
 366   enum VariableKind {
 367     VK_Let,
 368     VK_LetBB,
 369     VK_Fun,
 370     VK_SFun
 371   };
 372
 373   // These are defined after SExprRef contructor, below
 374   inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr);
 375   inline Variable(StringRef s, SExpr *D = nullptr);
 376   inline Variable(const Variable &Vd, SExpr *D);
 377
 378   VariableKind kind() const { return static_cast<VariableKind>(Flags); }
 379
 380   const StringRef name() const { return Name; }
 381   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
 382
 383   // Returns the definition (for let vars) or type (for parameter & self vars)
 384   SExpr *definition() { return Definition.get(); }
 385   const SExpr *definition() const { return Definition.get(); }
 386
 387   void attachVar() const { ++NumUses; }
 388   void detachVar() const { assert(NumUses > 0); --NumUses; }
 389
 390   unsigned getID() const { return Id; }
 391   unsigned getBlockID() const { return BlockID; }
 392
 393   void setName(StringRef S) { Name = S; }
 394   void setID(unsigned Bid, unsigned I) {
 395     BlockID = static_cast<unsigned short>(Bid);
 396     Id = static_cast<unsigned short>(I);
 397   }
 398   void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
 399   void setDefinition(SExpr *E);
 400   void setKind(VariableKind K) { Flags = K; }
 401
 402   template <class V>
 403   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 404     // This routine is only called for variable references.
 405     return Vs.reduceVariableRef(this);
 406   }
 407
 408   template <class C> typename C::CType compare(Variable* E, C& Cmp) {
 409     return Cmp.compareVariableRefs(this, E);
 410   }
 411
 412 private:
 413   friend class Function;
 414   friend class SFunction;
 415   friend class BasicBlock;
 416   friend class Let;
 417
 418   StringRef Name;                  // The name of the variable.
 419   SExprRef  Definition;            // The TIL type or definition
 420   const clang::ValueDecl *Cvdecl;  // The clang declaration for this variable.
 421
 422   unsigned short BlockID;
 423   unsigned short Id;
 424   mutable unsigned NumUses;
 425 };
 426
 427
 428 // Placeholder for an expression that has not yet been created.
 429 // Used to implement lazy copy and rewriting strategies.
 430 class Future : public SExpr {
 431 public:
 432   static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
 433
 434   enum FutureStatus {
 435     FS_pending,
 436     FS_evaluating,
 437     FS_done
 438   };
 439
 440   Future() :
 441     SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr)
 442   {}
 443 private:
 444   virtual ~Future() LLVM_DELETED_FUNCTION;
 445 public:
 446
 447   // Registers the location in the AST where this future is stored.
 448   // Forcing the future will automatically update the AST.
 449   static inline void registerLocation(SExprRef *Member) {
 450     if (Future *F = dyn_cast_or_null<Future>(Member->get()))
 451       F->Location = Member;
 452   }
 453
 454   // A lazy rewriting strategy should subclass Future and override this method.
 455   virtual SExpr *create() { return nullptr; }
 456
 457   // Return the result of this future if it exists, otherwise return null.
 458   SExpr *maybeGetResult() {
 459     return Result;
 460   }
 461
 462   // Return the result of this future; forcing it if necessary.
 463   SExpr *result() {
 464     switch (Status) {
 465     case FS_pending:
 466       force();
 467       return Result;
 468     case FS_evaluating:
 469       return nullptr; // infinite loop; illegal recursion.
 470     case FS_done:
 471       return Result;
 472     }
 473   }
 474
 475   template <class V>
 476   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 477     assert(Result && "Cannot traverse Future that has not been forced.");
 478     return Vs.traverse(Result, Ctx);
 479   }
 480
 481   template <class C> typename C::CType compare(Future* E, C& Cmp) {
 482     if (!Result || !E->Result)
 483       return Cmp.comparePointers(this, E);
 484     return Cmp.compare(Result, E->Result);
 485   }
 486
 487 private:
 488   // Force the future.
 489   inline void force();
 490
 491   FutureStatus Status;
 492   SExpr *Result;
 493   SExprRef *Location;
 494 };
 495
 496
 497 inline void SExprRef::attach() {
 498   if (!Ptr)
 499     return;
 500
 501   TIL_Opcode Op = Ptr->opcode();
 502   if (Op == COP_Variable) {
 503     cast<Variable>(Ptr)->attachVar();
 504   } else if (Op == COP_Future) {
 505     cast<Future>(Ptr)->registerLocation(this);
 506   }
 507 }
 508
 509 inline void SExprRef::detach() {
 510   if (Ptr && Ptr->opcode() == COP_Variable) {
 511     cast<Variable>(Ptr)->detachVar();
 512   }
 513 }
 514
 515 inline SExprRef::SExprRef(SExpr *P) : Ptr(P) {
 516   attach();
 517 }
 518
 519 inline SExprRef::~SExprRef() {
 520   detach();
 521 }
 522
 523 inline void SExprRef::reset(SExpr *P) {
 524   detach();
 525   Ptr = P;
 526   attach();
 527 }
 528
 529
 530 inline Variable::Variable(StringRef s, SExpr *D)
 531     : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr),
 532       BlockID(0), Id(0), NumUses(0) {
 533   Flags = VK_Let;
 534 }
 535
 536 inline Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd)
 537     : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
 538       Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) {
 539   Flags = VK_Let;
 540 }
 541
 542 inline Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor
 543     : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl),
 544       BlockID(0), Id(0), NumUses(0) {
 545   Flags = Vd.kind();
 546 }
 547
 548 inline void Variable::setDefinition(SExpr *E) {
 549   Definition.reset(E);
 550 }
 551
 552 void Future::force() {
 553   Status = FS_evaluating;
 554   SExpr *R = create();
 555   Result = R;
 556   if (Location)
 557     Location->reset(R);
 558   Status = FS_done;
 559 }
 560
 561
 562 // Placeholder for C++ expressions that cannot be represented in the TIL.
 563 class Undefined : public SExpr {
 564 public:
 565   static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
 566
 567   Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
 568   Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
 569
 570   template <class V>
 571   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 572     return Vs.reduceUndefined(*this);
 573   }
 574
 575   template <class C> typename C::CType compare(Undefined* E, C& Cmp) {
 576     return Cmp.comparePointers(Cstmt, E->Cstmt);
 577   }
 578
 579 private:
 580   const clang::Stmt *Cstmt;
 581 };
 582
 583
 584 // Placeholder for a wildcard that matches any other expression.
 585 class Wildcard : public SExpr {
 586 public:
 587   static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
 588
 589   Wildcard() : SExpr(COP_Wildcard) {}
 590   Wildcard(const Wildcard &W) : SExpr(W) {}
 591
 592   template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 593     return Vs.reduceWildcard(*this);
 594   }
 595
 596   template <class C> typename C::CType compare(Wildcard* E, C& Cmp) {
 597     return Cmp.trueResult();
 598   }
 599 };
 600
 601
 602 template <class T> class LiteralT;
 603
 604 // Base class for literal values.
 605 class Literal : public SExpr {
 606 public:
 607   static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
 608
 609   Literal(const clang::Expr *C)
 610      : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
 611   { }
 612   Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
 613   Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
 614
 615   // The clang expression for this literal.
 616   const clang::Expr *clangExpr() const { return Cexpr; }
 617
 618   ValueType valueType() const { return ValType; }
 619
 620   template<class T> const LiteralT<T>& as() const {
 621     return *static_cast<const LiteralT<T>*>(this);
 622   }
 623   template<class T> LiteralT<T>& as() {
 624     return *static_cast<LiteralT<T>*>(this);
 625   }
 626
 627   template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
 628
 629   template <class C> typename C::CType compare(Literal* E, C& Cmp) {
 630     // TODO -- use value, not pointer equality
 631     return Cmp.comparePointers(Cexpr, E->Cexpr);
 632   }
 633
 634 private:
 635   const ValueType ValType;
 636   const clang::Expr *Cexpr;
 637 };
 638
 639
 640 // Derived class for literal values, which stores the actual value.
 641 template<class T>
 642 class LiteralT : public Literal {
 643 public:
 644   LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
 645   LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
 646
 647   T  value() const { return Val;}
 648   T& value() { return Val; }
 649
 650 private:
 651   T Val;
 652 };
 653
 654
 655
 656 template <class V>
 657 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
 658   if (Cexpr)
 659     return Vs.reduceLiteral(*this);
 660
 661   switch (ValType.Base) {
 662   case ValueType::BT_Void:
 663     break;
 664   case ValueType::BT_Bool:
 665     return Vs.reduceLiteralT(as<bool>());
 666   case ValueType::BT_Int: {
 667     switch (ValType.Size) {
 668     case ValueType::ST_8:
 669       if (ValType.Signed)
 670         return Vs.reduceLiteralT(as<int8_t>());
 671       else
 672         return Vs.reduceLiteralT(as<uint8_t>());
 673     case ValueType::ST_16:
 674       if (ValType.Signed)
 675         return Vs.reduceLiteralT(as<int16_t>());
 676       else
 677         return Vs.reduceLiteralT(as<uint16_t>());
 678     case ValueType::ST_32:
 679       if (ValType.Signed)
 680         return Vs.reduceLiteralT(as<int32_t>());
 681       else
 682         return Vs.reduceLiteralT(as<uint32_t>());
 683     case ValueType::ST_64:
 684       if (ValType.Signed)
 685         return Vs.reduceLiteralT(as<int64_t>());
 686       else
 687         return Vs.reduceLiteralT(as<uint64_t>());
 688     default:
 689       break;
 690     }
 691   }
 692   case ValueType::BT_Float: {
 693     switch (ValType.Size) {
 694     case ValueType::ST_32:
 695       return Vs.reduceLiteralT(as<float>());
 696     case ValueType::ST_64:
 697       return Vs.reduceLiteralT(as<double>());
 698     default:
 699       break;
 700     }
 701   }
 702   case ValueType::BT_String:
 703     return Vs.reduceLiteralT(as<StringRef>());
 704   case ValueType::BT_Pointer:
 705     return Vs.reduceLiteralT(as<void*>());
 706   case ValueType::BT_ValueRef:
 707     break;
 708   }
 709   return Vs.reduceLiteral(*this);
 710 }
 711
 712
 713 // Literal pointer to an object allocated in memory.
 714 // At compile time, pointer literals are represented by symbolic names.
 715 class LiteralPtr : public SExpr {
 716 public:
 717   static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
 718
 719   LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
 720   LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
 721
 722   // The clang declaration for the value that this pointer points to.
 723   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
 724
 725   template <class V>
 726   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 727     return Vs.reduceLiteralPtr(*this);
 728   }
 729
 730   template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) {
 731     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
 732   }
 733
 734 private:
 735   const clang::ValueDecl *Cvdecl;
 736 };
 737
 738
 739 // A function -- a.k.a. lambda abstraction.
 740 // Functions with multiple arguments are created by currying,
 741 // e.g. (function (x: Int) (function (y: Int) (add x y)))
 742 class Function : public SExpr {
 743 public:
 744   static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
 745
 746   Function(Variable *Vd, SExpr *Bd)
 747       : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
 748     Vd->setKind(Variable::VK_Fun);
 749   }
 750   Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
 751       : SExpr(F), VarDecl(Vd), Body(Bd) {
 752     Vd->setKind(Variable::VK_Fun);
 753   }
 754
 755   Variable *variableDecl()  { return VarDecl; }
 756   const Variable *variableDecl() const { return VarDecl; }
 757
 758   SExpr *body() { return Body.get(); }
 759   const SExpr *body() const { return Body.get(); }
 760
 761   template <class V>
 762   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 763     // This is a variable declaration, so traverse the definition.
 764     auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
 765     // Tell the rewriter to enter the scope of the function.
 766     Variable *Nvd = Vs.enterScope(*VarDecl, E0);
 767     auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
 768     Vs.exitScope(*VarDecl);
 769     return Vs.reduceFunction(*this, Nvd, E1);
 770   }
 771
 772   template <class C> typename C::CType compare(Function* E, C& Cmp) {
 773     typename C::CType Ct =
 774       Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
 775     if (Cmp.notTrue(Ct))
 776       return Ct;
 777     Cmp.enterScope(variableDecl(), E->variableDecl());
 778     Ct = Cmp.compare(body(), E->body());
 779     Cmp.leaveScope();
 780     return Ct;
 781   }
 782
 783 private:
 784   Variable *VarDecl;
 785   SExprRef Body;
 786 };
 787
 788
 789 // A self-applicable function.
 790 // A self-applicable function can be applied to itself.  It's useful for
 791 // implementing objects and late binding
 792 class SFunction : public SExpr {
 793 public:
 794   static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
 795
 796   SFunction(Variable *Vd, SExpr *B)
 797       : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
 798     assert(Vd->Definition == nullptr);
 799     Vd->setKind(Variable::VK_SFun);
 800     Vd->Definition.reset(this);
 801   }
 802   SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
 803       : SExpr(F), VarDecl(Vd), Body(B) {
 804     assert(Vd->Definition == nullptr);
 805     Vd->setKind(Variable::VK_SFun);
 806     Vd->Definition.reset(this);
 807   }
 808
 809   Variable *variableDecl() { return VarDecl; }
 810   const Variable *variableDecl() const { return VarDecl; }
 811
 812   SExpr *body() { return Body.get(); }
 813   const SExpr *body() const { return Body.get(); }
 814
 815   template <class V>
 816   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 817     // A self-variable points to the SFunction itself.
 818     // A rewrite must introduce the variable with a null definition, and update
 819     // it after 'this' has been rewritten.
 820     Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
 821     auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
 822     Vs.exitScope(*VarDecl);
 823     // A rewrite operation will call SFun constructor to set Vvd->Definition.
 824     return Vs.reduceSFunction(*this, Nvd, E1);
 825   }
 826
 827   template <class C> typename C::CType compare(SFunction* E, C& Cmp) {
 828     Cmp.enterScope(variableDecl(), E->variableDecl());
 829     typename C::CType Ct = Cmp.compare(body(), E->body());
 830     Cmp.leaveScope();
 831     return Ct;
 832   }
 833
 834 private:
 835   Variable *VarDecl;
 836   SExprRef Body;
 837 };
 838
 839
 840 // A block of code -- e.g. the body of a function.
 841 class Code : public SExpr {
 842 public:
 843   static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
 844
 845   Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
 846   Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
 847       : SExpr(C), ReturnType(T), Body(B) {}
 848
 849   SExpr *returnType() { return ReturnType.get(); }
 850   const SExpr *returnType() const { return ReturnType.get(); }
 851
 852   SExpr *body() { return Body.get(); }
 853   const SExpr *body() const { return Body.get(); }
 854
 855   template <class V>
 856   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 857     auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
 858     auto Nb = Vs.traverse(Body,       Vs.lazyCtx(Ctx));
 859     return Vs.reduceCode(*this, Nt, Nb);
 860   }
 861
 862   template <class C> typename C::CType compare(Code* E, C& Cmp) {
 863     typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
 864     if (Cmp.notTrue(Ct))
 865       return Ct;
 866     return Cmp.compare(body(), E->body());
 867   }
 868
 869 private:
 870   SExprRef ReturnType;
 871   SExprRef Body;
 872 };
 873
 874
 875 // A typed, writable location in memory
 876 class Field : public SExpr {
 877 public:
 878   static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
 879
 880   Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
 881   Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
 882       : SExpr(C), Range(R), Body(B) {}
 883
 884   SExpr *range() { return Range.get(); }
 885   const SExpr *range() const { return Range.get(); }
 886
 887   SExpr *body() { return Body.get(); }
 888   const SExpr *body() const { return Body.get(); }
 889
 890   template <class V>
 891   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 892     auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
 893     auto Nb = Vs.traverse(Body,  Vs.lazyCtx(Ctx));
 894     return Vs.reduceField(*this, Nr, Nb);
 895   }
 896
 897   template <class C> typename C::CType compare(Field* E, C& Cmp) {
 898     typename C::CType Ct = Cmp.compare(range(), E->range());
 899     if (Cmp.notTrue(Ct))
 900       return Ct;
 901     return Cmp.compare(body(), E->body());
 902   }
 903
 904 private:
 905   SExprRef Range;
 906   SExprRef Body;
 907 };
 908
 909
 910 // Apply an argument to a function
 911 class Apply : public SExpr {
 912 public:
 913   static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
 914
 915   Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
 916   Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
 917       : SExpr(A), Fun(F), Arg(Ar)
 918   {}
 919
 920   SExpr *fun() { return Fun.get(); }
 921   const SExpr *fun() const { return Fun.get(); }
 922
 923   SExpr *arg() { return Arg.get(); }
 924   const SExpr *arg() const { return Arg.get(); }
 925
 926   template <class V>
 927   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 928     auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
 929     auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
 930     return Vs.reduceApply(*this, Nf, Na);
 931   }
 932
 933   template <class C> typename C::CType compare(Apply* E, C& Cmp) {
 934     typename C::CType Ct = Cmp.compare(fun(), E->fun());
 935     if (Cmp.notTrue(Ct))
 936       return Ct;
 937     return Cmp.compare(arg(), E->arg());
 938   }
 939
 940 private:
 941   SExprRef Fun;
 942   SExprRef Arg;
 943 };
 944
 945
 946 // Apply a self-argument to a self-applicable function
 947 class SApply : public SExpr {
 948 public:
 949   static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
 950
 951   SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
 952   SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
 953       : SExpr(A), Sfun(Sf), Arg(Ar) {}
 954
 955   SExpr *sfun() { return Sfun.get(); }
 956   const SExpr *sfun() const { return Sfun.get(); }
 957
 958   SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); }
 959   const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); }
 960
 961   bool isDelegation() const { return Arg == nullptr; }
 962
 963   template <class V>
 964   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
 965     auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
 966     typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
 967                                        : nullptr;
 968     return Vs.reduceSApply(*this, Nf, Na);
 969   }
 970
 971   template <class C> typename C::CType compare(SApply* E, C& Cmp) {
 972     typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
 973     if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
 974       return Ct;
 975     return Cmp.compare(arg(), E->arg());
 976   }
 977
 978 private:
 979   SExprRef Sfun;
 980   SExprRef Arg;
 981 };
 982
 983
 984 // Project a named slot from a C++ struct or class.
 985 class Project : public SExpr {
 986 public:
 987   static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
 988
 989   Project(SExpr *R, StringRef SName)
 990       : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
 991   { }
 992   Project(SExpr *R, clang::ValueDecl *Cvd)
 993       : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
 994   { }
 995   Project(const Project &P, SExpr *R)
 996       : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
 997   { }
 998
 999   SExpr *record() { return Rec.get(); }
1000   const SExpr *record() const { return Rec.get(); }
1001
1002   const clang::ValueDecl *clangValueDecl() const { return Cvdecl; }
1003
1004   StringRef slotName() const {
1005     if (Cvdecl)
1006       return Cvdecl->getName();
1007     else
1008       return SlotName;
1009   }
1010
1011   template <class V>
1012   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1013     auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
1014     return Vs.reduceProject(*this, Nr);
1015   }
1016
1017   template <class C> typename C::CType compare(Project* E, C& Cmp) {
1018     typename C::CType Ct = Cmp.compare(record(), E->record());
1019     if (Cmp.notTrue(Ct))
1020       return Ct;
1021     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
1022   }
1023
1024 private:
1025   SExprRef Rec;
1026   StringRef SlotName;
1027   clang::ValueDecl *Cvdecl;
1028 };
1029
1030
1031 // Call a function (after all arguments have been applied).
1032 class Call : public SExpr {
1033 public:
1034   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1035
1036   Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
1037       : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
1038   Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
1039
1040   SExpr *target() { return Target.get(); }
1041   const SExpr *target() const { return Target.get(); }
1042
1043   const clang::CallExpr *clangCallExpr() const { return Cexpr; }
1044
1045   template <class V>
1046   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1047     auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
1048     return Vs.reduceCall(*this, Nt);
1049   }
1050
1051   template <class C> typename C::CType compare(Call* E, C& Cmp) {
1052     return Cmp.compare(target(), E->target());
1053   }
1054
1055 private:
1056   SExprRef Target;
1057   const clang::CallExpr *Cexpr;
1058 };
1059
1060
1061 // Allocate memory for a new value on the heap or stack.
1062 class Alloc : public SExpr {
1063 public:
1064   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1065
1066   enum AllocKind {
1067     AK_Stack,
1068     AK_Heap
1069   };
1070
1071   Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1072   Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1073
1074   AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1075
1076   SExpr *dataType() { return Dtype.get(); }
1077   const SExpr *dataType() const { return Dtype.get(); }
1078
1079   template <class V>
1080   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1081     auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1082     return Vs.reduceAlloc(*this, Nd);
1083   }
1084
1085   template <class C> typename C::CType compare(Alloc* E, C& Cmp) {
1086     typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1087     if (Cmp.notTrue(Ct))
1088       return Ct;
1089     return Cmp.compare(dataType(), E->dataType());
1090   }
1091
1092 private:
1093   SExprRef Dtype;
1094 };
1095
1096
1097 // Load a value from memory.
1098 class Load : public SExpr {
1099 public:
1100   static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1101
1102   Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1103   Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1104
1105   SExpr *pointer() { return Ptr.get(); }
1106   const SExpr *pointer() const { return Ptr.get(); }
1107
1108   template <class V>
1109   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1110     auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1111     return Vs.reduceLoad(*this, Np);
1112   }
1113
1114   template <class C> typename C::CType compare(Load* E, C& Cmp) {
1115     return Cmp.compare(pointer(), E->pointer());
1116   }
1117
1118 private:
1119   SExprRef Ptr;
1120 };
1121
1122
1123 // Store a value to memory.
1124 // Source is a pointer, destination is the value to store.
1125 class Store : public SExpr {
1126 public:
1127   static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1128
1129   Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1130   Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1131
1132   SExpr *destination() { return Dest.get(); }  // Address to store to
1133   const SExpr *destination() const { return Dest.get(); }
1134
1135   SExpr *source() { return Source.get(); }     // Value to store
1136   const SExpr *source() const { return Source.get(); }
1137
1138   template <class V>
1139   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1140     auto Np = Vs.traverse(Dest,   Vs.subExprCtx(Ctx));
1141     auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1142     return Vs.reduceStore(*this, Np, Nv);
1143   }
1144
1145   template <class C> typename C::CType compare(Store* E, C& Cmp) {
1146     typename C::CType Ct = Cmp.compare(destination(), E->destination());
1147     if (Cmp.notTrue(Ct))
1148       return Ct;
1149     return Cmp.compare(source(), E->source());
1150   }
1151
1152 private:
1153   SExprRef Dest;
1154   SExprRef Source;
1155 };
1156
1157
1158 // If p is a reference to an array, then first(p) is a reference to the first
1159 // element.  The usual array notation p[i]  becomes first(p + i).
1160 class ArrayIndex : public SExpr {
1161 public:
1162   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1163
1164   ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1165   ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1166     : SExpr(E), Array(A), Index(N) {}
1167
1168   SExpr *array() { return Array.get(); }
1169   const SExpr *array() const { return Array.get(); }
1170
1171   SExpr *index() { return Index.get(); }
1172   const SExpr *index() const { return Index.get(); }
1173
1174   template <class V>
1175   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1176     auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1177     auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1178     return Vs.reduceArrayIndex(*this, Na, Ni);
1179   }
1180
1181   template <class C> typename C::CType compare(ArrayIndex* E, C& Cmp) {
1182     typename C::CType Ct = Cmp.compare(array(), E->array());
1183     if (Cmp.notTrue(Ct))
1184       return Ct;
1185     return Cmp.compare(index(), E->index());
1186   }
1187
1188 private:
1189   SExprRef Array;
1190   SExprRef Index;
1191 };
1192
1193
1194 // Pointer arithmetic, restricted to arrays only.
1195 // If p is a reference to an array, then p + n, where n is an integer, is
1196 // a reference to a subarray.
1197 class ArrayAdd : public SExpr {
1198 public:
1199   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1200
1201   ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1202   ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1203     : SExpr(E), Array(A), Index(N) {}
1204
1205   SExpr *array() { return Array.get(); }
1206   const SExpr *array() const { return Array.get(); }
1207
1208   SExpr *index() { return Index.get(); }
1209   const SExpr *index() const { return Index.get(); }
1210
1211   template <class V>
1212   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1213     auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1214     auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1215     return Vs.reduceArrayAdd(*this, Na, Ni);
1216   }
1217
1218   template <class C> typename C::CType compare(ArrayAdd* E, C& Cmp) {
1219     typename C::CType Ct = Cmp.compare(array(), E->array());
1220     if (Cmp.notTrue(Ct))
1221       return Ct;
1222     return Cmp.compare(index(), E->index());
1223   }
1224
1225 private:
1226   SExprRef Array;
1227   SExprRef Index;
1228 };
1229
1230
1231 // Simple unary operation -- e.g. !, ~, etc.
1232 class UnaryOp : public SExpr {
1233 public:
1234   static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1235
1236   UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1237     Flags = Op;
1238   }
1239   UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1240
1241   TIL_UnaryOpcode unaryOpcode() const {
1242     return static_cast<TIL_UnaryOpcode>(Flags);
1243   }
1244
1245   SExpr *expr() { return Expr0.get(); }
1246   const SExpr *expr() const { return Expr0.get(); }
1247
1248   template <class V>
1249   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1250     auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1251     return Vs.reduceUnaryOp(*this, Ne);
1252   }
1253
1254   template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) {
1255     typename C::CType Ct =
1256       Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1257     if (Cmp.notTrue(Ct))
1258       return Ct;
1259     return Cmp.compare(expr(), E->expr());
1260   }
1261
1262 private:
1263   SExprRef Expr0;
1264 };
1265
1266
1267 // Simple binary operation -- e.g. +, -, etc.
1268 class BinaryOp : public SExpr {
1269 public:
1270   static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1271
1272   BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1273       : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1274     Flags = Op;
1275   }
1276   BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1277       : SExpr(B), Expr0(E0), Expr1(E1) {
1278     Flags = B.Flags;
1279   }
1280
1281   TIL_BinaryOpcode binaryOpcode() const {
1282     return static_cast<TIL_BinaryOpcode>(Flags);
1283   }
1284
1285   SExpr *expr0() { return Expr0.get(); }
1286   const SExpr *expr0() const { return Expr0.get(); }
1287
1288   SExpr *expr1() { return Expr1.get(); }
1289   const SExpr *expr1() const { return Expr1.get(); }
1290
1291   template <class V>
1292   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1293     auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1294     auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1295     return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1296   }
1297
1298   template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) {
1299     typename C::CType Ct =
1300       Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1301     if (Cmp.notTrue(Ct))
1302       return Ct;
1303     Ct = Cmp.compare(expr0(), E->expr0());
1304     if (Cmp.notTrue(Ct))
1305       return Ct;
1306     return Cmp.compare(expr1(), E->expr1());
1307   }
1308
1309 private:
1310   SExprRef Expr0;
1311   SExprRef Expr1;
1312 };
1313
1314
1315 // Cast expression
1316 class Cast : public SExpr {
1317 public:
1318   static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1319
1320   Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1321   Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1322
1323   TIL_CastOpcode castOpcode() const {
1324     return static_cast<TIL_CastOpcode>(Flags);
1325   }
1326
1327   SExpr *expr() { return Expr0.get(); }
1328   const SExpr *expr() const { return Expr0.get(); }
1329
1330   template <class V>
1331   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1332     auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1333     return Vs.reduceCast(*this, Ne);
1334   }
1335
1336   template <class C> typename C::CType compare(Cast* E, C& Cmp) {
1337     typename C::CType Ct =
1338       Cmp.compareIntegers(castOpcode(), E->castOpcode());
1339     if (Cmp.notTrue(Ct))
1340       return Ct;
1341     return Cmp.compare(expr(), E->expr());
1342   }
1343
1344 private:
1345   SExprRef Expr0;
1346 };
1347
1348
1349 class SCFG;
1350
1351
1352 class Phi : public SExpr {
1353 public:
1354   // TODO: change to SExprRef
1355   typedef SimpleArray<SExpr *> ValArray;
1356
1357   // In minimal SSA form, all Phi nodes are MultiVal.
1358   // During conversion to SSA, incomplete Phi nodes may be introduced, which
1359   // are later determined to be SingleVal, and are thus redundant.
1360   enum Status {
1361     PH_MultiVal = 0, // Phi node has multiple distinct values.  (Normal)
1362     PH_SingleVal,    // Phi node has one distinct value, and can be eliminated
1363     PH_Incomplete    // Phi node is incomplete
1364   };
1365
1366   static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1367
1368   Phi() : SExpr(COP_Phi) {}
1369   Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1370   Phi(const Phi &P, ValArray &&Vs)    : SExpr(P), Values(std::move(Vs)) {}
1371
1372   const ValArray &values() const { return Values; }
1373   ValArray &values() { return Values; }
1374
1375   Status status() const { return static_cast<Status>(Flags); }
1376   void setStatus(Status s) { Flags = s; }
1377
1378   template <class V>
1379   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1380     typename V::template Container<typename V::R_SExpr>
1381       Nvs(Vs, Values.size());
1382
1383     for (auto *Val : Values) {
1384       Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1385     }
1386     return Vs.reducePhi(*this, Nvs);
1387   }
1388
1389   template <class C> typename C::CType compare(Phi *E, C &Cmp) {
1390     // TODO: implement CFG comparisons
1391     return Cmp.comparePointers(this, E);
1392   }
1393
1394 private:
1395   ValArray Values;
1396 };
1397
1398
1399 // A basic block is part of an SCFG, and can be treated as a function in
1400 // continuation passing style.  It consists of a sequence of phi nodes, which
1401 // are "arguments" to the function, followed by a sequence of instructions.
1402 // Both arguments and instructions define new variables.  It ends with a
1403 // branch or goto to another basic block in the same SCFG.
1404 class BasicBlock : public SExpr {
1405 public:
1406   typedef SimpleArray<Variable*>   VarArray;
1407   typedef SimpleArray<BasicBlock*> BlockArray;
1408
1409   static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1410
1411   explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr)
1412       : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),
1413         Parent(P), Terminator(nullptr)
1414   { }
1415   BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T)
1416       : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0),
1417         Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)),
1418         Terminator(T)
1419   { }
1420
1421   unsigned blockID() const { return BlockID; }
1422   unsigned numPredecessors() const { return Predecessors.size(); }
1423
1424   const SCFG* cfg() const { return CFGPtr; }
1425   SCFG* cfg() { return CFGPtr; }
1426
1427   const BasicBlock *parent() const { return Parent; }
1428   BasicBlock *parent() { return Parent; }
1429
1430   const VarArray &arguments() const { return Args; }
1431   VarArray &arguments() { return Args; }
1432
1433   const VarArray &instructions() const { return Instrs; }
1434   VarArray &instructions() { return Instrs; }
1435
1436   const BlockArray &predecessors() const { return Predecessors; }
1437   BlockArray &predecessors() { return Predecessors; }
1438
1439   const SExpr *terminator() const { return Terminator.get(); }
1440   SExpr *terminator() { return Terminator.get(); }
1441
1442   void setBlockID(unsigned i)   { BlockID = i; }
1443   void setParent(BasicBlock *P) { Parent = P;  }
1444   void setTerminator(SExpr *E)  { Terminator.reset(E); }
1445
1446   // Add a new argument.  V must define a phi-node.
1447   void addArgument(Variable *V) {
1448     V->setKind(Variable::VK_LetBB);
1449     Args.reserveCheck(1, Arena);
1450     Args.push_back(V);
1451   }
1452   // Add a new instruction.
1453   void addInstruction(Variable *V) {
1454     V->setKind(Variable::VK_LetBB);
1455     Instrs.reserveCheck(1, Arena);
1456     Instrs.push_back(V);
1457   }
1458   // Add a new predecessor, and return the phi-node index for it.
1459   // Will add an argument to all phi-nodes, initialized to nullptr.
1460   unsigned addPredecessor(BasicBlock *Pred);
1461
1462   // Reserve space for Nargs arguments.
1463   void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
1464
1465   // Reserve space for Nins instructions.
1466   void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1467
1468   // Reserve space for NumPreds predecessors, including space in phi nodes.
1469   void reservePredecessors(unsigned NumPreds);
1470
1471   // Return the index of BB, or Predecessors.size if BB is not a predecessor.
1472   unsigned findPredecessorIndex(const BasicBlock *BB) const {
1473     auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB);
1474     return std::distance(Predecessors.cbegin(), I);
1475   }
1476
1477   // Set id numbers for variables.
1478   void renumberVars();
1479
1480   template <class V>
1481   typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1482     typename V::template Container<Variable*> Nas(Vs, Args.size());
1483     typename V::template Container<Variable*> Nis(Vs, Instrs.size());
1484
1485     // Entering the basic block should do any scope initialization.
1486     Vs.enterBasicBlock(*this);
1487
1488     for (auto *A : Args) {
1489       auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx));
1490       Variable *Nvd = Vs.enterScope(*A, Ne);
1491       Nas.push_back(Nvd);
1492     }
1493     for (auto *I : Instrs) {
1494       auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx));
1495       Variable *Nvd = Vs.enterScope(*I, Ne);
1496       Nis.push_back(Nvd);
1497     }
1498     auto Nt = Vs.traverse(Terminator, Ctx);
1499
1500     // Exiting the basic block should handle any scope cleanup.
1501     Vs.exitBasicBlock(*this);
1502
1503     return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1504   }
1505
1506   template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) {
1507     // TODO: implement CFG comparisons
1508     return Cmp.comparePointers(this, E);
1509   }
1510
1511 private:
1512   friend class SCFG;
1513
1514   MemRegionRef Arena;
1515
1516   SCFG       *CFGPtr;       // The CFG that contains this block.
1517   unsigned   BlockID;       // unique id for this BB in the containing CFG
1518   BasicBlock *Parent;       // The parent block is the enclosing lexical scope.
1519                             // The parent dominates this block.
1520   BlockArray Predecessors;  // Predecessor blocks in the CFG.
1521   VarArray   Args;          // Phi nodes.  One argument per predecessor.
1522   VarArray   Instrs;        // Instructions.
1523   SExprRef   Terminator;    // Branch or Goto
1524 };
1525
1526
1527 // An SCFG is a control-flow graph.  It consists of a set of basic blocks, each
1528 // of which terminates in a branch to another basic block.  There is one
1529 // entry point, and one exit point.
1530 class SCFG : public SExpr {
1531 public:
1532   typedef SimpleArray<BasicBlock *> BlockArray;
1533   typedef BlockArray::iterator iterator;
1534   typedef BlockArray::const_iterator const_iterator;
1535
1536   static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1537
1538   SCFG(MemRegionRef A, unsigned Nblocks)
1539     : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks),
1540       Entry(nullptr), Exit(nullptr) {
1541     Entry = new (A) BasicBlock(A, nullptr);
1542     Exit  = new (A) BasicBlock(A, Entry);
1543     auto *V = new (A) Variable(new (A) Phi());
1544     Exit->addArgument(V);
1545     add(Entry);
1546     add(Exit);
1547   }
1548   SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1549       : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)),
1550         Entry(nullptr), Exit(nullptr) {
1551     // TODO: set entry and exit!
1552   }
1553
1554   iterator begin() { return Blocks.begin(); }
1555   iterator end() { return Blocks.end(); }
1556
1557   const_iterator begin() const { return cbegin(); }
1558   const_iterator end() const { return cend(); }
1559
1560   const_iterator cbegin() const { return Blocks.cbegin(); }
1561   const_iterator cend() const { return Blocks.cend(); }
1562
1563   const BasicBlock *entry() const { return Entry; }
1564   BasicBlock *entry() { return Entry; }
1565   const BasicBlock *exit() const { return Exit; }
1566   BasicBlock *exit() { return Exit; }
1567
1568   inline void add(BasicBlock *BB) {
1569     assert(BB->CFGPtr == nullptr || BB->CFGPtr == this);
1570     BB->setBlockID(Blocks.size());
1571     BB->CFGPtr = this;
1572     Blocks.reserveCheck(1, Arena);
1573     Blocks.push_back(BB);
1574   }
1575
1576   void setEntry(BasicBlock *BB) { Entry = BB; }
1577   void setExit(BasicBlock *BB)  { Exit = BB;  }
1578
1579   // Set varable ids in all blocks.
1580   void renumberVars();
1581
1582   template <class V>
1583   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1584     Vs.enterCFG(*this);
1585     typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1586     for (auto *B : Blocks) {
1587       Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1588     }
1589     Vs.exitCFG(*this);
1590     return Vs.reduceSCFG(*this, Bbs);
1591   }
1592
1593   template <class C> typename C::CType compare(SCFG *E, C &Cmp) {
1594     // TODO -- implement CFG comparisons
1595     return Cmp.comparePointers(this, E);
1596   }
1597
1598 private:
1599   MemRegionRef Arena;
1600   BlockArray   Blocks;
1601   BasicBlock   *Entry;
1602   BasicBlock   *Exit;
1603 };
1604
1605
1606 class Goto : public SExpr {
1607 public:
1608   static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1609
1610   Goto(BasicBlock *B, unsigned I)
1611       : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1612   Goto(const Goto &G, BasicBlock *B, unsigned I)
1613       : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1614
1615   const BasicBlock *targetBlock() const { return TargetBlock; }
1616   BasicBlock *targetBlock() { return TargetBlock; }
1617
1618   unsigned index() const { return Index; }
1619
1620   template <class V>
1621   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1622     BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1623     return Vs.reduceGoto(*this, Ntb);
1624   }
1625
1626   template <class C> typename C::CType compare(Goto *E, C &Cmp) {
1627     // TODO -- implement CFG comparisons
1628     return Cmp.comparePointers(this, E);
1629   }
1630
1631 private:
1632   BasicBlock *TargetBlock;
1633   unsigned Index;   // Index into Phi nodes of target block.
1634 };
1635
1636
1637 class Branch : public SExpr {
1638 public:
1639   static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1640
1641   Branch(SExpr *C, BasicBlock *T, BasicBlock *E, unsigned TI, unsigned EI)
1642       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1643         ThenIndex(TI), ElseIndex(EI)
1644   {}
1645   Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E,
1646          unsigned TI, unsigned EI)
1647       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1648         ThenIndex(TI), ElseIndex(EI)
1649   {}
1650
1651   const SExpr *condition() const { return Condition; }
1652   SExpr *condition() { return Condition; }
1653
1654   const BasicBlock *thenBlock() const { return ThenBlock; }
1655   BasicBlock *thenBlock() { return ThenBlock; }
1656
1657   const BasicBlock *elseBlock() const { return ElseBlock; }
1658   BasicBlock *elseBlock() { return ElseBlock; }
1659
1660   unsigned thenIndex() const { return ThenIndex; }
1661   unsigned elseIndex() const { return ElseIndex; }
1662
1663   template <class V>
1664   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1665     auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1666     BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock);
1667     BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock);
1668     return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1669   }
1670
1671   template <class C> typename C::CType compare(Branch *E, C &Cmp) {
1672     // TODO -- implement CFG comparisons
1673     return Cmp.comparePointers(this, E);
1674   }
1675
1676 private:
1677   SExpr *Condition;
1678   BasicBlock *ThenBlock;
1679   BasicBlock *ElseBlock;
1680   unsigned ThenIndex;
1681   unsigned ElseIndex;
1682 };
1683
1684
1685 // An identifier, e.g. 'foo' or 'x'.
1686 // This is a pseduo-term; it will be lowered to a variable or projection.
1687 class Identifier : public SExpr {
1688 public:
1689   static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1690
1691   Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
1692   Identifier(const Identifier& I) : SExpr(I), Name(I.Name)  { }
1693
1694   StringRef name() const { return Name; }
1695
1696   template <class V>
1697   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1698     return Vs.reduceIdentifier(*this);
1699   }
1700
1701   template <class C> typename C::CType compare(Identifier* E, C& Cmp) {
1702     return Cmp.compareStrings(name(), E->name());
1703   }
1704
1705 private:
1706   StringRef Name;
1707 };
1708
1709
1710 // An if-then-else expression.
1711 // This is a pseduo-term; it will be lowered to a branch in a CFG.
1712 class IfThenElse : public SExpr {
1713 public:
1714   static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1715
1716   IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1717     : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
1718   { }
1719   IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1720     : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
1721   { }
1722
1723   SExpr *condition() { return Condition.get(); }   // Address to store to
1724   const SExpr *condition() const { return Condition.get(); }
1725
1726   SExpr *thenExpr() { return ThenExpr.get(); }     // Value to store
1727   const SExpr *thenExpr() const { return ThenExpr.get(); }
1728
1729   SExpr *elseExpr() { return ElseExpr.get(); }     // Value to store
1730   const SExpr *elseExpr() const { return ElseExpr.get(); }
1731
1732   template <class V>
1733   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1734     auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1735     auto Nt = Vs.traverse(ThenExpr,  Vs.subExprCtx(Ctx));
1736     auto Ne = Vs.traverse(ElseExpr,  Vs.subExprCtx(Ctx));
1737     return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1738   }
1739
1740   template <class C> typename C::CType compare(IfThenElse* E, C& Cmp) {
1741     typename C::CType Ct = Cmp.compare(condition(), E->condition());
1742     if (Cmp.notTrue(Ct))
1743       return Ct;
1744     Ct = Cmp.compare(thenExpr(), E->thenExpr());
1745     if (Cmp.notTrue(Ct))
1746       return Ct;
1747     return Cmp.compare(elseExpr(), E->elseExpr());
1748   }
1749
1750 private:
1751   SExprRef Condition;
1752   SExprRef ThenExpr;
1753   SExprRef ElseExpr;
1754 };
1755
1756
1757 // A let-expression,  e.g.  let x=t; u.
1758 // This is a pseduo-term; it will be lowered to instructions in a CFG.
1759 class Let : public SExpr {
1760 public:
1761   static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1762
1763   Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1764     Vd->setKind(Variable::VK_Let);
1765   }
1766   Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1767     Vd->setKind(Variable::VK_Let);
1768   }
1769
1770   Variable *variableDecl()  { return VarDecl; }
1771   const Variable *variableDecl() const { return VarDecl; }
1772
1773   SExpr *body() { return Body.get(); }
1774   const SExpr *body() const { return Body.get(); }
1775
1776   template <class V>
1777   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1778     // This is a variable declaration, so traverse the definition.
1779     auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1780     // Tell the rewriter to enter the scope of the let variable.
1781     Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1782     auto E1 = Vs.traverse(Body, Ctx);
1783     Vs.exitScope(*VarDecl);
1784     return Vs.reduceLet(*this, Nvd, E1);
1785   }
1786
1787   template <class C> typename C::CType compare(Let* E, C& Cmp) {
1788     typename C::CType Ct =
1789       Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1790     if (Cmp.notTrue(Ct))
1791       return Ct;
1792     Cmp.enterScope(variableDecl(), E->variableDecl());
1793     Ct = Cmp.compare(body(), E->body());
1794     Cmp.leaveScope();
1795     return Ct;
1796   }
1797
1798 private:
1799   Variable *VarDecl;
1800   SExprRef Body;
1801 };
1802
1803
1804
1805 SExpr *getCanonicalVal(SExpr *E);
1806 void simplifyIncompleteArg(Variable *V, til::Phi *Ph);
1807
1808
1809 } // end namespace til
1810 } // end namespace threadSafety
1811 } // end namespace clang
1812
1813 #endif // LLVM_CLANG_THREAD_SAFETY_TIL_H