/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h
Line | Count | Source (jump to first uncovered line) |
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 | 0 | 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 | 0 | 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 | 0 | R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; } |
132 | | |
133 | | // Create context for a subexpression that occurs in a type position. |
134 | 0 | 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 | 0 | 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 | 49.5k | Self *self() { return reinterpret_cast<Self *>(this); } clang::threadSafety::til::Comparator<clang::threadSafety::til::EqualsComparator>::self() Line | Count | Source | 312 | 4.12k | Self *self() { return reinterpret_cast<Self *>(this); } |
clang::threadSafety::til::Comparator<clang::threadSafety::til::MatchComparator>::self() Line | Count | Source | 312 | 45.4k | Self *self() { return reinterpret_cast<Self *>(this); } |
|
313 | | |
314 | | public: |
315 | 49.5k | bool compareByCase(const SExpr *E1, const SExpr* E2) { |
316 | 49.5k | switch (E1->opcode()) { |
317 | 0 | #define TIL_OPCODE_DEF(X) \ |
318 | 49.5k | case COP_##X: \ |
319 | 49.5k | return cast<X>(E1)->compare(cast<X>(E2), *self()); |
320 | 49.5k | #include "ThreadSafetyOps.def"0 |
321 | 49.5k | #undef TIL_OPCODE_DEF |
322 | 49.5k | } |
323 | 0 | return false; |
324 | 49.5k | } clang::threadSafety::til::Comparator<clang::threadSafety::til::EqualsComparator>::compareByCase(clang::threadSafety::til::SExpr const*, clang::threadSafety::til::SExpr const*) Line | Count | Source | 315 | 4.12k | bool compareByCase(const SExpr *E1, const SExpr* E2) { | 316 | 4.12k | switch (E1->opcode()) { | 317 | 0 | #define TIL_OPCODE_DEF(X) \ | 318 | 0 | case COP_##X: \ | 319 | 0 | return cast<X>(E1)->compare(cast<X>(E2), *self()); | 320 | 4.12k | #include "ThreadSafetyOps.def"0 | 321 | 4.12k | #undef TIL_OPCODE_DEF | 322 | 4.12k | } | 323 | 0 | return false; | 324 | 4.12k | } |
clang::threadSafety::til::Comparator<clang::threadSafety::til::MatchComparator>::compareByCase(clang::threadSafety::til::SExpr const*, clang::threadSafety::til::SExpr const*) Line | Count | Source | 315 | 45.4k | bool compareByCase(const SExpr *E1, const SExpr* E2) { | 316 | 45.4k | switch (E1->opcode()) { | 317 | 0 | #define TIL_OPCODE_DEF(X) \ | 318 | 0 | case COP_##X: \ | 319 | 0 | return cast<X>(E1)->compare(cast<X>(E2), *self()); | 320 | 45.4k | #include "ThreadSafetyOps.def"0 | 321 | 45.4k | #undef TIL_OPCODE_DEF | 322 | 45.4k | } | 323 | 0 | return false; | 324 | 45.4k | } |
|
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 | 0 | CType trueResult() { return true; } |
335 | 2.06k | bool notTrue(CType ct) { return !ct; } |
336 | | |
337 | 0 | bool compareIntegers(unsigned i, unsigned j) { return i == j; } |
338 | 0 | bool compareStrings (StringRef s, StringRef r) { return s == r; } |
339 | 2.24k | bool comparePointers(const void* P, const void* Q) { return P == Q; } |
340 | | |
341 | 4.17k | bool compare(const SExpr *E1, const SExpr* E2) { |
342 | 4.17k | if (E1->opcode() != E2->opcode()) |
343 | 48 | return false; |
344 | 4.12k | return compareByCase(E1, E2); |
345 | 4.17k | } |
346 | | |
347 | | // TODO -- handle alpha-renaming of variables |
348 | 0 | void enterScope(const Variable *V1, const Variable *V2) {} |
349 | 0 | void leaveScope() {} |
350 | | |
351 | 832 | bool compareVariableRefs(const Variable *V1, const Variable *V2) { |
352 | 832 | return V1 == V2; |
353 | 832 | } |
354 | | |
355 | 1.09k | static bool compareExprs(const SExpr *E1, const SExpr* E2) { |
356 | 1.09k | EqualsComparator Eq; |
357 | 1.09k | return Eq.compare(E1, E2); |
358 | 1.09k | } |
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 | 392 | CType trueResult() { return true; } |
369 | 21.7k | bool notTrue(CType ct) { return !ct; } |
370 | | |
371 | 572 | bool compareIntegers(unsigned i, unsigned j) { return i == j; } |
372 | 0 | bool compareStrings (StringRef s, StringRef r) { return s == r; } |
373 | 19.8k | bool comparePointers(const void *P, const void *Q) { return P == Q; } |
374 | | |
375 | 47.2k | bool compare(const SExpr *E1, const SExpr *E2) { |
376 | | // Wildcards match anything. |
377 | 47.2k | if (E1->opcode() == COP_Wildcard || E2->opcode() == COP_Wildcard47.1k ) |
378 | 144 | return true; |
379 | | // otherwise normal equality. |
380 | 47.1k | if (E1->opcode() != E2->opcode()) |
381 | 1.66k | return false; |
382 | 45.4k | return compareByCase(E1, E2); |
383 | 47.1k | } |
384 | | |
385 | | // TODO -- handle alpha-renaming of variables |
386 | 0 | void enterScope(const Variable* V1, const Variable* V2) {} |
387 | 0 | void leaveScope() {} |
388 | | |
389 | 10.9k | bool compareVariableRefs(const Variable* V1, const Variable* V2) { |
390 | 10.9k | return V1 == V2; |
391 | 10.9k | } |
392 | | |
393 | 14.2k | static bool compareExprs(const SExpr *E1, const SExpr* E2) { |
394 | 14.2k | MatchComparator Matcher; |
395 | 14.2k | return Matcher.compare(E1, E2); |
396 | 14.2k | } |
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 | 4.10k | : Verbose(V), Cleanup(C), CStyle(CS) {} |
419 | | |
420 | 4.10k | static void print(const SExpr *E, StreamType &SS) { |
421 | 4.10k | Self printer; |
422 | 4.10k | printer.printSExpr(E, SS, Prec_MAX); |
423 | 4.10k | } |
424 | | |
425 | | protected: |
426 | 11.8k | Self *self() { return reinterpret_cast<Self *>(this); } |
427 | | |
428 | 0 | void newline(StreamType &SS) { |
429 | 0 | SS << "\n"; |
430 | 0 | } |
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 | 5.33k | unsigned precedence(const SExpr *E) { |
443 | 5.33k | switch (E->opcode()) { |
444 | 0 | case COP_Future: return Prec_Atom; |
445 | 0 | case COP_Undefined: return Prec_Atom; |
446 | 4 | case COP_Wildcard: return Prec_Atom; |
447 | | |
448 | 12 | case COP_Literal: return Prec_Atom; |
449 | 1.88k | case COP_LiteralPtr: return Prec_Atom; |
450 | 4 | case COP_Variable: return Prec_Atom; |
451 | 0 | case COP_Function: return Prec_Decl; |
452 | 0 | case COP_SFunction: return Prec_Decl; |
453 | 0 | case COP_Code: return Prec_Decl; |
454 | 0 | case COP_Field: return Prec_Decl; |
455 | | |
456 | 0 | case COP_Apply: return Prec_Postfix; |
457 | 518 | case COP_SApply: return Prec_Postfix; |
458 | 2.79k | case COP_Project: return Prec_Postfix; |
459 | | |
460 | 36 | case COP_Call: return Prec_Postfix; |
461 | 0 | case COP_Alloc: return Prec_Other; |
462 | 0 | case COP_Load: return Prec_Postfix; |
463 | 0 | case COP_Store: return Prec_Other; |
464 | 16 | case COP_ArrayIndex: return Prec_Postfix; |
465 | 0 | case COP_ArrayAdd: return Prec_Postfix; |
466 | | |
467 | 0 | case COP_UnaryOp: return Prec_Unary; |
468 | 16 | case COP_BinaryOp: return Prec_Binary; |
469 | 24 | case COP_Cast: return Prec_Atom; |
470 | | |
471 | 0 | case COP_SCFG: return Prec_Decl; |
472 | 0 | case COP_BasicBlock: return Prec_MAX; |
473 | 0 | case COP_Phi: return Prec_Atom; |
474 | 0 | case COP_Goto: return Prec_Atom; |
475 | 0 | case COP_Branch: return Prec_Atom; |
476 | 0 | case COP_Return: return Prec_Other; |
477 | | |
478 | 0 | case COP_Identifier: return Prec_Atom; |
479 | 16 | case COP_IfThenElse: return Prec_Other; |
480 | 0 | case COP_Let: return Prec_Decl; |
481 | 5.33k | } |
482 | 0 | return Prec_MAX; |
483 | 5.33k | } |
484 | | |
485 | 0 | void printBlockLabel(StreamType & SS, const BasicBlock *BB, int index) { |
486 | 0 | if (!BB) { |
487 | 0 | SS << "BB_null"; |
488 | 0 | return; |
489 | 0 | } |
490 | 0 | SS << "BB_"; |
491 | 0 | SS << BB->blockID(); |
492 | 0 | if (index >= 0) { |
493 | 0 | SS << ":"; |
494 | 0 | SS << index; |
495 | 0 | } |
496 | 0 | } |
497 | | |
498 | 5.33k | void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true) { |
499 | 5.33k | if (!E) { |
500 | 0 | self()->printNull(SS); |
501 | 0 | return; |
502 | 0 | } |
503 | 5.33k | if (Sub && E->block() && E->opcode() != COP_Variable0 ) { |
504 | 0 | SS << "_x" << E->id(); |
505 | 0 | return; |
506 | 0 | } |
507 | 5.33k | if (self()->precedence(E) > P) { |
508 | | // Wrap expr in () if necessary. |
509 | 16 | SS << "("; |
510 | 16 | self()->printSExpr(E, SS, Prec_MAX); |
511 | 16 | SS << ")"; |
512 | 16 | return; |
513 | 16 | } |
514 | | |
515 | 5.31k | switch (E->opcode()) { |
516 | 0 | #define TIL_OPCODE_DEF(X) \ |
517 | 5.31k | case COP_##X: \ |
518 | 5.31k | self()->print##X(cast<X>(E), SS); \ |
519 | 5.31k | return; |
520 | 5.31k | #include "ThreadSafetyOps.def"0 |
521 | 5.31k | #undef TIL_OPCODE_DEF |
522 | 5.31k | } |
523 | 5.31k | } |
524 | | |
525 | 0 | void printNull(StreamType &SS) { |
526 | 0 | SS << "#null"; |
527 | 0 | } |
528 | | |
529 | 0 | void printFuture(const Future *E, StreamType &SS) { |
530 | 0 | self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom); |
531 | 0 | } |
532 | | |
533 | 0 | void printUndefined(const Undefined *E, StreamType &SS) { |
534 | 0 | SS << "#undefined"; |
535 | 0 | } |
536 | | |
537 | 4 | void printWildcard(const Wildcard *E, StreamType &SS) { |
538 | 4 | SS << "*"; |
539 | 4 | } |
540 | | |
541 | | template<class T> |
542 | 0 | void printLiteralT(const LiteralT<T> *E, StreamType &SS) { |
543 | 0 | SS << E->value(); |
544 | 0 | } Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<signed char>(clang::threadSafety::til::LiteralT<signed char> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<short>(clang::threadSafety::til::LiteralT<short> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<unsigned short>(clang::threadSafety::til::LiteralT<unsigned short> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<int>(clang::threadSafety::til::LiteralT<int> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<unsigned int>(clang::threadSafety::til::LiteralT<unsigned int> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<long long>(clang::threadSafety::til::LiteralT<long long> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<unsigned long long>(clang::threadSafety::til::LiteralT<unsigned long long> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<float>(clang::threadSafety::til::LiteralT<float> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<double>(clang::threadSafety::til::LiteralT<double> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) Unexecuted instantiation: void clang::threadSafety::til::PrettyPrinter<clang::threadSafety::til::StdPrinter, std::__1::basic_ostream<char, std::__1::char_traits<char> > >::printLiteralT<llvm::StringRef>(clang::threadSafety::til::LiteralT<llvm::StringRef> const*, std::__1::basic_ostream<char, std::__1::char_traits<char> >&) |
545 | | |
546 | 0 | void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) { |
547 | 0 | SS << "'" << E->value() << "'"; |
548 | 0 | } |
549 | | |
550 | 12 | void printLiteral(const Literal *E, StreamType &SS) { |
551 | 12 | if (E->clangExpr()) { |
552 | 12 | SS << getSourceLiteralString(E->clangExpr()); |
553 | 12 | return; |
554 | 12 | } |
555 | 0 | else { |
556 | 0 | ValueType VT = E->valueType(); |
557 | 0 | switch (VT.Base) { |
558 | 0 | case ValueType::BT_Void: |
559 | 0 | SS << "void"; |
560 | 0 | return; |
561 | 0 | case ValueType::BT_Bool: |
562 | 0 | if (E->as<bool>().value()) |
563 | 0 | SS << "true"; |
564 | 0 | else |
565 | 0 | SS << "false"; |
566 | 0 | return; |
567 | 0 | case ValueType::BT_Int: |
568 | 0 | switch (VT.Size) { |
569 | 0 | case ValueType::ST_8: |
570 | 0 | if (VT.Signed) |
571 | 0 | printLiteralT(&E->as<int8_t>(), SS); |
572 | 0 | else |
573 | 0 | printLiteralT(&E->as<uint8_t>(), SS); |
574 | 0 | return; |
575 | 0 | case ValueType::ST_16: |
576 | 0 | if (VT.Signed) |
577 | 0 | printLiteralT(&E->as<int16_t>(), SS); |
578 | 0 | else |
579 | 0 | printLiteralT(&E->as<uint16_t>(), SS); |
580 | 0 | return; |
581 | 0 | case ValueType::ST_32: |
582 | 0 | if (VT.Signed) |
583 | 0 | printLiteralT(&E->as<int32_t>(), SS); |
584 | 0 | else |
585 | 0 | printLiteralT(&E->as<uint32_t>(), SS); |
586 | 0 | return; |
587 | 0 | case ValueType::ST_64: |
588 | 0 | if (VT.Signed) |
589 | 0 | printLiteralT(&E->as<int64_t>(), SS); |
590 | 0 | else |
591 | 0 | printLiteralT(&E->as<uint64_t>(), SS); |
592 | 0 | return; |
593 | 0 | default: |
594 | 0 | break; |
595 | 0 | } |
596 | 0 | break; |
597 | 0 | case ValueType::BT_Float: |
598 | 0 | switch (VT.Size) { |
599 | 0 | case ValueType::ST_32: |
600 | 0 | printLiteralT(&E->as<float>(), SS); |
601 | 0 | return; |
602 | 0 | case ValueType::ST_64: |
603 | 0 | printLiteralT(&E->as<double>(), SS); |
604 | 0 | return; |
605 | 0 | default: |
606 | 0 | break; |
607 | 0 | } |
608 | 0 | break; |
609 | 0 | case ValueType::BT_String: |
610 | 0 | SS << "\""; |
611 | 0 | printLiteralT(&E->as<StringRef>(), SS); |
612 | 0 | SS << "\""; |
613 | 0 | return; |
614 | 0 | case ValueType::BT_Pointer: |
615 | 0 | SS << "#ptr"; |
616 | 0 | return; |
617 | 0 | case ValueType::BT_ValueRef: |
618 | 0 | SS << "#vref"; |
619 | 0 | return; |
620 | 0 | } |
621 | 0 | } |
622 | 0 | SS << "#lit"; |
623 | 0 | } |
624 | | |
625 | 1.88k | void printLiteralPtr(const LiteralPtr *E, StreamType &SS) { |
626 | 1.88k | SS << E->clangDecl()->getNameAsString(); |
627 | 1.88k | } |
628 | | |
629 | 4 | void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) { |
630 | 4 | if (CStyle && V->kind() == Variable::VK_SFun) |
631 | 4 | SS << "this"; |
632 | 0 | else |
633 | 0 | SS << V->name() << V->id(); |
634 | 4 | } |
635 | | |
636 | 0 | void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) { |
637 | 0 | switch (sugared) { |
638 | 0 | default: |
639 | 0 | SS << "\\("; // Lambda |
640 | 0 | break; |
641 | 0 | case 1: |
642 | 0 | SS << "("; // Slot declarations |
643 | 0 | break; |
644 | 0 | case 2: |
645 | 0 | SS << ", "; // Curried functions |
646 | 0 | break; |
647 | 0 | } |
648 | 0 | self()->printVariable(E->variableDecl(), SS, true); |
649 | 0 | SS << ": "; |
650 | 0 | self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX); |
651 | |
|
652 | 0 | const SExpr *B = E->body(); |
653 | 0 | if (B && B->opcode() == COP_Function) |
654 | 0 | self()->printFunction(cast<Function>(B), SS, 2); |
655 | 0 | else { |
656 | 0 | SS << ")"; |
657 | 0 | self()->printSExpr(B, SS, Prec_Decl); |
658 | 0 | } |
659 | 0 | } |
660 | | |
661 | 0 | void printSFunction(const SFunction *E, StreamType &SS) { |
662 | 0 | SS << "@"; |
663 | 0 | self()->printVariable(E->variableDecl(), SS, true); |
664 | 0 | SS << " "; |
665 | 0 | self()->printSExpr(E->body(), SS, Prec_Decl); |
666 | 0 | } |
667 | | |
668 | 0 | void printCode(const Code *E, StreamType &SS) { |
669 | 0 | SS << ": "; |
670 | 0 | self()->printSExpr(E->returnType(), SS, Prec_Decl-1); |
671 | 0 | SS << " -> "; |
672 | 0 | self()->printSExpr(E->body(), SS, Prec_Decl); |
673 | 0 | } |
674 | | |
675 | 0 | void printField(const Field *E, StreamType &SS) { |
676 | 0 | SS << ": "; |
677 | 0 | self()->printSExpr(E->range(), SS, Prec_Decl-1); |
678 | 0 | SS << " = "; |
679 | 0 | self()->printSExpr(E->body(), SS, Prec_Decl); |
680 | 0 | } |
681 | | |
682 | 40 | void printApply(const Apply *E, StreamType &SS, bool sugared = false) { |
683 | 40 | const SExpr *F = E->fun(); |
684 | 40 | if (F->opcode() == COP_Apply) { |
685 | 16 | printApply(cast<Apply>(F), SS, true); |
686 | 16 | SS << ", "; |
687 | 24 | } else { |
688 | 24 | self()->printSExpr(F, SS, Prec_Postfix); |
689 | 24 | SS << "("; |
690 | 24 | } |
691 | 40 | self()->printSExpr(E->arg(), SS, Prec_MAX); |
692 | 40 | if (!sugared) |
693 | 0 | SS << ")$"; |
694 | 40 | } |
695 | | |
696 | 518 | void printSApply(const SApply *E, StreamType &SS) { |
697 | 518 | self()->printSExpr(E->sfun(), SS, Prec_Postfix); |
698 | 518 | if (E->isDelegation()) { |
699 | 0 | SS << "@("; |
700 | 0 | self()->printSExpr(E->arg(), SS, Prec_MAX); |
701 | 0 | SS << ")"; |
702 | 0 | } |
703 | 518 | } |
704 | | |
705 | 2.79k | void printProject(const Project *E, StreamType &SS) { |
706 | 2.79k | if (CStyle) { |
707 | | // Omit the this-> |
708 | 2.79k | if (const auto *SAP = dyn_cast<SApply>(E->record())) { |
709 | 2.77k | if (const auto *V = dyn_cast<Variable>(SAP->sfun())) { |
710 | 2.26k | if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) { |
711 | 2.26k | SS << E->slotName(); |
712 | 2.26k | return; |
713 | 2.26k | } |
714 | 2.26k | } |
715 | 2.77k | } |
716 | 538 | if (isa<Wildcard>(E->record())) { |
717 | | // handle existentials |
718 | 20 | SS << "&"; |
719 | 20 | SS << E->clangDecl()->getQualifiedNameAsString(); |
720 | 20 | return; |
721 | 20 | } |
722 | 538 | } |
723 | 518 | self()->printSExpr(E->record(), SS, Prec_Postfix); |
724 | 518 | if (CStyle && E->isArrow()) |
725 | 193 | SS << "->"; |
726 | 325 | else |
727 | 325 | SS << "."; |
728 | 518 | SS << E->slotName(); |
729 | 518 | } |
730 | | |
731 | 36 | void printCall(const Call *E, StreamType &SS) { |
732 | 36 | const SExpr *T = E->target(); |
733 | 36 | if (T->opcode() == COP_Apply) { |
734 | 24 | self()->printApply(cast<Apply>(T), SS, true); |
735 | 24 | SS << ")"; |
736 | 24 | } |
737 | 12 | else { |
738 | 12 | self()->printSExpr(T, SS, Prec_Postfix); |
739 | 12 | SS << "()"; |
740 | 12 | } |
741 | 36 | } |
742 | | |
743 | 0 | void printAlloc(const Alloc *E, StreamType &SS) { |
744 | 0 | SS << "new "; |
745 | 0 | self()->printSExpr(E->dataType(), SS, Prec_Other-1); |
746 | 0 | } |
747 | | |
748 | 0 | void printLoad(const Load *E, StreamType &SS) { |
749 | 0 | self()->printSExpr(E->pointer(), SS, Prec_Postfix); |
750 | 0 | if (!CStyle) |
751 | 0 | SS << "^"; |
752 | 0 | } |
753 | | |
754 | 0 | void printStore(const Store *E, StreamType &SS) { |
755 | 0 | self()->printSExpr(E->destination(), SS, Prec_Other-1); |
756 | 0 | SS << " := "; |
757 | 0 | self()->printSExpr(E->source(), SS, Prec_Other-1); |
758 | 0 | } |
759 | | |
760 | 16 | void printArrayIndex(const ArrayIndex *E, StreamType &SS) { |
761 | 16 | self()->printSExpr(E->array(), SS, Prec_Postfix); |
762 | 16 | SS << "["; |
763 | 16 | self()->printSExpr(E->index(), SS, Prec_MAX); |
764 | 16 | SS << "]"; |
765 | 16 | } |
766 | | |
767 | 0 | void printArrayAdd(const ArrayAdd *E, StreamType &SS) { |
768 | 0 | self()->printSExpr(E->array(), SS, Prec_Postfix); |
769 | 0 | SS << " + "; |
770 | 0 | self()->printSExpr(E->index(), SS, Prec_Atom); |
771 | 0 | } |
772 | | |
773 | 0 | void printUnaryOp(const UnaryOp *E, StreamType &SS) { |
774 | 0 | SS << getUnaryOpcodeString(E->unaryOpcode()); |
775 | 0 | self()->printSExpr(E->expr(), SS, Prec_Unary); |
776 | 0 | } |
777 | | |
778 | 8 | void printBinaryOp(const BinaryOp *E, StreamType &SS) { |
779 | 8 | self()->printSExpr(E->expr0(), SS, Prec_Binary-1); |
780 | 8 | SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " "; |
781 | 8 | self()->printSExpr(E->expr1(), SS, Prec_Binary-1); |
782 | 8 | } |
783 | | |
784 | 24 | void printCast(const Cast *E, StreamType &SS) { |
785 | 24 | if (!CStyle) { |
786 | 0 | SS << "cast["; |
787 | 0 | switch (E->castOpcode()) { |
788 | 0 | case CAST_none: |
789 | 0 | SS << "none"; |
790 | 0 | break; |
791 | 0 | case CAST_extendNum: |
792 | 0 | SS << "extendNum"; |
793 | 0 | break; |
794 | 0 | case CAST_truncNum: |
795 | 0 | SS << "truncNum"; |
796 | 0 | break; |
797 | 0 | case CAST_toFloat: |
798 | 0 | SS << "toFloat"; |
799 | 0 | break; |
800 | 0 | case CAST_toInt: |
801 | 0 | SS << "toInt"; |
802 | 0 | break; |
803 | 0 | case CAST_objToPtr: |
804 | 0 | SS << "objToPtr"; |
805 | 0 | break; |
806 | 0 | } |
807 | 0 | SS << "]("; |
808 | 0 | self()->printSExpr(E->expr(), SS, Prec_Unary); |
809 | 0 | SS << ")"; |
810 | 0 | return; |
811 | 0 | } |
812 | 24 | self()->printSExpr(E->expr(), SS, Prec_Unary); |
813 | 24 | } |
814 | | |
815 | 0 | void printSCFG(const SCFG *E, StreamType &SS) { |
816 | 0 | SS << "CFG {\n"; |
817 | 0 | for (const auto *BBI : *E) |
818 | 0 | printBasicBlock(BBI, SS); |
819 | 0 | SS << "}"; |
820 | 0 | newline(SS); |
821 | 0 | } |
822 | | |
823 | 0 | void printBBInstr(const SExpr *E, StreamType &SS) { |
824 | 0 | bool Sub = false; |
825 | 0 | if (E->opcode() == COP_Variable) { |
826 | 0 | const auto *V = cast<Variable>(E); |
827 | 0 | SS << "let " << V->name() << V->id() << " = "; |
828 | 0 | E = V->definition(); |
829 | 0 | Sub = true; |
830 | 0 | } |
831 | 0 | else if (E->opcode() != COP_Store) { |
832 | 0 | SS << "let _x" << E->id() << " = "; |
833 | 0 | } |
834 | 0 | self()->printSExpr(E, SS, Prec_MAX, Sub); |
835 | 0 | SS << ";"; |
836 | 0 | newline(SS); |
837 | 0 | } |
838 | | |
839 | 0 | void printBasicBlock(const BasicBlock *E, StreamType &SS) { |
840 | 0 | SS << "BB_" << E->blockID() << ":"; |
841 | 0 | if (E->parent()) |
842 | 0 | SS << " BB_" << E->parent()->blockID(); |
843 | 0 | newline(SS); |
844 | |
|
845 | 0 | for (const auto *A : E->arguments()) |
846 | 0 | printBBInstr(A, SS); |
847 | |
|
848 | 0 | for (const auto *I : E->instructions()) |
849 | 0 | printBBInstr(I, SS); |
850 | |
|
851 | 0 | const SExpr *T = E->terminator(); |
852 | 0 | if (T) { |
853 | 0 | self()->printSExpr(T, SS, Prec_MAX, false); |
854 | 0 | SS << ";"; |
855 | 0 | newline(SS); |
856 | 0 | } |
857 | 0 | newline(SS); |
858 | 0 | } |
859 | | |
860 | 0 | void printPhi(const Phi *E, StreamType &SS) { |
861 | 0 | SS << "phi("; |
862 | 0 | if (E->status() == Phi::PH_SingleVal) |
863 | 0 | self()->printSExpr(E->values()[0], SS, Prec_MAX); |
864 | 0 | else { |
865 | 0 | unsigned i = 0; |
866 | 0 | for (const auto *V : E->values()) { |
867 | 0 | if (i++ > 0) |
868 | 0 | SS << ", "; |
869 | 0 | self()->printSExpr(V, SS, Prec_MAX); |
870 | 0 | } |
871 | 0 | } |
872 | 0 | SS << ")"; |
873 | 0 | } |
874 | | |
875 | 0 | void printGoto(const Goto *E, StreamType &SS) { |
876 | 0 | SS << "goto "; |
877 | 0 | printBlockLabel(SS, E->targetBlock(), E->index()); |
878 | 0 | } |
879 | | |
880 | 0 | void printBranch(const Branch *E, StreamType &SS) { |
881 | 0 | SS << "branch ("; |
882 | 0 | self()->printSExpr(E->condition(), SS, Prec_MAX); |
883 | 0 | SS << ") "; |
884 | 0 | printBlockLabel(SS, E->thenBlock(), -1); |
885 | 0 | SS << " "; |
886 | 0 | printBlockLabel(SS, E->elseBlock(), -1); |
887 | 0 | } |
888 | | |
889 | 0 | void printReturn(const Return *E, StreamType &SS) { |
890 | 0 | SS << "return "; |
891 | 0 | self()->printSExpr(E->returnValue(), SS, Prec_Other); |
892 | 0 | } |
893 | | |
894 | 0 | void printIdentifier(const Identifier *E, StreamType &SS) { |
895 | 0 | SS << E->name(); |
896 | 0 | } |
897 | | |
898 | 8 | void printIfThenElse(const IfThenElse *E, StreamType &SS) { |
899 | 8 | if (CStyle) { |
900 | 8 | printSExpr(E->condition(), SS, Prec_Unary); |
901 | 8 | SS << " ? "; |
902 | 8 | printSExpr(E->thenExpr(), SS, Prec_Unary); |
903 | 8 | SS << " : "; |
904 | 8 | printSExpr(E->elseExpr(), SS, Prec_Unary); |
905 | 8 | return; |
906 | 8 | } |
907 | 0 | SS << "if ("; |
908 | 0 | printSExpr(E->condition(), SS, Prec_MAX); |
909 | 0 | SS << ") then "; |
910 | 0 | printSExpr(E->thenExpr(), SS, Prec_Other); |
911 | 0 | SS << " else "; |
912 | 0 | printSExpr(E->elseExpr(), SS, Prec_Other); |
913 | 0 | } |
914 | | |
915 | 0 | void printLet(const Let *E, StreamType &SS) { |
916 | 0 | SS << "let "; |
917 | 0 | printVariable(E->variableDecl(), SS, true); |
918 | 0 | SS << " = "; |
919 | 0 | printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1); |
920 | 0 | SS << "; "; |
921 | 0 | printSExpr(E->body(), SS, Prec_Decl-1); |
922 | 0 | } |
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 |