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