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 SExpr &operator=(const SExpr &) = delete; 323 324 const TIL_Opcode 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 TIL_Opcode 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 // The copy assignment operator is defined as deleted pending further 493 // motivation. 494 Undefined &operator=(const Undefined &) = delete; 495 496 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 497 498 template <class V> 499 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 500 return Vs.reduceUndefined(*this); 501 } 502 503 template <class C> 504 typename C::CType compare(const Undefined* E, C& Cmp) const { 505 return Cmp.trueResult(); 506 } 507 508 private: 509 const Stmt *Cstmt; 510 }; 511 512 /// Placeholder for a wildcard that matches any other expression. 513 class Wildcard : public SExpr { 514 public: 515 Wildcard() : SExpr(COP_Wildcard) {} 516 Wildcard(const Wildcard &) = default; 517 518 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 519 520 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 521 return Vs.reduceWildcard(*this); 522 } 523 524 template <class C> 525 typename C::CType compare(const Wildcard* E, C& Cmp) const { 526 return Cmp.trueResult(); 527 } 528 }; 529 530 template <class T> class LiteralT; 531 532 // Base class for literal values. 533 class Literal : public SExpr { 534 public: 535 Literal(const Expr *C) 536 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {} 537 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {} 538 Literal(const Literal &) = default; 539 540 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 541 542 // The clang expression for this literal. 543 const Expr *clangExpr() const { return Cexpr; } 544 545 ValueType valueType() const { return ValType; } 546 547 template<class T> const LiteralT<T>& as() const { 548 return *static_cast<const LiteralT<T>*>(this); 549 } 550 template<class T> LiteralT<T>& as() { 551 return *static_cast<LiteralT<T>*>(this); 552 } 553 554 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 555 556 template <class C> 557 typename C::CType compare(const Literal* E, C& Cmp) const { 558 // TODO: defer actual comparison to LiteralT 559 return Cmp.trueResult(); 560 } 561 562 private: 563 const ValueType ValType; 564 const Expr *Cexpr = nullptr; 565 }; 566 567 // Derived class for literal values, which stores the actual value. 568 template<class T> 569 class LiteralT : public Literal { 570 public: 571 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} 572 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} 573 574 // The copy assignment operator is defined as deleted pending further 575 // motivation. 576 LiteralT &operator=(const LiteralT<T> &) = delete; 577 578 T value() const { return Val;} 579 T& value() { return Val; } 580 581 private: 582 T Val; 583 }; 584 585 template <class V> 586 typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 587 if (Cexpr) 588 return Vs.reduceLiteral(*this); 589 590 switch (ValType.Base) { 591 case ValueType::BT_Void: 592 break; 593 case ValueType::BT_Bool: 594 return Vs.reduceLiteralT(as<bool>()); 595 case ValueType::BT_Int: { 596 switch (ValType.Size) { 597 case ValueType::ST_8: 598 if (ValType.Signed) 599 return Vs.reduceLiteralT(as<int8_t>()); 600 else 601 return Vs.reduceLiteralT(as<uint8_t>()); 602 case ValueType::ST_16: 603 if (ValType.Signed) 604 return Vs.reduceLiteralT(as<int16_t>()); 605 else 606 return Vs.reduceLiteralT(as<uint16_t>()); 607 case ValueType::ST_32: 608 if (ValType.Signed) 609 return Vs.reduceLiteralT(as<int32_t>()); 610 else 611 return Vs.reduceLiteralT(as<uint32_t>()); 612 case ValueType::ST_64: 613 if (ValType.Signed) 614 return Vs.reduceLiteralT(as<int64_t>()); 615 else 616 return Vs.reduceLiteralT(as<uint64_t>()); 617 default: 618 break; 619 } 620 } 621 case ValueType::BT_Float: { 622 switch (ValType.Size) { 623 case ValueType::ST_32: 624 return Vs.reduceLiteralT(as<float>()); 625 case ValueType::ST_64: 626 return Vs.reduceLiteralT(as<double>()); 627 default: 628 break; 629 } 630 } 631 case ValueType::BT_String: 632 return Vs.reduceLiteralT(as<StringRef>()); 633 case ValueType::BT_Pointer: 634 return Vs.reduceLiteralT(as<void*>()); 635 case ValueType::BT_ValueRef: 636 break; 637 } 638 return Vs.reduceLiteral(*this); 639 } 640 641 /// A Literal pointer to an object allocated in memory. 642 /// At compile time, pointer literals are represented by symbolic names. 643 class LiteralPtr : public SExpr { 644 public: 645 LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 646 LiteralPtr(const LiteralPtr &) = default; 647 648 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 649 650 // The clang declaration for the value that this pointer points to. 651 const ValueDecl *clangDecl() const { return Cvdecl; } 652 void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } 653 654 template <class V> 655 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 656 return Vs.reduceLiteralPtr(*this); 657 } 658 659 template <class C> 660 typename C::CType compare(const LiteralPtr* E, C& Cmp) const { 661 if (!Cvdecl || !E->Cvdecl) 662 return Cmp.comparePointers(this, E); 663 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 664 } 665 666 private: 667 const ValueDecl *Cvdecl; 668 }; 669 670 /// A function -- a.k.a. lambda abstraction. 671 /// Functions with multiple arguments are created by currying, 672 /// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) 673 class Function : public SExpr { 674 public: 675 Function(Variable *Vd, SExpr *Bd) 676 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 677 Vd->setKind(Variable::VK_Fun); 678 } 679 680 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 681 : SExpr(F), VarDecl(Vd), Body(Bd) { 682 Vd->setKind(Variable::VK_Fun); 683 } 684 685 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 686 687 Variable *variableDecl() { return VarDecl; } 688 const Variable *variableDecl() const { return VarDecl; } 689 690 SExpr *body() { return Body; } 691 const SExpr *body() const { return Body; } 692 693 template <class V> 694 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 695 // This is a variable declaration, so traverse the definition. 696 auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 697 // Tell the rewriter to enter the scope of the function. 698 Variable *Nvd = Vs.enterScope(*VarDecl, E0); 699 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 700 Vs.exitScope(*VarDecl); 701 return Vs.reduceFunction(*this, Nvd, E1); 702 } 703 704 template <class C> 705 typename C::CType compare(const Function* E, C& Cmp) const { 706 typename C::CType Ct = 707 Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 708 if (Cmp.notTrue(Ct)) 709 return Ct; 710 Cmp.enterScope(variableDecl(), E->variableDecl()); 711 Ct = Cmp.compare(body(), E->body()); 712 Cmp.leaveScope(); 713 return Ct; 714 } 715 716 private: 717 Variable *VarDecl; 718 SExpr* Body; 719 }; 720 721 /// A self-applicable function. 722 /// A self-applicable function can be applied to itself. It's useful for 723 /// implementing objects and late binding. 724 class SFunction : public SExpr { 725 public: 726 SFunction(Variable *Vd, SExpr *B) 727 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 728 assert(Vd->Definition == nullptr); 729 Vd->setKind(Variable::VK_SFun); 730 Vd->Definition = this; 731 } 732 733 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 734 : SExpr(F), VarDecl(Vd), Body(B) { 735 assert(Vd->Definition == nullptr); 736 Vd->setKind(Variable::VK_SFun); 737 Vd->Definition = this; 738 } 739 740 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 741 742 Variable *variableDecl() { return VarDecl; } 743 const Variable *variableDecl() const { return VarDecl; } 744 745 SExpr *body() { return Body; } 746 const SExpr *body() const { return Body; } 747 748 template <class V> 749 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 750 // A self-variable points to the SFunction itself. 751 // A rewrite must introduce the variable with a null definition, and update 752 // it after 'this' has been rewritten. 753 Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 754 auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 755 Vs.exitScope(*VarDecl); 756 // A rewrite operation will call SFun constructor to set Vvd->Definition. 757 return Vs.reduceSFunction(*this, Nvd, E1); 758 } 759 760 template <class C> 761 typename C::CType compare(const SFunction* E, C& Cmp) const { 762 Cmp.enterScope(variableDecl(), E->variableDecl()); 763 typename C::CType Ct = Cmp.compare(body(), E->body()); 764 Cmp.leaveScope(); 765 return Ct; 766 } 767 768 private: 769 Variable *VarDecl; 770 SExpr* Body; 771 }; 772 773 /// A block of code -- e.g. the body of a function. 774 class Code : public SExpr { 775 public: 776 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 777 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 778 : SExpr(C), ReturnType(T), Body(B) {} 779 780 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 781 782 SExpr *returnType() { return ReturnType; } 783 const SExpr *returnType() const { return ReturnType; } 784 785 SExpr *body() { return Body; } 786 const SExpr *body() const { return Body; } 787 788 template <class V> 789 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 790 auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 791 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 792 return Vs.reduceCode(*this, Nt, Nb); 793 } 794 795 template <class C> 796 typename C::CType compare(const Code* E, C& Cmp) const { 797 typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 798 if (Cmp.notTrue(Ct)) 799 return Ct; 800 return Cmp.compare(body(), E->body()); 801 } 802 803 private: 804 SExpr* ReturnType; 805 SExpr* Body; 806 }; 807 808 /// A typed, writable location in memory 809 class Field : public SExpr { 810 public: 811 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 812 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 813 : SExpr(C), Range(R), Body(B) {} 814 815 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 816 817 SExpr *range() { return Range; } 818 const SExpr *range() const { return Range; } 819 820 SExpr *body() { return Body; } 821 const SExpr *body() const { return Body; } 822 823 template <class V> 824 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 825 auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 826 auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 827 return Vs.reduceField(*this, Nr, Nb); 828 } 829 830 template <class C> 831 typename C::CType compare(const Field* E, C& Cmp) const { 832 typename C::CType Ct = Cmp.compare(range(), E->range()); 833 if (Cmp.notTrue(Ct)) 834 return Ct; 835 return Cmp.compare(body(), E->body()); 836 } 837 838 private: 839 SExpr* Range; 840 SExpr* Body; 841 }; 842 843 /// Apply an argument to a function. 844 /// Note that this does not actually call the function. Functions are curried, 845 /// so this returns a closure in which the first parameter has been applied. 846 /// Once all parameters have been applied, Call can be used to invoke the 847 /// function. 848 class Apply : public SExpr { 849 public: 850 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 851 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 852 : SExpr(A), Fun(F), Arg(Ar) {} 853 854 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 855 856 SExpr *fun() { return Fun; } 857 const SExpr *fun() const { return Fun; } 858 859 SExpr *arg() { return Arg; } 860 const SExpr *arg() const { return Arg; } 861 862 template <class V> 863 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 864 auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 865 auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 866 return Vs.reduceApply(*this, Nf, Na); 867 } 868 869 template <class C> 870 typename C::CType compare(const Apply* E, C& Cmp) const { 871 typename C::CType Ct = Cmp.compare(fun(), E->fun()); 872 if (Cmp.notTrue(Ct)) 873 return Ct; 874 return Cmp.compare(arg(), E->arg()); 875 } 876 877 private: 878 SExpr* Fun; 879 SExpr* Arg; 880 }; 881 882 /// Apply a self-argument to a self-applicable function. 883 class SApply : public SExpr { 884 public: 885 SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} 886 SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor 887 : SExpr(A), Sfun(Sf), Arg(Ar) {} 888 889 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 890 891 SExpr *sfun() { return Sfun; } 892 const SExpr *sfun() const { return Sfun; } 893 894 SExpr *arg() { return Arg ? Arg : Sfun; } 895 const SExpr *arg() const { return Arg ? Arg : Sfun; } 896 897 bool isDelegation() const { return Arg != nullptr; } 898 899 template <class V> 900 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 901 auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 902 typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 903 : nullptr; 904 return Vs.reduceSApply(*this, Nf, Na); 905 } 906 907 template <class C> 908 typename C::CType compare(const SApply* E, C& Cmp) const { 909 typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 910 if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 911 return Ct; 912 return Cmp.compare(arg(), E->arg()); 913 } 914 915 private: 916 SExpr* Sfun; 917 SExpr* Arg; 918 }; 919 920 /// Project a named slot from a C++ struct or class. 921 class Project : public SExpr { 922 public: 923 Project(SExpr *R, const ValueDecl *Cvd) 924 : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) { 925 assert(Cvd && "ValueDecl must not be null"); 926 } 927 928 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 929 930 SExpr *record() { return Rec; } 931 const SExpr *record() const { return Rec; } 932 933 const ValueDecl *clangDecl() const { return Cvdecl; } 934 935 bool isArrow() const { return (Flags & 0x01) != 0; } 936 937 void setArrow(bool b) { 938 if (b) Flags |= 0x01; 939 else Flags &= 0xFFFE; 940 } 941 942 StringRef slotName() const { 943 if (Cvdecl->getDeclName().isIdentifier()) 944 return Cvdecl->getName(); 945 if (!SlotName) { 946 SlotName = ""; 947 llvm::raw_string_ostream OS(*SlotName); 948 Cvdecl->printName(OS); 949 } 950 return *SlotName; 951 } 952 953 template <class V> 954 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 955 auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 956 return Vs.reduceProject(*this, Nr); 957 } 958 959 template <class C> 960 typename C::CType compare(const Project* E, C& Cmp) const { 961 typename C::CType Ct = Cmp.compare(record(), E->record()); 962 if (Cmp.notTrue(Ct)) 963 return Ct; 964 return Cmp.comparePointers(Cvdecl, E->Cvdecl); 965 } 966 967 private: 968 SExpr* Rec; 969 mutable std::optional<std::string> SlotName; 970 const ValueDecl *Cvdecl; 971 }; 972 973 /// Call a function (after all arguments have been applied). 974 class Call : public SExpr { 975 public: 976 Call(SExpr *T, const CallExpr *Ce = nullptr) 977 : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 978 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 979 980 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 981 982 SExpr *target() { return Target; } 983 const SExpr *target() const { return Target; } 984 985 const CallExpr *clangCallExpr() const { return Cexpr; } 986 987 template <class V> 988 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 989 auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 990 return Vs.reduceCall(*this, Nt); 991 } 992 993 template <class C> 994 typename C::CType compare(const Call* E, C& Cmp) const { 995 return Cmp.compare(target(), E->target()); 996 } 997 998 private: 999 SExpr* Target; 1000 const CallExpr *Cexpr; 1001 }; 1002 1003 /// Allocate memory for a new value on the heap or stack. 1004 class Alloc : public SExpr { 1005 public: 1006 enum AllocKind { 1007 AK_Stack, 1008 AK_Heap 1009 }; 1010 1011 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 1012 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 1013 1014 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 1015 1016 AllocKind kind() const { return static_cast<AllocKind>(Flags); } 1017 1018 SExpr *dataType() { return Dtype; } 1019 const SExpr *dataType() const { return Dtype; } 1020 1021 template <class V> 1022 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1023 auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); 1024 return Vs.reduceAlloc(*this, Nd); 1025 } 1026 1027 template <class C> 1028 typename C::CType compare(const Alloc* E, C& Cmp) const { 1029 typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); 1030 if (Cmp.notTrue(Ct)) 1031 return Ct; 1032 return Cmp.compare(dataType(), E->dataType()); 1033 } 1034 1035 private: 1036 SExpr* Dtype; 1037 }; 1038 1039 /// Load a value from memory. 1040 class Load : public SExpr { 1041 public: 1042 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 1043 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 1044 1045 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 1046 1047 SExpr *pointer() { return Ptr; } 1048 const SExpr *pointer() const { return Ptr; } 1049 1050 template <class V> 1051 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1052 auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1053 return Vs.reduceLoad(*this, Np); 1054 } 1055 1056 template <class C> 1057 typename C::CType compare(const Load* E, C& Cmp) const { 1058 return Cmp.compare(pointer(), E->pointer()); 1059 } 1060 1061 private: 1062 SExpr* Ptr; 1063 }; 1064 1065 /// Store a value to memory. 1066 /// The destination is a pointer to a field, the source is the value to store. 1067 class Store : public SExpr { 1068 public: 1069 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 1070 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 1071 1072 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 1073 1074 SExpr *destination() { return Dest; } // Address to store to 1075 const SExpr *destination() const { return Dest; } 1076 1077 SExpr *source() { return Source; } // Value to store 1078 const SExpr *source() const { return Source; } 1079 1080 template <class V> 1081 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1082 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1083 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1084 return Vs.reduceStore(*this, Np, Nv); 1085 } 1086 1087 template <class C> 1088 typename C::CType compare(const Store* E, C& Cmp) const { 1089 typename C::CType Ct = Cmp.compare(destination(), E->destination()); 1090 if (Cmp.notTrue(Ct)) 1091 return Ct; 1092 return Cmp.compare(source(), E->source()); 1093 } 1094 1095 private: 1096 SExpr* Dest; 1097 SExpr* Source; 1098 }; 1099 1100 /// If p is a reference to an array, then p[i] is a reference to the i'th 1101 /// element of the array. 1102 class ArrayIndex : public SExpr { 1103 public: 1104 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1105 ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1106 : SExpr(E), Array(A), Index(N) {} 1107 1108 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 1109 1110 SExpr *array() { return Array; } 1111 const SExpr *array() const { return Array; } 1112 1113 SExpr *index() { return Index; } 1114 const SExpr *index() const { return Index; } 1115 1116 template <class V> 1117 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1118 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1119 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1120 return Vs.reduceArrayIndex(*this, Na, Ni); 1121 } 1122 1123 template <class C> 1124 typename C::CType compare(const ArrayIndex* E, C& Cmp) const { 1125 typename C::CType Ct = Cmp.compare(array(), E->array()); 1126 if (Cmp.notTrue(Ct)) 1127 return Ct; 1128 return Cmp.compare(index(), E->index()); 1129 } 1130 1131 private: 1132 SExpr* Array; 1133 SExpr* Index; 1134 }; 1135 1136 /// Pointer arithmetic, restricted to arrays only. 1137 /// If p is a reference to an array, then p + n, where n is an integer, is 1138 /// a reference to a subarray. 1139 class ArrayAdd : public SExpr { 1140 public: 1141 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 1142 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 1143 : SExpr(E), Array(A), Index(N) {} 1144 1145 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 1146 1147 SExpr *array() { return Array; } 1148 const SExpr *array() const { return Array; } 1149 1150 SExpr *index() { return Index; } 1151 const SExpr *index() const { return Index; } 1152 1153 template <class V> 1154 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1155 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1156 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1157 return Vs.reduceArrayAdd(*this, Na, Ni); 1158 } 1159 1160 template <class C> 1161 typename C::CType compare(const ArrayAdd* E, C& Cmp) const { 1162 typename C::CType Ct = Cmp.compare(array(), E->array()); 1163 if (Cmp.notTrue(Ct)) 1164 return Ct; 1165 return Cmp.compare(index(), E->index()); 1166 } 1167 1168 private: 1169 SExpr* Array; 1170 SExpr* Index; 1171 }; 1172 1173 /// Simple arithmetic unary operations, e.g. negate and not. 1174 /// These operations have no side-effects. 1175 class UnaryOp : public SExpr { 1176 public: 1177 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 1178 Flags = Op; 1179 } 1180 1181 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 1182 1183 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 1184 1185 TIL_UnaryOpcode unaryOpcode() const { 1186 return static_cast<TIL_UnaryOpcode>(Flags); 1187 } 1188 1189 SExpr *expr() { return Expr0; } 1190 const SExpr *expr() const { return Expr0; } 1191 1192 template <class V> 1193 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1194 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1195 return Vs.reduceUnaryOp(*this, Ne); 1196 } 1197 1198 template <class C> 1199 typename C::CType compare(const UnaryOp* E, C& Cmp) const { 1200 typename C::CType Ct = 1201 Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 1202 if (Cmp.notTrue(Ct)) 1203 return Ct; 1204 return Cmp.compare(expr(), E->expr()); 1205 } 1206 1207 private: 1208 SExpr* Expr0; 1209 }; 1210 1211 /// Simple arithmetic binary operations, e.g. +, -, etc. 1212 /// These operations have no side effects. 1213 class BinaryOp : public SExpr { 1214 public: 1215 BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 1216 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 1217 Flags = Op; 1218 } 1219 1220 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 1221 : SExpr(B), Expr0(E0), Expr1(E1) { 1222 Flags = B.Flags; 1223 } 1224 1225 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 1226 1227 TIL_BinaryOpcode binaryOpcode() const { 1228 return static_cast<TIL_BinaryOpcode>(Flags); 1229 } 1230 1231 SExpr *expr0() { return Expr0; } 1232 const SExpr *expr0() const { return Expr0; } 1233 1234 SExpr *expr1() { return Expr1; } 1235 const SExpr *expr1() const { return Expr1; } 1236 1237 template <class V> 1238 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1239 auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1240 auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1241 return Vs.reduceBinaryOp(*this, Ne0, Ne1); 1242 } 1243 1244 template <class C> 1245 typename C::CType compare(const BinaryOp* E, C& Cmp) const { 1246 typename C::CType Ct = 1247 Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 1248 if (Cmp.notTrue(Ct)) 1249 return Ct; 1250 Ct = Cmp.compare(expr0(), E->expr0()); 1251 if (Cmp.notTrue(Ct)) 1252 return Ct; 1253 return Cmp.compare(expr1(), E->expr1()); 1254 } 1255 1256 private: 1257 SExpr* Expr0; 1258 SExpr* Expr1; 1259 }; 1260 1261 /// Cast expressions. 1262 /// Cast expressions are essentially unary operations, but we treat them 1263 /// as a distinct AST node because they only change the type of the result. 1264 class Cast : public SExpr { 1265 public: 1266 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 1267 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 1268 1269 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 1270 1271 TIL_CastOpcode castOpcode() const { 1272 return static_cast<TIL_CastOpcode>(Flags); 1273 } 1274 1275 SExpr *expr() { return Expr0; } 1276 const SExpr *expr() const { return Expr0; } 1277 1278 template <class V> 1279 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1280 auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1281 return Vs.reduceCast(*this, Ne); 1282 } 1283 1284 template <class C> 1285 typename C::CType compare(const Cast* E, C& Cmp) const { 1286 typename C::CType Ct = 1287 Cmp.compareIntegers(castOpcode(), E->castOpcode()); 1288 if (Cmp.notTrue(Ct)) 1289 return Ct; 1290 return Cmp.compare(expr(), E->expr()); 1291 } 1292 1293 private: 1294 SExpr* Expr0; 1295 }; 1296 1297 class SCFG; 1298 1299 /// Phi Node, for code in SSA form. 1300 /// Each Phi node has an array of possible values that it can take, 1301 /// depending on where control flow comes from. 1302 class Phi : public SExpr { 1303 public: 1304 using ValArray = SimpleArray<SExpr *>; 1305 1306 // In minimal SSA form, all Phi nodes are MultiVal. 1307 // During conversion to SSA, incomplete Phi nodes may be introduced, which 1308 // are later determined to be SingleVal, and are thus redundant. 1309 enum Status { 1310 PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1311 PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1312 PH_Incomplete // Phi node is incomplete 1313 }; 1314 1315 Phi() : SExpr(COP_Phi) {} 1316 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} 1317 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} 1318 1319 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 1320 1321 const ValArray &values() const { return Values; } 1322 ValArray &values() { return Values; } 1323 1324 Status status() const { return static_cast<Status>(Flags); } 1325 void setStatus(Status s) { Flags = s; } 1326 1327 /// Return the clang declaration of the variable for this Phi node, if any. 1328 const ValueDecl *clangDecl() const { return Cvdecl; } 1329 1330 /// Set the clang variable associated with this Phi node. 1331 void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; } 1332 1333 template <class V> 1334 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1335 typename V::template Container<typename V::R_SExpr> 1336 Nvs(Vs, Values.size()); 1337 1338 for (const auto *Val : Values) 1339 Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1340 return Vs.reducePhi(*this, Nvs); 1341 } 1342 1343 template <class C> 1344 typename C::CType compare(const Phi *E, C &Cmp) const { 1345 // TODO: implement CFG comparisons 1346 return Cmp.comparePointers(this, E); 1347 } 1348 1349 private: 1350 ValArray Values; 1351 const ValueDecl* Cvdecl = nullptr; 1352 }; 1353 1354 /// Base class for basic block terminators: Branch, Goto, and Return. 1355 class Terminator : public SExpr { 1356 protected: 1357 Terminator(TIL_Opcode Op) : SExpr(Op) {} 1358 Terminator(const SExpr &E) : SExpr(E) {} 1359 1360 public: 1361 static bool classof(const SExpr *E) { 1362 return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; 1363 } 1364 1365 /// Return the list of basic blocks that this terminator can branch to. 1366 ArrayRef<BasicBlock *> successors(); 1367 1368 ArrayRef<BasicBlock *> successors() const { 1369 return const_cast<Terminator*>(this)->successors(); 1370 } 1371 }; 1372 1373 /// Jump to another basic block. 1374 /// A goto instruction is essentially a tail-recursive call into another 1375 /// block. In addition to the block pointer, it specifies an index into the 1376 /// phi nodes of that block. The index can be used to retrieve the "arguments" 1377 /// of the call. 1378 class Goto : public Terminator { 1379 public: 1380 Goto(BasicBlock *B, unsigned I) 1381 : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1382 Goto(const Goto &G, BasicBlock *B, unsigned I) 1383 : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1384 1385 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1386 1387 const BasicBlock *targetBlock() const { return TargetBlock; } 1388 BasicBlock *targetBlock() { return TargetBlock; } 1389 1390 /// Returns the index into the 1391 unsigned index() const { return Index; } 1392 1393 /// Return the list of basic blocks that this terminator can branch to. 1394 ArrayRef<BasicBlock *> successors() { return TargetBlock; } 1395 1396 template <class V> 1397 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1398 BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1399 return Vs.reduceGoto(*this, Ntb); 1400 } 1401 1402 template <class C> 1403 typename C::CType compare(const Goto *E, C &Cmp) const { 1404 // TODO: implement CFG comparisons 1405 return Cmp.comparePointers(this, E); 1406 } 1407 1408 private: 1409 BasicBlock *TargetBlock; 1410 unsigned Index; 1411 }; 1412 1413 /// A conditional branch to two other blocks. 1414 /// Note that unlike Goto, Branch does not have an index. The target blocks 1415 /// must be child-blocks, and cannot have Phi nodes. 1416 class Branch : public Terminator { 1417 public: 1418 Branch(SExpr *C, BasicBlock *T, BasicBlock *E) 1419 : Terminator(COP_Branch), Condition(C) { 1420 Branches[0] = T; 1421 Branches[1] = E; 1422 } 1423 1424 Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) 1425 : Terminator(Br), Condition(C) { 1426 Branches[0] = T; 1427 Branches[1] = E; 1428 } 1429 1430 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1431 1432 const SExpr *condition() const { return Condition; } 1433 SExpr *condition() { return Condition; } 1434 1435 const BasicBlock *thenBlock() const { return Branches[0]; } 1436 BasicBlock *thenBlock() { return Branches[0]; } 1437 1438 const BasicBlock *elseBlock() const { return Branches[1]; } 1439 BasicBlock *elseBlock() { return Branches[1]; } 1440 1441 /// Return the list of basic blocks that this terminator can branch to. 1442 ArrayRef<BasicBlock *> successors() { return llvm::ArrayRef(Branches); } 1443 1444 template <class V> 1445 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1446 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1447 BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); 1448 BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); 1449 return Vs.reduceBranch(*this, Nc, Ntb, Nte); 1450 } 1451 1452 template <class C> 1453 typename C::CType compare(const Branch *E, C &Cmp) const { 1454 // TODO: implement CFG comparisons 1455 return Cmp.comparePointers(this, E); 1456 } 1457 1458 private: 1459 SExpr *Condition; 1460 BasicBlock *Branches[2]; 1461 }; 1462 1463 /// Return from the enclosing function, passing the return value to the caller. 1464 /// Only the exit block should end with a return statement. 1465 class Return : public Terminator { 1466 public: 1467 Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} 1468 Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} 1469 1470 static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } 1471 1472 /// Return an empty list. 1473 ArrayRef<BasicBlock *> successors() { return std::nullopt; } 1474 1475 SExpr *returnValue() { return Retval; } 1476 const SExpr *returnValue() const { return Retval; } 1477 1478 template <class V> 1479 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1480 auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); 1481 return Vs.reduceReturn(*this, Ne); 1482 } 1483 1484 template <class C> 1485 typename C::CType compare(const Return *E, C &Cmp) const { 1486 return Cmp.compare(Retval, E->Retval); 1487 } 1488 1489 private: 1490 SExpr* Retval; 1491 }; 1492 1493 inline ArrayRef<BasicBlock*> Terminator::successors() { 1494 switch (opcode()) { 1495 case COP_Goto: return cast<Goto>(this)->successors(); 1496 case COP_Branch: return cast<Branch>(this)->successors(); 1497 case COP_Return: return cast<Return>(this)->successors(); 1498 default: 1499 return std::nullopt; 1500 } 1501 } 1502 1503 /// A basic block is part of an SCFG. It can be treated as a function in 1504 /// continuation passing style. A block consists of a sequence of phi nodes, 1505 /// which are "arguments" to the function, followed by a sequence of 1506 /// instructions. It ends with a Terminator, which is a Branch or Goto to 1507 /// another basic block in the same SCFG. 1508 class BasicBlock : public SExpr { 1509 public: 1510 using InstrArray = SimpleArray<SExpr *>; 1511 using BlockArray = SimpleArray<BasicBlock *>; 1512 1513 // TopologyNodes are used to overlay tree structures on top of the CFG, 1514 // such as dominator and postdominator trees. Each block is assigned an 1515 // ID in the tree according to a depth-first search. Tree traversals are 1516 // always up, towards the parents. 1517 struct TopologyNode { 1518 int NodeID = 0; 1519 1520 // Includes this node, so must be > 1. 1521 int SizeOfSubTree = 0; 1522 1523 // Pointer to parent. 1524 BasicBlock *Parent = nullptr; 1525 1526 TopologyNode() = default; 1527 1528 bool isParentOf(const TopologyNode& OtherNode) { 1529 return OtherNode.NodeID > NodeID && 1530 OtherNode.NodeID < NodeID + SizeOfSubTree; 1531 } 1532 1533 bool isParentOfOrEqual(const TopologyNode& OtherNode) { 1534 return OtherNode.NodeID >= NodeID && 1535 OtherNode.NodeID < NodeID + SizeOfSubTree; 1536 } 1537 }; 1538 1539 explicit BasicBlock(MemRegionRef A) 1540 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {} 1541 BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, 1542 Terminator *T) 1543 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false), 1544 Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} 1545 1546 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } 1547 1548 /// Returns the block ID. Every block has a unique ID in the CFG. 1549 int blockID() const { return BlockID; } 1550 1551 /// Returns the number of predecessors. 1552 size_t numPredecessors() const { return Predecessors.size(); } 1553 size_t numSuccessors() const { return successors().size(); } 1554 1555 const SCFG* cfg() const { return CFGPtr; } 1556 SCFG* cfg() { return CFGPtr; } 1557 1558 const BasicBlock *parent() const { return DominatorNode.Parent; } 1559 BasicBlock *parent() { return DominatorNode.Parent; } 1560 1561 const InstrArray &arguments() const { return Args; } 1562 InstrArray &arguments() { return Args; } 1563 1564 InstrArray &instructions() { return Instrs; } 1565 const InstrArray &instructions() const { return Instrs; } 1566 1567 /// Returns a list of predecessors. 1568 /// The order of predecessors in the list is important; each phi node has 1569 /// exactly one argument for each precessor, in the same order. 1570 BlockArray &predecessors() { return Predecessors; } 1571 const BlockArray &predecessors() const { return Predecessors; } 1572 1573 ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } 1574 ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } 1575 1576 const Terminator *terminator() const { return TermInstr; } 1577 Terminator *terminator() { return TermInstr; } 1578 1579 void setTerminator(Terminator *E) { TermInstr = E; } 1580 1581 bool Dominates(const BasicBlock &Other) { 1582 return DominatorNode.isParentOfOrEqual(Other.DominatorNode); 1583 } 1584 1585 bool PostDominates(const BasicBlock &Other) { 1586 return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); 1587 } 1588 1589 /// Add a new argument. 1590 void addArgument(Phi *V) { 1591 Args.reserveCheck(1, Arena); 1592 Args.push_back(V); 1593 } 1594 1595 /// Add a new instruction. 1596 void addInstruction(SExpr *V) { 1597 Instrs.reserveCheck(1, Arena); 1598 Instrs.push_back(V); 1599 } 1600 1601 // Add a new predecessor, and return the phi-node index for it. 1602 // Will add an argument to all phi-nodes, initialized to nullptr. 1603 unsigned addPredecessor(BasicBlock *Pred); 1604 1605 // Reserve space for Nargs arguments. 1606 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } 1607 1608 // Reserve space for Nins instructions. 1609 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } 1610 1611 // Reserve space for NumPreds predecessors, including space in phi nodes. 1612 void reservePredecessors(unsigned NumPreds); 1613 1614 /// Return the index of BB, or Predecessors.size if BB is not a predecessor. 1615 unsigned findPredecessorIndex(const BasicBlock *BB) const { 1616 auto I = llvm::find(Predecessors, BB); 1617 return std::distance(Predecessors.cbegin(), I); 1618 } 1619 1620 template <class V> 1621 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { 1622 typename V::template Container<SExpr*> Nas(Vs, Args.size()); 1623 typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); 1624 1625 // Entering the basic block should do any scope initialization. 1626 Vs.enterBasicBlock(*this); 1627 1628 for (const auto *E : Args) { 1629 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1630 Nas.push_back(Ne); 1631 } 1632 for (const auto *E : Instrs) { 1633 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1634 Nis.push_back(Ne); 1635 } 1636 auto Nt = Vs.traverse(TermInstr, Ctx); 1637 1638 // Exiting the basic block should handle any scope cleanup. 1639 Vs.exitBasicBlock(*this); 1640 1641 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); 1642 } 1643 1644 template <class C> 1645 typename C::CType compare(const BasicBlock *E, C &Cmp) const { 1646 // TODO: implement CFG comparisons 1647 return Cmp.comparePointers(this, E); 1648 } 1649 1650 private: 1651 friend class SCFG; 1652 1653 // assign unique ids to all instructions 1654 unsigned renumberInstrs(unsigned id); 1655 1656 unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); 1657 unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID); 1658 void computeDominator(); 1659 void computePostDominator(); 1660 1661 // The arena used to allocate this block. 1662 MemRegionRef Arena; 1663 1664 // The CFG that contains this block. 1665 SCFG *CFGPtr = nullptr; 1666 1667 // Unique ID for this BB in the containing CFG. IDs are in topological order. 1668 unsigned BlockID : 31; 1669 1670 // Bit to determine if a block has been visited during a traversal. 1671 bool Visited : 1; 1672 1673 // Predecessor blocks in the CFG. 1674 BlockArray Predecessors; 1675 1676 // Phi nodes. One argument per predecessor. 1677 InstrArray Args; 1678 1679 // Instructions. 1680 InstrArray Instrs; 1681 1682 // Terminating instruction. 1683 Terminator *TermInstr = nullptr; 1684 1685 // The dominator tree. 1686 TopologyNode DominatorNode; 1687 1688 // The post-dominator tree. 1689 TopologyNode PostDominatorNode; 1690 }; 1691 1692 /// An SCFG is a control-flow graph. It consists of a set of basic blocks, 1693 /// each of which terminates in a branch to another basic block. There is one 1694 /// entry point, and one exit point. 1695 class SCFG : public SExpr { 1696 public: 1697 using BlockArray = SimpleArray<BasicBlock *>; 1698 using iterator = BlockArray::iterator; 1699 using const_iterator = BlockArray::const_iterator; 1700 1701 SCFG(MemRegionRef A, unsigned Nblocks) 1702 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) { 1703 Entry = new (A) BasicBlock(A); 1704 Exit = new (A) BasicBlock(A); 1705 auto *V = new (A) Phi(); 1706 Exit->addArgument(V); 1707 Exit->setTerminator(new (A) Return(V)); 1708 add(Entry); 1709 add(Exit); 1710 } 1711 1712 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba 1713 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) { 1714 // TODO: set entry and exit! 1715 } 1716 1717 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } 1718 1719 /// Return true if this CFG is valid. 1720 bool valid() const { return Entry && Exit && Blocks.size() > 0; } 1721 1722 /// Return true if this CFG has been normalized. 1723 /// After normalization, blocks are in topological order, and block and 1724 /// instruction IDs have been assigned. 1725 bool normal() const { return Normal; } 1726 1727 iterator begin() { return Blocks.begin(); } 1728 iterator end() { return Blocks.end(); } 1729 1730 const_iterator begin() const { return cbegin(); } 1731 const_iterator end() const { return cend(); } 1732 1733 const_iterator cbegin() const { return Blocks.cbegin(); } 1734 const_iterator cend() const { return Blocks.cend(); } 1735 1736 const BasicBlock *entry() const { return Entry; } 1737 BasicBlock *entry() { return Entry; } 1738 const BasicBlock *exit() const { return Exit; } 1739 BasicBlock *exit() { return Exit; } 1740 1741 /// Return the number of blocks in the CFG. 1742 /// Block::blockID() will return a number less than numBlocks(); 1743 size_t numBlocks() const { return Blocks.size(); } 1744 1745 /// Return the total number of instructions in the CFG. 1746 /// This is useful for building instruction side-tables; 1747 /// A call to SExpr::id() will return a number less than numInstructions(). 1748 unsigned numInstructions() { return NumInstructions; } 1749 1750 inline void add(BasicBlock *BB) { 1751 assert(BB->CFGPtr == nullptr); 1752 BB->CFGPtr = this; 1753 Blocks.reserveCheck(1, Arena); 1754 Blocks.push_back(BB); 1755 } 1756 1757 void setEntry(BasicBlock *BB) { Entry = BB; } 1758 void setExit(BasicBlock *BB) { Exit = BB; } 1759 1760 void computeNormalForm(); 1761 1762 template <class V> 1763 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1764 Vs.enterCFG(*this); 1765 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); 1766 1767 for (const auto *B : Blocks) { 1768 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); 1769 } 1770 Vs.exitCFG(*this); 1771 return Vs.reduceSCFG(*this, Bbs); 1772 } 1773 1774 template <class C> 1775 typename C::CType compare(const SCFG *E, C &Cmp) const { 1776 // TODO: implement CFG comparisons 1777 return Cmp.comparePointers(this, E); 1778 } 1779 1780 private: 1781 // assign unique ids to all instructions 1782 void renumberInstrs(); 1783 1784 MemRegionRef Arena; 1785 BlockArray Blocks; 1786 BasicBlock *Entry = nullptr; 1787 BasicBlock *Exit = nullptr; 1788 unsigned NumInstructions = 0; 1789 bool Normal = false; 1790 }; 1791 1792 /// An identifier, e.g. 'foo' or 'x'. 1793 /// This is a pseduo-term; it will be lowered to a variable or projection. 1794 class Identifier : public SExpr { 1795 public: 1796 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {} 1797 Identifier(const Identifier &) = default; 1798 1799 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } 1800 1801 StringRef name() const { return Name; } 1802 1803 template <class V> 1804 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1805 return Vs.reduceIdentifier(*this); 1806 } 1807 1808 template <class C> 1809 typename C::CType compare(const Identifier* E, C& Cmp) const { 1810 return Cmp.compareStrings(name(), E->name()); 1811 } 1812 1813 private: 1814 StringRef Name; 1815 }; 1816 1817 /// An if-then-else expression. 1818 /// This is a pseduo-term; it will be lowered to a branch in a CFG. 1819 class IfThenElse : public SExpr { 1820 public: 1821 IfThenElse(SExpr *C, SExpr *T, SExpr *E) 1822 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {} 1823 IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) 1824 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {} 1825 1826 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } 1827 1828 SExpr *condition() { return Condition; } // Address to store to 1829 const SExpr *condition() const { return Condition; } 1830 1831 SExpr *thenExpr() { return ThenExpr; } // Value to store 1832 const SExpr *thenExpr() const { return ThenExpr; } 1833 1834 SExpr *elseExpr() { return ElseExpr; } // Value to store 1835 const SExpr *elseExpr() const { return ElseExpr; } 1836 1837 template <class V> 1838 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1839 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1840 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); 1841 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); 1842 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); 1843 } 1844 1845 template <class C> 1846 typename C::CType compare(const IfThenElse* E, C& Cmp) const { 1847 typename C::CType Ct = Cmp.compare(condition(), E->condition()); 1848 if (Cmp.notTrue(Ct)) 1849 return Ct; 1850 Ct = Cmp.compare(thenExpr(), E->thenExpr()); 1851 if (Cmp.notTrue(Ct)) 1852 return Ct; 1853 return Cmp.compare(elseExpr(), E->elseExpr()); 1854 } 1855 1856 private: 1857 SExpr* Condition; 1858 SExpr* ThenExpr; 1859 SExpr* ElseExpr; 1860 }; 1861 1862 /// A let-expression, e.g. let x=t; u. 1863 /// This is a pseduo-term; it will be lowered to instructions in a CFG. 1864 class Let : public SExpr { 1865 public: 1866 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { 1867 Vd->setKind(Variable::VK_Let); 1868 } 1869 1870 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { 1871 Vd->setKind(Variable::VK_Let); 1872 } 1873 1874 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } 1875 1876 Variable *variableDecl() { return VarDecl; } 1877 const Variable *variableDecl() const { return VarDecl; } 1878 1879 SExpr *body() { return Body; } 1880 const SExpr *body() const { return Body; } 1881 1882 template <class V> 1883 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1884 // This is a variable declaration, so traverse the definition. 1885 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); 1886 // Tell the rewriter to enter the scope of the let variable. 1887 Variable *Nvd = Vs.enterScope(*VarDecl, E0); 1888 auto E1 = Vs.traverse(Body, Ctx); 1889 Vs.exitScope(*VarDecl); 1890 return Vs.reduceLet(*this, Nvd, E1); 1891 } 1892 1893 template <class C> 1894 typename C::CType compare(const Let* E, C& Cmp) const { 1895 typename C::CType Ct = 1896 Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 1897 if (Cmp.notTrue(Ct)) 1898 return Ct; 1899 Cmp.enterScope(variableDecl(), E->variableDecl()); 1900 Ct = Cmp.compare(body(), E->body()); 1901 Cmp.leaveScope(); 1902 return Ct; 1903 } 1904 1905 private: 1906 Variable *VarDecl; 1907 SExpr* Body; 1908 }; 1909 1910 const SExpr *getCanonicalVal(const SExpr *E); 1911 SExpr* simplifyToCanonicalVal(SExpr *E); 1912 void simplifyIncompleteArg(til::Phi *Ph); 1913 1914 } // namespace til 1915 } // namespace threadSafety 1916 1917 } // namespace clang 1918 1919 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 1920