granicus.if.org Git - clang/blob - include/clang/Analysis/Analyses/ThreadSafetyTIL.h

   1 //===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a simple intermediate language that is used by the
  11 // thread safety analysis (See ThreadSafety.cpp).  The thread safety analysis
  12 // works by comparing mutex expressions, e.g.
  13 //
  14 // class A { Mutex mu; int dat GUARDED_BY(this->mu); }
  15 // class B { A a; }
  16 //
  17 // void foo(B* b) {
  18 //   (*b).a.mu.lock();     // locks (*b).a.mu
  19 //   b->a.dat = 0;         // substitute &b->a for 'this';
  20 //                         // requires lock on (&b->a)->mu
  21 //   (b->a.mu).unlock();   // unlocks (b->a.mu)
  22 // }
  23 //
  24 // As illustrated by the above example, clang Exprs are not well-suited to
  25 // represent mutex expressions directly, since there is no easy way to compare
  26 // Exprs for equivalence.  The thread safety analysis thus lowers clang Exprs
  27 // into a simple intermediate language (IL).  The IL supports:
  28 //
  29 // (1) comparisons for semantic equality of expressions
  30 // (2) SSA renaming of variables
  31 // (3) wildcards and pattern matching over expressions
  32 // (4) hash-based expression lookup
  33 //
  34 // The IL is currently very experimental, is intended only for use within
  35 // the thread safety analysis, and is subject to change without notice.
  36 // After the API stabilizes and matures, it may be appropriate to make this
  37 // more generally available to other analyses.
  38 //
  39 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
  40 //
  41 //===----------------------------------------------------------------------===//
  42
  43 #ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H
  44 #define LLVM_CLANG_THREAD_SAFETY_TIL_H
  45
  46 #include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
  47 #include "clang/AST/ExprCXX.h"
  48 #include "llvm/ADT/StringRef.h"
  49 #include "llvm/Support/Compiler.h"
  50
  51 #include <cassert>
  52 #include <cstddef>
  53 #include <utility>
  54
  55
  56 namespace clang {
  57 namespace threadSafety {
  58 namespace til {
  59
  60 using llvm::StringRef;
  61 using clang::SourceLocation;
  62
  63
  64 enum TIL_Opcode {
  65 #define TIL_OPCODE_DEF(X) COP_##X,
  66 #include "clang/Analysis/Analyses/ThreadSafetyOps.def"
  67 #undef TIL_OPCODE_DEF
  68   COP_MAX
  69 };
  70
  71
  72 typedef clang::BinaryOperatorKind TIL_BinaryOpcode;
  73 typedef clang::UnaryOperatorKind TIL_UnaryOpcode;
  74 typedef clang::CastKind TIL_CastOpcode;
  75
  76
  77 enum TraversalKind {
  78   TRV_Normal,
  79   TRV_Lazy, // subexpression may need to be traversed lazily
  80   TRV_Tail  // subexpression occurs in a tail position
  81 };
  82
  83
  84 // Base class for AST nodes in the typed intermediate language.
  85 class SExpr {
  86 public:
  87   TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
  88
  89   // Subclasses of SExpr must define the following:
  90   //
  91   // This(const This& E, ...) {
  92   //   copy constructor: construct copy of E, with some additional arguments.
  93   // }
  94   //
  95   // template <class V> typename V::R_SExpr traverse(V &Visitor) {
  96   //   traverse all subexpressions, following the traversal/rewriter interface
  97   // }
  98   //
  99   // template <class C> typename C::CType compare(CType* E, C& Cmp) {
 100   //   compare all subexpressions, following the comparator interface
 101   // }
 102
 103   void *operator new(size_t S, clang::threadSafety::til::MemRegionRef &R) {
 104     return ::operator new(S, R);
 105   }
 106
 107 protected:
 108   SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {}
 109   SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {}
 110
 111   const unsigned char Opcode;
 112   unsigned char Reserved;
 113   unsigned short Flags;
 114
 115 private:
 116   SExpr() LLVM_DELETED_FUNCTION;
 117
 118   // SExpr objects must be created in an arena and cannot be deleted.
 119   void *operator new(size_t) LLVM_DELETED_FUNCTION;
 120   void operator delete(void *) LLVM_DELETED_FUNCTION;
 121 };
 122
 123
 124 // Class for owning references to SExprs.
 125 // Includes attach/detach logic for counting variable references and lazy
 126 // rewriting strategies.
 127 class SExprRef {
 128 public:
 129   SExprRef() : Ptr(nullptr) { }
 130   SExprRef(std::nullptr_t P) : Ptr(nullptr) { }
 131   SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; }
 132
 133   // Defined after Variable and Future, below.
 134   inline SExprRef(SExpr *P);
 135   inline ~SExprRef();
 136
 137   SExpr       *get()       { return Ptr; }
 138   const SExpr *get() const { return Ptr; }
 139
 140   SExpr       *operator->()       { return get(); }
 141   const SExpr *operator->() const { return get(); }
 142
 143   SExpr       &operator*()        { return *Ptr; }
 144   const SExpr &operator*() const  { return *Ptr; }
 145
 146   bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; }
 147   bool operator!=(const SExprRef &R) const { return !operator==(R); }
 148   bool operator==(const SExpr *P) const { return Ptr == P; }
 149   bool operator!=(const SExpr *P) const { return !operator==(P); }
 150   bool operator==(std::nullptr_t) const { return Ptr == nullptr; }
 151   bool operator!=(std::nullptr_t) const { return Ptr != nullptr; }
 152
 153   inline void reset(SExpr *E);
 154
 155 private:
 156   inline void attach();
 157   inline void detach();
 158
 159   SExpr *Ptr;
 160 };
 161
 162
 163 // Contains various helper functions for SExprs.
 164 namespace ThreadSafetyTIL {
 165   inline bool isTrivial(SExpr *E) {
 166     unsigned Op = E->opcode();
 167     return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
 168   }
 169 }
 170
 171 class Function;
 172 class SFunction;
 173 class BasicBlock;
 174
 175
 176 // A named variable, e.g. "x".
 177 //
 178 // There are two distinct places in which a Variable can appear in the AST.
 179 // A variable declaration introduces a new variable, and can occur in 3 places:
 180 //   Let-expressions:           (Let (x = t) u)
 181 //   Functions:                 (Function (x : t) u)
 182 //   Self-applicable functions  (SFunction (x) t)
 183 //
 184 // If a variable occurs in any other location, it is a reference to an existing
 185 // variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
 186 // allocate a separate AST node for variable references; a reference is just a
 187 // pointer to the original declaration.
 188 class Variable : public SExpr {
 189 public:
 190   static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
 191
 192   // Let-variable, function parameter, or self-variable
 193   enum VariableKind {
 194     VK_Let,
 195     VK_Fun,
 196     VK_SFun
 197   };
 198
 199   // These are defined after SExprRef contructor, below
 200   inline Variable(VariableKind K, SExpr *D = nullptr,
 201                   const clang::ValueDecl *Cvd = nullptr);
 202   inline Variable(SExpr *D = nullptr, const clang::ValueDecl *Cvd = nullptr);
 203   inline Variable(const Variable &Vd, SExpr *D);
 204
 205   VariableKind kind() const { return static_cast<VariableKind>(Flags); }
 206
 207   const StringRef name() const { return Cvdecl ? Cvdecl->getName() : "_x"; }
 208   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
 209
 210   // Returns the definition (for let vars) or type (for parameter & self vars)
 211   SExpr *definition() { return Definition.get(); }
 212
 213   void attachVar() const { ++NumUses; }
 214   void detachVar() const { assert(NumUses > 0); --NumUses; }
 215
 216   unsigned getID() const { return Id; }
 217   unsigned getBlockID() const { return BlockID; }
 218
 219   void setID(unsigned Bid, unsigned I) {
 220     BlockID = static_cast<unsigned short>(Bid);
 221     Id = static_cast<unsigned short>(I);
 222   }
 223   void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
 224
 225   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 226     // This routine is only called for variable references.
 227     return Visitor.reduceVariableRef(this);
 228   }
 229
 230   template <class C> typename C::CType compare(Variable* E, C& Cmp) {
 231     return Cmp.compareVariableRefs(this, E);
 232   }
 233
 234 private:
 235   friend class Function;
 236   friend class SFunction;
 237   friend class BasicBlock;
 238
 239   // Function, SFunction, and BasicBlock will reset the kind.
 240   void setKind(VariableKind K) { Flags = K; }
 241
 242   SExprRef Definition;             // The TIL type or definition
 243   const clang::ValueDecl *Cvdecl;  // The clang declaration for this variable.
 244
 245   unsigned short BlockID;
 246   unsigned short Id;
 247   mutable unsigned NumUses;
 248 };
 249
 250
 251 // Placeholder for an expression that has not yet been created.
 252 // Used to implement lazy copy and rewriting strategies.
 253 class Future : public SExpr {
 254 public:
 255   static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
 256
 257   enum FutureStatus {
 258     FS_pending,
 259     FS_evaluating,
 260     FS_done
 261   };
 262
 263   Future() :
 264     SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr)
 265   {}
 266 private:
 267   virtual ~Future() LLVM_DELETED_FUNCTION;
 268 public:
 269
 270   // Registers the location in the AST where this future is stored.
 271   // Forcing the future will automatically update the AST.
 272   static inline void registerLocation(SExprRef *Member) {
 273     if (Future *F = dyn_cast_or_null<Future>(Member->get()))
 274       F->Location = Member;
 275   }
 276
 277   // A lazy rewriting strategy should subclass Future and override this method.
 278   virtual SExpr *create() { return nullptr; }
 279
 280   // Return the result of this future if it exists, otherwise return null.
 281   SExpr *maybeGetResult() {
 282     return Result;
 283   }
 284
 285   // Return the result of this future; forcing it if necessary.
 286   SExpr *result() {
 287     switch (Status) {
 288     case FS_pending:
 289       force();
 290       return Result;
 291     case FS_evaluating:
 292       return nullptr; // infinite loop; illegal recursion.
 293     case FS_done:
 294       return Result;
 295     }
 296   }
 297
 298   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 299     assert(Result && "Cannot traverse Future that has not been forced.");
 300     return Visitor.traverse(Result);
 301   }
 302
 303   template <class C> typename C::CType compare(Future* E, C& Cmp) {
 304     if (!Result || !E->Result)
 305       return Cmp.comparePointers(this, E);
 306     return Cmp.compare(Result, E->Result);
 307   }
 308
 309 private:
 310   // Force the future.
 311   inline void force();
 312
 313   FutureStatus Status;
 314   SExpr *Result;
 315   SExprRef *Location;
 316 };
 317
 318 void SExprRef::attach() {
 319   if (!Ptr)
 320     return;
 321
 322   TIL_Opcode Op = Ptr->opcode();
 323   if (Op == COP_Variable) {
 324     cast<Variable>(Ptr)->attachVar();
 325   } else if (Op == COP_Future) {
 326     cast<Future>(Ptr)->registerLocation(this);
 327   }
 328 }
 329
 330 void SExprRef::detach() {
 331   if (Ptr && Ptr->opcode() == COP_Variable) {
 332     cast<Variable>(Ptr)->detachVar();
 333   }
 334 }
 335
 336 SExprRef::SExprRef(SExpr *P) : Ptr(P) {
 337   attach();
 338 }
 339
 340 SExprRef::~SExprRef() {
 341   detach();
 342 }
 343
 344 void SExprRef::reset(SExpr *P) {
 345   detach();
 346   Ptr = P;
 347   attach();
 348 }
 349
 350
 351 Variable::Variable(VariableKind K, SExpr *D, const clang::ValueDecl *Cvd)
 352     : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd),
 353       BlockID(0), Id(0),  NumUses(0) {
 354   Flags = K;
 355 }
 356
 357 Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd)
 358     : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd),
 359       BlockID(0), Id(0),  NumUses(0) {
 360   Flags = VK_Let;
 361 }
 362
 363 Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor
 364     : SExpr(Vd), Definition(D), Cvdecl(Vd.Cvdecl),
 365       BlockID(0), Id(0), NumUses(0) {
 366   Flags = Vd.kind();
 367 }
 368
 369 void Future::force() {
 370   Status = FS_evaluating;
 371   SExpr *R = create();
 372   Result = R;
 373   if (Location)
 374     Location->reset(R);
 375   Status = FS_done;
 376 }
 377
 378 // Placeholder for C++ expressions that cannot be represented in the TIL.
 379 class Undefined : public SExpr {
 380 public:
 381   static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
 382
 383   Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
 384   Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
 385
 386   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 387     return Visitor.reduceUndefined(*this);
 388   }
 389
 390   template <class C> typename C::CType compare(Undefined* E, C& Cmp) {
 391     return Cmp.comparePointers(Cstmt, E->Cstmt);
 392   }
 393
 394 private:
 395   const clang::Stmt *Cstmt;
 396 };
 397
 398
 399 // Placeholder for a wildcard that matches any other expression.
 400 class Wildcard : public SExpr {
 401 public:
 402   static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
 403
 404   Wildcard() : SExpr(COP_Wildcard) {}
 405   Wildcard(const Wildcard &W) : SExpr(W) {}
 406
 407   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 408     return Visitor.reduceWildcard(*this);
 409   }
 410
 411   template <class C> typename C::CType compare(Wildcard* E, C& Cmp) {
 412     return Cmp.trueResult();
 413   }
 414 };
 415
 416
 417 // Base class for literal values.
 418 class Literal : public SExpr {
 419 public:
 420   static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
 421
 422   Literal(const clang::Expr *C) : SExpr(COP_Literal), Cexpr(C) {}
 423   Literal(const Literal &L) : SExpr(L), Cexpr(L.Cexpr) {}
 424
 425   // The clang expression for this literal.
 426   const clang::Expr *clangExpr() const { return Cexpr; }
 427
 428   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 429     return Visitor.reduceLiteral(*this);
 430   }
 431
 432   template <class C> typename C::CType compare(Literal* E, C& Cmp) {
 433     // TODO -- use value, not pointer equality
 434     return Cmp.comparePointers(Cexpr, E->Cexpr);
 435   }
 436
 437 private:
 438   const clang::Expr *Cexpr;
 439 };
 440
 441 // Literal pointer to an object allocated in memory.
 442 // At compile time, pointer literals are represented by symbolic names.
 443 class LiteralPtr : public SExpr {
 444 public:
 445   static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
 446
 447   LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
 448   LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
 449
 450   // The clang declaration for the value that this pointer points to.
 451   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
 452
 453   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 454     return Visitor.reduceLiteralPtr(*this);
 455   }
 456
 457   template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) {
 458     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
 459   }
 460
 461 private:
 462   const clang::ValueDecl *Cvdecl;
 463 };
 464
 465 // A function -- a.k.a. lambda abstraction.
 466 // Functions with multiple arguments are created by currying,
 467 // e.g. (function (x: Int) (function (y: Int) (add x y)))
 468 class Function : public SExpr {
 469 public:
 470   static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
 471
 472   Function(Variable *Vd, SExpr *Bd)
 473       : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
 474     Vd->setKind(Variable::VK_Fun);
 475   }
 476   Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
 477       : SExpr(F), VarDecl(Vd), Body(Bd) {
 478     Vd->setKind(Variable::VK_Fun);
 479   }
 480
 481   Variable *variableDecl()  { return VarDecl; }
 482   const Variable *variableDecl() const { return VarDecl; }
 483
 484   SExpr *body() { return Body.get(); }
 485   const SExpr *body() const { return Body.get(); }
 486
 487   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 488     // This is a variable declaration, so traverse the definition.
 489     typename V::R_SExpr E0 = Visitor.traverse(VarDecl->Definition, TRV_Lazy);
 490     // Tell the rewriter to enter the scope of the function.
 491     Variable *Nvd = Visitor.enterScope(*VarDecl, E0);
 492     typename V::R_SExpr E1 = Visitor.traverse(Body);
 493     Visitor.exitScope(*VarDecl);
 494     return Visitor.reduceFunction(*this, Nvd, E1);
 495   }
 496
 497   template <class C> typename C::CType compare(Function* E, C& Cmp) {
 498     typename C::CType Ct =
 499       Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
 500     if (Cmp.notTrue(Ct))
 501       return Ct;
 502     Cmp.enterScope(variableDecl(), E->variableDecl());
 503     Ct = Cmp.compare(body(), E->body());
 504     Cmp.leaveScope();
 505     return Ct;
 506   }
 507
 508 private:
 509   Variable *VarDecl;
 510   SExprRef Body;
 511 };
 512
 513
 514 // A self-applicable function.
 515 // A self-applicable function can be applied to itself.  It's useful for
 516 // implementing objects and late binding
 517 class SFunction : public SExpr {
 518 public:
 519   static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
 520
 521   SFunction(Variable *Vd, SExpr *B)
 522       : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
 523     assert(Vd->Definition == nullptr);
 524     Vd->setKind(Variable::VK_SFun);
 525     Vd->Definition.reset(this);
 526   }
 527   SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
 528       : SExpr(F), VarDecl(Vd), Body(B) {
 529     assert(Vd->Definition == nullptr);
 530     Vd->setKind(Variable::VK_SFun);
 531     Vd->Definition.reset(this);
 532   }
 533
 534   Variable *variableDecl() { return VarDecl; }
 535   const Variable *variableDecl() const { return VarDecl; }
 536
 537   SExpr *body() { return Body.get(); }
 538   const SExpr *body() const { return Body.get(); }
 539
 540   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 541     // A self-variable points to the SFunction itself.
 542     // A rewrite must introduce the variable with a null definition, and update
 543     // it after 'this' has been rewritten.
 544     Variable *Nvd = Visitor.enterScope(*VarDecl, nullptr /* def */);
 545     typename V::R_SExpr E1 = Visitor.traverse(Body);
 546     Visitor.exitScope(*VarDecl);
 547     // A rewrite operation will call SFun constructor to set Vvd->Definition.
 548     return Visitor.reduceSFunction(*this, Nvd, E1);
 549   }
 550
 551   template <class C> typename C::CType compare(SFunction* E, C& Cmp) {
 552     Cmp.enterScope(variableDecl(), E->variableDecl());
 553     typename C::CType Ct = Cmp.compare(body(), E->body());
 554     Cmp.leaveScope();
 555     return Ct;
 556   }
 557
 558 private:
 559   Variable *VarDecl;
 560   SExprRef Body;
 561 };
 562
 563
 564 // A block of code -- e.g. the body of a function.
 565 class Code : public SExpr {
 566 public:
 567   static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
 568
 569   Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
 570   Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
 571       : SExpr(C), ReturnType(T), Body(B) {}
 572
 573   SExpr *returnType() { return ReturnType.get(); }
 574   const SExpr *returnType() const { return ReturnType.get(); }
 575
 576   SExpr *body() { return Body.get(); }
 577   const SExpr *body() const { return Body.get(); }
 578
 579   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 580     typename V::R_SExpr Nt = Visitor.traverse(ReturnType, TRV_Lazy);
 581     typename V::R_SExpr Nb = Visitor.traverse(Body, TRV_Lazy);
 582     return Visitor.reduceCode(*this, Nt, Nb);
 583   }
 584
 585   template <class C> typename C::CType compare(Code* E, C& Cmp) {
 586     typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
 587     if (Cmp.notTrue(Ct))
 588       return Ct;
 589     return Cmp.compare(body(), E->body());
 590   }
 591
 592 private:
 593   SExprRef ReturnType;
 594   SExprRef Body;
 595 };
 596
 597
 598 // Apply an argument to a function
 599 class Apply : public SExpr {
 600 public:
 601   static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
 602
 603   Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
 604   Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
 605       : SExpr(A), Fun(F), Arg(Ar)
 606   {}
 607
 608   SExpr *fun() { return Fun.get(); }
 609   const SExpr *fun() const { return Fun.get(); }
 610
 611   SExpr *arg() { return Arg.get(); }
 612   const SExpr *arg() const { return Arg.get(); }
 613
 614   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 615     typename V::R_SExpr Nf = Visitor.traverse(Fun);
 616     typename V::R_SExpr Na = Visitor.traverse(Arg);
 617     return Visitor.reduceApply(*this, Nf, Na);
 618   }
 619
 620   template <class C> typename C::CType compare(Apply* E, C& Cmp) {
 621     typename C::CType Ct = Cmp.compare(fun(), E->fun());
 622     if (Cmp.notTrue(Ct))
 623       return Ct;
 624     return Cmp.compare(arg(), E->arg());
 625   }
 626
 627 private:
 628   SExprRef Fun;
 629   SExprRef Arg;
 630 };
 631
 632
 633 // Apply a self-argument to a self-applicable function
 634 class SApply : public SExpr {
 635 public:
 636   static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
 637
 638   SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
 639   SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
 640       : SExpr(A), Sfun(Sf), Arg(Ar) {}
 641
 642   SExpr *sfun() { return Sfun.get(); }
 643   const SExpr *sfun() const { return Sfun.get(); }
 644
 645   SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); }
 646   const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); }
 647
 648   bool isDelegation() const { return Arg == nullptr; }
 649
 650   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 651     typename V::R_SExpr Nf = Visitor.traverse(Sfun);
 652     typename V::R_SExpr Na = Arg.get() ? Visitor.traverse(Arg) : nullptr;
 653     return Visitor.reduceSApply(*this, Nf, Na);
 654   }
 655
 656   template <class C> typename C::CType compare(SApply* E, C& Cmp) {
 657     typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
 658     if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
 659       return Ct;
 660     return Cmp.compare(arg(), E->arg());
 661   }
 662
 663 private:
 664   SExprRef Sfun;
 665   SExprRef Arg;
 666 };
 667
 668
 669 // Project a named slot from a C++ struct or class.
 670 class Project : public SExpr {
 671 public:
 672   static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
 673
 674   Project(SExpr *R, clang::ValueDecl *Cvd)
 675       : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {}
 676   Project(const Project &P, SExpr *R) : SExpr(P), Rec(R), Cvdecl(P.Cvdecl) {}
 677
 678   SExpr *record() { return Rec.get(); }
 679   const SExpr *record() const { return Rec.get(); }
 680
 681   const clang::ValueDecl *clangValueDecl() const { return Cvdecl; }
 682
 683   StringRef slotName() const { return Cvdecl->getName(); }
 684
 685   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 686     typename V::R_SExpr Nr = Visitor.traverse(Rec);
 687     return Visitor.reduceProject(*this, Nr);
 688   }
 689
 690   template <class C> typename C::CType compare(Project* E, C& Cmp) {
 691     typename C::CType Ct = Cmp.compare(record(), E->record());
 692     if (Cmp.notTrue(Ct))
 693       return Ct;
 694     return Cmp.comparePointers(Cvdecl, E->Cvdecl);
 695   }
 696
 697 private:
 698   SExprRef Rec;
 699   clang::ValueDecl *Cvdecl;
 700 };
 701
 702
 703 // Call a function (after all arguments have been applied).
 704 class Call : public SExpr {
 705 public:
 706   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
 707
 708   Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
 709       : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
 710   Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
 711
 712   SExpr *target() { return Target.get(); }
 713   const SExpr *target() const { return Target.get(); }
 714
 715   const clang::CallExpr *clangCallExpr() const { return Cexpr; }
 716
 717   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 718     typename V::R_SExpr Nt = Visitor.traverse(Target);
 719     return Visitor.reduceCall(*this, Nt);
 720   }
 721
 722   template <class C> typename C::CType compare(Call* E, C& Cmp) {
 723     return Cmp.compare(target(), E->target());
 724   }
 725
 726 private:
 727   SExprRef Target;
 728   const clang::CallExpr *Cexpr;
 729 };
 730
 731
 732 // Allocate memory for a new value on the heap or stack.
 733 class Alloc : public SExpr {
 734 public:
 735   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
 736
 737   enum AllocKind {
 738     AK_Stack,
 739     AK_Heap
 740   };
 741
 742   Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
 743   Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
 744
 745   AllocKind kind() const { return static_cast<AllocKind>(Flags); }
 746
 747   SExpr *dataType() { return Dtype.get(); }
 748   const SExpr *dataType() const { return Dtype.get(); }
 749
 750   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 751     typename V::R_SExpr Nd = Visitor.traverse(Dtype);
 752     return Visitor.reduceAlloc(*this, Nd);
 753   }
 754
 755   template <class C> typename C::CType compare(Alloc* E, C& Cmp) {
 756     typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
 757     if (Cmp.notTrue(Ct))
 758       return Ct;
 759     return Cmp.compare(dataType(), E->dataType());
 760   }
 761
 762 private:
 763   SExprRef Dtype;
 764 };
 765
 766
 767 // Load a value from memory.
 768 class Load : public SExpr {
 769 public:
 770   static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
 771
 772   Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
 773   Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
 774
 775   SExpr *pointer() { return Ptr.get(); }
 776   const SExpr *pointer() const { return Ptr.get(); }
 777
 778   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 779     typename V::R_SExpr Np = Visitor.traverse(Ptr);
 780     return Visitor.reduceLoad(*this, Np);
 781   }
 782
 783   template <class C> typename C::CType compare(Load* E, C& Cmp) {
 784     return Cmp.compare(pointer(), E->pointer());
 785   }
 786
 787 private:
 788   SExprRef Ptr;
 789 };
 790
 791
 792 // Store a value to memory.
 793 class Store : public SExpr {
 794 public:
 795   static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
 796
 797   Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
 798   Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
 799
 800   SExpr *destination() { return Dest.get(); }  // Address to store to
 801   const SExpr *destination() const { return Dest.get(); }
 802
 803   SExpr *source() { return Source.get(); }     // Value to store
 804   const SExpr *source() const { return Source.get(); }
 805
 806   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 807     typename V::R_SExpr Np = Visitor.traverse(Dest);
 808     typename V::R_SExpr Nv = Visitor.traverse(Source);
 809     return Visitor.reduceStore(*this, Np, Nv);
 810   }
 811
 812   template <class C> typename C::CType compare(Store* E, C& Cmp) {
 813     typename C::CType Ct = Cmp.compare(destination(), E->destination());
 814     if (Cmp.notTrue(Ct))
 815       return Ct;
 816     return Cmp.compare(source(), E->source());
 817   }
 818
 819 private:
 820   SExprRef Dest;
 821   SExprRef Source;
 822 };
 823
 824
 825 // Simple unary operation -- e.g. !, ~, etc.
 826 class UnaryOp : public SExpr {
 827 public:
 828   static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
 829
 830   UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
 831     Flags = Op;
 832   }
 833   UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U) { Flags = U.Flags; }
 834
 835   TIL_UnaryOpcode unaryOpcode() const {
 836     return static_cast<TIL_UnaryOpcode>(Flags);
 837   }
 838
 839   SExpr *expr() { return Expr0.get(); }
 840   const SExpr *expr() const { return Expr0.get(); }
 841
 842   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 843     typename V::R_SExpr Ne = Visitor.traverse(Expr0);
 844     return Visitor.reduceUnaryOp(*this, Ne);
 845   }
 846
 847   template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) {
 848     typename C::CType Ct =
 849       Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
 850     if (Cmp.notTrue(Ct))
 851       return Ct;
 852     return Cmp.compare(expr(), E->expr());
 853   }
 854
 855 private:
 856   SExprRef Expr0;
 857 };
 858
 859
 860 // Simple binary operation -- e.g. +, -, etc.
 861 class BinaryOp : public SExpr {
 862 public:
 863   static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
 864
 865   BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
 866       : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
 867     Flags = Op;
 868   }
 869   BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
 870       : SExpr(B), Expr0(E0), Expr1(E1) {
 871     Flags = B.Flags;
 872   }
 873
 874   TIL_BinaryOpcode binaryOpcode() const {
 875     return static_cast<TIL_BinaryOpcode>(Flags);
 876   }
 877
 878   SExpr *expr0() { return Expr0.get(); }
 879   const SExpr *expr0() const { return Expr0.get(); }
 880
 881   SExpr *expr1() { return Expr1.get(); }
 882   const SExpr *expr1() const { return Expr1.get(); }
 883
 884   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 885     typename V::R_SExpr Ne0 = Visitor.traverse(Expr0);
 886     typename V::R_SExpr Ne1 = Visitor.traverse(Expr1);
 887     return Visitor.reduceBinaryOp(*this, Ne0, Ne1);
 888   }
 889
 890   template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) {
 891     typename C::CType Ct =
 892       Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
 893     if (Cmp.notTrue(Ct))
 894       return Ct;
 895     Ct = Cmp.compare(expr0(), E->expr0());
 896     if (Cmp.notTrue(Ct))
 897       return Ct;
 898     return Cmp.compare(expr1(), E->expr1());
 899   }
 900
 901 private:
 902   SExprRef Expr0;
 903   SExprRef Expr1;
 904 };
 905
 906
 907 // Cast expression
 908 class Cast : public SExpr {
 909 public:
 910   static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
 911
 912   Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
 913   Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
 914
 915   TIL_CastOpcode castOpcode() const {
 916     return static_cast<TIL_CastOpcode>(Flags);
 917   }
 918
 919   SExpr *expr() { return Expr0.get(); }
 920   const SExpr *expr() const { return Expr0.get(); }
 921
 922   template <class V> typename V::R_SExpr traverse(V &Visitor) {
 923     typename V::R_SExpr Ne = Visitor.traverse(Expr0);
 924     return Visitor.reduceCast(*this, Ne);
 925   }
 926
 927   template <class C> typename C::CType compare(Cast* E, C& Cmp) {
 928     typename C::CType Ct =
 929       Cmp.compareIntegers(castOpcode(), E->castOpcode());
 930     if (Cmp.notTrue(Ct))
 931       return Ct;
 932     return Cmp.compare(expr(), E->expr());
 933   }
 934
 935 private:
 936   SExprRef Expr0;
 937 };
 938
 939
 940
 941 class BasicBlock;
 942
 943 // An SCFG is a control-flow graph.  It consists of a set of basic blocks, each
 944 // of which terminates in a branch to another basic block.  There is one
 945 // entry point, and one exit point.
 946 class SCFG : public SExpr {
 947 public:
 948   typedef SimpleArray<BasicBlock *> BlockArray;
 949   typedef BlockArray::iterator iterator;
 950   typedef BlockArray::const_iterator const_iterator;
 951
 952   static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
 953
 954   SCFG(MemRegionRef A, unsigned Nblocks)
 955       : SExpr(COP_SCFG), Blocks(A, Nblocks),
 956         Entry(nullptr), Exit(nullptr) {}
 957   SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
 958       : SExpr(COP_SCFG), Blocks(std::move(Ba)), Entry(nullptr), Exit(nullptr) {
 959     // TODO: set entry and exit!
 960   }
 961
 962   iterator begin() { return Blocks.begin(); }
 963   iterator end() { return Blocks.end(); }
 964
 965   const_iterator begin() const { return cbegin(); }
 966   const_iterator end() const { return cend(); }
 967
 968   const_iterator cbegin() const { return Blocks.cbegin(); }
 969   const_iterator cend() const { return Blocks.cend(); }
 970
 971   const BasicBlock *entry() const { return Entry; }
 972   BasicBlock *entry() { return Entry; }
 973   const BasicBlock *exit() const { return Exit; }
 974   BasicBlock *exit() { return Exit; }
 975
 976   void add(BasicBlock *BB);
 977   void setEntry(BasicBlock *BB) { Entry = BB; }
 978   void setExit(BasicBlock *BB) { Exit = BB; }
 979
 980   template <class V> typename V::R_SExpr traverse(V &Visitor);
 981
 982   template <class C> typename C::CType compare(SCFG *E, C &Cmp) {
 983     // TODO -- implement CFG comparisons
 984     return Cmp.comparePointers(this, E);
 985   }
 986
 987 private:
 988   BlockArray Blocks;
 989   BasicBlock *Entry;
 990   BasicBlock *Exit;
 991 };
 992
 993
 994 // A basic block is part of an SCFG, and can be treated as a function in
 995 // continuation passing style.  It consists of a sequence of phi nodes, which
 996 // are "arguments" to the function, followed by a sequence of instructions.
 997 // Both arguments and instructions define new variables.  It ends with a
 998 // branch or goto to another basic block in the same SCFG.
 999 class BasicBlock {
1000 public:
1001   typedef SimpleArray<Variable*> VarArray;
1002
1003   BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins,
1004              SExpr *Term = nullptr)
1005       : BlockID(0), NumVars(0), NumPredecessors(0), Parent(nullptr),
1006         Args(A, Nargs), Instrs(A, Nins), Terminator(Term) {}
1007   BasicBlock(const BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T)
1008       : BlockID(0),  NumVars(B.NumVars), NumPredecessors(B.NumPredecessors),
1009         Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)),
1010         Terminator(T) {}
1011
1012   unsigned blockID() const { return BlockID; }
1013   unsigned numPredecessors() const { return NumPredecessors; }
1014
1015   const BasicBlock *parent() const { return Parent; }
1016   BasicBlock *parent() { return Parent; }
1017
1018   const VarArray &arguments() const { return Args; }
1019   VarArray &arguments() { return Args; }
1020
1021   const VarArray &instructions() const { return Instrs; }
1022   VarArray &instructions() { return Instrs; }
1023
1024   const SExpr *terminator() const { return Terminator.get(); }
1025   SExpr *terminator() { return Terminator.get(); }
1026
1027   void setBlockID(unsigned i) { BlockID = i; }
1028   void setParent(BasicBlock *P) { Parent = P; }
1029   void setNumPredecessors(unsigned NP) { NumPredecessors = NP; }
1030   void setTerminator(SExpr *E) { Terminator.reset(E); }
1031
1032   void addArgument(Variable *V) {
1033     V->setID(BlockID, NumVars++);
1034     Args.push_back(V);
1035   }
1036   void addInstruction(Variable *V) {
1037     V->setID(BlockID, NumVars++);
1038     Instrs.push_back(V);
1039   }
1040
1041   template <class V> BasicBlock *traverse(V &Visitor) {
1042     typename V::template Container<Variable*> Nas(Visitor, Args.size());
1043     typename V::template Container<Variable*> Nis(Visitor, Instrs.size());
1044
1045     for (auto *A : Args) {
1046       typename V::R_SExpr Ne = Visitor.traverse(A->Definition);
1047       Variable *Nvd = Visitor.enterScope(*A, Ne);
1048       Nas.push_back(Nvd);
1049     }
1050     for (auto *I : Instrs) {
1051       typename V::R_SExpr Ne = Visitor.traverse(I->Definition);
1052       Variable *Nvd = Visitor.enterScope(*I, Ne);
1053       Nis.push_back(Nvd);
1054     }
1055     typename V::R_SExpr Nt = Visitor.traverse(Terminator);
1056
1057     // TODO: use reverse iterator
1058     for (unsigned J = 0, JN = Instrs.size(); J < JN; ++J)
1059       Visitor.exitScope(*Instrs[JN-J]);
1060     for (unsigned I = 0, IN = Instrs.size(); I < IN; ++I)
1061       Visitor.exitScope(*Args[IN-I]);
1062
1063     return Visitor.reduceBasicBlock(*this, Nas, Nis, Nt);
1064   }
1065
1066   template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) {
1067     // TODO: implement CFG comparisons
1068     return Cmp.comparePointers(this, E);
1069   }
1070
1071 private:
1072   friend class SCFG;
1073
1074   unsigned BlockID;
1075   unsigned NumVars;
1076   unsigned NumPredecessors; // Number of blocks which jump to this one.
1077
1078   BasicBlock *Parent;       // The parent block is the enclosing lexical scope.
1079                             // The parent dominates this block.
1080   VarArray Args;            // Phi nodes.  One argument per predecessor.
1081   VarArray Instrs;
1082   SExprRef Terminator;
1083 };
1084
1085
1086 inline void SCFG::add(BasicBlock *BB) {
1087   BB->setBlockID(Blocks.size());
1088   Blocks.push_back(BB);
1089 }
1090
1091
1092 template <class V>
1093 typename V::R_SExpr SCFG::traverse(V &Visitor) {
1094   Visitor.enterCFG(*this);
1095   typename V::template Container<BasicBlock *> Bbs(Visitor, Blocks.size());
1096   for (auto *B : Blocks) {
1097     BasicBlock *Nbb = B->traverse(Visitor);
1098     Bbs.push_back(Nbb);
1099   }
1100   Visitor.exitCFG(*this);
1101   return Visitor.reduceSCFG(*this, Bbs);
1102 }
1103
1104
1105 class Phi : public SExpr {
1106 public:
1107   // TODO: change to SExprRef
1108   typedef SimpleArray<SExpr *> ValArray;
1109
1110   static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1111
1112   Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1113   Phi(const Phi &P, ValArray &&Vs) // steals memory of Vs
1114       : SExpr(COP_Phi), Values(std::move(Vs)) {}
1115
1116   const ValArray &values() const { return Values; }
1117   ValArray &values() { return Values; }
1118
1119   // Incomplete phi nodes are constructed during SSA conversion, and
1120   // may not be necessary.
1121   bool incomplete() const { return Flags == 1; }
1122
1123   void setIncomplete(bool b) {
1124     if (b) Flags = 1;
1125     else Flags = 0;
1126   }
1127
1128   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1129     typename V::template Container<typename V::R_SExpr> Nvs(Visitor,
1130                                                             Values.size());
1131     for (auto *Val : Values) {
1132       typename V::R_SExpr Nv = Visitor.traverse(Val);
1133       Nvs.push_back(Nv);
1134     }
1135     return Visitor.reducePhi(*this, Nvs);
1136   }
1137
1138   template <class C> typename C::CType compare(Phi *E, C &Cmp) {
1139     // TODO: implement CFG comparisons
1140     return Cmp.comparePointers(this, E);
1141   }
1142
1143 private:
1144   ValArray Values;
1145 };
1146
1147
1148 class Goto : public SExpr {
1149 public:
1150   static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1151
1152   Goto(BasicBlock *B, unsigned Index)
1153       : SExpr(COP_Goto), TargetBlock(B), Index(0) {}
1154   Goto(const Goto &G, BasicBlock *B, unsigned I)
1155       : SExpr(COP_Goto), TargetBlock(B), Index(I) {}
1156
1157   const BasicBlock *targetBlock() const { return TargetBlock; }
1158   BasicBlock *targetBlock() { return TargetBlock; }
1159
1160   unsigned index() const { return Index; }
1161
1162   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1163     // TODO -- rewrite indices properly
1164     BasicBlock *Ntb = Visitor.reduceBasicBlockRef(TargetBlock);
1165     return Visitor.reduceGoto(*this, Ntb, Index);
1166   }
1167
1168   template <class C> typename C::CType compare(Goto *E, C &Cmp) {
1169     // TODO -- implement CFG comparisons
1170     return Cmp.comparePointers(this, E);
1171   }
1172
1173 private:
1174   BasicBlock *TargetBlock;
1175   unsigned Index;   // Index into Phi nodes of target block.
1176 };
1177
1178
1179 class Branch : public SExpr {
1180 public:
1181   static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1182
1183   Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1184       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1185         ThenIndex(0), ElseIndex(0)
1186   {}
1187   Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1188       : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E),
1189         ThenIndex(0), ElseIndex(0)
1190   {}
1191
1192   const SExpr *condition() const { return Condition; }
1193   SExpr *condition() { return Condition; }
1194
1195   const BasicBlock *thenBlock() const { return ThenBlock; }
1196   BasicBlock *thenBlock() { return ThenBlock; }
1197
1198   const BasicBlock *elseBlock() const { return ElseBlock; }
1199   BasicBlock *elseBlock() { return ElseBlock; }
1200
1201   unsigned thenIndex() const { return ThenIndex; }
1202   unsigned elseIndex() const { return ElseIndex; }
1203
1204   template <class V> typename V::R_SExpr traverse(V &Visitor) {
1205     typename V::R_SExpr Nc = Visitor.traverse(Condition);
1206     BasicBlock *Ntb = Visitor.reduceBasicBlockRef(ThenBlock);
1207     BasicBlock *Nte = Visitor.reduceBasicBlockRef(ElseBlock);
1208     return Visitor.reduceBranch(*this, Nc, Ntb, Nte);
1209   }
1210
1211   template <class C> typename C::CType compare(Branch *E, C &Cmp) {
1212     // TODO -- implement CFG comparisons
1213     return Cmp.comparePointers(this, E);
1214   }
1215
1216 private:
1217   SExpr *Condition;
1218   BasicBlock *ThenBlock;
1219   BasicBlock *ElseBlock;
1220   unsigned ThenIndex;
1221   unsigned ElseIndex;
1222 };
1223
1224
1225 } // end namespace til
1226 } // end namespace threadSafety
1227 } // end namespace clang
1228
1229 #endif // LLVM_CLANG_THREAD_SAFETY_TIL_H