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 for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a simple intermediate language that is used by the
  11 // thread safety analysis (See ThreadSafety.cpp).  The thread safety analysis
  12 // works by comparing mutex expressions, e.g.
  13 //
  14 // class A { Mutex mu; int dat GUARDED_BY(this->mu); }
  15 // class B { A a; }
  16 //
  17 // void foo(B* b) {
  18 //   (*b).a.mu.lock();     // locks (*b).a.mu
  19 //   b->a.dat = 0;         // substitute &b->a for 'this';
  20 //                         // requires lock on (&b->a)->mu
  21 //   (b->a.mu).unlock();   // unlocks (b->a.mu)
  22 // }
  23 //
  24 // As illustrated by the above example, clang Exprs are not well-suited to
  25 // represent mutex expressions directly, since there is no easy way to compare
  26 // Exprs for equivalence.  The thread safety analysis thus lowers clang Exprs
  27 // into a simple intermediate language (IL).  The IL supports:
  28 //
  29 // (1) comparisons for semantic equality of expressions
  30 // (2) SSA renaming of variables
  31 // (3) wildcards and pattern matching over expressions
  32 // (4) hash-based expression lookup
  33 //
  34 // The IL is currently very experimental, is intended only for use within
  35 // the thread safety analysis, and is subject to change without notice.
  36 // After the API stabilizes and matures, it may be appropriate to make this
  37 // more generally available to other analyses.
  38 //
  39 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
  40 //
  41 //===----------------------------------------------------------------------===//
  42
  43 #ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H
  44 #define LLVM_CLANG_THREAD_SAFETY_TIL_H
  45
  46 #include "clang/AST/DeclCXX.h"
  47 #include "clang/AST/ExprCXX.h"
  48 #include "clang/AST/StmtCXX.h"
  49 #include "clang/AST/Type.h"
  50 #include "llvm/ADT/StringRef.h"
  51 #include "llvm/Support/AlignOf.h"
  52 #include "llvm/Support/Allocator.h"
  53
  54 #include <cassert>
  55 #include <cstddef>
  56 #include <utility>
  57
  58 namespace clang {
  59 namespace threadSafety {
  60 namespace til {
  61
  62
  63 // Simple wrapper class to abstract away from the details of memory management.
  64 // SExprs are allocated in pools, and deallocated all at once.
  65 class MemRegionRef {
  66 private:
  67   union AlignmentType {
  68     double d;
  69     void *p;
  70     long double dd;
  71     long long ii;
  72   };
  73
  74 public:
  75   MemRegionRef() : Allocator(nullptr) {}
  76   MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
  77
  78   void *allocate(size_t Sz) {
  79     return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment);
  80   }
  81
  82   template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
  83
  84   template <typename T> T *allocateT(size_t NumElems) {
  85     return Allocator->Allocate<T>(NumElems);
  86   }
  87
  88 private:
  89   llvm::BumpPtrAllocator *Allocator;
  90 };
  91
  92
  93 } // end namespace til
  94 } // end namespace threadSafety
  95 } // end namespace clang
  96
  97
  98 inline void *operator new(size_t Sz,
  99                           clang::threadSafety::til::MemRegionRef &R) {
 100   return R.allocate(Sz);
 101 }
 102
 103
 104 namespace clang {
 105 namespace threadSafety {
 106 namespace til {
 107
 108 using llvm::StringRef;
 109
 110 // A simple fixed size array class that does not manage its own memory,
 111 // suitable for use with bump pointer allocation.
 112 template <class T> class SimpleArray {
 113 public:
 114   SimpleArray() : Data(nullptr), Size(0), Capacity(0) {}
 115   SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
 116       : Data(Dat), Size(0), Capacity(Cp) {}
 117   SimpleArray(MemRegionRef A, size_t Cp)
 118       : Data(A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {}
 119   SimpleArray(SimpleArray<T> &&A)
 120       : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
 121     A.Data = nullptr;
 122     A.Size = 0;
 123     A.Capacity = 0;
 124   }
 125
 126   T *resize(size_t Ncp, MemRegionRef A) {
 127     T *Odata = Data;
 128     Data = A.allocateT<T>(Ncp);
 129     memcpy(Data, Odata, sizeof(T) * Size);
 130     return Odata;
 131   }
 132
 133   typedef T *iterator;
 134   typedef const T *const_iterator;
 135
 136   size_t size() const { return Size; }
 137   size_t capacity() const { return Capacity; }
 138
 139   T &operator[](unsigned I) { return Data[I]; }
 140   const T &operator[](unsigned I) const { return Data[I]; }
 141
 142   iterator begin() { return Data; }
 143   iterator end() { return Data + Size; }
 144
 145   const_iterator cbegin() const { return Data; }
 146   const_iterator cend() const { return Data + Size; }
 147
 148   void push_back(const T &Elem) {
 149     assert(Size < Capacity);
 150     Data[Size++] = Elem;
 151   }
 152
 153   template <class Iter> unsigned append(Iter I, Iter E) {
 154     size_t Osz = Size;
 155     size_t J = Osz;
 156     for (; J < Capacity && I != E; ++J, ++I)
 157       Data[J] = *I;
 158     Size = J;
 159     return J - Osz;
 160   }
 161
 162 private:
 163   SimpleArray(const SimpleArray<T> &A) { }
 164
 165   T *Data;
 166   size_t Size;
 167   size_t Capacity;
 168 };
 169
 170
 171 enum TIL_Opcode {
 172 #define TIL_OPCODE_DEF(X) COP_##X,
 173 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
 174 #undef TIL_OPCODE_DEF
 175   COP_MAX
 176 };
 177
 178
 179 typedef clang::BinaryOperatorKind TIL_BinaryOpcode;
 180 typedef clang::UnaryOperatorKind TIL_UnaryOpcode;
 181 typedef clang::CastKind TIL_CastOpcode;
 182
 183
 184 enum TraversalKind {
 185   TRV_Normal,
 186   TRV_Lazy, // subexpression may need to be traversed lazily
 187   TRV_Tail  // subexpression occurs in a tail position
 188 };
 189
 190
 191 // Base class for AST nodes in the typed intermediate language.
 192 class SExpr {
 193 public:
 194   TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
 195
 196   // Subclasses of SExpr must define the following:
 197   //
 198   // This(const This& E, ...) {
 199   //   copy constructor: construct copy of E, with some additional arguments.
 200   // }
 201   //
 202   // template <class V> typename V::R_SExpr traverse(V &Visitor) {
 203   //   traverse all subexpressions, following the traversal/rewriter interface
 204   // }
 205   //
 206   // template <class C> typename C::CType compare(CType* E, C& Cmp) {
 207   //   compare all subexpressions, following the comparator interface
 208   // }
 209
 210   void *operator new(size_t S, clang::threadSafety::til::MemRegionRef &R) {
 211     return ::operator new(S, R);
 212   }
 213
 214 protected:
 215   SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {}
 216   SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {}
 217
 218   const unsigned char Opcode;
 219   unsigned char Reserved;
 220   unsigned short Flags;
 221
 222 private:
 223   SExpr() = delete;
 224
 225   // SExpr objects must be created in an arena and cannot be deleted.
 226   void *operator new(size_t) = delete;
 227   void operator delete(void *) = delete;
 228 };
 229
 230
 231 // Class for owning references to SExprs.
 232 // Includes attach/detach logic for counting variable references and lazy
 233 // rewriting strategies.
 234 class SExprRef {
 235 public:
 236   SExprRef() : Ptr(nullptr) { }
 237   SExprRef(std::nullptr_t P) : Ptr(nullptr) { }
 238   SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; }
 239
 240   // Defined after Variable and Future, below.
 241   inline SExprRef(SExpr *P);
 242   inline ~SExprRef();
 243
 244   SExpr       *get()       { return Ptr; }
 245   const SExpr *get() const { return Ptr; }
 246
 247   SExpr       *operator->()       { return get(); }
 248   const SExpr *operator->() const { return get(); }
 249
 250   SExpr       &operator*()        { return *Ptr; }
 251   const SExpr &operator*() const  { return *Ptr; }
 252
 253   bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; }
 254   bool operator!=(const SExprRef &R) const { return !operator==(R); }
 255   bool operator==(const SExpr *P) const { return Ptr == P; }
 256   bool operator!=(const SExpr *P) const { return !operator==(P); }
 257   bool operator==(std::nullptr_t) const { return Ptr == nullptr; }
 258   bool operator!=(std::nullptr_t) const { return Ptr != nullptr; }
 259
 260   inline void reset(SExpr *E);
 261
 262 private:
 263   inline void attach();
 264   inline void detach();
 265
 266   SExpr *Ptr;
 267 };
 268
 269
 270 // Contains various helper functions for SExprs.
 271 namespace ThreadSafetyTIL {
 272 static bool isTrivial(SExpr *E) {
 273   unsigned Op = E->opcode();
 274   return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
 275 }
 276 }
 277
 278 class Function;
 279 class SFunction;
 280 class BasicBlock;
 281
 282
 283 // A named variable, e.g. "x".
 284 //
 285 // There are two distinct places in which a Variable can appear in the AST.
 286 // A variable declaration introduces a new variable, and can occur in 3 places:
 287 //   Let-expressions:           (Let (x = t) u)
 288 //   Functions:                 (Function (x : t) u)
 289 //   Self-applicable functions  (SFunction (x) t)
 290 //
 291 // If a variable occurs in any other location, it is a reference to an existing
 292 // variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
 293 // allocate a separate AST node for variable references; a reference is just a
 294 // pointer to the original declaration.
 295 class Variable : public SExpr {
 296 public:
 297   static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
 298
 299   // Let-variable, function parameter, or self-variable
 300   enum VariableKind {
 301     VK_Let,
 302     VK_Fun,
 303     VK_SFun
 304   };
 305
 306   // These are defined after SExprRef contructor, below
 307   inline Variable(VariableKind K, SExpr *D = nullptr,
 308                   const clang::ValueDecl *Cvd = nullptr);
 309   inline Variable(const clang::ValueDecl *Cvd, SExpr *D = nullptr);
 310   inline Variable(const Variable &Vd, SExpr *D);
 311
 312   VariableKind kind() const { return static_cast<VariableKind>(Flags); }
 313
 314   const StringRef name() const { return Cvdecl ? Cvdecl->getName() : "_x"; }
 315   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
 316
 317   // Returns the definition (for let vars) or type (for parameter & self vars)
 318   SExpr *definition() { return Definition.get(); }
 319
 320   void attachVar() const { ++NumUses; }
 321   void detachVar() const { assert(NumUses > 0); --NumUses; }
 322
 323   unsigned getID() const { return Id; }
 324   unsigned getBlockID() const { return BlockID; }
 325
 326   void setID(unsigned Bid, unsigned I) {
 327     BlockID = static_cast<unsigned short>(Bid);
 328     Id = static_cast<unsigned short>(I);
 329   }
 330
 331   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 332     // This routine is only called for variable references.
 333     return Visitor.reduceVariableRef(this);
 334   }
 335
 336   template <class C> typename C::CType compare(Variable* E, C& Cmp) {
 337     return Cmp.compareVariableRefs(this, E);
 338   }
 339
 340 private:
 341   friend class Function;
 342   friend class SFunction;
 343   friend class BasicBlock;
 344
 345   // Function, SFunction, and BasicBlock will reset the kind.
 346   void setKind(VariableKind K) { Flags = K; }
 347
 348   SExprRef Definition;             // The TIL type or definition
 349   const clang::ValueDecl *Cvdecl;  // The clang declaration for this variable.
 350
 351   unsigned short BlockID;
 352   unsigned short Id;
 353   mutable unsigned NumUses;
 354 };
 355
 356
 357 // Placeholder for an expression that has not yet been created.
 358 // Used to implement lazy copy and rewriting strategies.
 359 class Future : public SExpr {
 360 public:
 361   static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
 362
 363   enum FutureStatus {
 364     FS_pending,
 365     FS_evaluating,
 366     FS_done
 367   };
 368
 369   Future() :
 370     SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr)
 371   {}
 372   virtual ~Future() = delete;
 373
 374   // Registers the location in the AST where this future is stored.
 375   // Forcing the future will automatically update the AST.
 376   static inline void registerLocation(SExprRef *Member) {
 377     if (Future *F = dyn_cast_or_null<Future>(Member->get()))
 378       F->Location = Member;
 379   }
 380
 381   // A lazy rewriting strategy should subclass Future and override this method.
 382   virtual SExpr *create() { return nullptr; }
 383
 384   // Return the result of this future if it exists, otherwise return null.
 385   SExpr *maybeGetResult() {
 386     return Result;
 387   }
 388
 389   // Return the result of this future; forcing it if necessary.
 390   SExpr *result() {
 391     switch (Status) {
 392     case FS_pending:
 393       force();
 394       return Result;
 395     case FS_evaluating:
 396       return nullptr; // infinite loop; illegal recursion.
 397     case FS_done:
 398       return Result;
 399     }
 400   }
 401
 402   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 403     assert(Result && "Cannot traverse Future that has not been forced.");
 404     return Visitor.traverse(Result);
 405   }
 406
 407   template <class C> typename C::CType compare(Future* E, C& Cmp) {
 408     if (!Result || !E->Result)
 409       return Cmp.comparePointers(this, E);
 410     return Cmp.compare(Result, E->Result);
 411   }
 412
 413 private:
 414   // Force the future.
 415   inline void force();
 416
 417   FutureStatus Status;
 418   SExpr *Result;
 419   SExprRef *Location;
 420 };
 421
 422
 423
 424 void SExprRef::attach() {
 425   if (!Ptr)
 426     return;
 427
 428   TIL_Opcode Op = Ptr->opcode();
 429   if (Op == COP_Variable) {
 430     cast<Variable>(Ptr)->attachVar();
 431   }
 432   else if (Op == COP_Future) {
 433     cast<Future>(Ptr)->registerLocation(this);
 434   }
 435 }
 436
 437 void SExprRef::detach() {
 438   if (Ptr && Ptr->opcode() == COP_Variable) {
 439     cast<Variable>(Ptr)->detachVar();
 440   }
 441 }
 442
 443 SExprRef::SExprRef(SExpr *P) : Ptr(P) {
 444   if (P)
 445     attach();
 446 }
 447
 448 SExprRef::~SExprRef() {
 449   detach();
 450 }
 451
 452 void SExprRef::reset(SExpr *P) {
 453   if (Ptr)
 454     detach();
 455   Ptr = P;
 456   if (P)
 457     attach();
 458 }
 459
 460
 461 Variable::Variable(VariableKind K, SExpr *D, const clang::ValueDecl *Cvd)
 462     : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd),
 463       BlockID(0), Id(0),  NumUses(0) {
 464   Flags = K;
 465 }
 466
 467 Variable::Variable(const clang::ValueDecl *Cvd, SExpr *D)
 468     : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd),
 469       BlockID(0), Id(0),  NumUses(0) {
 470   Flags = VK_Let;
 471 }
 472
 473 Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor
 474     : SExpr(Vd), Definition(D), Cvdecl(Vd.Cvdecl),
 475       BlockID(0), Id(0), NumUses(0) {
 476   Flags = Vd.kind();
 477 }
 478
 479
 480 void Future::force() {
 481   Status = FS_evaluating;
 482   SExpr *R = create();
 483   Result = R;
 484   if (Location) {
 485     Location->reset(R);
 486   }
 487   Status = FS_done;
 488 }
 489
 490
 491
 492 // Placeholder for C++ expressions that cannot be represented in the TIL.
 493 class Undefined : public SExpr {
 494 public:
 495   static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
 496
 497   Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
 498   Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
 499
 500   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 501     return Visitor.reduceUndefined(*this);
 502   }
 503
 504   template <class C> typename C::CType compare(Undefined* E, C& Cmp) {
 505     return Cmp.comparePointers(Cstmt, E->Cstmt);
 506   }
 507
 508 private:
 509   const clang::Stmt *Cstmt;
 510 };
 511
 512
 513 // Placeholder for a wildcard that matches any other expression.
 514 class Wildcard : public SExpr {
 515 public:
 516   static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
 517
 518   Wildcard() : SExpr(COP_Wildcard) {}
 519   Wildcard(const Wildcard &W) : SExpr(W) {}
 520
 521   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 522     return Visitor.reduceWildcard(*this);
 523   }
 524
 525   template <class C> typename C::CType compare(Wildcard* E, C& Cmp) {
 526     return Cmp.trueResult();
 527   }
 528 };
 529
 530
 531 // Base class for literal values.
 532 class Literal : public SExpr {
 533 public:
 534   static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
 535
 536   Literal(const clang::Expr *C) : SExpr(COP_Literal), Cexpr(C) {}
 537   Literal(const Literal &L) : SExpr(L), Cexpr(L.Cexpr) {}
 538
 539   // The clang expression for this literal.
 540   const clang::Expr *clangExpr() { return Cexpr; }
 541
 542   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 543     return Visitor.reduceLiteral(*this);
 544   }
 545
 546   template <class C> typename C::CType compare(Literal* E, C& Cmp) {
 547     // TODO -- use value, not pointer equality
 548     return Cmp.comparePointers(Cexpr, E->Cexpr);
 549   }
 550
 551 private:
 552   const clang::Expr *Cexpr;
 553 };
 554
 555
 556 // Literal pointer to an object allocated in memory.
 557 // At compile time, pointer literals are represented by symbolic names.
 558 class LiteralPtr : public SExpr {
 559 public:
 560   static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
 561
 562   LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
 563   LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
 564
 565   // The clang declaration for the value that this pointer points to.
 566   const clang::ValueDecl *clangDecl() { return Cvdecl; }
 567
 568   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 569     return Visitor.reduceLiteralPtr(*this);
 570   }
 571
 572   template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) {
 573     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
 574   }
 575
 576 private:
 577   const clang::ValueDecl *Cvdecl;
 578 };
 579
 580
 581
 582
 583
 584 // A function -- a.k.a. lambda abstraction.
 585 // Functions with multiple arguments are created by currying,
 586 // e.g. (function (x: Int) (function (y: Int) (add x y)))
 587 class Function : public SExpr {
 588 public:
 589   static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
 590
 591   Function(Variable *Vd, SExpr *Bd)
 592       : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
 593     Vd->setKind(Variable::VK_Fun);
 594   }
 595   Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
 596       : SExpr(F), VarDecl(Vd), Body(Bd) {
 597     Vd->setKind(Variable::VK_Fun);
 598   }
 599
 600   Variable *variableDecl()  { return VarDecl; }
 601   const Variable *variableDecl() const { return VarDecl; }
 602
 603   SExpr *body() { return Body.get(); }
 604   const SExpr *body() const { return Body.get(); }
 605
 606   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 607     // This is a variable declaration, so traverse the definition.
 608     typename V::R_SExpr E0 = Visitor.traverse(VarDecl->Definition, TRV_Lazy);
 609     // Tell the rewriter to enter the scope of the function.
 610     Variable *Nvd = Visitor.enterScope(*VarDecl, E0);
 611     typename V::R_SExpr E1 = Visitor.traverse(Body);
 612     Visitor.exitScope(*VarDecl);
 613     return Visitor.reduceFunction(*this, Nvd, E1);
 614   }
 615
 616   template <class C> typename C::CType compare(Function* E, C& Cmp) {
 617     typename C::CType Ct =
 618       Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
 619     if (Cmp.notTrue(Ct))
 620       return Ct;
 621     Cmp.enterScope(variableDecl(), E->variableDecl());
 622     Ct = Cmp.compare(body(), E->body());
 623     Cmp.leaveScope();
 624     return Ct;
 625   }
 626
 627 private:
 628   Variable *VarDecl;
 629   SExprRef Body;
 630 };
 631
 632
 633 // A self-applicable function.
 634 // A self-applicable function can be applied to itself.  It's useful for
 635 // implementing objects and late binding
 636 class SFunction : public SExpr {
 637 public:
 638   static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
 639
 640   SFunction(Variable *Vd, SExpr *B)
 641       : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
 642     assert(Vd->Definition == nullptr);
 643     Vd->setKind(Variable::VK_SFun);
 644     Vd->Definition.reset(this);
 645   }
 646   SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
 647       : SExpr(F),
 648         VarDecl(Vd),
 649         Body(B) {
 650     assert(Vd->Definition == nullptr);
 651     Vd->setKind(Variable::VK_SFun);
 652     Vd->Definition.reset(this);
 653   }
 654
 655   Variable *variableDecl() { return VarDecl; }
 656   const Variable *variableDecl() const { return VarDecl; }
 657
 658   SExpr *body() { return Body.get(); }
 659   const SExpr *body() const { return Body.get(); }
 660
 661   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 662     // A self-variable points to the SFunction itself.
 663     // A rewrite must introduce the variable with a null definition, and update
 664     // it after 'this' has been rewritten.
 665     Variable *Nvd = Visitor.enterScope(*VarDecl, nullptr /* def */);
 666     typename V::R_SExpr E1 = Visitor.traverse(Body);
 667     Visitor.exitScope(*VarDecl);
 668     // A rewrite operation will call SFun constructor to set Vvd->Definition.
 669     return Visitor.reduceSFunction(*this, Nvd, E1);
 670   }
 671
 672   template <class C> typename C::CType compare(SFunction* E, C& Cmp) {
 673     Cmp.enterScope(variableDecl(), E->variableDecl());
 674     typename C::CType Ct = Cmp.compare(body(), E->body());
 675     Cmp.leaveScope();
 676     return Ct;
 677   }
 678
 679 private:
 680   Variable *VarDecl;
 681   SExprRef Body;
 682 };
 683
 684
 685 // A block of code -- e.g. the body of a function.
 686 class Code : public SExpr {
 687 public:
 688   static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
 689
 690   Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
 691   Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
 692       : SExpr(C), ReturnType(T), Body(B) {}
 693
 694   SExpr *returnType() { return ReturnType.get(); }
 695   const SExpr *returnType() const { return ReturnType.get(); }
 696
 697   SExpr *body() { return Body.get(); }
 698   const SExpr *body() const { return Body.get(); }
 699
 700   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 701     typename V::R_SExpr Nt = Visitor.traverse(ReturnType, TRV_Lazy);
 702     typename V::R_SExpr Nb = Visitor.traverse(Body, TRV_Lazy);
 703     return Visitor.reduceCode(*this, Nt, Nb);
 704   }
 705
 706   template <class C> typename C::CType compare(Code* E, C& Cmp) {
 707     typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
 708     if (Cmp.notTrue(Ct))
 709       return Ct;
 710     return Cmp.compare(body(), E->body());
 711   }
 712
 713 private:
 714   SExprRef ReturnType;
 715   SExprRef Body;
 716 };
 717
 718
 719 // Apply an argument to a function
 720 class Apply : public SExpr {
 721 public:
 722   static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
 723
 724   Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
 725   Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
 726       : SExpr(A), Fun(F), Arg(Ar)
 727   {}
 728
 729   SExpr *fun() { return Fun.get(); }
 730   const SExpr *fun() const { return Fun.get(); }
 731
 732   SExpr *arg() { return Arg.get(); }
 733   const SExpr *arg() const { return Arg.get(); }
 734
 735   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 736     typename V::R_SExpr Nf = Visitor.traverse(Fun);
 737     typename V::R_SExpr Na = Visitor.traverse(Arg);
 738     return Visitor.reduceApply(*this, Nf, Na);
 739   }
 740
 741   template <class C> typename C::CType compare(Apply* E, C& Cmp) {
 742     typename C::CType Ct = Cmp.compare(fun(), E->fun());
 743     if (Cmp.notTrue(Ct))
 744       return Ct;
 745     return Cmp.compare(arg(), E->arg());
 746   }
 747
 748 private:
 749   SExprRef Fun;
 750   SExprRef Arg;
 751 };
 752
 753
 754 // Apply a self-argument to a self-applicable function
 755 class SApply : public SExpr {
 756 public:
 757   static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
 758
 759   SApply(SExpr *Sf, SExpr *A = nullptr)
 760       : SExpr(COP_SApply), Sfun(Sf), Arg(A)
 761   {}
 762   SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr)  // rewrite constructor
 763       : SExpr(A),  Sfun(Sf), Arg(Ar)
 764   {}
 765
 766   SExpr *sfun() { return Sfun.get(); }
 767   const SExpr *sfun() const { return Sfun.get(); }
 768
 769   SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); }
 770   const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); }
 771
 772   bool isDelegation() const { return Arg == nullptr; }
 773
 774   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 775     typename V::R_SExpr Nf = Visitor.traverse(Sfun);
 776     typename V::R_SExpr Na = Arg.get() ? Visitor.traverse(Arg) : nullptr;
 777     return Visitor.reduceSApply(*this, Nf, Na);
 778   }
 779
 780   template <class C> typename C::CType compare(SApply* E, C& Cmp) {
 781     typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
 782     if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
 783       return Ct;
 784     return Cmp.compare(arg(), E->arg());
 785   }
 786
 787 private:
 788   SExprRef Sfun;
 789   SExprRef Arg;
 790 };
 791
 792
 793 // Project a named slot from a C++ struct or class.
 794 class Project : public SExpr {
 795 public:
 796   static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
 797
 798   Project(SExpr *R, clang::ValueDecl *Cvd)
 799       : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {}
 800   Project(const Project &P, SExpr *R) : SExpr(P), Rec(R), Cvdecl(P.Cvdecl) {}
 801
 802   SExpr *record() { return Rec.get(); }
 803   const SExpr *record() const { return Rec.get(); }
 804
 805   const clang::ValueDecl *clangValueDecl() const { return Cvdecl; }
 806
 807   StringRef slotName() const { return Cvdecl->getName(); }
 808
 809   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 810     typename V::R_SExpr Nr = Visitor.traverse(Rec);
 811     return Visitor.reduceProject(*this, Nr);
 812   }
 813
 814   template <class C> typename C::CType compare(Project* E, C& Cmp) {
 815     typename C::CType Ct = Cmp.compare(record(), E->record());
 816     if (Cmp.notTrue(Ct))
 817       return Ct;
 818     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
 819   }
 820
 821 private:
 822   SExprRef Rec;
 823   clang::ValueDecl *Cvdecl;
 824 };
 825
 826
 827 // Call a function (after all arguments have been applied).
 828 class Call : public SExpr {
 829 public:
 830   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
 831
 832   Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
 833       : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
 834   Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
 835
 836   SExpr *target() { return Target.get(); }
 837   const SExpr *target() const { return Target.get(); }
 838
 839   const clang::CallExpr *clangCallExpr() { return Cexpr; }
 840
 841   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 842     typename V::R_SExpr Nt = Visitor.traverse(Target);
 843     return Visitor.reduceCall(*this, Nt);
 844   }
 845
 846   template <class C> typename C::CType compare(Call* E, C& Cmp) {
 847     return Cmp.compare(target(), E->target());
 848   }
 849
 850 private:
 851   SExprRef Target;
 852   const clang::CallExpr *Cexpr;
 853 };
 854
 855
 856 // Allocate memory for a new value on the heap or stack.
 857 class Alloc : public SExpr {
 858 public:
 859   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
 860
 861   enum AllocKind {
 862     AK_Stack,
 863     AK_Heap
 864   };
 865
 866   Alloc(SExpr* D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) {
 867     Flags = K;
 868   }
 869   Alloc(const Alloc &A, SExpr* Dt) : SExpr(A), Dtype(Dt) {
 870     Flags = A.kind();
 871   }
 872
 873   AllocKind kind() const { return static_cast<AllocKind>(Flags); }
 874
 875   SExpr* dataType() { return Dtype.get(); }
 876   const SExpr* dataType() const { return Dtype.get(); }
 877
 878   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 879     typename V::R_SExpr Nd = Visitor.traverse(Dtype);
 880     return Visitor.reduceAlloc(*this, Nd);
 881   }
 882
 883   template <class C> typename C::CType compare(Alloc* E, C& Cmp) {
 884     typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
 885     if (Cmp.notTrue(Ct))
 886       return Ct;
 887     return Cmp.compare(dataType(), E->dataType());
 888   }
 889
 890 private:
 891   SExprRef Dtype;
 892 };
 893
 894
 895 // Load a value from memory.
 896 class Load : public SExpr {
 897 public:
 898   static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
 899
 900   Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
 901   Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
 902
 903   SExpr *pointer() { return Ptr.get(); }
 904   const SExpr *pointer() const { return Ptr.get(); }
 905
 906   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 907     typename V::R_SExpr Np = Visitor.traverse(Ptr);
 908     return Visitor.reduceLoad(*this, Np);
 909   }
 910
 911   template <class C> typename C::CType compare(Load* E, C& Cmp) {
 912     return Cmp.compare(pointer(), E->pointer());
 913   }
 914
 915 private:
 916   SExprRef Ptr;
 917 };
 918
 919
 920 // Store a value to memory.
 921 class Store : public SExpr {
 922 public:
 923   static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
 924
 925   Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
 926   Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
 927
 928   SExpr *destination() { return Dest.get(); }  // Address to store to
 929   const SExpr *destination() const { return Dest.get(); }
 930
 931   SExpr *source() { return Source.get(); }     // Value to store
 932   const SExpr *source() const { return Source.get(); }
 933
 934   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 935     typename V::R_SExpr Np = Visitor.traverse(Dest);
 936     typename V::R_SExpr Nv = Visitor.traverse(Source);
 937     return Visitor.reduceStore(*this, Np, Nv);
 938   }
 939
 940   template <class C> typename C::CType compare(Store* E, C& Cmp) {
 941     typename C::CType Ct = Cmp.compare(destination(), E->destination());
 942     if (Cmp.notTrue(Ct))
 943       return Ct;
 944     return Cmp.compare(source(), E->source());
 945   }
 946
 947   SExprRef Dest;
 948   SExprRef Source;
 949 };
 950
 951
 952 // Simple unary operation -- e.g. !, ~, etc.
 953 class UnaryOp : public SExpr {
 954 public:
 955   static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
 956
 957   UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
 958     Flags = Op;
 959   }
 960   UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U) { Flags = U.Flags; }
 961
 962   TIL_UnaryOpcode unaryOpcode() { return static_cast<TIL_UnaryOpcode>(Flags); }
 963
 964   SExpr *expr() { return Expr0.get(); }
 965   const SExpr *expr() const { return Expr0.get(); }
 966
 967   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 968     typename V::R_SExpr Ne = Visitor.traverse(Expr0);
 969     return Visitor.reduceUnaryOp(*this, Ne);
 970   }
 971
 972   template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) {
 973     typename C::CType Ct =
 974       Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
 975     if (Cmp.notTrue(Ct))
 976       return Ct;
 977     return Cmp.compare(expr(), E->expr());
 978   }
 979
 980 private:
 981   SExprRef Expr0;
 982 };
 983
 984
 985 // Simple binary operation -- e.g. +, -, etc.
 986 class BinaryOp : public SExpr {
 987 public:
 988   static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
 989
 990   BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
 991       : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
 992     Flags = Op;
 993   }
 994   BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
 995       : SExpr(B), Expr0(E0), Expr1(E1) {
 996     Flags = B.Flags;
 997   }
 998
 999   TIL_BinaryOpcode binaryOpcode() {
1000     return static_cast<TIL_BinaryOpcode>(Flags);
1001   }
1002
1003   SExpr *expr0() { return Expr0.get(); }
1004   const SExpr *expr0() const { return Expr0.get(); }
1005
1006   SExpr *expr1() { return Expr1.get(); }
1007   const SExpr *expr1() const { return Expr1.get(); }
1008
1009   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1010     typename V::R_SExpr Ne0 = Visitor.traverse(Expr0);
1011     typename V::R_SExpr Ne1 = Visitor.traverse(Expr1);
1012     return Visitor.reduceBinaryOp(*this, Ne0, Ne1);
1013   }
1014
1015   template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) {
1016     typename C::CType Ct =
1017       Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1018     if (Cmp.notTrue(Ct))
1019       return Ct;
1020     Ct = Cmp.compare(expr0(), E->expr0());
1021     if (Cmp.notTrue(Ct))
1022       return Ct;
1023     return Cmp.compare(expr1(), E->expr1());
1024   }
1025
1026 private:
1027   SExprRef Expr0;
1028   SExprRef Expr1;
1029 };
1030
1031
1032 // Cast expression
1033 class Cast : public SExpr {
1034 public:
1035   static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1036
1037   Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1038   Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1039
1040   TIL_BinaryOpcode castOpcode() {
1041     return static_cast<TIL_BinaryOpcode>(Flags);
1042   }
1043
1044   SExpr *expr() { return Expr0.get(); }
1045   const SExpr *expr() const { return Expr0.get(); }
1046
1047   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1048     typename V::R_SExpr Ne = Visitor.traverse(Expr0);
1049     return Visitor.reduceCast(*this, Ne);
1050   }
1051
1052   template <class C> typename C::CType compare(Cast* E, C& Cmp) {
1053     typename C::CType Ct =
1054       Cmp.compareIntegers(castOpcode(), E->castOpcode());
1055     if (Cmp.notTrue(Ct))
1056       return Ct;
1057     return Cmp.compare(expr(), E->expr());
1058   }
1059
1060 private:
1061   SExprRef Expr0;
1062 };
1063
1064
1065
1066
1067 class BasicBlock;
1068
1069
1070 // An SCFG is a control-flow graph.  It consists of a set of basic blocks, each
1071 // of which terminates in a branch to another basic block.  There is one
1072 // entry point, and one exit point.
1073 class SCFG : public SExpr {
1074 public:
1075   typedef SimpleArray<BasicBlock*> BlockArray;
1076
1077   static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1078
1079   SCFG(MemRegionRef A, unsigned Nblocks)
1080       : SExpr(COP_SCFG), Blocks(A, Nblocks), Entry(nullptr), Exit(nullptr) {}
1081   SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1082       : SExpr(COP_SCFG),
1083         Blocks(std::move(Ba)),
1084         Entry(nullptr),
1085         Exit(nullptr) {
1086     // TODO: set entry and exit!
1087   }
1088
1089   typedef BlockArray::iterator iterator;
1090   typedef BlockArray::const_iterator const_iterator;
1091
1092   iterator begin() { return Blocks.begin(); }
1093   iterator end() { return Blocks.end(); }
1094
1095   const_iterator cbegin() const { return Blocks.cbegin(); }
1096   const_iterator cend() const { return Blocks.cend(); }
1097
1098   BasicBlock *entry() const { return Entry; }
1099   BasicBlock *exit() const { return Exit; }
1100
1101   void add(BasicBlock *BB) { Blocks.push_back(BB); }
1102   void setEntry(BasicBlock *BB) { Entry = BB; }
1103   void setExit(BasicBlock *BB) { Exit = BB; }
1104
1105   template <class V> typename V::R_SExpr traverse(V &Visitor);
1106
1107   template <class C> typename C::CType compare(SCFG* E, C& Cmp) {
1108     // TODO -- implement CFG comparisons
1109     return Cmp.comparePointers(this, E);
1110   }
1111
1112 private:
1113   BlockArray Blocks;
1114   BasicBlock *Entry;
1115   BasicBlock *Exit;
1116 };
1117
1118
1119 // A basic block is part of an SCFG, and can be treated as a function in
1120 // continuation passing style.  It consists of a sequence of phi nodes, which
1121 // are "arguments" to the function, followed by a sequence of instructions.
1122 // Both arguments and instructions define new variables.  It ends with a
1123 // branch or goto to another basic block in the same SCFG.
1124 class BasicBlock {
1125 public:
1126   typedef SimpleArray<Variable*> VarArray;
1127
1128   BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins,
1129              SExpr *Term = nullptr)
1130       : BlockID(0), Parent(nullptr), Args(A, Nargs), Instrs(A, Nins),
1131         Terminator(Term) {}
1132   BasicBlock(const BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T)
1133       : BlockID(0), Parent(nullptr),
1134         Args(std::move(As)), Instrs(std::move(Is)), Terminator(T)
1135   {}
1136
1137   unsigned blockID() const { return BlockID; }
1138   BasicBlock *parent() const { return Parent; }
1139
1140   const VarArray &arguments() const { return Args; }
1141   VarArray &arguments() { return Args; }
1142
1143   const VarArray &instructions() const { return Instrs; }
1144   VarArray &instructions() { return Instrs; }
1145
1146   const SExpr *terminator() const { return Terminator.get(); }
1147   SExpr *terminator() { return Terminator.get(); }
1148
1149   void setParent(BasicBlock *P) { Parent = P; }
1150   void setBlockID(unsigned i) { BlockID = i; }
1151   void setTerminator(SExpr *E) { Terminator.reset(E); }
1152   void addArgument(Variable *V) { Args.push_back(V); }
1153   void addInstr(Variable *V) { Args.push_back(V); }
1154
1155   template <class V> BasicBlock *traverse(V &Visitor) {
1156     typename V::template Container<Variable*> Nas(Visitor, Args.size());
1157     typename V::template Container<Variable*> Nis(Visitor, Instrs.size());
1158
1159     for (auto A : Args) {
1160       typename V::R_SExpr Ne = Visitor.traverse(A->Definition);
1161       Variable *Nvd = Visitor.enterScope(*A, Ne);
1162       Nas.push_back(Nvd);
1163     }
1164     for (auto I : Instrs) {
1165       typename V::R_SExpr Ne = Visitor.traverse(I->Definition);
1166       Variable *Nvd = Visitor.enterScope(*I, Ne);
1167       Nis.push_back(Nvd);
1168     }
1169     typename V::R_SExpr Nt = Visitor.traverse(Terminator);
1170
1171     // TODO: use reverse iterator
1172     for (unsigned J = 0, JN = Instrs.size(); J < JN; ++J)
1173       Visitor.exitScope(*Instrs[JN-J]);
1174     for (unsigned I = 0, IN = Instrs.size(); I < IN; ++I)
1175       Visitor.exitScope(*Args[IN-I]);
1176
1177     return Visitor.reduceBasicBlock(*this, Nas, Nis, Nt);
1178   }
1179
1180   template <class C> typename C::CType compare(BasicBlock* E, C& Cmp) {
1181     // TODO: implement CFG comparisons
1182     return Cmp.comparePointers(this, E);
1183   }
1184
1185 private:
1186   friend class SCFG;
1187
1188   unsigned BlockID;
1189   BasicBlock *Parent;   // The parent block is the enclosing lexical scope.
1190                         // The parent dominates this block.
1191   VarArray Args;        // Phi nodes
1192   VarArray Instrs;
1193   SExprRef Terminator;
1194 };
1195
1196
1197 template <class V>
1198 typename V::R_SExpr SCFG::traverse(V &Visitor) {
1199   Visitor.enterCFG(*this);
1200   typename V::template Container<BasicBlock *> Bbs(Visitor, Blocks.size());
1201   for (auto B : Blocks) {
1202     BasicBlock *Nbb = B->traverse(Visitor);
1203     Bbs.push_back(Nbb);
1204   }
1205   Visitor.exitCFG(*this);
1206   return Visitor.reduceSCFG(*this, Bbs);
1207 }
1208
1209
1210
1211 class Phi : public SExpr {
1212 public:
1213   // TODO: change to SExprRef
1214   typedef SimpleArray<SExpr*> ValArray;
1215
1216   static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1217
1218   Phi(MemRegionRef A, unsigned Nvals)
1219       : SExpr(COP_Phi), Values(A, Nvals)
1220   {}
1221   Phi(const Phi &P, ValArray &&Vs)  // steals memory of Vs
1222       : SExpr(COP_Phi), Values(std::move(Vs))
1223   {}
1224
1225   const ValArray &values() const { return Values; }
1226   ValArray &values() { return Values; }
1227
1228   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1229     typename V::template Container<typename V::R_SExpr> Nvs(Visitor,
1230                                                             Values.size());
1231     for (auto Val : Values) {
1232       typename V::R_SExpr Nv = Visitor.traverse(Val);
1233       Nvs.push_back(Nv);
1234     }
1235     return Visitor.reducePhi(*this, Nvs);
1236   }
1237
1238   template <class C> typename C::CType compare(Phi* E, C& Cmp) {
1239     // TODO -- implement CFG comparisons
1240     return Cmp.comparePointers(this, E);
1241   }
1242
1243 private:
1244   ValArray Values;
1245 };
1246
1247
1248 class Goto : public SExpr {
1249 public:
1250   static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1251
1252   Goto(BasicBlock *B, unsigned Index)
1253       : SExpr(COP_Goto), TargetBlock(B), Index(0) {}
1254   Goto(const Goto &G, BasicBlock *B, unsigned I)
1255       : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1256
1257   BasicBlock *targetBlock() const { return TargetBlock; }
1258   unsigned index() const { return Index; }
1259
1260   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1261     // TODO -- rewrite indices properly
1262     BasicBlock *Ntb = Visitor.reduceBasicBlockRef(TargetBlock);
1263     return Visitor.reduceGoto(*this, Ntb, Index);
1264   }
1265
1266   template <class C> typename C::CType compare(Goto* E, C& Cmp) {
1267     // TODO -- implement CFG comparisons
1268     return Cmp.comparePointers(this, E);
1269   }
1270
1271 private:
1272   BasicBlock *TargetBlock;
1273   unsigned Index;   // Index into Phi nodes of target block.
1274 };
1275
1276
1277 class Branch : public SExpr {
1278 public:
1279   static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1280
1281   Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1282       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {}
1283   Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1284       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {}
1285
1286   SExpr *condition() { return Condition; }
1287   BasicBlock *thenBlock() { return ThenBlock; }
1288   BasicBlock *elseBlock() { return ElseBlock; }
1289
1290   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1291     typename V::R_SExpr Nc = Visitor.traverse(Condition);
1292     BasicBlock *Ntb = Visitor.reduceBasicBlockRef(ThenBlock);
1293     BasicBlock *Nte = Visitor.reduceBasicBlockRef(ElseBlock);
1294     return Visitor.reduceBranch(*this, Nc, Ntb, Nte);
1295   }
1296
1297   template <class C> typename C::CType compare(Branch* E, C& Cmp) {
1298     // TODO -- implement CFG comparisons
1299     return Cmp.comparePointers(this, E);
1300   }
1301
1302 private:
1303   SExpr *Condition;
1304   BasicBlock *ThenBlock;
1305   BasicBlock *ElseBlock;
1306 };
1307
1308
1309
1310 // Defines an interface used to traverse SExprs.  Traversals have been made as
1311 // generic as possible, and are intended to handle any kind of pass over the
1312 // AST, e.g. visiters, copying, non-destructive rewriting, destructive
1313 // (in-place) rewriting, hashing, typing, etc.
1314 //
1315 // Traversals implement the functional notion of a "fold" operation on SExprs.
1316 // Each SExpr class provides a traverse method, which does the following:
1317 //   * e->traverse(v):
1318 //       // compute a result r_i for each subexpression e_i
1319 //       for (i = 1..n)  r_i = v.traverse(e_i);
1320 //       // combine results into a result for e,  where X is the class of e
1321 //       return v.reduceX(*e, r_1, .. r_n).
1322 //
1323 // A visitor can control the traversal by overriding the following methods:
1324 //   * v.traverse(e):
1325 //       return v.traverseByCase(e), which returns v.traverseX(e)
1326 //   * v.traverseX(e):   (X is the class of e)
1327 //       return e->traverse(v).
1328 //   * v.reduceX(*e, r_1, .. r_n):
1329 //       compute a result for a node of type X
1330 //
1331 // The reduceX methods control the kind of traversal (visitor, copy, etc.).
1332 // These are separated into a separate class R for the purpose of code reuse.
1333 // The full reducer interface also has methods to handle scopes
1334 template <class Self, class R> class Traversal : public R {
1335 public:
1336   Self *self() { return reinterpret_cast<Self *>(this); }
1337
1338   // Traverse an expression -- returning a result of type R_SExpr.
1339   // Override this method to do something for every expression, regardless
1340   // of which kind it is.  TraversalKind indicates the context in which
1341   // the expression occurs, and can be:
1342   //   TRV_Normal
1343   //   TRV_Lazy   -- e may need to be traversed lazily, using a Future.
1344   //   TRV_Tail   -- e occurs in a tail position
1345   typename R::R_SExpr traverse(SExprRef &E, TraversalKind K = TRV_Normal) {
1346     return traverse(E.get(), K);
1347   }
1348
1349   typename R::R_SExpr traverse(SExpr *E, TraversalKind K = TRV_Normal) {
1350     return traverseByCase(E);
1351   }
1352
1353   // Helper method to call traverseX(e) on the appropriate type.
1354   typename R::R_SExpr traverseByCase(SExpr *E) {
1355     switch (E->opcode()) {
1356 #define TIL_OPCODE_DEF(X)                                                   \
1357     case COP_##X:                                                           \
1358       return self()->traverse##X(cast<X>(E));
1359 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
1360 #undef TIL_OPCODE_DEF
1361     case COP_MAX:
1362       return self()->reduceNull();
1363     }
1364   }
1365
1366 // Traverse e, by static dispatch on the type "X" of e.
1367 // Override these methods to do something for a particular kind of term.
1368 #define TIL_OPCODE_DEF(X)                                                   \
1369   typename R::R_SExpr traverse##X(X *e) { return e->traverse(*self()); }
1370 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
1371 #undef TIL_OPCODE_DEF
1372 };
1373
1374
1375 // Implements a Reducer that makes a deep copy of an SExpr.
1376 // The default behavior of reduce##X(...) is to create a copy of the original.
1377 // Subclasses can override reduce##X to implement non-destructive rewriting
1378 // passes.
1379 class CopyReducer {
1380 public:
1381   CopyReducer() {}
1382
1383   void setArena(MemRegionRef A) { Arena = A; }
1384
1385   // R_SExpr is the result type for a traversal.
1386   // A copy or non-destructive rewrite returns a newly allocated term.
1387   typedef SExpr *R_SExpr;
1388
1389   // Container is a minimal interface used to store results when traversing
1390   // SExprs of variable arity, such as Phi, Goto, and SCFG.
1391   template <class T> class Container {
1392   public:
1393     // Allocate a new container with a capacity for n elements.
1394     Container(CopyReducer &R, unsigned N) : Elems(R.Arena, N) {}
1395
1396     // Push a new element onto the container.
1397     void push_back(T E) { Elems.push_back(E); }
1398
1399   private:
1400     friend class CopyReducer;
1401     SimpleArray<T> Elems;
1402   };
1403
1404 public:
1405   R_SExpr reduceNull() {
1406     return nullptr;
1407   }
1408   // R_SExpr reduceFuture(...)  is never used.
1409
1410   R_SExpr reduceUndefined(Undefined &Orig) {
1411     return new (Arena) Undefined(Orig);
1412   }
1413   R_SExpr reduceWildcard(Wildcard &Orig) {
1414     return new (Arena) Wildcard(Orig);
1415   }
1416
1417   R_SExpr reduceLiteral(Literal &Orig) {
1418     return new (Arena) Literal(Orig);
1419   }
1420   R_SExpr reduceLiteralPtr(LiteralPtr &Orig) {
1421     return new (Arena) LiteralPtr(Orig);
1422   }
1423
1424   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
1425     return new (Arena) Function(Orig, Nvd, E0);
1426   }
1427   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
1428     return new (Arena) SFunction(Orig, Nvd, E0);
1429   }
1430   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
1431     return new (Arena) Code(Orig, E0, E1);
1432   }
1433
1434   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
1435     return new (Arena) Apply(Orig, E0, E1);
1436   }
1437   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
1438     return new (Arena) SApply(Orig, E0, E1);
1439   }
1440   R_SExpr reduceProject(Project &Orig, R_SExpr E0) {
1441     return new (Arena) Project(Orig, E0);
1442   }
1443   R_SExpr reduceCall(Call &Orig, R_SExpr E0) {
1444     return new (Arena) Call(Orig, E0);
1445   }
1446
1447   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) {
1448     return new (Arena) Alloc(Orig, E0);
1449   }
1450   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) {
1451     return new (Arena) Load(Orig, E0);
1452   }
1453   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) {
1454     return new (Arena) Store(Orig, E0, E1);
1455   }
1456   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) {
1457     return new (Arena) UnaryOp(Orig, E0);
1458   }
1459   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
1460     return new (Arena) BinaryOp(Orig, E0, E1);
1461   }
1462   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) {
1463     return new (Arena) Cast(Orig, E0);
1464   }
1465
1466   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> &Bbs) {
1467     return new (Arena) SCFG(Orig, std::move(Bbs.Elems));
1468   }
1469   R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
1470     return new (Arena) Phi(Orig, std::move(As.Elems));
1471   }
1472   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, unsigned Index) {
1473     return new (Arena) Goto(Orig, B, Index);
1474   }
1475   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
1476     return new (Arena) Branch(O, C, B0, B1);
1477   }
1478
1479   BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As,
1480                                Container<Variable *> &Is, R_SExpr T) {
1481     return new (Arena) BasicBlock(Orig, std::move(As.Elems),
1482                                         std::move(Is.Elems), T);
1483   }
1484
1485   // Create a new variable from orig, and push it onto the lexical scope.
1486   Variable *enterScope(Variable &Orig, R_SExpr E0) {
1487     return new (Arena) Variable(Orig, E0);
1488   }
1489   // Exit the lexical scope of orig.
1490   void exitScope(const Variable &Orig) {}
1491
1492   void enterCFG(SCFG &Cfg) {}
1493   void exitCFG(SCFG &Cfg) {}
1494
1495   // Map Variable references to their rewritten definitions.
1496   Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
1497
1498   // Map BasicBlock references to their rewritten defs.
1499   BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
1500
1501 private:
1502   MemRegionRef Arena;
1503 };
1504
1505
1506 class SExprCopier : public Traversal<SExprCopier, CopyReducer> {
1507 public:
1508   SExprCopier(MemRegionRef A) { setArena(A); }
1509
1510   // Create a copy of e in region a.
1511   static SExpr *copy(SExpr *E, MemRegionRef A) {
1512     SExprCopier Copier(A);
1513     return Copier.traverse(E);
1514   }
1515 };
1516
1517
1518 // Implements a Reducer that visits each subexpression, and returns either
1519 // true or false.
1520 class VisitReducer {
1521 public:
1522   VisitReducer() {}
1523
1524   // A visitor returns a bool, representing success or failure.
1525   typedef bool R_SExpr;
1526
1527   // A visitor "container" is a single bool, which accumulates success.
1528   template <class T> class Container {
1529   public:
1530     Container(VisitReducer &R, unsigned N) : Success(true) {}
1531     void push_back(bool E) { Success = Success && E; }
1532
1533   private:
1534     friend class VisitReducer;
1535     bool Success;
1536   };
1537
1538 public:
1539   R_SExpr reduceNull() { return true; }
1540   R_SExpr reduceUndefined(Undefined &Orig) { return true; }
1541   R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
1542
1543   R_SExpr reduceLiteral(Literal &Orig) { return true; }
1544   R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
1545
1546   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
1547     return Nvd && E0;
1548   }
1549   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
1550     return Nvd && E0;
1551   }
1552   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
1553     return E0 && E1;
1554   }
1555   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
1556     return E0 && E1;
1557   }
1558   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
1559     return E0 && E1;
1560   }
1561   R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
1562   R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
1563   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
1564   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
1565   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
1566   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
1567   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
1568     return E0 && E1;
1569   }
1570   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
1571
1572   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) {
1573     return Bbs.Success;
1574   }
1575    R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
1576     return As.Success;
1577   }
1578   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, unsigned Index) {
1579     return true;
1580   }
1581   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
1582     return C;
1583   }
1584
1585   BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As,
1586                                Container<Variable *> &Is, R_SExpr T) {
1587     return (As.Success && Is.Success && T) ? &Orig : nullptr;
1588   }
1589
1590   Variable *enterScope(Variable &Orig, R_SExpr E0) {
1591     return E0 ? &Orig : nullptr;
1592   }
1593   void exitScope(const Variable &Orig) {}
1594
1595   void enterCFG(SCFG &Cfg) {}
1596   void exitCFG(SCFG &Cfg) {}
1597
1598   Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
1599
1600   BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
1601 };
1602
1603
1604 // A visitor will visit each node, and halt if any reducer returns false.
1605 template <class Self>
1606 class SExprVisitor : public Traversal<Self, VisitReducer> {
1607 public:
1608   SExprVisitor() : Success(true) {}
1609
1610   bool traverse(SExpr *E, TraversalKind K = TRV_Normal) {
1611     Success = Success && this->traverseByCase(E);
1612     return Success;
1613   }
1614
1615   static bool visit(SExpr *E) {
1616     SExprVisitor Visitor;
1617     return Visitor.traverse(E);
1618   }
1619
1620 private:
1621   bool Success;
1622 };
1623
1624
1625 // Basic class for comparison operations over expressions.
1626 template <typename Self>
1627 class Comparator {
1628 protected:
1629   Self *self() { return reinterpret_cast<Self *>(this); }
1630
1631 public:
1632   bool compareByCase(SExpr *E1, SExpr* E2) {
1633     switch (E1->opcode()) {
1634 #define TIL_OPCODE_DEF(X)                                                     \
1635     case COP_##X:                                                             \
1636       return cast<X>(E1)->compare(cast<X>(E2), *self());
1637 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
1638 #undef TIL_OPCODE_DEF
1639     case COP_MAX:
1640       return false;
1641     }
1642   }
1643 };
1644
1645
1646 class EqualsComparator : public Comparator<EqualsComparator> {
1647 public:
1648   // Result type for the comparison, e.g. bool for simple equality,
1649   // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
1650   // denotes "true".
1651   typedef bool CType;
1652
1653   CType trueResult() { return true; }
1654   bool notTrue(CType ct) { return !ct; }
1655
1656   bool compareIntegers(unsigned i, unsigned j) { return i == j; }
1657   bool comparePointers(const void* P, const void* Q) { return P == Q; }
1658
1659   bool compare(SExpr *E1, SExpr* E2) {
1660     if (E1->opcode() != E2->opcode())
1661       return false;
1662     return compareByCase(E1, E2);
1663   }
1664
1665   // TODO -- handle alpha-renaming of variables
1666   void enterScope(Variable* V1, Variable* V2) { }
1667   void leaveScope() { }
1668
1669   bool compareVariableRefs(Variable* V1, Variable* V2) {
1670     return V1 == V2;
1671   }
1672
1673   static bool compareExprs(SExpr *E1, SExpr* E2) {
1674     EqualsComparator Eq;
1675     return Eq.compare(E1, E2);
1676   }
1677 };
1678
1679
1680 // Pretty printer for TIL expressions
1681 template <typename Self, typename StreamType>
1682 class PrettyPrinter {
1683 public:
1684   static void print(SExpr *E, StreamType &SS) {
1685     Self printer;
1686     printer.printSExpr(E, SS, Prec_MAX);
1687   }
1688
1689 protected:
1690   Self *self() { return reinterpret_cast<Self *>(this); }
1691
1692   void newline(StreamType &SS) {
1693     SS << "\n";
1694   }
1695
1696   // TODO: further distinguish between binary operations.
1697   static const unsigned Prec_Atom = 0;
1698   static const unsigned Prec_Postfix = 1;
1699   static const unsigned Prec_Unary = 2;
1700   static const unsigned Prec_Binary = 3;
1701   static const unsigned Prec_Other = 4;
1702   static const unsigned Prec_Decl = 5;
1703   static const unsigned Prec_MAX = 6;
1704
1705   // Return the precedence of a given node, for use in pretty printing.
1706   unsigned precedence(SExpr *E) {
1707     switch (E->opcode()) {
1708       case COP_Future:     return Prec_Atom;
1709       case COP_Undefined:  return Prec_Atom;
1710       case COP_Wildcard:   return Prec_Atom;
1711
1712       case COP_Literal:    return Prec_Atom;
1713       case COP_LiteralPtr: return Prec_Atom;
1714       case COP_Variable:   return Prec_Atom;
1715       case COP_Function:   return Prec_Decl;
1716       case COP_SFunction:  return Prec_Decl;
1717       case COP_Code:       return Prec_Decl;
1718
1719       case COP_Apply:      return Prec_Postfix;
1720       case COP_SApply:     return Prec_Postfix;
1721       case COP_Project:    return Prec_Postfix;
1722
1723       case COP_Call:       return Prec_Postfix;
1724       case COP_Alloc:      return Prec_Other;
1725       case COP_Load:       return Prec_Postfix;
1726       case COP_Store:      return Prec_Other;
1727
1728       case COP_UnaryOp:    return Prec_Unary;
1729       case COP_BinaryOp:   return Prec_Binary;
1730       case COP_Cast:       return Prec_Unary;
1731
1732       case COP_SCFG:       return Prec_Decl;
1733       case COP_Phi:        return Prec_Atom;
1734       case COP_Goto:       return Prec_Atom;
1735       case COP_Branch:     return Prec_Atom;
1736       case COP_MAX:        return Prec_MAX;
1737     }
1738     return Prec_MAX;
1739   }
1740
1741   void printSExpr(SExpr *E, StreamType &SS, unsigned P) {
1742     if (!E) {
1743       self()->printNull(SS);
1744       return;
1745     }
1746     if (self()->precedence(E) > P) {
1747       // Wrap expr in () if necessary.
1748       SS << "(";
1749       self()->printSExpr(E, SS, Prec_MAX);
1750       SS << ")";
1751       return;
1752     }
1753
1754     switch (E->opcode()) {
1755 #define TIL_OPCODE_DEF(X)                                                  \
1756     case COP_##X:                                                          \
1757       self()->print##X(cast<X>(E), SS);                                    \
1758       return;
1759 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
1760 #undef TIL_OPCODE_DEF
1761     case COP_MAX:
1762       return;
1763     }
1764   }
1765
1766   void printNull(StreamType &SS) {
1767     SS << "#null";
1768   }
1769
1770   void printFuture(Future *E, StreamType &SS) {
1771     self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
1772   }
1773
1774   void printUndefined(Undefined *E, StreamType &SS) {
1775     SS << "#undefined";
1776   }
1777
1778   void printWildcard(Wildcard *E, StreamType &SS) {
1779     SS << "_";
1780   }
1781
1782   void printLiteral(Literal *E, StreamType &SS) {
1783     // TODO: actually pretty print the literal.
1784     SS << "#lit";
1785   }
1786
1787   void printLiteralPtr(LiteralPtr *E, StreamType &SS) {
1788     SS << E->clangDecl()->getName();
1789   }
1790
1791   void printVariable(Variable *E, StreamType &SS) {
1792     SS << E->name() << E->getBlockID() << "_" << E->getID();
1793   }
1794
1795   void printFunction(Function *E, StreamType &SS, unsigned sugared = 0) {
1796     switch (sugared) {
1797       default:
1798         SS << "\\(";   // Lambda
1799       case 1:
1800         SS << "(";     // Slot declarations
1801         break;
1802       case 2:
1803         SS << ", ";    // Curried functions
1804         break;
1805     }
1806     self()->printVariable(E->variableDecl(), SS);
1807     SS << ": ";
1808     self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX);
1809
1810     SExpr *B = E->body();
1811     if (B && B->opcode() == COP_Function)
1812       self()->printFunction(cast<Function>(B), SS, 2);
1813     else
1814       self()->printSExpr(B, SS, Prec_Decl);
1815   }
1816
1817   void printSFunction(SFunction *E, StreamType &SS) {
1818     SS << "@";
1819     self()->printVariable(E->variableDecl(), SS);
1820     SS << " ";
1821     self()->printSExpr(E->body(), SS, Prec_Decl);
1822   }
1823
1824   void printCode(Code *E, StreamType &SS) {
1825     SS << ": ";
1826     self()->printSExpr(E->returnType(), SS, Prec_Decl-1);
1827     SS << " = ";
1828     self()->printSExpr(E->body(), SS, Prec_Decl);
1829   }
1830
1831   void printApply(Apply *E, StreamType &SS, bool sugared = false) {
1832     SExpr *F = E->fun();
1833     if (F->opcode() == COP_Apply) {
1834       printApply(cast<Apply>(F), SS, true);
1835       SS << ", ";
1836     } else {
1837       self()->printSExpr(F, SS, Prec_Postfix);
1838       SS << "(";
1839     }
1840     self()->printSExpr(E->arg(), SS, Prec_MAX);
1841     if (!sugared)
1842       SS << ")$";
1843   }
1844
1845   void printSApply(SApply *E, StreamType &SS) {
1846     self()->printSExpr(E->sfun(), SS, Prec_Postfix);
1847     SS << "@(";
1848     self()->printSExpr(E->arg(), SS, Prec_MAX);
1849     SS << ")";
1850   }
1851
1852   void printProject(Project *E, StreamType &SS) {
1853     self()->printSExpr(E->record(), SS, Prec_Postfix);
1854     SS << ".";
1855     SS << E->slotName();
1856   }
1857
1858   void printCall(Call *E, StreamType &SS) {
1859     SExpr *T = E->target();
1860     if (T->opcode() == COP_Apply) {
1861       self()->printApply(cast<Apply>(T), SS, true);
1862       SS << ")";
1863     }
1864     else {
1865       self()->printSExpr(T, SS, Prec_Postfix);
1866       SS << "()";
1867     }
1868   }
1869
1870   void printAlloc(Alloc *E, StreamType &SS) {
1871     SS << "#alloc ";
1872     self()->printSExpr(E->dataType(), SS, Prec_Other-1);
1873   }
1874
1875   void printLoad(Load *E, StreamType &SS) {
1876     self()->printSExpr(E->pointer(), SS, Prec_Postfix);
1877     SS << "^";
1878   }
1879
1880   void printStore(Store *E, StreamType &SS) {
1881     self()->printSExpr(E->destination(), SS, Prec_Other-1);
1882     SS << " = ";
1883     self()->printSExpr(E->source(), SS, Prec_Other-1);
1884   }
1885
1886   void printUnaryOp(UnaryOp *E, StreamType &SS) {
1887     self()->printSExpr(E->expr(), SS, Prec_Unary);
1888   }
1889
1890   void printBinaryOp(BinaryOp *E, StreamType &SS) {
1891     self()->printSExpr(E->expr0(), SS, Prec_Binary-1);
1892     SS << " " << clang::BinaryOperator::getOpcodeStr(E->binaryOpcode()) << " ";
1893     self()->printSExpr(E->expr1(), SS, Prec_Binary-1);
1894   }
1895
1896   void printCast(Cast *E, StreamType &SS) {
1897     SS << "~";
1898     self()->printSExpr(E->expr(), SS, Prec_Unary);
1899   }
1900
1901   void printSCFG(SCFG *E, StreamType &SS) {
1902     SS << "#CFG {\n";
1903     for (auto BBI : *E) {
1904       SS << "BB_" << BBI->blockID() << ":";
1905       newline(SS);
1906       for (auto A : BBI->arguments()) {
1907         SS << "let ";
1908         self()->printVariable(A, SS);
1909         SS << " = ";
1910         self()->printSExpr(A->definition(), SS, Prec_MAX);
1911         SS << ";";
1912         newline(SS);
1913       }
1914       for (auto I : BBI->instructions()) {
1915         SS << "let ";
1916         self()->printVariable(I, SS);
1917         SS << " = ";
1918         self()->printSExpr(I->definition(), SS, Prec_MAX);
1919         SS << ";";
1920         newline(SS);
1921       }
1922       SExpr *T = BBI->terminator();
1923       if (T) {
1924         self()->printSExpr(T, SS, Prec_MAX);
1925         SS << ";";
1926         newline(SS);
1927       }
1928       newline(SS);
1929     }
1930     SS << "}";
1931     newline(SS);
1932   }
1933
1934   void printPhi(Phi *E, StreamType &SS) {
1935     SS << "#phi(";
1936     unsigned i = 0;
1937     for (auto V : E->values()) {
1938       ++i;
1939       if (i > 0)
1940         SS << ", ";
1941       self()->printSExpr(V, SS, Prec_MAX);
1942     }
1943     SS << ")";
1944   }
1945
1946   void printGoto(Goto *E, StreamType &SS) {
1947     SS << "#goto BB_";
1948     SS << E->targetBlock()->blockID();
1949     SS << ":";
1950     SS << E->index();
1951   }
1952
1953   void printBranch(Branch *E, StreamType &SS) {
1954     SS << "#branch (";
1955     self()->printSExpr(E->condition(), SS, Prec_MAX);
1956     SS << ") BB_";
1957     SS << E->thenBlock()->blockID();
1958     SS << " BB_";
1959     SS << E->elseBlock()->blockID();
1960   }
1961 };
1962
1963 } // end namespace til
1964
1965
1966
1967 } // end namespace threadSafety
1968 } // end namespace clang
1969
1970 #endif // THREAD_SAFETY_TIL_H