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