1 //===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT in the llvm repository for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines a simple Typed Intermediate Language, or TIL, that is used 11 // by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended 12 // to be largely independent of clang, in the hope that the analysis can be 13 // reused for other non-C++ languages. All dependencies on clang/llvm should 14 // go in ThreadSafetyUtil.h. 15 // 16 // Thread safety analysis works by comparing mutex expressions, e.g. 17 // 18 // class A { Mutex mu; int dat GUARDED_BY(this->mu); } 19 // class B { A a; } 20 // 21 // void foo(B* b) { 22 // (*b).a.mu.lock(); // locks (*b).a.mu 23 // b->a.dat = 0; // substitute &b->a for 'this'; 24 // // requires lock on (&b->a)->mu 25 // (b->a.mu).unlock(); // unlocks (b->a.mu) 26 // } 27 // 28 // As illustrated by the above example, clang Exprs are not well-suited to 29 // represent mutex expressions directly, since there is no easy way to compare 30 // Exprs for equivalence. The thread safety analysis thus lowers clang Exprs 31 // into a simple intermediate language (IL). The IL supports: 32 // 33 // (1) comparisons for semantic equality of expressions 34 // (2) SSA renaming of variables 35 // (3) wildcards and pattern matching over expressions 36 // (4) hash-based expression lookup 37 // 38 // The TIL is currently very experimental, is intended only for use within 39 // the thread safety analysis, and is subject to change without notice. 40 // After the API stabilizes and matures, it may be appropriate to make this 41 // more generally available to other analyses. 42 // 43 // UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 44 // 45 //===----------------------------------------------------------------------===// 46 47 #ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H 48 #define LLVM_CLANG_THREAD_SAFETY_TIL_H 49 50 // All clang include dependencies for this file must be put in 51 // ThreadSafetyUtil.h. 52 #include "ThreadSafetyUtil.h" 53 54 #include <stdint.h> 55 #include <algorithm> 56 #include <cassert> 57 #include <cstddef> 58 #include <utility> 59 60 61 namespace clang { 62 namespace threadSafety { 63 namespace til { 64 65 66 enum TIL_Opcode { 67 #define TIL_OPCODE_DEF(X) COP_##X, 68 #include "ThreadSafetyOps.def" 69 #undef TIL_OPCODE_DEF 70 }; 71 72 enum TIL_UnaryOpcode : unsigned char { 73 UOP_Minus, // - 74 UOP_BitNot, // ~ 75 UOP_LogicNot // ! 76 }; 77 78 enum TIL_BinaryOpcode : unsigned char { 79 BOP_Mul, // * 80 BOP_Div, // / 81 BOP_Rem, // % 82 BOP_Add, // + 83 BOP_Sub, // - 84 BOP_Shl, // << 85 BOP_Shr, // >> 86 BOP_BitAnd, // & 87 BOP_BitXor, // ^ 88 BOP_BitOr, // | 89 BOP_Eq, // == 90 BOP_Neq, // != 91 BOP_Lt, // < 92 BOP_Leq, // <= 93 BOP_LogicAnd, // && 94 BOP_LogicOr // || 95 }; 96 97 enum TIL_CastOpcode : unsigned char { 98 CAST_none = 0, 99 CAST_extendNum, // extend precision of numeric type 100 CAST_truncNum, // truncate precision of numeric type 101 CAST_toFloat, // convert to floating point type 102 CAST_toInt, // convert to integer type 103 }; 104 105 const TIL_Opcode COP_Min = COP_Future; 106 const TIL_Opcode COP_Max = COP_Branch; 107 const TIL_UnaryOpcode UOP_Min = UOP_Minus; 108 const TIL_UnaryOpcode UOP_Max = UOP_LogicNot; 109 const TIL_BinaryOpcode BOP_Min = BOP_Mul; 110 const TIL_BinaryOpcode BOP_Max = BOP_LogicOr; 111 const TIL_CastOpcode CAST_Min = CAST_none; 112 const TIL_CastOpcode CAST_Max = CAST_toInt; 113 114 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); 115 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); 116 117 118 // ValueTypes are data types that can actually be held in registers. 119 // All variables and expressions must have a vBNF_Nonealue type. 120 // Pointer types are further subdivided into the various heap-allocated 121 // types, such as functions, records, etc. 122 // Structured types that are passed by value (e.g. complex numbers) 123 // require special handling; they use BT_ValueRef, and size ST_0. 124 struct ValueType { 125 enum BaseType : unsigned char { 126 BT_Void = 0, 127 BT_Bool, 128 BT_Int, 129 BT_Float, 130 BT_String, // String literals 131 BT_Pointer, 132 BT_ValueRef 133 }; 134 135 enum SizeType : unsigned char { 136 ST_0 = 0, 137 ST_1, 138 ST_8, 139 ST_16, 140 ST_32, 141 ST_64, 142 ST_128 143 }; 144 145 inline static SizeType getSizeType(unsigned nbytes); 146 147 template <class T> 148 inline static ValueType getValueType(); 149 150 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) 151 : Base(B), Size(Sz), Signed(S), VectSize(VS) 152 { } 153 154 BaseType Base; 155 SizeType Size; 156 bool Signed; 157 unsigned char VectSize; // 0 for scalar, otherwise num elements in vector 158 }; 159 160 161 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { 162 switch (nbytes) { 163 case 1: return ST_8; 164 case 2: return ST_16; 165 case 4: return ST_32; 166 case 8: return ST_64; 167 case 16: return ST_128; 168 default: return ST_0; 169 } 170 } 171 172 173 template<> 174 inline ValueType ValueType::getValueType<void>() { 175 return ValueType(BT_Void, ST_0, false, 0); 176 } 177 178 template<> 179 inline ValueType ValueType::getValueType<bool>() { 180 return ValueType(BT_Bool, ST_1, false, 0); 181 } 182 183 template<> 184 inline ValueType ValueType::getValueType<int8_t>() { 185 return ValueType(BT_Int, ST_8, true, 0); 186 } 187 188 template<> 189 inline ValueType ValueType::getValueType<uint8_t>() { 190 return ValueType(BT_Int, ST_8, false, 0); 191 } 192 193 template<> 194 inline ValueType ValueType::getValueType<int16_t>() { 195 return ValueType(BT_Int, ST_16, true, 0); 196 } 197 198 template<> 199 inline ValueType ValueType::getValueType<uint16_t>() { 200 return ValueType(BT_Int, ST_16, false, 0); 201 } 202 203 template<> 204 inline ValueType ValueType::getValueType<int32_t>() { 205 return ValueType(BT_Int, ST_32, true, 0); 206 } 207 208 template<> 209 inline ValueType ValueType::getValueType<uint32_t>() { 210 return ValueType(BT_Int, ST_32, false, 0); 211 } 212 213 template<> 214 inline ValueType ValueType::getValueType<int64_t>() { 215 return ValueType(BT_Int, ST_64, true, 0); 216 } 217 218 template<> 219 inline ValueType ValueType::getValueType<uint64_t>() { 220 return ValueType(BT_Int, ST_64, false, 0); 221 } 222 223 template<> 224 inline ValueType ValueType::getValueType<float>() { 225 return ValueType(BT_Float, ST_32, true, 0); 226 } 227 228 template<> 229 inline ValueType ValueType::getValueType<double>() { 230 return ValueType(BT_Float, ST_64, true, 0); 231 } 232 233 template<> 234 inline ValueType ValueType::getValueType<long double>() { 235 return ValueType(BT_Float, ST_128, true, 0); 236 } 237 238 template<> 239 inline ValueType ValueType::getValueType<StringRef>() { 240 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); 241 } 242 243 template<> 244 inline ValueType ValueType::getValueType<void*>() { 245 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); 246 } 247 248 249 250 // Base class for AST nodes in the typed intermediate language. 251 class SExpr { 252 public: 253 TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } 254 255 // Subclasses of SExpr must define the following: 256 // 257 // This(const This& E, ...) { 258 // copy constructor: construct copy of E, with some additional arguments. 259 // } 260 // 261 // template <class V> 262 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 263 // traverse all subexpressions, following the traversal/rewriter interface. 264 // } 265 // 266 // template <class C> typename C::CType compare(CType* E, C& Cmp) { 267 // compare all subexpressions, following the comparator interface 268 // } 269 270 void *operator new(size_t S, MemRegionRef &R) { 271 return ::operator new(S, R); 272 } 273 274 // SExpr objects cannot be deleted. 275 // This declaration is public to workaround a gcc bug that breaks building 276 // with REQUIRES_EH=1. 277 void operator delete(void *) LLVM_DELETED_FUNCTION; 278 279 protected: 280 SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {} 281 SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {} 282 283 const unsigned char Opcode; 284 unsigned char Reserved; 285 unsigned short Flags; 286 287 private: 288 SExpr() LLVM_DELETED_FUNCTION; 289 290 // SExpr objects must be created in an arena. 291 void *operator new(size_t) LLVM_DELETED_FUNCTION; 292 }; 293 294 295 // Class for owning references to SExprs. 296 // Includes attach/detach logic for counting variable references and lazy 297 // rewriting strategies. 298 class SExprRef { 299 public: 300 SExprRef() : Ptr(nullptr) { } 301 SExprRef(std::nullptr_t P) : Ptr(nullptr) { } 302 SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; } 303 304 // Defined after Variable and Future, below. 305 inline SExprRef(SExpr *P); 306 inline ~SExprRef(); 307 308 SExpr *get() { return Ptr; } 309 const SExpr *get() const { return Ptr; } 310 311 SExpr *operator->() { return get(); } 312 const SExpr *operator->() const { return get(); } 313 314 SExpr &operator*() { return *Ptr; } 315 const SExpr &operator*() const { return *Ptr; } 316 317 bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; } 318 bool operator!=(const SExprRef &R) const { return !operator==(R); } 319 bool operator==(const SExpr *P) const { return Ptr == P; } 320 bool operator!=(const SExpr *P) const { return !operator==(P); } 321 bool operator==(std::nullptr_t) const { return Ptr == nullptr; } 322 bool operator!=(std::nullptr_t) const { return Ptr != nullptr; } 323 324 inline void reset(SExpr *E); 325 326 private: 327 inline void attach(); 328 inline void detach(); 329 330 SExpr *Ptr; 331 }; 332 333 334 // Contains various helper functions for SExprs. 335 namespace ThreadSafetyTIL { 336 inline bool isTrivial(const SExpr *E) { 337 unsigned Op = E->opcode(); 338 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; 339 } 340 } 341 342 // Nodes which declare variables 343 class Function; 344 class SFunction; 345 class BasicBlock; 346 class Let; 347 348 349 // A named variable, e.g. "x". 350 // 351 // There are two distinct places in which a Variable can appear in the AST. 352 // A variable declaration introduces a new variable, and can occur in 3 places: 353 // Let-expressions: (Let (x = t) u) 354 // Functions: (Function (x : t) u) 355 // Self-applicable functions (SFunction (x) t) 356 // 357 // If a variable occurs in any other location, it is a reference to an existing 358 // variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't 359 // allocate a separate AST node for variable references; a reference is just a 360 // pointer to the original declaration. 361 class Variable : public SExpr { 362 public: 363 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } 364 365 // Let-variable, function parameter, or self-variable 366 enum VariableKind { 367 VK_Let, 368 VK_LetBB, 369 VK_Fun, 370 VK_SFun 371 }; 372 373 // These are defined after SExprRef contructor, below 374 inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr); 375 inline Variable(StringRef s, SExpr *D = nullptr); 376 inline Variable(const Variable &Vd, SExpr *D); 377 378 VariableKind kind() const { return static_cast<VariableKind>(Flags); } 379 380 const StringRef name() const { return Name; } 381 const clang::ValueDecl *clangDecl() const { return Cvdecl; } 382 383 // Returns the definition (for let vars) or type (for parameter & self vars) 384 SExpr *definition() { return Definition.get(); } 385 const SExpr *definition() const { return Definition.get(); } 386 387 void attachVar() const { ++NumUses; } 388 void detachVar() const { assert(NumUses > 0); --NumUses; } 389 390 unsigned getID() const { return Id; } 391 unsigned getBlockID() const { return BlockID; } 392 393 void setName(StringRef S) { Name = S; } 394 void setID(unsigned Bid, unsigned I) { 395 BlockID = static_cast<unsigned short>(Bid); 396 Id = static_cast<unsigned short>(I); 397 } 398 void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } 399 void setDefinition(SExpr *E); 400 void setKind(VariableKind K) { Flags = K; } 401 402 template <class V> 403 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 404 // This routine is only called for variable references. 405 return Vs.reduceVariableRef(this); 406 } 407 408 template <class C> typename C::CType compare(Variable* E, C& Cmp) { 409 return Cmp.compareVariableRefs(this, E); 410 } 411 412 private: 413 friend class Function; 414 friend class SFunction; 415 friend class BasicBlock; 416 friend class Let; 417 418 StringRef Name; // The name of the variable. 419 SExprRef Definition; // The TIL type or definition 420 const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. 421 422 unsigned short BlockID; 423 unsigned short Id; 424 mutable unsigned NumUses; 425 }; 426 427 428 // Placeholder for an expression that has not yet been created. 429 // Used to implement lazy copy and rewriting strategies. 430 class Future : public SExpr { 431 public: 432 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } 433 434 enum FutureStatus { 435 FS_pending, 436 FS_evaluating, 437 FS_done 438 }; 439 440 Future() : 441 SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr) 442 {} 443 private: 444 virtual ~Future() LLVM_DELETED_FUNCTION; 445 public: 446 447 // Registers the location in the AST where this future is stored. 448 // Forcing the future will automatically update the AST. 449 static inline void registerLocation(SExprRef *Member) { 450 if (Future *F = dyn_cast_or_null<Future>(Member->get())) 451 F->Location = Member; 452 } 453 454 // A lazy rewriting strategy should subclass Future and override this method. 455 virtual SExpr *create() { return nullptr; } 456 457 // Return the result of this future if it exists, otherwise return null. 458 SExpr *maybeGetResult() { 459 return Result; 460 } 461 462 // Return the result of this future; forcing it if necessary. 463 SExpr *result() { 464 switch (Status) { 465 case FS_pending: 466 force(); 467 return Result; 468 case FS_evaluating: 469 return nullptr; // infinite loop; illegal recursion. 470 case FS_done: 471 return Result; 472 } 473 } 474 475 template <class V> 476 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 477 assert(Result && "Cannot traverse Future that has not been forced."); 478 return Vs.traverse(Result, Ctx); 479 } 480 481 template <class C> typename C::CType compare(Future* E, C& Cmp) { 482 if (!Result || !E->Result) 483 return Cmp.comparePointers(this, E); 484 return Cmp.compare(Result, E->Result); 485 } 486 487 private: 488 // Force the future. 489 inline void force(); 490 491 FutureStatus Status; 492 SExpr *Result; 493 SExprRef *Location; 494 }; 495 496 497 inline void SExprRef::attach() { 498 if (!Ptr) 499 return; 500 501 TIL_Opcode Op = Ptr->opcode(); 502 if (Op == COP_Variable) { 503 cast<Variable>(Ptr)->attachVar(); 504 } else if (Op == COP_Future) { 505 cast<Future>(Ptr)->registerLocation(this); 506 } 507 } 508 509 inline void SExprRef::detach() { 510 if (Ptr && Ptr->opcode() == COP_Variable) { 511 cast<Variable>(Ptr)->detachVar(); 512 } 513 } 514 515 inline SExprRef::SExprRef(SExpr *P) : Ptr(P) { 516 attach(); 517 } 518 519 inline SExprRef::~SExprRef() { 520 detach(); 521 } 522 523 inline void SExprRef::reset(SExpr *P) { 524 detach(); 525 Ptr = P; 526 attach(); 527 } 528 529 530 inline Variable::Variable(StringRef s, SExpr *D) 531 : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr), 532 BlockID(0), Id(0), NumUses(0) { 533 Flags = VK_Let; 534 } 535 536 inline Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd) 537 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), 538 Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) { 539 Flags = VK_Let; 540 } 541 542 inline Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor 543 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl), 544 BlockID(0), Id(0), NumUses(0) { 545 Flags = Vd.kind(); 546 } 547 548 inline void Variable::setDefinition(SExpr *E) { 549 Definition.reset(E); 550 } 551 552 void Future::force() { 553 Status = FS_evaluating; 554 SExpr *R = create(); 555 Result = R; 556 if (Location) 557 Location->reset(R); 558 Status = FS_done; 559 } 560 561 562 // Placeholder for C++ expressions that cannot be represented in the TIL. 563 class Undefined : public SExpr { 564 public: 565 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 566 567 Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} 568 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} 569 570 template <class V> 571 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 572 return Vs.reduceUndefined(*this); 573 } 574 575 template <class C> typename C::CType compare(Undefined* E, C& Cmp) { 576 return Cmp.comparePointers(Cstmt, E->Cstmt); 577 } 578 579 private: 580 const clang::Stmt *Cstmt; 581 }; 582 583 584 // Placeholder for a wildcard that matches any other expression. 585 class Wildcard : public SExpr { 586 public: 587 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 588 589 Wildcard() : SExpr(COP_Wildcard) {} 590 Wildcard(const Wildcard &W) : SExpr(W) {} 591 592 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 593 return Vs.reduceWildcard(*this); 594 } 595 596 template <class C> typename C::CType compare(Wildcard* E, C& Cmp) { 597 return Cmp.trueResult(); 598 } 599 }; 600 601 602 template <class T> class LiteralT; 603 604 // Base class for literal values. 605 class Literal : public SExpr { 606 public: 607 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 608 609 Literal(const clang::Expr *C) 610 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) 611 { } 612 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {} 613 Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {} 614 615 // The clang expression for this literal. 616 const clang::Expr *clangExpr() const { return Cexpr; } 617 618 ValueType valueType() const { return ValType; } 619 620 template<class T> const LiteralT<T>& as() const { 621 return *static_cast<const LiteralT<T>*>(this); 622 } 623 template<class T> LiteralT<T>& as() { 624 return *static_cast<LiteralT<T>*>(this); 625 } 626 627 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 628 629 template <class C> typename C::CType compare(Literal* E, C& Cmp) { 630 // TODO -- use value, not pointer equality 631 return Cmp.comparePointers(Cexpr, E->Cexpr); 632 } 633 634 private: 635 const ValueType ValType; 636 const clang::Expr *Cexpr; 637 }; 638 639 640 // Derived class for literal values, which stores the actual value. 641 template<class T> 642 class LiteralT : public Literal { 643 public: 644 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { } 645 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { } 646 647 T value() const { return Val;} 648 T& value() { return Val; } 649 650 private: 651 T Val; 652 }; 653 654 655 656 template <class V> 657 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 658 if (Cexpr) 659 return Vs.reduceLiteral(*this); 660 661 switch (ValType.Base) { 662 case ValueType::BT_Void: 663 break; 664 case ValueType::BT_Bool: 665 return Vs.reduceLiteralT(as<bool>()); 666 case ValueType::BT_Int: { 667 switch (ValType.Size) { 668 case ValueType::ST_8: 669 if (ValType.Signed) 670 return Vs.reduceLiteralT(as<int8_t>()); 671 else 672 return Vs.reduceLiteralT(as<uint8_t>()); 673 case ValueType::ST_16: 674 if (ValType.Signed) 675 return Vs.reduceLiteralT(as<int16_t>()); 676 else 677 return Vs.reduceLiteralT(as<uint16_t>()); 678 case ValueType::ST_32: 679 if (ValType.Signed) 680 return Vs.reduceLiteralT(as<int32_t>()); 681 else 682 return Vs.reduceLiteralT(as<uint32_t>()); 683 case ValueType::ST_64: 684 if (ValType.Signed) 685 return Vs.reduceLiteralT(as<int64_t>()); 686 else 687 return Vs.reduceLiteralT(as<uint64_t>()); 688 default: 689 break; 690 } 691 } 692 case ValueType::BT_Float: { 693 switch (ValType.Size) { 694 case ValueType::ST_32: 695 return Vs.reduceLiteralT(as<float>()); 696 case ValueType::ST_64: 697 return Vs.reduceLiteralT(as<double>()); 698 default: 699 break; 700 } 701 } 702 case ValueType::BT_String: 703 return Vs.reduceLiteralT(as<StringRef>()); 704 case ValueType::BT_Pointer: 705 return Vs.reduceLiteralT(as<void*>()); 706 case ValueType::BT_ValueRef: 707 break; 708 } 709 return Vs.reduceLiteral(*this); 710 } 711 712 713 // Literal pointer to an object allocated in memory. 714 // At compile time, pointer literals are represented by symbolic names. 715 class LiteralPtr : public SExpr { 716 public: 717 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 718 719 LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 720 LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} 721 722 // The clang declaration for the value that this pointer points to. 723 const clang::ValueDecl *clangDecl() const { return Cvdecl; } 724 725 template <class V> 726 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 727 return Vs.reduceLiteralPtr(*this); 728 } 729 730 template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) { 731 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 732 } 733 734 private: 735 const clang::ValueDecl *Cvdecl; 736 }; 737 738 739 // A function -- a.k.a. lambda abstraction. 740 // Functions with multiple arguments are created by currying, 741 // e.g. (function (x: Int) (function (y: Int) (add x y))) 742 class Function : public SExpr { 743 public: 744 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 745 746 Function(Variable *Vd, SExpr *Bd) 747 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 748 Vd->setKind(Variable::VK_Fun); 749 } 750 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 751 : SExpr(F), VarDecl(Vd), Body(Bd) { 752 Vd->setKind(Variable::VK_Fun); 753 } 754 755 Variable *variableDecl() { return VarDecl; } 756 const Variable *variableDecl() const { return VarDecl; } 757 758 SExpr *body() { return Body.get(); } 759 const SExpr *body() const { return Body.get(); } 760 761 template <class V> 762 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 763 // This is a variable declaration, so traverse the definition. 764 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 765 // Tell the rewriter to enter the scope of the function. 766 Variable *Nvd = Vs.enterScope(*VarDecl, E0); 767 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 768 Vs.exitScope(*VarDecl); 769 return Vs.reduceFunction(*this, Nvd, E1); 770 } 771 772 template <class C> typename C::CType compare(Function* E, C& Cmp) { 773 typename C::CType Ct = 774 Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 775 if (Cmp.notTrue(Ct)) 776 return Ct; 777 Cmp.enterScope(variableDecl(), E->variableDecl()); 778 Ct = Cmp.compare(body(), E->body()); 779 Cmp.leaveScope(); 780 return Ct; 781 } 782 783 private: 784 Variable *VarDecl; 785 SExprRef Body; 786 }; 787 788 789 // A self-applicable function. 790 // A self-applicable function can be applied to itself. It's useful for 791 // implementing objects and late binding 792 class SFunction : public SExpr { 793 public: 794 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 795 796 SFunction(Variable *Vd, SExpr *B) 797 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 798 assert(Vd->Definition == nullptr); 799 Vd->setKind(Variable::VK_SFun); 800 Vd->Definition.reset(this); 801 } 802 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 803 : SExpr(F), VarDecl(Vd), Body(B) { 804 assert(Vd->Definition == nullptr); 805 Vd->setKind(Variable::VK_SFun); 806 Vd->Definition.reset(this); 807 } 808 809 Variable *variableDecl() { return VarDecl; } 810 const Variable *variableDecl() const { return VarDecl; } 811 812 SExpr *body() { return Body.get(); } 813 const SExpr *body() const { return Body.get(); } 814 815 template <class V> 816 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 817 // A self-variable points to the SFunction itself. 818 // A rewrite must introduce the variable with a null definition, and update 819 // it after 'this' has been rewritten. 820 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 821 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 822 Vs.exitScope(*VarDecl); 823 // A rewrite operation will call SFun constructor to set Vvd->Definition. 824 return Vs.reduceSFunction(*this, Nvd, E1); 825 } 826 827 template <class C> typename C::CType compare(SFunction* E, C& Cmp) { 828 Cmp.enterScope(variableDecl(), E->variableDecl()); 829 typename C::CType Ct = Cmp.compare(body(), E->body()); 830 Cmp.leaveScope(); 831 return Ct; 832 } 833 834 private: 835 Variable *VarDecl; 836 SExprRef Body; 837 }; 838 839 840 // A block of code -- e.g. the body of a function. 841 class Code : public SExpr { 842 public: 843 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 844 845 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 846 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 847 : SExpr(C), ReturnType(T), Body(B) {} 848 849 SExpr *returnType() { return ReturnType.get(); } 850 const SExpr *returnType() const { return ReturnType.get(); } 851 852 SExpr *body() { return Body.get(); } 853 const SExpr *body() const { return Body.get(); } 854 855 template <class V> 856 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 857 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 858 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 859 return Vs.reduceCode(*this, Nt, Nb); 860 } 861 862 template <class C> typename C::CType compare(Code* E, C& Cmp) { 863 typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 864 if (Cmp.notTrue(Ct)) 865 return Ct; 866 return Cmp.compare(body(), E->body()); 867 } 868 869 private: 870 SExprRef ReturnType; 871 SExprRef Body; 872 }; 873 874 875 // A typed, writable location in memory 876 class Field : public SExpr { 877 public: 878 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 879 880 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 881 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 882 : SExpr(C), Range(R), Body(B) {} 883 884 SExpr *range() { return Range.get(); } 885 const SExpr *range() const { return Range.get(); } 886 887 SExpr *body() { return Body.get(); } 888 const SExpr *body() const { return Body.get(); } 889 890 template <class V> 891 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 892 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 893 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 894 return Vs.reduceField(*this, Nr, Nb); 895 } 896 897 template <class C> typename C::CType compare(Field* E, C& Cmp) { 898 typename C::CType Ct = Cmp.compare(range(), E->range()); 899 if (Cmp.notTrue(Ct)) 900 return Ct; 901 return Cmp.compare(body(), E->body()); 902 } 903 904 private: 905 SExprRef Range; 906 SExprRef Body; 907 }; 908 909 910 // Apply an argument to a function 911 class Apply : public SExpr { 912 public: 913 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 914 915 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 916 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 917 : SExpr(A), Fun(F), Arg(Ar) 918 {} 919 920 SExpr *fun() { return Fun.get(); } 921 const SExpr *fun() const { return Fun.get(); } 922 923 SExpr *arg() { return Arg.get(); } 924 const SExpr *arg() const { return Arg.get(); } 925 926 template <class V> 927 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 928 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 929 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 930 return Vs.reduceApply(*this, Nf, Na); 931 } 932 933 template <class C> typename C::CType compare(Apply* E, C& Cmp) { 934 typename C::CType Ct = Cmp.compare(fun(), E->fun()); 935 if (Cmp.notTrue(Ct)) 936 return Ct; 937 return Cmp.compare(arg(), E->arg()); 938 } 939 940 private: 941 SExprRef Fun; 942 SExprRef Arg; 943 }; 944 945 946 // Apply a self-argument to a self-applicable function 947 class SApply : public SExpr { 948 public: 949 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 950 951 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} 952 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor 953 : SExpr(A), Sfun(Sf), Arg(Ar) {} 954 955 SExpr *sfun() { return Sfun.get(); } 956 const SExpr *sfun() const { return Sfun.get(); } 957 958 SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); } 959 const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); } 960 961 bool isDelegation() const { return Arg == nullptr; } 962 963 template <class V> 964 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 965 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 966 typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 967 : nullptr; 968 return Vs.reduceSApply(*this, Nf, Na); 969 } 970 971 template <class C> typename C::CType compare(SApply* E, C& Cmp) { 972 typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 973 if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 974 return Ct; 975 return Cmp.compare(arg(), E->arg()); 976 } 977 978 private: 979 SExprRef Sfun; 980 SExprRef Arg; 981 }; 982 983 984 // Project a named slot from a C++ struct or class. 985 class Project : public SExpr { 986 public: 987 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 988 989 Project(SExpr *R, StringRef SName) 990 : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr) 991 { } 992 Project(SExpr *R, clang::ValueDecl *Cvd) 993 : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd) 994 { } 995 Project(const Project &P, SExpr *R) 996 : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl) 997 { } 998 999 SExpr *record() { return Rec.get(); } 1000 const SExpr *record() const { return Rec.get(); } 1001 1002 const clang::ValueDecl *clangValueDecl() const { return Cvdecl; } 1003 1004 StringRef slotName() const { 1005 if (Cvdecl) 1006 return Cvdecl->getName(); 1007 else 1008 return SlotName; 1009 } 1010 1011 template <class V> 1012 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1013 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 1014 return Vs.reduceProject(*this, Nr); 1015 } 1016 1017 template <class C> typename C::CType compare(Project* E, C& Cmp) { 1018 typename C::CType Ct = Cmp.compare(record(), E->record()); 1019 if (Cmp.notTrue(Ct)) 1020 return Ct; 1021 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 1022 } 1023 1024 private: 1025 SExprRef Rec; 1026 StringRef SlotName; 1027 clang::ValueDecl *Cvdecl; 1028 }; 1029 1030 1031 // Call a function (after all arguments have been applied). 1032 class Call : public SExpr { 1033 public: 1034 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 1035 1036 Call(SExpr *T, const clang::CallExpr *Ce = nullptr) 1037 : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 1038 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 1039 1040 SExpr *target() { return Target.get(); } 1041 const SExpr *target() const { return Target.get(); } 1042 1043 const clang::CallExpr *clangCallExpr() const { return Cexpr; } 1044 1045 template <class V> 1046 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1047 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 1048 return Vs.reduceCall(*this, Nt); 1049 } 1050 1051 template <class C> typename C::CType compare(Call* E, C& Cmp) { 1052 return Cmp.compare(target(), E->target()); 1053 } 1054 1055 private: 1056 SExprRef Target; 1057 const clang::CallExpr *Cexpr; 1058 }; 1059 1060 1061 // Allocate memory for a new value on the heap or stack. 1062 class Alloc : public SExpr { 1063 public: 1064 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 1065 1066 enum AllocKind { 1067 AK_Stack, 1068 AK_Heap 1069 }; 1070 1071 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 1072 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 1073 1074 AllocKind kind() const { return static_cast<AllocKind>(Flags); } 1075 1076 SExpr *dataType() { return Dtype.get(); } 1077 const SExpr *dataType() const { return Dtype.get(); } 1078 1079 template <class V> 1080 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1081 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); 1082 return Vs.reduceAlloc(*this, Nd); 1083 } 1084 1085 template <class C> typename C::CType compare(Alloc* E, C& Cmp) { 1086 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); 1087 if (Cmp.notTrue(Ct)) 1088 return Ct; 1089 return Cmp.compare(dataType(), E->dataType()); 1090 } 1091 1092 private: 1093 SExprRef Dtype; 1094 }; 1095 1096 1097 // Load a value from memory. 1098 class Load : public SExpr { 1099 public: 1100 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 1101 1102 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 1103 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 1104 1105 SExpr *pointer() { return Ptr.get(); } 1106 const SExpr *pointer() const { return Ptr.get(); } 1107 1108 template <class V> 1109 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1110 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1111 return Vs.reduceLoad(*this, Np); 1112 } 1113 1114 template <class C> typename C::CType compare(Load* E, C& Cmp) { 1115 return Cmp.compare(pointer(), E->pointer()); 1116 } 1117 1118 private: 1119 SExprRef Ptr; 1120 }; 1121 1122 1123 // Store a value to memory. 1124 // Source is a pointer, destination is the value to store. 1125 class Store : public SExpr { 1126 public: 1127 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 1128 1129 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 1130 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 1131 1132 SExpr *destination() { return Dest.get(); } // Address to store to 1133 const SExpr *destination() const { return Dest.get(); } 1134 1135 SExpr *source() { return Source.get(); } // Value to store 1136 const SExpr *source() const { return Source.get(); } 1137 1138 template <class V> 1139 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1140 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1141 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1142 return Vs.reduceStore(*this, Np, Nv); 1143 } 1144 1145 template <class C> typename C::CType compare(Store* E, C& Cmp) { 1146 typename C::CType Ct = Cmp.compare(destination(), E->destination()); 1147 if (Cmp.notTrue(Ct)) 1148 return Ct; 1149 return Cmp.compare(source(), E->source()); 1150 } 1151 1152 private: 1153 SExprRef Dest; 1154 SExprRef Source; 1155 }; 1156 1157 1158 // If p is a reference to an array, then first(p) is a reference to the first 1159 // element. The usual array notation p[i] becomes first(p + i). 1160 class ArrayIndex : public SExpr { 1161 public: 1162 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 1163 1164 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1165 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1166 : SExpr(E), Array(A), Index(N) {} 1167 1168 SExpr *array() { return Array.get(); } 1169 const SExpr *array() const { return Array.get(); } 1170 1171 SExpr *index() { return Index.get(); } 1172 const SExpr *index() const { return Index.get(); } 1173 1174 template <class V> 1175 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1176 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1177 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1178 return Vs.reduceArrayIndex(*this, Na, Ni); 1179 } 1180 1181 template <class C> typename C::CType compare(ArrayIndex* E, C& Cmp) { 1182 typename C::CType Ct = Cmp.compare(array(), E->array()); 1183 if (Cmp.notTrue(Ct)) 1184 return Ct; 1185 return Cmp.compare(index(), E->index()); 1186 } 1187 1188 private: 1189 SExprRef Array; 1190 SExprRef Index; 1191 }; 1192 1193 1194 // Pointer arithmetic, restricted to arrays only. 1195 // If p is a reference to an array, then p + n, where n is an integer, is 1196 // a reference to a subarray. 1197 class ArrayAdd : public SExpr { 1198 public: 1199 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 1200 1201 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 1202 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 1203 : SExpr(E), Array(A), Index(N) {} 1204 1205 SExpr *array() { return Array.get(); } 1206 const SExpr *array() const { return Array.get(); } 1207 1208 SExpr *index() { return Index.get(); } 1209 const SExpr *index() const { return Index.get(); } 1210 1211 template <class V> 1212 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1213 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1214 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1215 return Vs.reduceArrayAdd(*this, Na, Ni); 1216 } 1217 1218 template <class C> typename C::CType compare(ArrayAdd* E, C& Cmp) { 1219 typename C::CType Ct = Cmp.compare(array(), E->array()); 1220 if (Cmp.notTrue(Ct)) 1221 return Ct; 1222 return Cmp.compare(index(), E->index()); 1223 } 1224 1225 private: 1226 SExprRef Array; 1227 SExprRef Index; 1228 }; 1229 1230 1231 // Simple unary operation -- e.g. !, ~, etc. 1232 class UnaryOp : public SExpr { 1233 public: 1234 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 1235 1236 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 1237 Flags = Op; 1238 } 1239 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 1240 1241 TIL_UnaryOpcode unaryOpcode() const { 1242 return static_cast<TIL_UnaryOpcode>(Flags); 1243 } 1244 1245 SExpr *expr() { return Expr0.get(); } 1246 const SExpr *expr() const { return Expr0.get(); } 1247 1248 template <class V> 1249 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1250 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1251 return Vs.reduceUnaryOp(*this, Ne); 1252 } 1253 1254 template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) { 1255 typename C::CType Ct = 1256 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 1257 if (Cmp.notTrue(Ct)) 1258 return Ct; 1259 return Cmp.compare(expr(), E->expr()); 1260 } 1261 1262 private: 1263 SExprRef Expr0; 1264 }; 1265 1266 1267 // Simple binary operation -- e.g. +, -, etc. 1268 class BinaryOp : public SExpr { 1269 public: 1270 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 1271 1272 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 1273 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 1274 Flags = Op; 1275 } 1276 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 1277 : SExpr(B), Expr0(E0), Expr1(E1) { 1278 Flags = B.Flags; 1279 } 1280 1281 TIL_BinaryOpcode binaryOpcode() const { 1282 return static_cast<TIL_BinaryOpcode>(Flags); 1283 } 1284 1285 SExpr *expr0() { return Expr0.get(); } 1286 const SExpr *expr0() const { return Expr0.get(); } 1287 1288 SExpr *expr1() { return Expr1.get(); } 1289 const SExpr *expr1() const { return Expr1.get(); } 1290 1291 template <class V> 1292 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1293 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1294 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1295 return Vs.reduceBinaryOp(*this, Ne0, Ne1); 1296 } 1297 1298 template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) { 1299 typename C::CType Ct = 1300 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 1301 if (Cmp.notTrue(Ct)) 1302 return Ct; 1303 Ct = Cmp.compare(expr0(), E->expr0()); 1304 if (Cmp.notTrue(Ct)) 1305 return Ct; 1306 return Cmp.compare(expr1(), E->expr1()); 1307 } 1308 1309 private: 1310 SExprRef Expr0; 1311 SExprRef Expr1; 1312 }; 1313 1314 1315 // Cast expression 1316 class Cast : public SExpr { 1317 public: 1318 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 1319 1320 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 1321 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 1322 1323 TIL_CastOpcode castOpcode() const { 1324 return static_cast<TIL_CastOpcode>(Flags); 1325 } 1326 1327 SExpr *expr() { return Expr0.get(); } 1328 const SExpr *expr() const { return Expr0.get(); } 1329 1330 template <class V> 1331 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1332 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1333 return Vs.reduceCast(*this, Ne); 1334 } 1335 1336 template <class C> typename C::CType compare(Cast* E, C& Cmp) { 1337 typename C::CType Ct = 1338 Cmp.compareIntegers(castOpcode(), E->castOpcode()); 1339 if (Cmp.notTrue(Ct)) 1340 return Ct; 1341 return Cmp.compare(expr(), E->expr()); 1342 } 1343 1344 private: 1345 SExprRef Expr0; 1346 }; 1347 1348 1349 class SCFG; 1350 1351 1352 class Phi : public SExpr { 1353 public: 1354 // TODO: change to SExprRef 1355 typedef SimpleArray<SExpr *> ValArray; 1356 1357 // In minimal SSA form, all Phi nodes are MultiVal. 1358 // During conversion to SSA, incomplete Phi nodes may be introduced, which 1359 // are later determined to be SingleVal, and are thus redundant. 1360 enum Status { 1361 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1362 PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1363 PH_Incomplete // Phi node is incomplete 1364 }; 1365 1366 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 1367 1368 Phi() : SExpr(COP_Phi) {} 1369 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} 1370 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} 1371 1372 const ValArray &values() const { return Values; } 1373 ValArray &values() { return Values; } 1374 1375 Status status() const { return static_cast<Status>(Flags); } 1376 void setStatus(Status s) { Flags = s; } 1377 1378 template <class V> 1379 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1380 typename V::template Container<typename V::R_SExpr> 1381 Nvs(Vs, Values.size()); 1382 1383 for (auto *Val : Values) { 1384 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1385 } 1386 return Vs.reducePhi(*this, Nvs); 1387 } 1388 1389 template <class C> typename C::CType compare(Phi *E, C &Cmp) { 1390 // TODO: implement CFG comparisons 1391 return Cmp.comparePointers(this, E); 1392 } 1393 1394 private: 1395 ValArray Values; 1396 }; 1397 1398 1399 // A basic block is part of an SCFG, and can be treated as a function in 1400 // continuation passing style. It consists of a sequence of phi nodes, which 1401 // are "arguments" to the function, followed by a sequence of instructions. 1402 // Both arguments and instructions define new variables. It ends with a 1403 // branch or goto to another basic block in the same SCFG. 1404 class BasicBlock : public SExpr { 1405 public: 1406 typedef SimpleArray<Variable*> VarArray; 1407 typedef SimpleArray<BasicBlock*> BlockArray; 1408 1409 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } 1410 1411 explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr) 1412 : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), 1413 Parent(P), Terminator(nullptr) 1414 { } 1415 BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T) 1416 : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0), 1417 Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)), 1418 Terminator(T) 1419 { } 1420 1421 unsigned blockID() const { return BlockID; } 1422 unsigned numPredecessors() const { return Predecessors.size(); } 1423 1424 const SCFG* cfg() const { return CFGPtr; } 1425 SCFG* cfg() { return CFGPtr; } 1426 1427 const BasicBlock *parent() const { return Parent; } 1428 BasicBlock *parent() { return Parent; } 1429 1430 const VarArray &arguments() const { return Args; } 1431 VarArray &arguments() { return Args; } 1432 1433 const VarArray &instructions() const { return Instrs; } 1434 VarArray &instructions() { return Instrs; } 1435 1436 const BlockArray &predecessors() const { return Predecessors; } 1437 BlockArray &predecessors() { return Predecessors; } 1438 1439 const SExpr *terminator() const { return Terminator.get(); } 1440 SExpr *terminator() { return Terminator.get(); } 1441 1442 void setBlockID(unsigned i) { BlockID = i; } 1443 void setParent(BasicBlock *P) { Parent = P; } 1444 void setTerminator(SExpr *E) { Terminator.reset(E); } 1445 1446 // Add a new argument. V must define a phi-node. 1447 void addArgument(Variable *V) { 1448 V->setKind(Variable::VK_LetBB); 1449 Args.reserveCheck(1, Arena); 1450 Args.push_back(V); 1451 } 1452 // Add a new instruction. 1453 void addInstruction(Variable *V) { 1454 V->setKind(Variable::VK_LetBB); 1455 Instrs.reserveCheck(1, Arena); 1456 Instrs.push_back(V); 1457 } 1458 // Add a new predecessor, and return the phi-node index for it. 1459 // Will add an argument to all phi-nodes, initialized to nullptr. 1460 unsigned addPredecessor(BasicBlock *Pred); 1461 1462 // Reserve space for Nargs arguments. 1463 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } 1464 1465 // Reserve space for Nins instructions. 1466 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } 1467 1468 // Reserve space for NumPreds predecessors, including space in phi nodes. 1469 void reservePredecessors(unsigned NumPreds); 1470 1471 // Return the index of BB, or Predecessors.size if BB is not a predecessor. 1472 unsigned findPredecessorIndex(const BasicBlock *BB) const { 1473 auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB); 1474 return std::distance(Predecessors.cbegin(), I); 1475 } 1476 1477 // Set id numbers for variables. 1478 void renumberVars(); 1479 1480 template <class V> 1481 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { 1482 typename V::template Container<Variable*> Nas(Vs, Args.size()); 1483 typename V::template Container<Variable*> Nis(Vs, Instrs.size()); 1484 1485 // Entering the basic block should do any scope initialization. 1486 Vs.enterBasicBlock(*this); 1487 1488 for (auto *A : Args) { 1489 auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx)); 1490 Variable *Nvd = Vs.enterScope(*A, Ne); 1491 Nas.push_back(Nvd); 1492 } 1493 for (auto *I : Instrs) { 1494 auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx)); 1495 Variable *Nvd = Vs.enterScope(*I, Ne); 1496 Nis.push_back(Nvd); 1497 } 1498 auto Nt = Vs.traverse(Terminator, Ctx); 1499 1500 // Exiting the basic block should handle any scope cleanup. 1501 Vs.exitBasicBlock(*this); 1502 1503 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); 1504 } 1505 1506 template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) { 1507 // TODO: implement CFG comparisons 1508 return Cmp.comparePointers(this, E); 1509 } 1510 1511 private: 1512 friend class SCFG; 1513 1514 MemRegionRef Arena; 1515 1516 SCFG *CFGPtr; // The CFG that contains this block. 1517 unsigned BlockID; // unique id for this BB in the containing CFG 1518 BasicBlock *Parent; // The parent block is the enclosing lexical scope. 1519 // The parent dominates this block. 1520 BlockArray Predecessors; // Predecessor blocks in the CFG. 1521 VarArray Args; // Phi nodes. One argument per predecessor. 1522 VarArray Instrs; // Instructions. 1523 SExprRef Terminator; // Branch or Goto 1524 }; 1525 1526 1527 // An SCFG is a control-flow graph. It consists of a set of basic blocks, each 1528 // of which terminates in a branch to another basic block. There is one 1529 // entry point, and one exit point. 1530 class SCFG : public SExpr { 1531 public: 1532 typedef SimpleArray<BasicBlock *> BlockArray; 1533 typedef BlockArray::iterator iterator; 1534 typedef BlockArray::const_iterator const_iterator; 1535 1536 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } 1537 1538 SCFG(MemRegionRef A, unsigned Nblocks) 1539 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), 1540 Entry(nullptr), Exit(nullptr) { 1541 Entry = new (A) BasicBlock(A, nullptr); 1542 Exit = new (A) BasicBlock(A, Entry); 1543 auto *V = new (A) Variable(new (A) Phi()); 1544 Exit->addArgument(V); 1545 add(Entry); 1546 add(Exit); 1547 } 1548 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba 1549 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), 1550 Entry(nullptr), Exit(nullptr) { 1551 // TODO: set entry and exit! 1552 } 1553 1554 iterator begin() { return Blocks.begin(); } 1555 iterator end() { return Blocks.end(); } 1556 1557 const_iterator begin() const { return cbegin(); } 1558 const_iterator end() const { return cend(); } 1559 1560 const_iterator cbegin() const { return Blocks.cbegin(); } 1561 const_iterator cend() const { return Blocks.cend(); } 1562 1563 const BasicBlock *entry() const { return Entry; } 1564 BasicBlock *entry() { return Entry; } 1565 const BasicBlock *exit() const { return Exit; } 1566 BasicBlock *exit() { return Exit; } 1567 1568 inline void add(BasicBlock *BB) { 1569 assert(BB->CFGPtr == nullptr || BB->CFGPtr == this); 1570 BB->setBlockID(Blocks.size()); 1571 BB->CFGPtr = this; 1572 Blocks.reserveCheck(1, Arena); 1573 Blocks.push_back(BB); 1574 } 1575 1576 void setEntry(BasicBlock *BB) { Entry = BB; } 1577 void setExit(BasicBlock *BB) { Exit = BB; } 1578 1579 // Set varable ids in all blocks. 1580 void renumberVars(); 1581 1582 template <class V> 1583 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1584 Vs.enterCFG(*this); 1585 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); 1586 for (auto *B : Blocks) { 1587 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); 1588 } 1589 Vs.exitCFG(*this); 1590 return Vs.reduceSCFG(*this, Bbs); 1591 } 1592 1593 template <class C> typename C::CType compare(SCFG *E, C &Cmp) { 1594 // TODO -- implement CFG comparisons 1595 return Cmp.comparePointers(this, E); 1596 } 1597 1598 private: 1599 MemRegionRef Arena; 1600 BlockArray Blocks; 1601 BasicBlock *Entry; 1602 BasicBlock *Exit; 1603 }; 1604 1605 1606 class Goto : public SExpr { 1607 public: 1608 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1609 1610 Goto(BasicBlock *B, unsigned I) 1611 : SExpr(COP_Goto), TargetBlock(B), Index(I) {} 1612 Goto(const Goto &G, BasicBlock *B, unsigned I) 1613 : SExpr(COP_Goto), TargetBlock(B), Index(I) {} 1614 1615 const BasicBlock *targetBlock() const { return TargetBlock; } 1616 BasicBlock *targetBlock() { return TargetBlock; } 1617 1618 unsigned index() const { return Index; } 1619 1620 template <class V> 1621 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1622 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1623 return Vs.reduceGoto(*this, Ntb); 1624 } 1625 1626 template <class C> typename C::CType compare(Goto *E, C &Cmp) { 1627 // TODO -- implement CFG comparisons 1628 return Cmp.comparePointers(this, E); 1629 } 1630 1631 private: 1632 BasicBlock *TargetBlock; 1633 unsigned Index; // Index into Phi nodes of target block. 1634 }; 1635 1636 1637 class Branch : public SExpr { 1638 public: 1639 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1640 1641 Branch(SExpr *C, BasicBlock *T, BasicBlock *E, unsigned TI, unsigned EI) 1642 : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), 1643 ThenIndex(TI), ElseIndex(EI) 1644 {} 1645 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E, 1646 unsigned TI, unsigned EI) 1647 : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), 1648 ThenIndex(TI), ElseIndex(EI) 1649 {} 1650 1651 const SExpr *condition() const { return Condition; } 1652 SExpr *condition() { return Condition; } 1653 1654 const BasicBlock *thenBlock() const { return ThenBlock; } 1655 BasicBlock *thenBlock() { return ThenBlock; } 1656 1657 const BasicBlock *elseBlock() const { return ElseBlock; } 1658 BasicBlock *elseBlock() { return ElseBlock; } 1659 1660 unsigned thenIndex() const { return ThenIndex; } 1661 unsigned elseIndex() const { return ElseIndex; } 1662 1663 template <class V> 1664 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1665 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1666 BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock); 1667 BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock); 1668 return Vs.reduceBranch(*this, Nc, Ntb, Nte); 1669 } 1670 1671 template <class C> typename C::CType compare(Branch *E, C &Cmp) { 1672 // TODO -- implement CFG comparisons 1673 return Cmp.comparePointers(this, E); 1674 } 1675 1676 private: 1677 SExpr *Condition; 1678 BasicBlock *ThenBlock; 1679 BasicBlock *ElseBlock; 1680 unsigned ThenIndex; 1681 unsigned ElseIndex; 1682 }; 1683 1684 1685 // An identifier, e.g. 'foo' or 'x'. 1686 // This is a pseduo-term; it will be lowered to a variable or projection. 1687 class Identifier : public SExpr { 1688 public: 1689 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } 1690 1691 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { } 1692 Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { } 1693 1694 StringRef name() const { return Name; } 1695 1696 template <class V> 1697 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1698 return Vs.reduceIdentifier(*this); 1699 } 1700 1701 template <class C> typename C::CType compare(Identifier* E, C& Cmp) { 1702 return Cmp.compareStrings(name(), E->name()); 1703 } 1704 1705 private: 1706 StringRef Name; 1707 }; 1708 1709 1710 // An if-then-else expression. 1711 // This is a pseduo-term; it will be lowered to a branch in a CFG. 1712 class IfThenElse : public SExpr { 1713 public: 1714 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } 1715 1716 IfThenElse(SExpr *C, SExpr *T, SExpr *E) 1717 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) 1718 { } 1719 IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) 1720 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) 1721 { } 1722 1723 SExpr *condition() { return Condition.get(); } // Address to store to 1724 const SExpr *condition() const { return Condition.get(); } 1725 1726 SExpr *thenExpr() { return ThenExpr.get(); } // Value to store 1727 const SExpr *thenExpr() const { return ThenExpr.get(); } 1728 1729 SExpr *elseExpr() { return ElseExpr.get(); } // Value to store 1730 const SExpr *elseExpr() const { return ElseExpr.get(); } 1731 1732 template <class V> 1733 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1734 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1735 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); 1736 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); 1737 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); 1738 } 1739 1740 template <class C> typename C::CType compare(IfThenElse* E, C& Cmp) { 1741 typename C::CType Ct = Cmp.compare(condition(), E->condition()); 1742 if (Cmp.notTrue(Ct)) 1743 return Ct; 1744 Ct = Cmp.compare(thenExpr(), E->thenExpr()); 1745 if (Cmp.notTrue(Ct)) 1746 return Ct; 1747 return Cmp.compare(elseExpr(), E->elseExpr()); 1748 } 1749 1750 private: 1751 SExprRef Condition; 1752 SExprRef ThenExpr; 1753 SExprRef ElseExpr; 1754 }; 1755 1756 1757 // A let-expression, e.g. let x=t; u. 1758 // This is a pseduo-term; it will be lowered to instructions in a CFG. 1759 class Let : public SExpr { 1760 public: 1761 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } 1762 1763 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { 1764 Vd->setKind(Variable::VK_Let); 1765 } 1766 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { 1767 Vd->setKind(Variable::VK_Let); 1768 } 1769 1770 Variable *variableDecl() { return VarDecl; } 1771 const Variable *variableDecl() const { return VarDecl; } 1772 1773 SExpr *body() { return Body.get(); } 1774 const SExpr *body() const { return Body.get(); } 1775 1776 template <class V> 1777 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1778 // This is a variable declaration, so traverse the definition. 1779 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); 1780 // Tell the rewriter to enter the scope of the let variable. 1781 Variable *Nvd = Vs.enterScope(*VarDecl, E0); 1782 auto E1 = Vs.traverse(Body, Ctx); 1783 Vs.exitScope(*VarDecl); 1784 return Vs.reduceLet(*this, Nvd, E1); 1785 } 1786 1787 template <class C> typename C::CType compare(Let* E, C& Cmp) { 1788 typename C::CType Ct = 1789 Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 1790 if (Cmp.notTrue(Ct)) 1791 return Ct; 1792 Cmp.enterScope(variableDecl(), E->variableDecl()); 1793 Ct = Cmp.compare(body(), E->body()); 1794 Cmp.leaveScope(); 1795 return Ct; 1796 } 1797 1798 private: 1799 Variable *VarDecl; 1800 SExprRef Body; 1801 }; 1802 1803 1804 1805 SExpr *getCanonicalVal(SExpr *E); 1806 void simplifyIncompleteArg(Variable *V, til::Phi *Ph); 1807 1808 1809 } // end namespace til 1810 } // end namespace threadSafety 1811 } // end namespace clang 1812 1813 #endif // LLVM_CLANG_THREAD_SAFETY_TIL_H 1814