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