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