/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- ThreadSafetyTIL.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 simple Typed Intermediate Language, or TIL, that is used |
10 | | // by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended |
11 | | // to be largely independent of clang, in the hope that the analysis can be |
12 | | // reused for other non-C++ languages. All dependencies on clang/llvm should |
13 | | // go in ThreadSafetyUtil.h. |
14 | | // |
15 | | // Thread safety analysis works by comparing mutex expressions, e.g. |
16 | | // |
17 | | // class A { Mutex mu; int dat GUARDED_BY(this->mu); } |
18 | | // class B { A a; } |
19 | | // |
20 | | // void foo(B* b) { |
21 | | // (*b).a.mu.lock(); // locks (*b).a.mu |
22 | | // b->a.dat = 0; // substitute &b->a for 'this'; |
23 | | // // requires lock on (&b->a)->mu |
24 | | // (b->a.mu).unlock(); // unlocks (b->a.mu) |
25 | | // } |
26 | | // |
27 | | // As illustrated by the above example, clang Exprs are not well-suited to |
28 | | // represent mutex expressions directly, since there is no easy way to compare |
29 | | // Exprs for equivalence. The thread safety analysis thus lowers clang Exprs |
30 | | // into a simple intermediate language (IL). The IL supports: |
31 | | // |
32 | | // (1) comparisons for semantic equality of expressions |
33 | | // (2) SSA renaming of variables |
34 | | // (3) wildcards and pattern matching over expressions |
35 | | // (4) hash-based expression lookup |
36 | | // |
37 | | // The TIL is currently very experimental, is intended only for use within |
38 | | // the thread safety analysis, and is subject to change without notice. |
39 | | // After the API stabilizes and matures, it may be appropriate to make this |
40 | | // more generally available to other analyses. |
41 | | // |
42 | | // UNDER CONSTRUCTION. USE AT YOUR OWN RISK. |
43 | | // |
44 | | //===----------------------------------------------------------------------===// |
45 | | |
46 | | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H |
47 | | #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H |
48 | | |
49 | | #include "clang/AST/Decl.h" |
50 | | #include "clang/Analysis/Analyses/ThreadSafetyUtil.h" |
51 | | #include "clang/Basic/LLVM.h" |
52 | | #include "llvm/ADT/ArrayRef.h" |
53 | | #include "llvm/ADT/None.h" |
54 | | #include "llvm/ADT/Optional.h" |
55 | | #include "llvm/ADT/StringRef.h" |
56 | | #include "llvm/Support/Casting.h" |
57 | | #include "llvm/Support/raw_ostream.h" |
58 | | #include <algorithm> |
59 | | #include <cassert> |
60 | | #include <cstddef> |
61 | | #include <cstdint> |
62 | | #include <iterator> |
63 | | #include <string> |
64 | | #include <utility> |
65 | | |
66 | | namespace clang { |
67 | | |
68 | | class CallExpr; |
69 | | class Expr; |
70 | | class Stmt; |
71 | | |
72 | | namespace threadSafety { |
73 | | namespace til { |
74 | | |
75 | | class BasicBlock; |
76 | | |
77 | | /// Enum for the different distinct classes of SExpr |
78 | | enum TIL_Opcode { |
79 | | #define TIL_OPCODE_DEF(X) COP_##X, |
80 | | #include "ThreadSafetyOps.def" |
81 | | #undef TIL_OPCODE_DEF |
82 | | }; |
83 | | |
84 | | /// Opcode for unary arithmetic operations. |
85 | | enum TIL_UnaryOpcode : unsigned char { |
86 | | UOP_Minus, // - |
87 | | UOP_BitNot, // ~ |
88 | | UOP_LogicNot // ! |
89 | | }; |
90 | | |
91 | | /// Opcode for binary arithmetic operations. |
92 | | enum TIL_BinaryOpcode : unsigned char { |
93 | | BOP_Add, // + |
94 | | BOP_Sub, // - |
95 | | BOP_Mul, // * |
96 | | BOP_Div, // / |
97 | | BOP_Rem, // % |
98 | | BOP_Shl, // << |
99 | | BOP_Shr, // >> |
100 | | BOP_BitAnd, // & |
101 | | BOP_BitXor, // ^ |
102 | | BOP_BitOr, // | |
103 | | BOP_Eq, // == |
104 | | BOP_Neq, // != |
105 | | BOP_Lt, // < |
106 | | BOP_Leq, // <= |
107 | | BOP_Cmp, // <=> |
108 | | BOP_LogicAnd, // && (no short-circuit) |
109 | | BOP_LogicOr // || (no short-circuit) |
110 | | }; |
111 | | |
112 | | /// Opcode for cast operations. |
113 | | enum TIL_CastOpcode : unsigned char { |
114 | | CAST_none = 0, |
115 | | |
116 | | // Extend precision of numeric type |
117 | | CAST_extendNum, |
118 | | |
119 | | // Truncate precision of numeric type |
120 | | CAST_truncNum, |
121 | | |
122 | | // Convert to floating point type |
123 | | CAST_toFloat, |
124 | | |
125 | | // Convert to integer type |
126 | | CAST_toInt, |
127 | | |
128 | | // Convert smart pointer to pointer (C++ only) |
129 | | CAST_objToPtr |
130 | | }; |
131 | | |
132 | | const TIL_Opcode COP_Min = COP_Future; |
133 | | const TIL_Opcode COP_Max = COP_Branch; |
134 | | const TIL_UnaryOpcode UOP_Min = UOP_Minus; |
135 | | const TIL_UnaryOpcode UOP_Max = UOP_LogicNot; |
136 | | const TIL_BinaryOpcode BOP_Min = BOP_Add; |
137 | | const TIL_BinaryOpcode BOP_Max = BOP_LogicOr; |
138 | | const TIL_CastOpcode CAST_Min = CAST_none; |
139 | | const TIL_CastOpcode CAST_Max = CAST_toInt; |
140 | | |
141 | | /// Return the name of a unary opcode. |
142 | | StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); |
143 | | |
144 | | /// Return the name of a binary opcode. |
145 | | StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); |
146 | | |
147 | | /// ValueTypes are data types that can actually be held in registers. |
148 | | /// All variables and expressions must have a value type. |
149 | | /// Pointer types are further subdivided into the various heap-allocated |
150 | | /// types, such as functions, records, etc. |
151 | | /// Structured types that are passed by value (e.g. complex numbers) |
152 | | /// require special handling; they use BT_ValueRef, and size ST_0. |
153 | | struct ValueType { |
154 | | enum BaseType : unsigned char { |
155 | | BT_Void = 0, |
156 | | BT_Bool, |
157 | | BT_Int, |
158 | | BT_Float, |
159 | | BT_String, // String literals |
160 | | BT_Pointer, |
161 | | BT_ValueRef |
162 | | }; |
163 | | |
164 | | enum SizeType : unsigned char { |
165 | | ST_0 = 0, |
166 | | ST_1, |
167 | | ST_8, |
168 | | ST_16, |
169 | | ST_32, |
170 | | ST_64, |
171 | | ST_128 |
172 | | }; |
173 | | |
174 | | ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) |
175 | 72 | : Base(B), Size(Sz), Signed(S), VectSize(VS) {} |
176 | | |
177 | | inline static SizeType getSizeType(unsigned nbytes); |
178 | | |
179 | | template <class T> |
180 | | inline static ValueType getValueType(); |
181 | | |
182 | | BaseType Base; |
183 | | SizeType Size; |
184 | | bool Signed; |
185 | | |
186 | | // 0 for scalar, otherwise num elements in vector |
187 | | unsigned char VectSize; |
188 | | }; |
189 | | |
190 | 0 | inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { |
191 | 0 | switch (nbytes) { |
192 | 0 | case 1: return ST_8; |
193 | 0 | case 2: return ST_16; |
194 | 0 | case 4: return ST_32; |
195 | 0 | case 8: return ST_64; |
196 | 0 | case 16: return ST_128; |
197 | 0 | default: return ST_0; |
198 | 0 | } |
199 | 0 | } |
200 | | |
201 | | template<> |
202 | 72 | inline ValueType ValueType::getValueType<void>() { |
203 | 72 | return ValueType(BT_Void, ST_0, false, 0); |
204 | 72 | } |
205 | | |
206 | | template<> |
207 | 0 | inline ValueType ValueType::getValueType<bool>() { |
208 | 0 | return ValueType(BT_Bool, ST_1, false, 0); |
209 | 0 | } |
210 | | |
211 | | template<> |
212 | 0 | inline ValueType ValueType::getValueType<int8_t>() { |
213 | 0 | return ValueType(BT_Int, ST_8, true, 0); |
214 | 0 | } |
215 | | |
216 | | template<> |
217 | 0 | inline ValueType ValueType::getValueType<uint8_t>() { |
218 | 0 | return ValueType(BT_Int, ST_8, false, 0); |
219 | 0 | } |
220 | | |
221 | | template<> |
222 | 0 | inline ValueType ValueType::getValueType<int16_t>() { |
223 | 0 | return ValueType(BT_Int, ST_16, true, 0); |
224 | 0 | } |
225 | | |
226 | | template<> |
227 | 0 | inline ValueType ValueType::getValueType<uint16_t>() { |
228 | 0 | return ValueType(BT_Int, ST_16, false, 0); |
229 | 0 | } |
230 | | |
231 | | template<> |
232 | 0 | inline ValueType ValueType::getValueType<int32_t>() { |
233 | 0 | return ValueType(BT_Int, ST_32, true, 0); |
234 | 0 | } |
235 | | |
236 | | template<> |
237 | 0 | inline ValueType ValueType::getValueType<uint32_t>() { |
238 | 0 | return ValueType(BT_Int, ST_32, false, 0); |
239 | 0 | } |
240 | | |
241 | | template<> |
242 | 0 | inline ValueType ValueType::getValueType<int64_t>() { |
243 | 0 | return ValueType(BT_Int, ST_64, true, 0); |
244 | 0 | } |
245 | | |
246 | | template<> |
247 | 0 | inline ValueType ValueType::getValueType<uint64_t>() { |
248 | 0 | return ValueType(BT_Int, ST_64, false, 0); |
249 | 0 | } |
250 | | |
251 | | template<> |
252 | 0 | inline ValueType ValueType::getValueType<float>() { |
253 | 0 | return ValueType(BT_Float, ST_32, true, 0); |
254 | 0 | } |
255 | | |
256 | | template<> |
257 | 0 | inline ValueType ValueType::getValueType<double>() { |
258 | 0 | return ValueType(BT_Float, ST_64, true, 0); |
259 | 0 | } |
260 | | |
261 | | template<> |
262 | 0 | inline ValueType ValueType::getValueType<long double>() { |
263 | 0 | return ValueType(BT_Float, ST_128, true, 0); |
264 | 0 | } |
265 | | |
266 | | template<> |
267 | 0 | inline ValueType ValueType::getValueType<StringRef>() { |
268 | 0 | return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); |
269 | 0 | } |
270 | | |
271 | | template<> |
272 | 0 | inline ValueType ValueType::getValueType<void*>() { |
273 | 0 | return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); |
274 | 0 | } |
275 | | |
276 | | /// Base class for AST nodes in the typed intermediate language. |
277 | | class SExpr { |
278 | | public: |
279 | | SExpr() = delete; |
280 | | |
281 | 322k | TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } |
282 | | |
283 | | // Subclasses of SExpr must define the following: |
284 | | // |
285 | | // This(const This& E, ...) { |
286 | | // copy constructor: construct copy of E, with some additional arguments. |
287 | | // } |
288 | | // |
289 | | // template <class V> |
290 | | // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
291 | | // traverse all subexpressions, following the traversal/rewriter interface. |
292 | | // } |
293 | | // |
294 | | // template <class C> typename C::CType compare(CType* E, C& Cmp) { |
295 | | // compare all subexpressions, following the comparator interface |
296 | | // } |
297 | 20.1k | void *operator new(size_t S, MemRegionRef &R) { |
298 | 20.1k | return ::operator new(S, R); |
299 | 20.1k | } |
300 | | |
301 | | /// SExpr objects must be created in an arena. |
302 | | void *operator new(size_t) = delete; |
303 | | |
304 | | /// SExpr objects cannot be deleted. |
305 | | // This declaration is public to workaround a gcc bug that breaks building |
306 | | // with REQUIRES_EH=1. |
307 | | void operator delete(void *) = delete; |
308 | | |
309 | | /// Returns the instruction ID for this expression. |
310 | | /// All basic block instructions have a unique ID (i.e. virtual register). |
311 | 0 | unsigned id() const { return SExprID; } |
312 | | |
313 | | /// Returns the block, if this is an instruction in a basic block, |
314 | | /// otherwise returns null. |
315 | 4.23k | BasicBlock *block() const { return Block; } |
316 | | |
317 | | /// Set the basic block and instruction ID for this expression. |
318 | 0 | void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } |
319 | | |
320 | | protected: |
321 | 20.1k | SExpr(TIL_Opcode Op) : Opcode(Op) {} |
322 | 0 | SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {} |
323 | | |
324 | | const unsigned char Opcode; |
325 | | unsigned char Reserved = 0; |
326 | | unsigned short Flags = 0; |
327 | | unsigned SExprID = 0; |
328 | | BasicBlock *Block = nullptr; |
329 | | }; |
330 | | |
331 | | // Contains various helper functions for SExprs. |
332 | | namespace ThreadSafetyTIL { |
333 | | |
334 | 0 | inline bool isTrivial(const SExpr *E) { |
335 | 0 | unsigned Op = E->opcode(); |
336 | 0 | return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; |
337 | 0 | } |
338 | | |
339 | | } // namespace ThreadSafetyTIL |
340 | | |
341 | | // Nodes which declare variables |
342 | | |
343 | | /// A named variable, e.g. "x". |
344 | | /// |
345 | | /// There are two distinct places in which a Variable can appear in the AST. |
346 | | /// A variable declaration introduces a new variable, and can occur in 3 places: |
347 | | /// Let-expressions: (Let (x = t) u) |
348 | | /// Functions: (Function (x : t) u) |
349 | | /// Self-applicable functions (SFunction (x) t) |
350 | | /// |
351 | | /// If a variable occurs in any other location, it is a reference to an existing |
352 | | /// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't |
353 | | /// allocate a separate AST node for variable references; a reference is just a |
354 | | /// pointer to the original declaration. |
355 | | class Variable : public SExpr { |
356 | | public: |
357 | | enum VariableKind { |
358 | | /// Let-variable |
359 | | VK_Let, |
360 | | |
361 | | /// Function parameter |
362 | | VK_Fun, |
363 | | |
364 | | /// SFunction (self) parameter |
365 | | VK_SFun |
366 | | }; |
367 | | |
368 | | Variable(StringRef s, SExpr *D = nullptr) |
369 | 0 | : SExpr(COP_Variable), Name(s), Definition(D) { |
370 | 0 | Flags = VK_Let; |
371 | 0 | } |
372 | | |
373 | | Variable(SExpr *D, const ValueDecl *Cvd = nullptr) |
374 | | : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), |
375 | 2.14k | Definition(D), Cvdecl(Cvd) { |
376 | 2.14k | Flags = VK_Let; |
377 | 2.14k | } |
378 | | |
379 | | Variable(const Variable &Vd, SExpr *D) // rewrite constructor |
380 | 0 | : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { |
381 | 0 | Flags = Vd.kind(); |
382 | 0 | } |
383 | | |
384 | 8.94k | static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } |
385 | | |
386 | | /// Return the kind of variable (let, function param, or self) |
387 | 2.16k | VariableKind kind() const { return static_cast<VariableKind>(Flags); } |
388 | | |
389 | | /// Return the name of the variable, if any. |
390 | 0 | StringRef name() const { return Name; } |
391 | | |
392 | | /// Return the clang declaration for this variable, if any. |
393 | 4.05k | const ValueDecl *clangDecl() const { return Cvdecl; } |
394 | | |
395 | | /// Return the definition of the variable. |
396 | | /// For let-vars, this is the setting expression. |
397 | | /// For function and self parameters, it is the type of the variable. |
398 | 0 | SExpr *definition() { return Definition; } |
399 | 0 | const SExpr *definition() const { return Definition; } |
400 | | |
401 | 0 | void setName(StringRef S) { Name = S; } |
402 | 2.14k | void setKind(VariableKind K) { Flags = K; } |
403 | 0 | void setDefinition(SExpr *E) { Definition = E; } |
404 | 0 | void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } |
405 | | |
406 | | template <class V> |
407 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
408 | | // This routine is only called for variable references. |
409 | | return Vs.reduceVariableRef(this); |
410 | | } |
411 | | |
412 | | template <class C> |
413 | 11.5k | typename C::CType compare(const Variable* E, C& Cmp) const { |
414 | 11.5k | return Cmp.compareVariableRefs(this, E); |
415 | 11.5k | } clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Variable::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Variable const*, clang::threadSafety::til::EqualsComparator&) const Line | Count | Source | 413 | 832 | typename C::CType compare(const Variable* E, C& Cmp) const { | 414 | 832 | return Cmp.compareVariableRefs(this, E); | 415 | 832 | } |
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Variable::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Variable const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 413 | 10.7k | typename C::CType compare(const Variable* E, C& Cmp) const { | 414 | 10.7k | return Cmp.compareVariableRefs(this, E); | 415 | 10.7k | } |
|
416 | | |
417 | | private: |
418 | | friend class BasicBlock; |
419 | | friend class Function; |
420 | | friend class Let; |
421 | | friend class SFunction; |
422 | | |
423 | | // The name of the variable. |
424 | | StringRef Name; |
425 | | |
426 | | // The TIL type or definition. |
427 | | SExpr *Definition; |
428 | | |
429 | | // The clang declaration for this variable. |
430 | | const ValueDecl *Cvdecl = nullptr; |
431 | | }; |
432 | | |
433 | | /// Placeholder for an expression that has not yet been created. |
434 | | /// Used to implement lazy copy and rewriting strategies. |
435 | | class Future : public SExpr { |
436 | | public: |
437 | | enum FutureStatus { |
438 | | FS_pending, |
439 | | FS_evaluating, |
440 | | FS_done |
441 | | }; |
442 | | |
443 | 0 | Future() : SExpr(COP_Future) {} |
444 | | virtual ~Future() = delete; |
445 | | |
446 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } |
447 | | |
448 | | // A lazy rewriting strategy should subclass Future and override this method. |
449 | 0 | virtual SExpr *compute() { return nullptr; } |
450 | | |
451 | | // Return the result of this future if it exists, otherwise return null. |
452 | 0 | SExpr *maybeGetResult() const { return Result; } |
453 | | |
454 | | // Return the result of this future; forcing it if necessary. |
455 | 0 | SExpr *result() { |
456 | 0 | switch (Status) { |
457 | 0 | case FS_pending: |
458 | 0 | return force(); |
459 | 0 | case FS_evaluating: |
460 | 0 | return nullptr; // infinite loop; illegal recursion. |
461 | 0 | case FS_done: |
462 | 0 | return Result; |
463 | 0 | } |
464 | 0 | } |
465 | | |
466 | | template <class V> |
467 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
468 | | assert(Result && "Cannot traverse Future that has not been forced."); |
469 | | return Vs.traverse(Result, Ctx); |
470 | | } |
471 | | |
472 | | template <class C> |
473 | 0 | typename C::CType compare(const Future* E, C& Cmp) const { |
474 | 0 | if (!Result || !E->Result) |
475 | 0 | return Cmp.comparePointers(this, E); |
476 | 0 | return Cmp.compare(Result, E->Result); |
477 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Future::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Future const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Future::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Future const*, clang::threadSafety::til::MatchComparator&) const |
478 | | |
479 | | private: |
480 | | SExpr* force(); |
481 | | |
482 | | FutureStatus Status = FS_pending; |
483 | | SExpr *Result = nullptr; |
484 | | }; |
485 | | |
486 | | /// Placeholder for expressions that cannot be represented in the TIL. |
487 | | class Undefined : public SExpr { |
488 | | public: |
489 | 28 | Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} |
490 | 0 | Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} |
491 | | |
492 | 7.88k | static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } |
493 | | |
494 | | template <class V> |
495 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
496 | | return Vs.reduceUndefined(*this); |
497 | | } |
498 | | |
499 | | template <class C> |
500 | 36 | typename C::CType compare(const Undefined* E, C& Cmp) const { |
501 | 36 | return Cmp.trueResult(); |
502 | 36 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Undefined::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Undefined const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Undefined::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Undefined const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 500 | 36 | typename C::CType compare(const Undefined* E, C& Cmp) const { | 501 | 36 | return Cmp.trueResult(); | 502 | 36 | } |
|
503 | | |
504 | | private: |
505 | | const Stmt *Cstmt; |
506 | | }; |
507 | | |
508 | | /// Placeholder for a wildcard that matches any other expression. |
509 | | class Wildcard : public SExpr { |
510 | | public: |
511 | 148 | Wildcard() : SExpr(COP_Wildcard) {} |
512 | | Wildcard(const Wildcard &) = default; |
513 | | |
514 | 28.3k | static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } |
515 | | |
516 | | template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
517 | | return Vs.reduceWildcard(*this); |
518 | | } |
519 | | |
520 | | template <class C> |
521 | 0 | typename C::CType compare(const Wildcard* E, C& Cmp) const { |
522 | 0 | return Cmp.trueResult(); |
523 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Wildcard::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Wildcard const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Wildcard::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Wildcard const*, clang::threadSafety::til::MatchComparator&) const |
524 | | }; |
525 | | |
526 | | template <class T> class LiteralT; |
527 | | |
528 | | // Base class for literal values. |
529 | | class Literal : public SExpr { |
530 | | public: |
531 | | Literal(const Expr *C) |
532 | 72 | : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {} |
533 | 0 | Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {} |
534 | | Literal(const Literal &) = default; |
535 | | |
536 | 8.35k | static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } |
537 | | |
538 | | // The clang expression for this literal. |
539 | 24 | const Expr *clangExpr() const { return Cexpr; } |
540 | | |
541 | 0 | ValueType valueType() const { return ValType; } |
542 | | |
543 | 0 | template<class T> const LiteralT<T>& as() const { |
544 | 0 | return *static_cast<const LiteralT<T>*>(this); |
545 | 0 | } Unexecuted instantiation: clang::threadSafety::til::LiteralT<bool> const& clang::threadSafety::til::Literal::as<bool>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<signed char> const& clang::threadSafety::til::Literal::as<signed char>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned char> const& clang::threadSafety::til::Literal::as<unsigned char>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<short> const& clang::threadSafety::til::Literal::as<short>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned short> const& clang::threadSafety::til::Literal::as<unsigned short>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<int> const& clang::threadSafety::til::Literal::as<int>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned int> const& clang::threadSafety::til::Literal::as<unsigned int>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<long long> const& clang::threadSafety::til::Literal::as<long long>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned long long> const& clang::threadSafety::til::Literal::as<unsigned long long>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<float> const& clang::threadSafety::til::Literal::as<float>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<double> const& clang::threadSafety::til::Literal::as<double>() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<llvm::StringRef> const& clang::threadSafety::til::Literal::as<llvm::StringRef>() const |
546 | | template<class T> LiteralT<T>& as() { |
547 | | return *static_cast<LiteralT<T>*>(this); |
548 | | } |
549 | | |
550 | | template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); |
551 | | |
552 | | template <class C> |
553 | 356 | typename C::CType compare(const Literal* E, C& Cmp) const { |
554 | 356 | // TODO: defer actual comparison to LiteralT |
555 | 356 | return Cmp.trueResult(); |
556 | 356 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Literal::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Literal const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Literal::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Literal const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 553 | 356 | typename C::CType compare(const Literal* E, C& Cmp) const { | 554 | 356 | // TODO: defer actual comparison to LiteralT | 555 | 356 | return Cmp.trueResult(); | 556 | 356 | } |
|
557 | | |
558 | | private: |
559 | | const ValueType ValType; |
560 | | const Expr *Cexpr = nullptr; |
561 | | }; |
562 | | |
563 | | // Derived class for literal values, which stores the actual value. |
564 | | template<class T> |
565 | | class LiteralT : public Literal { |
566 | | public: |
567 | | LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} |
568 | | LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} |
569 | | |
570 | 0 | T value() const { return Val;} Unexecuted instantiation: clang::threadSafety::til::LiteralT<bool>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<signed char>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned char>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<short>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned short>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<int>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned int>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<long long>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned long long>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<float>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<double>::value() const Unexecuted instantiation: clang::threadSafety::til::LiteralT<llvm::StringRef>::value() const |
571 | | T& value() { return Val; } |
572 | | |
573 | | private: |
574 | | T Val; |
575 | | }; |
576 | | |
577 | | template <class V> |
578 | | typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { |
579 | | if (Cexpr) |
580 | | return Vs.reduceLiteral(*this); |
581 | | |
582 | | switch (ValType.Base) { |
583 | | case ValueType::BT_Void: |
584 | | break; |
585 | | case ValueType::BT_Bool: |
586 | | return Vs.reduceLiteralT(as<bool>()); |
587 | | case ValueType::BT_Int: { |
588 | | switch (ValType.Size) { |
589 | | case ValueType::ST_8: |
590 | | if (ValType.Signed) |
591 | | return Vs.reduceLiteralT(as<int8_t>()); |
592 | | else |
593 | | return Vs.reduceLiteralT(as<uint8_t>()); |
594 | | case ValueType::ST_16: |
595 | | if (ValType.Signed) |
596 | | return Vs.reduceLiteralT(as<int16_t>()); |
597 | | else |
598 | | return Vs.reduceLiteralT(as<uint16_t>()); |
599 | | case ValueType::ST_32: |
600 | | if (ValType.Signed) |
601 | | return Vs.reduceLiteralT(as<int32_t>()); |
602 | | else |
603 | | return Vs.reduceLiteralT(as<uint32_t>()); |
604 | | case ValueType::ST_64: |
605 | | if (ValType.Signed) |
606 | | return Vs.reduceLiteralT(as<int64_t>()); |
607 | | else |
608 | | return Vs.reduceLiteralT(as<uint64_t>()); |
609 | | default: |
610 | | break; |
611 | | } |
612 | | } |
613 | | case ValueType::BT_Float: { |
614 | | switch (ValType.Size) { |
615 | | case ValueType::ST_32: |
616 | | return Vs.reduceLiteralT(as<float>()); |
617 | | case ValueType::ST_64: |
618 | | return Vs.reduceLiteralT(as<double>()); |
619 | | default: |
620 | | break; |
621 | | } |
622 | | } |
623 | | case ValueType::BT_String: |
624 | | return Vs.reduceLiteralT(as<StringRef>()); |
625 | | case ValueType::BT_Pointer: |
626 | | return Vs.reduceLiteralT(as<void*>()); |
627 | | case ValueType::BT_ValueRef: |
628 | | break; |
629 | | } |
630 | | return Vs.reduceLiteral(*this); |
631 | | } |
632 | | |
633 | | /// A Literal pointer to an object allocated in memory. |
634 | | /// At compile time, pointer literals are represented by symbolic names. |
635 | | class LiteralPtr : public SExpr { |
636 | | public: |
637 | 4.25k | LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} |
638 | | LiteralPtr(const LiteralPtr &) = default; |
639 | | |
640 | 2.85k | static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } |
641 | | |
642 | | // The clang declaration for the value that this pointer points to. |
643 | 3.39k | const ValueDecl *clangDecl() const { return Cvdecl; } |
644 | | |
645 | | template <class V> |
646 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
647 | | return Vs.reduceLiteralPtr(*this); |
648 | | } |
649 | | |
650 | | template <class C> |
651 | 10.6k | typename C::CType compare(const LiteralPtr* E, C& Cmp) const { |
652 | 10.6k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); |
653 | 10.6k | } clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::LiteralPtr::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::LiteralPtr const*, clang::threadSafety::til::EqualsComparator&) const Line | Count | Source | 651 | 1.22k | typename C::CType compare(const LiteralPtr* E, C& Cmp) const { | 652 | 1.22k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); | 653 | 1.22k | } |
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::LiteralPtr::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::LiteralPtr const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 651 | 9.39k | typename C::CType compare(const LiteralPtr* E, C& Cmp) const { | 652 | 9.39k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); | 653 | 9.39k | } |
|
654 | | |
655 | | private: |
656 | | const ValueDecl *Cvdecl; |
657 | | }; |
658 | | |
659 | | /// A function -- a.k.a. lambda abstraction. |
660 | | /// Functions with multiple arguments are created by currying, |
661 | | /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) |
662 | | class Function : public SExpr { |
663 | | public: |
664 | | Function(Variable *Vd, SExpr *Bd) |
665 | 0 | : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { |
666 | 0 | Vd->setKind(Variable::VK_Fun); |
667 | 0 | } |
668 | | |
669 | | Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor |
670 | 0 | : SExpr(F), VarDecl(Vd), Body(Bd) { |
671 | 0 | Vd->setKind(Variable::VK_Fun); |
672 | 0 | } |
673 | | |
674 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } |
675 | | |
676 | 0 | Variable *variableDecl() { return VarDecl; } |
677 | 0 | const Variable *variableDecl() const { return VarDecl; } |
678 | | |
679 | 0 | SExpr *body() { return Body; } |
680 | 0 | const SExpr *body() const { return Body; } |
681 | | |
682 | | template <class V> |
683 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
684 | | // This is a variable declaration, so traverse the definition. |
685 | | auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); |
686 | | // Tell the rewriter to enter the scope of the function. |
687 | | Variable *Nvd = Vs.enterScope(*VarDecl, E0); |
688 | | auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); |
689 | | Vs.exitScope(*VarDecl); |
690 | | return Vs.reduceFunction(*this, Nvd, E1); |
691 | | } |
692 | | |
693 | | template <class C> |
694 | 0 | typename C::CType compare(const Function* E, C& Cmp) const { |
695 | 0 | typename C::CType Ct = |
696 | 0 | Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); |
697 | 0 | if (Cmp.notTrue(Ct)) |
698 | 0 | return Ct; |
699 | 0 | Cmp.enterScope(variableDecl(), E->variableDecl()); |
700 | 0 | Ct = Cmp.compare(body(), E->body()); |
701 | 0 | Cmp.leaveScope(); |
702 | 0 | return Ct; |
703 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Function::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Function const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Function::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Function const*, clang::threadSafety::til::MatchComparator&) const |
704 | | |
705 | | private: |
706 | | Variable *VarDecl; |
707 | | SExpr* Body; |
708 | | }; |
709 | | |
710 | | /// A self-applicable function. |
711 | | /// A self-applicable function can be applied to itself. It's useful for |
712 | | /// implementing objects and late binding. |
713 | | class SFunction : public SExpr { |
714 | | public: |
715 | | SFunction(Variable *Vd, SExpr *B) |
716 | 0 | : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { |
717 | 0 | assert(Vd->Definition == nullptr); |
718 | 0 | Vd->setKind(Variable::VK_SFun); |
719 | 0 | Vd->Definition = this; |
720 | 0 | } |
721 | | |
722 | | SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor |
723 | 0 | : SExpr(F), VarDecl(Vd), Body(B) { |
724 | 0 | assert(Vd->Definition == nullptr); |
725 | 0 | Vd->setKind(Variable::VK_SFun); |
726 | 0 | Vd->Definition = this; |
727 | 0 | } |
728 | | |
729 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } |
730 | | |
731 | 0 | Variable *variableDecl() { return VarDecl; } |
732 | 0 | const Variable *variableDecl() const { return VarDecl; } |
733 | | |
734 | 0 | SExpr *body() { return Body; } |
735 | 0 | const SExpr *body() const { return Body; } |
736 | | |
737 | | template <class V> |
738 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
739 | | // A self-variable points to the SFunction itself. |
740 | | // A rewrite must introduce the variable with a null definition, and update |
741 | | // it after 'this' has been rewritten. |
742 | | Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); |
743 | | auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); |
744 | | Vs.exitScope(*VarDecl); |
745 | | // A rewrite operation will call SFun constructor to set Vvd->Definition. |
746 | | return Vs.reduceSFunction(*this, Nvd, E1); |
747 | | } |
748 | | |
749 | | template <class C> |
750 | 0 | typename C::CType compare(const SFunction* E, C& Cmp) const { |
751 | 0 | Cmp.enterScope(variableDecl(), E->variableDecl()); |
752 | 0 | typename C::CType Ct = Cmp.compare(body(), E->body()); |
753 | 0 | Cmp.leaveScope(); |
754 | 0 | return Ct; |
755 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SFunction::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SFunction const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SFunction::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SFunction const*, clang::threadSafety::til::MatchComparator&) const |
756 | | |
757 | | private: |
758 | | Variable *VarDecl; |
759 | | SExpr* Body; |
760 | | }; |
761 | | |
762 | | /// A block of code -- e.g. the body of a function. |
763 | | class Code : public SExpr { |
764 | | public: |
765 | 0 | Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} |
766 | | Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor |
767 | 0 | : SExpr(C), ReturnType(T), Body(B) {} |
768 | | |
769 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } |
770 | | |
771 | 0 | SExpr *returnType() { return ReturnType; } |
772 | 0 | const SExpr *returnType() const { return ReturnType; } |
773 | | |
774 | 0 | SExpr *body() { return Body; } |
775 | 0 | const SExpr *body() const { return Body; } |
776 | | |
777 | | template <class V> |
778 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
779 | | auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); |
780 | | auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); |
781 | | return Vs.reduceCode(*this, Nt, Nb); |
782 | | } |
783 | | |
784 | | template <class C> |
785 | 0 | typename C::CType compare(const Code* E, C& Cmp) const { |
786 | 0 | typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); |
787 | 0 | if (Cmp.notTrue(Ct)) |
788 | 0 | return Ct; |
789 | 0 | return Cmp.compare(body(), E->body()); |
790 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Code::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Code const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Code::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Code const*, clang::threadSafety::til::MatchComparator&) const |
791 | | |
792 | | private: |
793 | | SExpr* ReturnType; |
794 | | SExpr* Body; |
795 | | }; |
796 | | |
797 | | /// A typed, writable location in memory |
798 | | class Field : public SExpr { |
799 | | public: |
800 | 0 | Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} |
801 | | Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor |
802 | 0 | : SExpr(C), Range(R), Body(B) {} |
803 | | |
804 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } |
805 | | |
806 | 0 | SExpr *range() { return Range; } |
807 | 0 | const SExpr *range() const { return Range; } |
808 | | |
809 | 0 | SExpr *body() { return Body; } |
810 | 0 | const SExpr *body() const { return Body; } |
811 | | |
812 | | template <class V> |
813 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
814 | | auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); |
815 | | auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); |
816 | | return Vs.reduceField(*this, Nr, Nb); |
817 | | } |
818 | | |
819 | | template <class C> |
820 | 0 | typename C::CType compare(const Field* E, C& Cmp) const { |
821 | 0 | typename C::CType Ct = Cmp.compare(range(), E->range()); |
822 | 0 | if (Cmp.notTrue(Ct)) |
823 | 0 | return Ct; |
824 | 0 | return Cmp.compare(body(), E->body()); |
825 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Field::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Field const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Field::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Field const*, clang::threadSafety::til::MatchComparator&) const |
826 | | |
827 | | private: |
828 | | SExpr* Range; |
829 | | SExpr* Body; |
830 | | }; |
831 | | |
832 | | /// Apply an argument to a function. |
833 | | /// Note that this does not actually call the function. Functions are curried, |
834 | | /// so this returns a closure in which the first parameter has been applied. |
835 | | /// Once all parameters have been applied, Call can be used to invoke the |
836 | | /// function. |
837 | | class Apply : public SExpr { |
838 | | public: |
839 | 200 | Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} |
840 | | Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor |
841 | 0 | : SExpr(A), Fun(F), Arg(Ar) {} |
842 | | |
843 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } |
844 | | |
845 | 0 | SExpr *fun() { return Fun; } |
846 | 2.71k | const SExpr *fun() const { return Fun; } |
847 | | |
848 | 0 | SExpr *arg() { return Arg; } |
849 | 2.04k | const SExpr *arg() const { return Arg; } |
850 | | |
851 | | template <class V> |
852 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
853 | | auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); |
854 | | auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); |
855 | | return Vs.reduceApply(*this, Nf, Na); |
856 | | } |
857 | | |
858 | | template <class C> |
859 | 1.33k | typename C::CType compare(const Apply* E, C& Cmp) const { |
860 | 1.33k | typename C::CType Ct = Cmp.compare(fun(), E->fun()); |
861 | 1.33k | if (Cmp.notTrue(Ct)) |
862 | 336 | return Ct; |
863 | 1.00k | return Cmp.compare(arg(), E->arg()); |
864 | 1.00k | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Apply::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Apply const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Apply::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Apply const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 859 | 1.33k | typename C::CType compare(const Apply* E, C& Cmp) const { | 860 | 1.33k | typename C::CType Ct = Cmp.compare(fun(), E->fun()); | 861 | 1.33k | if (Cmp.notTrue(Ct)) | 862 | 336 | return Ct; | 863 | 1.00k | return Cmp.compare(arg(), E->arg()); | 864 | 1.00k | } |
|
865 | | |
866 | | private: |
867 | | SExpr* Fun; |
868 | | SExpr* Arg; |
869 | | }; |
870 | | |
871 | | /// Apply a self-argument to a self-applicable function. |
872 | | class SApply : public SExpr { |
873 | | public: |
874 | 6.27k | SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} |
875 | | SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor |
876 | 0 | : SExpr(A), Sfun(Sf), Arg(Ar) {} |
877 | | |
878 | 2.69k | static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } |
879 | | |
880 | 0 | SExpr *sfun() { return Sfun; } |
881 | 23.8k | const SExpr *sfun() const { return Sfun; } |
882 | | |
883 | 0 | SExpr *arg() { return Arg ? Arg : Sfun; } |
884 | 27.8k | const SExpr *arg() const { return Arg ? Arg0 : Sfun; } |
885 | | |
886 | 2.67k | bool isDelegation() const { return Arg != nullptr; } |
887 | | |
888 | | template <class V> |
889 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
890 | | auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); |
891 | | typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) |
892 | | : nullptr; |
893 | | return Vs.reduceSApply(*this, Nf, Na); |
894 | | } |
895 | | |
896 | | template <class C> |
897 | 10.3k | typename C::CType compare(const SApply* E, C& Cmp) const { |
898 | 10.3k | typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); |
899 | 10.3k | if (Cmp.notTrue(Ct) || (9.28k !arg()9.28k && !E->arg()0 )) |
900 | 1.06k | return Ct; |
901 | 9.28k | return Cmp.compare(arg(), E->arg()); |
902 | 9.28k | } clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SApply::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SApply const*, clang::threadSafety::til::EqualsComparator&) const Line | Count | Source | 897 | 1.03k | typename C::CType compare(const SApply* E, C& Cmp) const { | 898 | 1.03k | typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); | 899 | 1.03k | if (Cmp.notTrue(Ct) || (1.01k !arg()1.01k && !E->arg()0 )) | 900 | 16 | return Ct; | 901 | 1.01k | return Cmp.compare(arg(), E->arg()); | 902 | 1.01k | } |
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SApply::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SApply const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 897 | 9.30k | typename C::CType compare(const SApply* E, C& Cmp) const { | 898 | 9.30k | typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); | 899 | 9.30k | if (Cmp.notTrue(Ct) || (8.26k !arg()8.26k && !E->arg()0 )) | 900 | 1.04k | return Ct; | 901 | 8.26k | return Cmp.compare(arg(), E->arg()); | 902 | 8.26k | } |
|
903 | | |
904 | | private: |
905 | | SExpr* Sfun; |
906 | | SExpr* Arg; |
907 | | }; |
908 | | |
909 | | /// Project a named slot from a C++ struct or class. |
910 | | class Project : public SExpr { |
911 | | public: |
912 | | Project(SExpr *R, const ValueDecl *Cvd) |
913 | 6.35k | : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { |
914 | 6.35k | assert(Cvd && "ValueDecl must not be null"); |
915 | 6.35k | } |
916 | | |
917 | 6.13k | static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } |
918 | | |
919 | 0 | SExpr *record() { return Rec; } |
920 | 24.7k | const SExpr *record() const { return Rec; } |
921 | | |
922 | 3.01k | const ValueDecl *clangDecl() const { return Cvdecl; } |
923 | | |
924 | 518 | bool isArrow() const { return (Flags & 0x01) != 0; } |
925 | | |
926 | 754 | void setArrow(bool b) { |
927 | 754 | if (b) Flags |= 0x01; |
928 | 0 | else Flags &= 0xFFFE; |
929 | 754 | } |
930 | | |
931 | 2.67k | StringRef slotName() const { |
932 | 2.67k | if (Cvdecl->getDeclName().isIdentifier()) |
933 | 2.67k | return Cvdecl->getName(); |
934 | 0 | if (!SlotName) { |
935 | 0 | SlotName = ""; |
936 | 0 | llvm::raw_string_ostream OS(*SlotName); |
937 | 0 | Cvdecl->printName(OS); |
938 | 0 | } |
939 | 0 | return *SlotName; |
940 | 0 | } |
941 | | |
942 | | template <class V> |
943 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
944 | | auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); |
945 | | return Vs.reduceProject(*this, Nr); |
946 | | } |
947 | | |
948 | | template <class C> |
949 | 10.4k | typename C::CType compare(const Project* E, C& Cmp) const { |
950 | 10.4k | typename C::CType Ct = Cmp.compare(record(), E->record()); |
951 | 10.4k | if (Cmp.notTrue(Ct)) |
952 | 1.06k | return Ct; |
953 | 9.42k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); |
954 | 9.42k | } clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Project::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Project const*, clang::threadSafety::til::EqualsComparator&) const Line | Count | Source | 949 | 1.03k | typename C::CType compare(const Project* E, C& Cmp) const { | 950 | 1.03k | typename C::CType Ct = Cmp.compare(record(), E->record()); | 951 | 1.03k | if (Cmp.notTrue(Ct)) | 952 | 16 | return Ct; | 953 | 1.01k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); | 954 | 1.01k | } |
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Project::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Project const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 949 | 9.45k | typename C::CType compare(const Project* E, C& Cmp) const { | 950 | 9.45k | typename C::CType Ct = Cmp.compare(record(), E->record()); | 951 | 9.45k | if (Cmp.notTrue(Ct)) | 952 | 1.04k | return Ct; | 953 | 8.40k | return Cmp.comparePointers(Cvdecl, E->Cvdecl); | 954 | 8.40k | } |
|
955 | | |
956 | | private: |
957 | | SExpr* Rec; |
958 | | mutable llvm::Optional<std::string> SlotName; |
959 | | const ValueDecl *Cvdecl; |
960 | | }; |
961 | | |
962 | | /// Call a function (after all arguments have been applied). |
963 | | class Call : public SExpr { |
964 | | public: |
965 | | Call(SExpr *T, const CallExpr *Ce = nullptr) |
966 | 200 | : SExpr(COP_Call), Target(T), Cexpr(Ce) {} |
967 | 0 | Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} |
968 | | |
969 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } |
970 | | |
971 | 0 | SExpr *target() { return Target; } |
972 | 2.93k | const SExpr *target() const { return Target; } |
973 | | |
974 | 0 | const CallExpr *clangCallExpr() const { return Cexpr; } |
975 | | |
976 | | template <class V> |
977 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
978 | | auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); |
979 | | return Vs.reduceCall(*this, Nt); |
980 | | } |
981 | | |
982 | | template <class C> |
983 | 1.44k | typename C::CType compare(const Call* E, C& Cmp) const { |
984 | 1.44k | return Cmp.compare(target(), E->target()); |
985 | 1.44k | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Call::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Call const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Call::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Call const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 983 | 1.44k | typename C::CType compare(const Call* E, C& Cmp) const { | 984 | 1.44k | return Cmp.compare(target(), E->target()); | 985 | 1.44k | } |
|
986 | | |
987 | | private: |
988 | | SExpr* Target; |
989 | | const CallExpr *Cexpr; |
990 | | }; |
991 | | |
992 | | /// Allocate memory for a new value on the heap or stack. |
993 | | class Alloc : public SExpr { |
994 | | public: |
995 | | enum AllocKind { |
996 | | AK_Stack, |
997 | | AK_Heap |
998 | | }; |
999 | | |
1000 | 0 | Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } |
1001 | 0 | Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } |
1002 | | |
1003 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } |
1004 | | |
1005 | 0 | AllocKind kind() const { return static_cast<AllocKind>(Flags); } |
1006 | | |
1007 | 0 | SExpr *dataType() { return Dtype; } |
1008 | 0 | const SExpr *dataType() const { return Dtype; } |
1009 | | |
1010 | | template <class V> |
1011 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1012 | | auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); |
1013 | | return Vs.reduceAlloc(*this, Nd); |
1014 | | } |
1015 | | |
1016 | | template <class C> |
1017 | 0 | typename C::CType compare(const Alloc* E, C& Cmp) const { |
1018 | 0 | typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); |
1019 | 0 | if (Cmp.notTrue(Ct)) |
1020 | 0 | return Ct; |
1021 | 0 | return Cmp.compare(dataType(), E->dataType()); |
1022 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Alloc::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Alloc const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Alloc::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Alloc const*, clang::threadSafety::til::MatchComparator&) const |
1023 | | |
1024 | | private: |
1025 | | SExpr* Dtype; |
1026 | | }; |
1027 | | |
1028 | | /// Load a value from memory. |
1029 | | class Load : public SExpr { |
1030 | | public: |
1031 | 0 | Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} |
1032 | 0 | Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} |
1033 | | |
1034 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } |
1035 | | |
1036 | 0 | SExpr *pointer() { return Ptr; } |
1037 | 0 | const SExpr *pointer() const { return Ptr; } |
1038 | | |
1039 | | template <class V> |
1040 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1041 | | auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); |
1042 | | return Vs.reduceLoad(*this, Np); |
1043 | | } |
1044 | | |
1045 | | template <class C> |
1046 | 0 | typename C::CType compare(const Load* E, C& Cmp) const { |
1047 | 0 | return Cmp.compare(pointer(), E->pointer()); |
1048 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Load::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Load const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Load::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Load const*, clang::threadSafety::til::MatchComparator&) const |
1049 | | |
1050 | | private: |
1051 | | SExpr* Ptr; |
1052 | | }; |
1053 | | |
1054 | | /// Store a value to memory. |
1055 | | /// The destination is a pointer to a field, the source is the value to store. |
1056 | | class Store : public SExpr { |
1057 | | public: |
1058 | 0 | Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} |
1059 | 0 | Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} |
1060 | | |
1061 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } |
1062 | | |
1063 | 0 | SExpr *destination() { return Dest; } // Address to store to |
1064 | 0 | const SExpr *destination() const { return Dest; } |
1065 | | |
1066 | 0 | SExpr *source() { return Source; } // Value to store |
1067 | 0 | const SExpr *source() const { return Source; } |
1068 | | |
1069 | | template <class V> |
1070 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1071 | | auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); |
1072 | | auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); |
1073 | | return Vs.reduceStore(*this, Np, Nv); |
1074 | | } |
1075 | | |
1076 | | template <class C> |
1077 | 0 | typename C::CType compare(const Store* E, C& Cmp) const { |
1078 | 0 | typename C::CType Ct = Cmp.compare(destination(), E->destination()); |
1079 | 0 | if (Cmp.notTrue(Ct)) |
1080 | 0 | return Ct; |
1081 | 0 | return Cmp.compare(source(), E->source()); |
1082 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Store::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Store const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Store::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Store const*, clang::threadSafety::til::MatchComparator&) const |
1083 | | |
1084 | | private: |
1085 | | SExpr* Dest; |
1086 | | SExpr* Source; |
1087 | | }; |
1088 | | |
1089 | | /// If p is a reference to an array, then p[i] is a reference to the i'th |
1090 | | /// element of the array. |
1091 | | class ArrayIndex : public SExpr { |
1092 | | public: |
1093 | 48 | ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} |
1094 | | ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) |
1095 | 0 | : SExpr(E), Array(A), Index(N) {} |
1096 | | |
1097 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } |
1098 | | |
1099 | 0 | SExpr *array() { return Array; } |
1100 | 440 | const SExpr *array() const { return Array; } |
1101 | | |
1102 | 0 | SExpr *index() { return Index; } |
1103 | 440 | const SExpr *index() const { return Index; } |
1104 | | |
1105 | | template <class V> |
1106 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1107 | | auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); |
1108 | | auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); |
1109 | | return Vs.reduceArrayIndex(*this, Na, Ni); |
1110 | | } |
1111 | | |
1112 | | template <class C> |
1113 | 212 | typename C::CType compare(const ArrayIndex* E, C& Cmp) const { |
1114 | 212 | typename C::CType Ct = Cmp.compare(array(), E->array()); |
1115 | 212 | if (Cmp.notTrue(Ct)) |
1116 | 0 | return Ct; |
1117 | 212 | return Cmp.compare(index(), E->index()); |
1118 | 212 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::ArrayIndex::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::ArrayIndex const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::ArrayIndex::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::ArrayIndex const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 1113 | 212 | typename C::CType compare(const ArrayIndex* E, C& Cmp) const { | 1114 | 212 | typename C::CType Ct = Cmp.compare(array(), E->array()); | 1115 | 212 | if (Cmp.notTrue(Ct)) | 1116 | 0 | return Ct; | 1117 | 212 | return Cmp.compare(index(), E->index()); | 1118 | 212 | } |
|
1119 | | |
1120 | | private: |
1121 | | SExpr* Array; |
1122 | | SExpr* Index; |
1123 | | }; |
1124 | | |
1125 | | /// Pointer arithmetic, restricted to arrays only. |
1126 | | /// If p is a reference to an array, then p + n, where n is an integer, is |
1127 | | /// a reference to a subarray. |
1128 | | class ArrayAdd : public SExpr { |
1129 | | public: |
1130 | 0 | ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} |
1131 | | ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) |
1132 | 0 | : SExpr(E), Array(A), Index(N) {} |
1133 | | |
1134 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } |
1135 | | |
1136 | 0 | SExpr *array() { return Array; } |
1137 | 0 | const SExpr *array() const { return Array; } |
1138 | | |
1139 | 0 | SExpr *index() { return Index; } |
1140 | 0 | const SExpr *index() const { return Index; } |
1141 | | |
1142 | | template <class V> |
1143 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1144 | | auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); |
1145 | | auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); |
1146 | | return Vs.reduceArrayAdd(*this, Na, Ni); |
1147 | | } |
1148 | | |
1149 | | template <class C> |
1150 | 0 | typename C::CType compare(const ArrayAdd* E, C& Cmp) const { |
1151 | 0 | typename C::CType Ct = Cmp.compare(array(), E->array()); |
1152 | 0 | if (Cmp.notTrue(Ct)) |
1153 | 0 | return Ct; |
1154 | 0 | return Cmp.compare(index(), E->index()); |
1155 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::ArrayAdd::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::ArrayAdd const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::ArrayAdd::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::ArrayAdd const*, clang::threadSafety::til::MatchComparator&) const |
1156 | | |
1157 | | private: |
1158 | | SExpr* Array; |
1159 | | SExpr* Index; |
1160 | | }; |
1161 | | |
1162 | | /// Simple arithmetic unary operations, e.g. negate and not. |
1163 | | /// These operations have no side-effects. |
1164 | | class UnaryOp : public SExpr { |
1165 | | public: |
1166 | 0 | UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { |
1167 | 0 | Flags = Op; |
1168 | 0 | } |
1169 | | |
1170 | 0 | UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } |
1171 | | |
1172 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } |
1173 | | |
1174 | 0 | TIL_UnaryOpcode unaryOpcode() const { |
1175 | 0 | return static_cast<TIL_UnaryOpcode>(Flags); |
1176 | 0 | } |
1177 | | |
1178 | 0 | SExpr *expr() { return Expr0; } |
1179 | 0 | const SExpr *expr() const { return Expr0; } |
1180 | | |
1181 | | template <class V> |
1182 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1183 | | auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); |
1184 | | return Vs.reduceUnaryOp(*this, Ne); |
1185 | | } |
1186 | | |
1187 | | template <class C> |
1188 | 0 | typename C::CType compare(const UnaryOp* E, C& Cmp) const { |
1189 | 0 | typename C::CType Ct = |
1190 | 0 | Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); |
1191 | 0 | if (Cmp.notTrue(Ct)) |
1192 | 0 | return Ct; |
1193 | 0 | return Cmp.compare(expr(), E->expr()); |
1194 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::UnaryOp::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::UnaryOp const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::UnaryOp::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::UnaryOp const*, clang::threadSafety::til::MatchComparator&) const |
1195 | | |
1196 | | private: |
1197 | | SExpr* Expr0; |
1198 | | }; |
1199 | | |
1200 | | /// Simple arithmetic binary operations, e.g. +, -, etc. |
1201 | | /// These operations have no side effects. |
1202 | | class BinaryOp : public SExpr { |
1203 | | public: |
1204 | | BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) |
1205 | 36 | : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { |
1206 | 36 | Flags = Op; |
1207 | 36 | } |
1208 | | |
1209 | | BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) |
1210 | 0 | : SExpr(B), Expr0(E0), Expr1(E1) { |
1211 | 0 | Flags = B.Flags; |
1212 | 0 | } |
1213 | | |
1214 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } |
1215 | | |
1216 | 368 | TIL_BinaryOpcode binaryOpcode() const { |
1217 | 368 | return static_cast<TIL_BinaryOpcode>(Flags); |
1218 | 368 | } |
1219 | | |
1220 | 0 | SExpr *expr0() { return Expr0; } |
1221 | 368 | const SExpr *expr0() const { return Expr0; } |
1222 | | |
1223 | 0 | SExpr *expr1() { return Expr1; } |
1224 | 368 | const SExpr *expr1() const { return Expr1; } |
1225 | | |
1226 | | template <class V> |
1227 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1228 | | auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); |
1229 | | auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); |
1230 | | return Vs.reduceBinaryOp(*this, Ne0, Ne1); |
1231 | | } |
1232 | | |
1233 | | template <class C> |
1234 | 180 | typename C::CType compare(const BinaryOp* E, C& Cmp) const { |
1235 | 180 | typename C::CType Ct = |
1236 | 180 | Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); |
1237 | 180 | if (Cmp.notTrue(Ct)) |
1238 | 0 | return Ct; |
1239 | 180 | Ct = Cmp.compare(expr0(), E->expr0()); |
1240 | 180 | if (Cmp.notTrue(Ct)) |
1241 | 0 | return Ct; |
1242 | 180 | return Cmp.compare(expr1(), E->expr1()); |
1243 | 180 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::BinaryOp::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::BinaryOp const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::BinaryOp::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::BinaryOp const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 1234 | 180 | typename C::CType compare(const BinaryOp* E, C& Cmp) const { | 1235 | 180 | typename C::CType Ct = | 1236 | 180 | Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); | 1237 | 180 | if (Cmp.notTrue(Ct)) | 1238 | 0 | return Ct; | 1239 | 180 | Ct = Cmp.compare(expr0(), E->expr0()); | 1240 | 180 | if (Cmp.notTrue(Ct)) | 1241 | 0 | return Ct; | 1242 | 180 | return Cmp.compare(expr1(), E->expr1()); | 1243 | 180 | } |
|
1244 | | |
1245 | | private: |
1246 | | SExpr* Expr0; |
1247 | | SExpr* Expr1; |
1248 | | }; |
1249 | | |
1250 | | /// Cast expressions. |
1251 | | /// Cast expressions are essentially unary operations, but we treat them |
1252 | | /// as a distinct AST node because they only change the type of the result. |
1253 | | class Cast : public SExpr { |
1254 | | public: |
1255 | 392 | Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } |
1256 | 0 | Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } |
1257 | | |
1258 | 13.9k | static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } |
1259 | | |
1260 | 888 | TIL_CastOpcode castOpcode() const { |
1261 | 888 | return static_cast<TIL_CastOpcode>(Flags); |
1262 | 888 | } |
1263 | | |
1264 | 0 | SExpr *expr() { return Expr0; } |
1265 | 792 | const SExpr *expr() const { return Expr0; } |
1266 | | |
1267 | | template <class V> |
1268 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1269 | | auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); |
1270 | | return Vs.reduceCast(*this, Ne); |
1271 | | } |
1272 | | |
1273 | | template <class C> |
1274 | 248 | typename C::CType compare(const Cast* E, C& Cmp) const { |
1275 | 248 | typename C::CType Ct = |
1276 | 248 | Cmp.compareIntegers(castOpcode(), E->castOpcode()); |
1277 | 248 | if (Cmp.notTrue(Ct)) |
1278 | 0 | return Ct; |
1279 | 248 | return Cmp.compare(expr(), E->expr()); |
1280 | 248 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Cast::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Cast const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Cast::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Cast const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 1274 | 248 | typename C::CType compare(const Cast* E, C& Cmp) const { | 1275 | 248 | typename C::CType Ct = | 1276 | 248 | Cmp.compareIntegers(castOpcode(), E->castOpcode()); | 1277 | 248 | if (Cmp.notTrue(Ct)) | 1278 | 0 | return Ct; | 1279 | 248 | return Cmp.compare(expr(), E->expr()); | 1280 | 248 | } |
|
1281 | | |
1282 | | private: |
1283 | | SExpr* Expr0; |
1284 | | }; |
1285 | | |
1286 | | class SCFG; |
1287 | | |
1288 | | /// Phi Node, for code in SSA form. |
1289 | | /// Each Phi node has an array of possible values that it can take, |
1290 | | /// depending on where control flow comes from. |
1291 | | class Phi : public SExpr { |
1292 | | public: |
1293 | | using ValArray = SimpleArray<SExpr *>; |
1294 | | |
1295 | | // In minimal SSA form, all Phi nodes are MultiVal. |
1296 | | // During conversion to SSA, incomplete Phi nodes may be introduced, which |
1297 | | // are later determined to be SingleVal, and are thus redundant. |
1298 | | enum Status { |
1299 | | PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) |
1300 | | PH_SingleVal, // Phi node has one distinct value, and can be eliminated |
1301 | | PH_Incomplete // Phi node is incomplete |
1302 | | }; |
1303 | | |
1304 | 0 | Phi() : SExpr(COP_Phi) {} |
1305 | 0 | Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} |
1306 | 0 | Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} |
1307 | | |
1308 | 2.21k | static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } |
1309 | | |
1310 | 0 | const ValArray &values() const { return Values; } |
1311 | 0 | ValArray &values() { return Values; } |
1312 | | |
1313 | 0 | Status status() const { return static_cast<Status>(Flags); } |
1314 | 0 | void setStatus(Status s) { Flags = s; } |
1315 | | |
1316 | | /// Return the clang declaration of the variable for this Phi node, if any. |
1317 | 0 | const ValueDecl *clangDecl() const { return Cvdecl; } |
1318 | | |
1319 | | /// Set the clang variable associated with this Phi node. |
1320 | 0 | void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; } |
1321 | | |
1322 | | template <class V> |
1323 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1324 | | typename V::template Container<typename V::R_SExpr> |
1325 | | Nvs(Vs, Values.size()); |
1326 | | |
1327 | | for (const auto *Val : Values) |
1328 | | Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); |
1329 | | return Vs.reducePhi(*this, Nvs); |
1330 | | } |
1331 | | |
1332 | | template <class C> |
1333 | 0 | typename C::CType compare(const Phi *E, C &Cmp) const { |
1334 | 0 | // TODO: implement CFG comparisons |
1335 | 0 | return Cmp.comparePointers(this, E); |
1336 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Phi::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Phi const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Phi::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Phi const*, clang::threadSafety::til::MatchComparator&) const |
1337 | | |
1338 | | private: |
1339 | | ValArray Values; |
1340 | | const ValueDecl* Cvdecl = nullptr; |
1341 | | }; |
1342 | | |
1343 | | /// Base class for basic block terminators: Branch, Goto, and Return. |
1344 | | class Terminator : public SExpr { |
1345 | | protected: |
1346 | 0 | Terminator(TIL_Opcode Op) : SExpr(Op) {} |
1347 | 0 | Terminator(const SExpr &E) : SExpr(E) {} |
1348 | | |
1349 | | public: |
1350 | 0 | static bool classof(const SExpr *E) { |
1351 | 0 | return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; |
1352 | 0 | } |
1353 | | |
1354 | | /// Return the list of basic blocks that this terminator can branch to. |
1355 | | ArrayRef<BasicBlock *> successors(); |
1356 | | |
1357 | 0 | ArrayRef<BasicBlock *> successors() const { |
1358 | 0 | return const_cast<Terminator*>(this)->successors(); |
1359 | 0 | } |
1360 | | }; |
1361 | | |
1362 | | /// Jump to another basic block. |
1363 | | /// A goto instruction is essentially a tail-recursive call into another |
1364 | | /// block. In addition to the block pointer, it specifies an index into the |
1365 | | /// phi nodes of that block. The index can be used to retrieve the "arguments" |
1366 | | /// of the call. |
1367 | | class Goto : public Terminator { |
1368 | | public: |
1369 | | Goto(BasicBlock *B, unsigned I) |
1370 | 0 | : Terminator(COP_Goto), TargetBlock(B), Index(I) {} |
1371 | | Goto(const Goto &G, BasicBlock *B, unsigned I) |
1372 | 0 | : Terminator(COP_Goto), TargetBlock(B), Index(I) {} |
1373 | | |
1374 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } |
1375 | | |
1376 | 0 | const BasicBlock *targetBlock() const { return TargetBlock; } |
1377 | 0 | BasicBlock *targetBlock() { return TargetBlock; } |
1378 | | |
1379 | | /// Returns the index into the |
1380 | 0 | unsigned index() const { return Index; } |
1381 | | |
1382 | | /// Return the list of basic blocks that this terminator can branch to. |
1383 | 0 | ArrayRef<BasicBlock *> successors() { return TargetBlock; } |
1384 | | |
1385 | | template <class V> |
1386 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1387 | | BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); |
1388 | | return Vs.reduceGoto(*this, Ntb); |
1389 | | } |
1390 | | |
1391 | | template <class C> |
1392 | 0 | typename C::CType compare(const Goto *E, C &Cmp) const { |
1393 | 0 | // TODO: implement CFG comparisons |
1394 | 0 | return Cmp.comparePointers(this, E); |
1395 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Goto::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Goto const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Goto::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Goto const*, clang::threadSafety::til::MatchComparator&) const |
1396 | | |
1397 | | private: |
1398 | | BasicBlock *TargetBlock; |
1399 | | unsigned Index; |
1400 | | }; |
1401 | | |
1402 | | /// A conditional branch to two other blocks. |
1403 | | /// Note that unlike Goto, Branch does not have an index. The target blocks |
1404 | | /// must be child-blocks, and cannot have Phi nodes. |
1405 | | class Branch : public Terminator { |
1406 | | public: |
1407 | | Branch(SExpr *C, BasicBlock *T, BasicBlock *E) |
1408 | 0 | : Terminator(COP_Branch), Condition(C) { |
1409 | 0 | Branches[0] = T; |
1410 | 0 | Branches[1] = E; |
1411 | 0 | } |
1412 | | |
1413 | | Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) |
1414 | 0 | : Terminator(Br), Condition(C) { |
1415 | 0 | Branches[0] = T; |
1416 | 0 | Branches[1] = E; |
1417 | 0 | } |
1418 | | |
1419 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } |
1420 | | |
1421 | 0 | const SExpr *condition() const { return Condition; } |
1422 | 0 | SExpr *condition() { return Condition; } |
1423 | | |
1424 | 0 | const BasicBlock *thenBlock() const { return Branches[0]; } |
1425 | 0 | BasicBlock *thenBlock() { return Branches[0]; } |
1426 | | |
1427 | 0 | const BasicBlock *elseBlock() const { return Branches[1]; } |
1428 | 0 | BasicBlock *elseBlock() { return Branches[1]; } |
1429 | | |
1430 | | /// Return the list of basic blocks that this terminator can branch to. |
1431 | 0 | ArrayRef<BasicBlock*> successors() { |
1432 | 0 | return llvm::makeArrayRef(Branches); |
1433 | 0 | } |
1434 | | |
1435 | | template <class V> |
1436 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1437 | | auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); |
1438 | | BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); |
1439 | | BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); |
1440 | | return Vs.reduceBranch(*this, Nc, Ntb, Nte); |
1441 | | } |
1442 | | |
1443 | | template <class C> |
1444 | 0 | typename C::CType compare(const Branch *E, C &Cmp) const { |
1445 | 0 | // TODO: implement CFG comparisons |
1446 | 0 | return Cmp.comparePointers(this, E); |
1447 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Branch::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Branch const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Branch::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Branch const*, clang::threadSafety::til::MatchComparator&) const |
1448 | | |
1449 | | private: |
1450 | | SExpr *Condition; |
1451 | | BasicBlock *Branches[2]; |
1452 | | }; |
1453 | | |
1454 | | /// Return from the enclosing function, passing the return value to the caller. |
1455 | | /// Only the exit block should end with a return statement. |
1456 | | class Return : public Terminator { |
1457 | | public: |
1458 | 0 | Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} |
1459 | 0 | Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} |
1460 | | |
1461 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } |
1462 | | |
1463 | | /// Return an empty list. |
1464 | 0 | ArrayRef<BasicBlock *> successors() { return None; } |
1465 | | |
1466 | 0 | SExpr *returnValue() { return Retval; } |
1467 | 0 | const SExpr *returnValue() const { return Retval; } |
1468 | | |
1469 | | template <class V> |
1470 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1471 | | auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); |
1472 | | return Vs.reduceReturn(*this, Ne); |
1473 | | } |
1474 | | |
1475 | | template <class C> |
1476 | 0 | typename C::CType compare(const Return *E, C &Cmp) const { |
1477 | 0 | return Cmp.compare(Retval, E->Retval); |
1478 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Return::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Return const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Return::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Return const*, clang::threadSafety::til::MatchComparator&) const |
1479 | | |
1480 | | private: |
1481 | | SExpr* Retval; |
1482 | | }; |
1483 | | |
1484 | | inline ArrayRef<BasicBlock*> Terminator::successors() { |
1485 | | switch (opcode()) { |
1486 | | case COP_Goto: return cast<Goto>(this)->successors(); |
1487 | | case COP_Branch: return cast<Branch>(this)->successors(); |
1488 | | case COP_Return: return cast<Return>(this)->successors(); |
1489 | | default: |
1490 | | return None; |
1491 | | } |
1492 | | } |
1493 | | |
1494 | | /// A basic block is part of an SCFG. It can be treated as a function in |
1495 | | /// continuation passing style. A block consists of a sequence of phi nodes, |
1496 | | /// which are "arguments" to the function, followed by a sequence of |
1497 | | /// instructions. It ends with a Terminator, which is a Branch or Goto to |
1498 | | /// another basic block in the same SCFG. |
1499 | | class BasicBlock : public SExpr { |
1500 | | public: |
1501 | | using InstrArray = SimpleArray<SExpr *>; |
1502 | | using BlockArray = SimpleArray<BasicBlock *>; |
1503 | | |
1504 | | // TopologyNodes are used to overlay tree structures on top of the CFG, |
1505 | | // such as dominator and postdominator trees. Each block is assigned an |
1506 | | // ID in the tree according to a depth-first search. Tree traversals are |
1507 | | // always up, towards the parents. |
1508 | | struct TopologyNode { |
1509 | | int NodeID = 0; |
1510 | | |
1511 | | // Includes this node, so must be > 1. |
1512 | | int SizeOfSubTree = 0; |
1513 | | |
1514 | | // Pointer to parent. |
1515 | | BasicBlock *Parent = nullptr; |
1516 | | |
1517 | 0 | TopologyNode() = default; |
1518 | | |
1519 | 0 | bool isParentOf(const TopologyNode& OtherNode) { |
1520 | 0 | return OtherNode.NodeID > NodeID && |
1521 | 0 | OtherNode.NodeID < NodeID + SizeOfSubTree; |
1522 | 0 | } |
1523 | | |
1524 | 0 | bool isParentOfOrEqual(const TopologyNode& OtherNode) { |
1525 | 0 | return OtherNode.NodeID >= NodeID && |
1526 | 0 | OtherNode.NodeID < NodeID + SizeOfSubTree; |
1527 | 0 | } |
1528 | | }; |
1529 | | |
1530 | | explicit BasicBlock(MemRegionRef A) |
1531 | 0 | : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {} |
1532 | | BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, |
1533 | | Terminator *T) |
1534 | | : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false), |
1535 | 0 | Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} |
1536 | | |
1537 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } |
1538 | | |
1539 | | /// Returns the block ID. Every block has a unique ID in the CFG. |
1540 | 0 | int blockID() const { return BlockID; } |
1541 | | |
1542 | | /// Returns the number of predecessors. |
1543 | 0 | size_t numPredecessors() const { return Predecessors.size(); } |
1544 | 0 | size_t numSuccessors() const { return successors().size(); } |
1545 | | |
1546 | 0 | const SCFG* cfg() const { return CFGPtr; } |
1547 | 0 | SCFG* cfg() { return CFGPtr; } |
1548 | | |
1549 | 0 | const BasicBlock *parent() const { return DominatorNode.Parent; } |
1550 | 0 | BasicBlock *parent() { return DominatorNode.Parent; } |
1551 | | |
1552 | 0 | const InstrArray &arguments() const { return Args; } |
1553 | 0 | InstrArray &arguments() { return Args; } |
1554 | | |
1555 | 0 | InstrArray &instructions() { return Instrs; } |
1556 | 0 | const InstrArray &instructions() const { return Instrs; } |
1557 | | |
1558 | | /// Returns a list of predecessors. |
1559 | | /// The order of predecessors in the list is important; each phi node has |
1560 | | /// exactly one argument for each precessor, in the same order. |
1561 | 0 | BlockArray &predecessors() { return Predecessors; } |
1562 | 0 | const BlockArray &predecessors() const { return Predecessors; } |
1563 | | |
1564 | 0 | ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } |
1565 | 0 | ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } |
1566 | | |
1567 | 0 | const Terminator *terminator() const { return TermInstr; } |
1568 | 0 | Terminator *terminator() { return TermInstr; } |
1569 | | |
1570 | 0 | void setTerminator(Terminator *E) { TermInstr = E; } |
1571 | | |
1572 | 0 | bool Dominates(const BasicBlock &Other) { |
1573 | 0 | return DominatorNode.isParentOfOrEqual(Other.DominatorNode); |
1574 | 0 | } |
1575 | | |
1576 | 0 | bool PostDominates(const BasicBlock &Other) { |
1577 | 0 | return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); |
1578 | 0 | } |
1579 | | |
1580 | | /// Add a new argument. |
1581 | 0 | void addArgument(Phi *V) { |
1582 | 0 | Args.reserveCheck(1, Arena); |
1583 | 0 | Args.push_back(V); |
1584 | 0 | } |
1585 | | |
1586 | | /// Add a new instruction. |
1587 | 0 | void addInstruction(SExpr *V) { |
1588 | 0 | Instrs.reserveCheck(1, Arena); |
1589 | 0 | Instrs.push_back(V); |
1590 | 0 | } |
1591 | | |
1592 | | // Add a new predecessor, and return the phi-node index for it. |
1593 | | // Will add an argument to all phi-nodes, initialized to nullptr. |
1594 | | unsigned addPredecessor(BasicBlock *Pred); |
1595 | | |
1596 | | // Reserve space for Nargs arguments. |
1597 | 0 | void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } |
1598 | | |
1599 | | // Reserve space for Nins instructions. |
1600 | 0 | void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } |
1601 | | |
1602 | | // Reserve space for NumPreds predecessors, including space in phi nodes. |
1603 | | void reservePredecessors(unsigned NumPreds); |
1604 | | |
1605 | | /// Return the index of BB, or Predecessors.size if BB is not a predecessor. |
1606 | 0 | unsigned findPredecessorIndex(const BasicBlock *BB) const { |
1607 | 0 | auto I = llvm::find(Predecessors, BB); |
1608 | 0 | return std::distance(Predecessors.cbegin(), I); |
1609 | 0 | } |
1610 | | |
1611 | | template <class V> |
1612 | | typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { |
1613 | | typename V::template Container<SExpr*> Nas(Vs, Args.size()); |
1614 | | typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); |
1615 | | |
1616 | | // Entering the basic block should do any scope initialization. |
1617 | | Vs.enterBasicBlock(*this); |
1618 | | |
1619 | | for (const auto *E : Args) { |
1620 | | auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); |
1621 | | Nas.push_back(Ne); |
1622 | | } |
1623 | | for (const auto *E : Instrs) { |
1624 | | auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); |
1625 | | Nis.push_back(Ne); |
1626 | | } |
1627 | | auto Nt = Vs.traverse(TermInstr, Ctx); |
1628 | | |
1629 | | // Exiting the basic block should handle any scope cleanup. |
1630 | | Vs.exitBasicBlock(*this); |
1631 | | |
1632 | | return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); |
1633 | | } |
1634 | | |
1635 | | template <class C> |
1636 | 0 | typename C::CType compare(const BasicBlock *E, C &Cmp) const { |
1637 | 0 | // TODO: implement CFG comparisons |
1638 | 0 | return Cmp.comparePointers(this, E); |
1639 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::BasicBlock::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::BasicBlock const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::BasicBlock::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::BasicBlock const*, clang::threadSafety::til::MatchComparator&) const |
1640 | | |
1641 | | private: |
1642 | | friend class SCFG; |
1643 | | |
1644 | | // assign unique ids to all instructions |
1645 | | unsigned renumberInstrs(unsigned id); |
1646 | | |
1647 | | unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); |
1648 | | unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); |
1649 | | void computeDominator(); |
1650 | | void computePostDominator(); |
1651 | | |
1652 | | // The arena used to allocate this block. |
1653 | | MemRegionRef Arena; |
1654 | | |
1655 | | // The CFG that contains this block. |
1656 | | SCFG *CFGPtr = nullptr; |
1657 | | |
1658 | | // Unique ID for this BB in the containing CFG. IDs are in topological order. |
1659 | | unsigned BlockID : 31; |
1660 | | |
1661 | | // Bit to determine if a block has been visited during a traversal. |
1662 | | bool Visited : 1; |
1663 | | |
1664 | | // Predecessor blocks in the CFG. |
1665 | | BlockArray Predecessors; |
1666 | | |
1667 | | // Phi nodes. One argument per predecessor. |
1668 | | InstrArray Args; |
1669 | | |
1670 | | // Instructions. |
1671 | | InstrArray Instrs; |
1672 | | |
1673 | | // Terminating instruction. |
1674 | | Terminator *TermInstr = nullptr; |
1675 | | |
1676 | | // The dominator tree. |
1677 | | TopologyNode DominatorNode; |
1678 | | |
1679 | | // The post-dominator tree. |
1680 | | TopologyNode PostDominatorNode; |
1681 | | }; |
1682 | | |
1683 | | /// An SCFG is a control-flow graph. It consists of a set of basic blocks, |
1684 | | /// each of which terminates in a branch to another basic block. There is one |
1685 | | /// entry point, and one exit point. |
1686 | | class SCFG : public SExpr { |
1687 | | public: |
1688 | | using BlockArray = SimpleArray<BasicBlock *>; |
1689 | | using iterator = BlockArray::iterator; |
1690 | | using const_iterator = BlockArray::const_iterator; |
1691 | | |
1692 | | SCFG(MemRegionRef A, unsigned Nblocks) |
1693 | 0 | : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) { |
1694 | 0 | Entry = new (A) BasicBlock(A); |
1695 | 0 | Exit = new (A) BasicBlock(A); |
1696 | 0 | auto *V = new (A) Phi(); |
1697 | 0 | Exit->addArgument(V); |
1698 | 0 | Exit->setTerminator(new (A) Return(V)); |
1699 | 0 | add(Entry); |
1700 | 0 | add(Exit); |
1701 | 0 | } |
1702 | | |
1703 | | SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba |
1704 | 0 | : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) { |
1705 | 0 | // TODO: set entry and exit! |
1706 | 0 | } |
1707 | | |
1708 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } |
1709 | | |
1710 | | /// Return true if this CFG is valid. |
1711 | 0 | bool valid() const { return Entry && Exit && Blocks.size() > 0; } |
1712 | | |
1713 | | /// Return true if this CFG has been normalized. |
1714 | | /// After normalization, blocks are in topological order, and block and |
1715 | | /// instruction IDs have been assigned. |
1716 | 0 | bool normal() const { return Normal; } |
1717 | | |
1718 | 0 | iterator begin() { return Blocks.begin(); } |
1719 | 0 | iterator end() { return Blocks.end(); } |
1720 | | |
1721 | 0 | const_iterator begin() const { return cbegin(); } |
1722 | 0 | const_iterator end() const { return cend(); } |
1723 | | |
1724 | 0 | const_iterator cbegin() const { return Blocks.cbegin(); } |
1725 | 0 | const_iterator cend() const { return Blocks.cend(); } |
1726 | | |
1727 | 0 | const BasicBlock *entry() const { return Entry; } |
1728 | 0 | BasicBlock *entry() { return Entry; } |
1729 | 0 | const BasicBlock *exit() const { return Exit; } |
1730 | 0 | BasicBlock *exit() { return Exit; } |
1731 | | |
1732 | | /// Return the number of blocks in the CFG. |
1733 | | /// Block::blockID() will return a number less than numBlocks(); |
1734 | 0 | size_t numBlocks() const { return Blocks.size(); } |
1735 | | |
1736 | | /// Return the total number of instructions in the CFG. |
1737 | | /// This is useful for building instruction side-tables; |
1738 | | /// A call to SExpr::id() will return a number less than numInstructions(). |
1739 | 0 | unsigned numInstructions() { return NumInstructions; } |
1740 | | |
1741 | 0 | inline void add(BasicBlock *BB) { |
1742 | 0 | assert(BB->CFGPtr == nullptr); |
1743 | 0 | BB->CFGPtr = this; |
1744 | 0 | Blocks.reserveCheck(1, Arena); |
1745 | 0 | Blocks.push_back(BB); |
1746 | 0 | } |
1747 | | |
1748 | 0 | void setEntry(BasicBlock *BB) { Entry = BB; } |
1749 | 0 | void setExit(BasicBlock *BB) { Exit = BB; } |
1750 | | |
1751 | | void computeNormalForm(); |
1752 | | |
1753 | | template <class V> |
1754 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1755 | | Vs.enterCFG(*this); |
1756 | | typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); |
1757 | | |
1758 | | for (const auto *B : Blocks) { |
1759 | | Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); |
1760 | | } |
1761 | | Vs.exitCFG(*this); |
1762 | | return Vs.reduceSCFG(*this, Bbs); |
1763 | | } |
1764 | | |
1765 | | template <class C> |
1766 | 0 | typename C::CType compare(const SCFG *E, C &Cmp) const { |
1767 | 0 | // TODO: implement CFG comparisons |
1768 | 0 | return Cmp.comparePointers(this, E); |
1769 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SCFG::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SCFG const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SCFG::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SCFG const*, clang::threadSafety::til::MatchComparator&) const |
1770 | | |
1771 | | private: |
1772 | | // assign unique ids to all instructions |
1773 | | void renumberInstrs(); |
1774 | | |
1775 | | MemRegionRef Arena; |
1776 | | BlockArray Blocks; |
1777 | | BasicBlock *Entry = nullptr; |
1778 | | BasicBlock *Exit = nullptr; |
1779 | | unsigned NumInstructions = 0; |
1780 | | bool Normal = false; |
1781 | | }; |
1782 | | |
1783 | | /// An identifier, e.g. 'foo' or 'x'. |
1784 | | /// This is a pseduo-term; it will be lowered to a variable or projection. |
1785 | | class Identifier : public SExpr { |
1786 | | public: |
1787 | 0 | Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {} |
1788 | | Identifier(const Identifier &) = default; |
1789 | | |
1790 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } |
1791 | | |
1792 | 0 | StringRef name() const { return Name; } |
1793 | | |
1794 | | template <class V> |
1795 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1796 | | return Vs.reduceIdentifier(*this); |
1797 | | } |
1798 | | |
1799 | | template <class C> |
1800 | 0 | typename C::CType compare(const Identifier* E, C& Cmp) const { |
1801 | 0 | return Cmp.compareStrings(name(), E->name()); |
1802 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Identifier::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Identifier const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Identifier::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Identifier const*, clang::threadSafety::til::MatchComparator&) const |
1803 | | |
1804 | | private: |
1805 | | StringRef Name; |
1806 | | }; |
1807 | | |
1808 | | /// An if-then-else expression. |
1809 | | /// This is a pseduo-term; it will be lowered to a branch in a CFG. |
1810 | | class IfThenElse : public SExpr { |
1811 | | public: |
1812 | | IfThenElse(SExpr *C, SExpr *T, SExpr *E) |
1813 | 24 | : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {} |
1814 | | IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) |
1815 | 0 | : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {} |
1816 | | |
1817 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } |
1818 | | |
1819 | 0 | SExpr *condition() { return Condition; } // Address to store to |
1820 | 224 | const SExpr *condition() const { return Condition; } |
1821 | | |
1822 | 0 | SExpr *thenExpr() { return ThenExpr; } // Value to store |
1823 | 224 | const SExpr *thenExpr() const { return ThenExpr; } |
1824 | | |
1825 | 0 | SExpr *elseExpr() { return ElseExpr; } // Value to store |
1826 | 216 | const SExpr *elseExpr() const { return ElseExpr; } |
1827 | | |
1828 | | template <class V> |
1829 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1830 | | auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); |
1831 | | auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); |
1832 | | auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); |
1833 | | return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); |
1834 | | } |
1835 | | |
1836 | | template <class C> |
1837 | 108 | typename C::CType compare(const IfThenElse* E, C& Cmp) const { |
1838 | 108 | typename C::CType Ct = Cmp.compare(condition(), E->condition()); |
1839 | 108 | if (Cmp.notTrue(Ct)) |
1840 | 0 | return Ct; |
1841 | 108 | Ct = Cmp.compare(thenExpr(), E->thenExpr()); |
1842 | 108 | if (Cmp.notTrue(Ct)) |
1843 | 4 | return Ct; |
1844 | 104 | return Cmp.compare(elseExpr(), E->elseExpr()); |
1845 | 104 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::IfThenElse::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::IfThenElse const*, clang::threadSafety::til::EqualsComparator&) const clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::IfThenElse::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::IfThenElse const*, clang::threadSafety::til::MatchComparator&) const Line | Count | Source | 1837 | 108 | typename C::CType compare(const IfThenElse* E, C& Cmp) const { | 1838 | 108 | typename C::CType Ct = Cmp.compare(condition(), E->condition()); | 1839 | 108 | if (Cmp.notTrue(Ct)) | 1840 | 0 | return Ct; | 1841 | 108 | Ct = Cmp.compare(thenExpr(), E->thenExpr()); | 1842 | 108 | if (Cmp.notTrue(Ct)) | 1843 | 4 | return Ct; | 1844 | 104 | return Cmp.compare(elseExpr(), E->elseExpr()); | 1845 | 104 | } |
|
1846 | | |
1847 | | private: |
1848 | | SExpr* Condition; |
1849 | | SExpr* ThenExpr; |
1850 | | SExpr* ElseExpr; |
1851 | | }; |
1852 | | |
1853 | | /// A let-expression, e.g. let x=t; u. |
1854 | | /// This is a pseduo-term; it will be lowered to instructions in a CFG. |
1855 | | class Let : public SExpr { |
1856 | | public: |
1857 | 0 | Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { |
1858 | 0 | Vd->setKind(Variable::VK_Let); |
1859 | 0 | } |
1860 | | |
1861 | 0 | Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { |
1862 | 0 | Vd->setKind(Variable::VK_Let); |
1863 | 0 | } |
1864 | | |
1865 | 0 | static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } |
1866 | | |
1867 | 0 | Variable *variableDecl() { return VarDecl; } |
1868 | 0 | const Variable *variableDecl() const { return VarDecl; } |
1869 | | |
1870 | 0 | SExpr *body() { return Body; } |
1871 | 0 | const SExpr *body() const { return Body; } |
1872 | | |
1873 | | template <class V> |
1874 | | typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { |
1875 | | // This is a variable declaration, so traverse the definition. |
1876 | | auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); |
1877 | | // Tell the rewriter to enter the scope of the let variable. |
1878 | | Variable *Nvd = Vs.enterScope(*VarDecl, E0); |
1879 | | auto E1 = Vs.traverse(Body, Ctx); |
1880 | | Vs.exitScope(*VarDecl); |
1881 | | return Vs.reduceLet(*this, Nvd, E1); |
1882 | | } |
1883 | | |
1884 | | template <class C> |
1885 | 0 | typename C::CType compare(const Let* E, C& Cmp) const { |
1886 | 0 | typename C::CType Ct = |
1887 | 0 | Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); |
1888 | 0 | if (Cmp.notTrue(Ct)) |
1889 | 0 | return Ct; |
1890 | 0 | Cmp.enterScope(variableDecl(), E->variableDecl()); |
1891 | 0 | Ct = Cmp.compare(body(), E->body()); |
1892 | 0 | Cmp.leaveScope(); |
1893 | 0 | return Ct; |
1894 | 0 | } Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Let::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Let const*, clang::threadSafety::til::EqualsComparator&) const Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Let::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Let const*, clang::threadSafety::til::MatchComparator&) const |
1895 | | |
1896 | | private: |
1897 | | Variable *VarDecl; |
1898 | | SExpr* Body; |
1899 | | }; |
1900 | | |
1901 | | const SExpr *getCanonicalVal(const SExpr *E); |
1902 | | SExpr* simplifyToCanonicalVal(SExpr *E); |
1903 | | void simplifyIncompleteArg(til::Phi *Ph); |
1904 | | |
1905 | | } // namespace til |
1906 | | } // namespace threadSafety |
1907 | | |
1908 | | } // namespace clang |
1909 | | |
1910 | | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H |