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