1 //===- ThreadSafetyTIL.h ----------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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.
15 // Thread safety analysis works by comparing mutex expressions, e.g.
17 // class A { Mutex mu; int dat GUARDED_BY(this->mu); }
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)
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:
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
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.
42 // UNDER CONSTRUCTION. USE AT YOUR OWN RISK.
44 //===----------------------------------------------------------------------===//
46 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
47 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
49 #include "clang/AST/Decl.h"
50 #include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
51 #include "clang/Basic/LLVM.h"
52 #include "llvm/ADT/ArrayRef.h"
53 #include "llvm/ADT/None.h"
54 #include "llvm/ADT/Optional.h"
55 #include "llvm/ADT/StringRef.h"
56 #include "llvm/Support/Casting.h"
57 #include "llvm/Support/raw_ostream.h"
72 namespace threadSafety {
77 /// Enum for the different distinct classes of SExpr
79 #define TIL_OPCODE_DEF(X) COP_##X,
80 #include "ThreadSafetyOps.def"
84 /// Opcode for unary arithmetic operations.
85 enum TIL_UnaryOpcode : unsigned char {
91 /// Opcode for binary arithmetic operations.
92 enum TIL_BinaryOpcode : unsigned char {
108 BOP_LogicAnd, // && (no short-circuit)
109 BOP_LogicOr // || (no short-circuit)
112 /// Opcode for cast operations.
113 enum TIL_CastOpcode : unsigned char {
116 // Extend precision of numeric type
119 // Truncate precision of numeric type
122 // Convert to floating point type
125 // Convert to integer type
128 // Convert smart pointer to pointer (C++ only)
132 const TIL_Opcode COP_Min = COP_Future;
133 const TIL_Opcode COP_Max = COP_Branch;
134 const TIL_UnaryOpcode UOP_Min = UOP_Minus;
135 const TIL_UnaryOpcode UOP_Max = UOP_LogicNot;
136 const TIL_BinaryOpcode BOP_Min = BOP_Add;
137 const TIL_BinaryOpcode BOP_Max = BOP_LogicOr;
138 const TIL_CastOpcode CAST_Min = CAST_none;
139 const TIL_CastOpcode CAST_Max = CAST_toInt;
141 /// Return the name of a unary opcode.
142 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
144 /// Return the name of a binary opcode.
145 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
147 /// ValueTypes are data types that can actually be held in registers.
148 /// All variables and expressions must have a value type.
149 /// Pointer types are further subdivided into the various heap-allocated
150 /// types, such as functions, records, etc.
151 /// Structured types that are passed by value (e.g. complex numbers)
152 /// require special handling; they use BT_ValueRef, and size ST_0.
154 enum BaseType : unsigned char {
159 BT_String, // String literals
164 enum SizeType : unsigned char {
174 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
175 : Base(B), Size(Sz), Signed(S), VectSize(VS) {}
177 inline static SizeType getSizeType(unsigned nbytes);
180 inline static ValueType getValueType();
186 // 0 for scalar, otherwise num elements in vector
187 unsigned char VectSize;
190 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
193 case 2: return ST_16;
194 case 4: return ST_32;
195 case 8: return ST_64;
196 case 16: return ST_128;
197 default: return ST_0;
202 inline ValueType ValueType::getValueType<void>() {
203 return ValueType(BT_Void, ST_0, false, 0);
207 inline ValueType ValueType::getValueType<bool>() {
208 return ValueType(BT_Bool, ST_1, false, 0);
212 inline ValueType ValueType::getValueType<int8_t>() {
213 return ValueType(BT_Int, ST_8, true, 0);
217 inline ValueType ValueType::getValueType<uint8_t>() {
218 return ValueType(BT_Int, ST_8, false, 0);
222 inline ValueType ValueType::getValueType<int16_t>() {
223 return ValueType(BT_Int, ST_16, true, 0);
227 inline ValueType ValueType::getValueType<uint16_t>() {
228 return ValueType(BT_Int, ST_16, false, 0);
232 inline ValueType ValueType::getValueType<int32_t>() {
233 return ValueType(BT_Int, ST_32, true, 0);
237 inline ValueType ValueType::getValueType<uint32_t>() {
238 return ValueType(BT_Int, ST_32, false, 0);
242 inline ValueType ValueType::getValueType<int64_t>() {
243 return ValueType(BT_Int, ST_64, true, 0);
247 inline ValueType ValueType::getValueType<uint64_t>() {
248 return ValueType(BT_Int, ST_64, false, 0);
252 inline ValueType ValueType::getValueType<float>() {
253 return ValueType(BT_Float, ST_32, true, 0);
257 inline ValueType ValueType::getValueType<double>() {
258 return ValueType(BT_Float, ST_64, true, 0);
262 inline ValueType ValueType::getValueType<long double>() {
263 return ValueType(BT_Float, ST_128, true, 0);
267 inline ValueType ValueType::getValueType<StringRef>() {
268 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
272 inline ValueType ValueType::getValueType<void*>() {
273 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
276 /// Base class for AST nodes in the typed intermediate language.
281 TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
283 // Subclasses of SExpr must define the following:
285 // This(const This& E, ...) {
286 // copy constructor: construct copy of E, with some additional arguments.
289 // template <class V>
290 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
291 // traverse all subexpressions, following the traversal/rewriter interface.
294 // template <class C> typename C::CType compare(CType* E, C& Cmp) {
295 // compare all subexpressions, following the comparator interface
297 void *operator new(size_t S, MemRegionRef &R) {
298 return ::operator new(S, R);
301 /// SExpr objects must be created in an arena.
302 void *operator new(size_t) = delete;
304 /// SExpr objects cannot be deleted.
305 // This declaration is public to workaround a gcc bug that breaks building
306 // with REQUIRES_EH=1.
307 void operator delete(void *) = delete;
309 /// Returns the instruction ID for this expression.
310 /// All basic block instructions have a unique ID (i.e. virtual register).
311 unsigned id() const { return SExprID; }
313 /// Returns the block, if this is an instruction in a basic block,
314 /// otherwise returns null.
315 BasicBlock *block() const { return Block; }
317 /// Set the basic block and instruction ID for this expression.
318 void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
321 SExpr(TIL_Opcode Op) : Opcode(Op) {}
322 SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
324 const unsigned char Opcode;
325 unsigned char Reserved = 0;
326 unsigned short Flags = 0;
327 unsigned SExprID = 0;
328 BasicBlock *Block = nullptr;
331 // Contains various helper functions for SExprs.
332 namespace ThreadSafetyTIL {
334 inline bool isTrivial(const SExpr *E) {
335 unsigned Op = E->opcode();
336 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
339 } // namespace ThreadSafetyTIL
341 // Nodes which declare variables
343 /// A named variable, e.g. "x".
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)
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 {
361 /// Function parameter
364 /// SFunction (self) parameter
368 Variable(StringRef s, SExpr *D = nullptr)
369 : SExpr(COP_Variable), Name(s), Definition(D) {
373 Variable(SExpr *D, const ValueDecl *Cvd = nullptr)
374 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
375 Definition(D), Cvdecl(Cvd) {
379 Variable(const Variable &Vd, SExpr *D) // rewrite constructor
380 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
384 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
386 /// Return the kind of variable (let, function param, or self)
387 VariableKind kind() const { return static_cast<VariableKind>(Flags); }
389 /// Return the name of the variable, if any.
390 StringRef name() const { return Name; }
392 /// Return the clang declaration for this variable, if any.
393 const ValueDecl *clangDecl() const { return Cvdecl; }
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; }
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; }
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);
413 typename C::CType compare(const Variable* E, C& Cmp) const {
414 return Cmp.compareVariableRefs(this, E);
418 friend class BasicBlock;
419 friend class Function;
421 friend class SFunction;
423 // The name of the variable.
426 // The TIL type or definition.
429 // The clang declaration for this variable.
430 const ValueDecl *Cvdecl = nullptr;
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 {
443 Future() : SExpr(COP_Future) {}
444 virtual ~Future() = delete;
446 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
448 // A lazy rewriting strategy should subclass Future and override this method.
449 virtual SExpr *compute() { return nullptr; }
451 // Return the result of this future if it exists, otherwise return null.
452 SExpr *maybeGetResult() const { return Result; }
454 // Return the result of this future; forcing it if necessary.
460 return nullptr; // infinite loop; illegal recursion.
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);
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);
482 FutureStatus Status = FS_pending;
483 SExpr *Result = nullptr;
486 /// Placeholder for expressions that cannot be represented in the TIL.
487 class Undefined : public SExpr {
489 Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
490 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
492 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
495 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
496 return Vs.reduceUndefined(*this);
500 typename C::CType compare(const Undefined* E, C& Cmp) const {
501 return Cmp.trueResult();
508 /// Placeholder for a wildcard that matches any other expression.
509 class Wildcard : public SExpr {
511 Wildcard() : SExpr(COP_Wildcard) {}
512 Wildcard(const Wildcard &) = default;
514 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
516 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
517 return Vs.reduceWildcard(*this);
521 typename C::CType compare(const Wildcard* E, C& Cmp) const {
522 return Cmp.trueResult();
526 template <class T> class LiteralT;
528 // Base class for literal values.
529 class Literal : public SExpr {
531 Literal(const Expr *C)
532 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
533 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
534 Literal(const Literal &) = default;
536 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
538 // The clang expression for this literal.
539 const Expr *clangExpr() const { return Cexpr; }
541 ValueType valueType() const { return ValType; }
543 template<class T> const LiteralT<T>& as() const {
544 return *static_cast<const LiteralT<T>*>(this);
546 template<class T> LiteralT<T>& as() {
547 return *static_cast<LiteralT<T>*>(this);
550 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
553 typename C::CType compare(const Literal* E, C& Cmp) const {
554 // TODO: defer actual comparison to LiteralT
555 return Cmp.trueResult();
559 const ValueType ValType;
560 const Expr *Cexpr = nullptr;
563 // Derived class for literal values, which stores the actual value.
565 class LiteralT : public Literal {
567 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
568 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
570 T value() const { return Val;}
571 T& value() { return Val; }
578 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
580 return Vs.reduceLiteral(*this);
582 switch (ValType.Base) {
583 case ValueType::BT_Void:
585 case ValueType::BT_Bool:
586 return Vs.reduceLiteralT(as<bool>());
587 case ValueType::BT_Int: {
588 switch (ValType.Size) {
589 case ValueType::ST_8:
591 return Vs.reduceLiteralT(as<int8_t>());
593 return Vs.reduceLiteralT(as<uint8_t>());
594 case ValueType::ST_16:
596 return Vs.reduceLiteralT(as<int16_t>());
598 return Vs.reduceLiteralT(as<uint16_t>());
599 case ValueType::ST_32:
601 return Vs.reduceLiteralT(as<int32_t>());
603 return Vs.reduceLiteralT(as<uint32_t>());
604 case ValueType::ST_64:
606 return Vs.reduceLiteralT(as<int64_t>());
608 return Vs.reduceLiteralT(as<uint64_t>());
613 case ValueType::BT_Float: {
614 switch (ValType.Size) {
615 case ValueType::ST_32:
616 return Vs.reduceLiteralT(as<float>());
617 case ValueType::ST_64:
618 return Vs.reduceLiteralT(as<double>());
623 case ValueType::BT_String:
624 return Vs.reduceLiteralT(as<StringRef>());
625 case ValueType::BT_Pointer:
626 return Vs.reduceLiteralT(as<void*>());
627 case ValueType::BT_ValueRef:
630 return Vs.reduceLiteral(*this);
633 /// A Literal pointer to an object allocated in memory.
634 /// At compile time, pointer literals are represented by symbolic names.
635 class LiteralPtr : public SExpr {
637 LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
638 LiteralPtr(const LiteralPtr &) = default;
640 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
642 // The clang declaration for the value that this pointer points to.
643 const ValueDecl *clangDecl() const { return Cvdecl; }
646 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
647 return Vs.reduceLiteralPtr(*this);
651 typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
656 const ValueDecl *Cvdecl;
659 /// A function -- a.k.a. lambda abstraction.
660 /// Functions with multiple arguments are created by currying,
661 /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
662 class Function : public SExpr {
664 Function(Variable *Vd, SExpr *Bd)
665 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
666 Vd->setKind(Variable::VK_Fun);
669 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
670 : SExpr(F), VarDecl(Vd), Body(Bd) {
671 Vd->setKind(Variable::VK_Fun);
674 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
676 Variable *variableDecl() { return VarDecl; }
677 const Variable *variableDecl() const { return VarDecl; }
679 SExpr *body() { return Body; }
680 const SExpr *body() const { return Body; }
683 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
684 // This is a variable declaration, so traverse the definition.
685 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
686 // Tell the rewriter to enter the scope of the function.
687 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
688 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
689 Vs.exitScope(*VarDecl);
690 return Vs.reduceFunction(*this, Nvd, E1);
694 typename C::CType compare(const Function* E, C& Cmp) const {
695 typename C::CType Ct =
696 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
699 Cmp.enterScope(variableDecl(), E->variableDecl());
700 Ct = Cmp.compare(body(), E->body());
710 /// A self-applicable function.
711 /// A self-applicable function can be applied to itself. It's useful for
712 /// implementing objects and late binding.
713 class SFunction : public SExpr {
715 SFunction(Variable *Vd, SExpr *B)
716 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
717 assert(Vd->Definition == nullptr);
718 Vd->setKind(Variable::VK_SFun);
719 Vd->Definition = this;
722 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
723 : SExpr(F), VarDecl(Vd), Body(B) {
724 assert(Vd->Definition == nullptr);
725 Vd->setKind(Variable::VK_SFun);
726 Vd->Definition = this;
729 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
731 Variable *variableDecl() { return VarDecl; }
732 const Variable *variableDecl() const { return VarDecl; }
734 SExpr *body() { return Body; }
735 const SExpr *body() const { return Body; }
738 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
739 // A self-variable points to the SFunction itself.
740 // A rewrite must introduce the variable with a null definition, and update
741 // it after 'this' has been rewritten.
742 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
743 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
744 Vs.exitScope(*VarDecl);
745 // A rewrite operation will call SFun constructor to set Vvd->Definition.
746 return Vs.reduceSFunction(*this, Nvd, E1);
750 typename C::CType compare(const SFunction* E, C& Cmp) const {
751 Cmp.enterScope(variableDecl(), E->variableDecl());
752 typename C::CType Ct = Cmp.compare(body(), E->body());
762 /// A block of code -- e.g. the body of a function.
763 class Code : public SExpr {
765 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
766 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
767 : SExpr(C), ReturnType(T), Body(B) {}
769 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
771 SExpr *returnType() { return ReturnType; }
772 const SExpr *returnType() const { return ReturnType; }
774 SExpr *body() { return Body; }
775 const SExpr *body() const { return Body; }
778 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
779 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
780 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
781 return Vs.reduceCode(*this, Nt, Nb);
785 typename C::CType compare(const Code* E, C& Cmp) const {
786 typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
789 return Cmp.compare(body(), E->body());
797 /// A typed, writable location in memory
798 class Field : public SExpr {
800 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
801 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
802 : SExpr(C), Range(R), Body(B) {}
804 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
806 SExpr *range() { return Range; }
807 const SExpr *range() const { return Range; }
809 SExpr *body() { return Body; }
810 const SExpr *body() const { return Body; }
813 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
814 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
815 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx));
816 return Vs.reduceField(*this, Nr, Nb);
820 typename C::CType compare(const Field* E, C& Cmp) const {
821 typename C::CType Ct = Cmp.compare(range(), E->range());
824 return Cmp.compare(body(), E->body());
832 /// Apply an argument to a function.
833 /// Note that this does not actually call the function. Functions are curried,
834 /// so this returns a closure in which the first parameter has been applied.
835 /// Once all parameters have been applied, Call can be used to invoke the
837 class Apply : public SExpr {
839 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
840 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
841 : SExpr(A), Fun(F), Arg(Ar) {}
843 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
845 SExpr *fun() { return Fun; }
846 const SExpr *fun() const { return Fun; }
848 SExpr *arg() { return Arg; }
849 const SExpr *arg() const { return Arg; }
852 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
853 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
854 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
855 return Vs.reduceApply(*this, Nf, Na);
859 typename C::CType compare(const Apply* E, C& Cmp) const {
860 typename C::CType Ct = Cmp.compare(fun(), E->fun());
863 return Cmp.compare(arg(), E->arg());
871 /// Apply a self-argument to a self-applicable function.
872 class SApply : public SExpr {
874 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
875 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
876 : SExpr(A), Sfun(Sf), Arg(Ar) {}
878 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
880 SExpr *sfun() { return Sfun; }
881 const SExpr *sfun() const { return Sfun; }
883 SExpr *arg() { return Arg ? Arg : Sfun; }
884 const SExpr *arg() const { return Arg ? Arg : Sfun; }
886 bool isDelegation() const { return Arg != nullptr; }
889 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
890 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
891 typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
893 return Vs.reduceSApply(*this, Nf, Na);
897 typename C::CType compare(const SApply* E, C& Cmp) const {
898 typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899 if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
901 return Cmp.compare(arg(), E->arg());
909 /// Project a named slot from a C++ struct or class.
910 class Project : public SExpr {
912 Project(SExpr *R, const ValueDecl *Cvd)
913 : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
914 assert(Cvd && "ValueDecl must not be null");
917 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
919 SExpr *record() { return Rec; }
920 const SExpr *record() const { return Rec; }
922 const ValueDecl *clangDecl() const { return Cvdecl; }
924 bool isArrow() const { return (Flags & 0x01) != 0; }
926 void setArrow(bool b) {
927 if (b) Flags |= 0x01;
928 else Flags &= 0xFFFE;
931 StringRef slotName() const {
932 if (Cvdecl->getDeclName().isIdentifier())
933 return Cvdecl->getName();
936 llvm::raw_string_ostream OS(*SlotName);
937 Cvdecl->printName(OS);
943 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
944 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
945 return Vs.reduceProject(*this, Nr);
949 typename C::CType compare(const Project* E, C& Cmp) const {
950 typename C::CType Ct = Cmp.compare(record(), E->record());
953 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
958 mutable llvm::Optional<std::string> SlotName;
959 const ValueDecl *Cvdecl;
962 /// Call a function (after all arguments have been applied).
963 class Call : public SExpr {
965 Call(SExpr *T, const CallExpr *Ce = nullptr)
966 : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
967 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
969 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
971 SExpr *target() { return Target; }
972 const SExpr *target() const { return Target; }
974 const CallExpr *clangCallExpr() const { return Cexpr; }
977 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
978 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
979 return Vs.reduceCall(*this, Nt);
983 typename C::CType compare(const Call* E, C& Cmp) const {
984 return Cmp.compare(target(), E->target());
989 const CallExpr *Cexpr;
992 /// Allocate memory for a new value on the heap or stack.
993 class Alloc : public SExpr {
1000 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1001 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1003 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1005 AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1007 SExpr *dataType() { return Dtype; }
1008 const SExpr *dataType() const { return Dtype; }
1011 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1012 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1013 return Vs.reduceAlloc(*this, Nd);
1017 typename C::CType compare(const Alloc* E, C& Cmp) const {
1018 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1019 if (Cmp.notTrue(Ct))
1021 return Cmp.compare(dataType(), E->dataType());
1028 /// Load a value from memory.
1029 class Load : public SExpr {
1031 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1032 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1034 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1036 SExpr *pointer() { return Ptr; }
1037 const SExpr *pointer() const { return Ptr; }
1040 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1041 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1042 return Vs.reduceLoad(*this, Np);
1046 typename C::CType compare(const Load* E, C& Cmp) const {
1047 return Cmp.compare(pointer(), E->pointer());
1054 /// Store a value to memory.
1055 /// The destination is a pointer to a field, the source is the value to store.
1056 class Store : public SExpr {
1058 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1059 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1061 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1063 SExpr *destination() { return Dest; } // Address to store to
1064 const SExpr *destination() const { return Dest; }
1066 SExpr *source() { return Source; } // Value to store
1067 const SExpr *source() const { return Source; }
1070 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1071 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
1072 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1073 return Vs.reduceStore(*this, Np, Nv);
1077 typename C::CType compare(const Store* E, C& Cmp) const {
1078 typename C::CType Ct = Cmp.compare(destination(), E->destination());
1079 if (Cmp.notTrue(Ct))
1081 return Cmp.compare(source(), E->source());
1089 /// If p is a reference to an array, then p[i] is a reference to the i'th
1090 /// element of the array.
1091 class ArrayIndex : public SExpr {
1093 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1094 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1095 : SExpr(E), Array(A), Index(N) {}
1097 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1099 SExpr *array() { return Array; }
1100 const SExpr *array() const { return Array; }
1102 SExpr *index() { return Index; }
1103 const SExpr *index() const { return Index; }
1106 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1107 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1108 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1109 return Vs.reduceArrayIndex(*this, Na, Ni);
1113 typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1114 typename C::CType Ct = Cmp.compare(array(), E->array());
1115 if (Cmp.notTrue(Ct))
1117 return Cmp.compare(index(), E->index());
1125 /// Pointer arithmetic, restricted to arrays only.
1126 /// If p is a reference to an array, then p + n, where n is an integer, is
1127 /// a reference to a subarray.
1128 class ArrayAdd : public SExpr {
1130 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1131 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1132 : SExpr(E), Array(A), Index(N) {}
1134 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1136 SExpr *array() { return Array; }
1137 const SExpr *array() const { return Array; }
1139 SExpr *index() { return Index; }
1140 const SExpr *index() const { return Index; }
1143 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1144 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1145 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1146 return Vs.reduceArrayAdd(*this, Na, Ni);
1150 typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1151 typename C::CType Ct = Cmp.compare(array(), E->array());
1152 if (Cmp.notTrue(Ct))
1154 return Cmp.compare(index(), E->index());
1162 /// Simple arithmetic unary operations, e.g. negate and not.
1163 /// These operations have no side-effects.
1164 class UnaryOp : public SExpr {
1166 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1170 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1172 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1174 TIL_UnaryOpcode unaryOpcode() const {
1175 return static_cast<TIL_UnaryOpcode>(Flags);
1178 SExpr *expr() { return Expr0; }
1179 const SExpr *expr() const { return Expr0; }
1182 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1183 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1184 return Vs.reduceUnaryOp(*this, Ne);
1188 typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1189 typename C::CType Ct =
1190 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1191 if (Cmp.notTrue(Ct))
1193 return Cmp.compare(expr(), E->expr());
1200 /// Simple arithmetic binary operations, e.g. +, -, etc.
1201 /// These operations have no side effects.
1202 class BinaryOp : public SExpr {
1204 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1205 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1209 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1210 : SExpr(B), Expr0(E0), Expr1(E1) {
1214 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1216 TIL_BinaryOpcode binaryOpcode() const {
1217 return static_cast<TIL_BinaryOpcode>(Flags);
1220 SExpr *expr0() { return Expr0; }
1221 const SExpr *expr0() const { return Expr0; }
1223 SExpr *expr1() { return Expr1; }
1224 const SExpr *expr1() const { return Expr1; }
1227 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1228 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1229 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1230 return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1234 typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1235 typename C::CType Ct =
1236 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1237 if (Cmp.notTrue(Ct))
1239 Ct = Cmp.compare(expr0(), E->expr0());
1240 if (Cmp.notTrue(Ct))
1242 return Cmp.compare(expr1(), E->expr1());
1250 /// Cast expressions.
1251 /// Cast expressions are essentially unary operations, but we treat them
1252 /// as a distinct AST node because they only change the type of the result.
1253 class Cast : public SExpr {
1255 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1256 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1258 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1260 TIL_CastOpcode castOpcode() const {
1261 return static_cast<TIL_CastOpcode>(Flags);
1264 SExpr *expr() { return Expr0; }
1265 const SExpr *expr() const { return Expr0; }
1268 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1269 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1270 return Vs.reduceCast(*this, Ne);
1274 typename C::CType compare(const Cast* E, C& Cmp) const {
1275 typename C::CType Ct =
1276 Cmp.compareIntegers(castOpcode(), E->castOpcode());
1277 if (Cmp.notTrue(Ct))
1279 return Cmp.compare(expr(), E->expr());
1288 /// Phi Node, for code in SSA form.
1289 /// Each Phi node has an array of possible values that it can take,
1290 /// depending on where control flow comes from.
1291 class Phi : public SExpr {
1293 using ValArray = SimpleArray<SExpr *>;
1295 // In minimal SSA form, all Phi nodes are MultiVal.
1296 // During conversion to SSA, incomplete Phi nodes may be introduced, which
1297 // are later determined to be SingleVal, and are thus redundant.
1299 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal)
1300 PH_SingleVal, // Phi node has one distinct value, and can be eliminated
1301 PH_Incomplete // Phi node is incomplete
1304 Phi() : SExpr(COP_Phi) {}
1305 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1306 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1308 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1310 const ValArray &values() const { return Values; }
1311 ValArray &values() { return Values; }
1313 Status status() const { return static_cast<Status>(Flags); }
1314 void setStatus(Status s) { Flags = s; }
1316 /// Return the clang declaration of the variable for this Phi node, if any.
1317 const ValueDecl *clangDecl() const { return Cvdecl; }
1319 /// Set the clang variable associated with this Phi node.
1320 void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
1323 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1324 typename V::template Container<typename V::R_SExpr>
1325 Nvs(Vs, Values.size());
1327 for (const auto *Val : Values)
1328 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1329 return Vs.reducePhi(*this, Nvs);
1333 typename C::CType compare(const Phi *E, C &Cmp) const {
1334 // TODO: implement CFG comparisons
1335 return Cmp.comparePointers(this, E);
1340 const ValueDecl* Cvdecl = nullptr;
1343 /// Base class for basic block terminators: Branch, Goto, and Return.
1344 class Terminator : public SExpr {
1346 Terminator(TIL_Opcode Op) : SExpr(Op) {}
1347 Terminator(const SExpr &E) : SExpr(E) {}
1350 static bool classof(const SExpr *E) {
1351 return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1354 /// Return the list of basic blocks that this terminator can branch to.
1355 ArrayRef<BasicBlock *> successors();
1357 ArrayRef<BasicBlock *> successors() const {
1358 return const_cast<Terminator*>(this)->successors();
1362 /// Jump to another basic block.
1363 /// A goto instruction is essentially a tail-recursive call into another
1364 /// block. In addition to the block pointer, it specifies an index into the
1365 /// phi nodes of that block. The index can be used to retrieve the "arguments"
1367 class Goto : public Terminator {
1369 Goto(BasicBlock *B, unsigned I)
1370 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1371 Goto(const Goto &G, BasicBlock *B, unsigned I)
1372 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1374 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1376 const BasicBlock *targetBlock() const { return TargetBlock; }
1377 BasicBlock *targetBlock() { return TargetBlock; }
1379 /// Returns the index into the
1380 unsigned index() const { return Index; }
1382 /// Return the list of basic blocks that this terminator can branch to.
1383 ArrayRef<BasicBlock *> successors() { return TargetBlock; }
1386 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1387 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1388 return Vs.reduceGoto(*this, Ntb);
1392 typename C::CType compare(const Goto *E, C &Cmp) const {
1393 // TODO: implement CFG comparisons
1394 return Cmp.comparePointers(this, E);
1398 BasicBlock *TargetBlock;
1402 /// A conditional branch to two other blocks.
1403 /// Note that unlike Goto, Branch does not have an index. The target blocks
1404 /// must be child-blocks, and cannot have Phi nodes.
1405 class Branch : public Terminator {
1407 Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1408 : Terminator(COP_Branch), Condition(C) {
1413 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1414 : Terminator(Br), Condition(C) {
1419 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1421 const SExpr *condition() const { return Condition; }
1422 SExpr *condition() { return Condition; }
1424 const BasicBlock *thenBlock() const { return Branches[0]; }
1425 BasicBlock *thenBlock() { return Branches[0]; }
1427 const BasicBlock *elseBlock() const { return Branches[1]; }
1428 BasicBlock *elseBlock() { return Branches[1]; }
1430 /// Return the list of basic blocks that this terminator can branch to.
1431 ArrayRef<BasicBlock*> successors() {
1432 return llvm::makeArrayRef(Branches);
1436 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1437 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1438 BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
1439 BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
1440 return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1444 typename C::CType compare(const Branch *E, C &Cmp) const {
1445 // TODO: implement CFG comparisons
1446 return Cmp.comparePointers(this, E);
1451 BasicBlock *Branches[2];
1454 /// Return from the enclosing function, passing the return value to the caller.
1455 /// Only the exit block should end with a return statement.
1456 class Return : public Terminator {
1458 Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1459 Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1461 static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1463 /// Return an empty list.
1464 ArrayRef<BasicBlock *> successors() { return None; }
1466 SExpr *returnValue() { return Retval; }
1467 const SExpr *returnValue() const { return Retval; }
1470 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1471 auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
1472 return Vs.reduceReturn(*this, Ne);
1476 typename C::CType compare(const Return *E, C &Cmp) const {
1477 return Cmp.compare(Retval, E->Retval);
1484 inline ArrayRef<BasicBlock*> Terminator::successors() {
1486 case COP_Goto: return cast<Goto>(this)->successors();
1487 case COP_Branch: return cast<Branch>(this)->successors();
1488 case COP_Return: return cast<Return>(this)->successors();
1494 /// A basic block is part of an SCFG. It can be treated as a function in
1495 /// continuation passing style. A block consists of a sequence of phi nodes,
1496 /// which are "arguments" to the function, followed by a sequence of
1497 /// instructions. It ends with a Terminator, which is a Branch or Goto to
1498 /// another basic block in the same SCFG.
1499 class BasicBlock : public SExpr {
1501 using InstrArray = SimpleArray<SExpr *>;
1502 using BlockArray = SimpleArray<BasicBlock *>;
1504 // TopologyNodes are used to overlay tree structures on top of the CFG,
1505 // such as dominator and postdominator trees. Each block is assigned an
1506 // ID in the tree according to a depth-first search. Tree traversals are
1507 // always up, towards the parents.
1508 struct TopologyNode {
1511 // Includes this node, so must be > 1.
1512 int SizeOfSubTree = 0;
1514 // Pointer to parent.
1515 BasicBlock *Parent = nullptr;
1517 TopologyNode() = default;
1519 bool isParentOf(const TopologyNode& OtherNode) {
1520 return OtherNode.NodeID > NodeID &&
1521 OtherNode.NodeID < NodeID + SizeOfSubTree;
1524 bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1525 return OtherNode.NodeID >= NodeID &&
1526 OtherNode.NodeID < NodeID + SizeOfSubTree;
1530 explicit BasicBlock(MemRegionRef A)
1531 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
1532 BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
1534 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
1535 Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1537 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1539 /// Returns the block ID. Every block has a unique ID in the CFG.
1540 int blockID() const { return BlockID; }
1542 /// Returns the number of predecessors.
1543 size_t numPredecessors() const { return Predecessors.size(); }
1544 size_t numSuccessors() const { return successors().size(); }
1546 const SCFG* cfg() const { return CFGPtr; }
1547 SCFG* cfg() { return CFGPtr; }
1549 const BasicBlock *parent() const { return DominatorNode.Parent; }
1550 BasicBlock *parent() { return DominatorNode.Parent; }
1552 const InstrArray &arguments() const { return Args; }
1553 InstrArray &arguments() { return Args; }
1555 InstrArray &instructions() { return Instrs; }
1556 const InstrArray &instructions() const { return Instrs; }
1558 /// Returns a list of predecessors.
1559 /// The order of predecessors in the list is important; each phi node has
1560 /// exactly one argument for each precessor, in the same order.
1561 BlockArray &predecessors() { return Predecessors; }
1562 const BlockArray &predecessors() const { return Predecessors; }
1564 ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
1565 ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1567 const Terminator *terminator() const { return TermInstr; }
1568 Terminator *terminator() { return TermInstr; }
1570 void setTerminator(Terminator *E) { TermInstr = E; }
1572 bool Dominates(const BasicBlock &Other) {
1573 return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1576 bool PostDominates(const BasicBlock &Other) {
1577 return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1580 /// Add a new argument.
1581 void addArgument(Phi *V) {
1582 Args.reserveCheck(1, Arena);
1586 /// Add a new instruction.
1587 void addInstruction(SExpr *V) {
1588 Instrs.reserveCheck(1, Arena);
1589 Instrs.push_back(V);
1592 // Add a new predecessor, and return the phi-node index for it.
1593 // Will add an argument to all phi-nodes, initialized to nullptr.
1594 unsigned addPredecessor(BasicBlock *Pred);
1596 // Reserve space for Nargs arguments.
1597 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
1599 // Reserve space for Nins instructions.
1600 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1602 // Reserve space for NumPreds predecessors, including space in phi nodes.
1603 void reservePredecessors(unsigned NumPreds);
1605 /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
1606 unsigned findPredecessorIndex(const BasicBlock *BB) const {
1607 auto I = llvm::find(Predecessors, BB);
1608 return std::distance(Predecessors.cbegin(), I);
1612 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1613 typename V::template Container<SExpr*> Nas(Vs, Args.size());
1614 typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
1616 // Entering the basic block should do any scope initialization.
1617 Vs.enterBasicBlock(*this);
1619 for (const auto *E : Args) {
1620 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1623 for (const auto *E : Instrs) {
1624 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1627 auto Nt = Vs.traverse(TermInstr, Ctx);
1629 // Exiting the basic block should handle any scope cleanup.
1630 Vs.exitBasicBlock(*this);
1632 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1636 typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1637 // TODO: implement CFG comparisons
1638 return Cmp.comparePointers(this, E);
1644 // assign unique ids to all instructions
1645 unsigned renumberInstrs(unsigned id);
1647 unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1648 unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1649 void computeDominator();
1650 void computePostDominator();
1652 // The arena used to allocate this block.
1655 // The CFG that contains this block.
1656 SCFG *CFGPtr = nullptr;
1658 // Unique ID for this BB in the containing CFG. IDs are in topological order.
1659 unsigned BlockID : 31;
1661 // Bit to determine if a block has been visited during a traversal.
1664 // Predecessor blocks in the CFG.
1665 BlockArray Predecessors;
1667 // Phi nodes. One argument per predecessor.
1673 // Terminating instruction.
1674 Terminator *TermInstr = nullptr;
1676 // The dominator tree.
1677 TopologyNode DominatorNode;
1679 // The post-dominator tree.
1680 TopologyNode PostDominatorNode;
1683 /// An SCFG is a control-flow graph. It consists of a set of basic blocks,
1684 /// each of which terminates in a branch to another basic block. There is one
1685 /// entry point, and one exit point.
1686 class SCFG : public SExpr {
1688 using BlockArray = SimpleArray<BasicBlock *>;
1689 using iterator = BlockArray::iterator;
1690 using const_iterator = BlockArray::const_iterator;
1692 SCFG(MemRegionRef A, unsigned Nblocks)
1693 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
1694 Entry = new (A) BasicBlock(A);
1695 Exit = new (A) BasicBlock(A);
1696 auto *V = new (A) Phi();
1697 Exit->addArgument(V);
1698 Exit->setTerminator(new (A) Return(V));
1703 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1704 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
1705 // TODO: set entry and exit!
1708 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1710 /// Return true if this CFG is valid.
1711 bool valid() const { return Entry && Exit && Blocks.size() > 0; }
1713 /// Return true if this CFG has been normalized.
1714 /// After normalization, blocks are in topological order, and block and
1715 /// instruction IDs have been assigned.
1716 bool normal() const { return Normal; }
1718 iterator begin() { return Blocks.begin(); }
1719 iterator end() { return Blocks.end(); }
1721 const_iterator begin() const { return cbegin(); }
1722 const_iterator end() const { return cend(); }
1724 const_iterator cbegin() const { return Blocks.cbegin(); }
1725 const_iterator cend() const { return Blocks.cend(); }
1727 const BasicBlock *entry() const { return Entry; }
1728 BasicBlock *entry() { return Entry; }
1729 const BasicBlock *exit() const { return Exit; }
1730 BasicBlock *exit() { return Exit; }
1732 /// Return the number of blocks in the CFG.
1733 /// Block::blockID() will return a number less than numBlocks();
1734 size_t numBlocks() const { return Blocks.size(); }
1736 /// Return the total number of instructions in the CFG.
1737 /// This is useful for building instruction side-tables;
1738 /// A call to SExpr::id() will return a number less than numInstructions().
1739 unsigned numInstructions() { return NumInstructions; }
1741 inline void add(BasicBlock *BB) {
1742 assert(BB->CFGPtr == nullptr);
1744 Blocks.reserveCheck(1, Arena);
1745 Blocks.push_back(BB);
1748 void setEntry(BasicBlock *BB) { Entry = BB; }
1749 void setExit(BasicBlock *BB) { Exit = BB; }
1751 void computeNormalForm();
1754 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1756 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1758 for (const auto *B : Blocks) {
1759 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1762 return Vs.reduceSCFG(*this, Bbs);
1766 typename C::CType compare(const SCFG *E, C &Cmp) const {
1767 // TODO: implement CFG comparisons
1768 return Cmp.comparePointers(this, E);
1772 // assign unique ids to all instructions
1773 void renumberInstrs();
1777 BasicBlock *Entry = nullptr;
1778 BasicBlock *Exit = nullptr;
1779 unsigned NumInstructions = 0;
1780 bool Normal = false;
1783 /// An identifier, e.g. 'foo' or 'x'.
1784 /// This is a pseduo-term; it will be lowered to a variable or projection.
1785 class Identifier : public SExpr {
1787 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
1788 Identifier(const Identifier &) = default;
1790 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1792 StringRef name() const { return Name; }
1795 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1796 return Vs.reduceIdentifier(*this);
1800 typename C::CType compare(const Identifier* E, C& Cmp) const {
1801 return Cmp.compareStrings(name(), E->name());
1808 /// An if-then-else expression.
1809 /// This is a pseduo-term; it will be lowered to a branch in a CFG.
1810 class IfThenElse : public SExpr {
1812 IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1813 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
1814 IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1815 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
1817 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1819 SExpr *condition() { return Condition; } // Address to store to
1820 const SExpr *condition() const { return Condition; }
1822 SExpr *thenExpr() { return ThenExpr; } // Value to store
1823 const SExpr *thenExpr() const { return ThenExpr; }
1825 SExpr *elseExpr() { return ElseExpr; } // Value to store
1826 const SExpr *elseExpr() const { return ElseExpr; }
1829 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1830 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1831 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
1832 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
1833 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1837 typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1838 typename C::CType Ct = Cmp.compare(condition(), E->condition());
1839 if (Cmp.notTrue(Ct))
1841 Ct = Cmp.compare(thenExpr(), E->thenExpr());
1842 if (Cmp.notTrue(Ct))
1844 return Cmp.compare(elseExpr(), E->elseExpr());
1853 /// A let-expression, e.g. let x=t; u.
1854 /// This is a pseduo-term; it will be lowered to instructions in a CFG.
1855 class Let : public SExpr {
1857 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1858 Vd->setKind(Variable::VK_Let);
1861 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1862 Vd->setKind(Variable::VK_Let);
1865 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1867 Variable *variableDecl() { return VarDecl; }
1868 const Variable *variableDecl() const { return VarDecl; }
1870 SExpr *body() { return Body; }
1871 const SExpr *body() const { return Body; }
1874 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1875 // This is a variable declaration, so traverse the definition.
1876 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1877 // Tell the rewriter to enter the scope of the let variable.
1878 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1879 auto E1 = Vs.traverse(Body, Ctx);
1880 Vs.exitScope(*VarDecl);
1881 return Vs.reduceLet(*this, Nvd, E1);
1885 typename C::CType compare(const Let* E, C& Cmp) const {
1886 typename C::CType Ct =
1887 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1888 if (Cmp.notTrue(Ct))
1890 Cmp.enterScope(variableDecl(), E->variableDecl());
1891 Ct = Cmp.compare(body(), E->body());
1901 const SExpr *getCanonicalVal(const SExpr *E);
1902 SExpr* simplifyToCanonicalVal(SExpr *E);
1903 void simplifyIncompleteArg(til::Phi *Ph);
1906 } // namespace threadSafety
1908 } // namespace clang
1910 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H