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

   1 //===- ThreadSafetyTraverse.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 framework for doing generic traversals and rewriting
  11 // operations over the Thread Safety TIL.
  12 //
  13 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H
  18 #define LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H
  19
  20 #include "ThreadSafetyTIL.h"
  21
  22 namespace clang {
  23 namespace threadSafety {
  24 namespace til {
  25
  26 // Defines an interface used to traverse SExprs.  Traversals have been made as
  27 // generic as possible, and are intended to handle any kind of pass over the
  28 // AST, e.g. visiters, copying, non-destructive rewriting, destructive
  29 // (in-place) rewriting, hashing, typing, etc.
  30 //
  31 // Traversals implement the functional notion of a "fold" operation on SExprs.
  32 // Each SExpr class provides a traverse method, which does the following:
  33 //   * e->traverse(v):
  34 //       // compute a result r_i for each subexpression e_i
  35 //       for (i = 1..n)  r_i = v.traverse(e_i);
  36 //       // combine results into a result for e,  where X is the class of e
  37 //       return v.reduceX(*e, r_1, .. r_n).
  38 //
  39 // A visitor can control the traversal by overriding the following methods:
  40 //   * v.traverse(e):
  41 //       return v.traverseByCase(e), which returns v.traverseX(e)
  42 //   * v.traverseX(e):   (X is the class of e)
  43 //       return e->traverse(v).
  44 //   * v.reduceX(*e, r_1, .. r_n):
  45 //       compute a result for a node of type X
  46 //
  47 // The reduceX methods control the kind of traversal (visitor, copy, etc.).
  48 // They are defined in derived classes.
  49 //
  50 // Class R defines the basic interface types (R_SExpr).
  51 template <class Self, class R>
  52 class Traversal {
  53 public:
  54   Self *self() { return static_cast<Self *>(this); }
  55
  56   // Traverse an expression -- returning a result of type R_SExpr.
  57   // Override this method to do something for every expression, regardless
  58   // of which kind it is.
  59   typename R::R_SExpr traverse(SExprRef &E, typename R::R_Ctx Ctx) {
  60     return traverse(E.get(), Ctx);
  61   }
  62
  63   typename R::R_SExpr traverse(SExpr *E, typename R::R_Ctx Ctx) {
  64     return traverseByCase(E, Ctx);
  65   }
  66
  67   // Helper method to call traverseX(e) on the appropriate type.
  68   typename R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx) {
  69     switch (E->opcode()) {
  70 #define TIL_OPCODE_DEF(X)                                                   \
  71     case COP_##X:                                                           \
  72       return self()->traverse##X(cast<X>(E), Ctx);
  73 #include "ThreadSafetyOps.def"
  74 #undef TIL_OPCODE_DEF
  75     }
  76   }
  77
  78 // Traverse e, by static dispatch on the type "X" of e.
  79 // Override these methods to do something for a particular kind of term.
  80 #define TIL_OPCODE_DEF(X)                                                   \
  81   typename R::R_SExpr traverse##X(X *e, typename R::R_Ctx Ctx) {            \
  82     return e->traverse(*self(), Ctx);                                       \
  83   }
  84 #include "ThreadSafetyOps.def"
  85 #undef TIL_OPCODE_DEF
  86 };
  87
  88
  89 // Base class for simple reducers that don't much care about the context.
  90 class SimpleReducerBase {
  91 public:
  92   enum TraversalKind {
  93     TRV_Normal,
  94     TRV_Decl,
  95     TRV_Lazy,
  96     TRV_Type
  97   };
  98
  99   // R_Ctx defines a "context" for the traversal, which encodes information
 100   // about where a term appears.  This can be used to encoding the
 101   // "current continuation" for CPS transforms, or other information.
 102   typedef TraversalKind R_Ctx;
 103
 104   // Create context for an ordinary subexpression.
 105   R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; }
 106
 107   // Create context for a subexpression that occurs in a declaration position
 108   // (e.g. function body).
 109   R_Ctx declCtx(R_Ctx Ctx) { return TRV_Decl; }
 110
 111   // Create context for a subexpression that occurs in a position that
 112   // should be reduced lazily.  (e.g. code body).
 113   R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; }
 114
 115   // Create context for a subexpression that occurs in a type position.
 116   R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; }
 117 };
 118
 119
 120 // Base class for traversals that rewrite an SExpr to another SExpr.
 121 class CopyReducerBase : public SimpleReducerBase {
 122 public:
 123   // R_SExpr is the result type for a traversal.
 124   // A copy or non-destructive rewrite returns a newly allocated term.
 125   typedef SExpr *R_SExpr;
 126   typedef BasicBlock *R_BasicBlock;
 127
 128   // Container is a minimal interface used to store results when traversing
 129   // SExprs of variable arity, such as Phi, Goto, and SCFG.
 130   template <class T> class Container {
 131   public:
 132     // Allocate a new container with a capacity for n elements.
 133     Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {}
 134
 135     // Push a new element onto the container.
 136     void push_back(T E) { Elems.push_back(E); }
 137
 138     SimpleArray<T> Elems;
 139   };
 140
 141   CopyReducerBase(MemRegionRef A) : Arena(A) {}
 142
 143 protected:
 144   MemRegionRef Arena;
 145 };
 146
 147
 148 // Implements a traversal that makes a deep copy of an SExpr.
 149 // The default behavior of reduce##X(...) is to create a copy of the original.
 150 // Subclasses can override reduce##X to implement non-destructive rewriting
 151 // passes.
 152 template<class Self>
 153 class CopyReducer : public Traversal<Self, CopyReducerBase>,
 154                     public CopyReducerBase {
 155 public:
 156   CopyReducer(MemRegionRef A) : CopyReducerBase(A) {}
 157
 158 public:
 159   R_SExpr reduceNull() {
 160     return nullptr;
 161   }
 162   // R_SExpr reduceFuture(...)  is never used.
 163
 164   R_SExpr reduceUndefined(Undefined &Orig) {
 165     return new (Arena) Undefined(Orig);
 166   }
 167   R_SExpr reduceWildcard(Wildcard &Orig) {
 168     return new (Arena) Wildcard(Orig);
 169   }
 170
 171   R_SExpr reduceLiteral(Literal &Orig) {
 172     return new (Arena) Literal(Orig);
 173   }
 174   template<class T>
 175   R_SExpr reduceLiteralT(LiteralT<T> &Orig) {
 176     return new (Arena) LiteralT<T>(Orig);
 177   }
 178   R_SExpr reduceLiteralPtr(LiteralPtr &Orig) {
 179     return new (Arena) LiteralPtr(Orig);
 180   }
 181
 182   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
 183     return new (Arena) Function(Orig, Nvd, E0);
 184   }
 185   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
 186     return new (Arena) SFunction(Orig, Nvd, E0);
 187   }
 188   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
 189     return new (Arena) Code(Orig, E0, E1);
 190   }
 191   R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) {
 192     return new (Arena) Field(Orig, E0, E1);
 193   }
 194
 195   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
 196     return new (Arena) Apply(Orig, E0, E1);
 197   }
 198   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
 199     return new (Arena) SApply(Orig, E0, E1);
 200   }
 201   R_SExpr reduceProject(Project &Orig, R_SExpr E0) {
 202     return new (Arena) Project(Orig, E0);
 203   }
 204   R_SExpr reduceCall(Call &Orig, R_SExpr E0) {
 205     return new (Arena) Call(Orig, E0);
 206   }
 207
 208   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) {
 209     return new (Arena) Alloc(Orig, E0);
 210   }
 211   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) {
 212     return new (Arena) Load(Orig, E0);
 213   }
 214   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) {
 215     return new (Arena) Store(Orig, E0, E1);
 216   }
 217   R_SExpr reduceArrayIndex(ArrayIndex &Orig, R_SExpr E0, R_SExpr E1) {
 218     return new (Arena) ArrayIndex(Orig, E0, E1);
 219   }
 220   R_SExpr reduceArrayAdd(ArrayAdd &Orig, R_SExpr E0, R_SExpr E1) {
 221     return new (Arena) ArrayAdd(Orig, E0, E1);
 222   }
 223   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) {
 224     return new (Arena) UnaryOp(Orig, E0);
 225   }
 226   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
 227     return new (Arena) BinaryOp(Orig, E0, E1);
 228   }
 229   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) {
 230     return new (Arena) Cast(Orig, E0);
 231   }
 232
 233   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> &Bbs) {
 234     return nullptr;  // FIXME: implement CFG rewriting
 235   }
 236   R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As,
 237                                 Container<Variable *> &Is, R_SExpr T) {
 238     return nullptr;  // FIXME: implement CFG rewriting
 239   }
 240   R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
 241     return new (Arena) Phi(Orig, std::move(As.Elems));
 242   }
 243   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) {
 244     return new (Arena) Goto(Orig, B, 0);  // FIXME: set index
 245   }
 246   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
 247     return new (Arena) Branch(O, C, B0, B1, 0, 0);  // FIXME: set indices
 248   }
 249
 250   R_SExpr reduceIdentifier(Identifier &Orig) {
 251     return new (Arena) Identifier(Orig);
 252   }
 253   R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) {
 254     return new (Arena) IfThenElse(Orig, C, T, E);
 255   }
 256   R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) {
 257     return new (Arena) Let(Orig, Nvd, B);
 258   }
 259
 260   // Create a new variable from orig, and push it onto the lexical scope.
 261   Variable *enterScope(Variable &Orig, R_SExpr E0) {
 262     return new (Arena) Variable(Orig, E0);
 263   }
 264   // Exit the lexical scope of orig.
 265   void exitScope(const Variable &Orig) {}
 266
 267   void enterCFG(SCFG &Cfg) {}
 268   void exitCFG(SCFG &Cfg) {}
 269   void enterBasicBlock(BasicBlock &BB) {}
 270   void exitBasicBlock(BasicBlock &BB) {}
 271
 272   // Map Variable references to their rewritten definitions.
 273   Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
 274
 275   // Map BasicBlock references to their rewritten definitions.
 276   BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
 277 };
 278
 279
 280 class SExprCopier : public CopyReducer<SExprCopier> {
 281 public:
 282   typedef SExpr *R_SExpr;
 283
 284   SExprCopier(MemRegionRef A) : CopyReducer(A) { }
 285
 286   // Create a copy of e in region a.
 287   static SExpr *copy(SExpr *E, MemRegionRef A) {
 288     SExprCopier Copier(A);
 289     return Copier.traverse(E, TRV_Normal);
 290   }
 291 };
 292
 293
 294
 295 // Base class for visit traversals.
 296 class VisitReducerBase : public SimpleReducerBase {
 297 public:
 298   // A visitor returns a bool, representing success or failure.
 299   typedef bool R_SExpr;
 300   typedef bool R_BasicBlock;
 301
 302   // A visitor "container" is a single bool, which accumulates success.
 303   template <class T> class Container {
 304   public:
 305     Container(VisitReducerBase &S, unsigned N) : Success(true) {}
 306     void push_back(bool E) { Success = Success && E; }
 307
 308     bool Success;
 309   };
 310 };
 311
 312
 313 // Implements a traversal that visits each subexpression, and returns either
 314 // true or false.
 315 template <class Self>
 316 class VisitReducer : public Traversal<Self, VisitReducerBase>,
 317                      public VisitReducerBase {
 318 public:
 319   VisitReducer() {}
 320
 321 public:
 322   R_SExpr reduceNull() { return true; }
 323   R_SExpr reduceUndefined(Undefined &Orig) { return true; }
 324   R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
 325
 326   R_SExpr reduceLiteral(Literal &Orig) { return true; }
 327   template<class T>
 328   R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; }
 329   R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
 330
 331   R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) {
 332     return Nvd && E0;
 333   }
 334   R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) {
 335     return Nvd && E0;
 336   }
 337   R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) {
 338     return E0 && E1;
 339   }
 340   R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) {
 341     return E0 && E1;
 342   }
 343   R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) {
 344     return E0 && E1;
 345   }
 346   R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) {
 347     return E0 && E1;
 348   }
 349   R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
 350   R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
 351   R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
 352   R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
 353   R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
 354   R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) {
 355     return E0 && E1;
 356   }
 357   R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) {
 358     return E0 && E1;
 359   }
 360   R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
 361   R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) {
 362     return E0 && E1;
 363   }
 364   R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
 365
 366   R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) {
 367     return Bbs.Success;
 368   }
 369   R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As,
 370                                 Container<Variable *> &Is, R_SExpr T) {
 371     return (As.Success && Is.Success && T);
 372   }
 373   R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) {
 374     return As.Success;
 375   }
 376   R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) {
 377     return true;
 378   }
 379   R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) {
 380     return C;
 381   }
 382
 383   R_SExpr reduceIdentifier(Identifier &Orig) {
 384     return true;
 385   }
 386   R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) {
 387     return C && T && E;
 388   }
 389   R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) {
 390     return Nvd && B;
 391   }
 392
 393   Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; }
 394   void exitScope(const Variable &Orig) {}
 395   void enterCFG(SCFG &Cfg) {}
 396   void exitCFG(SCFG &Cfg) {}
 397   void enterBasicBlock(BasicBlock &BB) {}
 398   void exitBasicBlock(BasicBlock &BB) {}
 399
 400   Variable   *reduceVariableRef  (Variable *Ovd)   { return Ovd; }
 401   BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; }
 402
 403 public:
 404   bool traverse(SExpr *E, TraversalKind K = TRV_Normal) {
 405     Success = Success && this->traverseByCase(E);
 406     return Success;
 407   }
 408
 409   static bool visit(SExpr *E) {
 410     Self Visitor;
 411     return Visitor.traverse(E, TRV_Normal);
 412   }
 413
 414 private:
 415   bool Success;
 416 };
 417
 418
 419 // Basic class for comparison operations over expressions.
 420 template <typename Self>
 421 class Comparator {
 422 protected:
 423   Self *self() { return reinterpret_cast<Self *>(this); }
 424
 425 public:
 426   bool compareByCase(SExpr *E1, SExpr* E2) {
 427     switch (E1->opcode()) {
 428 #define TIL_OPCODE_DEF(X)                                                     \
 429     case COP_##X:                                                             \
 430       return cast<X>(E1)->compare(cast<X>(E2), *self());
 431 #include "ThreadSafetyOps.def"
 432 #undef TIL_OPCODE_DEF
 433     }
 434   }
 435 };
 436
 437
 438 class EqualsComparator : public Comparator<EqualsComparator> {
 439 public:
 440   // Result type for the comparison, e.g. bool for simple equality,
 441   // or int for lexigraphic comparison (-1, 0, 1).  Must have one value which
 442   // denotes "true".
 443   typedef bool CType;
 444
 445   CType trueResult() { return true; }
 446   bool notTrue(CType ct) { return !ct; }
 447
 448   bool compareIntegers(unsigned i, unsigned j)       { return i == j; }
 449   bool compareStrings (StringRef s, StringRef r)     { return s == r; }
 450   bool comparePointers(const void* P, const void* Q) { return P == Q; }
 451
 452   bool compare(SExpr *E1, SExpr* E2) {
 453     if (E1->opcode() != E2->opcode())
 454       return false;
 455     return compareByCase(E1, E2);
 456   }
 457
 458   // TODO -- handle alpha-renaming of variables
 459   void enterScope(Variable* V1, Variable* V2) { }
 460   void leaveScope() { }
 461
 462   bool compareVariableRefs(Variable* V1, Variable* V2) {
 463     return V1 == V2;
 464   }
 465
 466   static bool compareExprs(SExpr *E1, SExpr* E2) {
 467     EqualsComparator Eq;
 468     return Eq.compare(E1, E2);
 469   }
 470 };
 471
 472
 473 // Pretty printer for TIL expressions
 474 template <typename Self, typename StreamType>
 475 class PrettyPrinter {
 476 private:
 477   bool Verbose;  // Print out additional information
 478   bool Cleanup;  // Omit redundant decls.
 479
 480 public:
 481   PrettyPrinter(bool V = false, bool C = true) : Verbose(V), Cleanup(C) { }
 482
 483   static void print(SExpr *E, StreamType &SS) {
 484     Self printer;
 485     printer.printSExpr(E, SS, Prec_MAX);
 486   }
 487
 488 protected:
 489   Self *self() { return reinterpret_cast<Self *>(this); }
 490
 491   void newline(StreamType &SS) {
 492     SS << "\n";
 493   }
 494
 495   // TODO: further distinguish between binary operations.
 496   static const unsigned Prec_Atom = 0;
 497   static const unsigned Prec_Postfix = 1;
 498   static const unsigned Prec_Unary = 2;
 499   static const unsigned Prec_Binary = 3;
 500   static const unsigned Prec_Other = 4;
 501   static const unsigned Prec_Decl = 5;
 502   static const unsigned Prec_MAX = 6;
 503
 504   // Return the precedence of a given node, for use in pretty printing.
 505   unsigned precedence(SExpr *E) {
 506     switch (E->opcode()) {
 507       case COP_Future:     return Prec_Atom;
 508       case COP_Undefined:  return Prec_Atom;
 509       case COP_Wildcard:   return Prec_Atom;
 510
 511       case COP_Literal:    return Prec_Atom;
 512       case COP_LiteralPtr: return Prec_Atom;
 513       case COP_Variable:   return Prec_Atom;
 514       case COP_Function:   return Prec_Decl;
 515       case COP_SFunction:  return Prec_Decl;
 516       case COP_Code:       return Prec_Decl;
 517       case COP_Field:      return Prec_Decl;
 518
 519       case COP_Apply:      return Prec_Postfix;
 520       case COP_SApply:     return Prec_Postfix;
 521       case COP_Project:    return Prec_Postfix;
 522
 523       case COP_Call:       return Prec_Postfix;
 524       case COP_Alloc:      return Prec_Other;
 525       case COP_Load:       return Prec_Postfix;
 526       case COP_Store:      return Prec_Other;
 527       case COP_ArrayIndex: return Prec_Postfix;
 528       case COP_ArrayAdd:   return Prec_Postfix;
 529
 530       case COP_UnaryOp:    return Prec_Unary;
 531       case COP_BinaryOp:   return Prec_Binary;
 532       case COP_Cast:       return Prec_Unary;
 533
 534       case COP_SCFG:       return Prec_Decl;
 535       case COP_BasicBlock: return Prec_MAX;
 536       case COP_Phi:        return Prec_Atom;
 537       case COP_Goto:       return Prec_Atom;
 538       case COP_Branch:     return Prec_Atom;
 539
 540       case COP_Identifier: return Prec_Atom;
 541       case COP_IfThenElse: return Prec_Other;
 542       case COP_Let:        return Prec_Decl;
 543     }
 544     return Prec_MAX;
 545   }
 546
 547   void printBlockLabel(StreamType & SS, BasicBlock *BB, unsigned index) {
 548     if (!BB) {
 549       SS << "BB_null";
 550       return;
 551     }
 552     SS << "BB_";
 553     SS << BB->blockID();
 554     SS << ":";
 555     SS << index;
 556   }
 557
 558   void printSExpr(SExpr *E, StreamType &SS, unsigned P) {
 559     if (!E) {
 560       self()->printNull(SS);
 561       return;
 562     }
 563     if (self()->precedence(E) > P) {
 564       // Wrap expr in () if necessary.
 565       SS << "(";
 566       self()->printSExpr(E, SS, Prec_MAX);
 567       SS << ")";
 568       return;
 569     }
 570
 571     switch (E->opcode()) {
 572 #define TIL_OPCODE_DEF(X)                                                  \
 573     case COP_##X:                                                          \
 574       self()->print##X(cast<X>(E), SS);                                    \
 575       return;
 576 #include "ThreadSafetyOps.def"
 577 #undef TIL_OPCODE_DEF
 578     }
 579   }
 580
 581   void printNull(StreamType &SS) {
 582     SS << "#null";
 583   }
 584
 585   void printFuture(Future *E, StreamType &SS) {
 586     self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
 587   }
 588
 589   void printUndefined(Undefined *E, StreamType &SS) {
 590     SS << "#undefined";
 591   }
 592
 593   void printWildcard(Wildcard *E, StreamType &SS) {
 594     SS << "_";
 595   }
 596
 597   template<class T>
 598   void printLiteralT(LiteralT<T> *E, StreamType &SS) {
 599     SS << E->value();
 600   }
 601
 602   void printLiteralT(LiteralT<uint8_t> *E, StreamType &SS) {
 603     SS << "'" << E->value() << "'";
 604   }
 605
 606   void printLiteral(Literal *E, StreamType &SS) {
 607     if (E->clangExpr()) {
 608       SS << getSourceLiteralString(E->clangExpr());
 609       return;
 610     }
 611     else {
 612       ValueType VT = E->valueType();
 613       switch (VT.Base) {
 614       case ValueType::BT_Void: {
 615         SS << "void";
 616         return;
 617       }
 618       case ValueType::BT_Bool: {
 619         if (E->as<bool>().value())
 620           SS << "true";
 621         else
 622           SS << "false";
 623         return;
 624       }
 625       case ValueType::BT_Int: {
 626         switch (VT.Size) {
 627         case ValueType::ST_8:
 628           if (VT.Signed)
 629             printLiteralT(&E->as<int8_t>(), SS);
 630           else
 631             printLiteralT(&E->as<uint8_t>(), SS);
 632           return;
 633         case ValueType::ST_16:
 634           if (VT.Signed)
 635             printLiteralT(&E->as<int16_t>(), SS);
 636           else
 637             printLiteralT(&E->as<uint16_t>(), SS);
 638           return;
 639         case ValueType::ST_32:
 640           if (VT.Signed)
 641             printLiteralT(&E->as<int32_t>(), SS);
 642           else
 643             printLiteralT(&E->as<uint32_t>(), SS);
 644           return;
 645         case ValueType::ST_64:
 646           if (VT.Signed)
 647             printLiteralT(&E->as<int64_t>(), SS);
 648           else
 649             printLiteralT(&E->as<uint64_t>(), SS);
 650           return;
 651         default:
 652           break;
 653         }
 654         break;
 655       }
 656       case ValueType::BT_Float: {
 657         switch (VT.Size) {
 658         case ValueType::ST_32:
 659           printLiteralT(&E->as<float>(), SS);
 660           return;
 661         case ValueType::ST_64:
 662           printLiteralT(&E->as<double>(), SS);
 663           return;
 664         default:
 665           break;
 666         }
 667         break;
 668       }
 669       case ValueType::BT_String: {
 670         SS << "\"";
 671         printLiteralT(&E->as<StringRef>(), SS);
 672         SS << "\"";
 673         return;
 674       }
 675       case ValueType::BT_Pointer: {
 676         SS << "#ptr";
 677         return;
 678       }
 679       case ValueType::BT_ValueRef: {
 680         SS << "#vref";
 681         return;
 682       }
 683       }
 684     }
 685     SS << "#lit";
 686   }
 687
 688   void printLiteralPtr(LiteralPtr *E, StreamType &SS) {
 689     SS << E->clangDecl()->getNameAsString();
 690   }
 691
 692   void printVariable(Variable *V, StreamType &SS, bool IsVarDecl = false) {
 693     if (!IsVarDecl && Cleanup) {
 694       SExpr* E = getCanonicalVal(V);
 695       if (E != V) {
 696         printSExpr(E, SS, Prec_Atom);
 697         return;
 698       }
 699     }
 700     if (V->kind() == Variable::VK_LetBB)
 701       SS << V->name() << V->getBlockID() << "_" << V->getID();
 702     else
 703       SS << V->name() << V->getID();
 704   }
 705
 706   void printFunction(Function *E, StreamType &SS, unsigned sugared = 0) {
 707     switch (sugared) {
 708       default:
 709         SS << "\\(";   // Lambda
 710         break;
 711       case 1:
 712         SS << "(";     // Slot declarations
 713         break;
 714       case 2:
 715         SS << ", ";    // Curried functions
 716         break;
 717     }
 718     self()->printVariable(E->variableDecl(), SS, true);
 719     SS << ": ";
 720     self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX);
 721
 722     SExpr *B = E->body();
 723     if (B && B->opcode() == COP_Function)
 724       self()->printFunction(cast<Function>(B), SS, 2);
 725     else {
 726       SS << ")";
 727       self()->printSExpr(B, SS, Prec_Decl);
 728     }
 729   }
 730
 731   void printSFunction(SFunction *E, StreamType &SS) {
 732     SS << "@";
 733     self()->printVariable(E->variableDecl(), SS, true);
 734     SS << " ";
 735     self()->printSExpr(E->body(), SS, Prec_Decl);
 736   }
 737
 738   void printCode(Code *E, StreamType &SS) {
 739     SS << ": ";
 740     self()->printSExpr(E->returnType(), SS, Prec_Decl-1);
 741     SS << " -> ";
 742     self()->printSExpr(E->body(), SS, Prec_Decl);
 743   }
 744
 745   void printField(Field *E, StreamType &SS) {
 746     SS << ": ";
 747     self()->printSExpr(E->range(), SS, Prec_Decl-1);
 748     SS << " = ";
 749     self()->printSExpr(E->body(), SS, Prec_Decl);
 750   }
 751
 752   void printApply(Apply *E, StreamType &SS, bool sugared = false) {
 753     SExpr *F = E->fun();
 754     if (F->opcode() == COP_Apply) {
 755       printApply(cast<Apply>(F), SS, true);
 756       SS << ", ";
 757     } else {
 758       self()->printSExpr(F, SS, Prec_Postfix);
 759       SS << "(";
 760     }
 761     self()->printSExpr(E->arg(), SS, Prec_MAX);
 762     if (!sugared)
 763       SS << ")$";
 764   }
 765
 766   void printSApply(SApply *E, StreamType &SS) {
 767     self()->printSExpr(E->sfun(), SS, Prec_Postfix);
 768     if (E->isDelegation()) {
 769       SS << "@(";
 770       self()->printSExpr(E->arg(), SS, Prec_MAX);
 771       SS << ")";
 772     }
 773   }
 774
 775   void printProject(Project *E, StreamType &SS) {
 776     self()->printSExpr(E->record(), SS, Prec_Postfix);
 777     SS << ".";
 778     SS << E->slotName();
 779   }
 780
 781   void printCall(Call *E, StreamType &SS) {
 782     SExpr *T = E->target();
 783     if (T->opcode() == COP_Apply) {
 784       self()->printApply(cast<Apply>(T), SS, true);
 785       SS << ")";
 786     }
 787     else {
 788       self()->printSExpr(T, SS, Prec_Postfix);
 789       SS << "()";
 790     }
 791   }
 792
 793   void printAlloc(Alloc *E, StreamType &SS) {
 794     SS << "new ";
 795     self()->printSExpr(E->dataType(), SS, Prec_Other-1);
 796   }
 797
 798   void printLoad(Load *E, StreamType &SS) {
 799     self()->printSExpr(E->pointer(), SS, Prec_Postfix);
 800     SS << "^";
 801   }
 802
 803   void printStore(Store *E, StreamType &SS) {
 804     self()->printSExpr(E->destination(), SS, Prec_Other-1);
 805     SS << " := ";
 806     self()->printSExpr(E->source(), SS, Prec_Other-1);
 807   }
 808
 809   void printArrayIndex(ArrayIndex *E, StreamType &SS) {
 810     self()->printSExpr(E->array(), SS, Prec_Postfix);
 811     SS << "[";
 812     self()->printSExpr(E->index(), SS, Prec_MAX);
 813     SS << "]";
 814   }
 815
 816   void printArrayAdd(ArrayAdd *E, StreamType &SS) {
 817     self()->printSExpr(E->array(), SS, Prec_Postfix);
 818     SS << " + ";
 819     self()->printSExpr(E->index(), SS, Prec_Atom);
 820   }
 821
 822   void printUnaryOp(UnaryOp *E, StreamType &SS) {
 823     SS << getUnaryOpcodeString(E->unaryOpcode());
 824     self()->printSExpr(E->expr(), SS, Prec_Unary);
 825   }
 826
 827   void printBinaryOp(BinaryOp *E, StreamType &SS) {
 828     self()->printSExpr(E->expr0(), SS, Prec_Binary-1);
 829     SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " ";
 830     self()->printSExpr(E->expr1(), SS, Prec_Binary-1);
 831   }
 832
 833   void printCast(Cast *E, StreamType &SS) {
 834     SS << "%";
 835     self()->printSExpr(E->expr(), SS, Prec_Unary);
 836   }
 837
 838   void printSCFG(SCFG *E, StreamType &SS) {
 839     SS << "CFG {\n";
 840     for (auto BBI : *E) {
 841       printBasicBlock(BBI, SS);
 842     }
 843     SS << "}";
 844     newline(SS);
 845   }
 846
 847   void printBasicBlock(BasicBlock *E, StreamType &SS) {
 848     SS << "BB_" << E->blockID() << ":";
 849     if (E->parent())
 850       SS << " BB_" << E->parent()->blockID();
 851     newline(SS);
 852     for (auto *A : E->arguments()) {
 853       SS << "let ";
 854       self()->printVariable(A, SS, true);
 855       SS << " = ";
 856       self()->printSExpr(A->definition(), SS, Prec_MAX);
 857       SS << ";";
 858       newline(SS);
 859     }
 860     for (auto *I : E->instructions()) {
 861       if (I->definition()->opcode() != COP_Store) {
 862         SS << "let ";
 863         self()->printVariable(I, SS, true);
 864         SS << " = ";
 865       }
 866       self()->printSExpr(I->definition(), SS, Prec_MAX);
 867       SS << ";";
 868       newline(SS);
 869     }
 870     SExpr *T = E->terminator();
 871     if (T) {
 872       self()->printSExpr(T, SS, Prec_MAX);
 873       SS << ";";
 874       newline(SS);
 875     }
 876     newline(SS);
 877   }
 878
 879   void printPhi(Phi *E, StreamType &SS) {
 880     SS << "phi(";
 881     if (E->status() == Phi::PH_SingleVal)
 882       self()->printSExpr(E->values()[0], SS, Prec_MAX);
 883     else {
 884       unsigned i = 0;
 885       for (auto V : E->values()) {
 886         if (i++ > 0)
 887           SS << ", ";
 888         self()->printSExpr(V, SS, Prec_MAX);
 889       }
 890     }
 891     SS << ")";
 892   }
 893
 894   void printGoto(Goto *E, StreamType &SS) {
 895     SS << "goto ";
 896     printBlockLabel(SS, E->targetBlock(), E->index());
 897   }
 898
 899   void printBranch(Branch *E, StreamType &SS) {
 900     SS << "branch (";
 901     self()->printSExpr(E->condition(), SS, Prec_MAX);
 902     SS << ") ";
 903     printBlockLabel(SS, E->thenBlock(), E->thenIndex());
 904     SS << " ";
 905     printBlockLabel(SS, E->elseBlock(), E->elseIndex());
 906   }
 907
 908   void printIdentifier(Identifier *E, StreamType &SS) {
 909     SS << E->name();
 910   }
 911
 912   void printIfThenElse(IfThenElse *E, StreamType &SS) {
 913     SS << "if (";
 914     printSExpr(E->condition(), SS, Prec_MAX);
 915     SS << ") then ";
 916     printSExpr(E->thenExpr(), SS, Prec_Other);
 917     SS << " else ";
 918     printSExpr(E->elseExpr(), SS, Prec_Other);
 919   }
 920
 921   void printLet(Let *E, StreamType &SS) {
 922     SS << "let ";
 923     printVariable(E->variableDecl(), SS, true);
 924     SS << " = ";
 925     printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1);
 926     SS << "; ";
 927     printSExpr(E->body(), SS, Prec_Decl-1);
 928   }
 929 };
 930
 931
 932 } // end namespace til
 933 } // end namespace threadSafety
 934 } // end namespace clang
 935
 936 #endif  // LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H