diff options
| -rw-r--r-- | include/clang/Analysis/Analyses/ThreadSafetyCommon.h | 244 | ||||
| -rw-r--r-- | include/clang/Analysis/Analyses/ThreadSafetyOps.def | 44 | ||||
| -rw-r--r-- | include/clang/Analysis/Analyses/ThreadSafetyTIL.h | 1831 | ||||
| -rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Analysis/ThreadSafety.cpp | 23 | ||||
| -rw-r--r-- | lib/Analysis/ThreadSafetyCommon.cpp | 407 |
6 files changed, 2542 insertions, 8 deletions
diff --git a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h new file mode 100644 index 0000000000..92d904e59a --- /dev/null +++ b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -0,0 +1,244 @@ +//===- ThreadSafetyCommon.h ------------------------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Parts of thread safety analysis that are not specific to thread safety +// itself have been factored into classes here, where they can be potentially +// used by other analyses. Currently these include: +// +// * Generalize clang CFG visitors. +// * Conversion of the clang CFG to SSA form. +// * Translation of clang Exprs to TIL SExprs +// +// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/Attr.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/StmtCXX.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/CFGStmtMap.h" +#include "clang/Basic/OperatorKinds.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Basic/SourceManager.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include <vector> + + +namespace clang { +namespace threadSafety { + + +// Simple Visitor class for traversing a clang CFG. +class CFGVisitor { +public: + // Enter the CFG for Decl D, and perform any initial setup operations. + void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} + + // Enter a CFGBlock. + void enterCFGBlock(const CFGBlock *B) {} + + // Process an ordinary statement. + void handleStatement(const Stmt *S) {} + + // Process a destructor call + void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} + + // Process a successor edge. + void handleSuccessor(const CFGBlock *Succ) {} + + // Process a successor back edge to a previously visited block. + void handleSuccessorBackEdge(const CFGBlock *Succ) {} + + // Leave a CFGBlock. + void exitCFGBlock(const CFGBlock *B) {} + + // Leave the CFG, and perform any final cleanup operations. + void exitCFG(const CFGBlock *Last) {} +}; + + +// Walks the clang CFG, and invokes methods on a given CFGVisitor. +class CFGWalker { +public: + CFGWalker() : CFGraph(0), FDecl(0), ACtx(0), SortedGraph(0) {} + + ~CFGWalker() { } + + // Initialize the CFGWalker. This setup only needs to be done once, even + // if there are multiple passes over the CFG. + bool init(AnalysisDeclContext &AC) { + ACtx = &AC; + CFGraph = AC.getCFG(); + if (!CFGraph) + return false; + + FDecl = dyn_cast_or_null<NamedDecl>(AC.getDecl()); + if (!FDecl) // ignore anonymous functions + return false; + + SortedGraph = AC.getAnalysis<PostOrderCFGView>(); + if (!SortedGraph) + return false; + + return true; + } + + // Traverse the CFG, calling methods on V as appropriate. + template <class Visitor> + void walk(Visitor &V) { + PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); + + V.enterCFG(CFGraph, FDecl, &CFGraph->getEntry()); + + for (const CFGBlock* CurrBlock : *SortedGraph) { + VisitedBlocks.insert(CurrBlock); + + V.enterCFGBlock(CurrBlock); + + // Process statements + for (CFGBlock::const_iterator BI = CurrBlock->begin(), + BE = CurrBlock->end(); + BI != BE; ++BI) { + switch (BI->getKind()) { + case CFGElement::Statement: { + V.handleStatement(BI->castAs<CFGStmt>().getStmt()); + break; + } + case CFGElement::AutomaticObjectDtor: { + CFGAutomaticObjDtor AD = BI->castAs<CFGAutomaticObjDtor>(); + CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( + AD.getDestructorDecl(ACtx->getASTContext())); + VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); + V.handleDestructorCall(VD, DD); + break; + } + default: + break; + } + } + + // Process successors + for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), + SE = CurrBlock->succ_end(); + SI != SE; ++SI) { + if (*SI == 0) + continue; + + if (VisitedBlocks.alreadySet(*SI)) { + V.handleSuccessorBackEdge(*SI); + continue; + } + V.handleSuccessor(*SI); + } + + V.exitCFGBlock(CurrBlock); + } + V.exitCFG(&CFGraph->getExit()); + } + +public: + CFG *CFGraph; + const NamedDecl *FDecl; + AnalysisDeclContext *ACtx; + PostOrderCFGView *SortedGraph; +}; + + +// Translate clang::Expr to til::SExpr. +class SExprBuilder { +public: + typedef llvm::DenseMap<const Stmt*, til::Variable*> StatementMap; + + /// \brief Encapsulates the lexical context of a function call. The lexical + /// context includes the arguments to the call, including the implicit object + /// argument. When an attribute containing a mutex expression is attached to + /// a method, the expression may refer to formal parameters of the method. + /// Actual arguments must be substituted for formal parameters to derive + /// the appropriate mutex expression in the lexical context where the function + /// is called. PrevCtx holds the context in which the arguments themselves + /// should be evaluated; multiple calling contexts can be chained together + /// by the lock_returned attribute. + struct CallingContext { + const NamedDecl *AttrDecl; // The decl to which the attr is attached. + const Expr *SelfArg; // Implicit object argument -- e.g. 'this' + unsigned NumArgs; // Number of funArgs + const Expr *const *FunArgs; // Function arguments + CallingContext *Prev; // The previous context; or 0 if none. + bool SelfArrow; // is Self referred to with -> or .? + + CallingContext(const NamedDecl *D = 0, const Expr *S = 0, unsigned N = 0, + const Expr *const *A = 0, CallingContext *P = 0) + : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P), + SelfArrow(false) + {} + }; + + til::SExpr *lookupStmt(const Stmt *S); + void insertStmt(const Stmt *S, til::Variable *V); + + // Translate a clang statement or expression to a TIL expression. + // Also performs substitution of variables; Ctx provides the context. + // Dispatches on the type of S. + til::SExpr *translate(const Stmt *S, CallingContext *Ctx); + + + til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, + CallingContext *Ctx) ; + til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); + til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); + til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx); + til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, + CallingContext *Ctx); + til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, + CallingContext *Ctx); + til::SExpr *translateUnaryOperator(const UnaryOperator *UO, + CallingContext *Ctx); + til::SExpr *translateBinaryOperator(const BinaryOperator *BO, + CallingContext *Ctx); + til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); + til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, + CallingContext *Ctx); + til::SExpr *translateConditionalOperator(const ConditionalOperator *C, + CallingContext *Ctx); + til::SExpr *translateBinaryConditionalOperator( + const BinaryConditionalOperator *C, CallingContext *Ctx); + + + SExprBuilder(til::MemRegionRef A, StatementMap *SM = 0) + : Arena(A), SMap(SM), SelfVar(0) { + // FIXME: we don't always have a self-variable. + SelfVar = new (Arena) til::Variable(til::Variable::VK_SFun); + } + +protected: + til::MemRegionRef Arena; + StatementMap *SMap; // Map from Stmt to TIL Variables + til::Variable *SelfVar; // Variable to use for 'this' +}; + + +// Dump an SCFG to llvm::errs(). +void printSCFG(CFGWalker &walker); + + +} // end namespace threadSafety + +} // end namespace clang diff --git a/include/clang/Analysis/Analyses/ThreadSafetyOps.def b/include/clang/Analysis/Analyses/ThreadSafetyOps.def new file mode 100644 index 0000000000..b33e2e8bf6 --- /dev/null +++ b/include/clang/Analysis/Analyses/ThreadSafetyOps.def @@ -0,0 +1,44 @@ +//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the list of core opcodes for the Thread Safety +// Typed Intermediate language. Please see ThreadSafetyTIL.h for more +// information. +// +//===----------------------------------------------------------------------===// + + +TIL_OPCODE_DEF(Future) +TIL_OPCODE_DEF(Undefined) +TIL_OPCODE_DEF(Wildcard) + +TIL_OPCODE_DEF(Literal) +TIL_OPCODE_DEF(LiteralPtr) +TIL_OPCODE_DEF(Variable) +TIL_OPCODE_DEF(Function) +TIL_OPCODE_DEF(SFunction) +TIL_OPCODE_DEF(Code) + +TIL_OPCODE_DEF(Apply) +TIL_OPCODE_DEF(SApply) +TIL_OPCODE_DEF(Project) + +TIL_OPCODE_DEF(Call) +TIL_OPCODE_DEF(Alloc) +TIL_OPCODE_DEF(Load) +TIL_OPCODE_DEF(Store) + +TIL_OPCODE_DEF(UnaryOp) +TIL_OPCODE_DEF(BinaryOp) +TIL_OPCODE_DEF(Cast) + +TIL_OPCODE_DEF(SCFG) +TIL_OPCODE_DEF(Phi) +TIL_OPCODE_DEF(Goto) +TIL_OPCODE_DEF(Branch) diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h new file mode 100644 index 0000000000..782faf6976 --- /dev/null +++ b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -0,0 +1,1831 @@ +//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a simple intermediate language that is used by the +// thread safety analysis (See ThreadSafety.cpp). The thread safety analysis +// works by comparing mutex expressions, e.g. +// +// class A { Mutex mu; int dat GUARDED_BY(this->mu); } +// class B { A a; } +// +// void foo(B* b) { +// (*b).a.mu.lock(); // locks (*b).a.mu +// b->a.dat = 0; // substitute &b->a for 'this'; +// // requires lock on (&b->a)->mu +// (b->a.mu).unlock(); // unlocks (b->a.mu) +// } +// +// As illustrated by the above example, clang Exprs are not well-suited to +// represent mutex expressions directly, since there is no easy way to compare +// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs +// into a simple intermediate language (IL). The IL supports: +// +// (1) comparisons for semantic equality of expressions +// (2) SSA renaming of variables +// (3) wildcards and pattern matching over expressions +// (4) hash-based expression lookup +// +// The IL is currently very experimental, is intended only for use within +// the thread safety analysis, and is subject to change without notice. +// After the API stabilizes and matures, it may be appropriate to make this +// more generally available to other analyses. +// +// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H +#define LLVM_CLANG_THREAD_SAFETY_TIL_H + +#include "clang/AST/DeclCXX.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/StmtCXX.h" +#include "clang/AST/Type.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/AlignOf.h" +#include "llvm/Support/Allocator.h" + +#include <cassert> +#include <cstddef> + +namespace clang { +namespace threadSafety { +namespace til { + + +// Simple wrapper class to abstract away from the details of memory management. +// SExprs are allocated in pools, and deallocated all at once. +class MemRegionRef { +private: + union AlignmentType { + double d; + void *p; + long double dd; + long long ii; + }; + +public: + MemRegionRef() : Allocator(0) {} + MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} + + void *allocate(size_t Sz) { + return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment); + } + + template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } + + template <typename T> T *allocateT(size_t NumElems) { + return Allocator->Allocate<T>(NumElems); + } + +private: + llvm::BumpPtrAllocator *Allocator; +}; + + +} // end namespace til +} // end namespace threadSafety +} // end namespace clang + + +inline void *operator new(size_t Sz, + clang::threadSafety::til::MemRegionRef &R) { + return R.allocate(Sz); +} + + +namespace clang { +namespace threadSafety { +namespace til { + +using llvm::StringRef; + +// A simple fixed size array class that does not manage its own memory, +// suitable for use with bump pointer allocation. +template <class T> class SimpleArray { +public: + SimpleArray() : Data(0), Size(0), Capacity(0) {} + SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) + : Data(Dat), Size(0), Capacity(Cp) {} + SimpleArray(MemRegionRef A, size_t Cp) + : Data(A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} + SimpleArray(SimpleArray<T> &A, bool Steal) + : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { + A.Data = 0; + A.Size = 0; + A.Capacity = 0; + } + + T *resize(size_t Ncp, MemRegionRef A) { + T *Odata = Data; + Data = A.allocateT<T>(Ncp); + memcpy(Data, Odata, sizeof(T) * Size); + return Odata; + } + + typedef T *iterator; + typedef const T *const_iterator; + + size_t size() const { return Size; } + size_t capacity() const { return Capacity; } + + T &operator[](unsigned I) { return Data[I]; } + const T &operator[](unsigned I) const { return Data[I]; } + + iterator begin() { return Data; } + iterator end() { return Data + Size; } + + const_iterator cbegin() const { return Data; } + const_iterator cend() const { return Data + Size; } + + void push_back(const T &Elem) { + assert(Size < Capacity); + Data[Size++] = Elem; + } + + template <class Iter> unsigned append(Iter I, Iter E) { + size_t Osz = Size; + size_t J = Osz; + for (; J < Capacity && I != E; ++J, ++I) + Data[J] = *I; + Size = J; + return J - Osz; + } + +private: + T *Data; + size_t Size; + size_t Capacity; +}; + + +enum TIL_Opcode { +#define TIL_OPCODE_DEF(X) COP_##X, +#include "clang/Analysis/Analyses/ThreadSafetyOps.def" +#undef TIL_OPCODE_DEF + COP_MAX +}; + + +typedef clang::BinaryOperatorKind TIL_BinaryOpcode; +typedef clang::UnaryOperatorKind TIL_UnaryOpcode; +typedef clang::CastKind TIL_CastOpcode; + + +enum TIL_TraversalKind { + TRV_Normal, + TRV_Lazy, // subexpression may need to be traversed lazily + TRV_Tail // subexpression occurs in a tail position +}; + + +// Base class for AST nodes in the typed intermediate language. +class SExpr { +public: + TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } + + // Subclasses of SExpr must define the following: + // + // This(const This& E, ...) { + // copy constructor: construct copy of E, with some additional arguments. + // } + // + // template <class V> typename V::R_SExpr traverse(V &Visitor) { + // traverse all subexpressions, following the traversal/rewriter interface + // } + // + // template <class C> typename C::CType compare(CType* E, C& Cmp) { + // compare all subexpressions, following the comparator interface + // } + +protected: + SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {} + SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {} + + const unsigned char Opcode; + unsigned char Reserved; + unsigned short Flags; + +private: + SExpr(); +}; + +typedef SExpr* SExprRef; + + +// Contains various helper functions for SExprs. +class ThreadSafetyTIL { +public: + static const int MaxOpcode = COP_MAX; + + static inline bool isTrivial(SExpr *E) { + unsigned Op = E->opcode(); + return Op == COP_Variable || Op == COP_Literal; + } + + static inline bool isLargeValue(SExpr *E) { + unsigned Op = E->opcode(); + return (Op >= COP_Function && Op <= COP_Code); + } +}; + + +// Placeholder for an expression that has not yet been created. +// Used to implement lazy copy and rewriting strategies. +class Future : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } + + enum FutureStatus { + FS_pending, + FS_evaluating, + FS_done + }; + + Future() : SExpr(COP_Future), Status(FS_pending), Result(0), Location(0) {} + virtual ~Future() {} + + // Registers the location in the AST where this future is stored. + // Forcing the future will automatically update the AST. + static inline void registerLocation(SExpr **Member) { + if (Future *F = dyn_cast_or_null<Future>(*Member)) + F->Location = Member; + } + + // A lazy rewriting strategy should subclass Future and override this method. + virtual SExpr *create() { return 0; } + + // Return the result of this future if it exists, otherwise return null. + SExpr *maybeGetResult() { + return Result; + } + + // Return the result of this future; forcing it if necessary. + SExpr *result() { + switch (Status) { + case FS_pending: + force(); + return Result; + case FS_evaluating: + return 0; // infinite loop; illegal recursion. + case FS_done: + return Result; + } + } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + assert(Result && "Cannot traverse Future that has not been forced."); + return Visitor.traverse(Result); + } + + template <class C> typename C::CType compare(Future* E, C& Cmp) { + if (!Result || !E->Result) + return Cmp.comparePointers(this, E); + return Cmp.compare(Result, E->Result); + } + +private: + // Force the future. + void force() { + Status = FS_evaluating; + SExpr *R = create(); + Result = R; + if (Location) { + *Location = R; + } + Status = FS_done; + } + + FutureStatus Status; + SExpr *Result; + SExpr **Location; +}; + + +// Placeholder for C++ expressions that cannot be represented in the TIL. +class Undefined : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } + + Undefined(const clang::Stmt *S = 0) : SExpr(COP_Undefined), Cstmt(S) {} + Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + return Visitor.reduceUndefined(*this); + } + + template <class C> typename C::CType compare(Undefined* E, C& Cmp) { + return Cmp.comparePointers(Cstmt, E->Cstmt); + } + +private: + const clang::Stmt *Cstmt; +}; + + +// Placeholder for a wildcard that matches any other expression. +class Wildcard : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } + + Wildcard() : SExpr(COP_Wildcard) {} + Wildcard(const Wildcard &W) : SExpr(W) {} + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + return Visitor.reduceWildcard(*this); + } + + template <class C> typename C::CType compare(Wildcard* E, C& Cmp) { + return Cmp.trueResult(); + } +}; + + +// Base class for literal values. +class Literal : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } + + Literal(const clang::Expr *C) : SExpr(COP_Literal), Cexpr(C) {} + Literal(const Literal &L) : SExpr(L), Cexpr(L.Cexpr) {} + + // The clang expression for this literal. + const clang::Expr *clangExpr() { return Cexpr; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + return Visitor.reduceLiteral(*this); + } + + template <class C> typename C::CType compare(Literal* E, C& Cmp) { + // TODO -- use value, not pointer equality + return Cmp.comparePointers(Cexpr, E->Cexpr); + } + +private: + const clang::Expr *Cexpr; +}; + + +// Literal pointer to an object allocated in memory. +// At compile time, pointer literals are represented by symbolic names. +class LiteralPtr : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } + + LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} + LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} + + // The clang declaration for the value that this pointer points to. + const clang::ValueDecl *clangDecl() { return Cvdecl; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + return Visitor.reduceLiteralPtr(*this); + } + + template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) { + return Cmp.comparePointers(Cvdecl, E->Cvdecl); + } + +private: + const clang::ValueDecl *Cvdecl; +}; + + +// A named variable, e.g. "x". +// +// There are two distinct places in which a Variable can appear in the AST. +// A variable declaration introduces a new variable, and can occur in 3 places: +// Let-expressions: (Let (x = t) u) +// Functions: (Function (x : t) u) +// Self-applicable functions (SFunction (x) t) +// +// If a variable occurs in any other location, it is a reference to an existing +// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't +// allocate a separate AST node for variable references; a reference is just a +// pointer to the original declaration. +class Variable : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } + + // Let-variable, function parameter, or self-variable + enum VariableKind { + VK_Let, + VK_Fun, + VK_SFun + }; + + Variable(VariableKind K, SExpr *D = 0, const clang::ValueDecl *Cvd = 0) + : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd), + BlockID(0), Id(0), NumUses(0) { + Flags = K; + Future::registerLocation(&Definition); + } + Variable(const clang::ValueDecl *Cvd, SExpr *D = 0) + : SExpr(COP_Variable), Definition(D), Cvdecl(Cvd), + BlockID(0), Id(0), NumUses(0) { + Flags = VK_Let; + Future::registerLocation(&Definition); + } + Variable(const Variable &Vd, SExpr *D) // rewrite constructor + : SExpr(Vd), Definition(D), Cvdecl(Vd.Cvdecl), + BlockID(0), Id(0), NumUses(0) { + Flags = Vd.kind(); + Future::registerLocation(&Definition); + } + + VariableKind kind() const { return static_cast<VariableKind>(Flags); } + + StringRef name() const { return Cvdecl ? Cvdecl->getName() : "_x"; } + const clang::ValueDecl *clangDecl() const { return Cvdecl; } + + // Returns the definition (for let vars) or type (for parameter & self vars) + SExpr *definition() const { return Definition; } + + void attachVar() const { ++NumUses; } + void detachVar() const { --NumUses; } + + unsigned getID() { return Id; } + unsigned getBlockID() { return BlockID; } + + void setID(unsigned Bid, unsigned I) { + BlockID = static_cast<unsigned short>(Bid); + Id = static_cast<unsigned short>(I); + } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + // This routine is only called for variable references. + return Visitor.reduceVariableRef(this); + } + + template <class C> typename C::CType compare(Variable* E, C& Cmp) { + return Cmp.compareVariableRefs(this, E); + } + +private: + friend class Function; + friend class SFunction; + friend class BasicBlock; + + // Function, SFunction, and BasicBlock will reset the kind. + void setKind(VariableKind K) { Flags = K; } + + SExpr *Definition; // The TIL type or definition + const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. + + unsigned short BlockID; + unsigned short Id; + mutable int NumUses; +}; + + +// A function -- a.k.a. lambda abstraction. +// Functions with multiple arguments are created by currying, +// e.g. (function (x: Int) (function (y: Int) (add x y))) +class Function : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } + + Function(Variable *Vd, SExpr *Bd) + : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { + Vd->setKind(Variable::VK_Fun); + } + Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor + : SExpr(F), VarDecl(Vd), Body(Bd) { + Vd->setKind(Variable::VK_Fun); + } + + Variable *variableDecl() const { return VarDecl; } + SExpr *body() const { return Body; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + // This is a variable declaration, so traverse the definition. + typename V::R_SExpr E0 = Visitor.traverse(VarDecl->Definition, TRV_Lazy); + // Tell the rewriter to enter the scope of the function. + Variable *Nvd = Visitor.enterScope(*VarDecl, E0); + typename V::R_SExpr E1 = Visitor.traverse(Body); + Visitor.exitScope(*VarDecl); + return Visitor.reduceFunction(*this, Nvd, E1); + } + + template <class C> typename C::CType compare(Function* E, C& Cmp) { + typename C::CType Ct = + Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); + if (Cmp.notTrue(Ct)) + return Ct; + Cmp.enterScope(VarDecl, E->VarDecl); + Ct = Cmp.compare(Body, E->Body); + Cmp.leaveScope(); + return Ct; + } + +private: + Variable *VarDecl; + SExpr *Body; +}; + + +// A self-applicable function. +// A self-applicable function can be applied to itself. It's useful for +// implementing objects and late binding +class SFunction : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } + + SFunction(Variable *Vd, SExpr *B) + : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { + assert(Vd->Definition == 0); + Vd->setKind(Variable::VK_SFun); + Vd->Definition = this; + } + SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor + : SExpr(F), + VarDecl(Vd), + Body(B) { + assert(Vd->Definition == 0); + Vd->setKind(Variable::VK_SFun); + Vd->Definition = this; + } + + Variable *variableDecl() const { return VarDecl; } + SExpr *body() const { return Body; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + // A self-variable points to the SFunction itself. + // A rewrite must introduce the variable with a null definition, and update + // it after 'this' has been rewritten. + Variable *Nvd = Visitor.enterScope(*VarDecl, 0 /* def */); + typename V::R_SExpr E1 = Visitor.traverse(Body); + Visitor.exitScope(*VarDecl); + // A rewrite operation will call SFun constructor to set Vvd->Definition. + return Visitor.reduceSFunction(*this, Nvd, E1); + } + + template <class C> typename C::CType compare(SFunction* E, C& Cmp) { + Cmp.enterScope(VarDecl, E->VarDecl); + typename C::CType Ct = Cmp.compare(Body, E->Body); + Cmp.leaveScope(); + return Ct; + } + +private: + Variable *VarDecl; + SExpr *Body; +}; + + +// A block of code -- e.g. the body of a function. +class Code : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } + + Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) { + Future::registerLocation(&ReturnType); + Future::registerLocation(&Body); + } + Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor + : SExpr(C), + ReturnType(T), + Body(B) { + Future::registerLocation(&ReturnType); + Future::registerLocation(&Body); + } + + SExpr *returnType() { return ReturnType; } + SExpr *body() { return Body; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nt = Visitor.traverse(ReturnType, TRV_Lazy); + typename V::R_SExpr Nb = Visitor.traverse(Body, TRV_Lazy); + return Visitor.reduceCode(*this, Nt, Nb); + } + + template <class C> typename C::CType compare(Code* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(ReturnType, E->ReturnType); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Body, E->Body); + } + +private: + SExpr *ReturnType; + SExpr *Body; +}; + + +// Apply an argument to a function +class Apply : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } + + Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} + Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor + : SExpr(A), Fun(F), Arg(Ar) + {} + + SExpr *fun() const { return Fun; } + SExpr *arg() const { return Arg; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nf = Visitor.traverse(Fun); + typename V::R_SExpr Na = Visitor.traverse(Arg); + return Visitor.reduceApply(*this, Nf, Na); + } + + template <class C> typename C::CType compare(Apply* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(Fun, E->Fun); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Arg, E->Arg); + } + +private: + SExpr *Fun; + SExpr *Arg; +}; + + +// Apply a self-argument to a self-applicable function +class SApply : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } + + SApply(SExpr *Sf, SExpr *A = 0) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} + SApply(SApply &A, SExpr *Sf, SExpr *Ar = 0) // rewrite constructor + : SExpr(A), Sfun(Sf), Arg(Ar) + {} + + SExpr *sfun() const { return Sfun; } + SExpr *arg() const { return Arg ? Arg : Sfun; } + + bool isDelegation() const { return Arg == 0; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nf = Visitor.traverse(Sfun); + typename V::R_SExpr Na = Arg ? Visitor.traverse(Arg) : 0; + return Visitor.reduceSApply(*this, Nf, Na); + } + + template <class C> typename C::CType compare(SApply* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(Sfun, E->Sfun); + if (Cmp.notTrue(Ct) || (!Arg && !E->Arg)) + return Ct; + return Cmp.compare(arg(), E->arg()); + } + +private: + SExpr *Sfun; + SExpr *Arg; +}; + + +// Project a named slot from a C++ struct or class. +class Project : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } + + Project(SExpr *R, clang::ValueDecl *Cvd) + : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {} + Project(const Project &P, SExpr *R) : SExpr(P), Rec(R), Cvdecl(P.Cvdecl) {} + + SExpr *record() const { return Rec; } + clang::ValueDecl *clangValueDecl() const { return Cvdecl; } + + StringRef slotName() const { return Cvdecl->getName(); } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nr = Visitor.traverse(Rec); + return Visitor.reduceProject(*this, Nr); + } + + template <class C> typename C::CType compare(Project* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(Rec, E->Rec); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.comparePointers(Cvdecl, E->Cvdecl); + } + +private: + SExpr *Rec; + clang::ValueDecl *Cvdecl; +}; + + +// Call a function (after all arguments have been applied). +class Call : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } + + Call(SExpr *T, const clang::CallExpr *Ce = 0) + : SExpr(COP_Call), Target(T), Cexpr(Ce) {} + Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} + + SExpr *target() const { return Target; } + const clang::CallExpr *clangCallExpr() { return Cexpr; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nt = Visitor.traverse(Target); + return Visitor.reduceCall(*this, Nt); + } + + template <class C> typename C::CType compare(Call* E, C& Cmp) { + return Cmp.compare(Target, E->Target); + } + +private: + SExpr *Target; + const clang::CallExpr *Cexpr; +}; + + +// Allocate memory for a new value on the heap or stack. +class Alloc : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } + + enum AllocKind { + AK_Stack, + AK_Heap + }; + + Alloc(SExpr* D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { + Flags = K; + } + Alloc(const Alloc &A, SExpr* Dt) : SExpr(A), Dtype(Dt) { + Flags = A.kind(); + } + + AllocKind kind() const { return static_cast<AllocKind>(Flags); } + SExpr* dataType() const { return Dtype; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nd = Visitor.traverse(Dtype); + return Visitor.reduceAlloc(*this, Nd); + } + + template <class C> typename C::CType compare(Alloc* E, C& Cmp) { + typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Dtype, E->Dtype); + } + +private: + SExpr* Dtype; +}; + + +// Load a value from memory. +class Load : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } + + Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} + Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} + + SExpr *pointer() { return Ptr; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Np = Visitor.traverse(Ptr); + return Visitor.reduceLoad(*this, Np); + } + + template <class C> typename C::CType compare(Load* E, C& Cmp) { + return Cmp.compare(Ptr, E->Ptr); + } + +private: + SExpr *Ptr; +}; + + +// Store a value to memory. +class Store : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } + + Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Ptr(P) {} + Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Ptr(P) {} + + SExpr *pointer() const { return Ptr; } + SExpr *value() const { return Value; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Np = Visitor.traverse(Ptr); + typename V::R_SExpr Nv = Visitor.traverse(Value); + return Visitor.reduceStore(*this, Np, Nv); + } + + template <class C> typename C::CType compare(Store* E, C& Cmp) { + typename C::CType Ct = Cmp.compare(Ptr, E->Ptr); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Value, E->Value); + } + + SExpr *Ptr; + SExpr *Value; +}; + + +// Simple unary operation -- e.g. !, ~, etc. +class UnaryOp : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } + + UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { + Flags = Op; + } + UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U) { Flags = U.Flags; } + + TIL_UnaryOpcode unaryOpcode() { return static_cast<TIL_UnaryOpcode>(Flags); } + + SExpr *expr() const { return Expr0; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Ne = Visitor.traverse(Expr0); + return Visitor.reduceUnaryOp(*this, Ne); + } + + template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) { + typename C::CType Ct = + Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Expr0, E->Expr0); + } + +private: + SExpr *Expr0; +}; + + +// Simple binary operation -- e.g. +, -, etc. +class BinaryOp : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } + + BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) + : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { + Flags = Op; + } + BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) + : SExpr(B), Expr0(E0), Expr1(E1) { + Flags = B.Flags; + } + + TIL_BinaryOpcode binaryOpcode() { + return static_cast<TIL_BinaryOpcode>(Flags); + } + + SExpr *expr0() const { return Expr0; } + SExpr *expr1() const { return Expr1; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Ne0 = Visitor.traverse(Expr0); + typename V::R_SExpr Ne1 = Visitor.traverse(Expr1); + return Visitor.reduceBinaryOp(*this, Ne0, Ne1); + } + + template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) { + typename C::CType Ct = + Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); + if (Cmp.notTrue(Ct)) + return Ct; + Ct = Cmp.compare(Expr0, E->Expr0); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Expr1, E->Expr1); + } + +private: + SExpr *Expr0; + SExpr *Expr1; +}; + + +// Cast expression +class Cast : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } + + Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } + Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } + + TIL_BinaryOpcode castOpcode() { return static_cast<TIL_BinaryOpcode>(Flags); } + + SExpr *expr() const { return Expr0; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Ne = Visitor.traverse(Expr0); + return Visitor.reduceCast(*this, Ne); + } + + template <class C> typename C::CType compare(Cast* E, C& Cmp) { + typename C::CType Ct = + Cmp.compareIntegers(castOpcode(), E->castOpcode()); + if (Cmp.notTrue(Ct)) + return Ct; + return Cmp.compare(Expr0, E->Expr0); + } + +private: + SExpr *Expr0; +}; + + + + +class BasicBlock; + + +// An SCFG is a control-flow graph. It consists of a set of basic blocks, each +// of which terminates in a branch to another basic block. There is one +// entry point, and one exit point. +class SCFG : public SExpr { +public: + typedef SimpleArray<BasicBlock*> BlockArray; + + static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } + + SCFG(MemRegionRef A, unsigned Nblocks) + : SExpr(COP_SCFG), Blocks(A, Nblocks), Entry(0), Exit(0) {} + SCFG(const SCFG &Cfg, BlockArray &Ba) // steals memory from ba + : SExpr(COP_SCFG), + Blocks(Ba, true), + Entry(0), + Exit(0) { /* TODO: set entry and exit! */ + } + + typedef BlockArray::iterator iterator; + typedef BlockArray::const_iterator const_iterator; + + iterator begin() { return Blocks.begin(); } + iterator end() { return Blocks.end(); } + + const_iterator cbegin() const { return Blocks.cbegin(); } + const_iterator cend() const { return Blocks.cend(); } + + BasicBlock *entry() const { return Entry; } + BasicBlock *exit() const { return Exit; } + + void add(BasicBlock *BB) { Blocks.push_back(BB); } + void setEntry(BasicBlock *BB) { Entry = BB; } + void setExit(BasicBlock *BB) { Exit = BB; } + + template <class V> typename V::R_SExpr traverse(V &Visitor); + + template <class C> typename C::CType compare(SCFG* E, C& Cmp) { + // TODO -- implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + BlockArray Blocks; + BasicBlock *Entry; + BasicBlock *Exit; +}; + + +// A basic block is part of an SCFG, and can be treated as a function in +// continuation passing style. It consists of a sequence of phi nodes, which +// are "arguments" to the function, followed by a sequence of instructions. +// Both arguments and instructions define new variables. It ends with a +// branch or goto to another basic block in the same SCFG. +class BasicBlock { +public: + typedef SimpleArray<Variable*> VarArray; + + BasicBlock(MemRegionRef A, unsigned Nargs, unsigned Nins, SExpr *Term = 0) + : BlockID(0), Parent(0), Args(A, Nargs), Instrs(A, Nins), + Terminator(Term) {} + BasicBlock(const BasicBlock &B, VarArray &As, VarArray &Is, SExpr *T) + : BlockID(0), Parent(0), Args(As, true), Instrs(Is, true), Terminator(T) + {} + + unsigned blockID() const { return BlockID; } + BasicBlock *parent() const { return Parent; } + + const VarArray &arguments() const { return Args; } + VarArray &arguments() { return Args; } + + const VarArray &instructions() const { return Instrs; } + VarArray &instructions() { return Instrs; } + + const SExpr *terminator() const { return Terminator; } + SExpr *terminator() { return Terminator; } + + void setParent(BasicBlock *P) { Parent = P; } + void setBlockID(unsigned i) { BlockID = i; } + void setTerminator(SExpr *E) { Terminator = E; } + void addArgument(Variable *V) { Args.push_back(V); } + void addInstr(Variable *V) { Args.push_back(V); } + + template <class V> BasicBlock *traverse(V &Visitor) { + typename V::template Container<Variable*> Nas(Visitor, Args.size()); + typename V::template Container<Variable*> Nis(Visitor, Instrs.size()); + + for (unsigned I = 0; I < Args.size(); ++I) { + typename V::R_SExpr Ne = Visitor.traverse(Args[I]->Definition); + Variable *Nvd = Visitor.enterScope(*Args[I], Ne); + Nas.push_back(Nvd); + } + for (unsigned J = 0; J < Instrs.size(); ++J) { + typename V::R_SExpr Ne = Visitor.traverse(Instrs[J]->Definition); + Variable *Nvd = Visitor.enterScope(*Instrs[J], Ne); + Nis.push_back(Nvd); + } + typename V::R_SExpr Nt = Visitor.traverse(Terminator); + + for (unsigned J = 0, JN = Instrs.size(); J < JN; ++J) + Visitor.exitScope(*Instrs[JN-J]); + for (unsigned I = 0, IN = Instrs.size(); I < IN; ++I) + Visitor.exitScope(*Args[IN-I]); + + return Visitor.reduceBasicBlock(*this, Nas, Nis, Nt); + } + + template <class C> typename C::CType compare(BasicBlock* E, C& Cmp) { + // TODO -- implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + friend class SCFG; + + unsigned BlockID; + BasicBlock *Parent; // The parent block is the enclosing lexical scope. + // The parent dominates this block. + VarArray Args; // Phi nodes + VarArray Instrs; + SExpr *Terminator; +}; + + +template <class V> +typename V::R_SExpr SCFG::traverse(V &Visitor) { + Visitor.enterCFG(*this); + typename V::template Container<BasicBlock *> Bbs(Visitor, Blocks.size()); + for (unsigned I = 0; I < Blocks.size(); ++I) { + BasicBlock *Nbb = Blocks[I]->traverse(Visitor); + Bbs.push_back(Nbb); + } + Visitor.exitCFG(*this); + return Visitor.reduceSCFG(*this, Bbs); +} + + + +class Phi : public SExpr { +public: + typedef SimpleArray<SExpr *> ValArray; + + static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } + + Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} + Phi(const Phi &P, ValArray &Vs) // steals memory of vs + : SExpr(COP_Phi), Values(Vs, true) {} + + const ValArray &values() const { return Values; } + ValArray &values() { return Values; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::template Container<typename V::R_SExpr> Nvs(Visitor, + Values.size()); + for (ValArray::iterator I = Values.begin(), E = Values.end(); I != E; ++I) { + typename V::R_SExpr Nv = Visitor.traverse(*I); + Nvs.push_back(Nv); + } + return Visitor.reducePhi(*this, Nvs); + } + + template <class C> typename C::CType compare(Phi* E, C& Cmp) { + // TODO -- implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + ValArray Values; +}; + + +class Goto : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } + + Goto(BasicBlock *B, unsigned Index) + : SExpr(COP_Goto), TargetBlock(B) {} + Goto(const Goto &G, BasicBlock *B, unsigned Index) + : SExpr(COP_Goto), TargetBlock(B) {} + + BasicBlock *targetBlock() const { return TargetBlock; } + unsigned index() const { return Index; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + // TODO -- rewrite indices properly + BasicBlock *Ntb = Visitor.reduceBasicBlockRef(TargetBlock); + return Visitor.reduceGoto(*this, Ntb, Index); + } + + template <class C> typename C::CType compare(Goto* E, C& Cmp) { + // TODO -- implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + BasicBlock *TargetBlock; + unsigned Index; // Index into Phi nodes of target block. +}; + + +class Branch : public SExpr { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } + + Branch(SExpr *C, BasicBlock *T, BasicBlock *E) + : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {} + Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) + : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E) {} + + SExpr *condition() { return Condition; } + BasicBlock *thenBlock() { return ThenBlock; } + BasicBlock *elseBlock() { return ElseBlock; } + + template <class V> typename V::R_SExpr traverse(V &Visitor) { + typename V::R_SExpr Nc = Visitor.traverse(Condition); + BasicBlock *Ntb = Visitor.reduceBasicBlockRef(ThenBlock); + BasicBlock *Nte = Visitor.reduceBasicBlockRef(ElseBlock); + return Visitor.reduceBranch(*this, Nc, Ntb, Nte); + } + + template <class C> typename C::CType compare(Branch* E, C& Cmp) { + // TODO -- implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + SExpr *Condition; + BasicBlock *ThenBlock; + BasicBlock *ElseBlock; +}; + + + +// Defines an interface used to traverse SExprs. Traversals have been made as +// generic as possible, and are intended to handle any kind of pass over the +// AST, e.g. visiters, copying, non-destructive rewriting, destructive +// (in-place) rewriting, hashing, typing, etc. +// +// Traversals implement the functional notion of a "fold" operation on SExprs. +// Each SExpr class provides a traverse method, which does the following: +// * e->traverse(v): +// // compute a result r_i for each subexpression e_i +// for (i = 1..n) r_i = v.traverse(e_i); +// // combine results into a result for e, where X is the class of e +// return v.reduceX(*e, r_1, .. r_n). +// +// A visitor can control the traversal by overriding the following methods: +// * v.traverse(e): +// return v.traverseByCase(e), which returns v.traverseX(e) +// * v.traverseX(e): (X is the class of e) +// return e->traverse(v). +// * v.reduceX(*e, r_1, .. r_n): +// compute a result for a node of type X +// +// The reduceX methods control the kind of traversal (visitor, copy, etc.). +// These are separated into a separate class R for the purpose of code reuse. +// The full reducer interface also has methods to handle scopes +template <class Self, class R> class TILTraversal : public R { +public: + Self *self() { return reinterpret_cast<Self *>(this); } + + // Traverse an expression -- returning a result of type R_SExpr. + // Override this method to do something for every expression, regardless + // of which kind it is. TIL_TraversalKind indicates the context in which + // the expression occurs, and can be: + // TRV_Normal + // TRV_Lazy -- e may need to be traversed lazily, using a Future. + // TRV_Tail -- e occurs in a tail position + typename R::R_SExpr traverse(SExpr *E, TIL_TraversalKind K = TRV_Normal) { + return traverseByCase(E); + } + + // Helper method to call traverseX(e) on the appropriate type. + typename R::R_SExpr traverseByCase(SExpr *E) { + switch (E->opcode()) { +#define TIL_OPCODE_DEF(X) \ + case COP_##X: \ + return self()->traverse##X(cast<X>(E)); +#include "clang/Analysis/Analyses/ThreadSafetyOps.def" +#undef TIL_OPCODE_DEF + case COP_MAX: + return self()->reduceNull(); + } + } + +// Traverse e, by static dispatch on the type "X" of e. +// Override these methods to do something for a particular kind of term. +#define TIL_OPCODE_DEF(X) \ + typename R::R_SExpr traverse##X(X *e) { return e->traverse(*self()); } +#include "clang/Analysis/Analyses/ThreadSafetyOps.def" +#undef TIL_OPCODE_DEF +}; + + +// Implements a Reducer that makes a deep copy of an SExpr. +// The default behavior of reduce##X(...) is to create a copy of the original. +// Subclasses can override reduce##X to implement non-destructive rewriting +// passes. +class TILCopyReducer { +public: + TILCopyReducer() {} + + void setArena(MemRegionRef A) { Arena = A; } + + // R_SExpr is the result type for a traversal. + // A copy or non-destructive rewrite returns a newly allocated term. + typedef SExpr *R_SExpr; + + // Container is a minimal interface used to store results when traversing + // SExprs of variable arity, such as Phi, Goto, and SCFG. + template <class T> class Container { + public: + // Allocate a new container with a capacity for n elements. + Container(TILCopyReducer &R, unsigned N) : Elems(R.Arena, N) {} + + // Push a new element onto the container. + void push_back(T E) { Elems.push_back(E); } + + private: + friend class TILCopyReducer; + SimpleArray<T> Elems; + }; + +public: + R_SExpr reduceNull() { + return 0; + } + // R_SExpr reduceFuture(...) is never used. + + R_SExpr reduceUndefined(Undefined &Orig) { + return new (Arena) Undefined(Orig); + } + R_SExpr reduceWildcard(Wildcard &Orig) { + return new (Arena) Wildcard(Orig); + } + + R_SExpr reduceLiteral(Literal &Orig) { + return new (Arena) Literal(Orig); + } + R_SExpr reduceLiteralPtr(LiteralPtr &Orig) { + return new (Arena) LiteralPtr(Orig); + } + + R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { + return new (Arena) Function(Orig, Nvd, E0); + } + R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) { + return new (Arena) SFunction(Orig, Nvd, E0); + } + R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) Code(Orig, E0, E1); + } + + R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) Apply(Orig, E0, E1); + } + R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) SApply(Orig, E0, E1); + } + R_SExpr reduceProject(Project &Orig, R_SExpr E0) { + return new (Arena) Project(Orig, E0); + } + R_SExpr reduceCall(Call &Orig, R_SExpr E0) { + return new (Arena) Call(Orig, E0); + } + + R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { + return new (Arena) Alloc(Orig, E0); + } + R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { + return new (Arena) Load(Orig, E0); + } + R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) Store(Orig, E0, E1); + } + R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { + return new (Arena) UnaryOp(Orig); + } + R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) { + return new (Arena) BinaryOp(Orig, E0, E1); + } + R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { + return new (Arena) Cast(Orig, E0); + } + + R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { + return new (Arena) SCFG(Orig, Bbs.Elems); + } + R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> As) { + return new (Arena) Phi(Orig, As.Elems); + } + R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, unsigned Index) { + return new (Arena) Goto(Orig, B, Index); + } + R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { + return new (Arena) Branch(O, C, B0, B1); + } + + BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As, + Container<Variable *> &Is, R_SExpr T) { + return new (Arena) BasicBlock(Orig, As.Elems, Is.Elems, T); + } + + // Create a new variable from orig, and push it onto the lexical scope. + Variable *enterScope(Variable &Orig, R_SExpr E0) { + return new (Arena) Variable(Orig, E0); + } + // Exit the lexical scope of orig. + void exitScope(const Variable &Orig) {} + + void enterCFG(SCFG &Cfg) {} + void exitCFG(SCFG &Cfg) {} + + // Map Variable references to their rewritten definitions. + Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } + + // Map BasicBlock references to their rewritten defs. + BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } + +private: + MemRegionRef Arena; +}; + + +class SExprCopier : public TILTraversal<SExprCopier, TILCopyReducer> { +public: + SExprCopier(MemRegionRef A) { setArena(A); } + + // Create a copy of e in region a. + static SExpr *copy(SExpr *E, MemRegionRef A) { + SExprCopier Copier(A); + return Copier.traverse(E); + } +}; + + +// Implements a Reducer that visits each subexpression, and returns either +// true or false. +class TILVisitReducer { +public: + TILVisitReducer() {} + + // A visitor returns a bool, representing success or failure. + typedef bool R_SExpr; + + // A visitor "container" is a single bool, which accumulates success. + template <class T> class Container { + public: + Container(TILVisitReducer &R, unsigned N) : Success(true) {} + void push_back(bool E) { Success = Success && E; } + + private: + friend class TILVisitReducer; + bool Success; + }; + +public: + R_SExpr reduceNull() { return true; } + R_SExpr reduceUndefined(Undefined &Orig) { return true; } + R_SExpr reduceWildcard(Wildcard &Orig) { return true; } + + R_SExpr reduceLiteral(Literal &Orig) { return true; } + R_SExpr reduceLiteralPtr(Literal &Orig) { return true; } + + R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { + return Nvd && E0; + } + R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) { + return Nvd && E0; + } + R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) { + return E0 && E1; + } + R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) { + return E0 && E1; + } + R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) { + return E0 && E1; + } + R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } + R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; } + R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) { + return E0 && E1; + } + R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; } + + R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { + return Bbs.Success; + } + R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> As) { + return As.Success; + } + R_SExpr reduceGoto(Goto &Orig, BasicBlock *B, Container<R_SExpr> As) { + return As.Success; + } + R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { + return C; + } + + BasicBlock *reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As, + Container<Variable *> &Is, R_SExpr T) { + return (As.Success && Is.Success && T) ? &Orig : 0; + } + + Variable *enterScope(Variable &Orig, R_SExpr E0) { return E0 ? &Orig : 0; } + void exitScope(const Variable &Orig) {} + + void enterCFG(SCFG &Cfg) {} + void exitCFG(SCFG &Cfg) {} + + Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } + + BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } +}; + + +// A visitor will visit each node, and halt if any reducer returns false. +template <class Self> +class SExprVisitor : public TILTraversal<Self, TILVisitReducer> { +public: + SExprVisitor() : Success(true) {} + + bool traverse(SExpr *E, TIL_TraversalKind K = TRV_Normal) { + Success = Success && this->traverseByCase(E); + return Success; + } + + static bool visit(SExpr *E) { + SExprVisitor Visitor; + return Visitor.traverse(E); + } + +private: + bool Success; +}; + + +// Basic class for comparison operations over expressions. +template <typename Self> +class TILComparator { +public: + Self *self() { return reinterpret_cast<Self *>(this); } + + bool compareByCase(SExpr *E1, SExpr* E2) { + switch (E1->opcode()) { +#define TIL_OPCODE_DEF(X) \ + case COP_##X: \ + return cast<X>(E1)->compare(cast<X>(E2), *self()); +#include "clang/Analysis/Analyses/ThreadSafetyOps.def" +#undef TIL_OPCODE_DEF + case COP_MAX: + return false; + } + } +}; + + +class TILEqualsComparator : public TILComparator<TILEqualsComparator> { +public: + // Result type for the comparison, e.g. bool for simple equality, + // or int for lexigraphic comparison (-1, 0, 1). Must have one value which + // denotes "true". + typedef bool CType; + + CType trueResult() { return true; } + bool notTrue(CType ct) { return !ct; } + + bool compareIntegers(unsigned i, unsigned j) { return i == j; } + bool comparePointers(const void* P, const void* Q) { return P == Q; } + + bool compare(SExpr *E1, SExpr* E2) { + if (E1->opcode() != E2->opcode()) + return false; + return compareByCase(E1, E2); + } + + // TODO -- handle alpha-renaming of variables + void enterScope(Variable* V1, Variable* V2) { } + void leaveScope() { } + + bool compareVariableRefs(Variable* V1, Variable* V2) { + return V1 == V2; + } + + static bool compareExprs(SExpr *E1, SExpr* E2) { + TILEqualsComparator Eq; + return Eq.compareExprs(E1, E2); + } +}; + + +// Pretty printer for TIL expressions +template <typename Self, typename StreamType> +class TILPrettyPrinter { +public: + static void print(SExpr *E, StreamType &SS) { + Self printer; + printer.printSExpr(E, SS, Prec_MAX); + } + +protected: + Self *self() { return reinterpret_cast<Self *>(this); } + + void newline(StreamType &SS) { + SS << "\n"; + } + + // TODO: further distinguish between binary operations. + static const unsigned Prec_Atom = 0; + static const unsigned Prec_Postfix = 1; + static const unsigned Prec_Unary = 2; + static const unsigned Prec_Binary = 3; + static const unsigned Prec_Other = 4; + static const unsigned Prec_Decl = 5; + static const unsigned Prec_MAX = 6; + + // Return the precedence of a given node, for use in pretty printing. + unsigned precedence(SExpr *E) { + switch (E->opcode()) { + case COP_Future: return Prec_Atom; + case COP_Undefined: return Prec_Atom; + case COP_Wildcard: return Prec_Atom; + + case COP_Literal: return Prec_Atom; + case COP_LiteralPtr: return Prec_Atom; + case COP_Variable: return Prec_Atom; + case COP_Function: return Prec_Decl; + case COP_SFunction: return Prec_Decl; + case COP_Code: return Prec_Decl; + + case COP_Apply: return Prec_Postfix; + case COP_SApply: return Prec_Postfix; + case COP_Project: return Prec_Postfix; + + case COP_Call: return Prec_Postfix; + case COP_Alloc: return Prec_Other; + case COP_Load: return Prec_Postfix; + case COP_Store: return Prec_Other; + + case COP_UnaryOp: return Prec_Unary; + case COP_BinaryOp: return Prec_Binary; + case COP_Cast: return Prec_Unary; + + case COP_SCFG: return Prec_Decl; + case COP_Phi: return Prec_Atom; + case COP_Goto: return Prec_Atom; + case COP_Branch: return Prec_Atom; + case COP_MAX: return Prec_MAX; + } + return Prec_MAX; + } + + void printSExpr(SExpr *E, StreamType &SS, unsigned P) { + if (!E) { + self()->printNull(SS); + return; + } + if (self()->precedence(E) > P) { + // Wrap expr in () if necessary. + SS << "("; + self()->printSExpr(E, SS, Prec_MAX); + SS << ")"; + return; + } + + switch (E->opcode()) { +#define TIL_OPCODE_DEF(X) \ + case COP_##X: \ + self()->print##X(cast<X>(E), SS); \ + return; +#include "clang/Analysis/Analyses/ThreadSafetyOps.def" +#undef TIL_OPCODE_DEF + case COP_MAX: + return; + } + } + + void printNull(StreamType &SS) { + SS << "#null"; + } + + void printFuture(Future *E, StreamType &SS) { + self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom); + } + + void printUndefined(Undefined *E, StreamType &SS) { + SS << "#undefined"; + } + + void printWildcard(Wildcard *E, StreamType &SS) { + SS << "_"; + } + + void printLiteral(Literal *E, StreamType &SS) { + // TODO: actually pretty print the literal. + SS << "#lit"; + } + + void printLiteralPtr(LiteralPtr *E, StreamType &SS) { + SS << E->clangDecl()->getName(); + } + + void printVariable(Variable *E, StreamType &SS) { + SS << E->name() << E->getBlockID() << "_" << E->getID(); + } + + void printFunction(Function *E, StreamType &SS, unsigned sugared = 0) { + switch (sugared) { + default: + SS << "\\("; // Lambda + case 1: + SS << "("; // Slot declarations + break; + case 2: + SS << ", "; // Curried functions + break; + } + self()->printVariable(E->variableDecl(), SS); + SS << ": "; + self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX); + + SExpr *B = E->body(); + if (B && B->opcode() == COP_Function) + self()->printFunction(cast<Function>(B), SS, 2); + else + self()->printSExpr(B, SS, Prec_Decl); + } + + void printSFunction(SFunction *E, StreamType &SS) { + SS << "@"; + self()->printVariable(E->variableDecl(), SS); + SS << " "; + self()->printSExpr(E->body(), SS, Prec_Decl); + } + + void printCode(Code *E, StreamType &SS) { + SS << ": "; + self()->printSExpr(E->returnType(), SS, Prec_Decl-1); + SS << " = "; + self()->printSExpr(E->body(), SS, Prec_Decl); + } + + void printApply(Apply *E, StreamType &SS, bool sugared = false) { + SExpr *F = E->fun(); + if (F->opcode() == COP_Apply) { + printApply(cast<Apply>(F), SS, true); + SS << ", "; + } else { + self()->printSExpr(F, SS, Prec_Postfix); + SS << "("; + } + self()->printSExpr(E->arg(), SS, Prec_MAX); + if (!sugared) + SS << ")$"; + } + + void printSApply(SApply *E, StreamType &SS) { + self()->printSExpr(E->sfun(), SS, Prec_Postfix); + SS << "@("; + self()->printSExpr(E->arg(), SS, Prec_MAX); + SS << ")"; + } + + void printProject(Project *E, StreamType &SS) { + self()->printSExpr(E->record(), SS, Prec_Postfix); + SS << "."; + SS << E->slotName(); + } + + void printCall(Call *E, StreamType &SS) { + SExpr *T = E->target(); + if (T->opcode() == COP_Apply) { + self()->printApply(cast<Apply>(T), SS, true); + SS << ")"; + } + else { + self()->printSExpr(T, SS, Prec_Postfix); + SS << "()"; + } + } + + void printAlloc(Alloc *E, StreamType &SS) { + SS << "#alloc "; + self()->printSExpr(E->dataType(), SS, Prec_Other-1); + } + + void printLoad(Load *E, StreamType &SS) { + self()->printSExpr(E->pointer(), SS, Prec_Postfix); + SS << "^"; + } + + void printStore(Store *E, StreamType &SS) { + self()->printSExpr(E->pointer(), SS, Prec_Other-1); + SS << " = "; + self()->printSExpr(E->value(), SS, Prec_Other-1); + } + + void printUnaryOp(UnaryOp *E, StreamType &SS) { + self()->printSExpr(E->expr(), SS, Prec_Unary); + } + + void printBinaryOp(BinaryOp *E, StreamType &SS) { + self()->printSExpr(E->expr0(), SS, Prec_Binary-1); + SS << " " << clang::BinaryOperator::getOpcodeStr(E->binaryOpcode()) << " "; + self()->printSExpr(E->expr1(), SS, Prec_Binary-1); + } + + void printCast(Cast *E, StreamType &SS) { + SS << "~"; + self()->printSExpr(E->expr(), SS, Prec_Unary); + } + + void printSCFG(SCFG *E, StreamType &SS) { + SS << "#CFG {\n"; + for (auto BBI : *E) { + SS << "BB_" << BBI->blockID() << ":"; + newline(SS); + for (auto I : BBI->arguments()) { + SS << "let "; + self()->printVariable(I, SS); + SS << " = "; + self()->printSExpr(I->definition(), SS, Prec_MAX); + SS << ";"; + newline(SS); + } + for (auto I : BBI->instructions()) { + SS << "let "; + self()->printVariable(I, SS); + SS << " = "; + self()->printSExpr(I->definition(), SS, Prec_MAX); + SS << ";"; + newline(SS); + } + SExpr *T = BBI->terminator(); + if (T) { + self()->printSExpr(T, SS, Prec_MAX); + SS << ";"; + newline(SS); + } + newline(SS); + } + SS << "}"; + newline(SS); + } + + void printPhi(Phi *E, StreamType &SS) { + SS << "#phi("; + unsigned i = 0; + for (auto V : E->values()) { + ++i; + if (i > 0) + SS << ", "; + self()->printSExpr(V, SS, Prec_MAX); + } + SS << ")"; + } + + void printGoto(Goto *E, StreamType &SS) { + SS << "#goto BB_"; + SS << E->targetBlock()->blockID(); + SS << ":"; + SS << E->index(); + } + + void printBranch(Branch *E, StreamType &SS) { + SS << "#branch ("; + self()->printSExpr(E->condition(), SS, Prec_MAX); + SS << ") BB_"; + SS << E->thenBlock()->blockID(); + SS << " BB_"; + SS << E->elseBlock()->blockID(); + } +}; + +} // end namespace til + + + +} // end namespace threadSafety +} // end namespace clang + +#endif // THREAD_SAFETY_TIL_H diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 9630bc0be0..f3e4358974 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -22,6 +22,7 @@ add_clang_library(clangAnalysis PseudoConstantAnalysis.cpp ReachableCode.cpp ScanfFormatString.cpp + ThreadSafetyCommon.cpp ThreadSafety.cpp UninitializedValues.cpp diff --git a/lib/Analysis/ThreadSafety.cpp b/lib/Analysis/ThreadSafety.cpp index fd804eba99..9cc2a55f0a 100644 --- a/lib/Analysis/ThreadSafety.cpp +++ b/lib/Analysis/ThreadSafety.cpp @@ -10,18 +10,20 @@ // A intra-procedural analysis for thread safety (e.g. deadlocks and race // conditions), based off of an annotation system. // -// See http://clang.llvm.org/docs/LanguageExtensions.html#thread-safety-annotation-checking +// See http://clang.llvm.org/docs/ThreadSafetyAnalysis.html // for more information. // //===----------------------------------------------------------------------===// -#include "clang/Analysis/Analyses/ThreadSafety.h" #include "clang/AST/Attr.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/StmtCXX.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/ThreadSafety.h" +#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyCommon.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" @@ -2362,16 +2364,21 @@ inline bool neverReturns(const CFGBlock* B) { /// at the end of each block, and issue warnings for thread safety violations. /// Each block in the CFG is traversed exactly once. void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { - CFG *CFGraph = AC.getCFG(); - if (!CFGraph) return; - const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); + // TODO: this whole function needs be rewritten as a visitor for CFGWalker. + // For now, we just use the walker to set things up. + threadSafety::CFGWalker walker; + if (!walker.init(AC)) + return; // AC.dumpCFG(true); + // threadSafety::printSCFG(walker); + + CFG *CFGraph = walker.CFGraph; + const NamedDecl *D = walker.FDecl; - if (!D) - return; // Ignore anonymous functions for now. if (D->hasAttr<NoThreadSafetyAnalysisAttr>()) return; + // FIXME: Do something a bit more intelligent inside constructor and // destructor code. Constructors and destructors must assume unique access // to 'this', so checks on member variable access is disabled, but we should @@ -2387,7 +2394,7 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { // We need to explore the CFG via a "topological" ordering. // That way, we will be guaranteed to have information about required // predecessor locksets when exploring a new block. - PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); + PostOrderCFGView *SortedGraph = walker.SortedGraph; PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); // Mark entry block as reachable diff --git a/lib/Analysis/ThreadSafetyCommon.cpp b/lib/Analysis/ThreadSafetyCommon.cpp new file mode 100644 index 0000000000..cd416e57c9 --- /dev/null +++ b/lib/Analysis/ThreadSafetyCommon.cpp @@ -0,0 +1,407 @@ +//===- ThreadSafetyCommon.cpp ----------------------------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Implementation of the interfaces declared in ThreadSafetyCommon.h +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/Attr.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/StmtCXX.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/Analysis/Analyses/PostOrderCFGView.h" +#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyCommon.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/CFGStmtMap.h" +#include "clang/Basic/OperatorKinds.h" +#include "clang/Basic/SourceLocation.h" +#include "clang/Basic/SourceManager.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include <vector> + + +namespace clang { +namespace threadSafety { + +typedef SExprBuilder::CallingContext CallingContext; + + +til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) { + if (!SMap) + return 0; + auto It = SMap->find(S); + if (It != SMap->end()) + return It->second; + return 0; +} + +void SExprBuilder::insertStmt(const Stmt *S, til::Variable *V) { + SMap->insert(std::make_pair(S, V)); +} + + +// Translate a clang statement or expression to a TIL expression. +// Also performs substitution of variables; Ctx provides the context. +// Dispatches on the type of S. +til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) { + // Check if S has already been translated and cached. + // This handles the lookup of SSA names for DeclRefExprs here. + if (til::SExpr *E = lookupStmt(S)) + return E; + + switch (S->getStmtClass()) { + case Stmt::DeclRefExprClass: + return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx); + case Stmt::CXXThisExprClass: + return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx); + case Stmt::MemberExprClass: + return translateMemberExpr(cast<MemberExpr>(S), Ctx); + case Stmt::CallExprClass: + return translateCallExpr(cast<CallExpr>(S), Ctx); + case Stmt::CXXMemberCallExprClass: + return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx); + case Stmt::CXXOperatorCallExprClass: + return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx); + case Stmt::UnaryOperatorClass: + return translateUnaryOperator(cast<UnaryOperator>(S), Ctx); + case Stmt::BinaryOperatorClass: + return translateBinaryOperator(cast<BinaryOperator>(S), Ctx); + + case Stmt::ArraySubscriptExprClass: + return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx); + case Stmt::ConditionalOperatorClass: + return translateConditionalOperator(cast<ConditionalOperator>(S), Ctx); + case Stmt::BinaryConditionalOperatorClass: + return translateBinaryConditionalOperator( + cast<BinaryConditionalOperator>(S), Ctx); + + // We treat these as no-ops + case Stmt::ParenExprClass: + return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx); + case Stmt::ExprWithCleanupsClass: + return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx); + case Stmt::CXXBindTemporaryExprClass: + return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx); + + // Collect all literals + case Stmt::CharacterLiteralClass: + case Stmt::CXXNullPtrLiteralExprClass: + case Stmt::GNUNullExprClass: + case Stmt::CXXBoolLiteralExprClass: + case Stmt::FloatingLiteralClass: + case Stmt::ImaginaryLiteralClass: + case Stmt::IntegerLiteralClass: + case Stmt::StringLiteralClass: + case Stmt::ObjCStringLiteralClass: + return new (Arena) til::Literal(cast<Expr>(S)); + default: + break; + } + if (const CastExpr *CE = dyn_cast<CastExpr>(S)) + return translateCastExpr(CE, Ctx); + + return new (Arena) til::Undefined(S); +} + + +til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE, + CallingContext *Ctx) { + const ValueDecl *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl()); + + // Function parameters require substitution and/or renaming. + if (const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(VD)) { + const FunctionDecl *FD = + cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); + unsigned I = PV->getFunctionScopeIndex(); + + if (Ctx && Ctx->FunArgs && FD == Ctx->AttrDecl->getCanonicalDecl()) { + // Substitute call arguments for references to function parameters + assert(I < Ctx->NumArgs); + return translate(Ctx->FunArgs[I], Ctx->Prev); + } + // Map the param back to the param of the original function declaration + // for consistent comparisons. + VD = FD->getParamDecl(I); + } + + // For non-local variables, treat it as a referenced to a named object. + return new (Arena) til::LiteralPtr(VD); +} + + +til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE, + CallingContext *Ctx) { + // Substitute for 'this' + if (Ctx && Ctx->SelfArg) + return translate(Ctx->SelfArg, Ctx->Prev); + assert(SelfVar && "We have no variable for 'this'!"); + return SelfVar; +} + + +til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME, + CallingContext *Ctx) { + til::SExpr *E = translate(ME->getBase(), Ctx); + E = new (Arena) til::SApply(E); + return new (Arena) til::Project(E, ME->getMemberDecl()); +} + + +til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE, + CallingContext *Ctx) { + // TODO -- Lock returned + til::SExpr *E = translate(CE->getCallee(), Ctx); + for (unsigned I = 0, N = CE->getNumArgs(); I < N; ++I) { + til::SExpr *A = translate(CE->getArg(I), Ctx); + E = new (Arena) til::Apply(E, A); + } + return new (Arena) til::Call(E, CE); +} + + +til::SExpr *SExprBuilder::translateCXXMemberCallExpr( + const CXXMemberCallExpr *ME, CallingContext *Ctx) { + return translateCallExpr(cast<CallExpr>(ME), Ctx); +} + + +til::SExpr *SExprBuilder::translateCXXOperatorCallExpr( + const CXXOperatorCallExpr *OCE, CallingContext *Ctx) { + return translateCallExpr(cast<CallExpr>(OCE), Ctx); +} + + +til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO, + CallingContext *Ctx) { + switch (UO->getOpcode()) { + case UO_PostInc: + case UO_PostDec: + case UO_PreInc: + case UO_PreDec: + return new (Arena) til::Undefined(UO); + + // We treat these as no-ops + case UO_AddrOf: + case UO_Deref: + case UO_Plus: + return translate(UO->getSubExpr(), Ctx); + + case UO_Minus: + case UO_Not: + case UO_LNot: + case UO_Real: + case UO_Imag: + case UO_Extension: { + til::SExpr *E0 = translate(UO->getSubExpr(), Ctx); + return new (Arena) til::UnaryOp(UO->getOpcode(), E0); + } + } + return new (Arena) til::Undefined(UO); +} + +til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, + CallingContext *Ctx) { + switch (BO->getOpcode()) { + case BO_PtrMemD: + case BO_PtrMemI: + return new (Arena) til::Undefined(BO); + + case BO_Mul: + case BO_Div: + case BO_Rem: + case BO_Add: + case BO_Sub: + case BO_Shl: + case BO_Shr: + case BO_LT: + case BO_GT: + case BO_LE: + case BO_GE: + case BO_EQ: + case BO_NE: + case BO_And: + case BO_Xor: + case BO_Or: + case BO_LAnd: + case BO_LOr: { + til::SExpr *E0 = translate(BO->getLHS(), Ctx); + til::SExpr *E1 = translate(BO->getRHS(), Ctx); + return new (Arena) til::BinaryOp(BO->getOpcode(), E0, E1); + } + case BO_Assign: { + til::SExpr *E0 = translate(BO->getLHS(), Ctx); + til::SExpr *E1 = translate(BO->getRHS(), Ctx); + return new (Arena) til::Store(E0, E1); + } + case BO_MulAssign: + case BO_DivAssign: + case BO_RemAssign: + case BO_AddAssign: + case BO_SubAssign: + case BO_ShlAssign: + case BO_ShrAssign: + case BO_AndAssign: + case BO_XorAssign: + case BO_OrAssign: + return new (Arena) til::Undefined(BO); + + case BO_Comma: + // TODO: handle LHS + return translate(BO->getRHS(), Ctx); + } + + return new (Arena) til::Undefined(BO); +} + + +til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE, + CallingContext *Ctx) { + til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); + + clang::CastKind K = CE->getCastKind(); + switch (K) { + case CK_LValueToRValue: + return new (Arena) til::Load(E0); + + case CK_NoOp: + case CK_DerivedToBase: + case CK_UncheckedDerivedToBase: + case CK_ArrayToPointerDecay: + case CK_FunctionToPointerDecay: + return E0; + + default: + return new (Arena) til::Cast(K, E0); + } +} + + +til::SExpr *SExprBuilder::translateArraySubscriptExpr( + const ArraySubscriptExpr *E, CallingContext *Ctx) { + return new (Arena) til::Undefined(E); +} + + +til::SExpr *SExprBuilder::translateConditionalOperator( + const ConditionalOperator *C, CallingContext *Ctx) { + return new (Arena) til::Undefined(C); +} + + +til::SExpr *SExprBuilder::translateBinaryConditionalOperator( + const BinaryConditionalOperator *C, CallingContext *Ctx) { + return new (Arena) til::Undefined(C); +} + + +// Build a complete SCFG from a clang CFG. +class SCFGBuilder : public CFGVisitor { +public: + // return true if E should be included in the SCFG + bool includeExpr(til::SExpr* E) { + if (!E) + return false; + if (E->opcode() == til::COP_Variable) + return false; + if (E->opcode() == til::COP_LiteralPtr) + return false; + return true; + } + + // Enter the CFG for Decl D, and perform any initial setup operations. + void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) { + Scfg = new til::SCFG(Arena, Cfg->getNumBlockIDs()); + CallCtx = new SExprBuilder::CallingContext(D); + } + + // Enter a CFGBlock. + void enterCFGBlock(const CFGBlock *B) { + CurrentBB = new til::BasicBlock(Arena, 0, B->size()); + CurrentBB->setBlockID(CurrentBlockID); + CurrentVarID = 0; + Scfg->add(CurrentBB); + } + + // Process an ordinary statement. + void handleStatement(const Stmt *S) { + til::SExpr *E = BuildEx.translate(S, CallCtx); + if (includeExpr(E)) { + til::Variable *V = new til::Variable(til::Variable::VK_Let, E); + V->setID(CurrentBlockID, CurrentVarID++); + CurrentBB->addInstr(V); + BuildEx.insertStmt(S, V); + } + } + + // Process a destructor call + void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} + + // Process a successor edge. + void handleSuccessor(const CFGBlock *Succ) {} + + // Process a successor back edge to a previously visited block. + void handleSuccessorBackEdge(const CFGBlock *Succ) {} + + // Leave a CFGBlock. + void exitCFGBlock(const CFGBlock *B) { + CurrentBlockID++; + CurrentBB = 0; + } + + // Leave the CFG, and perform any final cleanup operations. + void exitCFG(const CFGBlock *Last) {} + + SCFGBuilder(til::MemRegionRef A) + : Arena(A), Scfg(0), CurrentBB(0), CurrentBlockID(0), + BuildEx(A, new SExprBuilder::StatementMap()) + { } + + til::SCFG *getCFG() const { return Scfg; } + +private: + til::MemRegionRef Arena; + til::SCFG *Scfg; + til::BasicBlock *CurrentBB; + unsigned CurrentBlockID; + unsigned CurrentVarID; + + SExprBuilder BuildEx; + SExprBuilder::CallingContext *CallCtx; +}; + + + +class LLVMPrinter : + public til::TILPrettyPrinter<LLVMPrinter, llvm::raw_ostream> { +}; + + +void printSCFG(CFGWalker &walker) { + llvm::BumpPtrAllocator Bpa; + til::MemRegionRef Arena(&Bpa); + SCFGBuilder builder(Arena); + // CFGVisitor visitor; + walker.walk(builder); + LLVMPrinter::print(builder.getCFG(), llvm::errs()); +} + + + +} // end namespace threadSafety + +} // end namespace clang |