Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
14 | pmbaty | 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" |
||
20 | #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" |
||
21 | #include "clang/Analysis/Analyses/ThreadSafetyUtil.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. |
||
101 | class SimpleReducerBase { |
||
102 | public: |
||
103 | enum TraversalKind { |
||
104 | // Ordinary subexpressions. |
||
105 | TRV_Normal, |
||
106 | |||
107 | // Declarations (e.g. function bodies). |
||
108 | TRV_Decl, |
||
109 | |||
110 | // Expressions that require lazy evaluation. |
||
111 | TRV_Lazy, |
||
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. |
||
120 | using R_Ctx = TraversalKind; |
||
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. |
||
138 | class CopyReducerBase : public SimpleReducerBase { |
||
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 *; |
||
143 | using R_BasicBlock = BasicBlock *; |
||
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 | |||
155 | SimpleArray<T> Elems; |
||
156 | }; |
||
157 | |||
158 | CopyReducerBase(MemRegionRef A) : Arena(A) {} |
||
159 | |||
160 | protected: |
||
161 | MemRegionRef Arena; |
||
162 | }; |
||
163 | |||
164 | // Base class for visit traversals. |
||
165 | class VisitReducerBase : public SimpleReducerBase { |
||
166 | public: |
||
167 | // A visitor returns a bool, representing success or failure. |
||
168 | using R_SExpr = bool; |
||
169 | using R_BasicBlock = 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 | |||
200 | R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { |
||
201 | return Nvd && E0; |
||
202 | } |
||
203 | |||
204 | R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) { |
||
205 | return Nvd && E0; |
||
206 | } |
||
207 | |||
208 | R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) { |
||
209 | return E0 && E1; |
||
210 | } |
||
211 | |||
212 | R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) { |
||
213 | return E0 && E1; |
||
214 | } |
||
215 | |||
216 | R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) { |
||
217 | return E0 && E1; |
||
218 | } |
||
219 | |||
220 | R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) { |
||
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 | |||
230 | R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) { |
||
231 | return E0 && E1; |
||
232 | } |
||
233 | |||
234 | R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) { |
||
235 | return E0 && E1; |
||
236 | } |
||
237 | |||
238 | R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; } |
||
239 | |||
240 | R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) { |
||
241 | return E0 && E1; |
||
242 | } |
||
243 | |||
244 | R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; } |
||
245 | |||
246 | R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { |
||
247 | return Bbs.Success; |
||
248 | } |
||
249 | |||
250 | R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<R_SExpr> &As, |
||
251 | Container<R_SExpr> &Is, R_SExpr T) { |
||
252 | return (As.Success && Is.Success && T); |
||
253 | } |
||
254 | |||
255 | R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) { |
||
256 | return As.Success; |
||
257 | } |
||
258 | |||
259 | R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { |
||
260 | return true; |
||
261 | } |
||
262 | |||
263 | R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { |
||
264 | return C; |
||
265 | } |
||
266 | |||
267 | R_SExpr reduceReturn(Return &O, R_SExpr E) { |
||
268 | return E; |
||
269 | } |
||
270 | |||
271 | R_SExpr reduceIdentifier(Identifier &Orig) { |
||
272 | return true; |
||
273 | } |
||
274 | |||
275 | R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) { |
||
276 | return C && T && E; |
||
277 | } |
||
278 | |||
279 | R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) { |
||
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) {} |
||
287 | void enterBasicBlock(BasicBlock &BB) {} |
||
288 | void exitBasicBlock(BasicBlock &BB) {} |
||
289 | |||
290 | Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } |
||
291 | BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } |
||
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> |
||
405 | class PrettyPrinter { |
||
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; |
||
609 | case ValueType::BT_String: |
||
610 | SS << "\""; |
||
611 | printLiteralT(&E->as<StringRef>(), SS); |
||
612 | SS << "\""; |
||
613 | return; |
||
614 | case ValueType::BT_Pointer: |
||
615 | SS << "#ptr"; |
||
616 | return; |
||
617 | case ValueType::BT_ValueRef: |
||
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 << "&"; |
||
722 | SS << E->clangDecl()->getQualifiedNameAsString(); |
||
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) { |
||
777 | SS << getUnaryOpcodeString(E->unaryOpcode()); |
||
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) { |
||
903 | printSExpr(E->condition(), SS, Prec_Unary); |
||
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 << " = "; |
||
922 | printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1); |
||
923 | SS << "; "; |
||
924 | printSExpr(E->body(), SS, Prec_Decl-1); |
||
925 | } |
||
926 | }; |
||
927 | |||
928 | class 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 |