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/StringRef.h" 54 #include "llvm/Support/Casting.h" 55 #include "llvm/Support/raw_ostream.h" 56 #include <algorithm> 57 #include <cassert> 58 #include <cstddef> 59 #include <cstdint> 60 #include <iterator> 61 #include <optional> 62 #include <string> 63 #include <utility> 64 65 namespace clang { 66 67 class CallExpr; 68 class Expr; 69 class Stmt; 70 71 namespace threadSafety { 72 namespace til { 73 74 class BasicBlock; 75 76 /// Enum for the different distinct classes of SExpr 77 enum TIL_Opcode : unsigned char { 78 #define TIL_OPCODE_DEF(X) COP_##X, 79 #include "ThreadSafetyOps.def" 80 #undef TIL_OPCODE_DEF 81 }; 82 83 /// Opcode for unary arithmetic operations. 84 enum TIL_UnaryOpcode : unsigned char { 85 UOP_Minus, // - 86 UOP_BitNot, // ~ 87 UOP_LogicNot // ! 88 }; 89 90 /// Opcode for binary arithmetic operations. 91 enum TIL_BinaryOpcode : unsigned char { 92 BOP_Add, // + 93 BOP_Sub, // - 94 BOP_Mul, // * 95 BOP_Div, // / 96 BOP_Rem, // % 97 BOP_Shl, // << 98 BOP_Shr, // >> 99 BOP_BitAnd, // & 100 BOP_BitXor, // ^ 101 BOP_BitOr, // | 102 BOP_Eq, // == 103 BOP_Neq, // != 104 BOP_Lt, // < 105 BOP_Leq, // <= 106 BOP_Cmp, // <=> 107 BOP_LogicAnd, // && (no short-circuit) 108 BOP_LogicOr // || (no short-circuit) 109 }; 110 111 /// Opcode for cast operations. 112 enum TIL_CastOpcode : unsigned char { 113 CAST_none = 0, 114 115 // Extend precision of numeric type 116 CAST_extendNum, 117 118 // Truncate precision of numeric type 119 CAST_truncNum, 120 121 // Convert to floating point type 122 CAST_toFloat, 123 124 // Convert to integer type 125 CAST_toInt, 126 127 // Convert smart pointer to pointer (C++ only) 128 CAST_objToPtr 129 }; 130 131 const TIL_Opcode COP_Min = COP_Future; 132 const TIL_Opcode COP_Max = COP_Branch; 133 const TIL_UnaryOpcode UOP_Min = UOP_Minus; 134 const TIL_UnaryOpcode UOP_Max = UOP_LogicNot; 135 const TIL_BinaryOpcode BOP_Min = BOP_Add; 136 const TIL_BinaryOpcode BOP_Max = BOP_LogicOr; 137 const TIL_CastOpcode CAST_Min = CAST_none; 138 const TIL_CastOpcode CAST_Max = CAST_toInt; 139 140 /// Return the name of a unary opcode. 141 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); 142 143 /// Return the name of a binary opcode. 144 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); 145 146 /// ValueTypes are data types that can actually be held in registers. 147 /// All variables and expressions must have a value type. 148 /// Pointer types are further subdivided into the various heap-allocated 149 /// types, such as functions, records, etc. 150 /// Structured types that are passed by value (e.g. complex numbers) 151 /// require special handling; they use BT_ValueRef, and size ST_0. 152 struct ValueType { 153 enum BaseType : unsigned char { 154 BT_Void = 0, 155 BT_Bool, 156 BT_Int, 157 BT_Float, 158 BT_String, // String literals 159 BT_Pointer, 160 BT_ValueRef 161 }; 162 163 enum SizeType : unsigned char { 164 ST_0 = 0, 165 ST_1, 166 ST_8, 167 ST_16, 168 ST_32, 169 ST_64, 170 ST_128 171 }; 172 173 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) 174 : Base(B), Size(Sz), Signed(S), VectSize(VS) {} 175 176 inline static SizeType getSizeType(unsigned nbytes); 177 178 template <class T> 179 inline static ValueType getValueType(); 180 181 BaseType Base; 182 SizeType Size; 183 bool Signed; 184 185 // 0 for scalar, otherwise num elements in vector 186 unsigned char VectSize; 187 }; 188 189 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { 190 switch (nbytes) { 191 case 1: return ST_8; 192 case 2: return ST_16; 193 case 4: return ST_32; 194 case 8: return ST_64; 195 case 16: return ST_128; 196 default: return ST_0; 197 } 198 } 199 200 template<> 201 inline ValueType ValueType::getValueType<void>() { 202 return ValueType(BT_Void, ST_0, false, 0); 203 } 204 205 template<> 206 inline ValueType ValueType::getValueType<bool>() { 207 return ValueType(BT_Bool, ST_1, false, 0); 208 } 209 210 template<> 211 inline ValueType ValueType::getValueType<int8_t>() { 212 return ValueType(BT_Int, ST_8, true, 0); 213 } 214 215 template<> 216 inline ValueType ValueType::getValueType<uint8_t>() { 217 return ValueType(BT_Int, ST_8, false, 0); 218 } 219 220 template<> 221 inline ValueType ValueType::getValueType<int16_t>() { 222 return ValueType(BT_Int, ST_16, true, 0); 223 } 224 225 template<> 226 inline ValueType ValueType::getValueType<uint16_t>() { 227 return ValueType(BT_Int, ST_16, false, 0); 228 } 229 230 template<> 231 inline ValueType ValueType::getValueType<int32_t>() { 232 return ValueType(BT_Int, ST_32, true, 0); 233 } 234 235 template<> 236 inline ValueType ValueType::getValueType<uint32_t>() { 237 return ValueType(BT_Int, ST_32, false, 0); 238 } 239 240 template<> 241 inline ValueType ValueType::getValueType<int64_t>() { 242 return ValueType(BT_Int, ST_64, true, 0); 243 } 244 245 template<> 246 inline ValueType ValueType::getValueType<uint64_t>() { 247 return ValueType(BT_Int, ST_64, false, 0); 248 } 249 250 template<> 251 inline ValueType ValueType::getValueType<float>() { 252 return ValueType(BT_Float, ST_32, true, 0); 253 } 254 255 template<> 256 inline ValueType ValueType::getValueType<double>() { 257 return ValueType(BT_Float, ST_64, true, 0); 258 } 259 260 template<> 261 inline ValueType ValueType::getValueType<long double>() { 262 return ValueType(BT_Float, ST_128, true, 0); 263 } 264 265 template<> 266 inline ValueType ValueType::getValueType<StringRef>() { 267 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); 268 } 269 270 template<> 271 inline ValueType ValueType::getValueType<void*>() { 272 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); 273 } 274 275 /// Base class for AST nodes in the typed intermediate language. 276 class SExpr { 277 public: 278 SExpr() = delete; 279 280 TIL_Opcode opcode() const { return Opcode; } 281 282 // Subclasses of SExpr must define the following: 283 // 284 // This(const This& E, ...) { 285 // copy constructor: construct copy of E, with some additional arguments. 286 // } 287 // 288 // template <class V> 289 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 290 // traverse all subexpressions, following the traversal/rewriter interface. 291 // } 292 // 293 // template <class C> typename C::CType compare(CType* E, C& Cmp) { 294 // compare all subexpressions, following the comparator interface 295 // } 296 void *operator new(size_t S, MemRegionRef &R) { 297 return ::operator new(S, R); 298 } 299 300 /// SExpr objects must be created in an arena. 301 void *operator new(size_t) = delete; 302 303 /// SExpr objects cannot be deleted. 304 // This declaration is public to workaround a gcc bug that breaks building 305 // with REQUIRES_EH=1. 306 void operator delete(void *) = delete; 307 308 /// Returns the instruction ID for this expression. 309 /// All basic block instructions have a unique ID (i.e. virtual register). 310 unsigned id() const { return SExprID; } 311 312 /// Returns the block, if this is an instruction in a basic block, 313 /// otherwise returns null. 314 BasicBlock *block() const { return Block; } 315 316 /// Set the basic block and instruction ID for this expression. 317 void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } 318 319 protected: 320 SExpr(TIL_Opcode Op) : Opcode(Op) {} 321 SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {} 322 323 const TIL_Opcode Opcode; 324 unsigned char Reserved = 0; 325 unsigned short Flags = 0; 326 unsigned SExprID = 0; 327 BasicBlock *Block = nullptr; 328 }; 329 330 // Contains various helper functions for SExprs. 331 namespace ThreadSafetyTIL { 332 333 inline bool isTrivial(const SExpr *E) { 334 TIL_Opcode Op = E->opcode(); 335 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; 336 } 337 338 } // namespace ThreadSafetyTIL 339 340 // Nodes which declare variables 341 342 /// A named variable, e.g. "x". 343 /// 344 /// There are two distinct places in which a Variable can appear in the AST. 345 /// A variable declaration introduces a new variable, and can occur in 3 places: 346 /// Let-expressions: (Let (x = t) u) 347 /// Functions: (Function (x : t) u) 348 /// Self-applicable functions (SFunction (x) t) 349 /// 350 /// If a variable occurs in any other location, it is a reference to an existing 351 /// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't 352 /// allocate a separate AST node for variable references; a reference is just a 353 /// pointer to the original declaration. 354 class Variable : public SExpr { 355 public: 356 enum VariableKind { 357 /// Let-variable 358 VK_Let, 359 360 /// Function parameter 361 VK_Fun, 362 363 /// SFunction (self) parameter 364 VK_SFun 365 }; 366 367 Variable(StringRef s, SExpr *D = nullptr) 368 : SExpr(COP_Variable), Name(s), Definition(D) { 369 Flags = VK_Let; 370 } 371 372 Variable(SExpr *D, const ValueDecl *Cvd = nullptr) 373 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), 374 Definition(D), Cvdecl(Cvd) { 375 Flags = VK_Let; 376 } 377 378 Variable(const Variable &Vd, SExpr *D) // rewrite constructor 379 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { 380 Flags = Vd.kind(); 381 } 382 383 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } 384 385 /// Return the kind of variable (let, function param, or self) 386 VariableKind kind() const { return static_cast<VariableKind>(Flags); } 387 388 /// Return the name of the variable, if any. 389 StringRef name() const { return Name; } 390 391 /// Return the clang declaration for this variable, if any. 392 const ValueDecl *clangDecl() const { return Cvdecl; } 393 394 /// Return the definition of the variable. 395 /// For let-vars, this is the setting expression. 396 /// For function and self parameters, it is the type of the variable. 397 SExpr *definition() { return Definition; } 398 const SExpr *definition() const { return Definition; } 399 400 void setName(StringRef S) { Name = S; } 401 void setKind(VariableKind K) { Flags = K; } 402 void setDefinition(SExpr *E) { Definition = E; } 403 void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } 404 405 template <class V> 406 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 407 // This routine is only called for variable references. 408 return Vs.reduceVariableRef(this); 409 } 410 411 template <class C> 412 typename C::CType compare(const Variable* E, C& Cmp) const { 413 return Cmp.compareVariableRefs(this, E); 414 } 415 416 private: 417 friend class BasicBlock; 418 friend class Function; 419 friend class Let; 420 friend class SFunction; 421 422 // The name of the variable. 423 StringRef Name; 424 425 // The TIL type or definition. 426 SExpr *Definition; 427 428 // The clang declaration for this variable. 429 const ValueDecl *Cvdecl = nullptr; 430 }; 431 432 /// Placeholder for an expression that has not yet been created. 433 /// Used to implement lazy copy and rewriting strategies. 434 class Future : public SExpr { 435 public: 436 enum FutureStatus { 437 FS_pending, 438 FS_evaluating, 439 FS_done 440 }; 441 442 Future() : SExpr(COP_Future) {} 443 virtual ~Future() = delete; 444 445 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } 446 447 // A lazy rewriting strategy should subclass Future and override this method. 448 virtual SExpr *compute() { return nullptr; } 449 450 // Return the result of this future if it exists, otherwise return null. 451 SExpr *maybeGetResult() const { return Result; } 452 453 // Return the result of this future; forcing it if necessary. 454 SExpr *result() { 455 switch (Status) { 456 case FS_pending: 457 return force(); 458 case FS_evaluating: 459 return nullptr; // infinite loop; illegal recursion. 460 case FS_done: 461 return Result; 462 } 463 } 464 465 template <class V> 466 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 467 assert(Result && "Cannot traverse Future that has not been forced."); 468 return Vs.traverse(Result, Ctx); 469 } 470 471 template <class C> 472 typename C::CType compare(const Future* E, C& Cmp) const { 473 if (!Result || !E->Result) 474 return Cmp.comparePointers(this, E); 475 return Cmp.compare(Result, E->Result); 476 } 477 478 private: 479 SExpr* force(); 480 481 FutureStatus Status = FS_pending; 482 SExpr *Result = nullptr; 483 }; 484 485 /// Placeholder for expressions that cannot be represented in the TIL. 486 class Undefined : public SExpr { 487 public: 488 Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} 489 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} 490 491 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 492 493 template <class V> 494 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 495 return Vs.reduceUndefined(*this); 496 } 497 498 template <class C> 499 typename C::CType compare(const Undefined* E, C& Cmp) const { 500 return Cmp.trueResult(); 501 } 502 503 private: 504 const Stmt *Cstmt; 505 }; 506 507 /// Placeholder for a wildcard that matches any other expression. 508 class Wildcard : public SExpr { 509 public: 510 Wildcard() : SExpr(COP_Wildcard) {} 511 Wildcard(const Wildcard &) = default; 512 513 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 514 515 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 516 return Vs.reduceWildcard(*this); 517 } 518 519 template <class C> 520 typename C::CType compare(const Wildcard* E, C& Cmp) const { 521 return Cmp.trueResult(); 522 } 523 }; 524 525 template <class T> class LiteralT; 526 527 // Base class for literal values. 528 class Literal : public SExpr { 529 public: 530 Literal(const Expr *C) 531 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {} 532 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {} 533 Literal(const Literal &) = default; 534 535 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 536 537 // The clang expression for this literal. 538 const Expr *clangExpr() const { return Cexpr; } 539 540 ValueType valueType() const { return ValType; } 541 542 template<class T> const LiteralT<T>& as() const { 543 return *static_cast<const LiteralT<T>*>(this); 544 } 545 template<class T> LiteralT<T>& as() { 546 return *static_cast<LiteralT<T>*>(this); 547 } 548 549 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 550 551 template <class C> 552 typename C::CType compare(const Literal* E, C& Cmp) const { 553 // TODO: defer actual comparison to LiteralT 554 return Cmp.trueResult(); 555 } 556 557 private: 558 const ValueType ValType; 559 const Expr *Cexpr = nullptr; 560 }; 561 562 // Derived class for literal values, which stores the actual value. 563 template<class T> 564 class LiteralT : public Literal { 565 public: 566 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} 567 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} 568 569 T value() const { return Val;} 570 T& value() { return Val; } 571 572 private: 573 T Val; 574 }; 575 576 template <class V> 577 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 578 if (Cexpr) 579 return Vs.reduceLiteral(*this); 580 581 switch (ValType.Base) { 582 case ValueType::BT_Void: 583 break; 584 case ValueType::BT_Bool: 585 return Vs.reduceLiteralT(as<bool>()); 586 case ValueType::BT_Int: { 587 switch (ValType.Size) { 588 case ValueType::ST_8: 589 if (ValType.Signed) 590 return Vs.reduceLiteralT(as<int8_t>()); 591 else 592 return Vs.reduceLiteralT(as<uint8_t>()); 593 case ValueType::ST_16: 594 if (ValType.Signed) 595 return Vs.reduceLiteralT(as<int16_t>()); 596 else 597 return Vs.reduceLiteralT(as<uint16_t>()); 598 case ValueType::ST_32: 599 if (ValType.Signed) 600 return Vs.reduceLiteralT(as<int32_t>()); 601 else 602 return Vs.reduceLiteralT(as<uint32_t>()); 603 case ValueType::ST_64: 604 if (ValType.Signed) 605 return Vs.reduceLiteralT(as<int64_t>()); 606 else 607 return Vs.reduceLiteralT(as<uint64_t>()); 608 default: 609 break; 610 } 611 } 612 case ValueType::BT_Float: { 613 switch (ValType.Size) { 614 case ValueType::ST_32: 615 return Vs.reduceLiteralT(as<float>()); 616 case ValueType::ST_64: 617 return Vs.reduceLiteralT(as<double>()); 618 default: 619 break; 620 } 621 } 622 case ValueType::BT_String: 623 return Vs.reduceLiteralT(as<StringRef>()); 624 case ValueType::BT_Pointer: 625 return Vs.reduceLiteralT(as<void*>()); 626 case ValueType::BT_ValueRef: 627 break; 628 } 629 return Vs.reduceLiteral(*this); 630 } 631 632 /// A Literal pointer to an object allocated in memory. 633 /// At compile time, pointer literals are represented by symbolic names. 634 class LiteralPtr : public SExpr { 635 public: 636 LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 637 LiteralPtr(const LiteralPtr &) = default; 638 639 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 640 641 // The clang declaration for the value that this pointer points to. 642 const ValueDecl *clangDecl() const { return Cvdecl; } 643 void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } 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 if (!Cvdecl || !E->Cvdecl) 653 return Cmp.comparePointers(this, E); 654 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 655 } 656 657 private: 658 const ValueDecl *Cvdecl; 659 }; 660 661 /// A function -- a.k.a. lambda abstraction. 662 /// Functions with multiple arguments are created by currying, 663 /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) 664 class Function : public SExpr { 665 public: 666 Function(Variable *Vd, SExpr *Bd) 667 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 668 Vd->setKind(Variable::VK_Fun); 669 } 670 671 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 672 : SExpr(F), VarDecl(Vd), Body(Bd) { 673 Vd->setKind(Variable::VK_Fun); 674 } 675 676 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 677 678 Variable *variableDecl() { return VarDecl; } 679 const Variable *variableDecl() const { return VarDecl; } 680 681 SExpr *body() { return Body; } 682 const SExpr *body() const { return Body; } 683 684 template <class V> 685 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 686 // This is a variable declaration, so traverse the definition. 687 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 688 // Tell the rewriter to enter the scope of the function. 689 Variable *Nvd = Vs.enterScope(*VarDecl, E0); 690 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 691 Vs.exitScope(*VarDecl); 692 return Vs.reduceFunction(*this, Nvd, E1); 693 } 694 695 template <class C> 696 typename C::CType compare(const Function* E, C& Cmp) const { 697 typename C::CType Ct = 698 Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 699 if (Cmp.notTrue(Ct)) 700 return Ct; 701 Cmp.enterScope(variableDecl(), E->variableDecl()); 702 Ct = Cmp.compare(body(), E->body()); 703 Cmp.leaveScope(); 704 return Ct; 705 } 706 707 private: 708 Variable *VarDecl; 709 SExpr* Body; 710 }; 711 712 /// A self-applicable function. 713 /// A self-applicable function can be applied to itself. It's useful for 714 /// implementing objects and late binding. 715 class SFunction : public SExpr { 716 public: 717 SFunction(Variable *Vd, SExpr *B) 718 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 719 assert(Vd->Definition == nullptr); 720 Vd->setKind(Variable::VK_SFun); 721 Vd->Definition = this; 722 } 723 724 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 725 : SExpr(F), VarDecl(Vd), Body(B) { 726 assert(Vd->Definition == nullptr); 727 Vd->setKind(Variable::VK_SFun); 728 Vd->Definition = this; 729 } 730 731 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 732 733 Variable *variableDecl() { return VarDecl; } 734 const Variable *variableDecl() const { return VarDecl; } 735 736 SExpr *body() { return Body; } 737 const SExpr *body() const { return Body; } 738 739 template <class V> 740 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 741 // A self-variable points to the SFunction itself. 742 // A rewrite must introduce the variable with a null definition, and update 743 // it after 'this' has been rewritten. 744 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 745 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 746 Vs.exitScope(*VarDecl); 747 // A rewrite operation will call SFun constructor to set Vvd->Definition. 748 return Vs.reduceSFunction(*this, Nvd, E1); 749 } 750 751 template <class C> 752 typename C::CType compare(const SFunction* E, C& Cmp) const { 753 Cmp.enterScope(variableDecl(), E->variableDecl()); 754 typename C::CType Ct = Cmp.compare(body(), E->body()); 755 Cmp.leaveScope(); 756 return Ct; 757 } 758 759 private: 760 Variable *VarDecl; 761 SExpr* Body; 762 }; 763 764 /// A block of code -- e.g. the body of a function. 765 class Code : public SExpr { 766 public: 767 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 768 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 769 : SExpr(C), ReturnType(T), Body(B) {} 770 771 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 772 773 SExpr *returnType() { return ReturnType; } 774 const SExpr *returnType() const { return ReturnType; } 775 776 SExpr *body() { return Body; } 777 const SExpr *body() const { return Body; } 778 779 template <class V> 780 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 781 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 782 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 783 return Vs.reduceCode(*this, Nt, Nb); 784 } 785 786 template <class C> 787 typename C::CType compare(const Code* E, C& Cmp) const { 788 typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 789 if (Cmp.notTrue(Ct)) 790 return Ct; 791 return Cmp.compare(body(), E->body()); 792 } 793 794 private: 795 SExpr* ReturnType; 796 SExpr* Body; 797 }; 798 799 /// A typed, writable location in memory 800 class Field : public SExpr { 801 public: 802 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 803 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 804 : SExpr(C), Range(R), Body(B) {} 805 806 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 807 808 SExpr *range() { return Range; } 809 const SExpr *range() const { return Range; } 810 811 SExpr *body() { return Body; } 812 const SExpr *body() const { return Body; } 813 814 template <class V> 815 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 816 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 817 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 818 return Vs.reduceField(*this, Nr, Nb); 819 } 820 821 template <class C> 822 typename C::CType compare(const Field* E, C& Cmp) const { 823 typename C::CType Ct = Cmp.compare(range(), E->range()); 824 if (Cmp.notTrue(Ct)) 825 return Ct; 826 return Cmp.compare(body(), E->body()); 827 } 828 829 private: 830 SExpr* Range; 831 SExpr* Body; 832 }; 833 834 /// Apply an argument to a function. 835 /// Note that this does not actually call the function. Functions are curried, 836 /// so this returns a closure in which the first parameter has been applied. 837 /// Once all parameters have been applied, Call can be used to invoke the 838 /// function. 839 class Apply : public SExpr { 840 public: 841 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 842 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 843 : SExpr(A), Fun(F), Arg(Ar) {} 844 845 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 846 847 SExpr *fun() { return Fun; } 848 const SExpr *fun() const { return Fun; } 849 850 SExpr *arg() { return Arg; } 851 const SExpr *arg() const { return Arg; } 852 853 template <class V> 854 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 855 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 856 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 857 return Vs.reduceApply(*this, Nf, Na); 858 } 859 860 template <class C> 861 typename C::CType compare(const Apply* E, C& Cmp) const { 862 typename C::CType Ct = Cmp.compare(fun(), E->fun()); 863 if (Cmp.notTrue(Ct)) 864 return Ct; 865 return Cmp.compare(arg(), E->arg()); 866 } 867 868 private: 869 SExpr* Fun; 870 SExpr* Arg; 871 }; 872 873 /// Apply a self-argument to a self-applicable function. 874 class SApply : public SExpr { 875 public: 876 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} 877 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor 878 : SExpr(A), Sfun(Sf), Arg(Ar) {} 879 880 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 881 882 SExpr *sfun() { return Sfun; } 883 const SExpr *sfun() const { return Sfun; } 884 885 SExpr *arg() { return Arg ? Arg : Sfun; } 886 const SExpr *arg() const { return Arg ? Arg : Sfun; } 887 888 bool isDelegation() const { return Arg != nullptr; } 889 890 template <class V> 891 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 892 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 893 typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 894 : nullptr; 895 return Vs.reduceSApply(*this, Nf, Na); 896 } 897 898 template <class C> 899 typename C::CType compare(const SApply* E, C& Cmp) const { 900 typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 901 if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 902 return Ct; 903 return Cmp.compare(arg(), E->arg()); 904 } 905 906 private: 907 SExpr* Sfun; 908 SExpr* Arg; 909 }; 910 911 /// Project a named slot from a C++ struct or class. 912 class Project : public SExpr { 913 public: 914 Project(SExpr *R, const ValueDecl *Cvd) 915 : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { 916 assert(Cvd && "ValueDecl must not be null"); 917 } 918 919 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 920 921 SExpr *record() { return Rec; } 922 const SExpr *record() const { return Rec; } 923 924 const ValueDecl *clangDecl() const { return Cvdecl; } 925 926 bool isArrow() const { return (Flags & 0x01) != 0; } 927 928 void setArrow(bool b) { 929 if (b) Flags |= 0x01; 930 else Flags &= 0xFFFE; 931 } 932 933 StringRef slotName() const { 934 if (Cvdecl->getDeclName().isIdentifier()) 935 return Cvdecl->getName(); 936 if (!SlotName) { 937 SlotName = ""; 938 llvm::raw_string_ostream OS(*SlotName); 939 Cvdecl->printName(OS); 940 } 941 return *SlotName; 942 } 943 944 template <class V> 945 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 946 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 947 return Vs.reduceProject(*this, Nr); 948 } 949 950 template <class C> 951 typename C::CType compare(const Project* E, C& Cmp) const { 952 typename C::CType Ct = Cmp.compare(record(), E->record()); 953 if (Cmp.notTrue(Ct)) 954 return Ct; 955 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 956 } 957 958 private: 959 SExpr* Rec; 960 mutable std::optional<std::string> SlotName; 961 const ValueDecl *Cvdecl; 962 }; 963 964 /// Call a function (after all arguments have been applied). 965 class Call : public SExpr { 966 public: 967 Call(SExpr *T, const CallExpr *Ce = nullptr) 968 : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 969 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 970 971 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 972 973 SExpr *target() { return Target; } 974 const SExpr *target() const { return Target; } 975 976 const CallExpr *clangCallExpr() const { return Cexpr; } 977 978 template <class V> 979 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 980 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 981 return Vs.reduceCall(*this, Nt); 982 } 983 984 template <class C> 985 typename C::CType compare(const Call* E, C& Cmp) const { 986 return Cmp.compare(target(), E->target()); 987 } 988 989 private: 990 SExpr* Target; 991 const CallExpr *Cexpr; 992 }; 993 994 /// Allocate memory for a new value on the heap or stack. 995 class Alloc : public SExpr { 996 public: 997 enum AllocKind { 998 AK_Stack, 999 AK_Heap 1000 }; 1001 1002 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 1003 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 1004 1005 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 1006 1007 AllocKind kind() const { return static_cast<AllocKind>(Flags); } 1008 1009 SExpr *dataType() { return Dtype; } 1010 const SExpr *dataType() const { return Dtype; } 1011 1012 template <class V> 1013 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1014 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); 1015 return Vs.reduceAlloc(*this, Nd); 1016 } 1017 1018 template <class C> 1019 typename C::CType compare(const Alloc* E, C& Cmp) const { 1020 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); 1021 if (Cmp.notTrue(Ct)) 1022 return Ct; 1023 return Cmp.compare(dataType(), E->dataType()); 1024 } 1025 1026 private: 1027 SExpr* Dtype; 1028 }; 1029 1030 /// Load a value from memory. 1031 class Load : public SExpr { 1032 public: 1033 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 1034 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 1035 1036 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 1037 1038 SExpr *pointer() { return Ptr; } 1039 const SExpr *pointer() const { return Ptr; } 1040 1041 template <class V> 1042 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1043 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1044 return Vs.reduceLoad(*this, Np); 1045 } 1046 1047 template <class C> 1048 typename C::CType compare(const Load* E, C& Cmp) const { 1049 return Cmp.compare(pointer(), E->pointer()); 1050 } 1051 1052 private: 1053 SExpr* Ptr; 1054 }; 1055 1056 /// Store a value to memory. 1057 /// The destination is a pointer to a field, the source is the value to store. 1058 class Store : public SExpr { 1059 public: 1060 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 1061 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 1062 1063 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 1064 1065 SExpr *destination() { return Dest; } // Address to store to 1066 const SExpr *destination() const { return Dest; } 1067 1068 SExpr *source() { return Source; } // Value to store 1069 const SExpr *source() const { return Source; } 1070 1071 template <class V> 1072 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1073 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1074 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1075 return Vs.reduceStore(*this, Np, Nv); 1076 } 1077 1078 template <class C> 1079 typename C::CType compare(const Store* E, C& Cmp) const { 1080 typename C::CType Ct = Cmp.compare(destination(), E->destination()); 1081 if (Cmp.notTrue(Ct)) 1082 return Ct; 1083 return Cmp.compare(source(), E->source()); 1084 } 1085 1086 private: 1087 SExpr* Dest; 1088 SExpr* Source; 1089 }; 1090 1091 /// If p is a reference to an array, then p[i] is a reference to the i'th 1092 /// element of the array. 1093 class ArrayIndex : public SExpr { 1094 public: 1095 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1096 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1097 : SExpr(E), Array(A), Index(N) {} 1098 1099 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 1100 1101 SExpr *array() { return Array; } 1102 const SExpr *array() const { return Array; } 1103 1104 SExpr *index() { return Index; } 1105 const SExpr *index() const { return Index; } 1106 1107 template <class V> 1108 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1109 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1110 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1111 return Vs.reduceArrayIndex(*this, Na, Ni); 1112 } 1113 1114 template <class C> 1115 typename C::CType compare(const ArrayIndex* E, C& Cmp) const { 1116 typename C::CType Ct = Cmp.compare(array(), E->array()); 1117 if (Cmp.notTrue(Ct)) 1118 return Ct; 1119 return Cmp.compare(index(), E->index()); 1120 } 1121 1122 private: 1123 SExpr* Array; 1124 SExpr* Index; 1125 }; 1126 1127 /// Pointer arithmetic, restricted to arrays only. 1128 /// If p is a reference to an array, then p + n, where n is an integer, is 1129 /// a reference to a subarray. 1130 class ArrayAdd : public SExpr { 1131 public: 1132 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 1133 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 1134 : SExpr(E), Array(A), Index(N) {} 1135 1136 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 1137 1138 SExpr *array() { return Array; } 1139 const SExpr *array() const { return Array; } 1140 1141 SExpr *index() { return Index; } 1142 const SExpr *index() const { return Index; } 1143 1144 template <class V> 1145 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1146 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1147 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1148 return Vs.reduceArrayAdd(*this, Na, Ni); 1149 } 1150 1151 template <class C> 1152 typename C::CType compare(const ArrayAdd* E, C& Cmp) const { 1153 typename C::CType Ct = Cmp.compare(array(), E->array()); 1154 if (Cmp.notTrue(Ct)) 1155 return Ct; 1156 return Cmp.compare(index(), E->index()); 1157 } 1158 1159 private: 1160 SExpr* Array; 1161 SExpr* Index; 1162 }; 1163 1164 /// Simple arithmetic unary operations, e.g. negate and not. 1165 /// These operations have no side-effects. 1166 class UnaryOp : public SExpr { 1167 public: 1168 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 1169 Flags = Op; 1170 } 1171 1172 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 1173 1174 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 1175 1176 TIL_UnaryOpcode unaryOpcode() const { 1177 return static_cast<TIL_UnaryOpcode>(Flags); 1178 } 1179 1180 SExpr *expr() { return Expr0; } 1181 const SExpr *expr() const { return Expr0; } 1182 1183 template <class V> 1184 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1185 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1186 return Vs.reduceUnaryOp(*this, Ne); 1187 } 1188 1189 template <class C> 1190 typename C::CType compare(const UnaryOp* E, C& Cmp) const { 1191 typename C::CType Ct = 1192 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 1193 if (Cmp.notTrue(Ct)) 1194 return Ct; 1195 return Cmp.compare(expr(), E->expr()); 1196 } 1197 1198 private: 1199 SExpr* Expr0; 1200 }; 1201 1202 /// Simple arithmetic binary operations, e.g. +, -, etc. 1203 /// These operations have no side effects. 1204 class BinaryOp : public SExpr { 1205 public: 1206 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 1207 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 1208 Flags = Op; 1209 } 1210 1211 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 1212 : SExpr(B), Expr0(E0), Expr1(E1) { 1213 Flags = B.Flags; 1214 } 1215 1216 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 1217 1218 TIL_BinaryOpcode binaryOpcode() const { 1219 return static_cast<TIL_BinaryOpcode>(Flags); 1220 } 1221 1222 SExpr *expr0() { return Expr0; } 1223 const SExpr *expr0() const { return Expr0; } 1224 1225 SExpr *expr1() { return Expr1; } 1226 const SExpr *expr1() const { return Expr1; } 1227 1228 template <class V> 1229 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1230 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1231 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1232 return Vs.reduceBinaryOp(*this, Ne0, Ne1); 1233 } 1234 1235 template <class C> 1236 typename C::CType compare(const BinaryOp* E, C& Cmp) const { 1237 typename C::CType Ct = 1238 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 1239 if (Cmp.notTrue(Ct)) 1240 return Ct; 1241 Ct = Cmp.compare(expr0(), E->expr0()); 1242 if (Cmp.notTrue(Ct)) 1243 return Ct; 1244 return Cmp.compare(expr1(), E->expr1()); 1245 } 1246 1247 private: 1248 SExpr* Expr0; 1249 SExpr* Expr1; 1250 }; 1251 1252 /// Cast expressions. 1253 /// Cast expressions are essentially unary operations, but we treat them 1254 /// as a distinct AST node because they only change the type of the result. 1255 class Cast : public SExpr { 1256 public: 1257 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 1258 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 1259 1260 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 1261 1262 TIL_CastOpcode castOpcode() const { 1263 return static_cast<TIL_CastOpcode>(Flags); 1264 } 1265 1266 SExpr *expr() { return Expr0; } 1267 const SExpr *expr() const { return Expr0; } 1268 1269 template <class V> 1270 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1271 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1272 return Vs.reduceCast(*this, Ne); 1273 } 1274 1275 template <class C> 1276 typename C::CType compare(const Cast* E, C& Cmp) const { 1277 typename C::CType Ct = 1278 Cmp.compareIntegers(castOpcode(), E->castOpcode()); 1279 if (Cmp.notTrue(Ct)) 1280 return Ct; 1281 return Cmp.compare(expr(), E->expr()); 1282 } 1283 1284 private: 1285 SExpr* Expr0; 1286 }; 1287 1288 class SCFG; 1289 1290 /// Phi Node, for code in SSA form. 1291 /// Each Phi node has an array of possible values that it can take, 1292 /// depending on where control flow comes from. 1293 class Phi : public SExpr { 1294 public: 1295 using ValArray = SimpleArray<SExpr *>; 1296 1297 // In minimal SSA form, all Phi nodes are MultiVal. 1298 // During conversion to SSA, incomplete Phi nodes may be introduced, which 1299 // are later determined to be SingleVal, and are thus redundant. 1300 enum Status { 1301 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1302 PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1303 PH_Incomplete // Phi node is incomplete 1304 }; 1305 1306 Phi() : SExpr(COP_Phi) {} 1307 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} 1308 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} 1309 1310 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 1311 1312 const ValArray &values() const { return Values; } 1313 ValArray &values() { return Values; } 1314 1315 Status status() const { return static_cast<Status>(Flags); } 1316 void setStatus(Status s) { Flags = s; } 1317 1318 /// Return the clang declaration of the variable for this Phi node, if any. 1319 const ValueDecl *clangDecl() const { return Cvdecl; } 1320 1321 /// Set the clang variable associated with this Phi node. 1322 void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; } 1323 1324 template <class V> 1325 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1326 typename V::template Container<typename V::R_SExpr> 1327 Nvs(Vs, Values.size()); 1328 1329 for (const auto *Val : Values) 1330 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1331 return Vs.reducePhi(*this, Nvs); 1332 } 1333 1334 template <class C> 1335 typename C::CType compare(const Phi *E, C &Cmp) const { 1336 // TODO: implement CFG comparisons 1337 return Cmp.comparePointers(this, E); 1338 } 1339 1340 private: 1341 ValArray Values; 1342 const ValueDecl* Cvdecl = nullptr; 1343 }; 1344 1345 /// Base class for basic block terminators: Branch, Goto, and Return. 1346 class Terminator : public SExpr { 1347 protected: 1348 Terminator(TIL_Opcode Op) : SExpr(Op) {} 1349 Terminator(const SExpr &E) : SExpr(E) {} 1350 1351 public: 1352 static bool classof(const SExpr *E) { 1353 return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; 1354 } 1355 1356 /// Return the list of basic blocks that this terminator can branch to. 1357 ArrayRef<BasicBlock *> successors(); 1358 1359 ArrayRef<BasicBlock *> successors() const { 1360 return const_cast<Terminator*>(this)->successors(); 1361 } 1362 }; 1363 1364 /// Jump to another basic block. 1365 /// A goto instruction is essentially a tail-recursive call into another 1366 /// block. In addition to the block pointer, it specifies an index into the 1367 /// phi nodes of that block. The index can be used to retrieve the "arguments" 1368 /// of the call. 1369 class Goto : public Terminator { 1370 public: 1371 Goto(BasicBlock *B, unsigned I) 1372 : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1373 Goto(const Goto &G, BasicBlock *B, unsigned I) 1374 : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1375 1376 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1377 1378 const BasicBlock *targetBlock() const { return TargetBlock; } 1379 BasicBlock *targetBlock() { return TargetBlock; } 1380 1381 /// Returns the index into the 1382 unsigned index() const { return Index; } 1383 1384 /// Return the list of basic blocks that this terminator can branch to. 1385 ArrayRef<BasicBlock *> successors() { return TargetBlock; } 1386 1387 template <class V> 1388 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1389 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1390 return Vs.reduceGoto(*this, Ntb); 1391 } 1392 1393 template <class C> 1394 typename C::CType compare(const Goto *E, C &Cmp) const { 1395 // TODO: implement CFG comparisons 1396 return Cmp.comparePointers(this, E); 1397 } 1398 1399 private: 1400 BasicBlock *TargetBlock; 1401 unsigned Index; 1402 }; 1403 1404 /// A conditional branch to two other blocks. 1405 /// Note that unlike Goto, Branch does not have an index. The target blocks 1406 /// must be child-blocks, and cannot have Phi nodes. 1407 class Branch : public Terminator { 1408 public: 1409 Branch(SExpr *C, BasicBlock *T, BasicBlock *E) 1410 : Terminator(COP_Branch), Condition(C) { 1411 Branches[0] = T; 1412 Branches[1] = E; 1413 } 1414 1415 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) 1416 : Terminator(Br), Condition(C) { 1417 Branches[0] = T; 1418 Branches[1] = E; 1419 } 1420 1421 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1422 1423 const SExpr *condition() const { return Condition; } 1424 SExpr *condition() { return Condition; } 1425 1426 const BasicBlock *thenBlock() const { return Branches[0]; } 1427 BasicBlock *thenBlock() { return Branches[0]; } 1428 1429 const BasicBlock *elseBlock() const { return Branches[1]; } 1430 BasicBlock *elseBlock() { return Branches[1]; } 1431 1432 /// Return the list of basic blocks that this terminator can branch to. 1433 ArrayRef<BasicBlock *> successors() { return llvm::ArrayRef(Branches); } 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 std::nullopt; } 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 std::nullopt; 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