1341825Sdim//===- ThreadSafetyTIL.h ----------------------------------------*- C++ -*-===// 2274958Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6274958Sdim// 7274958Sdim//===----------------------------------------------------------------------===// 8274958Sdim// 9274958Sdim// This file defines a simple Typed Intermediate Language, or TIL, that is used 10274958Sdim// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended 11274958Sdim// to be largely independent of clang, in the hope that the analysis can be 12274958Sdim// reused for other non-C++ languages. All dependencies on clang/llvm should 13274958Sdim// go in ThreadSafetyUtil.h. 14274958Sdim// 15274958Sdim// Thread safety analysis works by comparing mutex expressions, e.g. 16274958Sdim// 17274958Sdim// class A { Mutex mu; int dat GUARDED_BY(this->mu); } 18274958Sdim// class B { A a; } 19274958Sdim// 20274958Sdim// void foo(B* b) { 21274958Sdim// (*b).a.mu.lock(); // locks (*b).a.mu 22274958Sdim// b->a.dat = 0; // substitute &b->a for 'this'; 23274958Sdim// // requires lock on (&b->a)->mu 24274958Sdim// (b->a.mu).unlock(); // unlocks (b->a.mu) 25274958Sdim// } 26274958Sdim// 27274958Sdim// As illustrated by the above example, clang Exprs are not well-suited to 28274958Sdim// represent mutex expressions directly, since there is no easy way to compare 29274958Sdim// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs 30274958Sdim// into a simple intermediate language (IL). The IL supports: 31274958Sdim// 32274958Sdim// (1) comparisons for semantic equality of expressions 33274958Sdim// (2) SSA renaming of variables 34274958Sdim// (3) wildcards and pattern matching over expressions 35274958Sdim// (4) hash-based expression lookup 36274958Sdim// 37274958Sdim// The TIL is currently very experimental, is intended only for use within 38274958Sdim// the thread safety analysis, and is subject to change without notice. 39274958Sdim// After the API stabilizes and matures, it may be appropriate to make this 40274958Sdim// more generally available to other analyses. 41274958Sdim// 42274958Sdim// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 43274958Sdim// 44274958Sdim//===----------------------------------------------------------------------===// 45274958Sdim 46280031Sdim#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 47280031Sdim#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 48274958Sdim 49341825Sdim#include "clang/AST/Decl.h" 50341825Sdim#include "clang/Analysis/Analyses/ThreadSafetyUtil.h" 51341825Sdim#include "clang/Basic/LLVM.h" 52341825Sdim#include "llvm/ADT/ArrayRef.h" 53341825Sdim#include "llvm/ADT/None.h" 54341825Sdim#include "llvm/ADT/Optional.h" 55341825Sdim#include "llvm/ADT/StringRef.h" 56341825Sdim#include "llvm/Support/Casting.h" 57341825Sdim#include "llvm/Support/raw_ostream.h" 58274958Sdim#include <algorithm> 59274958Sdim#include <cassert> 60274958Sdim#include <cstddef> 61341825Sdim#include <cstdint> 62341825Sdim#include <iterator> 63341825Sdim#include <string> 64274958Sdim#include <utility> 65274958Sdim 66341825Sdimnamespace clang { 67274958Sdim 68341825Sdimclass CallExpr; 69341825Sdimclass Expr; 70341825Sdimclass Stmt; 71341825Sdim 72274958Sdimnamespace threadSafety { 73274958Sdimnamespace til { 74274958Sdim 75341825Sdimclass BasicBlock; 76274958Sdim 77280031Sdim/// Enum for the different distinct classes of SExpr 78274958Sdimenum TIL_Opcode { 79274958Sdim#define TIL_OPCODE_DEF(X) COP_##X, 80274958Sdim#include "ThreadSafetyOps.def" 81274958Sdim#undef TIL_OPCODE_DEF 82274958Sdim}; 83274958Sdim 84280031Sdim/// Opcode for unary arithmetic operations. 85274958Sdimenum TIL_UnaryOpcode : unsigned char { 86274958Sdim UOP_Minus, // - 87274958Sdim UOP_BitNot, // ~ 88274958Sdim UOP_LogicNot // ! 89274958Sdim}; 90274958Sdim 91280031Sdim/// Opcode for binary arithmetic operations. 92274958Sdimenum TIL_BinaryOpcode : unsigned char { 93280031Sdim BOP_Add, // + 94280031Sdim BOP_Sub, // - 95274958Sdim BOP_Mul, // * 96274958Sdim BOP_Div, // / 97274958Sdim BOP_Rem, // % 98274958Sdim BOP_Shl, // << 99274958Sdim BOP_Shr, // >> 100274958Sdim BOP_BitAnd, // & 101274958Sdim BOP_BitXor, // ^ 102274958Sdim BOP_BitOr, // | 103274958Sdim BOP_Eq, // == 104274958Sdim BOP_Neq, // != 105274958Sdim BOP_Lt, // < 106274958Sdim BOP_Leq, // <= 107327952Sdim BOP_Cmp, // <=> 108280031Sdim BOP_LogicAnd, // && (no short-circuit) 109280031Sdim BOP_LogicOr // || (no short-circuit) 110274958Sdim}; 111274958Sdim 112280031Sdim/// Opcode for cast operations. 113274958Sdimenum TIL_CastOpcode : unsigned char { 114274958Sdim CAST_none = 0, 115341825Sdim 116341825Sdim // Extend precision of numeric type 117341825Sdim CAST_extendNum, 118341825Sdim 119341825Sdim // Truncate precision of numeric type 120341825Sdim CAST_truncNum, 121341825Sdim 122341825Sdim // Convert to floating point type 123341825Sdim CAST_toFloat, 124341825Sdim 125341825Sdim // Convert to integer type 126341825Sdim CAST_toInt, 127341825Sdim 128341825Sdim // Convert smart pointer to pointer (C++ only) 129341825Sdim CAST_objToPtr 130274958Sdim}; 131274958Sdim 132274958Sdimconst TIL_Opcode COP_Min = COP_Future; 133274958Sdimconst TIL_Opcode COP_Max = COP_Branch; 134274958Sdimconst TIL_UnaryOpcode UOP_Min = UOP_Minus; 135274958Sdimconst TIL_UnaryOpcode UOP_Max = UOP_LogicNot; 136280031Sdimconst TIL_BinaryOpcode BOP_Min = BOP_Add; 137274958Sdimconst TIL_BinaryOpcode BOP_Max = BOP_LogicOr; 138274958Sdimconst TIL_CastOpcode CAST_Min = CAST_none; 139274958Sdimconst TIL_CastOpcode CAST_Max = CAST_toInt; 140274958Sdim 141280031Sdim/// Return the name of a unary opcode. 142274958SdimStringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); 143280031Sdim 144280031Sdim/// Return the name of a binary opcode. 145274958SdimStringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); 146274958Sdim 147280031Sdim/// ValueTypes are data types that can actually be held in registers. 148280031Sdim/// All variables and expressions must have a value type. 149280031Sdim/// Pointer types are further subdivided into the various heap-allocated 150280031Sdim/// types, such as functions, records, etc. 151280031Sdim/// Structured types that are passed by value (e.g. complex numbers) 152280031Sdim/// require special handling; they use BT_ValueRef, and size ST_0. 153274958Sdimstruct ValueType { 154274958Sdim enum BaseType : unsigned char { 155274958Sdim BT_Void = 0, 156274958Sdim BT_Bool, 157274958Sdim BT_Int, 158274958Sdim BT_Float, 159274958Sdim BT_String, // String literals 160274958Sdim BT_Pointer, 161274958Sdim BT_ValueRef 162274958Sdim }; 163274958Sdim 164274958Sdim enum SizeType : unsigned char { 165274958Sdim ST_0 = 0, 166274958Sdim ST_1, 167274958Sdim ST_8, 168274958Sdim ST_16, 169274958Sdim ST_32, 170274958Sdim ST_64, 171274958Sdim ST_128 172274958Sdim }; 173274958Sdim 174341825Sdim ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) 175341825Sdim : Base(B), Size(Sz), Signed(S), VectSize(VS) {} 176341825Sdim 177274958Sdim inline static SizeType getSizeType(unsigned nbytes); 178274958Sdim 179274958Sdim template <class T> 180274958Sdim inline static ValueType getValueType(); 181274958Sdim 182341825Sdim BaseType Base; 183341825Sdim SizeType Size; 184341825Sdim bool Signed; 185274958Sdim 186341825Sdim // 0 for scalar, otherwise num elements in vector 187341825Sdim unsigned char VectSize; 188274958Sdim}; 189274958Sdim 190274958Sdiminline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { 191274958Sdim switch (nbytes) { 192274958Sdim case 1: return ST_8; 193274958Sdim case 2: return ST_16; 194274958Sdim case 4: return ST_32; 195274958Sdim case 8: return ST_64; 196274958Sdim case 16: return ST_128; 197274958Sdim default: return ST_0; 198274958Sdim } 199274958Sdim} 200274958Sdim 201274958Sdimtemplate<> 202274958Sdiminline ValueType ValueType::getValueType<void>() { 203274958Sdim return ValueType(BT_Void, ST_0, false, 0); 204274958Sdim} 205274958Sdim 206274958Sdimtemplate<> 207274958Sdiminline ValueType ValueType::getValueType<bool>() { 208274958Sdim return ValueType(BT_Bool, ST_1, false, 0); 209274958Sdim} 210274958Sdim 211274958Sdimtemplate<> 212274958Sdiminline ValueType ValueType::getValueType<int8_t>() { 213274958Sdim return ValueType(BT_Int, ST_8, true, 0); 214274958Sdim} 215274958Sdim 216274958Sdimtemplate<> 217274958Sdiminline ValueType ValueType::getValueType<uint8_t>() { 218274958Sdim return ValueType(BT_Int, ST_8, false, 0); 219274958Sdim} 220274958Sdim 221274958Sdimtemplate<> 222274958Sdiminline ValueType ValueType::getValueType<int16_t>() { 223274958Sdim return ValueType(BT_Int, ST_16, true, 0); 224274958Sdim} 225274958Sdim 226274958Sdimtemplate<> 227274958Sdiminline ValueType ValueType::getValueType<uint16_t>() { 228274958Sdim return ValueType(BT_Int, ST_16, false, 0); 229274958Sdim} 230274958Sdim 231274958Sdimtemplate<> 232274958Sdiminline ValueType ValueType::getValueType<int32_t>() { 233274958Sdim return ValueType(BT_Int, ST_32, true, 0); 234274958Sdim} 235274958Sdim 236274958Sdimtemplate<> 237274958Sdiminline ValueType ValueType::getValueType<uint32_t>() { 238274958Sdim return ValueType(BT_Int, ST_32, false, 0); 239274958Sdim} 240274958Sdim 241274958Sdimtemplate<> 242274958Sdiminline ValueType ValueType::getValueType<int64_t>() { 243274958Sdim return ValueType(BT_Int, ST_64, true, 0); 244274958Sdim} 245274958Sdim 246274958Sdimtemplate<> 247274958Sdiminline ValueType ValueType::getValueType<uint64_t>() { 248274958Sdim return ValueType(BT_Int, ST_64, false, 0); 249274958Sdim} 250274958Sdim 251274958Sdimtemplate<> 252274958Sdiminline ValueType ValueType::getValueType<float>() { 253274958Sdim return ValueType(BT_Float, ST_32, true, 0); 254274958Sdim} 255274958Sdim 256274958Sdimtemplate<> 257274958Sdiminline ValueType ValueType::getValueType<double>() { 258274958Sdim return ValueType(BT_Float, ST_64, true, 0); 259274958Sdim} 260274958Sdim 261274958Sdimtemplate<> 262274958Sdiminline ValueType ValueType::getValueType<long double>() { 263274958Sdim return ValueType(BT_Float, ST_128, true, 0); 264274958Sdim} 265274958Sdim 266274958Sdimtemplate<> 267274958Sdiminline ValueType ValueType::getValueType<StringRef>() { 268274958Sdim return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); 269274958Sdim} 270274958Sdim 271274958Sdimtemplate<> 272274958Sdiminline ValueType ValueType::getValueType<void*>() { 273274958Sdim return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); 274274958Sdim} 275274958Sdim 276280031Sdim/// Base class for AST nodes in the typed intermediate language. 277274958Sdimclass SExpr { 278274958Sdimpublic: 279341825Sdim SExpr() = delete; 280341825Sdim 281274958Sdim TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } 282274958Sdim 283274958Sdim // Subclasses of SExpr must define the following: 284274958Sdim // 285274958Sdim // This(const This& E, ...) { 286274958Sdim // copy constructor: construct copy of E, with some additional arguments. 287274958Sdim // } 288274958Sdim // 289274958Sdim // template <class V> 290274958Sdim // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 291274958Sdim // traverse all subexpressions, following the traversal/rewriter interface. 292274958Sdim // } 293274958Sdim // 294274958Sdim // template <class C> typename C::CType compare(CType* E, C& Cmp) { 295274958Sdim // compare all subexpressions, following the comparator interface 296274958Sdim // } 297274958Sdim void *operator new(size_t S, MemRegionRef &R) { 298274958Sdim return ::operator new(S, R); 299274958Sdim } 300274958Sdim 301341825Sdim /// SExpr objects must be created in an arena. 302341825Sdim void *operator new(size_t) = delete; 303341825Sdim 304280031Sdim /// SExpr objects cannot be deleted. 305274958Sdim // This declaration is public to workaround a gcc bug that breaks building 306274958Sdim // with REQUIRES_EH=1. 307288943Sdim void operator delete(void *) = delete; 308274958Sdim 309280031Sdim /// Returns the instruction ID for this expression. 310280031Sdim /// All basic block instructions have a unique ID (i.e. virtual register). 311280031Sdim unsigned id() const { return SExprID; } 312280031Sdim 313280031Sdim /// Returns the block, if this is an instruction in a basic block, 314280031Sdim /// otherwise returns null. 315341825Sdim BasicBlock *block() const { return Block; } 316280031Sdim 317280031Sdim /// Set the basic block and instruction ID for this expression. 318280031Sdim void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } 319280031Sdim 320274958Sdimprotected: 321341825Sdim SExpr(TIL_Opcode Op) : Opcode(Op) {} 322341825Sdim SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {} 323274958Sdim 324274958Sdim const unsigned char Opcode; 325341825Sdim unsigned char Reserved = 0; 326341825Sdim unsigned short Flags = 0; 327341825Sdim unsigned SExprID = 0; 328341825Sdim BasicBlock *Block = nullptr; 329274958Sdim}; 330274958Sdim 331274958Sdim// Contains various helper functions for SExprs. 332274958Sdimnamespace ThreadSafetyTIL { 333341825Sdim 334341825Sdiminline bool isTrivial(const SExpr *E) { 335341825Sdim unsigned Op = E->opcode(); 336341825Sdim return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; 337274958Sdim} 338274958Sdim 339341825Sdim} // namespace ThreadSafetyTIL 340341825Sdim 341274958Sdim// Nodes which declare variables 342274958Sdim 343280031Sdim/// A named variable, e.g. "x". 344280031Sdim/// 345280031Sdim/// There are two distinct places in which a Variable can appear in the AST. 346280031Sdim/// A variable declaration introduces a new variable, and can occur in 3 places: 347280031Sdim/// Let-expressions: (Let (x = t) u) 348280031Sdim/// Functions: (Function (x : t) u) 349280031Sdim/// Self-applicable functions (SFunction (x) t) 350280031Sdim/// 351280031Sdim/// If a variable occurs in any other location, it is a reference to an existing 352280031Sdim/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't 353280031Sdim/// allocate a separate AST node for variable references; a reference is just a 354280031Sdim/// pointer to the original declaration. 355274958Sdimclass Variable : public SExpr { 356274958Sdimpublic: 357341825Sdim enum VariableKind { 358341825Sdim /// Let-variable 359341825Sdim VK_Let, 360274958Sdim 361341825Sdim /// Function parameter 362341825Sdim VK_Fun, 363341825Sdim 364341825Sdim /// SFunction (self) parameter 365341825Sdim VK_SFun 366274958Sdim }; 367274958Sdim 368280031Sdim Variable(StringRef s, SExpr *D = nullptr) 369341825Sdim : SExpr(COP_Variable), Name(s), Definition(D) { 370280031Sdim Flags = VK_Let; 371280031Sdim } 372341825Sdim 373341825Sdim Variable(SExpr *D, const ValueDecl *Cvd = nullptr) 374280031Sdim : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), 375280031Sdim Definition(D), Cvdecl(Cvd) { 376280031Sdim Flags = VK_Let; 377280031Sdim } 378341825Sdim 379280031Sdim Variable(const Variable &Vd, SExpr *D) // rewrite constructor 380280031Sdim : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { 381280031Sdim Flags = Vd.kind(); 382280031Sdim } 383274958Sdim 384341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } 385341825Sdim 386280031Sdim /// Return the kind of variable (let, function param, or self) 387274958Sdim VariableKind kind() const { return static_cast<VariableKind>(Flags); } 388274958Sdim 389280031Sdim /// Return the name of the variable, if any. 390280031Sdim StringRef name() const { return Name; } 391280031Sdim 392280031Sdim /// Return the clang declaration for this variable, if any. 393341825Sdim const ValueDecl *clangDecl() const { return Cvdecl; } 394274958Sdim 395280031Sdim /// Return the definition of the variable. 396280031Sdim /// For let-vars, this is the setting expression. 397280031Sdim /// For function and self parameters, it is the type of the variable. 398280031Sdim SExpr *definition() { return Definition; } 399280031Sdim const SExpr *definition() const { return Definition; } 400274958Sdim 401280031Sdim void setName(StringRef S) { Name = S; } 402280031Sdim void setKind(VariableKind K) { Flags = K; } 403280031Sdim void setDefinition(SExpr *E) { Definition = E; } 404341825Sdim void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } 405274958Sdim 406274958Sdim template <class V> 407274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 408274958Sdim // This routine is only called for variable references. 409274958Sdim return Vs.reduceVariableRef(this); 410274958Sdim } 411274958Sdim 412280031Sdim template <class C> 413280031Sdim typename C::CType compare(const Variable* E, C& Cmp) const { 414274958Sdim return Cmp.compareVariableRefs(this, E); 415274958Sdim } 416274958Sdim 417274958Sdimprivate: 418341825Sdim friend class BasicBlock; 419274958Sdim friend class Function; 420341825Sdim friend class Let; 421274958Sdim friend class SFunction; 422274958Sdim 423341825Sdim // The name of the variable. 424341825Sdim StringRef Name; 425341825Sdim 426341825Sdim // The TIL type or definition. 427341825Sdim SExpr *Definition; 428341825Sdim 429341825Sdim // The clang declaration for this variable. 430341825Sdim const ValueDecl *Cvdecl = nullptr; 431274958Sdim}; 432274958Sdim 433280031Sdim/// Placeholder for an expression that has not yet been created. 434280031Sdim/// Used to implement lazy copy and rewriting strategies. 435274958Sdimclass Future : public SExpr { 436274958Sdimpublic: 437274958Sdim enum FutureStatus { 438274958Sdim FS_pending, 439274958Sdim FS_evaluating, 440274958Sdim FS_done 441274958Sdim }; 442274958Sdim 443341825Sdim Future() : SExpr(COP_Future) {} 444288943Sdim virtual ~Future() = delete; 445280031Sdim 446341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } 447341825Sdim 448274958Sdim // A lazy rewriting strategy should subclass Future and override this method. 449280031Sdim virtual SExpr *compute() { return nullptr; } 450274958Sdim 451274958Sdim // Return the result of this future if it exists, otherwise return null. 452341825Sdim SExpr *maybeGetResult() const { return Result; } 453274958Sdim 454274958Sdim // Return the result of this future; forcing it if necessary. 455274958Sdim SExpr *result() { 456274958Sdim switch (Status) { 457274958Sdim case FS_pending: 458280031Sdim return force(); 459274958Sdim case FS_evaluating: 460274958Sdim return nullptr; // infinite loop; illegal recursion. 461274958Sdim case FS_done: 462274958Sdim return Result; 463274958Sdim } 464274958Sdim } 465274958Sdim 466274958Sdim template <class V> 467274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 468274958Sdim assert(Result && "Cannot traverse Future that has not been forced."); 469274958Sdim return Vs.traverse(Result, Ctx); 470274958Sdim } 471274958Sdim 472280031Sdim template <class C> 473280031Sdim typename C::CType compare(const Future* E, C& Cmp) const { 474274958Sdim if (!Result || !E->Result) 475274958Sdim return Cmp.comparePointers(this, E); 476274958Sdim return Cmp.compare(Result, E->Result); 477274958Sdim } 478274958Sdim 479274958Sdimprivate: 480280031Sdim SExpr* force(); 481274958Sdim 482341825Sdim FutureStatus Status = FS_pending; 483341825Sdim SExpr *Result = nullptr; 484274958Sdim}; 485274958Sdim 486280031Sdim/// Placeholder for expressions that cannot be represented in the TIL. 487274958Sdimclass Undefined : public SExpr { 488274958Sdimpublic: 489341825Sdim Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} 490341825Sdim Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} 491341825Sdim 492274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 493274958Sdim 494274958Sdim template <class V> 495274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 496274958Sdim return Vs.reduceUndefined(*this); 497274958Sdim } 498274958Sdim 499280031Sdim template <class C> 500280031Sdim typename C::CType compare(const Undefined* E, C& Cmp) const { 501280031Sdim return Cmp.trueResult(); 502274958Sdim } 503274958Sdim 504274958Sdimprivate: 505341825Sdim const Stmt *Cstmt; 506274958Sdim}; 507274958Sdim 508280031Sdim/// Placeholder for a wildcard that matches any other expression. 509274958Sdimclass Wildcard : public SExpr { 510274958Sdimpublic: 511341825Sdim Wildcard() : SExpr(COP_Wildcard) {} 512341825Sdim Wildcard(const Wildcard &) = default; 513341825Sdim 514274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 515274958Sdim 516274958Sdim template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 517274958Sdim return Vs.reduceWildcard(*this); 518274958Sdim } 519274958Sdim 520280031Sdim template <class C> 521280031Sdim typename C::CType compare(const Wildcard* E, C& Cmp) const { 522274958Sdim return Cmp.trueResult(); 523274958Sdim } 524274958Sdim}; 525274958Sdim 526274958Sdimtemplate <class T> class LiteralT; 527274958Sdim 528274958Sdim// Base class for literal values. 529274958Sdimclass Literal : public SExpr { 530274958Sdimpublic: 531341825Sdim Literal(const Expr *C) 532341825Sdim : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {} 533341825Sdim Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {} 534341825Sdim Literal(const Literal &) = default; 535341825Sdim 536274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 537274958Sdim 538274958Sdim // The clang expression for this literal. 539341825Sdim const Expr *clangExpr() const { return Cexpr; } 540274958Sdim 541274958Sdim ValueType valueType() const { return ValType; } 542274958Sdim 543274958Sdim template<class T> const LiteralT<T>& as() const { 544274958Sdim return *static_cast<const LiteralT<T>*>(this); 545274958Sdim } 546274958Sdim template<class T> LiteralT<T>& as() { 547274958Sdim return *static_cast<LiteralT<T>*>(this); 548274958Sdim } 549274958Sdim 550274958Sdim template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 551274958Sdim 552280031Sdim template <class C> 553280031Sdim typename C::CType compare(const Literal* E, C& Cmp) const { 554280031Sdim // TODO: defer actual comparison to LiteralT 555280031Sdim return Cmp.trueResult(); 556274958Sdim } 557274958Sdim 558274958Sdimprivate: 559274958Sdim const ValueType ValType; 560341825Sdim const Expr *Cexpr = nullptr; 561274958Sdim}; 562274958Sdim 563274958Sdim// Derived class for literal values, which stores the actual value. 564274958Sdimtemplate<class T> 565274958Sdimclass LiteralT : public Literal { 566274958Sdimpublic: 567341825Sdim LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} 568341825Sdim LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} 569274958Sdim 570341825Sdim T value() const { return Val;} 571274958Sdim T& value() { return Val; } 572274958Sdim 573274958Sdimprivate: 574274958Sdim T Val; 575274958Sdim}; 576274958Sdim 577274958Sdimtemplate <class V> 578274958Sdimtypename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 579274958Sdim if (Cexpr) 580274958Sdim return Vs.reduceLiteral(*this); 581274958Sdim 582274958Sdim switch (ValType.Base) { 583274958Sdim case ValueType::BT_Void: 584274958Sdim break; 585274958Sdim case ValueType::BT_Bool: 586274958Sdim return Vs.reduceLiteralT(as<bool>()); 587274958Sdim case ValueType::BT_Int: { 588274958Sdim switch (ValType.Size) { 589274958Sdim case ValueType::ST_8: 590274958Sdim if (ValType.Signed) 591274958Sdim return Vs.reduceLiteralT(as<int8_t>()); 592274958Sdim else 593274958Sdim return Vs.reduceLiteralT(as<uint8_t>()); 594274958Sdim case ValueType::ST_16: 595274958Sdim if (ValType.Signed) 596274958Sdim return Vs.reduceLiteralT(as<int16_t>()); 597274958Sdim else 598274958Sdim return Vs.reduceLiteralT(as<uint16_t>()); 599274958Sdim case ValueType::ST_32: 600274958Sdim if (ValType.Signed) 601274958Sdim return Vs.reduceLiteralT(as<int32_t>()); 602274958Sdim else 603274958Sdim return Vs.reduceLiteralT(as<uint32_t>()); 604274958Sdim case ValueType::ST_64: 605274958Sdim if (ValType.Signed) 606274958Sdim return Vs.reduceLiteralT(as<int64_t>()); 607274958Sdim else 608274958Sdim return Vs.reduceLiteralT(as<uint64_t>()); 609274958Sdim default: 610274958Sdim break; 611274958Sdim } 612274958Sdim } 613274958Sdim case ValueType::BT_Float: { 614274958Sdim switch (ValType.Size) { 615274958Sdim case ValueType::ST_32: 616274958Sdim return Vs.reduceLiteralT(as<float>()); 617274958Sdim case ValueType::ST_64: 618274958Sdim return Vs.reduceLiteralT(as<double>()); 619274958Sdim default: 620274958Sdim break; 621274958Sdim } 622274958Sdim } 623274958Sdim case ValueType::BT_String: 624274958Sdim return Vs.reduceLiteralT(as<StringRef>()); 625274958Sdim case ValueType::BT_Pointer: 626274958Sdim return Vs.reduceLiteralT(as<void*>()); 627274958Sdim case ValueType::BT_ValueRef: 628274958Sdim break; 629274958Sdim } 630274958Sdim return Vs.reduceLiteral(*this); 631274958Sdim} 632274958Sdim 633280031Sdim/// A Literal pointer to an object allocated in memory. 634280031Sdim/// At compile time, pointer literals are represented by symbolic names. 635274958Sdimclass LiteralPtr : public SExpr { 636274958Sdimpublic: 637341825Sdim LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 638341825Sdim LiteralPtr(const LiteralPtr &) = default; 639341825Sdim 640274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 641274958Sdim 642274958Sdim // The clang declaration for the value that this pointer points to. 643341825Sdim const ValueDecl *clangDecl() const { return Cvdecl; } 644274958Sdim 645274958Sdim template <class V> 646274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 647274958Sdim return Vs.reduceLiteralPtr(*this); 648274958Sdim } 649274958Sdim 650280031Sdim template <class C> 651280031Sdim typename C::CType compare(const LiteralPtr* E, C& Cmp) const { 652274958Sdim return Cmp.comparePointers(Cvdecl, E->Cvdecl); 653274958Sdim } 654274958Sdim 655274958Sdimprivate: 656341825Sdim const ValueDecl *Cvdecl; 657274958Sdim}; 658274958Sdim 659280031Sdim/// A function -- a.k.a. lambda abstraction. 660280031Sdim/// Functions with multiple arguments are created by currying, 661280031Sdim/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) 662274958Sdimclass Function : public SExpr { 663274958Sdimpublic: 664274958Sdim Function(Variable *Vd, SExpr *Bd) 665274958Sdim : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 666274958Sdim Vd->setKind(Variable::VK_Fun); 667274958Sdim } 668341825Sdim 669274958Sdim Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 670274958Sdim : SExpr(F), VarDecl(Vd), Body(Bd) { 671274958Sdim Vd->setKind(Variable::VK_Fun); 672274958Sdim } 673274958Sdim 674341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 675341825Sdim 676274958Sdim Variable *variableDecl() { return VarDecl; } 677274958Sdim const Variable *variableDecl() const { return VarDecl; } 678274958Sdim 679280031Sdim SExpr *body() { return Body; } 680280031Sdim const SExpr *body() const { return Body; } 681274958Sdim 682274958Sdim template <class V> 683274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 684274958Sdim // This is a variable declaration, so traverse the definition. 685274958Sdim auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 686274958Sdim // Tell the rewriter to enter the scope of the function. 687274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, E0); 688274958Sdim auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 689274958Sdim Vs.exitScope(*VarDecl); 690274958Sdim return Vs.reduceFunction(*this, Nvd, E1); 691274958Sdim } 692274958Sdim 693280031Sdim template <class C> 694280031Sdim typename C::CType compare(const Function* E, C& Cmp) const { 695274958Sdim typename C::CType Ct = 696274958Sdim Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 697274958Sdim if (Cmp.notTrue(Ct)) 698274958Sdim return Ct; 699274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 700274958Sdim Ct = Cmp.compare(body(), E->body()); 701274958Sdim Cmp.leaveScope(); 702274958Sdim return Ct; 703274958Sdim } 704274958Sdim 705274958Sdimprivate: 706274958Sdim Variable *VarDecl; 707280031Sdim SExpr* Body; 708274958Sdim}; 709274958Sdim 710280031Sdim/// A self-applicable function. 711280031Sdim/// A self-applicable function can be applied to itself. It's useful for 712280031Sdim/// implementing objects and late binding. 713274958Sdimclass SFunction : public SExpr { 714274958Sdimpublic: 715274958Sdim SFunction(Variable *Vd, SExpr *B) 716274958Sdim : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 717274958Sdim assert(Vd->Definition == nullptr); 718274958Sdim Vd->setKind(Variable::VK_SFun); 719280031Sdim Vd->Definition = this; 720274958Sdim } 721341825Sdim 722274958Sdim SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 723274958Sdim : SExpr(F), VarDecl(Vd), Body(B) { 724274958Sdim assert(Vd->Definition == nullptr); 725274958Sdim Vd->setKind(Variable::VK_SFun); 726280031Sdim Vd->Definition = this; 727274958Sdim } 728274958Sdim 729341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 730341825Sdim 731274958Sdim Variable *variableDecl() { return VarDecl; } 732274958Sdim const Variable *variableDecl() const { return VarDecl; } 733274958Sdim 734280031Sdim SExpr *body() { return Body; } 735280031Sdim const SExpr *body() const { return Body; } 736274958Sdim 737274958Sdim template <class V> 738274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 739274958Sdim // A self-variable points to the SFunction itself. 740274958Sdim // A rewrite must introduce the variable with a null definition, and update 741274958Sdim // it after 'this' has been rewritten. 742274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 743274958Sdim auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 744274958Sdim Vs.exitScope(*VarDecl); 745274958Sdim // A rewrite operation will call SFun constructor to set Vvd->Definition. 746274958Sdim return Vs.reduceSFunction(*this, Nvd, E1); 747274958Sdim } 748274958Sdim 749280031Sdim template <class C> 750280031Sdim typename C::CType compare(const SFunction* E, C& Cmp) const { 751274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 752274958Sdim typename C::CType Ct = Cmp.compare(body(), E->body()); 753274958Sdim Cmp.leaveScope(); 754274958Sdim return Ct; 755274958Sdim } 756274958Sdim 757274958Sdimprivate: 758274958Sdim Variable *VarDecl; 759280031Sdim SExpr* Body; 760274958Sdim}; 761274958Sdim 762280031Sdim/// A block of code -- e.g. the body of a function. 763274958Sdimclass Code : public SExpr { 764274958Sdimpublic: 765274958Sdim Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 766274958Sdim Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 767274958Sdim : SExpr(C), ReturnType(T), Body(B) {} 768274958Sdim 769341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 770341825Sdim 771280031Sdim SExpr *returnType() { return ReturnType; } 772280031Sdim const SExpr *returnType() const { return ReturnType; } 773274958Sdim 774280031Sdim SExpr *body() { return Body; } 775280031Sdim const SExpr *body() const { return Body; } 776274958Sdim 777274958Sdim template <class V> 778274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 779274958Sdim auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 780274958Sdim auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 781274958Sdim return Vs.reduceCode(*this, Nt, Nb); 782274958Sdim } 783274958Sdim 784280031Sdim template <class C> 785280031Sdim typename C::CType compare(const Code* E, C& Cmp) const { 786274958Sdim typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 787274958Sdim if (Cmp.notTrue(Ct)) 788274958Sdim return Ct; 789274958Sdim return Cmp.compare(body(), E->body()); 790274958Sdim } 791274958Sdim 792274958Sdimprivate: 793280031Sdim SExpr* ReturnType; 794280031Sdim SExpr* Body; 795274958Sdim}; 796274958Sdim 797280031Sdim/// A typed, writable location in memory 798274958Sdimclass Field : public SExpr { 799274958Sdimpublic: 800274958Sdim Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 801274958Sdim Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 802274958Sdim : SExpr(C), Range(R), Body(B) {} 803274958Sdim 804341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 805341825Sdim 806280031Sdim SExpr *range() { return Range; } 807280031Sdim const SExpr *range() const { return Range; } 808274958Sdim 809280031Sdim SExpr *body() { return Body; } 810280031Sdim const SExpr *body() const { return Body; } 811274958Sdim 812274958Sdim template <class V> 813274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 814274958Sdim auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 815274958Sdim auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 816274958Sdim return Vs.reduceField(*this, Nr, Nb); 817274958Sdim } 818274958Sdim 819280031Sdim template <class C> 820280031Sdim typename C::CType compare(const Field* E, C& Cmp) const { 821274958Sdim typename C::CType Ct = Cmp.compare(range(), E->range()); 822274958Sdim if (Cmp.notTrue(Ct)) 823274958Sdim return Ct; 824274958Sdim return Cmp.compare(body(), E->body()); 825274958Sdim } 826274958Sdim 827274958Sdimprivate: 828280031Sdim SExpr* Range; 829280031Sdim SExpr* Body; 830274958Sdim}; 831274958Sdim 832280031Sdim/// Apply an argument to a function. 833280031Sdim/// Note that this does not actually call the function. Functions are curried, 834280031Sdim/// so this returns a closure in which the first parameter has been applied. 835280031Sdim/// Once all parameters have been applied, Call can be used to invoke the 836280031Sdim/// function. 837274958Sdimclass Apply : public SExpr { 838274958Sdimpublic: 839274958Sdim Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 840274958Sdim Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 841341825Sdim : SExpr(A), Fun(F), Arg(Ar) {} 842274958Sdim 843341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 844341825Sdim 845280031Sdim SExpr *fun() { return Fun; } 846280031Sdim const SExpr *fun() const { return Fun; } 847274958Sdim 848280031Sdim SExpr *arg() { return Arg; } 849280031Sdim const SExpr *arg() const { return Arg; } 850274958Sdim 851274958Sdim template <class V> 852274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 853274958Sdim auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 854274958Sdim auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 855274958Sdim return Vs.reduceApply(*this, Nf, Na); 856274958Sdim } 857274958Sdim 858280031Sdim template <class C> 859280031Sdim typename C::CType compare(const Apply* E, C& Cmp) const { 860274958Sdim typename C::CType Ct = Cmp.compare(fun(), E->fun()); 861274958Sdim if (Cmp.notTrue(Ct)) 862274958Sdim return Ct; 863274958Sdim return Cmp.compare(arg(), E->arg()); 864274958Sdim } 865274958Sdim 866274958Sdimprivate: 867280031Sdim SExpr* Fun; 868280031Sdim SExpr* Arg; 869274958Sdim}; 870274958Sdim 871280031Sdim/// Apply a self-argument to a self-applicable function. 872274958Sdimclass SApply : public SExpr { 873274958Sdimpublic: 874274958Sdim SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} 875274958Sdim SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor 876274958Sdim : SExpr(A), Sfun(Sf), Arg(Ar) {} 877274958Sdim 878341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 879341825Sdim 880280031Sdim SExpr *sfun() { return Sfun; } 881280031Sdim const SExpr *sfun() const { return Sfun; } 882274958Sdim 883280031Sdim SExpr *arg() { return Arg ? Arg : Sfun; } 884280031Sdim const SExpr *arg() const { return Arg ? Arg : Sfun; } 885274958Sdim 886280031Sdim bool isDelegation() const { return Arg != nullptr; } 887274958Sdim 888274958Sdim template <class V> 889274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 890274958Sdim auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 891280031Sdim typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 892274958Sdim : nullptr; 893274958Sdim return Vs.reduceSApply(*this, Nf, Na); 894274958Sdim } 895274958Sdim 896280031Sdim template <class C> 897280031Sdim typename C::CType compare(const SApply* E, C& Cmp) const { 898274958Sdim typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 899274958Sdim if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 900274958Sdim return Ct; 901274958Sdim return Cmp.compare(arg(), E->arg()); 902274958Sdim } 903274958Sdim 904274958Sdimprivate: 905280031Sdim SExpr* Sfun; 906280031Sdim SExpr* Arg; 907274958Sdim}; 908274958Sdim 909280031Sdim/// Project a named slot from a C++ struct or class. 910274958Sdimclass Project : public SExpr { 911274958Sdimpublic: 912341825Sdim Project(SExpr *R, const ValueDecl *Cvd) 913327952Sdim : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { 914327952Sdim assert(Cvd && "ValueDecl must not be null"); 915327952Sdim } 916274958Sdim 917341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 918341825Sdim 919280031Sdim SExpr *record() { return Rec; } 920280031Sdim const SExpr *record() const { return Rec; } 921274958Sdim 922341825Sdim const ValueDecl *clangDecl() const { return Cvdecl; } 923274958Sdim 924280031Sdim bool isArrow() const { return (Flags & 0x01) != 0; } 925341825Sdim 926280031Sdim void setArrow(bool b) { 927280031Sdim if (b) Flags |= 0x01; 928280031Sdim else Flags &= 0xFFFE; 929280031Sdim } 930280031Sdim 931274958Sdim StringRef slotName() const { 932327952Sdim if (Cvdecl->getDeclName().isIdentifier()) 933274958Sdim return Cvdecl->getName(); 934327952Sdim if (!SlotName) { 935327952Sdim SlotName = ""; 936327952Sdim llvm::raw_string_ostream OS(*SlotName); 937327952Sdim Cvdecl->printName(OS); 938327952Sdim } 939327952Sdim return *SlotName; 940274958Sdim } 941274958Sdim 942274958Sdim template <class V> 943274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 944274958Sdim auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 945274958Sdim return Vs.reduceProject(*this, Nr); 946274958Sdim } 947274958Sdim 948280031Sdim template <class C> 949280031Sdim typename C::CType compare(const Project* E, C& Cmp) const { 950274958Sdim typename C::CType Ct = Cmp.compare(record(), E->record()); 951274958Sdim if (Cmp.notTrue(Ct)) 952274958Sdim return Ct; 953274958Sdim return Cmp.comparePointers(Cvdecl, E->Cvdecl); 954274958Sdim } 955274958Sdim 956274958Sdimprivate: 957280031Sdim SExpr* Rec; 958327952Sdim mutable llvm::Optional<std::string> SlotName; 959341825Sdim const ValueDecl *Cvdecl; 960274958Sdim}; 961274958Sdim 962280031Sdim/// Call a function (after all arguments have been applied). 963274958Sdimclass Call : public SExpr { 964274958Sdimpublic: 965341825Sdim Call(SExpr *T, const CallExpr *Ce = nullptr) 966274958Sdim : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 967274958Sdim Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 968274958Sdim 969341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 970341825Sdim 971280031Sdim SExpr *target() { return Target; } 972280031Sdim const SExpr *target() const { return Target; } 973274958Sdim 974341825Sdim const CallExpr *clangCallExpr() const { return Cexpr; } 975274958Sdim 976274958Sdim template <class V> 977274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 978274958Sdim auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 979274958Sdim return Vs.reduceCall(*this, Nt); 980274958Sdim } 981274958Sdim 982280031Sdim template <class C> 983280031Sdim typename C::CType compare(const Call* E, C& Cmp) const { 984274958Sdim return Cmp.compare(target(), E->target()); 985274958Sdim } 986274958Sdim 987274958Sdimprivate: 988280031Sdim SExpr* Target; 989341825Sdim const CallExpr *Cexpr; 990274958Sdim}; 991274958Sdim 992280031Sdim/// Allocate memory for a new value on the heap or stack. 993274958Sdimclass Alloc : public SExpr { 994274958Sdimpublic: 995274958Sdim enum AllocKind { 996274958Sdim AK_Stack, 997274958Sdim AK_Heap 998274958Sdim }; 999274958Sdim 1000274958Sdim Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 1001274958Sdim Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 1002274958Sdim 1003341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 1004341825Sdim 1005274958Sdim AllocKind kind() const { return static_cast<AllocKind>(Flags); } 1006274958Sdim 1007280031Sdim SExpr *dataType() { return Dtype; } 1008280031Sdim const SExpr *dataType() const { return Dtype; } 1009274958Sdim 1010274958Sdim template <class V> 1011274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1012274958Sdim auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); 1013274958Sdim return Vs.reduceAlloc(*this, Nd); 1014274958Sdim } 1015274958Sdim 1016280031Sdim template <class C> 1017280031Sdim typename C::CType compare(const Alloc* E, C& Cmp) const { 1018274958Sdim typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); 1019274958Sdim if (Cmp.notTrue(Ct)) 1020274958Sdim return Ct; 1021274958Sdim return Cmp.compare(dataType(), E->dataType()); 1022274958Sdim } 1023274958Sdim 1024274958Sdimprivate: 1025280031Sdim SExpr* Dtype; 1026274958Sdim}; 1027274958Sdim 1028280031Sdim/// Load a value from memory. 1029274958Sdimclass Load : public SExpr { 1030274958Sdimpublic: 1031274958Sdim Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 1032274958Sdim Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 1033274958Sdim 1034341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 1035341825Sdim 1036280031Sdim SExpr *pointer() { return Ptr; } 1037280031Sdim const SExpr *pointer() const { return Ptr; } 1038274958Sdim 1039274958Sdim template <class V> 1040274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1041274958Sdim auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1042274958Sdim return Vs.reduceLoad(*this, Np); 1043274958Sdim } 1044274958Sdim 1045280031Sdim template <class C> 1046280031Sdim typename C::CType compare(const Load* E, C& Cmp) const { 1047274958Sdim return Cmp.compare(pointer(), E->pointer()); 1048274958Sdim } 1049274958Sdim 1050274958Sdimprivate: 1051280031Sdim SExpr* Ptr; 1052274958Sdim}; 1053274958Sdim 1054280031Sdim/// Store a value to memory. 1055280031Sdim/// The destination is a pointer to a field, the source is the value to store. 1056274958Sdimclass Store : public SExpr { 1057274958Sdimpublic: 1058274958Sdim Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 1059274958Sdim Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 1060274958Sdim 1061341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 1062341825Sdim 1063280031Sdim SExpr *destination() { return Dest; } // Address to store to 1064280031Sdim const SExpr *destination() const { return Dest; } 1065274958Sdim 1066280031Sdim SExpr *source() { return Source; } // Value to store 1067280031Sdim const SExpr *source() const { return Source; } 1068274958Sdim 1069274958Sdim template <class V> 1070274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1071274958Sdim auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1072274958Sdim auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1073274958Sdim return Vs.reduceStore(*this, Np, Nv); 1074274958Sdim } 1075274958Sdim 1076280031Sdim template <class C> 1077280031Sdim typename C::CType compare(const Store* E, C& Cmp) const { 1078274958Sdim typename C::CType Ct = Cmp.compare(destination(), E->destination()); 1079274958Sdim if (Cmp.notTrue(Ct)) 1080274958Sdim return Ct; 1081274958Sdim return Cmp.compare(source(), E->source()); 1082274958Sdim } 1083274958Sdim 1084274958Sdimprivate: 1085280031Sdim SExpr* Dest; 1086280031Sdim SExpr* Source; 1087274958Sdim}; 1088274958Sdim 1089280031Sdim/// If p is a reference to an array, then p[i] is a reference to the i'th 1090280031Sdim/// element of the array. 1091274958Sdimclass ArrayIndex : public SExpr { 1092274958Sdimpublic: 1093274958Sdim ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1094274958Sdim ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1095341825Sdim : SExpr(E), Array(A), Index(N) {} 1096274958Sdim 1097341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 1098341825Sdim 1099280031Sdim SExpr *array() { return Array; } 1100280031Sdim const SExpr *array() const { return Array; } 1101274958Sdim 1102280031Sdim SExpr *index() { return Index; } 1103280031Sdim const SExpr *index() const { return Index; } 1104274958Sdim 1105274958Sdim template <class V> 1106274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1107274958Sdim auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1108274958Sdim auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1109274958Sdim return Vs.reduceArrayIndex(*this, Na, Ni); 1110274958Sdim } 1111274958Sdim 1112280031Sdim template <class C> 1113280031Sdim typename C::CType compare(const ArrayIndex* E, C& Cmp) const { 1114274958Sdim typename C::CType Ct = Cmp.compare(array(), E->array()); 1115274958Sdim if (Cmp.notTrue(Ct)) 1116274958Sdim return Ct; 1117274958Sdim return Cmp.compare(index(), E->index()); 1118274958Sdim } 1119274958Sdim 1120274958Sdimprivate: 1121280031Sdim SExpr* Array; 1122280031Sdim SExpr* Index; 1123274958Sdim}; 1124274958Sdim 1125280031Sdim/// Pointer arithmetic, restricted to arrays only. 1126280031Sdim/// If p is a reference to an array, then p + n, where n is an integer, is 1127280031Sdim/// a reference to a subarray. 1128274958Sdimclass ArrayAdd : public SExpr { 1129274958Sdimpublic: 1130274958Sdim ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 1131274958Sdim ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 1132341825Sdim : SExpr(E), Array(A), Index(N) {} 1133274958Sdim 1134341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 1135341825Sdim 1136280031Sdim SExpr *array() { return Array; } 1137280031Sdim const SExpr *array() const { return Array; } 1138274958Sdim 1139280031Sdim SExpr *index() { return Index; } 1140280031Sdim const SExpr *index() const { return Index; } 1141274958Sdim 1142274958Sdim template <class V> 1143274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1144274958Sdim auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1145274958Sdim auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1146274958Sdim return Vs.reduceArrayAdd(*this, Na, Ni); 1147274958Sdim } 1148274958Sdim 1149280031Sdim template <class C> 1150280031Sdim typename C::CType compare(const ArrayAdd* E, C& Cmp) const { 1151274958Sdim typename C::CType Ct = Cmp.compare(array(), E->array()); 1152274958Sdim if (Cmp.notTrue(Ct)) 1153274958Sdim return Ct; 1154274958Sdim return Cmp.compare(index(), E->index()); 1155274958Sdim } 1156274958Sdim 1157274958Sdimprivate: 1158280031Sdim SExpr* Array; 1159280031Sdim SExpr* Index; 1160274958Sdim}; 1161274958Sdim 1162280031Sdim/// Simple arithmetic unary operations, e.g. negate and not. 1163280031Sdim/// These operations have no side-effects. 1164274958Sdimclass UnaryOp : public SExpr { 1165274958Sdimpublic: 1166274958Sdim UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 1167274958Sdim Flags = Op; 1168274958Sdim } 1169341825Sdim 1170274958Sdim UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 1171274958Sdim 1172341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 1173341825Sdim 1174274958Sdim TIL_UnaryOpcode unaryOpcode() const { 1175274958Sdim return static_cast<TIL_UnaryOpcode>(Flags); 1176274958Sdim } 1177274958Sdim 1178280031Sdim SExpr *expr() { return Expr0; } 1179280031Sdim const SExpr *expr() const { return Expr0; } 1180274958Sdim 1181274958Sdim template <class V> 1182274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1183274958Sdim auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1184274958Sdim return Vs.reduceUnaryOp(*this, Ne); 1185274958Sdim } 1186274958Sdim 1187280031Sdim template <class C> 1188280031Sdim typename C::CType compare(const UnaryOp* E, C& Cmp) const { 1189274958Sdim typename C::CType Ct = 1190274958Sdim Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 1191274958Sdim if (Cmp.notTrue(Ct)) 1192274958Sdim return Ct; 1193274958Sdim return Cmp.compare(expr(), E->expr()); 1194274958Sdim } 1195274958Sdim 1196274958Sdimprivate: 1197280031Sdim SExpr* Expr0; 1198274958Sdim}; 1199274958Sdim 1200280031Sdim/// Simple arithmetic binary operations, e.g. +, -, etc. 1201280031Sdim/// These operations have no side effects. 1202274958Sdimclass BinaryOp : public SExpr { 1203274958Sdimpublic: 1204274958Sdim BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 1205274958Sdim : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 1206274958Sdim Flags = Op; 1207274958Sdim } 1208341825Sdim 1209274958Sdim BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 1210274958Sdim : SExpr(B), Expr0(E0), Expr1(E1) { 1211274958Sdim Flags = B.Flags; 1212274958Sdim } 1213274958Sdim 1214341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 1215341825Sdim 1216274958Sdim TIL_BinaryOpcode binaryOpcode() const { 1217274958Sdim return static_cast<TIL_BinaryOpcode>(Flags); 1218274958Sdim } 1219274958Sdim 1220280031Sdim SExpr *expr0() { return Expr0; } 1221280031Sdim const SExpr *expr0() const { return Expr0; } 1222274958Sdim 1223280031Sdim SExpr *expr1() { return Expr1; } 1224280031Sdim const SExpr *expr1() const { return Expr1; } 1225274958Sdim 1226274958Sdim template <class V> 1227274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1228274958Sdim auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1229274958Sdim auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1230274958Sdim return Vs.reduceBinaryOp(*this, Ne0, Ne1); 1231274958Sdim } 1232274958Sdim 1233280031Sdim template <class C> 1234280031Sdim typename C::CType compare(const BinaryOp* E, C& Cmp) const { 1235274958Sdim typename C::CType Ct = 1236274958Sdim Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 1237274958Sdim if (Cmp.notTrue(Ct)) 1238274958Sdim return Ct; 1239274958Sdim Ct = Cmp.compare(expr0(), E->expr0()); 1240274958Sdim if (Cmp.notTrue(Ct)) 1241274958Sdim return Ct; 1242274958Sdim return Cmp.compare(expr1(), E->expr1()); 1243274958Sdim } 1244274958Sdim 1245274958Sdimprivate: 1246280031Sdim SExpr* Expr0; 1247280031Sdim SExpr* Expr1; 1248274958Sdim}; 1249274958Sdim 1250280031Sdim/// Cast expressions. 1251280031Sdim/// Cast expressions are essentially unary operations, but we treat them 1252280031Sdim/// as a distinct AST node because they only change the type of the result. 1253274958Sdimclass Cast : public SExpr { 1254274958Sdimpublic: 1255274958Sdim Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 1256274958Sdim Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 1257274958Sdim 1258341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 1259341825Sdim 1260274958Sdim TIL_CastOpcode castOpcode() const { 1261274958Sdim return static_cast<TIL_CastOpcode>(Flags); 1262274958Sdim } 1263274958Sdim 1264280031Sdim SExpr *expr() { return Expr0; } 1265280031Sdim const SExpr *expr() const { return Expr0; } 1266274958Sdim 1267274958Sdim template <class V> 1268274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1269274958Sdim auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1270274958Sdim return Vs.reduceCast(*this, Ne); 1271274958Sdim } 1272274958Sdim 1273280031Sdim template <class C> 1274280031Sdim typename C::CType compare(const Cast* E, C& Cmp) const { 1275274958Sdim typename C::CType Ct = 1276274958Sdim Cmp.compareIntegers(castOpcode(), E->castOpcode()); 1277274958Sdim if (Cmp.notTrue(Ct)) 1278274958Sdim return Ct; 1279274958Sdim return Cmp.compare(expr(), E->expr()); 1280274958Sdim } 1281274958Sdim 1282274958Sdimprivate: 1283280031Sdim SExpr* Expr0; 1284274958Sdim}; 1285274958Sdim 1286274958Sdimclass SCFG; 1287274958Sdim 1288280031Sdim/// Phi Node, for code in SSA form. 1289280031Sdim/// Each Phi node has an array of possible values that it can take, 1290280031Sdim/// depending on where control flow comes from. 1291274958Sdimclass Phi : public SExpr { 1292274958Sdimpublic: 1293341825Sdim using ValArray = SimpleArray<SExpr *>; 1294274958Sdim 1295274958Sdim // In minimal SSA form, all Phi nodes are MultiVal. 1296274958Sdim // During conversion to SSA, incomplete Phi nodes may be introduced, which 1297274958Sdim // are later determined to be SingleVal, and are thus redundant. 1298274958Sdim enum Status { 1299274958Sdim PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1300274958Sdim PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1301274958Sdim PH_Incomplete // Phi node is incomplete 1302274958Sdim }; 1303274958Sdim 1304341825Sdim Phi() : SExpr(COP_Phi) {} 1305341825Sdim Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} 1306341825Sdim Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} 1307341825Sdim 1308274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 1309274958Sdim 1310274958Sdim const ValArray &values() const { return Values; } 1311274958Sdim ValArray &values() { return Values; } 1312274958Sdim 1313274958Sdim Status status() const { return static_cast<Status>(Flags); } 1314274958Sdim void setStatus(Status s) { Flags = s; } 1315274958Sdim 1316280031Sdim /// Return the clang declaration of the variable for this Phi node, if any. 1317341825Sdim const ValueDecl *clangDecl() const { return Cvdecl; } 1318280031Sdim 1319280031Sdim /// Set the clang variable associated with this Phi node. 1320341825Sdim void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; } 1321280031Sdim 1322274958Sdim template <class V> 1323274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1324274958Sdim typename V::template Container<typename V::R_SExpr> 1325274958Sdim Nvs(Vs, Values.size()); 1326274958Sdim 1327341825Sdim for (const auto *Val : Values) 1328274958Sdim Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1329274958Sdim return Vs.reducePhi(*this, Nvs); 1330274958Sdim } 1331274958Sdim 1332280031Sdim template <class C> 1333280031Sdim typename C::CType compare(const Phi *E, C &Cmp) const { 1334274958Sdim // TODO: implement CFG comparisons 1335274958Sdim return Cmp.comparePointers(this, E); 1336274958Sdim } 1337274958Sdim 1338274958Sdimprivate: 1339274958Sdim ValArray Values; 1340341825Sdim const ValueDecl* Cvdecl = nullptr; 1341274958Sdim}; 1342274958Sdim 1343280031Sdim/// Base class for basic block terminators: Branch, Goto, and Return. 1344280031Sdimclass Terminator : public SExpr { 1345341825Sdimprotected: 1346341825Sdim Terminator(TIL_Opcode Op) : SExpr(Op) {} 1347341825Sdim Terminator(const SExpr &E) : SExpr(E) {} 1348341825Sdim 1349280031Sdimpublic: 1350280031Sdim static bool classof(const SExpr *E) { 1351280031Sdim return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; 1352280031Sdim } 1353280031Sdim 1354280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1355341825Sdim ArrayRef<BasicBlock *> successors(); 1356280031Sdim 1357341825Sdim ArrayRef<BasicBlock *> successors() const { 1358280031Sdim return const_cast<Terminator*>(this)->successors(); 1359280031Sdim } 1360280031Sdim}; 1361280031Sdim 1362280031Sdim/// Jump to another basic block. 1363280031Sdim/// A goto instruction is essentially a tail-recursive call into another 1364280031Sdim/// block. In addition to the block pointer, it specifies an index into the 1365280031Sdim/// phi nodes of that block. The index can be used to retrieve the "arguments" 1366280031Sdim/// of the call. 1367280031Sdimclass Goto : public Terminator { 1368280031Sdimpublic: 1369280031Sdim Goto(BasicBlock *B, unsigned I) 1370280031Sdim : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1371280031Sdim Goto(const Goto &G, BasicBlock *B, unsigned I) 1372280031Sdim : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1373280031Sdim 1374341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1375341825Sdim 1376280031Sdim const BasicBlock *targetBlock() const { return TargetBlock; } 1377280031Sdim BasicBlock *targetBlock() { return TargetBlock; } 1378280031Sdim 1379280031Sdim /// Returns the index into the 1380280031Sdim unsigned index() const { return Index; } 1381280031Sdim 1382280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1383341825Sdim ArrayRef<BasicBlock *> successors() { return TargetBlock; } 1384280031Sdim 1385280031Sdim template <class V> 1386280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1387280031Sdim BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1388280031Sdim return Vs.reduceGoto(*this, Ntb); 1389280031Sdim } 1390280031Sdim 1391280031Sdim template <class C> 1392280031Sdim typename C::CType compare(const Goto *E, C &Cmp) const { 1393280031Sdim // TODO: implement CFG comparisons 1394280031Sdim return Cmp.comparePointers(this, E); 1395280031Sdim } 1396280031Sdim 1397280031Sdimprivate: 1398280031Sdim BasicBlock *TargetBlock; 1399280031Sdim unsigned Index; 1400280031Sdim}; 1401280031Sdim 1402280031Sdim/// A conditional branch to two other blocks. 1403280031Sdim/// Note that unlike Goto, Branch does not have an index. The target blocks 1404280031Sdim/// must be child-blocks, and cannot have Phi nodes. 1405280031Sdimclass Branch : public Terminator { 1406280031Sdimpublic: 1407280031Sdim Branch(SExpr *C, BasicBlock *T, BasicBlock *E) 1408280031Sdim : Terminator(COP_Branch), Condition(C) { 1409280031Sdim Branches[0] = T; 1410280031Sdim Branches[1] = E; 1411280031Sdim } 1412341825Sdim 1413280031Sdim Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) 1414280031Sdim : Terminator(Br), Condition(C) { 1415280031Sdim Branches[0] = T; 1416280031Sdim Branches[1] = E; 1417280031Sdim } 1418280031Sdim 1419341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1420341825Sdim 1421280031Sdim const SExpr *condition() const { return Condition; } 1422280031Sdim SExpr *condition() { return Condition; } 1423280031Sdim 1424280031Sdim const BasicBlock *thenBlock() const { return Branches[0]; } 1425280031Sdim BasicBlock *thenBlock() { return Branches[0]; } 1426280031Sdim 1427280031Sdim const BasicBlock *elseBlock() const { return Branches[1]; } 1428280031Sdim BasicBlock *elseBlock() { return Branches[1]; } 1429280031Sdim 1430280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1431280031Sdim ArrayRef<BasicBlock*> successors() { 1432296417Sdim return llvm::makeArrayRef(Branches); 1433280031Sdim } 1434280031Sdim 1435280031Sdim template <class V> 1436280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1437280031Sdim auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1438280031Sdim BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); 1439280031Sdim BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); 1440280031Sdim return Vs.reduceBranch(*this, Nc, Ntb, Nte); 1441280031Sdim } 1442280031Sdim 1443280031Sdim template <class C> 1444280031Sdim typename C::CType compare(const Branch *E, C &Cmp) const { 1445280031Sdim // TODO: implement CFG comparisons 1446280031Sdim return Cmp.comparePointers(this, E); 1447280031Sdim } 1448280031Sdim 1449280031Sdimprivate: 1450341825Sdim SExpr *Condition; 1451280031Sdim BasicBlock *Branches[2]; 1452280031Sdim}; 1453280031Sdim 1454280031Sdim/// Return from the enclosing function, passing the return value to the caller. 1455280031Sdim/// Only the exit block should end with a return statement. 1456280031Sdimclass Return : public Terminator { 1457280031Sdimpublic: 1458280031Sdim Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} 1459280031Sdim Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} 1460280031Sdim 1461341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } 1462341825Sdim 1463280031Sdim /// Return an empty list. 1464341825Sdim ArrayRef<BasicBlock *> successors() { return None; } 1465280031Sdim 1466280031Sdim SExpr *returnValue() { return Retval; } 1467280031Sdim const SExpr *returnValue() const { return Retval; } 1468280031Sdim 1469280031Sdim template <class V> 1470280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1471280031Sdim auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); 1472280031Sdim return Vs.reduceReturn(*this, Ne); 1473280031Sdim } 1474280031Sdim 1475280031Sdim template <class C> 1476280031Sdim typename C::CType compare(const Return *E, C &Cmp) const { 1477280031Sdim return Cmp.compare(Retval, E->Retval); 1478280031Sdim } 1479280031Sdim 1480280031Sdimprivate: 1481280031Sdim SExpr* Retval; 1482280031Sdim}; 1483280031Sdim 1484280031Sdiminline ArrayRef<BasicBlock*> Terminator::successors() { 1485280031Sdim switch (opcode()) { 1486280031Sdim case COP_Goto: return cast<Goto>(this)->successors(); 1487280031Sdim case COP_Branch: return cast<Branch>(this)->successors(); 1488280031Sdim case COP_Return: return cast<Return>(this)->successors(); 1489280031Sdim default: 1490296417Sdim return None; 1491280031Sdim } 1492280031Sdim} 1493280031Sdim 1494280031Sdim/// A basic block is part of an SCFG. It can be treated as a function in 1495280031Sdim/// continuation passing style. A block consists of a sequence of phi nodes, 1496280031Sdim/// which are "arguments" to the function, followed by a sequence of 1497280031Sdim/// instructions. It ends with a Terminator, which is a Branch or Goto to 1498280031Sdim/// another basic block in the same SCFG. 1499274958Sdimclass BasicBlock : public SExpr { 1500274958Sdimpublic: 1501341825Sdim using InstrArray = SimpleArray<SExpr *>; 1502341825Sdim using BlockArray = SimpleArray<BasicBlock *>; 1503274958Sdim 1504280031Sdim // TopologyNodes are used to overlay tree structures on top of the CFG, 1505280031Sdim // such as dominator and postdominator trees. Each block is assigned an 1506280031Sdim // ID in the tree according to a depth-first search. Tree traversals are 1507280031Sdim // always up, towards the parents. 1508280031Sdim struct TopologyNode { 1509341825Sdim int NodeID = 0; 1510280031Sdim 1511341825Sdim // Includes this node, so must be > 1. 1512341825Sdim int SizeOfSubTree = 0; 1513341825Sdim 1514341825Sdim // Pointer to parent. 1515341825Sdim BasicBlock *Parent = nullptr; 1516341825Sdim 1517341825Sdim TopologyNode() = default; 1518341825Sdim 1519280031Sdim bool isParentOf(const TopologyNode& OtherNode) { 1520280031Sdim return OtherNode.NodeID > NodeID && 1521280031Sdim OtherNode.NodeID < NodeID + SizeOfSubTree; 1522280031Sdim } 1523280031Sdim 1524280031Sdim bool isParentOfOrEqual(const TopologyNode& OtherNode) { 1525280031Sdim return OtherNode.NodeID >= NodeID && 1526280031Sdim OtherNode.NodeID < NodeID + SizeOfSubTree; 1527280031Sdim } 1528280031Sdim }; 1529280031Sdim 1530280031Sdim explicit BasicBlock(MemRegionRef A) 1531341825Sdim : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {} 1532280031Sdim BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, 1533280031Sdim Terminator *T) 1534341825Sdim : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false), 1535280031Sdim Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} 1536274958Sdim 1537341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } 1538341825Sdim 1539280031Sdim /// Returns the block ID. Every block has a unique ID in the CFG. 1540280031Sdim int blockID() const { return BlockID; } 1541274958Sdim 1542280031Sdim /// Returns the number of predecessors. 1543280031Sdim size_t numPredecessors() const { return Predecessors.size(); } 1544280031Sdim size_t numSuccessors() const { return successors().size(); } 1545280031Sdim 1546274958Sdim const SCFG* cfg() const { return CFGPtr; } 1547274958Sdim SCFG* cfg() { return CFGPtr; } 1548274958Sdim 1549280031Sdim const BasicBlock *parent() const { return DominatorNode.Parent; } 1550280031Sdim BasicBlock *parent() { return DominatorNode.Parent; } 1551274958Sdim 1552280031Sdim const InstrArray &arguments() const { return Args; } 1553280031Sdim InstrArray &arguments() { return Args; } 1554274958Sdim 1555280031Sdim InstrArray &instructions() { return Instrs; } 1556280031Sdim const InstrArray &instructions() const { return Instrs; } 1557274958Sdim 1558280031Sdim /// Returns a list of predecessors. 1559280031Sdim /// The order of predecessors in the list is important; each phi node has 1560280031Sdim /// exactly one argument for each precessor, in the same order. 1561280031Sdim BlockArray &predecessors() { return Predecessors; } 1562274958Sdim const BlockArray &predecessors() const { return Predecessors; } 1563274958Sdim 1564280031Sdim ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } 1565280031Sdim ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } 1566274958Sdim 1567280031Sdim const Terminator *terminator() const { return TermInstr; } 1568280031Sdim Terminator *terminator() { return TermInstr; } 1569274958Sdim 1570280031Sdim void setTerminator(Terminator *E) { TermInstr = E; } 1571280031Sdim 1572280031Sdim bool Dominates(const BasicBlock &Other) { 1573280031Sdim return DominatorNode.isParentOfOrEqual(Other.DominatorNode); 1574280031Sdim } 1575280031Sdim 1576280031Sdim bool PostDominates(const BasicBlock &Other) { 1577280031Sdim return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); 1578280031Sdim } 1579280031Sdim 1580280031Sdim /// Add a new argument. 1581280031Sdim void addArgument(Phi *V) { 1582274958Sdim Args.reserveCheck(1, Arena); 1583274958Sdim Args.push_back(V); 1584274958Sdim } 1585341825Sdim 1586280031Sdim /// Add a new instruction. 1587280031Sdim void addInstruction(SExpr *V) { 1588274958Sdim Instrs.reserveCheck(1, Arena); 1589274958Sdim Instrs.push_back(V); 1590274958Sdim } 1591341825Sdim 1592274958Sdim // Add a new predecessor, and return the phi-node index for it. 1593274958Sdim // Will add an argument to all phi-nodes, initialized to nullptr. 1594274958Sdim unsigned addPredecessor(BasicBlock *Pred); 1595274958Sdim 1596274958Sdim // Reserve space for Nargs arguments. 1597274958Sdim void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } 1598274958Sdim 1599274958Sdim // Reserve space for Nins instructions. 1600274958Sdim void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } 1601274958Sdim 1602274958Sdim // Reserve space for NumPreds predecessors, including space in phi nodes. 1603274958Sdim void reservePredecessors(unsigned NumPreds); 1604274958Sdim 1605280031Sdim /// Return the index of BB, or Predecessors.size if BB is not a predecessor. 1606274958Sdim unsigned findPredecessorIndex(const BasicBlock *BB) const { 1607353358Sdim auto I = llvm::find(Predecessors, BB); 1608274958Sdim return std::distance(Predecessors.cbegin(), I); 1609274958Sdim } 1610274958Sdim 1611274958Sdim template <class V> 1612274958Sdim typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { 1613280031Sdim typename V::template Container<SExpr*> Nas(Vs, Args.size()); 1614280031Sdim typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); 1615274958Sdim 1616274958Sdim // Entering the basic block should do any scope initialization. 1617274958Sdim Vs.enterBasicBlock(*this); 1618274958Sdim 1619341825Sdim for (const auto *E : Args) { 1620280031Sdim auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1621280031Sdim Nas.push_back(Ne); 1622274958Sdim } 1623341825Sdim for (const auto *E : Instrs) { 1624280031Sdim auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1625280031Sdim Nis.push_back(Ne); 1626274958Sdim } 1627280031Sdim auto Nt = Vs.traverse(TermInstr, Ctx); 1628274958Sdim 1629274958Sdim // Exiting the basic block should handle any scope cleanup. 1630274958Sdim Vs.exitBasicBlock(*this); 1631274958Sdim 1632274958Sdim return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); 1633274958Sdim } 1634274958Sdim 1635280031Sdim template <class C> 1636280031Sdim typename C::CType compare(const BasicBlock *E, C &Cmp) const { 1637274958Sdim // TODO: implement CFG comparisons 1638274958Sdim return Cmp.comparePointers(this, E); 1639274958Sdim } 1640274958Sdim 1641274958Sdimprivate: 1642274958Sdim friend class SCFG; 1643274958Sdim 1644341825Sdim // assign unique ids to all instructions 1645344779Sdim unsigned renumberInstrs(unsigned id); 1646341825Sdim 1647344779Sdim unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); 1648344779Sdim unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); 1649280031Sdim void computeDominator(); 1650280031Sdim void computePostDominator(); 1651274958Sdim 1652341825Sdim // The arena used to allocate this block. 1653341825Sdim MemRegionRef Arena; 1654280031Sdim 1655341825Sdim // The CFG that contains this block. 1656341825Sdim SCFG *CFGPtr = nullptr; 1657341825Sdim 1658341825Sdim // Unique ID for this BB in the containing CFG. IDs are in topological order. 1659344779Sdim unsigned BlockID : 31; 1660341825Sdim 1661341825Sdim // Bit to determine if a block has been visited during a traversal. 1662341825Sdim bool Visited : 1; 1663341825Sdim 1664341825Sdim // Predecessor blocks in the CFG. 1665341825Sdim BlockArray Predecessors; 1666341825Sdim 1667341825Sdim // Phi nodes. One argument per predecessor. 1668341825Sdim InstrArray Args; 1669341825Sdim 1670341825Sdim // Instructions. 1671341825Sdim InstrArray Instrs; 1672341825Sdim 1673341825Sdim // Terminating instruction. 1674341825Sdim Terminator *TermInstr = nullptr; 1675341825Sdim 1676341825Sdim // The dominator tree. 1677341825Sdim TopologyNode DominatorNode; 1678341825Sdim 1679341825Sdim // The post-dominator tree. 1680341825Sdim TopologyNode PostDominatorNode; 1681274958Sdim}; 1682274958Sdim 1683280031Sdim/// An SCFG is a control-flow graph. It consists of a set of basic blocks, 1684280031Sdim/// each of which terminates in a branch to another basic block. There is one 1685280031Sdim/// entry point, and one exit point. 1686274958Sdimclass SCFG : public SExpr { 1687274958Sdimpublic: 1688341825Sdim using BlockArray = SimpleArray<BasicBlock *>; 1689341825Sdim using iterator = BlockArray::iterator; 1690341825Sdim using const_iterator = BlockArray::const_iterator; 1691274958Sdim 1692274958Sdim SCFG(MemRegionRef A, unsigned Nblocks) 1693341825Sdim : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) { 1694280031Sdim Entry = new (A) BasicBlock(A); 1695280031Sdim Exit = new (A) BasicBlock(A); 1696280031Sdim auto *V = new (A) Phi(); 1697274958Sdim Exit->addArgument(V); 1698280031Sdim Exit->setTerminator(new (A) Return(V)); 1699274958Sdim add(Entry); 1700274958Sdim add(Exit); 1701274958Sdim } 1702341825Sdim 1703274958Sdim SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba 1704341825Sdim : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) { 1705274958Sdim // TODO: set entry and exit! 1706274958Sdim } 1707274958Sdim 1708341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } 1709341825Sdim 1710280031Sdim /// Return true if this CFG is valid. 1711280031Sdim bool valid() const { return Entry && Exit && Blocks.size() > 0; } 1712280031Sdim 1713280031Sdim /// Return true if this CFG has been normalized. 1714280031Sdim /// After normalization, blocks are in topological order, and block and 1715280031Sdim /// instruction IDs have been assigned. 1716280031Sdim bool normal() const { return Normal; } 1717280031Sdim 1718274958Sdim iterator begin() { return Blocks.begin(); } 1719274958Sdim iterator end() { return Blocks.end(); } 1720274958Sdim 1721274958Sdim const_iterator begin() const { return cbegin(); } 1722274958Sdim const_iterator end() const { return cend(); } 1723274958Sdim 1724274958Sdim const_iterator cbegin() const { return Blocks.cbegin(); } 1725274958Sdim const_iterator cend() const { return Blocks.cend(); } 1726274958Sdim 1727274958Sdim const BasicBlock *entry() const { return Entry; } 1728274958Sdim BasicBlock *entry() { return Entry; } 1729274958Sdim const BasicBlock *exit() const { return Exit; } 1730274958Sdim BasicBlock *exit() { return Exit; } 1731274958Sdim 1732280031Sdim /// Return the number of blocks in the CFG. 1733280031Sdim /// Block::blockID() will return a number less than numBlocks(); 1734280031Sdim size_t numBlocks() const { return Blocks.size(); } 1735280031Sdim 1736280031Sdim /// Return the total number of instructions in the CFG. 1737280031Sdim /// This is useful for building instruction side-tables; 1738280031Sdim /// A call to SExpr::id() will return a number less than numInstructions(). 1739280031Sdim unsigned numInstructions() { return NumInstructions; } 1740280031Sdim 1741274958Sdim inline void add(BasicBlock *BB) { 1742280031Sdim assert(BB->CFGPtr == nullptr); 1743274958Sdim BB->CFGPtr = this; 1744274958Sdim Blocks.reserveCheck(1, Arena); 1745274958Sdim Blocks.push_back(BB); 1746274958Sdim } 1747274958Sdim 1748274958Sdim void setEntry(BasicBlock *BB) { Entry = BB; } 1749274958Sdim void setExit(BasicBlock *BB) { Exit = BB; } 1750274958Sdim 1751280031Sdim void computeNormalForm(); 1752274958Sdim 1753274958Sdim template <class V> 1754274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1755274958Sdim Vs.enterCFG(*this); 1756274958Sdim typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); 1757280031Sdim 1758341825Sdim for (const auto *B : Blocks) { 1759274958Sdim Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); 1760274958Sdim } 1761274958Sdim Vs.exitCFG(*this); 1762274958Sdim return Vs.reduceSCFG(*this, Bbs); 1763274958Sdim } 1764274958Sdim 1765280031Sdim template <class C> 1766280031Sdim typename C::CType compare(const SCFG *E, C &Cmp) const { 1767280031Sdim // TODO: implement CFG comparisons 1768274958Sdim return Cmp.comparePointers(this, E); 1769274958Sdim } 1770274958Sdim 1771274958Sdimprivate: 1772341825Sdim // assign unique ids to all instructions 1773341825Sdim void renumberInstrs(); 1774280031Sdim 1775274958Sdim MemRegionRef Arena; 1776341825Sdim BlockArray Blocks; 1777341825Sdim BasicBlock *Entry = nullptr; 1778341825Sdim BasicBlock *Exit = nullptr; 1779341825Sdim unsigned NumInstructions = 0; 1780341825Sdim bool Normal = false; 1781274958Sdim}; 1782274958Sdim 1783280031Sdim/// An identifier, e.g. 'foo' or 'x'. 1784280031Sdim/// This is a pseduo-term; it will be lowered to a variable or projection. 1785274958Sdimclass Identifier : public SExpr { 1786274958Sdimpublic: 1787341825Sdim Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {} 1788341825Sdim Identifier(const Identifier &) = default; 1789341825Sdim 1790274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } 1791274958Sdim 1792274958Sdim StringRef name() const { return Name; } 1793274958Sdim 1794274958Sdim template <class V> 1795274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1796274958Sdim return Vs.reduceIdentifier(*this); 1797274958Sdim } 1798274958Sdim 1799280031Sdim template <class C> 1800280031Sdim typename C::CType compare(const Identifier* E, C& Cmp) const { 1801274958Sdim return Cmp.compareStrings(name(), E->name()); 1802274958Sdim } 1803274958Sdim 1804274958Sdimprivate: 1805274958Sdim StringRef Name; 1806274958Sdim}; 1807274958Sdim 1808280031Sdim/// An if-then-else expression. 1809280031Sdim/// This is a pseduo-term; it will be lowered to a branch in a CFG. 1810274958Sdimclass IfThenElse : public SExpr { 1811274958Sdimpublic: 1812274958Sdim IfThenElse(SExpr *C, SExpr *T, SExpr *E) 1813341825Sdim : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {} 1814274958Sdim IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) 1815341825Sdim : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {} 1816274958Sdim 1817341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } 1818341825Sdim 1819280031Sdim SExpr *condition() { return Condition; } // Address to store to 1820280031Sdim const SExpr *condition() const { return Condition; } 1821274958Sdim 1822280031Sdim SExpr *thenExpr() { return ThenExpr; } // Value to store 1823280031Sdim const SExpr *thenExpr() const { return ThenExpr; } 1824274958Sdim 1825280031Sdim SExpr *elseExpr() { return ElseExpr; } // Value to store 1826280031Sdim const SExpr *elseExpr() const { return ElseExpr; } 1827274958Sdim 1828274958Sdim template <class V> 1829274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1830274958Sdim auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1831274958Sdim auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); 1832274958Sdim auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); 1833274958Sdim return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); 1834274958Sdim } 1835274958Sdim 1836280031Sdim template <class C> 1837280031Sdim typename C::CType compare(const IfThenElse* E, C& Cmp) const { 1838274958Sdim typename C::CType Ct = Cmp.compare(condition(), E->condition()); 1839274958Sdim if (Cmp.notTrue(Ct)) 1840274958Sdim return Ct; 1841274958Sdim Ct = Cmp.compare(thenExpr(), E->thenExpr()); 1842274958Sdim if (Cmp.notTrue(Ct)) 1843274958Sdim return Ct; 1844274958Sdim return Cmp.compare(elseExpr(), E->elseExpr()); 1845274958Sdim } 1846274958Sdim 1847274958Sdimprivate: 1848280031Sdim SExpr* Condition; 1849280031Sdim SExpr* ThenExpr; 1850280031Sdim SExpr* ElseExpr; 1851274958Sdim}; 1852274958Sdim 1853280031Sdim/// A let-expression, e.g. let x=t; u. 1854280031Sdim/// This is a pseduo-term; it will be lowered to instructions in a CFG. 1855274958Sdimclass Let : public SExpr { 1856274958Sdimpublic: 1857274958Sdim Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { 1858274958Sdim Vd->setKind(Variable::VK_Let); 1859274958Sdim } 1860341825Sdim 1861274958Sdim Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { 1862274958Sdim Vd->setKind(Variable::VK_Let); 1863274958Sdim } 1864274958Sdim 1865341825Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } 1866341825Sdim 1867274958Sdim Variable *variableDecl() { return VarDecl; } 1868274958Sdim const Variable *variableDecl() const { return VarDecl; } 1869274958Sdim 1870280031Sdim SExpr *body() { return Body; } 1871280031Sdim const SExpr *body() const { return Body; } 1872274958Sdim 1873274958Sdim template <class V> 1874274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1875274958Sdim // This is a variable declaration, so traverse the definition. 1876274958Sdim auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); 1877274958Sdim // Tell the rewriter to enter the scope of the let variable. 1878274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, E0); 1879274958Sdim auto E1 = Vs.traverse(Body, Ctx); 1880274958Sdim Vs.exitScope(*VarDecl); 1881274958Sdim return Vs.reduceLet(*this, Nvd, E1); 1882274958Sdim } 1883274958Sdim 1884280031Sdim template <class C> 1885280031Sdim typename C::CType compare(const Let* E, C& Cmp) const { 1886274958Sdim typename C::CType Ct = 1887274958Sdim Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 1888274958Sdim if (Cmp.notTrue(Ct)) 1889274958Sdim return Ct; 1890274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 1891274958Sdim Ct = Cmp.compare(body(), E->body()); 1892274958Sdim Cmp.leaveScope(); 1893274958Sdim return Ct; 1894274958Sdim } 1895274958Sdim 1896274958Sdimprivate: 1897274958Sdim Variable *VarDecl; 1898280031Sdim SExpr* Body; 1899274958Sdim}; 1900274958Sdim 1901280031Sdimconst SExpr *getCanonicalVal(const SExpr *E); 1902280031SdimSExpr* simplifyToCanonicalVal(SExpr *E); 1903280031Sdimvoid simplifyIncompleteArg(til::Phi *Ph); 1904274958Sdim 1905341825Sdim} // namespace til 1906341825Sdim} // namespace threadSafety 1907274958Sdim 1908341825Sdim} // namespace clang 1909274958Sdim 1910341825Sdim#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 1911