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