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