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