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
65namespace clang {
66
67class CallExpr;
68class Expr;
69class Stmt;
70
71namespace threadSafety {
72namespace til {
73
74class BasicBlock;
75
76/// Enum for the different distinct classes of SExpr
77enum 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.
84enum TIL_UnaryOpcode : unsigned char {
85 UOP_Minus, // -
86 UOP_BitNot, // ~
87 UOP_LogicNot // !
88};
89
90/// Opcode for binary arithmetic operations.
91enum 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.
112enum 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
131const TIL_Opcode COP_Min = COP_Future;
132const TIL_Opcode COP_Max = COP_Branch;
133const TIL_UnaryOpcode UOP_Min = UOP_Minus;
134const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
135const TIL_BinaryOpcode BOP_Min = BOP_Add;
136const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
137const TIL_CastOpcode CAST_Min = CAST_none;
138const TIL_CastOpcode CAST_Max = CAST_toInt;
139
140/// Return the name of a unary opcode.
141StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
142
143/// Return the name of a binary opcode.
144StringRef 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.
152struct 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
189inline 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
200template<>
201inline ValueType ValueType::getValueType<void>() {
202 return ValueType(BT_Void, ST_0, false, 0);
203}
204
205template<>
206inline ValueType ValueType::getValueType<bool>() {
207 return ValueType(BT_Bool, ST_1, false, 0);
208}
209
210template<>
211inline ValueType ValueType::getValueType<int8_t>() {
212 return ValueType(BT_Int, ST_8, true, 0);
213}
214
215template<>
216inline ValueType ValueType::getValueType<uint8_t>() {
217 return ValueType(BT_Int, ST_8, false, 0);
218}
219
220template<>
221inline ValueType ValueType::getValueType<int16_t>() {
222 return ValueType(BT_Int, ST_16, true, 0);
223}
224
225template<>
226inline ValueType ValueType::getValueType<uint16_t>() {
227 return ValueType(BT_Int, ST_16, false, 0);
228}
229
230template<>
231inline ValueType ValueType::getValueType<int32_t>() {
232 return ValueType(BT_Int, ST_32, true, 0);
233}
234
235template<>
236inline ValueType ValueType::getValueType<uint32_t>() {
237 return ValueType(BT_Int, ST_32, false, 0);
238}
239
240template<>
241inline ValueType ValueType::getValueType<int64_t>() {
242 return ValueType(BT_Int, ST_64, true, 0);
243}
244
245template<>
246inline ValueType ValueType::getValueType<uint64_t>() {
247 return ValueType(BT_Int, ST_64, false, 0);
248}
249
250template<>
251inline ValueType ValueType::getValueType<float>() {
252 return ValueType(BT_Float, ST_32, true, 0);
253}
254
255template<>
256inline ValueType ValueType::getValueType<double>() {
257 return ValueType(BT_Float, ST_64, true, 0);
258}
259
260template<>
261inline ValueType ValueType::getValueType<long double>() {
262 return ValueType(BT_Float, ST_128, true, 0);
263}
264
265template<>
266inline ValueType ValueType::getValueType<StringRef>() {
267 return ValueType(BT_String, getSizeType(nbytes: sizeof(StringRef)), false, 0);
268}
269
270template<>
271inline 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.
276class SExpr {
277public:
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
319protected:
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.
332namespace ThreadSafetyTIL {
333
334inline 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.
355class Variable : public SExpr {
356public:
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
417private:
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.
435class Future : public SExpr {
436public:
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
479private:
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.
487class Undefined : public SExpr {
488public:
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
508private:
509 const Stmt *Cstmt;
510};
511
512/// Placeholder for a wildcard that matches any other expression.
513class Wildcard : public SExpr {
514public:
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
530template <class T> class LiteralT;
531
532// Base class for literal values.
533class Literal : public SExpr {
534public:
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
562private:
563 const ValueType ValType;
564 const Expr *Cexpr = nullptr;
565};
566
567// Derived class for literal values, which stores the actual value.
568template<class T>
569class LiteralT : public Literal {
570public:
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
581private:
582 T Val;
583};
584
585template <class V>
586typename 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.
643class LiteralPtr : public SExpr {
644public:
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
666private:
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 })))
673class Function : public SExpr {
674public:
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
716private:
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.
724class SFunction : public SExpr {
725public:
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
768private:
769 Variable *VarDecl;
770 SExpr* Body;
771};
772
773/// A block of code -- e.g. the body of a function.
774class Code : public SExpr {
775public:
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
803private:
804 SExpr* ReturnType;
805 SExpr* Body;
806};
807
808/// A typed, writable location in memory
809class Field : public SExpr {
810public:
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
838private:
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.
848class Apply : public SExpr {
849public:
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
877private:
878 SExpr* Fun;
879 SExpr* Arg;
880};
881
882/// Apply a self-argument to a self-applicable function.
883class SApply : public SExpr {
884public:
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
915private:
916 SExpr* Sfun;
917 SExpr* Arg;
918};
919
920/// Project a named slot from a C++ struct or class.
921class Project : public SExpr {
922public:
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
967private:
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).
974class Call : public SExpr {
975public:
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
998private:
999 SExpr* Target;
1000 const CallExpr *Cexpr;
1001};
1002
1003/// Allocate memory for a new value on the heap or stack.
1004class Alloc : public SExpr {
1005public:
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
1035private:
1036 SExpr* Dtype;
1037};
1038
1039/// Load a value from memory.
1040class Load : public SExpr {
1041public:
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
1061private:
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.
1067class Store : public SExpr {
1068public:
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
1095private:
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.
1102class ArrayIndex : public SExpr {
1103public:
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
1131private:
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.
1139class ArrayAdd : public SExpr {
1140public:
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
1168private:
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.
1175class UnaryOp : public SExpr {
1176public:
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
1207private:
1208 SExpr* Expr0;
1209};
1210
1211/// Simple arithmetic binary operations, e.g. +, -, etc.
1212/// These operations have no side effects.
1213class BinaryOp : public SExpr {
1214public:
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
1256private:
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.
1264class Cast : public SExpr {
1265public:
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
1293private:
1294 SExpr* Expr0;
1295};
1296
1297class 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.
1302class Phi : public SExpr {
1303public:
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
1349private:
1350 ValArray Values;
1351 const ValueDecl* Cvdecl = nullptr;
1352};
1353
1354/// Base class for basic block terminators: Branch, Goto, and Return.
1355class Terminator : public SExpr {
1356protected:
1357 Terminator(TIL_Opcode Op) : SExpr(Op) {}
1358 Terminator(const SExpr &E) : SExpr(E) {}
1359
1360public:
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.
1378class Goto : public Terminator {
1379public:
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
1408private:
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.
1416class Branch : public Terminator {
1417public:
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
1458private:
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.
1465class Return : public Terminator {
1466public:
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
1489private:
1490 SExpr* Retval;
1491};
1492
1493inline 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.
1508class BasicBlock : public SExpr {
1509public:
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
1650private:
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.
1695class SCFG : public SExpr {
1696public:
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
1780private:
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.
1794class Identifier : public SExpr {
1795public:
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
1813private:
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.
1819class IfThenElse : public SExpr {
1820public:
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
1856private:
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.
1864class Let : public SExpr {
1865public:
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
1905private:
1906 Variable *VarDecl;
1907 SExpr* Body;
1908};
1909
1910const SExpr *getCanonicalVal(const SExpr *E);
1911SExpr* simplifyToCanonicalVal(SExpr *E);
1912void 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

source code of clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h