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