clang  6.0.0svn
ThreadSafetyTraverse.h
Go to the documentation of this file.
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:
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>
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.
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.
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.
98 public:
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.
110 
111  // Create context for an ordinary subexpression.
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).
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).
120  R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; }
121 
122  // Create context for a subexpression that occurs in a type position.
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.
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;
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.
140  Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {}
141 
142  // Push a new element onto the container.
143  void push_back(T E) { Elems.push_back(E); }
144 
146  };
147 
148  CopyReducerBase(MemRegionRef A) : Arena(A) {}
149 
150 protected:
152 };
153 
154 
155 // Base class for visit traversals.
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:
165  Container(VisitReducerBase &S, unsigned N) : Success(true) {}
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:
180 
181 public:
182  R_SExpr reduceNull() { return true; }
183  R_SExpr reduceUndefined(Undefined &Orig) { return true; }
184  R_SExpr reduceWildcard(Wildcard &Orig) { return true; }
185 
186  R_SExpr reduceLiteral(Literal &Orig) { return true; }
187  template<class T>
188  R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; }
189  R_SExpr reduceLiteralPtr(Literal &Orig) { return true; }
190 
192  return Nvd && E0;
193  }
195  return Nvd && E0;
196  }
198  return E0 && E1;
199  }
201  return E0 && E1;
202  }
204  return E0 && E1;
205  }
207  return E0 && E1;
208  }
209  R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; }
210  R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; }
211  R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; }
212  R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; }
213  R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; }
215  return E0 && E1;
216  }
218  return E0 && E1;
219  }
220  R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
222  return E0 && E1;
223  }
224  R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
225 
227  return Bbs.Success;
228  }
231  return (As.Success && Is.Success && T);
232  }
234  return As.Success;
235  }
237  return true;
238  }
240  return C;
241  }
243  return E;
244  }
245 
247  return true;
248  }
250  return C && T && E;
251  }
253  return Nvd && B;
254  }
255 
256  Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; }
257  void exitScope(const Variable &Orig) {}
258  void enterCFG(SCFG &Cfg) {}
259  void exitCFG(SCFG &Cfg) {}
262 
263  Variable *reduceVariableRef (Variable *Ovd) { return Ovd; }
265 
266 public:
267  bool traverse(SExpr *E, TraversalKind K = TRV_Normal) {
268  Success = Success && this->traverseByCase(E);
269  return Success;
270  }
271 
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:
286  Self *self() { return reinterpret_cast<Self *>(this); }
287 
288 public:
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 
309  CType trueResult() { return true; }
310  bool notTrue(CType ct) { return !ct; }
311 
312  bool compareIntegers(unsigned i, unsigned j) { return i == j; }
313  bool compareStrings (StringRef s, StringRef r) { return s == r; }
314  bool comparePointers(const void* P, const void* Q) { return P == Q; }
315 
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
323  void enterScope(const Variable* V1, const Variable* V2) { }
324  void leaveScope() { }
325 
326  bool compareVariableRefs(const Variable* V1, const Variable* V2) {
327  return V1 == V2;
328  }
329 
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 
345  CType trueResult() { return true; }
346  bool notTrue(CType ct) { return !ct; }
347 
348  bool compareIntegers(unsigned i, unsigned j) { return i == j; }
349  bool compareStrings (StringRef s, StringRef r) { return s == r; }
350  bool comparePointers(const void* P, const void* Q) { return P == Q; }
351 
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
363  void enterScope(const Variable* V1, const Variable* V2) { }
364  void leaveScope() { }
365 
366  bool compareVariableRefs(const Variable* V1, const Variable* V2) {
367  return V1 == V2;
368  }
369 
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>
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)
392  : Verbose(V), Cleanup(C), CStyle(CS)
393  {}
394 
395  static void print(const SExpr *E, StreamType &SS) {
396  Self printer;
397  printer.printSExpr(E, SS, Prec_MAX);
398  }
399 
400 protected:
401  Self *self() { return reinterpret_cast<Self *>(this); }
402 
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.
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 
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 
501  void printNull(StreamType &SS) {
502  SS << "#null";
503  }
504 
505  void printFuture(const Future *E, StreamType &SS) {
506  self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom);
507  }
508 
509  void printUndefined(const Undefined *E, StreamType &SS) {
510  SS << "#undefined";
511  }
512 
513  void printWildcard(const Wildcard *E, StreamType &SS) {
514  SS << "*";
515  }
516 
517  template<class T>
518  void printLiteralT(const LiteralT<T> *E, StreamType &SS) {
519  SS << E->value();
520  }
521 
522  void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) {
523  SS << "'" << E->value() << "'";
524  }
525 
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 
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 
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 
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 
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 
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 
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 
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 
728  void printAlloc(const Alloc *E, StreamType &SS) {
729  SS << "new ";
730  self()->printSExpr(E->dataType(), SS, Prec_Other-1);
731  }
732 
733  void printLoad(const Load *E, StreamType &SS) {
734  self()->printSExpr(E->pointer(), SS, Prec_Postfix);
735  if (!CStyle)
736  SS << "^";
737  }
738 
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 
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 
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 
758  void printUnaryOp(const UnaryOp *E, StreamType &SS) {
759  SS << getUnaryOpcodeString(E->unaryOpcode());
760  self()->printSExpr(E->expr(), SS, Prec_Unary);
761  }
762 
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 
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 
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 
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 
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 
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 
843  void printGoto(const Goto *E, StreamType &SS) {
844  SS << "goto ";
845  printBlockLabel(SS, E->targetBlock(), E->index());
846  }
847 
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 
857  void printReturn(const Return *E, StreamType &SS) {
858  SS << "return ";
859  self()->printSExpr(E->returnValue(), SS, Prec_Other);
860  }
861 
862  void printIdentifier(const Identifier *E, StreamType &SS) {
863  SS << E->name();
864  }
865 
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 
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
VariableKind kind() const
Return the kind of variable (let, function param, or self)
R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1)
Simple arithmetic unary operations, e.g.
Apply a self-argument to a self-applicable function.
unsigned index() const
Returns the index into the.
Pointer arithmetic, restricted to arrays only.
TIL_BinaryOpcode binaryOpcode() const
const Terminator * terminator() const
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)
Return the name of a binary opcode.
R_SExpr reduceCall(Call &Orig, R_SExpr E0)
R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1)
void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true)
void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false)
R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0)
A typed, writable location in memory.
A conditional branch to two other blocks.
bool compareVariableRefs(const Variable *V1, const Variable *V2)
ValueTypes are data types that can actually be held in registers.
void printStore(const Store *E, StreamType &SS)
R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1)
StringRef P
void printCall(const Call *E, StreamType &SS)
R::R_SExpr traverse(T *&E, typename R::R_Ctx Ctx)
R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1)
BasicBlock * reduceBasicBlockRef(BasicBlock *Obb)
R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E)
StringRef name() const
Return the name of the variable, if any.
void printWildcard(const Wildcard *E, StreamType &SS)
R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1)
If p is a reference to an array, then p[i] is a reference to the i&#39;th element of the array...
unsigned id() const
Returns the instruction ID for this expression.
Project a named slot from a C++ struct or class.
R::R_SExpr traverseSExpr(SExpr *E, typename R::R_Ctx Ctx)
void printUndefined(const Undefined *E, StreamType &SS)
R_SExpr reduceProject(Project &Orig, R_SExpr E0)
R_SExpr reducePhi(Phi &Orig, Container< R_SExpr > &As)
R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx)
R_SExpr reduceSCFG(SCFG &Orig, Container< BasicBlock *> Bbs)
void printReturn(const Return *E, StreamType &SS)
void printLiteralT(const LiteralT< uint8_t > *E, StreamType &SS)
const LiteralT< T > & as() const
void printBinaryOp(const BinaryOp *E, StreamType &SS)
R_SExpr reduceReturn(Return &O, R_SExpr E)
void printSFunction(const SFunction *E, StreamType &SS)
static void print(const SExpr *E, StreamType &SS)
void printFunction(const Function *E, StreamType &SS, unsigned sugared=0)
bool compareVariableRefs(const Variable *V1, const Variable *V2)
R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B)
const clang::ValueDecl * clangDecl() const
A basic block is part of an SCFG.
void printArrayAdd(const ArrayAdd *E, StreamType &SS)
void printArrayIndex(const ArrayIndex *E, StreamType &SS)
Placeholder for expressions that cannot be represented in the TIL.
bool traverse(SExpr *E, TraversalKind K=TRV_Normal)
R_SExpr reduceCast(Cast &Orig, R_SExpr E0)
A self-applicable function.
An SCFG is a control-flow graph.
R_SExpr reduceLoad(Load &Orig, R_SExpr E0)
R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1)
void printLiteral(const Literal *E, StreamType &SS)
PrettyPrinter(bool V=false, bool C=true, bool CS=true)
void printField(const Field *E, StreamType &SS)
Apply an argument to a function.
void printBranch(const Branch *E, StreamType &SS)
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)
Return the name of a unary opcode.
const FunctionProtoType * T
TIL_UnaryOpcode unaryOpcode() const
void enterScope(const Variable *V1, const Variable *V2)
bool compare(const SExpr *E1, const SExpr *E2)
const clang::ValueDecl * clangDecl() const
bool compareByCase(const SExpr *E1, const SExpr *E2)
R_SExpr reduceLiteralT(LiteralT< T > &Orig)
Jump to another basic block.
void printCast(const Cast *E, StreamType &SS)
Return from the enclosing function, passing the return value to the caller.
R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0)
static bool compareExprs(const SExpr *E1, const SExpr *E2)
bool compareIntegers(unsigned i, unsigned j)
void enterScope(const Variable *V1, const Variable *V2)
void printGoto(const Goto *E, StreamType &SS)
void printBasicBlock(const BasicBlock *E, StreamType &SS)
R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1)
void printFuture(const Future *E, StreamType &SS)
void printLet(const Let *E, StreamType &SS)
bool compareStrings(StringRef s, StringRef r)
const BasicBlock * parent() const
std::string getNameAsString() const
getNameAsString - Get a human-readable name for the declaration, even if it is one of the special kin...
Definition: Decl.h:252
const ValArray & values() const
void printBBInstr(const SExpr *E, StreamType &SS)
bool comparePointers(const void *P, const void *Q)
R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0)
std::string getSourceLiteralString(const clang::Expr *CE)
Placeholder for a wildcard that matches any other expression.
void printApply(const Apply *E, StreamType &SS, bool sugared=false)
const InstrArray & arguments() const
const BasicBlock * thenBlock() const
const BasicBlock * targetBlock() const
Load a value from memory.
Dataflow Directional Tag Classes.
Allocate memory for a new value on the heap or stack.
void printSApply(const SApply *E, StreamType &SS)
void printSCFG(const SCFG *E, StreamType &SS)
void printUnaryOp(const UnaryOp *E, StreamType &SS)
An if-then-else expression.
R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0)
BasicBlock * block() const
Returns the block, if this is an instruction in a basic block, otherwise returns null.
Variable * enterScope(Variable &Orig, R_SExpr E0)
const BasicBlock * elseBlock() const
A let-expression, e.g.
R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container< R_SExpr > &As, Container< R_SExpr > &Is, R_SExpr T)
Phi Node, for code in SSA form.
R_SExpr reduceGoto(Goto &Orig, BasicBlock *B)
Simple arithmetic binary operations, e.g.
A block of code – e.g. the body of a function.
void printBlockLabel(StreamType &SS, const BasicBlock *BB, int index)
R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1)
void printLiteralPtr(const LiteralPtr *E, StreamType &SS)
void printLiteralT(const LiteralT< T > *E, StreamType &SS)
void printIdentifier(const Identifier *E, StreamType &SS)
TIL_CastOpcode castOpcode() const
R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1)
SExpr * definition()
Return the definition of the variable.
void printProject(const Project *E, StreamType &SS)
int blockID() const
Returns the block ID. Every block has a unique ID in the CFG.
void printAlloc(const Alloc *E, StreamType &SS)
Store a value to memory.
bool compare(const SExpr *E1, const SExpr *E2)
void printIfThenElse(const IfThenElse *E, StreamType &SS)
std::string getQualifiedNameAsString() const
Definition: Decl.cpp:1436
const clang::Expr * clangExpr() const
Placeholder for an expression that has not yet been created.
Base class for AST nodes in the typed intermediate language.
A Literal pointer to an object allocated in memory.
void printPhi(const Phi *E, StreamType &SS)
static bool compareExprs(const SExpr *E1, const SExpr *E2)
#define true
Definition: stdbool.h:32
Call a function (after all arguments have been applied).
void printLoad(const Load *E, StreamType &SS)
bool compareStrings(StringRef s, StringRef r)
bool comparePointers(const void *P, const void *Q)
void printCode(const Code *E, StreamType &SS)