clang  8.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 "clang/AST/Decl.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.
103 public:
105  // Ordinary subexpressions.
107 
108  // Declarations (e.g. function bodies).
110 
111  // Expressions that require lazy evaluation.
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.
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.
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 *;
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 
157  };
158 
159  CopyReducerBase(MemRegionRef A) : Arena(A) {}
160 
161 protected:
163 };
164 
165 // Base class for visit traversals.
167 public:
168  // A visitor returns a bool, representing success or failure.
169  using R_SExpr = 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 
202  return Nvd && E0;
203  }
204 
206  return Nvd && E0;
207  }
208 
210  return E0 && E1;
211  }
212 
214  return E0 && E1;
215  }
216 
218  return E0 && E1;
219  }
220 
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 
232  return E0 && E1;
233  }
234 
236  return E0 && E1;
237  }
238 
239  R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; }
240 
242  return E0 && E1;
243  }
244 
245  R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; }
246 
248  return Bbs.Success;
249  }
250 
252  Container<R_SExpr> &Is, R_SExpr T) {
253  return (As.Success && Is.Success && T);
254  }
255 
257  return As.Success;
258  }
259 
261  return true;
262  }
263 
265  return C;
266  }
267 
269  return E;
270  }
271 
273  return true;
274  }
275 
277  return C && T && E;
278  }
279 
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) {}
290 
291  Variable *reduceVariableRef(Variable *Ovd) { return Ovd; }
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>
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;
611  SS << "\"";
612  printLiteralT(&E->as<StringRef>(), SS);
613  SS << "\"";
614  return;
616  SS << "#ptr";
617  return;
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  SS << E->castOpcode();
789  SS << "](";
790  self()->printSExpr(E->expr(), SS, Prec_Unary);
791  SS << ")";
792  return;
793  }
794  self()->printSExpr(E->expr(), SS, Prec_Unary);
795  }
796 
797  void printSCFG(const SCFG *E, StreamType &SS) {
798  SS << "CFG {\n";
799  for (const auto *BBI : *E)
800  printBasicBlock(BBI, SS);
801  SS << "}";
802  newline(SS);
803  }
804 
805  void printBBInstr(const SExpr *E, StreamType &SS) {
806  bool Sub = false;
807  if (E->opcode() == COP_Variable) {
808  const auto *V = cast<Variable>(E);
809  SS << "let " << V->name() << V->id() << " = ";
810  E = V->definition();
811  Sub = true;
812  }
813  else if (E->opcode() != COP_Store) {
814  SS << "let _x" << E->id() << " = ";
815  }
816  self()->printSExpr(E, SS, Prec_MAX, Sub);
817  SS << ";";
818  newline(SS);
819  }
820 
821  void printBasicBlock(const BasicBlock *E, StreamType &SS) {
822  SS << "BB_" << E->blockID() << ":";
823  if (E->parent())
824  SS << " BB_" << E->parent()->blockID();
825  newline(SS);
826 
827  for (const auto *A : E->arguments())
828  printBBInstr(A, SS);
829 
830  for (const auto *I : E->instructions())
831  printBBInstr(I, SS);
832 
833  const SExpr *T = E->terminator();
834  if (T) {
835  self()->printSExpr(T, SS, Prec_MAX, false);
836  SS << ";";
837  newline(SS);
838  }
839  newline(SS);
840  }
841 
842  void printPhi(const Phi *E, StreamType &SS) {
843  SS << "phi(";
844  if (E->status() == Phi::PH_SingleVal)
845  self()->printSExpr(E->values()[0], SS, Prec_MAX);
846  else {
847  unsigned i = 0;
848  for (const auto *V : E->values()) {
849  if (i++ > 0)
850  SS << ", ";
851  self()->printSExpr(V, SS, Prec_MAX);
852  }
853  }
854  SS << ")";
855  }
856 
857  void printGoto(const Goto *E, StreamType &SS) {
858  SS << "goto ";
859  printBlockLabel(SS, E->targetBlock(), E->index());
860  }
861 
862  void printBranch(const Branch *E, StreamType &SS) {
863  SS << "branch (";
864  self()->printSExpr(E->condition(), SS, Prec_MAX);
865  SS << ") ";
866  printBlockLabel(SS, E->thenBlock(), -1);
867  SS << " ";
868  printBlockLabel(SS, E->elseBlock(), -1);
869  }
870 
871  void printReturn(const Return *E, StreamType &SS) {
872  SS << "return ";
873  self()->printSExpr(E->returnValue(), SS, Prec_Other);
874  }
875 
876  void printIdentifier(const Identifier *E, StreamType &SS) {
877  SS << E->name();
878  }
879 
880  void printIfThenElse(const IfThenElse *E, StreamType &SS) {
881  if (CStyle) {
882  printSExpr(E->condition(), SS, Prec_Unary);
883  SS << " ? ";
884  printSExpr(E->thenExpr(), SS, Prec_Unary);
885  SS << " : ";
886  printSExpr(E->elseExpr(), SS, Prec_Unary);
887  return;
888  }
889  SS << "if (";
890  printSExpr(E->condition(), SS, Prec_MAX);
891  SS << ") then ";
892  printSExpr(E->thenExpr(), SS, Prec_Other);
893  SS << " else ";
894  printSExpr(E->elseExpr(), SS, Prec_Other);
895  }
896 
897  void printLet(const Let *E, StreamType &SS) {
898  SS << "let ";
899  printVariable(E->variableDecl(), SS, true);
900  SS << " = ";
901  printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1);
902  SS << "; ";
903  printSExpr(E->body(), SS, Prec_Decl-1);
904  }
905 };
906 
907 class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> {};
908 
909 } // namespace til
910 } // namespace threadSafety
911 } // namespace clang
912 
913 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_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)
std::string getSourceLiteralString(const Expr *CE)
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)
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
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)
A basic block is part of an SCFG.
void printArrayAdd(const ArrayAdd *E, StreamType &SS)
void printArrayIndex(const ArrayIndex *E, StreamType &SS)
const ValueDecl * clangDecl() const
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.
TIL_UnaryOpcode unaryOpcode() const
#define bool
Definition: stdbool.h:31
void enterScope(const Variable *V1, const Variable *V2)
bool compare(const SExpr *E1, const SExpr *E2)
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
Get a human-readable name for the declaration, even if it is one of the special kinds of names (C++ c...
Definition: Decl.h:291
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)
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)
const ValueDecl * clangDecl() const
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:1500
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)
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)