ThreadSafetyTIL.h revision 327952
1274958Sdim//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// 2274958Sdim// 3274958Sdim// The LLVM Compiler Infrastructure 4274958Sdim// 5274958Sdim// This file is distributed under the University of Illinois Open Source 6274958Sdim// License. See LICENSE.TXT in the llvm repository for details. 7274958Sdim// 8274958Sdim//===----------------------------------------------------------------------===// 9274958Sdim// 10274958Sdim// This file defines a simple Typed Intermediate Language, or TIL, that is used 11274958Sdim// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended 12274958Sdim// to be largely independent of clang, in the hope that the analysis can be 13274958Sdim// reused for other non-C++ languages. All dependencies on clang/llvm should 14274958Sdim// go in ThreadSafetyUtil.h. 15274958Sdim// 16274958Sdim// Thread safety analysis works by comparing mutex expressions, e.g. 17274958Sdim// 18274958Sdim// class A { Mutex mu; int dat GUARDED_BY(this->mu); } 19274958Sdim// class B { A a; } 20274958Sdim// 21274958Sdim// void foo(B* b) { 22274958Sdim// (*b).a.mu.lock(); // locks (*b).a.mu 23274958Sdim// b->a.dat = 0; // substitute &b->a for 'this'; 24274958Sdim// // requires lock on (&b->a)->mu 25274958Sdim// (b->a.mu).unlock(); // unlocks (b->a.mu) 26274958Sdim// } 27274958Sdim// 28274958Sdim// As illustrated by the above example, clang Exprs are not well-suited to 29274958Sdim// represent mutex expressions directly, since there is no easy way to compare 30274958Sdim// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs 31274958Sdim// into a simple intermediate language (IL). The IL supports: 32274958Sdim// 33274958Sdim// (1) comparisons for semantic equality of expressions 34274958Sdim// (2) SSA renaming of variables 35274958Sdim// (3) wildcards and pattern matching over expressions 36274958Sdim// (4) hash-based expression lookup 37274958Sdim// 38274958Sdim// The TIL is currently very experimental, is intended only for use within 39274958Sdim// the thread safety analysis, and is subject to change without notice. 40274958Sdim// After the API stabilizes and matures, it may be appropriate to make this 41274958Sdim// more generally available to other analyses. 42274958Sdim// 43274958Sdim// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 44274958Sdim// 45274958Sdim//===----------------------------------------------------------------------===// 46274958Sdim 47280031Sdim#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 48280031Sdim#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 49274958Sdim 50274958Sdim// All clang include dependencies for this file must be put in 51274958Sdim// ThreadSafetyUtil.h. 52274958Sdim#include "ThreadSafetyUtil.h" 53274958Sdim#include <algorithm> 54274958Sdim#include <cassert> 55274958Sdim#include <cstddef> 56280031Sdim#include <stdint.h> 57274958Sdim#include <utility> 58274958Sdim 59274958Sdim 60274958Sdimnamespace clang { 61274958Sdimnamespace threadSafety { 62274958Sdimnamespace til { 63274958Sdim 64274958Sdim 65280031Sdim/// Enum for the different distinct classes of SExpr 66274958Sdimenum TIL_Opcode { 67274958Sdim#define TIL_OPCODE_DEF(X) COP_##X, 68274958Sdim#include "ThreadSafetyOps.def" 69274958Sdim#undef TIL_OPCODE_DEF 70274958Sdim}; 71274958Sdim 72280031Sdim/// Opcode for unary arithmetic operations. 73274958Sdimenum TIL_UnaryOpcode : unsigned char { 74274958Sdim UOP_Minus, // - 75274958Sdim UOP_BitNot, // ~ 76274958Sdim UOP_LogicNot // ! 77274958Sdim}; 78274958Sdim 79280031Sdim/// Opcode for binary arithmetic operations. 80274958Sdimenum TIL_BinaryOpcode : unsigned char { 81280031Sdim BOP_Add, // + 82280031Sdim BOP_Sub, // - 83274958Sdim BOP_Mul, // * 84274958Sdim BOP_Div, // / 85274958Sdim BOP_Rem, // % 86274958Sdim BOP_Shl, // << 87274958Sdim BOP_Shr, // >> 88274958Sdim BOP_BitAnd, // & 89274958Sdim BOP_BitXor, // ^ 90274958Sdim BOP_BitOr, // | 91274958Sdim BOP_Eq, // == 92274958Sdim BOP_Neq, // != 93274958Sdim BOP_Lt, // < 94274958Sdim BOP_Leq, // <= 95327952Sdim BOP_Cmp, // <=> 96280031Sdim BOP_LogicAnd, // && (no short-circuit) 97280031Sdim BOP_LogicOr // || (no short-circuit) 98274958Sdim}; 99274958Sdim 100280031Sdim/// Opcode for cast operations. 101274958Sdimenum TIL_CastOpcode : unsigned char { 102274958Sdim CAST_none = 0, 103274958Sdim CAST_extendNum, // extend precision of numeric type 104274958Sdim CAST_truncNum, // truncate precision of numeric type 105274958Sdim CAST_toFloat, // convert to floating point type 106274958Sdim CAST_toInt, // convert to integer type 107280031Sdim CAST_objToPtr // convert smart pointer to pointer (C++ only) 108274958Sdim}; 109274958Sdim 110274958Sdimconst TIL_Opcode COP_Min = COP_Future; 111274958Sdimconst TIL_Opcode COP_Max = COP_Branch; 112274958Sdimconst TIL_UnaryOpcode UOP_Min = UOP_Minus; 113274958Sdimconst TIL_UnaryOpcode UOP_Max = UOP_LogicNot; 114280031Sdimconst TIL_BinaryOpcode BOP_Min = BOP_Add; 115274958Sdimconst TIL_BinaryOpcode BOP_Max = BOP_LogicOr; 116274958Sdimconst TIL_CastOpcode CAST_Min = CAST_none; 117274958Sdimconst TIL_CastOpcode CAST_Max = CAST_toInt; 118274958Sdim 119280031Sdim/// Return the name of a unary opcode. 120274958SdimStringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); 121280031Sdim 122280031Sdim/// Return the name of a binary opcode. 123274958SdimStringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); 124274958Sdim 125274958Sdim 126280031Sdim/// ValueTypes are data types that can actually be held in registers. 127280031Sdim/// All variables and expressions must have a value type. 128280031Sdim/// Pointer types are further subdivided into the various heap-allocated 129280031Sdim/// types, such as functions, records, etc. 130280031Sdim/// Structured types that are passed by value (e.g. complex numbers) 131280031Sdim/// require special handling; they use BT_ValueRef, and size ST_0. 132274958Sdimstruct ValueType { 133274958Sdim enum BaseType : unsigned char { 134274958Sdim BT_Void = 0, 135274958Sdim BT_Bool, 136274958Sdim BT_Int, 137274958Sdim BT_Float, 138274958Sdim BT_String, // String literals 139274958Sdim BT_Pointer, 140274958Sdim BT_ValueRef 141274958Sdim }; 142274958Sdim 143274958Sdim enum SizeType : unsigned char { 144274958Sdim ST_0 = 0, 145274958Sdim ST_1, 146274958Sdim ST_8, 147274958Sdim ST_16, 148274958Sdim ST_32, 149274958Sdim ST_64, 150274958Sdim ST_128 151274958Sdim }; 152274958Sdim 153274958Sdim inline static SizeType getSizeType(unsigned nbytes); 154274958Sdim 155274958Sdim template <class T> 156274958Sdim inline static ValueType getValueType(); 157274958Sdim 158274958Sdim ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) 159274958Sdim : Base(B), Size(Sz), Signed(S), VectSize(VS) 160274958Sdim { } 161274958Sdim 162274958Sdim BaseType Base; 163274958Sdim SizeType Size; 164274958Sdim bool Signed; 165274958Sdim unsigned char VectSize; // 0 for scalar, otherwise num elements in vector 166274958Sdim}; 167274958Sdim 168274958Sdim 169274958Sdiminline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { 170274958Sdim switch (nbytes) { 171274958Sdim case 1: return ST_8; 172274958Sdim case 2: return ST_16; 173274958Sdim case 4: return ST_32; 174274958Sdim case 8: return ST_64; 175274958Sdim case 16: return ST_128; 176274958Sdim default: return ST_0; 177274958Sdim } 178274958Sdim} 179274958Sdim 180274958Sdim 181274958Sdimtemplate<> 182274958Sdiminline ValueType ValueType::getValueType<void>() { 183274958Sdim return ValueType(BT_Void, ST_0, false, 0); 184274958Sdim} 185274958Sdim 186274958Sdimtemplate<> 187274958Sdiminline ValueType ValueType::getValueType<bool>() { 188274958Sdim return ValueType(BT_Bool, ST_1, false, 0); 189274958Sdim} 190274958Sdim 191274958Sdimtemplate<> 192274958Sdiminline ValueType ValueType::getValueType<int8_t>() { 193274958Sdim return ValueType(BT_Int, ST_8, true, 0); 194274958Sdim} 195274958Sdim 196274958Sdimtemplate<> 197274958Sdiminline ValueType ValueType::getValueType<uint8_t>() { 198274958Sdim return ValueType(BT_Int, ST_8, false, 0); 199274958Sdim} 200274958Sdim 201274958Sdimtemplate<> 202274958Sdiminline ValueType ValueType::getValueType<int16_t>() { 203274958Sdim return ValueType(BT_Int, ST_16, true, 0); 204274958Sdim} 205274958Sdim 206274958Sdimtemplate<> 207274958Sdiminline ValueType ValueType::getValueType<uint16_t>() { 208274958Sdim return ValueType(BT_Int, ST_16, false, 0); 209274958Sdim} 210274958Sdim 211274958Sdimtemplate<> 212274958Sdiminline ValueType ValueType::getValueType<int32_t>() { 213274958Sdim return ValueType(BT_Int, ST_32, true, 0); 214274958Sdim} 215274958Sdim 216274958Sdimtemplate<> 217274958Sdiminline ValueType ValueType::getValueType<uint32_t>() { 218274958Sdim return ValueType(BT_Int, ST_32, false, 0); 219274958Sdim} 220274958Sdim 221274958Sdimtemplate<> 222274958Sdiminline ValueType ValueType::getValueType<int64_t>() { 223274958Sdim return ValueType(BT_Int, ST_64, true, 0); 224274958Sdim} 225274958Sdim 226274958Sdimtemplate<> 227274958Sdiminline ValueType ValueType::getValueType<uint64_t>() { 228274958Sdim return ValueType(BT_Int, ST_64, false, 0); 229274958Sdim} 230274958Sdim 231274958Sdimtemplate<> 232274958Sdiminline ValueType ValueType::getValueType<float>() { 233274958Sdim return ValueType(BT_Float, ST_32, true, 0); 234274958Sdim} 235274958Sdim 236274958Sdimtemplate<> 237274958Sdiminline ValueType ValueType::getValueType<double>() { 238274958Sdim return ValueType(BT_Float, ST_64, true, 0); 239274958Sdim} 240274958Sdim 241274958Sdimtemplate<> 242274958Sdiminline ValueType ValueType::getValueType<long double>() { 243274958Sdim return ValueType(BT_Float, ST_128, true, 0); 244274958Sdim} 245274958Sdim 246274958Sdimtemplate<> 247274958Sdiminline ValueType ValueType::getValueType<StringRef>() { 248274958Sdim return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); 249274958Sdim} 250274958Sdim 251274958Sdimtemplate<> 252274958Sdiminline ValueType ValueType::getValueType<void*>() { 253274958Sdim return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); 254274958Sdim} 255274958Sdim 256274958Sdim 257280031Sdimclass BasicBlock; 258274958Sdim 259280031Sdim 260280031Sdim/// Base class for AST nodes in the typed intermediate language. 261274958Sdimclass SExpr { 262274958Sdimpublic: 263274958Sdim TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } 264274958Sdim 265274958Sdim // Subclasses of SExpr must define the following: 266274958Sdim // 267274958Sdim // This(const This& E, ...) { 268274958Sdim // copy constructor: construct copy of E, with some additional arguments. 269274958Sdim // } 270274958Sdim // 271274958Sdim // template <class V> 272274958Sdim // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 273274958Sdim // traverse all subexpressions, following the traversal/rewriter interface. 274274958Sdim // } 275274958Sdim // 276274958Sdim // template <class C> typename C::CType compare(CType* E, C& Cmp) { 277274958Sdim // compare all subexpressions, following the comparator interface 278274958Sdim // } 279274958Sdim void *operator new(size_t S, MemRegionRef &R) { 280274958Sdim return ::operator new(S, R); 281274958Sdim } 282274958Sdim 283280031Sdim /// SExpr objects cannot be deleted. 284274958Sdim // This declaration is public to workaround a gcc bug that breaks building 285274958Sdim // with REQUIRES_EH=1. 286288943Sdim void operator delete(void *) = delete; 287274958Sdim 288280031Sdim /// Returns the instruction ID for this expression. 289280031Sdim /// All basic block instructions have a unique ID (i.e. virtual register). 290280031Sdim unsigned id() const { return SExprID; } 291280031Sdim 292280031Sdim /// Returns the block, if this is an instruction in a basic block, 293280031Sdim /// otherwise returns null. 294280031Sdim BasicBlock* block() const { return Block; } 295280031Sdim 296280031Sdim /// Set the basic block and instruction ID for this expression. 297280031Sdim void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } 298280031Sdim 299274958Sdimprotected: 300280031Sdim SExpr(TIL_Opcode Op) 301280031Sdim : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {} 302280031Sdim SExpr(const SExpr &E) 303280031Sdim : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0), 304280031Sdim Block(nullptr) {} 305274958Sdim 306274958Sdim const unsigned char Opcode; 307274958Sdim unsigned char Reserved; 308274958Sdim unsigned short Flags; 309280031Sdim unsigned SExprID; 310280031Sdim BasicBlock* Block; 311274958Sdim 312274958Sdimprivate: 313288943Sdim SExpr() = delete; 314274958Sdim 315280031Sdim /// SExpr objects must be created in an arena. 316288943Sdim void *operator new(size_t) = delete; 317274958Sdim}; 318274958Sdim 319274958Sdim 320274958Sdim// Contains various helper functions for SExprs. 321274958Sdimnamespace ThreadSafetyTIL { 322274958Sdim inline bool isTrivial(const SExpr *E) { 323274958Sdim unsigned Op = E->opcode(); 324274958Sdim return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; 325274958Sdim } 326274958Sdim} 327274958Sdim 328274958Sdim// Nodes which declare variables 329274958Sdimclass Function; 330274958Sdimclass SFunction; 331274958Sdimclass Let; 332274958Sdim 333274958Sdim 334280031Sdim/// A named variable, e.g. "x". 335280031Sdim/// 336280031Sdim/// There are two distinct places in which a Variable can appear in the AST. 337280031Sdim/// A variable declaration introduces a new variable, and can occur in 3 places: 338280031Sdim/// Let-expressions: (Let (x = t) u) 339280031Sdim/// Functions: (Function (x : t) u) 340280031Sdim/// Self-applicable functions (SFunction (x) t) 341280031Sdim/// 342280031Sdim/// If a variable occurs in any other location, it is a reference to an existing 343280031Sdim/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't 344280031Sdim/// allocate a separate AST node for variable references; a reference is just a 345280031Sdim/// pointer to the original declaration. 346274958Sdimclass Variable : public SExpr { 347274958Sdimpublic: 348274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } 349274958Sdim 350274958Sdim enum VariableKind { 351280031Sdim VK_Let, ///< Let-variable 352280031Sdim VK_Fun, ///< Function parameter 353280031Sdim VK_SFun ///< SFunction (self) parameter 354274958Sdim }; 355274958Sdim 356280031Sdim Variable(StringRef s, SExpr *D = nullptr) 357280031Sdim : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) { 358280031Sdim Flags = VK_Let; 359280031Sdim } 360280031Sdim Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr) 361280031Sdim : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), 362280031Sdim Definition(D), Cvdecl(Cvd) { 363280031Sdim Flags = VK_Let; 364280031Sdim } 365280031Sdim Variable(const Variable &Vd, SExpr *D) // rewrite constructor 366280031Sdim : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { 367280031Sdim Flags = Vd.kind(); 368280031Sdim } 369274958Sdim 370280031Sdim /// Return the kind of variable (let, function param, or self) 371274958Sdim VariableKind kind() const { return static_cast<VariableKind>(Flags); } 372274958Sdim 373280031Sdim /// Return the name of the variable, if any. 374280031Sdim StringRef name() const { return Name; } 375280031Sdim 376280031Sdim /// Return the clang declaration for this variable, if any. 377274958Sdim const clang::ValueDecl *clangDecl() const { return Cvdecl; } 378274958Sdim 379280031Sdim /// Return the definition of the variable. 380280031Sdim /// For let-vars, this is the setting expression. 381280031Sdim /// For function and self parameters, it is the type of the variable. 382280031Sdim SExpr *definition() { return Definition; } 383280031Sdim const SExpr *definition() const { return Definition; } 384274958Sdim 385280031Sdim void setName(StringRef S) { Name = S; } 386280031Sdim void setKind(VariableKind K) { Flags = K; } 387280031Sdim void setDefinition(SExpr *E) { Definition = E; } 388274958Sdim void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } 389274958Sdim 390274958Sdim template <class V> 391274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 392274958Sdim // This routine is only called for variable references. 393274958Sdim return Vs.reduceVariableRef(this); 394274958Sdim } 395274958Sdim 396280031Sdim template <class C> 397280031Sdim typename C::CType compare(const Variable* E, C& Cmp) const { 398274958Sdim return Cmp.compareVariableRefs(this, E); 399274958Sdim } 400274958Sdim 401274958Sdimprivate: 402274958Sdim friend class Function; 403274958Sdim friend class SFunction; 404274958Sdim friend class BasicBlock; 405274958Sdim friend class Let; 406274958Sdim 407274958Sdim StringRef Name; // The name of the variable. 408280031Sdim SExpr* Definition; // The TIL type or definition 409274958Sdim const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. 410274958Sdim}; 411274958Sdim 412274958Sdim 413280031Sdim/// Placeholder for an expression that has not yet been created. 414280031Sdim/// Used to implement lazy copy and rewriting strategies. 415274958Sdimclass Future : public SExpr { 416274958Sdimpublic: 417274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } 418274958Sdim 419274958Sdim enum FutureStatus { 420274958Sdim FS_pending, 421274958Sdim FS_evaluating, 422274958Sdim FS_done 423274958Sdim }; 424274958Sdim 425280031Sdim Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {} 426280031Sdim 427274958Sdimprivate: 428288943Sdim virtual ~Future() = delete; 429280031Sdim 430274958Sdimpublic: 431274958Sdim // A lazy rewriting strategy should subclass Future and override this method. 432280031Sdim virtual SExpr *compute() { return nullptr; } 433274958Sdim 434274958Sdim // Return the result of this future if it exists, otherwise return null. 435280031Sdim SExpr *maybeGetResult() const { 436274958Sdim return Result; 437274958Sdim } 438274958Sdim 439274958Sdim // Return the result of this future; forcing it if necessary. 440274958Sdim SExpr *result() { 441274958Sdim switch (Status) { 442274958Sdim case FS_pending: 443280031Sdim return force(); 444274958Sdim case FS_evaluating: 445274958Sdim return nullptr; // infinite loop; illegal recursion. 446274958Sdim case FS_done: 447274958Sdim return Result; 448274958Sdim } 449274958Sdim } 450274958Sdim 451274958Sdim template <class V> 452274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 453274958Sdim assert(Result && "Cannot traverse Future that has not been forced."); 454274958Sdim return Vs.traverse(Result, Ctx); 455274958Sdim } 456274958Sdim 457280031Sdim template <class C> 458280031Sdim typename C::CType compare(const Future* E, C& Cmp) const { 459274958Sdim if (!Result || !E->Result) 460274958Sdim return Cmp.comparePointers(this, E); 461274958Sdim return Cmp.compare(Result, E->Result); 462274958Sdim } 463274958Sdim 464274958Sdimprivate: 465280031Sdim SExpr* force(); 466274958Sdim 467274958Sdim FutureStatus Status; 468274958Sdim SExpr *Result; 469274958Sdim}; 470274958Sdim 471274958Sdim 472280031Sdim/// Placeholder for expressions that cannot be represented in the TIL. 473274958Sdimclass Undefined : public SExpr { 474274958Sdimpublic: 475274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 476274958Sdim 477274958Sdim Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} 478274958Sdim Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} 479274958Sdim 480274958Sdim template <class V> 481274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 482274958Sdim return Vs.reduceUndefined(*this); 483274958Sdim } 484274958Sdim 485280031Sdim template <class C> 486280031Sdim typename C::CType compare(const Undefined* E, C& Cmp) const { 487280031Sdim return Cmp.trueResult(); 488274958Sdim } 489274958Sdim 490274958Sdimprivate: 491274958Sdim const clang::Stmt *Cstmt; 492274958Sdim}; 493274958Sdim 494274958Sdim 495280031Sdim/// Placeholder for a wildcard that matches any other expression. 496274958Sdimclass Wildcard : public SExpr { 497274958Sdimpublic: 498274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 499274958Sdim 500274958Sdim Wildcard() : SExpr(COP_Wildcard) {} 501274958Sdim Wildcard(const Wildcard &W) : SExpr(W) {} 502274958Sdim 503274958Sdim template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 504274958Sdim return Vs.reduceWildcard(*this); 505274958Sdim } 506274958Sdim 507280031Sdim template <class C> 508280031Sdim typename C::CType compare(const Wildcard* E, C& Cmp) const { 509274958Sdim return Cmp.trueResult(); 510274958Sdim } 511274958Sdim}; 512274958Sdim 513274958Sdim 514274958Sdimtemplate <class T> class LiteralT; 515274958Sdim 516274958Sdim// Base class for literal values. 517274958Sdimclass Literal : public SExpr { 518274958Sdimpublic: 519274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 520274958Sdim 521274958Sdim Literal(const clang::Expr *C) 522274958Sdim : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) 523274958Sdim { } 524274958Sdim Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {} 525274958Sdim Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {} 526274958Sdim 527274958Sdim // The clang expression for this literal. 528274958Sdim const clang::Expr *clangExpr() const { return Cexpr; } 529274958Sdim 530274958Sdim ValueType valueType() const { return ValType; } 531274958Sdim 532274958Sdim template<class T> const LiteralT<T>& as() const { 533274958Sdim return *static_cast<const LiteralT<T>*>(this); 534274958Sdim } 535274958Sdim template<class T> LiteralT<T>& as() { 536274958Sdim return *static_cast<LiteralT<T>*>(this); 537274958Sdim } 538274958Sdim 539274958Sdim template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 540274958Sdim 541280031Sdim template <class C> 542280031Sdim typename C::CType compare(const Literal* E, C& Cmp) const { 543280031Sdim // TODO: defer actual comparison to LiteralT 544280031Sdim return Cmp.trueResult(); 545274958Sdim } 546274958Sdim 547274958Sdimprivate: 548274958Sdim const ValueType ValType; 549274958Sdim const clang::Expr *Cexpr; 550274958Sdim}; 551274958Sdim 552274958Sdim 553274958Sdim// Derived class for literal values, which stores the actual value. 554274958Sdimtemplate<class T> 555274958Sdimclass LiteralT : public Literal { 556274958Sdimpublic: 557274958Sdim LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { } 558274958Sdim LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { } 559274958Sdim 560274958Sdim T value() const { return Val;} 561274958Sdim T& value() { return Val; } 562274958Sdim 563274958Sdimprivate: 564274958Sdim T Val; 565274958Sdim}; 566274958Sdim 567274958Sdim 568274958Sdim 569274958Sdimtemplate <class V> 570274958Sdimtypename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 571274958Sdim if (Cexpr) 572274958Sdim return Vs.reduceLiteral(*this); 573274958Sdim 574274958Sdim switch (ValType.Base) { 575274958Sdim case ValueType::BT_Void: 576274958Sdim break; 577274958Sdim case ValueType::BT_Bool: 578274958Sdim return Vs.reduceLiteralT(as<bool>()); 579274958Sdim case ValueType::BT_Int: { 580274958Sdim switch (ValType.Size) { 581274958Sdim case ValueType::ST_8: 582274958Sdim if (ValType.Signed) 583274958Sdim return Vs.reduceLiteralT(as<int8_t>()); 584274958Sdim else 585274958Sdim return Vs.reduceLiteralT(as<uint8_t>()); 586274958Sdim case ValueType::ST_16: 587274958Sdim if (ValType.Signed) 588274958Sdim return Vs.reduceLiteralT(as<int16_t>()); 589274958Sdim else 590274958Sdim return Vs.reduceLiteralT(as<uint16_t>()); 591274958Sdim case ValueType::ST_32: 592274958Sdim if (ValType.Signed) 593274958Sdim return Vs.reduceLiteralT(as<int32_t>()); 594274958Sdim else 595274958Sdim return Vs.reduceLiteralT(as<uint32_t>()); 596274958Sdim case ValueType::ST_64: 597274958Sdim if (ValType.Signed) 598274958Sdim return Vs.reduceLiteralT(as<int64_t>()); 599274958Sdim else 600274958Sdim return Vs.reduceLiteralT(as<uint64_t>()); 601274958Sdim default: 602274958Sdim break; 603274958Sdim } 604274958Sdim } 605274958Sdim case ValueType::BT_Float: { 606274958Sdim switch (ValType.Size) { 607274958Sdim case ValueType::ST_32: 608274958Sdim return Vs.reduceLiteralT(as<float>()); 609274958Sdim case ValueType::ST_64: 610274958Sdim return Vs.reduceLiteralT(as<double>()); 611274958Sdim default: 612274958Sdim break; 613274958Sdim } 614274958Sdim } 615274958Sdim case ValueType::BT_String: 616274958Sdim return Vs.reduceLiteralT(as<StringRef>()); 617274958Sdim case ValueType::BT_Pointer: 618274958Sdim return Vs.reduceLiteralT(as<void*>()); 619274958Sdim case ValueType::BT_ValueRef: 620274958Sdim break; 621274958Sdim } 622274958Sdim return Vs.reduceLiteral(*this); 623274958Sdim} 624274958Sdim 625274958Sdim 626280031Sdim/// A Literal pointer to an object allocated in memory. 627280031Sdim/// At compile time, pointer literals are represented by symbolic names. 628274958Sdimclass LiteralPtr : public SExpr { 629274958Sdimpublic: 630274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 631274958Sdim 632274958Sdim LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 633274958Sdim LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} 634274958Sdim 635274958Sdim // The clang declaration for the value that this pointer points to. 636274958Sdim const clang::ValueDecl *clangDecl() const { return Cvdecl; } 637274958Sdim 638274958Sdim template <class V> 639274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 640274958Sdim return Vs.reduceLiteralPtr(*this); 641274958Sdim } 642274958Sdim 643280031Sdim template <class C> 644280031Sdim typename C::CType compare(const LiteralPtr* E, C& Cmp) const { 645274958Sdim return Cmp.comparePointers(Cvdecl, E->Cvdecl); 646274958Sdim } 647274958Sdim 648274958Sdimprivate: 649274958Sdim const clang::ValueDecl *Cvdecl; 650274958Sdim}; 651274958Sdim 652274958Sdim 653280031Sdim/// A function -- a.k.a. lambda abstraction. 654280031Sdim/// Functions with multiple arguments are created by currying, 655280031Sdim/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) 656274958Sdimclass Function : public SExpr { 657274958Sdimpublic: 658274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 659274958Sdim 660274958Sdim Function(Variable *Vd, SExpr *Bd) 661274958Sdim : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 662274958Sdim Vd->setKind(Variable::VK_Fun); 663274958Sdim } 664274958Sdim Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 665274958Sdim : SExpr(F), VarDecl(Vd), Body(Bd) { 666274958Sdim Vd->setKind(Variable::VK_Fun); 667274958Sdim } 668274958Sdim 669274958Sdim Variable *variableDecl() { return VarDecl; } 670274958Sdim const Variable *variableDecl() const { return VarDecl; } 671274958Sdim 672280031Sdim SExpr *body() { return Body; } 673280031Sdim const SExpr *body() const { return Body; } 674274958Sdim 675274958Sdim template <class V> 676274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 677274958Sdim // This is a variable declaration, so traverse the definition. 678274958Sdim auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 679274958Sdim // Tell the rewriter to enter the scope of the function. 680274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, E0); 681274958Sdim auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 682274958Sdim Vs.exitScope(*VarDecl); 683274958Sdim return Vs.reduceFunction(*this, Nvd, E1); 684274958Sdim } 685274958Sdim 686280031Sdim template <class C> 687280031Sdim typename C::CType compare(const Function* E, C& Cmp) const { 688274958Sdim typename C::CType Ct = 689274958Sdim Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 690274958Sdim if (Cmp.notTrue(Ct)) 691274958Sdim return Ct; 692274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 693274958Sdim Ct = Cmp.compare(body(), E->body()); 694274958Sdim Cmp.leaveScope(); 695274958Sdim return Ct; 696274958Sdim } 697274958Sdim 698274958Sdimprivate: 699274958Sdim Variable *VarDecl; 700280031Sdim SExpr* Body; 701274958Sdim}; 702274958Sdim 703274958Sdim 704280031Sdim/// A self-applicable function. 705280031Sdim/// A self-applicable function can be applied to itself. It's useful for 706280031Sdim/// implementing objects and late binding. 707274958Sdimclass SFunction : public SExpr { 708274958Sdimpublic: 709274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 710274958Sdim 711274958Sdim SFunction(Variable *Vd, SExpr *B) 712274958Sdim : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 713274958Sdim assert(Vd->Definition == nullptr); 714274958Sdim Vd->setKind(Variable::VK_SFun); 715280031Sdim Vd->Definition = this; 716274958Sdim } 717274958Sdim SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 718274958Sdim : SExpr(F), VarDecl(Vd), Body(B) { 719274958Sdim assert(Vd->Definition == nullptr); 720274958Sdim Vd->setKind(Variable::VK_SFun); 721280031Sdim Vd->Definition = this; 722274958Sdim } 723274958Sdim 724274958Sdim Variable *variableDecl() { return VarDecl; } 725274958Sdim const Variable *variableDecl() const { return VarDecl; } 726274958Sdim 727280031Sdim SExpr *body() { return Body; } 728280031Sdim const SExpr *body() const { return Body; } 729274958Sdim 730274958Sdim template <class V> 731274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 732274958Sdim // A self-variable points to the SFunction itself. 733274958Sdim // A rewrite must introduce the variable with a null definition, and update 734274958Sdim // it after 'this' has been rewritten. 735274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 736274958Sdim auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 737274958Sdim Vs.exitScope(*VarDecl); 738274958Sdim // A rewrite operation will call SFun constructor to set Vvd->Definition. 739274958Sdim return Vs.reduceSFunction(*this, Nvd, E1); 740274958Sdim } 741274958Sdim 742280031Sdim template <class C> 743280031Sdim typename C::CType compare(const SFunction* E, C& Cmp) const { 744274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 745274958Sdim typename C::CType Ct = Cmp.compare(body(), E->body()); 746274958Sdim Cmp.leaveScope(); 747274958Sdim return Ct; 748274958Sdim } 749274958Sdim 750274958Sdimprivate: 751274958Sdim Variable *VarDecl; 752280031Sdim SExpr* Body; 753274958Sdim}; 754274958Sdim 755274958Sdim 756280031Sdim/// A block of code -- e.g. the body of a function. 757274958Sdimclass Code : public SExpr { 758274958Sdimpublic: 759274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 760274958Sdim 761274958Sdim Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 762274958Sdim Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 763274958Sdim : SExpr(C), ReturnType(T), Body(B) {} 764274958Sdim 765280031Sdim SExpr *returnType() { return ReturnType; } 766280031Sdim const SExpr *returnType() const { return ReturnType; } 767274958Sdim 768280031Sdim SExpr *body() { return Body; } 769280031Sdim const SExpr *body() const { return Body; } 770274958Sdim 771274958Sdim template <class V> 772274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 773274958Sdim auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 774274958Sdim auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 775274958Sdim return Vs.reduceCode(*this, Nt, Nb); 776274958Sdim } 777274958Sdim 778280031Sdim template <class C> 779280031Sdim typename C::CType compare(const Code* E, C& Cmp) const { 780274958Sdim typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 781274958Sdim if (Cmp.notTrue(Ct)) 782274958Sdim return Ct; 783274958Sdim return Cmp.compare(body(), E->body()); 784274958Sdim } 785274958Sdim 786274958Sdimprivate: 787280031Sdim SExpr* ReturnType; 788280031Sdim SExpr* Body; 789274958Sdim}; 790274958Sdim 791274958Sdim 792280031Sdim/// A typed, writable location in memory 793274958Sdimclass Field : public SExpr { 794274958Sdimpublic: 795274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 796274958Sdim 797274958Sdim Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 798274958Sdim Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 799274958Sdim : SExpr(C), Range(R), Body(B) {} 800274958Sdim 801280031Sdim SExpr *range() { return Range; } 802280031Sdim const SExpr *range() const { return Range; } 803274958Sdim 804280031Sdim SExpr *body() { return Body; } 805280031Sdim const SExpr *body() const { return Body; } 806274958Sdim 807274958Sdim template <class V> 808274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 809274958Sdim auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 810274958Sdim auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 811274958Sdim return Vs.reduceField(*this, Nr, Nb); 812274958Sdim } 813274958Sdim 814280031Sdim template <class C> 815280031Sdim typename C::CType compare(const Field* E, C& Cmp) const { 816274958Sdim typename C::CType Ct = Cmp.compare(range(), E->range()); 817274958Sdim if (Cmp.notTrue(Ct)) 818274958Sdim return Ct; 819274958Sdim return Cmp.compare(body(), E->body()); 820274958Sdim } 821274958Sdim 822274958Sdimprivate: 823280031Sdim SExpr* Range; 824280031Sdim SExpr* Body; 825274958Sdim}; 826274958Sdim 827274958Sdim 828280031Sdim/// Apply an argument to a function. 829280031Sdim/// Note that this does not actually call the function. Functions are curried, 830280031Sdim/// so this returns a closure in which the first parameter has been applied. 831280031Sdim/// Once all parameters have been applied, Call can be used to invoke the 832280031Sdim/// function. 833274958Sdimclass Apply : public SExpr { 834274958Sdimpublic: 835274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 836274958Sdim 837274958Sdim Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 838274958Sdim Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 839274958Sdim : SExpr(A), Fun(F), Arg(Ar) 840274958Sdim {} 841274958Sdim 842280031Sdim SExpr *fun() { return Fun; } 843280031Sdim const SExpr *fun() const { return Fun; } 844274958Sdim 845280031Sdim SExpr *arg() { return Arg; } 846280031Sdim const SExpr *arg() const { return Arg; } 847274958Sdim 848274958Sdim template <class V> 849274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 850274958Sdim auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 851274958Sdim auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 852274958Sdim return Vs.reduceApply(*this, Nf, Na); 853274958Sdim } 854274958Sdim 855280031Sdim template <class C> 856280031Sdim typename C::CType compare(const Apply* E, C& Cmp) const { 857274958Sdim typename C::CType Ct = Cmp.compare(fun(), E->fun()); 858274958Sdim if (Cmp.notTrue(Ct)) 859274958Sdim return Ct; 860274958Sdim return Cmp.compare(arg(), E->arg()); 861274958Sdim } 862274958Sdim 863274958Sdimprivate: 864280031Sdim SExpr* Fun; 865280031Sdim SExpr* Arg; 866274958Sdim}; 867274958Sdim 868274958Sdim 869280031Sdim/// Apply a self-argument to a self-applicable function. 870274958Sdimclass SApply : public SExpr { 871274958Sdimpublic: 872274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 873274958Sdim 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 878280031Sdim SExpr *sfun() { return Sfun; } 879280031Sdim const SExpr *sfun() const { return Sfun; } 880274958Sdim 881280031Sdim SExpr *arg() { return Arg ? Arg : Sfun; } 882280031Sdim const SExpr *arg() const { return Arg ? Arg : Sfun; } 883274958Sdim 884280031Sdim bool isDelegation() const { return Arg != nullptr; } 885274958Sdim 886274958Sdim template <class V> 887274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 888274958Sdim auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 889280031Sdim typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 890274958Sdim : nullptr; 891274958Sdim return Vs.reduceSApply(*this, Nf, Na); 892274958Sdim } 893274958Sdim 894280031Sdim template <class C> 895280031Sdim typename C::CType compare(const SApply* E, C& Cmp) const { 896274958Sdim typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 897274958Sdim if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 898274958Sdim return Ct; 899274958Sdim return Cmp.compare(arg(), E->arg()); 900274958Sdim } 901274958Sdim 902274958Sdimprivate: 903280031Sdim SExpr* Sfun; 904280031Sdim SExpr* Arg; 905274958Sdim}; 906274958Sdim 907274958Sdim 908280031Sdim/// Project a named slot from a C++ struct or class. 909274958Sdimclass Project : public SExpr { 910274958Sdimpublic: 911274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 912274958Sdim 913280031Sdim Project(SExpr *R, const clang::ValueDecl *Cvd) 914327952Sdim : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { 915327952Sdim assert(Cvd && "ValueDecl must not be null"); 916327952Sdim } 917274958Sdim 918280031Sdim SExpr *record() { return Rec; } 919280031Sdim const SExpr *record() const { return Rec; } 920274958Sdim 921280031Sdim const clang::ValueDecl *clangDecl() const { return Cvdecl; } 922274958Sdim 923280031Sdim bool isArrow() const { return (Flags & 0x01) != 0; } 924280031Sdim void setArrow(bool b) { 925280031Sdim if (b) Flags |= 0x01; 926280031Sdim else Flags &= 0xFFFE; 927280031Sdim } 928280031Sdim 929274958Sdim StringRef slotName() const { 930327952Sdim if (Cvdecl->getDeclName().isIdentifier()) 931274958Sdim return Cvdecl->getName(); 932327952Sdim if (!SlotName) { 933327952Sdim SlotName = ""; 934327952Sdim llvm::raw_string_ostream OS(*SlotName); 935327952Sdim Cvdecl->printName(OS); 936327952Sdim } 937327952Sdim return *SlotName; 938274958Sdim } 939274958Sdim 940274958Sdim template <class V> 941274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 942274958Sdim auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 943274958Sdim return Vs.reduceProject(*this, Nr); 944274958Sdim } 945274958Sdim 946280031Sdim template <class C> 947280031Sdim typename C::CType compare(const Project* E, C& Cmp) const { 948274958Sdim typename C::CType Ct = Cmp.compare(record(), E->record()); 949274958Sdim if (Cmp.notTrue(Ct)) 950274958Sdim return Ct; 951274958Sdim return Cmp.comparePointers(Cvdecl, E->Cvdecl); 952274958Sdim } 953274958Sdim 954274958Sdimprivate: 955280031Sdim SExpr* Rec; 956327952Sdim mutable llvm::Optional<std::string> SlotName; 957280031Sdim const clang::ValueDecl *Cvdecl; 958274958Sdim}; 959274958Sdim 960274958Sdim 961280031Sdim/// Call a function (after all arguments have been applied). 962274958Sdimclass Call : public SExpr { 963274958Sdimpublic: 964274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 965274958Sdim 966274958Sdim Call(SExpr *T, const clang::CallExpr *Ce = nullptr) 967274958Sdim : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 968274958Sdim Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 969274958Sdim 970280031Sdim SExpr *target() { return Target; } 971280031Sdim const SExpr *target() const { return Target; } 972274958Sdim 973274958Sdim const clang::CallExpr *clangCallExpr() const { return Cexpr; } 974274958Sdim 975274958Sdim template <class V> 976274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 977274958Sdim auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 978274958Sdim return Vs.reduceCall(*this, Nt); 979274958Sdim } 980274958Sdim 981280031Sdim template <class C> 982280031Sdim typename C::CType compare(const Call* E, C& Cmp) const { 983274958Sdim return Cmp.compare(target(), E->target()); 984274958Sdim } 985274958Sdim 986274958Sdimprivate: 987280031Sdim SExpr* Target; 988274958Sdim const clang::CallExpr *Cexpr; 989274958Sdim}; 990274958Sdim 991274958Sdim 992280031Sdim/// Allocate memory for a new value on the heap or stack. 993274958Sdimclass Alloc : public SExpr { 994274958Sdimpublic: 995274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 996274958Sdim 997274958Sdim enum AllocKind { 998274958Sdim AK_Stack, 999274958Sdim AK_Heap 1000274958Sdim }; 1001274958Sdim 1002274958Sdim Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 1003274958Sdim Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 1004274958Sdim 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 1028274958Sdim 1029280031Sdim/// Load a value from memory. 1030274958Sdimclass Load : public SExpr { 1031274958Sdimpublic: 1032274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 1033274958Sdim 1034274958Sdim Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 1035274958Sdim Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 1036274958Sdim 1037280031Sdim SExpr *pointer() { return Ptr; } 1038280031Sdim const SExpr *pointer() const { return Ptr; } 1039274958Sdim 1040274958Sdim template <class V> 1041274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1042274958Sdim auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1043274958Sdim return Vs.reduceLoad(*this, Np); 1044274958Sdim } 1045274958Sdim 1046280031Sdim template <class C> 1047280031Sdim typename C::CType compare(const Load* E, C& Cmp) const { 1048274958Sdim return Cmp.compare(pointer(), E->pointer()); 1049274958Sdim } 1050274958Sdim 1051274958Sdimprivate: 1052280031Sdim SExpr* Ptr; 1053274958Sdim}; 1054274958Sdim 1055274958Sdim 1056280031Sdim/// Store a value to memory. 1057280031Sdim/// The destination is a pointer to a field, the source is the value to store. 1058274958Sdimclass Store : public SExpr { 1059274958Sdimpublic: 1060274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 1061274958Sdim 1062274958Sdim Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 1063274958Sdim Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 1064274958Sdim 1065280031Sdim SExpr *destination() { return Dest; } // Address to store to 1066280031Sdim const SExpr *destination() const { return Dest; } 1067274958Sdim 1068280031Sdim SExpr *source() { return Source; } // Value to store 1069280031Sdim const SExpr *source() const { return Source; } 1070274958Sdim 1071274958Sdim template <class V> 1072274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1073274958Sdim auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1074274958Sdim auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1075274958Sdim return Vs.reduceStore(*this, Np, Nv); 1076274958Sdim } 1077274958Sdim 1078280031Sdim template <class C> 1079280031Sdim typename C::CType compare(const Store* E, C& Cmp) const { 1080274958Sdim typename C::CType Ct = Cmp.compare(destination(), E->destination()); 1081274958Sdim if (Cmp.notTrue(Ct)) 1082274958Sdim return Ct; 1083274958Sdim return Cmp.compare(source(), E->source()); 1084274958Sdim } 1085274958Sdim 1086274958Sdimprivate: 1087280031Sdim SExpr* Dest; 1088280031Sdim SExpr* Source; 1089274958Sdim}; 1090274958Sdim 1091274958Sdim 1092280031Sdim/// If p is a reference to an array, then p[i] is a reference to the i'th 1093280031Sdim/// element of the array. 1094274958Sdimclass ArrayIndex : public SExpr { 1095274958Sdimpublic: 1096274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 1097274958Sdim 1098274958Sdim ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1099274958Sdim ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1100274958Sdim : SExpr(E), Array(A), Index(N) {} 1101274958Sdim 1102280031Sdim SExpr *array() { return Array; } 1103280031Sdim const SExpr *array() const { return Array; } 1104274958Sdim 1105280031Sdim SExpr *index() { return Index; } 1106280031Sdim const SExpr *index() const { return Index; } 1107274958Sdim 1108274958Sdim template <class V> 1109274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1110274958Sdim auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1111274958Sdim auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1112274958Sdim return Vs.reduceArrayIndex(*this, Na, Ni); 1113274958Sdim } 1114274958Sdim 1115280031Sdim template <class C> 1116280031Sdim typename C::CType compare(const ArrayIndex* E, C& Cmp) const { 1117274958Sdim typename C::CType Ct = Cmp.compare(array(), E->array()); 1118274958Sdim if (Cmp.notTrue(Ct)) 1119274958Sdim return Ct; 1120274958Sdim return Cmp.compare(index(), E->index()); 1121274958Sdim } 1122274958Sdim 1123274958Sdimprivate: 1124280031Sdim SExpr* Array; 1125280031Sdim SExpr* Index; 1126274958Sdim}; 1127274958Sdim 1128274958Sdim 1129280031Sdim/// Pointer arithmetic, restricted to arrays only. 1130280031Sdim/// If p is a reference to an array, then p + n, where n is an integer, is 1131280031Sdim/// a reference to a subarray. 1132274958Sdimclass ArrayAdd : public SExpr { 1133274958Sdimpublic: 1134274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 1135274958Sdim 1136274958Sdim ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 1137274958Sdim ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 1138274958Sdim : SExpr(E), Array(A), Index(N) {} 1139274958Sdim 1140280031Sdim SExpr *array() { return Array; } 1141280031Sdim const SExpr *array() const { return Array; } 1142274958Sdim 1143280031Sdim SExpr *index() { return Index; } 1144280031Sdim const SExpr *index() const { return Index; } 1145274958Sdim 1146274958Sdim template <class V> 1147274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1148274958Sdim auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1149274958Sdim auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1150274958Sdim return Vs.reduceArrayAdd(*this, Na, Ni); 1151274958Sdim } 1152274958Sdim 1153280031Sdim template <class C> 1154280031Sdim typename C::CType compare(const ArrayAdd* E, C& Cmp) const { 1155274958Sdim typename C::CType Ct = Cmp.compare(array(), E->array()); 1156274958Sdim if (Cmp.notTrue(Ct)) 1157274958Sdim return Ct; 1158274958Sdim return Cmp.compare(index(), E->index()); 1159274958Sdim } 1160274958Sdim 1161274958Sdimprivate: 1162280031Sdim SExpr* Array; 1163280031Sdim SExpr* Index; 1164274958Sdim}; 1165274958Sdim 1166274958Sdim 1167280031Sdim/// Simple arithmetic unary operations, e.g. negate and not. 1168280031Sdim/// These operations have no side-effects. 1169274958Sdimclass UnaryOp : public SExpr { 1170274958Sdimpublic: 1171274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 1172274958Sdim 1173274958Sdim UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 1174274958Sdim Flags = Op; 1175274958Sdim } 1176274958Sdim UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 1177274958Sdim 1178274958Sdim TIL_UnaryOpcode unaryOpcode() const { 1179274958Sdim return static_cast<TIL_UnaryOpcode>(Flags); 1180274958Sdim } 1181274958Sdim 1182280031Sdim SExpr *expr() { return Expr0; } 1183280031Sdim const SExpr *expr() const { return Expr0; } 1184274958Sdim 1185274958Sdim template <class V> 1186274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1187274958Sdim auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1188274958Sdim return Vs.reduceUnaryOp(*this, Ne); 1189274958Sdim } 1190274958Sdim 1191280031Sdim template <class C> 1192280031Sdim typename C::CType compare(const UnaryOp* E, C& Cmp) const { 1193274958Sdim typename C::CType Ct = 1194274958Sdim Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 1195274958Sdim if (Cmp.notTrue(Ct)) 1196274958Sdim return Ct; 1197274958Sdim return Cmp.compare(expr(), E->expr()); 1198274958Sdim } 1199274958Sdim 1200274958Sdimprivate: 1201280031Sdim SExpr* Expr0; 1202274958Sdim}; 1203274958Sdim 1204274958Sdim 1205280031Sdim/// Simple arithmetic binary operations, e.g. +, -, etc. 1206280031Sdim/// These operations have no side effects. 1207274958Sdimclass BinaryOp : public SExpr { 1208274958Sdimpublic: 1209274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 1210274958Sdim 1211274958Sdim BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 1212274958Sdim : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 1213274958Sdim Flags = Op; 1214274958Sdim } 1215274958Sdim BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 1216274958Sdim : SExpr(B), Expr0(E0), Expr1(E1) { 1217274958Sdim Flags = B.Flags; 1218274958Sdim } 1219274958Sdim 1220274958Sdim TIL_BinaryOpcode binaryOpcode() const { 1221274958Sdim return static_cast<TIL_BinaryOpcode>(Flags); 1222274958Sdim } 1223274958Sdim 1224280031Sdim SExpr *expr0() { return Expr0; } 1225280031Sdim const SExpr *expr0() const { return Expr0; } 1226274958Sdim 1227280031Sdim SExpr *expr1() { return Expr1; } 1228280031Sdim const SExpr *expr1() const { return Expr1; } 1229274958Sdim 1230274958Sdim template <class V> 1231274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1232274958Sdim auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1233274958Sdim auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1234274958Sdim return Vs.reduceBinaryOp(*this, Ne0, Ne1); 1235274958Sdim } 1236274958Sdim 1237280031Sdim template <class C> 1238280031Sdim typename C::CType compare(const BinaryOp* E, C& Cmp) const { 1239274958Sdim typename C::CType Ct = 1240274958Sdim Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 1241274958Sdim if (Cmp.notTrue(Ct)) 1242274958Sdim return Ct; 1243274958Sdim Ct = Cmp.compare(expr0(), E->expr0()); 1244274958Sdim if (Cmp.notTrue(Ct)) 1245274958Sdim return Ct; 1246274958Sdim return Cmp.compare(expr1(), E->expr1()); 1247274958Sdim } 1248274958Sdim 1249274958Sdimprivate: 1250280031Sdim SExpr* Expr0; 1251280031Sdim SExpr* Expr1; 1252274958Sdim}; 1253274958Sdim 1254274958Sdim 1255280031Sdim/// Cast expressions. 1256280031Sdim/// Cast expressions are essentially unary operations, but we treat them 1257280031Sdim/// as a distinct AST node because they only change the type of the result. 1258274958Sdimclass Cast : public SExpr { 1259274958Sdimpublic: 1260274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 1261274958Sdim 1262274958Sdim Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 1263274958Sdim Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 1264274958Sdim 1265274958Sdim TIL_CastOpcode castOpcode() const { 1266274958Sdim return static_cast<TIL_CastOpcode>(Flags); 1267274958Sdim } 1268274958Sdim 1269280031Sdim SExpr *expr() { return Expr0; } 1270280031Sdim const SExpr *expr() const { return Expr0; } 1271274958Sdim 1272274958Sdim template <class V> 1273274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1274274958Sdim auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1275274958Sdim return Vs.reduceCast(*this, Ne); 1276274958Sdim } 1277274958Sdim 1278280031Sdim template <class C> 1279280031Sdim typename C::CType compare(const Cast* E, C& Cmp) const { 1280274958Sdim typename C::CType Ct = 1281274958Sdim Cmp.compareIntegers(castOpcode(), E->castOpcode()); 1282274958Sdim if (Cmp.notTrue(Ct)) 1283274958Sdim return Ct; 1284274958Sdim return Cmp.compare(expr(), E->expr()); 1285274958Sdim } 1286274958Sdim 1287274958Sdimprivate: 1288280031Sdim SExpr* Expr0; 1289274958Sdim}; 1290274958Sdim 1291274958Sdim 1292274958Sdimclass SCFG; 1293274958Sdim 1294274958Sdim 1295280031Sdim/// Phi Node, for code in SSA form. 1296280031Sdim/// Each Phi node has an array of possible values that it can take, 1297280031Sdim/// depending on where control flow comes from. 1298274958Sdimclass Phi : public SExpr { 1299274958Sdimpublic: 1300274958Sdim typedef SimpleArray<SExpr *> ValArray; 1301274958Sdim 1302274958Sdim // In minimal SSA form, all Phi nodes are MultiVal. 1303274958Sdim // During conversion to SSA, incomplete Phi nodes may be introduced, which 1304274958Sdim // are later determined to be SingleVal, and are thus redundant. 1305274958Sdim enum Status { 1306274958Sdim PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1307274958Sdim PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1308274958Sdim PH_Incomplete // Phi node is incomplete 1309274958Sdim }; 1310274958Sdim 1311274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 1312274958Sdim 1313280031Sdim Phi() 1314280031Sdim : SExpr(COP_Phi), Cvdecl(nullptr) {} 1315280031Sdim Phi(MemRegionRef A, unsigned Nvals) 1316280031Sdim : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {} 1317280031Sdim Phi(const Phi &P, ValArray &&Vs) 1318280031Sdim : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {} 1319274958Sdim 1320274958Sdim const ValArray &values() const { return Values; } 1321274958Sdim ValArray &values() { return Values; } 1322274958Sdim 1323274958Sdim Status status() const { return static_cast<Status>(Flags); } 1324274958Sdim void setStatus(Status s) { Flags = s; } 1325274958Sdim 1326280031Sdim /// Return the clang declaration of the variable for this Phi node, if any. 1327280031Sdim const clang::ValueDecl *clangDecl() const { return Cvdecl; } 1328280031Sdim 1329280031Sdim /// Set the clang variable associated with this Phi node. 1330280031Sdim void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; } 1331280031Sdim 1332274958Sdim template <class V> 1333274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1334274958Sdim typename V::template Container<typename V::R_SExpr> 1335274958Sdim Nvs(Vs, Values.size()); 1336274958Sdim 1337274958Sdim for (auto *Val : Values) { 1338274958Sdim Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1339274958Sdim } 1340274958Sdim return Vs.reducePhi(*this, Nvs); 1341274958Sdim } 1342274958Sdim 1343280031Sdim template <class C> 1344280031Sdim typename C::CType compare(const Phi *E, C &Cmp) const { 1345274958Sdim // TODO: implement CFG comparisons 1346274958Sdim return Cmp.comparePointers(this, E); 1347274958Sdim } 1348274958Sdim 1349274958Sdimprivate: 1350274958Sdim ValArray Values; 1351280031Sdim const clang::ValueDecl* Cvdecl; 1352274958Sdim}; 1353274958Sdim 1354274958Sdim 1355280031Sdim/// Base class for basic block terminators: Branch, Goto, and Return. 1356280031Sdimclass Terminator : public SExpr { 1357280031Sdimpublic: 1358280031Sdim static bool classof(const SExpr *E) { 1359280031Sdim return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; 1360280031Sdim } 1361280031Sdim 1362280031Sdimprotected: 1363280031Sdim Terminator(TIL_Opcode Op) : SExpr(Op) {} 1364280031Sdim Terminator(const SExpr &E) : SExpr(E) {} 1365280031Sdim 1366280031Sdimpublic: 1367280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1368280031Sdim ArrayRef<BasicBlock*> successors(); 1369280031Sdim 1370280031Sdim ArrayRef<BasicBlock*> successors() const { 1371280031Sdim return const_cast<Terminator*>(this)->successors(); 1372280031Sdim } 1373280031Sdim}; 1374280031Sdim 1375280031Sdim 1376280031Sdim/// Jump to another basic block. 1377280031Sdim/// A goto instruction is essentially a tail-recursive call into another 1378280031Sdim/// block. In addition to the block pointer, it specifies an index into the 1379280031Sdim/// phi nodes of that block. The index can be used to retrieve the "arguments" 1380280031Sdim/// of the call. 1381280031Sdimclass Goto : public Terminator { 1382280031Sdimpublic: 1383280031Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1384280031Sdim 1385280031Sdim Goto(BasicBlock *B, unsigned I) 1386280031Sdim : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1387280031Sdim Goto(const Goto &G, BasicBlock *B, unsigned I) 1388280031Sdim : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1389280031Sdim 1390280031Sdim const BasicBlock *targetBlock() const { return TargetBlock; } 1391280031Sdim BasicBlock *targetBlock() { return TargetBlock; } 1392280031Sdim 1393280031Sdim /// Returns the index into the 1394280031Sdim unsigned index() const { return Index; } 1395280031Sdim 1396280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1397280031Sdim ArrayRef<BasicBlock*> successors() { 1398296417Sdim return TargetBlock; 1399280031Sdim } 1400280031Sdim 1401280031Sdim template <class V> 1402280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1403280031Sdim BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1404280031Sdim return Vs.reduceGoto(*this, Ntb); 1405280031Sdim } 1406280031Sdim 1407280031Sdim template <class C> 1408280031Sdim typename C::CType compare(const Goto *E, C &Cmp) const { 1409280031Sdim // TODO: implement CFG comparisons 1410280031Sdim return Cmp.comparePointers(this, E); 1411280031Sdim } 1412280031Sdim 1413280031Sdimprivate: 1414280031Sdim BasicBlock *TargetBlock; 1415280031Sdim unsigned Index; 1416280031Sdim}; 1417280031Sdim 1418280031Sdim 1419280031Sdim/// A conditional branch to two other blocks. 1420280031Sdim/// Note that unlike Goto, Branch does not have an index. The target blocks 1421280031Sdim/// must be child-blocks, and cannot have Phi nodes. 1422280031Sdimclass Branch : public Terminator { 1423280031Sdimpublic: 1424280031Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1425280031Sdim 1426280031Sdim Branch(SExpr *C, BasicBlock *T, BasicBlock *E) 1427280031Sdim : Terminator(COP_Branch), Condition(C) { 1428280031Sdim Branches[0] = T; 1429280031Sdim Branches[1] = E; 1430280031Sdim } 1431280031Sdim Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) 1432280031Sdim : Terminator(Br), Condition(C) { 1433280031Sdim Branches[0] = T; 1434280031Sdim Branches[1] = E; 1435280031Sdim } 1436280031Sdim 1437280031Sdim const SExpr *condition() const { return Condition; } 1438280031Sdim SExpr *condition() { return Condition; } 1439280031Sdim 1440280031Sdim const BasicBlock *thenBlock() const { return Branches[0]; } 1441280031Sdim BasicBlock *thenBlock() { return Branches[0]; } 1442280031Sdim 1443280031Sdim const BasicBlock *elseBlock() const { return Branches[1]; } 1444280031Sdim BasicBlock *elseBlock() { return Branches[1]; } 1445280031Sdim 1446280031Sdim /// Return the list of basic blocks that this terminator can branch to. 1447280031Sdim ArrayRef<BasicBlock*> successors() { 1448296417Sdim return llvm::makeArrayRef(Branches); 1449280031Sdim } 1450280031Sdim 1451280031Sdim template <class V> 1452280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1453280031Sdim auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1454280031Sdim BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); 1455280031Sdim BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); 1456280031Sdim return Vs.reduceBranch(*this, Nc, Ntb, Nte); 1457280031Sdim } 1458280031Sdim 1459280031Sdim template <class C> 1460280031Sdim typename C::CType compare(const Branch *E, C &Cmp) const { 1461280031Sdim // TODO: implement CFG comparisons 1462280031Sdim return Cmp.comparePointers(this, E); 1463280031Sdim } 1464280031Sdim 1465280031Sdimprivate: 1466280031Sdim SExpr* Condition; 1467280031Sdim BasicBlock *Branches[2]; 1468280031Sdim}; 1469280031Sdim 1470280031Sdim 1471280031Sdim/// Return from the enclosing function, passing the return value to the caller. 1472280031Sdim/// Only the exit block should end with a return statement. 1473280031Sdimclass Return : public Terminator { 1474280031Sdimpublic: 1475280031Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } 1476280031Sdim 1477280031Sdim Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} 1478280031Sdim Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} 1479280031Sdim 1480280031Sdim /// Return an empty list. 1481280031Sdim ArrayRef<BasicBlock*> successors() { 1482296417Sdim return None; 1483280031Sdim } 1484280031Sdim 1485280031Sdim SExpr *returnValue() { return Retval; } 1486280031Sdim const SExpr *returnValue() const { return Retval; } 1487280031Sdim 1488280031Sdim template <class V> 1489280031Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1490280031Sdim auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); 1491280031Sdim return Vs.reduceReturn(*this, Ne); 1492280031Sdim } 1493280031Sdim 1494280031Sdim template <class C> 1495280031Sdim typename C::CType compare(const Return *E, C &Cmp) const { 1496280031Sdim return Cmp.compare(Retval, E->Retval); 1497280031Sdim } 1498280031Sdim 1499280031Sdimprivate: 1500280031Sdim SExpr* Retval; 1501280031Sdim}; 1502280031Sdim 1503280031Sdim 1504280031Sdiminline ArrayRef<BasicBlock*> Terminator::successors() { 1505280031Sdim switch (opcode()) { 1506280031Sdim case COP_Goto: return cast<Goto>(this)->successors(); 1507280031Sdim case COP_Branch: return cast<Branch>(this)->successors(); 1508280031Sdim case COP_Return: return cast<Return>(this)->successors(); 1509280031Sdim default: 1510296417Sdim return None; 1511280031Sdim } 1512280031Sdim} 1513280031Sdim 1514280031Sdim 1515280031Sdim/// A basic block is part of an SCFG. It can be treated as a function in 1516280031Sdim/// continuation passing style. A block consists of a sequence of phi nodes, 1517280031Sdim/// which are "arguments" to the function, followed by a sequence of 1518280031Sdim/// instructions. It ends with a Terminator, which is a Branch or Goto to 1519280031Sdim/// another basic block in the same SCFG. 1520274958Sdimclass BasicBlock : public SExpr { 1521274958Sdimpublic: 1522280031Sdim typedef SimpleArray<SExpr*> InstrArray; 1523274958Sdim typedef SimpleArray<BasicBlock*> BlockArray; 1524274958Sdim 1525280031Sdim // TopologyNodes are used to overlay tree structures on top of the CFG, 1526280031Sdim // such as dominator and postdominator trees. Each block is assigned an 1527280031Sdim // ID in the tree according to a depth-first search. Tree traversals are 1528280031Sdim // always up, towards the parents. 1529280031Sdim struct TopologyNode { 1530280031Sdim TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {} 1531280031Sdim 1532280031Sdim bool isParentOf(const TopologyNode& OtherNode) { 1533280031Sdim return OtherNode.NodeID > NodeID && 1534280031Sdim OtherNode.NodeID < NodeID + SizeOfSubTree; 1535280031Sdim } 1536280031Sdim 1537280031Sdim bool isParentOfOrEqual(const TopologyNode& OtherNode) { 1538280031Sdim return OtherNode.NodeID >= NodeID && 1539280031Sdim OtherNode.NodeID < NodeID + SizeOfSubTree; 1540280031Sdim } 1541280031Sdim 1542280031Sdim int NodeID; 1543280031Sdim int SizeOfSubTree; // Includes this node, so must be > 1. 1544280031Sdim BasicBlock *Parent; // Pointer to parent. 1545280031Sdim }; 1546280031Sdim 1547274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } 1548274958Sdim 1549280031Sdim explicit BasicBlock(MemRegionRef A) 1550274958Sdim : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), 1551280031Sdim Visited(0), TermInstr(nullptr) {} 1552280031Sdim BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, 1553280031Sdim Terminator *T) 1554280031Sdim : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0), 1555280031Sdim Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} 1556274958Sdim 1557280031Sdim /// Returns the block ID. Every block has a unique ID in the CFG. 1558280031Sdim int blockID() const { return BlockID; } 1559274958Sdim 1560280031Sdim /// Returns the number of predecessors. 1561280031Sdim size_t numPredecessors() const { return Predecessors.size(); } 1562280031Sdim size_t numSuccessors() const { return successors().size(); } 1563280031Sdim 1564274958Sdim const SCFG* cfg() const { return CFGPtr; } 1565274958Sdim SCFG* cfg() { return CFGPtr; } 1566274958Sdim 1567280031Sdim const BasicBlock *parent() const { return DominatorNode.Parent; } 1568280031Sdim BasicBlock *parent() { return DominatorNode.Parent; } 1569274958Sdim 1570280031Sdim const InstrArray &arguments() const { return Args; } 1571280031Sdim InstrArray &arguments() { return Args; } 1572274958Sdim 1573280031Sdim InstrArray &instructions() { return Instrs; } 1574280031Sdim const InstrArray &instructions() const { return Instrs; } 1575274958Sdim 1576280031Sdim /// Returns a list of predecessors. 1577280031Sdim /// The order of predecessors in the list is important; each phi node has 1578280031Sdim /// exactly one argument for each precessor, in the same order. 1579280031Sdim BlockArray &predecessors() { return Predecessors; } 1580274958Sdim const BlockArray &predecessors() const { return Predecessors; } 1581274958Sdim 1582280031Sdim ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } 1583280031Sdim ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } 1584274958Sdim 1585280031Sdim const Terminator *terminator() const { return TermInstr; } 1586280031Sdim Terminator *terminator() { return TermInstr; } 1587274958Sdim 1588280031Sdim void setTerminator(Terminator *E) { TermInstr = E; } 1589280031Sdim 1590280031Sdim bool Dominates(const BasicBlock &Other) { 1591280031Sdim return DominatorNode.isParentOfOrEqual(Other.DominatorNode); 1592280031Sdim } 1593280031Sdim 1594280031Sdim bool PostDominates(const BasicBlock &Other) { 1595280031Sdim return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); 1596280031Sdim } 1597280031Sdim 1598280031Sdim /// Add a new argument. 1599280031Sdim void addArgument(Phi *V) { 1600274958Sdim Args.reserveCheck(1, Arena); 1601274958Sdim Args.push_back(V); 1602274958Sdim } 1603280031Sdim /// Add a new instruction. 1604280031Sdim void addInstruction(SExpr *V) { 1605274958Sdim Instrs.reserveCheck(1, Arena); 1606274958Sdim Instrs.push_back(V); 1607274958Sdim } 1608274958Sdim // Add a new predecessor, and return the phi-node index for it. 1609274958Sdim // Will add an argument to all phi-nodes, initialized to nullptr. 1610274958Sdim unsigned addPredecessor(BasicBlock *Pred); 1611274958Sdim 1612274958Sdim // Reserve space for Nargs arguments. 1613274958Sdim void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } 1614274958Sdim 1615274958Sdim // Reserve space for Nins instructions. 1616274958Sdim void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } 1617274958Sdim 1618274958Sdim // Reserve space for NumPreds predecessors, including space in phi nodes. 1619274958Sdim void reservePredecessors(unsigned NumPreds); 1620274958Sdim 1621280031Sdim /// Return the index of BB, or Predecessors.size if BB is not a predecessor. 1622274958Sdim unsigned findPredecessorIndex(const BasicBlock *BB) const { 1623274958Sdim auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB); 1624274958Sdim return std::distance(Predecessors.cbegin(), I); 1625274958Sdim } 1626274958Sdim 1627274958Sdim template <class V> 1628274958Sdim typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { 1629280031Sdim typename V::template Container<SExpr*> Nas(Vs, Args.size()); 1630280031Sdim typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); 1631274958Sdim 1632274958Sdim // Entering the basic block should do any scope initialization. 1633274958Sdim Vs.enterBasicBlock(*this); 1634274958Sdim 1635280031Sdim for (auto *E : Args) { 1636280031Sdim auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1637280031Sdim Nas.push_back(Ne); 1638274958Sdim } 1639280031Sdim for (auto *E : Instrs) { 1640280031Sdim auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1641280031Sdim Nis.push_back(Ne); 1642274958Sdim } 1643280031Sdim auto Nt = Vs.traverse(TermInstr, Ctx); 1644274958Sdim 1645274958Sdim // Exiting the basic block should handle any scope cleanup. 1646274958Sdim Vs.exitBasicBlock(*this); 1647274958Sdim 1648274958Sdim return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); 1649274958Sdim } 1650274958Sdim 1651280031Sdim template <class C> 1652280031Sdim typename C::CType compare(const BasicBlock *E, C &Cmp) const { 1653274958Sdim // TODO: implement CFG comparisons 1654274958Sdim return Cmp.comparePointers(this, E); 1655274958Sdim } 1656274958Sdim 1657274958Sdimprivate: 1658274958Sdim friend class SCFG; 1659274958Sdim 1660280031Sdim int renumberInstrs(int id); // assign unique ids to all instructions 1661280031Sdim int topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID); 1662280031Sdim int topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID); 1663280031Sdim void computeDominator(); 1664280031Sdim void computePostDominator(); 1665274958Sdim 1666280031Sdimprivate: 1667280031Sdim MemRegionRef Arena; // The arena used to allocate this block. 1668280031Sdim SCFG *CFGPtr; // The CFG that contains this block. 1669280031Sdim int BlockID : 31; // unique id for this BB in the containing CFG. 1670280031Sdim // IDs are in topological order. 1671280031Sdim bool Visited : 1; // Bit to determine if a block has been visited 1672280031Sdim // during a traversal. 1673280031Sdim BlockArray Predecessors; // Predecessor blocks in the CFG. 1674280031Sdim InstrArray Args; // Phi nodes. One argument per predecessor. 1675280031Sdim InstrArray Instrs; // Instructions. 1676280031Sdim Terminator* TermInstr; // Terminating instruction 1677280031Sdim 1678280031Sdim TopologyNode DominatorNode; // The dominator tree 1679280031Sdim TopologyNode PostDominatorNode; // The post-dominator tree 1680274958Sdim}; 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: 1688274958Sdim typedef SimpleArray<BasicBlock *> BlockArray; 1689274958Sdim typedef BlockArray::iterator iterator; 1690274958Sdim typedef BlockArray::const_iterator const_iterator; 1691274958Sdim 1692274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } 1693274958Sdim 1694274958Sdim SCFG(MemRegionRef A, unsigned Nblocks) 1695274958Sdim : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), 1696280031Sdim Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { 1697280031Sdim Entry = new (A) BasicBlock(A); 1698280031Sdim Exit = new (A) BasicBlock(A); 1699280031Sdim auto *V = new (A) Phi(); 1700274958Sdim Exit->addArgument(V); 1701280031Sdim Exit->setTerminator(new (A) Return(V)); 1702274958Sdim add(Entry); 1703274958Sdim add(Exit); 1704274958Sdim } 1705274958Sdim SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba 1706274958Sdim : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), 1707280031Sdim Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { 1708274958Sdim // TODO: set entry and exit! 1709274958Sdim } 1710274958Sdim 1711280031Sdim /// Return true if this CFG is valid. 1712280031Sdim bool valid() const { return Entry && Exit && Blocks.size() > 0; } 1713280031Sdim 1714280031Sdim /// Return true if this CFG has been normalized. 1715280031Sdim /// After normalization, blocks are in topological order, and block and 1716280031Sdim /// instruction IDs have been assigned. 1717280031Sdim bool normal() const { return Normal; } 1718280031Sdim 1719274958Sdim iterator begin() { return Blocks.begin(); } 1720274958Sdim iterator end() { return Blocks.end(); } 1721274958Sdim 1722274958Sdim const_iterator begin() const { return cbegin(); } 1723274958Sdim const_iterator end() const { return cend(); } 1724274958Sdim 1725274958Sdim const_iterator cbegin() const { return Blocks.cbegin(); } 1726274958Sdim const_iterator cend() const { return Blocks.cend(); } 1727274958Sdim 1728274958Sdim const BasicBlock *entry() const { return Entry; } 1729274958Sdim BasicBlock *entry() { return Entry; } 1730274958Sdim const BasicBlock *exit() const { return Exit; } 1731274958Sdim BasicBlock *exit() { return Exit; } 1732274958Sdim 1733280031Sdim /// Return the number of blocks in the CFG. 1734280031Sdim /// Block::blockID() will return a number less than numBlocks(); 1735280031Sdim size_t numBlocks() const { return Blocks.size(); } 1736280031Sdim 1737280031Sdim /// Return the total number of instructions in the CFG. 1738280031Sdim /// This is useful for building instruction side-tables; 1739280031Sdim /// A call to SExpr::id() will return a number less than numInstructions(). 1740280031Sdim unsigned numInstructions() { return NumInstructions; } 1741280031Sdim 1742274958Sdim inline void add(BasicBlock *BB) { 1743280031Sdim assert(BB->CFGPtr == nullptr); 1744274958Sdim BB->CFGPtr = this; 1745274958Sdim Blocks.reserveCheck(1, Arena); 1746274958Sdim Blocks.push_back(BB); 1747274958Sdim } 1748274958Sdim 1749274958Sdim void setEntry(BasicBlock *BB) { Entry = BB; } 1750274958Sdim void setExit(BasicBlock *BB) { Exit = BB; } 1751274958Sdim 1752280031Sdim void computeNormalForm(); 1753274958Sdim 1754274958Sdim template <class V> 1755274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1756274958Sdim Vs.enterCFG(*this); 1757274958Sdim typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); 1758280031Sdim 1759274958Sdim for (auto *B : Blocks) { 1760274958Sdim Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); 1761274958Sdim } 1762274958Sdim Vs.exitCFG(*this); 1763274958Sdim return Vs.reduceSCFG(*this, Bbs); 1764274958Sdim } 1765274958Sdim 1766280031Sdim template <class C> 1767280031Sdim typename C::CType compare(const SCFG *E, C &Cmp) const { 1768280031Sdim // TODO: implement CFG comparisons 1769274958Sdim return Cmp.comparePointers(this, E); 1770274958Sdim } 1771274958Sdim 1772274958Sdimprivate: 1773280031Sdim void renumberInstrs(); // assign unique ids to all instructions 1774280031Sdim 1775280031Sdimprivate: 1776274958Sdim MemRegionRef Arena; 1777274958Sdim BlockArray Blocks; 1778274958Sdim BasicBlock *Entry; 1779274958Sdim BasicBlock *Exit; 1780280031Sdim unsigned NumInstructions; 1781280031Sdim bool Normal; 1782274958Sdim}; 1783274958Sdim 1784274958Sdim 1785274958Sdim 1786280031Sdim/// An identifier, e.g. 'foo' or 'x'. 1787280031Sdim/// This is a pseduo-term; it will be lowered to a variable or projection. 1788274958Sdimclass Identifier : public SExpr { 1789274958Sdimpublic: 1790274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } 1791274958Sdim 1792274958Sdim Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { } 1793274958Sdim Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { } 1794274958Sdim 1795274958Sdim StringRef name() const { return Name; } 1796274958Sdim 1797274958Sdim template <class V> 1798274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1799274958Sdim return Vs.reduceIdentifier(*this); 1800274958Sdim } 1801274958Sdim 1802280031Sdim template <class C> 1803280031Sdim typename C::CType compare(const Identifier* E, C& Cmp) const { 1804274958Sdim return Cmp.compareStrings(name(), E->name()); 1805274958Sdim } 1806274958Sdim 1807274958Sdimprivate: 1808274958Sdim StringRef Name; 1809274958Sdim}; 1810274958Sdim 1811274958Sdim 1812280031Sdim/// An if-then-else expression. 1813280031Sdim/// This is a pseduo-term; it will be lowered to a branch in a CFG. 1814274958Sdimclass IfThenElse : public SExpr { 1815274958Sdimpublic: 1816274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } 1817274958Sdim 1818274958Sdim IfThenElse(SExpr *C, SExpr *T, SExpr *E) 1819274958Sdim : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) 1820274958Sdim { } 1821274958Sdim IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) 1822274958Sdim : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) 1823274958Sdim { } 1824274958Sdim 1825280031Sdim SExpr *condition() { return Condition; } // Address to store to 1826280031Sdim const SExpr *condition() const { return Condition; } 1827274958Sdim 1828280031Sdim SExpr *thenExpr() { return ThenExpr; } // Value to store 1829280031Sdim const SExpr *thenExpr() const { return ThenExpr; } 1830274958Sdim 1831280031Sdim SExpr *elseExpr() { return ElseExpr; } // Value to store 1832280031Sdim const SExpr *elseExpr() const { return ElseExpr; } 1833274958Sdim 1834274958Sdim template <class V> 1835274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1836274958Sdim auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1837274958Sdim auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); 1838274958Sdim auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); 1839274958Sdim return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); 1840274958Sdim } 1841274958Sdim 1842280031Sdim template <class C> 1843280031Sdim typename C::CType compare(const IfThenElse* E, C& Cmp) const { 1844274958Sdim typename C::CType Ct = Cmp.compare(condition(), E->condition()); 1845274958Sdim if (Cmp.notTrue(Ct)) 1846274958Sdim return Ct; 1847274958Sdim Ct = Cmp.compare(thenExpr(), E->thenExpr()); 1848274958Sdim if (Cmp.notTrue(Ct)) 1849274958Sdim return Ct; 1850274958Sdim return Cmp.compare(elseExpr(), E->elseExpr()); 1851274958Sdim } 1852274958Sdim 1853274958Sdimprivate: 1854280031Sdim SExpr* Condition; 1855280031Sdim SExpr* ThenExpr; 1856280031Sdim SExpr* ElseExpr; 1857274958Sdim}; 1858274958Sdim 1859274958Sdim 1860280031Sdim/// A let-expression, e.g. let x=t; u. 1861280031Sdim/// This is a pseduo-term; it will be lowered to instructions in a CFG. 1862274958Sdimclass Let : public SExpr { 1863274958Sdimpublic: 1864274958Sdim static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } 1865274958Sdim 1866274958Sdim Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { 1867274958Sdim Vd->setKind(Variable::VK_Let); 1868274958Sdim } 1869274958Sdim Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { 1870274958Sdim Vd->setKind(Variable::VK_Let); 1871274958Sdim } 1872274958Sdim 1873274958Sdim Variable *variableDecl() { return VarDecl; } 1874274958Sdim const Variable *variableDecl() const { return VarDecl; } 1875274958Sdim 1876280031Sdim SExpr *body() { return Body; } 1877280031Sdim const SExpr *body() const { return Body; } 1878274958Sdim 1879274958Sdim template <class V> 1880274958Sdim typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1881274958Sdim // This is a variable declaration, so traverse the definition. 1882274958Sdim auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); 1883274958Sdim // Tell the rewriter to enter the scope of the let variable. 1884274958Sdim Variable *Nvd = Vs.enterScope(*VarDecl, E0); 1885274958Sdim auto E1 = Vs.traverse(Body, Ctx); 1886274958Sdim Vs.exitScope(*VarDecl); 1887274958Sdim return Vs.reduceLet(*this, Nvd, E1); 1888274958Sdim } 1889274958Sdim 1890280031Sdim template <class C> 1891280031Sdim typename C::CType compare(const Let* E, C& Cmp) const { 1892274958Sdim typename C::CType Ct = 1893274958Sdim Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 1894274958Sdim if (Cmp.notTrue(Ct)) 1895274958Sdim return Ct; 1896274958Sdim Cmp.enterScope(variableDecl(), E->variableDecl()); 1897274958Sdim Ct = Cmp.compare(body(), E->body()); 1898274958Sdim Cmp.leaveScope(); 1899274958Sdim return Ct; 1900274958Sdim } 1901274958Sdim 1902274958Sdimprivate: 1903274958Sdim Variable *VarDecl; 1904280031Sdim SExpr* Body; 1905274958Sdim}; 1906274958Sdim 1907274958Sdim 1908274958Sdim 1909280031Sdimconst SExpr *getCanonicalVal(const SExpr *E); 1910280031SdimSExpr* simplifyToCanonicalVal(SExpr *E); 1911280031Sdimvoid simplifyIncompleteArg(til::Phi *Ph); 1912274958Sdim 1913274958Sdim 1914274958Sdim} // end namespace til 1915274958Sdim} // end namespace threadSafety 1916274958Sdim} // end namespace clang 1917274958Sdim 1918280031Sdim#endif 1919