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