clang 17.0.0git
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
28namespace clang {
29namespace threadSafety {
30namespace 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).
57template <class Self, class R>
58class Traversal {
59public:
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.
102public:
104 // Ordinary subexpressions.
106
107 // Declarations (e.g. function bodies).
109
110 // Expressions that require lazy evaluation.
112
113 // Type expressions.
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.
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.
139public:
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
159
160protected:
162};
163
164// Base class for visit traversals.
166public:
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.
184template <class Self>
185class VisitReducer : public Traversal<Self, VisitReducerBase>,
186 public VisitReducerBase {
187public:
188 VisitReducer() = default;
189
190public:
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
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
293public:
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
304private:
305 bool Success;
306};
307
308// Basic class for comparison operations over expressions.
309template <typename Self>
311protected:
312 Self *self() { return reinterpret_cast<Self *>(this); }
313
314public:
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
327class EqualsComparator : public Comparator<EqualsComparator> {
328public:
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) {
357 return Eq.compare(E1, E2);
358 }
359};
360
361class MatchComparator : public Comparator<MatchComparator> {
362public:
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
404template <typename Self, typename StreamType>
406private:
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
416public:
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
425protected:
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()) {
553 return;
554 }
555 else {
556 ValueType VT = E->valueType();
557 switch (VT.Base) {
559 SS << "void";
560 return;
562 if (E->as<bool>().value())
563 SS << "true";
564 else
565 SS << "false";
566 return;
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;
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 if (const NamedDecl *D = E->clangDecl())
627 SS << D->getNameAsString();
628 else
629 SS << "<temporary>";
630 }
631
632 void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) {
633 if (CStyle && V->kind() == Variable::VK_SFun)
634 SS << "this";
635 else
636 SS << V->name() << V->id();
637 }
638
639 void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) {
640 switch (sugared) {
641 default:
642 SS << "\\("; // Lambda
643 break;
644 case 1:
645 SS << "("; // Slot declarations
646 break;
647 case 2:
648 SS << ", "; // Curried functions
649 break;
650 }
651 self()->printVariable(E->variableDecl(), SS, true);
652 SS << ": ";
653 self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX);
654
655 const SExpr *B = E->body();
656 if (B && B->opcode() == COP_Function)
657 self()->printFunction(cast<Function>(B), SS, 2);
658 else {
659 SS << ")";
660 self()->printSExpr(B, SS, Prec_Decl);
661 }
662 }
663
664 void printSFunction(const SFunction *E, StreamType &SS) {
665 SS << "@";
666 self()->printVariable(E->variableDecl(), SS, true);
667 SS << " ";
668 self()->printSExpr(E->body(), SS, Prec_Decl);
669 }
670
671 void printCode(const Code *E, StreamType &SS) {
672 SS << ": ";
673 self()->printSExpr(E->returnType(), SS, Prec_Decl-1);
674 SS << " -> ";
675 self()->printSExpr(E->body(), SS, Prec_Decl);
676 }
677
678 void printField(const Field *E, StreamType &SS) {
679 SS << ": ";
680 self()->printSExpr(E->range(), SS, Prec_Decl-1);
681 SS << " = ";
682 self()->printSExpr(E->body(), SS, Prec_Decl);
683 }
684
685 void printApply(const Apply *E, StreamType &SS, bool sugared = false) {
686 const SExpr *F = E->fun();
687 if (F->opcode() == COP_Apply) {
688 printApply(cast<Apply>(F), SS, true);
689 SS << ", ";
690 } else {
691 self()->printSExpr(F, SS, Prec_Postfix);
692 SS << "(";
693 }
694 self()->printSExpr(E->arg(), SS, Prec_MAX);
695 if (!sugared)
696 SS << ")$";
697 }
698
699 void printSApply(const SApply *E, StreamType &SS) {
700 self()->printSExpr(E->sfun(), SS, Prec_Postfix);
701 if (E->isDelegation()) {
702 SS << "@(";
703 self()->printSExpr(E->arg(), SS, Prec_MAX);
704 SS << ")";
705 }
706 }
707
708 void printProject(const Project *E, StreamType &SS) {
709 if (CStyle) {
710 // Omit the this->
711 if (const auto *SAP = dyn_cast<SApply>(E->record())) {
712 if (const auto *V = dyn_cast<Variable>(SAP->sfun())) {
713 if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) {
714 SS << E->slotName();
715 return;
716 }
717 }
718 }
719 if (isa<Wildcard>(E->record())) {
720 // handle existentials
721 SS << "&";
723 return;
724 }
725 }
726 self()->printSExpr(E->record(), SS, Prec_Postfix);
727 if (CStyle && E->isArrow())
728 SS << "->";
729 else
730 SS << ".";
731 SS << E->slotName();
732 }
733
734 void printCall(const Call *E, StreamType &SS) {
735 const SExpr *T = E->target();
736 if (T->opcode() == COP_Apply) {
737 self()->printApply(cast<Apply>(T), SS, true);
738 SS << ")";
739 }
740 else {
741 self()->printSExpr(T, SS, Prec_Postfix);
742 SS << "()";
743 }
744 }
745
746 void printAlloc(const Alloc *E, StreamType &SS) {
747 SS << "new ";
748 self()->printSExpr(E->dataType(), SS, Prec_Other-1);
749 }
750
751 void printLoad(const Load *E, StreamType &SS) {
752 self()->printSExpr(E->pointer(), SS, Prec_Postfix);
753 if (!CStyle)
754 SS << "^";
755 }
756
757 void printStore(const Store *E, StreamType &SS) {
758 self()->printSExpr(E->destination(), SS, Prec_Other-1);
759 SS << " := ";
760 self()->printSExpr(E->source(), SS, Prec_Other-1);
761 }
762
763 void printArrayIndex(const ArrayIndex *E, StreamType &SS) {
764 self()->printSExpr(E->array(), SS, Prec_Postfix);
765 SS << "[";
766 self()->printSExpr(E->index(), SS, Prec_MAX);
767 SS << "]";
768 }
769
770 void printArrayAdd(const ArrayAdd *E, StreamType &SS) {
771 self()->printSExpr(E->array(), SS, Prec_Postfix);
772 SS << " + ";
773 self()->printSExpr(E->index(), SS, Prec_Atom);
774 }
775
776 void printUnaryOp(const UnaryOp *E, StreamType &SS) {
778 self()->printSExpr(E->expr(), SS, Prec_Unary);
779 }
780
781 void printBinaryOp(const BinaryOp *E, StreamType &SS) {
782 self()->printSExpr(E->expr0(), SS, Prec_Binary-1);
783 SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " ";
784 self()->printSExpr(E->expr1(), SS, Prec_Binary-1);
785 }
786
787 void printCast(const Cast *E, StreamType &SS) {
788 if (!CStyle) {
789 SS << "cast[";
790 switch (E->castOpcode()) {
791 case CAST_none:
792 SS << "none";
793 break;
794 case CAST_extendNum:
795 SS << "extendNum";
796 break;
797 case CAST_truncNum:
798 SS << "truncNum";
799 break;
800 case CAST_toFloat:
801 SS << "toFloat";
802 break;
803 case CAST_toInt:
804 SS << "toInt";
805 break;
806 case CAST_objToPtr:
807 SS << "objToPtr";
808 break;
809 }
810 SS << "](";
811 self()->printSExpr(E->expr(), SS, Prec_Unary);
812 SS << ")";
813 return;
814 }
815 self()->printSExpr(E->expr(), SS, Prec_Unary);
816 }
817
818 void printSCFG(const SCFG *E, StreamType &SS) {
819 SS << "CFG {\n";
820 for (const auto *BBI : *E)
821 printBasicBlock(BBI, SS);
822 SS << "}";
823 newline(SS);
824 }
825
826 void printBBInstr(const SExpr *E, StreamType &SS) {
827 bool Sub = false;
828 if (E->opcode() == COP_Variable) {
829 const auto *V = cast<Variable>(E);
830 SS << "let " << V->name() << V->id() << " = ";
831 E = V->definition();
832 Sub = true;
833 }
834 else if (E->opcode() != COP_Store) {
835 SS << "let _x" << E->id() << " = ";
836 }
837 self()->printSExpr(E, SS, Prec_MAX, Sub);
838 SS << ";";
839 newline(SS);
840 }
841
842 void printBasicBlock(const BasicBlock *E, StreamType &SS) {
843 SS << "BB_" << E->blockID() << ":";
844 if (E->parent())
845 SS << " BB_" << E->parent()->blockID();
846 newline(SS);
847
848 for (const auto *A : E->arguments())
849 printBBInstr(A, SS);
850
851 for (const auto *I : E->instructions())
852 printBBInstr(I, SS);
853
854 const SExpr *T = E->terminator();
855 if (T) {
856 self()->printSExpr(T, SS, Prec_MAX, false);
857 SS << ";";
858 newline(SS);
859 }
860 newline(SS);
861 }
862
863 void printPhi(const Phi *E, StreamType &SS) {
864 SS << "phi(";
865 if (E->status() == Phi::PH_SingleVal)
866 self()->printSExpr(E->values()[0], SS, Prec_MAX);
867 else {
868 unsigned i = 0;
869 for (const auto *V : E->values()) {
870 if (i++ > 0)
871 SS << ", ";
872 self()->printSExpr(V, SS, Prec_MAX);
873 }
874 }
875 SS << ")";
876 }
877
878 void printGoto(const Goto *E, StreamType &SS) {
879 SS << "goto ";
880 printBlockLabel(SS, E->targetBlock(), E->index());
881 }
882
883 void printBranch(const Branch *E, StreamType &SS) {
884 SS << "branch (";
885 self()->printSExpr(E->condition(), SS, Prec_MAX);
886 SS << ") ";
887 printBlockLabel(SS, E->thenBlock(), -1);
888 SS << " ";
889 printBlockLabel(SS, E->elseBlock(), -1);
890 }
891
892 void printReturn(const Return *E, StreamType &SS) {
893 SS << "return ";
894 self()->printSExpr(E->returnValue(), SS, Prec_Other);
895 }
896
897 void printIdentifier(const Identifier *E, StreamType &SS) {
898 SS << E->name();
899 }
900
901 void printIfThenElse(const IfThenElse *E, StreamType &SS) {
902 if (CStyle) {
904 SS << " ? ";
905 printSExpr(E->thenExpr(), SS, Prec_Unary);
906 SS << " : ";
907 printSExpr(E->elseExpr(), SS, Prec_Unary);
908 return;
909 }
910 SS << "if (";
911 printSExpr(E->condition(), SS, Prec_MAX);
912 SS << ") then ";
913 printSExpr(E->thenExpr(), SS, Prec_Other);
914 SS << " else ";
915 printSExpr(E->elseExpr(), SS, Prec_Other);
916 }
917
918 void printLet(const Let *E, StreamType &SS) {
919 SS << "let ";
920 printVariable(E->variableDecl(), SS, true);
921 SS << " = ";
923 SS << "; ";
924 printSExpr(E->body(), SS, Prec_Decl-1);
925 }
926};
927
928class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> {};
929
930} // namespace til
931} // namespace threadSafety
932} // namespace clang
933
934#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H
#define V(N, I)
Definition: ASTContext.h:3217
StringRef P
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
__device__ __2f16 float bool s
This represents a decl that may have a name.
Definition: Decl.h:247
std::string getQualifiedNameAsString() const
Definition: Decl.cpp:1646
Allocate memory for a new value on the heap or stack.
Apply an argument to a function.
Pointer arithmetic, restricted to arrays only.
If p is a reference to an array, then p[i] is a reference to the i'th element of the array.
A basic block is part of an SCFG.
int blockID() const
Returns the block ID. Every block has a unique ID in the CFG.
const InstrArray & arguments() const
const Terminator * terminator() const
const BasicBlock * parent() const
Simple arithmetic binary operations, e.g.
TIL_BinaryOpcode binaryOpcode() const
A conditional branch to two other blocks.
const BasicBlock * elseBlock() const
const BasicBlock * thenBlock() const
Call a function (after all arguments have been applied).
TIL_CastOpcode castOpcode() const
A block of code – e.g. the body of a function.
bool compareByCase(const SExpr *E1, const SExpr *E2)
bool compare(const SExpr *E1, const SExpr *E2)
bool comparePointers(const void *P, const void *Q)
bool compareStrings(StringRef s, StringRef r)
void enterScope(const Variable *V1, const Variable *V2)
bool compareVariableRefs(const Variable *V1, const Variable *V2)
static bool compareExprs(const SExpr *E1, const SExpr *E2)
A typed, writable location in memory.
Placeholder for an expression that has not yet been created.
Jump to another basic block.
unsigned index() const
Returns the index into the.
const BasicBlock * targetBlock() const
An if-then-else expression.
A let-expression, e.g.
A Literal pointer to an object allocated in memory.
const ValueDecl * clangDecl() const
const LiteralT< T > & as() const
Load a value from memory.
bool compareVariableRefs(const Variable *V1, const Variable *V2)
bool comparePointers(const void *P, const void *Q)
static bool compareExprs(const SExpr *E1, const SExpr *E2)
bool compare(const SExpr *E1, const SExpr *E2)
bool compareIntegers(unsigned i, unsigned j)
bool compareStrings(StringRef s, StringRef r)
void enterScope(const Variable *V1, const Variable *V2)
Phi Node, for code in SSA form.
const ValArray & values() const
void printFuture(const Future *E, StreamType &SS)
void printCall(const Call *E, StreamType &SS)
void printLiteralT(const LiteralT< uint8_t > *E, StreamType &SS)
void printApply(const Apply *E, StreamType &SS, bool sugared=false)
void printProject(const Project *E, StreamType &SS)
void printWildcard(const Wildcard *E, StreamType &SS)
void printBranch(const Branch *E, StreamType &SS)
void printLet(const Let *E, StreamType &SS)
void printLiteral(const Literal *E, StreamType &SS)
void printField(const Field *E, StreamType &SS)
void printUnaryOp(const UnaryOp *E, StreamType &SS)
void printUndefined(const Undefined *E, StreamType &SS)
void printIdentifier(const Identifier *E, StreamType &SS)
static void print(const SExpr *E, StreamType &SS)
void printReturn(const Return *E, StreamType &SS)
void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false)
void printCode(const Code *E, StreamType &SS)
void printStore(const Store *E, StreamType &SS)
void printCast(const Cast *E, StreamType &SS)
void printIfThenElse(const IfThenElse *E, StreamType &SS)
void printBasicBlock(const BasicBlock *E, StreamType &SS)
void printLiteralPtr(const LiteralPtr *E, StreamType &SS)
void printGoto(const Goto *E, StreamType &SS)
void printBBInstr(const SExpr *E, StreamType &SS)
void printAlloc(const Alloc *E, StreamType &SS)
void printPhi(const Phi *E, StreamType &SS)
void printSCFG(const SCFG *E, StreamType &SS)
void printFunction(const Function *E, StreamType &SS, unsigned sugared=0)
void printBinaryOp(const BinaryOp *E, StreamType &SS)
void printArrayAdd(const ArrayAdd *E, StreamType &SS)
void printSFunction(const SFunction *E, StreamType &SS)
void printArrayIndex(const ArrayIndex *E, StreamType &SS)
void printSApply(const SApply *E, StreamType &SS)
void printLoad(const Load *E, StreamType &SS)
void printLiteralT(const LiteralT< T > *E, StreamType &SS)
PrettyPrinter(bool V=false, bool C=true, bool CS=true)
void printBlockLabel(StreamType &SS, const BasicBlock *BB, int index)
void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true)
Project a named slot from a C++ struct or class.
const ValueDecl * clangDecl() const
Return from the enclosing function, passing the return value to the caller.
Apply a self-argument to a self-applicable function.
An SCFG is a control-flow graph.
Base class for AST nodes in the typed intermediate language.
BasicBlock * block() const
Returns the block, if this is an instruction in a basic block, otherwise returns null.
unsigned id() const
Returns the instruction ID for this expression.
A self-applicable function.
Store a value to memory.
R::R_SExpr traverse(T *&E, typename R::R_Ctx Ctx)
R::R_SExpr traverseSExpr(SExpr *E, typename R::R_Ctx Ctx)
R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx)
Simple arithmetic unary operations, e.g.
TIL_UnaryOpcode unaryOpcode() const
Placeholder for expressions that cannot be represented in the TIL.
SExpr * definition()
Return the definition of the variable.
@ VK_SFun
SFunction (self) parameter.
Variable * enterScope(Variable &Orig, R_SExpr E0)
R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceProject(Project &Orig, R_SExpr E0)
R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B)
R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0)
R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0)
R_SExpr reduceSCFG(SCFG &Orig, Container< BasicBlock * > Bbs)
R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1)
R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container< R_SExpr > &As, Container< R_SExpr > &Is, R_SExpr T)
BasicBlock * reduceBasicBlockRef(BasicBlock *Obb)
R_SExpr reduceGoto(Goto &Orig, BasicBlock *B)
bool traverse(SExpr *E, TraversalKind K=TRV_Normal)
R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reducePhi(Phi &Orig, Container< R_SExpr > &As)
R_SExpr reduceLoad(Load &Orig, R_SExpr E0)
R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0)
R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0)
R_SExpr reduceLiteralT(LiteralT< T > &Orig)
R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1)
R_SExpr reduceReturn(Return &O, R_SExpr E)
R_SExpr reduceCast(Cast &Orig, R_SExpr E0)
R_SExpr reduceCall(Call &Orig, R_SExpr E0)
R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1)
R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E)
Placeholder for a wildcard that matches any other expression.
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)
Return the name of a binary opcode.
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)
Return the name of a unary opcode.
std::string getSourceLiteralString(const Expr *CE)
@ C
Languages that the frontend can parse and compile.
#define bool
Definition: stdbool.h:20
ValueTypes are data types that can actually be held in registers.