diff options
Diffstat (limited to 'include/clang/Analysis')
26 files changed, 1140 insertions, 826 deletions
diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h index a61d9e47881d..cc14c7bd33db 100644 --- a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h +++ b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h @@ -13,8 +13,8 @@ // //===----------------------------------------------------------------------===// -#ifndef CLANG_ANALYSIS_CFG_REACHABILITY -#define CLANG_ANALYSIS_CFG_REACHABILITY +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" diff --git a/include/clang/Analysis/Analyses/Consumed.h b/include/clang/Analysis/Analyses/Consumed.h index 36e07c21907b..a7109233987c 100644 --- a/include/clang/Analysis/Analyses/Consumed.h +++ b/include/clang/Analysis/Analyses/Consumed.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_CONSUMED_H -#define LLVM_CLANG_CONSUMED_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H #include "clang/AST/DeclCXX.h" #include "clang/AST/ExprCXX.h" diff --git a/include/clang/Analysis/Analyses/Dominators.h b/include/clang/Analysis/Analyses/Dominators.h index 6c6d9238e5a9..fcef0fc10ac8 100644 --- a/include/clang/Analysis/Analyses/Dominators.h +++ b/include/clang/Analysis/Analyses/Dominators.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_DOMINATORS_H -#define LLVM_CLANG_DOMINATORS_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" diff --git a/include/clang/Analysis/Analyses/FormatString.h b/include/clang/Analysis/Analyses/FormatString.h index 76fe9ddca6f8..174cce4f363c 100644 --- a/include/clang/Analysis/Analyses/FormatString.h +++ b/include/clang/Analysis/Analyses/FormatString.h @@ -16,8 +16,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_FORMAT_H -#define LLVM_CLANG_FORMAT_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_FORMATSTRING_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_FORMATSTRING_H #include "clang/AST/CanonicalType.h" @@ -79,6 +79,7 @@ public: AsLongDouble, // 'L' AsAllocate, // for '%as', GNU extension to C90 scanf AsMAllocate, // for '%ms', GNU extension to scanf + AsWide, // 'w' (MSVCRT, like l but only for c, C, s, S, or Z AsWideChar = AsLong // for '%ls', only makes sense for printf }; @@ -154,6 +155,8 @@ public: // ** Printf-specific ** + ZArg, // MS extension + // Objective-C specific specifiers. ObjCObjArg, // '@' ObjCBeg = ObjCObjArg, ObjCEnd = ObjCObjArg, @@ -644,6 +647,9 @@ public: bool ParsePrintfString(FormatStringHandler &H, const char *beg, const char *end, const LangOptions &LO, const TargetInfo &Target); + +bool ParseFormatStringHasSArg(const char *beg, const char *end, const LangOptions &LO, + const TargetInfo &Target); bool ParseScanfString(FormatStringHandler &H, const char *beg, const char *end, const LangOptions &LO, diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 784227108ead..c29dd409e56c 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_LIVEVARIABLES_H -#define LLVM_CLANG_LIVEVARIABLES_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H #include "clang/AST/Decl.h" #include "clang/Analysis/AnalysisContext.h" diff --git a/include/clang/Analysis/Analyses/PostOrderCFGView.h b/include/clang/Analysis/Analyses/PostOrderCFGView.h index 91bf51cd613f..a1c650427588 100644 --- a/include/clang/Analysis/Analyses/PostOrderCFGView.h +++ b/include/clang/Analysis/Analyses/PostOrderCFGView.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_POSTORDER_CFGVIEW -#define LLVM_CLANG_POSTORDER_CFGVIEW +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H #include <vector> //#include <algorithm> @@ -47,17 +47,17 @@ public: /// \brief Set the bit associated with a particular CFGBlock. /// This is the important method for the SetType template parameter. - bool insert(const CFGBlock *Block) { + std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) { // Note that insert() is called by po_iterator, which doesn't check to // make sure that Block is non-null. Moreover, the CFGBlock iterator will // occasionally hand out null pointers for pruned edges, so we catch those // here. if (!Block) - return false; // if an edge is trivially false. + return std::make_pair(None, false); // if an edge is trivially false. if (VisitedBlockIDs.test(Block->getBlockID())) - return false; + return std::make_pair(None, false); VisitedBlockIDs.set(Block->getBlockID()); - return true; + return std::make_pair(None, true); } /// \brief Check if the bit for a CFGBlock has been already set. diff --git a/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h b/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h index cb73850b08c7..c4ec2f22eca0 100644 --- a/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h +++ b/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h @@ -13,8 +13,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_PSEUDOCONSTANTANALYSIS -#define LLVM_CLANG_ANALYSIS_PSEUDOCONSTANTANALYSIS +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_PSEUDOCONSTANTANALYSIS_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_PSEUDOCONSTANTANALYSIS_H #include "clang/AST/Stmt.h" diff --git a/include/clang/Analysis/Analyses/ReachableCode.h b/include/clang/Analysis/Analyses/ReachableCode.h index 90a6d014f58d..4c523bfc8b56 100644 --- a/include/clang/Analysis/Analyses/ReachableCode.h +++ b/include/clang/Analysis/Analyses/ReachableCode.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_REACHABLECODE_H -#define LLVM_CLANG_REACHABLECODE_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H #include "clang/Basic/SourceLocation.h" diff --git a/include/clang/Analysis/Analyses/ThreadSafety.h b/include/clang/Analysis/Analyses/ThreadSafety.h index b533c1db492e..458bb576f459 100644 --- a/include/clang/Analysis/Analyses/ThreadSafety.h +++ b/include/clang/Analysis/Analyses/ThreadSafety.h @@ -16,31 +16,33 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREADSAFETY_H -#define LLVM_CLANG_THREADSAFETY_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETY_H #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/SourceLocation.h" #include "llvm/ADT/StringRef.h" namespace clang { -namespace thread_safety { +namespace threadSafety { /// This enum distinguishes between different kinds of operations that may /// need to be protected by locks. We use this enum in error handling. enum ProtectedOperationKind { POK_VarDereference, ///< Dereferencing a variable (e.g. p in *p = 5;) POK_VarAccess, ///< Reading or writing a variable (e.g. x in x = 5;) - POK_FunctionCall ///< Making a function call (e.g. fool()) + POK_FunctionCall, ///< Making a function call (e.g. fool()) + POK_PassByRef, ///< Passing a guarded variable by reference. + POK_PtPassByRef, ///< Passing a pt-guarded variable by reference. }; /// This enum distinguishes between different kinds of lock actions. For /// example, it is an error to write a variable protected by shared version of a /// mutex. enum LockKind { - LK_Shared, ///< Shared/reader lock of a mutex. + LK_Shared, ///< Shared/reader lock of a mutex. LK_Exclusive, ///< Exclusive/writer lock of a mutex. - LK_Generic ///< Can be either Shared or Exclusive + LK_Generic ///< Can be either Shared or Exclusive }; /// This enum distinguishes between different ways to access (read or write) a @@ -161,6 +163,16 @@ public: LockKind LK, SourceLocation Loc, Name *PossibleMatch = nullptr) {} + /// Warn when acquiring a lock that the negative capability is not held. + /// \param Kind -- the capability's name parameter (role, mutex, etc). + /// \param LockName -- The name for the lock expression, to be printed in the + /// diagnostic. + /// \param Neg -- The name of the negative capability to be printed in the + /// diagnostic. + /// \param Loc -- The location of the protected operation. + virtual void handleNegativeNotHeld(StringRef Kind, Name LockName, Name Neg, + SourceLocation Loc) {} + /// Warn when a function is called while an excluded mutex is locked. For /// example, the mutex may be locked inside the function. /// \param Kind -- the capability's name parameter (role, mutex, etc). @@ -171,6 +183,13 @@ public: virtual void handleFunExcludesLock(StringRef Kind, Name FunName, Name LockName, SourceLocation Loc) {} + /// Called by the analysis when starting analysis of a function. + /// Used to issue suggestions for changes to annotations. + virtual void enterFunction(const FunctionDecl *FD) {} + + /// Called by the analysis when finishing analysis of a function. + virtual void leaveFunction(const FunctionDecl *FD) {} + bool issueBetaWarnings() { return IssueBetaWarnings; } void setIssueBetaWarnings(bool b) { IssueBetaWarnings = b; } @@ -190,5 +209,5 @@ void runThreadSafetyAnalysis(AnalysisDeclContext &AC, /// of access. LockKind getLockKindFromAccessKind(AccessKind AK); -}} // end namespace clang::thread_safety +}} // end namespace clang::threadSafety #endif diff --git a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 09c614ca3e36..be81121c102b 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -19,21 +19,63 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREAD_SAFETY_COMMON_H -#define LLVM_CLANG_THREAD_SAFETY_COMMON_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" +#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/OperatorKinds.h" - #include <memory> +#include <ostream> +#include <sstream> #include <vector> namespace clang { namespace threadSafety { + +// Various helper functions on til::SExpr +namespace sx { + +inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { + return til::EqualsComparator::compareExprs(E1, E2); +} + +inline bool matches(const til::SExpr *E1, const til::SExpr *E2) { + // We treat a top-level wildcard as the "univsersal" lock. + // It matches everything for the purpose of checking locks, but not + // for unlocking them. + if (isa<til::Wildcard>(E1)) + return isa<til::Wildcard>(E2); + if (isa<til::Wildcard>(E2)) + return isa<til::Wildcard>(E1); + + return til::MatchComparator::compareExprs(E1, E2); +} + +inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { + const auto *PE1 = dyn_cast_or_null<til::Project>(E1); + if (!PE1) + return false; + const auto *PE2 = dyn_cast_or_null<til::Project>(E2); + if (!PE2) + return false; + return PE1->clangDecl() == PE2->clangDecl(); +} + +inline std::string toString(const til::SExpr *E) { + std::stringstream ss; + til::StdPrinter::print(E, ss); + return ss.str(); +} + +} // end namespace sx + + + // This class defines the interface of a clang CFG Visitor. // CFGWalker will invoke the following methods. // Note that methods are not virtual; the visitor is templatized. @@ -206,6 +248,59 @@ private: }; + + +class CapabilityExpr { + // TODO: move this back into ThreadSafety.cpp + // This is specific to thread safety. It is here because + // translateAttrExpr needs it, but that should be moved too. + +private: + const til::SExpr* CapExpr; ///< The capability expression. + bool Negated; ///< True if this is a negative capability + +public: + CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} + + const til::SExpr* sexpr() const { return CapExpr; } + bool negative() const { return Negated; } + + CapabilityExpr operator!() const { + return CapabilityExpr(CapExpr, !Negated); + } + + bool equals(const CapabilityExpr &other) const { + return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); + } + + bool matches(const CapabilityExpr &other) const { + return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); + } + + bool matchesUniv(const CapabilityExpr &CapE) const { + return isUniversal() || matches(CapE); + } + + bool partiallyMatches(const CapabilityExpr &other) const { + return (Negated == other.Negated) && + sx::partiallyMatches(CapExpr, other.CapExpr); + } + + std::string toString() const { + if (Negated) + return "!" + sx::toString(CapExpr); + return sx::toString(CapExpr); + } + + bool shouldIgnore() const { return CapExpr == nullptr; } + + bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } + + bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } +}; + + + // Translate clang::Expr to til::SExpr. class SExprBuilder { public: @@ -219,18 +314,16 @@ public: /// should be evaluated; multiple calling contexts can be chained together /// by the lock_returned attribute. struct CallingContext { + CallingContext *Prev; // The previous context; or 0 if none. 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 = nullptr, const Expr *S = nullptr, - unsigned N = 0, const Expr *const *A = nullptr, - CallingContext *P = nullptr) - : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P), - SelfArrow(false) + CallingContext(CallingContext *P, const NamedDecl *D = nullptr) + : Prev(P), AttrDecl(D), SelfArg(nullptr), + NumArgs(0), FunArgs(nullptr), SelfArrow(false) {} }; @@ -242,6 +335,13 @@ public: SelfVar->setKind(til::Variable::VK_SFun); } + // Translate a clang expression in an attribute to a til::SExpr. + // Constructs the context from D, DeclExp, and SelfDecl. + CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, + const Expr *DeclExp, VarDecl *SelfD=nullptr); + + CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); + // 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. @@ -262,7 +362,8 @@ private: 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 *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, + const Expr *SelfE = nullptr); til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, CallingContext *Ctx); til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, @@ -280,10 +381,8 @@ private: 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); + til::SExpr *translateAbstractConditionalOperator( + const AbstractConditionalOperator *C, CallingContext *Ctx); til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); @@ -362,21 +461,24 @@ private: void mergePhiNodesBackEdge(const CFGBlock *Blk); private: + // Set to true when parsing capability expressions, which get translated + // inaccurately in order to hack around smart pointers etc. + static const bool CapabilityExprMode = true; + til::MemRegionRef Arena; til::Variable *SelfVar; // Variable to use for 'this'. May be null. - til::SCFG *Scfg; + til::SCFG *Scfg; StatementMap SMap; // Map from Stmt to TIL Variables LVarIndexMap LVarIdxMap; // Indices of clang local vars. std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. std::vector<BlockInfo> BBInfo; // Extra information per BB. // Indexed by clang BlockID. - std::unique_ptr<SExprBuilder::CallingContext> CallCtx; // Root calling context LVarDefinitionMap CurrentLVarMap; - std::vector<til::Variable*> CurrentArguments; - std::vector<til::Variable*> CurrentInstructions; - std::vector<til::Variable*> IncompleteArgs; + std::vector<til::Phi*> CurrentArguments; + std::vector<til::SExpr*> CurrentInstructions; + std::vector<til::Phi*> IncompleteArgs; til::BasicBlock *CurrentBB; BlockInfo *CurrentBlockInfo; }; diff --git a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h b/include/clang/Analysis/Analyses/ThreadSafetyLogical.h index c4f4b21aab12..bc78021343a4 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyLogical.h @@ -10,8 +10,8 @@ // that are used as part of fact-checking capability expressions. //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREAD_SAFETY_LOGICAL_H -#define LLVM_CLANG_THREAD_SAFETY_LOGICAL_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" @@ -41,13 +41,13 @@ private: }; class Terminal : public LExpr { - til::SExprRef Expr; + til::SExpr *Expr; public: Terminal(til::SExpr *Expr) : LExpr(LExpr::Terminal), Expr(Expr) {} - const til::SExpr *expr() const { return Expr.get(); } - til::SExpr *expr() { return Expr.get(); } + const til::SExpr *expr() const { return Expr; } + til::SExpr *expr() { return Expr; } static bool classof(const LExpr *E) { return E->kind() == LExpr::Terminal; } }; @@ -104,5 +104,5 @@ bool LExpr::implies(const LExpr *RHS) const { } } -#endif // LLVM_CLANG_THREAD_SAFETY_LOGICAL_H +#endif diff --git a/include/clang/Analysis/Analyses/ThreadSafetyOps.def b/include/clang/Analysis/Analyses/ThreadSafetyOps.def index 6ebc95dbe9a7..0d2458b0c893 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyOps.def +++ b/include/clang/Analysis/Analyses/ThreadSafetyOps.def @@ -44,8 +44,11 @@ TIL_OPCODE_DEF(Cast) TIL_OPCODE_DEF(SCFG) TIL_OPCODE_DEF(BasicBlock) TIL_OPCODE_DEF(Phi) + +// Terminator instructions TIL_OPCODE_DEF(Goto) TIL_OPCODE_DEF(Branch) +TIL_OPCODE_DEF(Return) // pseudo-terms TIL_OPCODE_DEF(Identifier) diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index 8e4299ea70e8..2cd8c6d6d2d6 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -44,17 +44,16 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREAD_SAFETY_TIL_H -#define LLVM_CLANG_THREAD_SAFETY_TIL_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H // All clang include dependencies for this file must be put in // ThreadSafetyUtil.h. #include "ThreadSafetyUtil.h" - -#include <stdint.h> #include <algorithm> #include <cassert> #include <cstddef> +#include <stdint.h> #include <utility> @@ -63,24 +62,27 @@ namespace threadSafety { namespace til { +/// Enum for the different distinct classes of SExpr enum TIL_Opcode { #define TIL_OPCODE_DEF(X) COP_##X, #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF }; +/// Opcode for unary arithmetic operations. enum TIL_UnaryOpcode : unsigned char { UOP_Minus, // - UOP_BitNot, // ~ UOP_LogicNot // ! }; +/// Opcode for binary arithmetic operations. enum TIL_BinaryOpcode : unsigned char { + BOP_Add, // + + BOP_Sub, // - BOP_Mul, // * BOP_Div, // / BOP_Rem, // % - BOP_Add, // + - BOP_Sub, // - BOP_Shl, // << BOP_Shr, // >> BOP_BitAnd, // & @@ -90,37 +92,42 @@ enum TIL_BinaryOpcode : unsigned char { BOP_Neq, // != BOP_Lt, // < BOP_Leq, // <= - BOP_LogicAnd, // && - BOP_LogicOr // || + BOP_LogicAnd, // && (no short-circuit) + BOP_LogicOr // || (no short-circuit) }; +/// Opcode for cast operations. enum TIL_CastOpcode : unsigned char { CAST_none = 0, CAST_extendNum, // extend precision of numeric type CAST_truncNum, // truncate precision of numeric type CAST_toFloat, // convert to floating point type CAST_toInt, // convert to integer type + CAST_objToPtr // convert smart pointer to pointer (C++ only) }; const TIL_Opcode COP_Min = COP_Future; const TIL_Opcode COP_Max = COP_Branch; const TIL_UnaryOpcode UOP_Min = UOP_Minus; const TIL_UnaryOpcode UOP_Max = UOP_LogicNot; -const TIL_BinaryOpcode BOP_Min = BOP_Mul; +const TIL_BinaryOpcode BOP_Min = BOP_Add; const TIL_BinaryOpcode BOP_Max = BOP_LogicOr; const TIL_CastOpcode CAST_Min = CAST_none; const TIL_CastOpcode CAST_Max = CAST_toInt; +/// Return the name of a unary opcode. StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); + +/// Return the name of a binary opcode. StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); -// ValueTypes are data types that can actually be held in registers. -// All variables and expressions must have a vBNF_Nonealue type. -// Pointer types are further subdivided into the various heap-allocated -// types, such as functions, records, etc. -// Structured types that are passed by value (e.g. complex numbers) -// require special handling; they use BT_ValueRef, and size ST_0. +/// ValueTypes are data types that can actually be held in registers. +/// All variables and expressions must have a value type. +/// Pointer types are further subdivided into the various heap-allocated +/// types, such as functions, records, etc. +/// Structured types that are passed by value (e.g. complex numbers) +/// require special handling; they use BT_ValueRef, and size ST_0. struct ValueType { enum BaseType : unsigned char { BT_Void = 0, @@ -246,8 +253,10 @@ inline ValueType ValueType::getValueType<void*>() { } +class BasicBlock; + -// Base class for AST nodes in the typed intermediate language. +/// Base class for AST nodes in the typed intermediate language. class SExpr { public: TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } @@ -266,71 +275,47 @@ public: // template <class C> typename C::CType compare(CType* E, C& Cmp) { // compare all subexpressions, following the comparator interface // } - void *operator new(size_t S, MemRegionRef &R) { return ::operator new(S, R); } - // SExpr objects cannot be deleted. + /// SExpr objects cannot be deleted. // This declaration is public to workaround a gcc bug that breaks building // with REQUIRES_EH=1. void operator delete(void *) LLVM_DELETED_FUNCTION; + /// Returns the instruction ID for this expression. + /// All basic block instructions have a unique ID (i.e. virtual register). + unsigned id() const { return SExprID; } + + /// Returns the block, if this is an instruction in a basic block, + /// otherwise returns null. + BasicBlock* block() const { return Block; } + + /// Set the basic block and instruction ID for this expression. + void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } + protected: - SExpr(TIL_Opcode Op) : Opcode(Op), Reserved(0), Flags(0) {} - SExpr(const SExpr &E) : Opcode(E.Opcode), Reserved(0), Flags(E.Flags) {} + SExpr(TIL_Opcode Op) + : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {} + SExpr(const SExpr &E) + : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0), + Block(nullptr) {} const unsigned char Opcode; unsigned char Reserved; unsigned short Flags; + unsigned SExprID; + BasicBlock* Block; private: SExpr() LLVM_DELETED_FUNCTION; - // SExpr objects must be created in an arena. + /// SExpr objects must be created in an arena. void *operator new(size_t) LLVM_DELETED_FUNCTION; }; -// Class for owning references to SExprs. -// Includes attach/detach logic for counting variable references and lazy -// rewriting strategies. -class SExprRef { -public: - SExprRef() : Ptr(nullptr) { } - SExprRef(std::nullptr_t P) : Ptr(nullptr) { } - SExprRef(SExprRef &&R) : Ptr(R.Ptr) { R.Ptr = nullptr; } - - // Defined after Variable and Future, below. - inline SExprRef(SExpr *P); - inline ~SExprRef(); - - SExpr *get() { return Ptr; } - const SExpr *get() const { return Ptr; } - - SExpr *operator->() { return get(); } - const SExpr *operator->() const { return get(); } - - SExpr &operator*() { return *Ptr; } - const SExpr &operator*() const { return *Ptr; } - - bool operator==(const SExprRef &R) const { return Ptr == R.Ptr; } - bool operator!=(const SExprRef &R) const { return !operator==(R); } - bool operator==(const SExpr *P) const { return Ptr == P; } - bool operator!=(const SExpr *P) const { return !operator==(P); } - bool operator==(std::nullptr_t) const { return Ptr == nullptr; } - bool operator!=(std::nullptr_t) const { return Ptr != nullptr; } - - inline void reset(SExpr *E); - -private: - inline void attach(); - inline void detach(); - - SExpr *Ptr; -}; - - // Contains various helper functions for SExprs. namespace ThreadSafetyTIL { inline bool isTrivial(const SExpr *E) { @@ -342,62 +327,64 @@ namespace ThreadSafetyTIL { // Nodes which declare variables class Function; class SFunction; -class BasicBlock; class Let; -// 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. +/// 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_LetBB, - VK_Fun, - VK_SFun + VK_Let, ///< Let-variable + VK_Fun, ///< Function parameter + VK_SFun ///< SFunction (self) parameter }; - // These are defined after SExprRef contructor, below - inline Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr); - inline Variable(StringRef s, SExpr *D = nullptr); - inline Variable(const Variable &Vd, SExpr *D); + Variable(StringRef s, SExpr *D = nullptr) + : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) { + Flags = VK_Let; + } + Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr) + : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), + Definition(D), Cvdecl(Cvd) { + Flags = VK_Let; + } + Variable(const Variable &Vd, SExpr *D) // rewrite constructor + : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { + Flags = Vd.kind(); + } + /// Return the kind of variable (let, function param, or self) VariableKind kind() const { return static_cast<VariableKind>(Flags); } - const StringRef name() const { return Name; } - const clang::ValueDecl *clangDecl() const { return Cvdecl; } - - // Returns the definition (for let vars) or type (for parameter & self vars) - SExpr *definition() { return Definition.get(); } - const SExpr *definition() const { return Definition.get(); } + /// Return the name of the variable, if any. + StringRef name() const { return Name; } - void attachVar() const { ++NumUses; } - void detachVar() const { assert(NumUses > 0); --NumUses; } + /// Return the clang declaration for this variable, if any. + const clang::ValueDecl *clangDecl() const { return Cvdecl; } - unsigned getID() const { return Id; } - unsigned getBlockID() const { return BlockID; } + /// Return the definition of the variable. + /// For let-vars, this is the setting expression. + /// For function and self parameters, it is the type of the variable. + SExpr *definition() { return Definition; } + const SExpr *definition() const { return Definition; } - void setName(StringRef S) { Name = S; } - void setID(unsigned Bid, unsigned I) { - BlockID = static_cast<unsigned short>(Bid); - Id = static_cast<unsigned short>(I); - } - void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } - void setDefinition(SExpr *E); + void setName(StringRef S) { Name = S; } void setKind(VariableKind K) { Flags = K; } + void setDefinition(SExpr *E) { Definition = E; } + void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -405,7 +392,8 @@ public: return Vs.reduceVariableRef(this); } - template <class C> typename C::CType compare(Variable* E, C& Cmp) { + template <class C> + typename C::CType compare(const Variable* E, C& Cmp) const { return Cmp.compareVariableRefs(this, E); } @@ -416,17 +404,13 @@ private: friend class Let; StringRef Name; // The name of the variable. - SExprRef Definition; // The TIL type or definition + SExpr* Definition; // The TIL type or definition const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. - - unsigned short BlockID; - unsigned short Id; - mutable unsigned NumUses; }; -// Placeholder for an expression that has not yet been created. -// Used to implement lazy copy and rewriting strategies. +/// 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; } @@ -437,25 +421,17 @@ public: FS_done }; - Future() : - SExpr(COP_Future), Status(FS_pending), Result(nullptr), Location(nullptr) - {} + Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {} + private: virtual ~Future() LLVM_DELETED_FUNCTION; -public: - - // Registers the location in the AST where this future is stored. - // Forcing the future will automatically update the AST. - static inline void registerLocation(SExprRef *Member) { - if (Future *F = dyn_cast_or_null<Future>(Member->get())) - F->Location = Member; - } +public: // A lazy rewriting strategy should subclass Future and override this method. - virtual SExpr *create() { return nullptr; } + virtual SExpr *compute() { return nullptr; } // Return the result of this future if it exists, otherwise return null. - SExpr *maybeGetResult() { + SExpr *maybeGetResult() const { return Result; } @@ -463,8 +439,7 @@ public: SExpr *result() { switch (Status) { case FS_pending: - force(); - return Result; + return force(); case FS_evaluating: return nullptr; // infinite loop; illegal recursion. case FS_done: @@ -478,88 +453,22 @@ public: return Vs.traverse(Result, Ctx); } - template <class C> typename C::CType compare(Future* E, C& Cmp) { + template <class C> + typename C::CType compare(const Future* E, C& Cmp) const { if (!Result || !E->Result) return Cmp.comparePointers(this, E); return Cmp.compare(Result, E->Result); } private: - // Force the future. - inline void force(); + SExpr* force(); FutureStatus Status; SExpr *Result; - SExprRef *Location; }; -inline void SExprRef::attach() { - if (!Ptr) - return; - - TIL_Opcode Op = Ptr->opcode(); - if (Op == COP_Variable) { - cast<Variable>(Ptr)->attachVar(); - } else if (Op == COP_Future) { - cast<Future>(Ptr)->registerLocation(this); - } -} - -inline void SExprRef::detach() { - if (Ptr && Ptr->opcode() == COP_Variable) { - cast<Variable>(Ptr)->detachVar(); - } -} - -inline SExprRef::SExprRef(SExpr *P) : Ptr(P) { - attach(); -} - -inline SExprRef::~SExprRef() { - detach(); -} - -inline void SExprRef::reset(SExpr *P) { - detach(); - Ptr = P; - attach(); -} - - -inline Variable::Variable(StringRef s, SExpr *D) - : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr), - BlockID(0), Id(0), NumUses(0) { - Flags = VK_Let; -} - -inline Variable::Variable(SExpr *D, const clang::ValueDecl *Cvd) - : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), - Definition(D), Cvdecl(Cvd), BlockID(0), Id(0), NumUses(0) { - Flags = VK_Let; -} - -inline Variable::Variable(const Variable &Vd, SExpr *D) // rewrite constructor - : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl), - BlockID(0), Id(0), NumUses(0) { - Flags = Vd.kind(); -} - -inline void Variable::setDefinition(SExpr *E) { - Definition.reset(E); -} - -void Future::force() { - Status = FS_evaluating; - SExpr *R = create(); - Result = R; - if (Location) - Location->reset(R); - Status = FS_done; -} - - -// Placeholder for C++ expressions that cannot be represented in the TIL. +/// Placeholder for expressions that cannot be represented in the TIL. class Undefined : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } @@ -572,8 +481,9 @@ public: return Vs.reduceUndefined(*this); } - template <class C> typename C::CType compare(Undefined* E, C& Cmp) { - return Cmp.comparePointers(Cstmt, E->Cstmt); + template <class C> + typename C::CType compare(const Undefined* E, C& Cmp) const { + return Cmp.trueResult(); } private: @@ -581,7 +491,7 @@ private: }; -// Placeholder for a wildcard that matches any other expression. +/// 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; } @@ -593,7 +503,8 @@ public: return Vs.reduceWildcard(*this); } - template <class C> typename C::CType compare(Wildcard* E, C& Cmp) { + template <class C> + typename C::CType compare(const Wildcard* E, C& Cmp) const { return Cmp.trueResult(); } }; @@ -626,9 +537,10 @@ public: template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); - template <class C> typename C::CType compare(Literal* E, C& Cmp) { - // TODO -- use value, not pointer equality - return Cmp.comparePointers(Cexpr, E->Cexpr); + template <class C> + typename C::CType compare(const Literal* E, C& Cmp) const { + // TODO: defer actual comparison to LiteralT + return Cmp.trueResult(); } private: @@ -710,8 +622,8 @@ typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { } -// Literal pointer to an object allocated in memory. -// At compile time, pointer literals are represented by symbolic names. +/// A 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; } @@ -727,7 +639,8 @@ public: return Vs.reduceLiteralPtr(*this); } - template <class C> typename C::CType compare(LiteralPtr* E, C& Cmp) { + template <class C> + typename C::CType compare(const LiteralPtr* E, C& Cmp) const { return Cmp.comparePointers(Cvdecl, E->Cvdecl); } @@ -736,9 +649,9 @@ private: }; -// 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))) +/// A function -- a.k.a. lambda abstraction. +/// Functions with multiple arguments are created by currying, +/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) class Function : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } @@ -755,8 +668,8 @@ public: Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } - SExpr *body() { return Body.get(); } - const SExpr *body() const { return Body.get(); } + SExpr *body() { return Body; } + const SExpr *body() const { return Body; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -769,7 +682,8 @@ public: return Vs.reduceFunction(*this, Nvd, E1); } - template <class C> typename C::CType compare(Function* E, C& Cmp) { + template <class C> + typename C::CType compare(const Function* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); if (Cmp.notTrue(Ct)) @@ -782,13 +696,13 @@ public: private: Variable *VarDecl; - SExprRef Body; + SExpr* Body; }; -// A self-applicable function. -// A self-applicable function can be applied to itself. It's useful for -// implementing objects and late binding +/// 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; } @@ -797,20 +711,20 @@ public: : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { assert(Vd->Definition == nullptr); Vd->setKind(Variable::VK_SFun); - Vd->Definition.reset(this); + Vd->Definition = this; } SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor : SExpr(F), VarDecl(Vd), Body(B) { assert(Vd->Definition == nullptr); Vd->setKind(Variable::VK_SFun); - Vd->Definition.reset(this); + Vd->Definition = this; } Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } - SExpr *body() { return Body.get(); } - const SExpr *body() const { return Body.get(); } + SExpr *body() { return Body; } + const SExpr *body() const { return Body; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -824,7 +738,8 @@ public: return Vs.reduceSFunction(*this, Nvd, E1); } - template <class C> typename C::CType compare(SFunction* E, C& Cmp) { + template <class C> + typename C::CType compare(const SFunction* E, C& Cmp) const { Cmp.enterScope(variableDecl(), E->variableDecl()); typename C::CType Ct = Cmp.compare(body(), E->body()); Cmp.leaveScope(); @@ -833,11 +748,11 @@ public: private: Variable *VarDecl; - SExprRef Body; + SExpr* Body; }; -// A block of code -- e.g. the body of a function. +/// 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; } @@ -846,11 +761,11 @@ public: Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor : SExpr(C), ReturnType(T), Body(B) {} - SExpr *returnType() { return ReturnType.get(); } - const SExpr *returnType() const { return ReturnType.get(); } + SExpr *returnType() { return ReturnType; } + const SExpr *returnType() const { return ReturnType; } - SExpr *body() { return Body.get(); } - const SExpr *body() const { return Body.get(); } + SExpr *body() { return Body; } + const SExpr *body() const { return Body; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -859,7 +774,8 @@ public: return Vs.reduceCode(*this, Nt, Nb); } - template <class C> typename C::CType compare(Code* E, C& Cmp) { + template <class C> + typename C::CType compare(const Code* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); if (Cmp.notTrue(Ct)) return Ct; @@ -867,12 +783,12 @@ public: } private: - SExprRef ReturnType; - SExprRef Body; + SExpr* ReturnType; + SExpr* Body; }; -// A typed, writable location in memory +/// A typed, writable location in memory class Field : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } @@ -881,11 +797,11 @@ public: Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor : SExpr(C), Range(R), Body(B) {} - SExpr *range() { return Range.get(); } - const SExpr *range() const { return Range.get(); } + SExpr *range() { return Range; } + const SExpr *range() const { return Range; } - SExpr *body() { return Body.get(); } - const SExpr *body() const { return Body.get(); } + SExpr *body() { return Body; } + const SExpr *body() const { return Body; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -894,7 +810,8 @@ public: return Vs.reduceField(*this, Nr, Nb); } - template <class C> typename C::CType compare(Field* E, C& Cmp) { + template <class C> + typename C::CType compare(const Field* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(range(), E->range()); if (Cmp.notTrue(Ct)) return Ct; @@ -902,12 +819,16 @@ public: } private: - SExprRef Range; - SExprRef Body; + SExpr* Range; + SExpr* Body; }; -// Apply an argument to a function +/// Apply an argument to a function. +/// Note that this does not actually call the function. Functions are curried, +/// so this returns a closure in which the first parameter has been applied. +/// Once all parameters have been applied, Call can be used to invoke the +/// function. class Apply : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } @@ -917,11 +838,11 @@ public: : SExpr(A), Fun(F), Arg(Ar) {} - SExpr *fun() { return Fun.get(); } - const SExpr *fun() const { return Fun.get(); } + SExpr *fun() { return Fun; } + const SExpr *fun() const { return Fun; } - SExpr *arg() { return Arg.get(); } - const SExpr *arg() const { return Arg.get(); } + SExpr *arg() { return Arg; } + const SExpr *arg() const { return Arg; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -930,7 +851,8 @@ public: return Vs.reduceApply(*this, Nf, Na); } - template <class C> typename C::CType compare(Apply* E, C& Cmp) { + template <class C> + typename C::CType compare(const Apply* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(fun(), E->fun()); if (Cmp.notTrue(Ct)) return Ct; @@ -938,12 +860,12 @@ public: } private: - SExprRef Fun; - SExprRef Arg; + SExpr* Fun; + SExpr* Arg; }; -// Apply a self-argument to a self-applicable function +/// 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; } @@ -952,23 +874,24 @@ public: SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor : SExpr(A), Sfun(Sf), Arg(Ar) {} - SExpr *sfun() { return Sfun.get(); } - const SExpr *sfun() const { return Sfun.get(); } + SExpr *sfun() { return Sfun; } + const SExpr *sfun() const { return Sfun; } - SExpr *arg() { return Arg.get() ? Arg.get() : Sfun.get(); } - const SExpr *arg() const { return Arg.get() ? Arg.get() : Sfun.get(); } + SExpr *arg() { return Arg ? Arg : Sfun; } + const SExpr *arg() const { return Arg ? Arg : Sfun; } - bool isDelegation() const { return Arg == nullptr; } + bool isDelegation() const { return Arg != nullptr; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); - typename V::R_SExpr Na = Arg.get() ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) + typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) : nullptr; return Vs.reduceSApply(*this, Nf, Na); } - template <class C> typename C::CType compare(SApply* E, C& Cmp) { + template <class C> + typename C::CType compare(const SApply* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) return Ct; @@ -976,12 +899,12 @@ public: } private: - SExprRef Sfun; - SExprRef Arg; + SExpr* Sfun; + SExpr* Arg; }; -// Project a named slot from a C++ struct or class. +/// 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; } @@ -989,17 +912,23 @@ public: Project(SExpr *R, StringRef SName) : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr) { } - Project(SExpr *R, clang::ValueDecl *Cvd) + Project(SExpr *R, const clang::ValueDecl *Cvd) : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd) { } Project(const Project &P, SExpr *R) : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl) { } - SExpr *record() { return Rec.get(); } - const SExpr *record() const { return Rec.get(); } + SExpr *record() { return Rec; } + const SExpr *record() const { return Rec; } + + const clang::ValueDecl *clangDecl() const { return Cvdecl; } - const clang::ValueDecl *clangValueDecl() const { return Cvdecl; } + bool isArrow() const { return (Flags & 0x01) != 0; } + void setArrow(bool b) { + if (b) Flags |= 0x01; + else Flags &= 0xFFFE; + } StringRef slotName() const { if (Cvdecl) @@ -1014,7 +943,8 @@ public: return Vs.reduceProject(*this, Nr); } - template <class C> typename C::CType compare(Project* E, C& Cmp) { + template <class C> + typename C::CType compare(const Project* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(record(), E->record()); if (Cmp.notTrue(Ct)) return Ct; @@ -1022,13 +952,13 @@ public: } private: - SExprRef Rec; + SExpr* Rec; StringRef SlotName; - clang::ValueDecl *Cvdecl; + const clang::ValueDecl *Cvdecl; }; -// Call a function (after all arguments have been applied). +/// 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; } @@ -1037,8 +967,8 @@ public: : SExpr(COP_Call), Target(T), Cexpr(Ce) {} Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} - SExpr *target() { return Target.get(); } - const SExpr *target() const { return Target.get(); } + SExpr *target() { return Target; } + const SExpr *target() const { return Target; } const clang::CallExpr *clangCallExpr() const { return Cexpr; } @@ -1048,17 +978,18 @@ public: return Vs.reduceCall(*this, Nt); } - template <class C> typename C::CType compare(Call* E, C& Cmp) { + template <class C> + typename C::CType compare(const Call* E, C& Cmp) const { return Cmp.compare(target(), E->target()); } private: - SExprRef Target; + SExpr* Target; const clang::CallExpr *Cexpr; }; -// Allocate memory for a new value on the heap or stack. +/// 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; } @@ -1073,8 +1004,8 @@ public: AllocKind kind() const { return static_cast<AllocKind>(Flags); } - SExpr *dataType() { return Dtype.get(); } - const SExpr *dataType() const { return Dtype.get(); } + SExpr *dataType() { return Dtype; } + const SExpr *dataType() const { return Dtype; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1082,7 +1013,8 @@ public: return Vs.reduceAlloc(*this, Nd); } - template <class C> typename C::CType compare(Alloc* E, C& Cmp) { + template <class C> + typename C::CType compare(const Alloc* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); if (Cmp.notTrue(Ct)) return Ct; @@ -1090,11 +1022,11 @@ public: } private: - SExprRef Dtype; + SExpr* Dtype; }; -// Load a value from memory. +/// Load a value from memory. class Load : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } @@ -1102,8 +1034,8 @@ public: Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} - SExpr *pointer() { return Ptr.get(); } - const SExpr *pointer() const { return Ptr.get(); } + SExpr *pointer() { return Ptr; } + const SExpr *pointer() const { return Ptr; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1111,17 +1043,18 @@ public: return Vs.reduceLoad(*this, Np); } - template <class C> typename C::CType compare(Load* E, C& Cmp) { + template <class C> + typename C::CType compare(const Load* E, C& Cmp) const { return Cmp.compare(pointer(), E->pointer()); } private: - SExprRef Ptr; + SExpr* Ptr; }; -// Store a value to memory. -// Source is a pointer, destination is the value to store. +/// Store a value to memory. +/// The destination is a pointer to a field, the source is the value to store. class Store : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } @@ -1129,11 +1062,11 @@ public: Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} - SExpr *destination() { return Dest.get(); } // Address to store to - const SExpr *destination() const { return Dest.get(); } + SExpr *destination() { return Dest; } // Address to store to + const SExpr *destination() const { return Dest; } - SExpr *source() { return Source.get(); } // Value to store - const SExpr *source() const { return Source.get(); } + SExpr *source() { return Source; } // Value to store + const SExpr *source() const { return Source; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1142,7 +1075,8 @@ public: return Vs.reduceStore(*this, Np, Nv); } - template <class C> typename C::CType compare(Store* E, C& Cmp) { + template <class C> + typename C::CType compare(const Store* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(destination(), E->destination()); if (Cmp.notTrue(Ct)) return Ct; @@ -1150,13 +1084,13 @@ public: } private: - SExprRef Dest; - SExprRef Source; + SExpr* Dest; + SExpr* Source; }; -// If p is a reference to an array, then first(p) is a reference to the first -// element. The usual array notation p[i] becomes first(p + i). +/// If p is a reference to an array, then p[i] is a reference to the i'th +/// element of the array. class ArrayIndex : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } @@ -1165,11 +1099,11 @@ public: ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) : SExpr(E), Array(A), Index(N) {} - SExpr *array() { return Array.get(); } - const SExpr *array() const { return Array.get(); } + SExpr *array() { return Array; } + const SExpr *array() const { return Array; } - SExpr *index() { return Index.get(); } - const SExpr *index() const { return Index.get(); } + SExpr *index() { return Index; } + const SExpr *index() const { return Index; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1178,7 +1112,8 @@ public: return Vs.reduceArrayIndex(*this, Na, Ni); } - template <class C> typename C::CType compare(ArrayIndex* E, C& Cmp) { + template <class C> + typename C::CType compare(const ArrayIndex* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(array(), E->array()); if (Cmp.notTrue(Ct)) return Ct; @@ -1186,14 +1121,14 @@ public: } private: - SExprRef Array; - SExprRef Index; + SExpr* Array; + SExpr* Index; }; -// Pointer arithmetic, restricted to arrays only. -// If p is a reference to an array, then p + n, where n is an integer, is -// a reference to a subarray. +/// Pointer arithmetic, restricted to arrays only. +/// If p is a reference to an array, then p + n, where n is an integer, is +/// a reference to a subarray. class ArrayAdd : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } @@ -1202,11 +1137,11 @@ public: ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) : SExpr(E), Array(A), Index(N) {} - SExpr *array() { return Array.get(); } - const SExpr *array() const { return Array.get(); } + SExpr *array() { return Array; } + const SExpr *array() const { return Array; } - SExpr *index() { return Index.get(); } - const SExpr *index() const { return Index.get(); } + SExpr *index() { return Index; } + const SExpr *index() const { return Index; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1215,7 +1150,8 @@ public: return Vs.reduceArrayAdd(*this, Na, Ni); } - template <class C> typename C::CType compare(ArrayAdd* E, C& Cmp) { + template <class C> + typename C::CType compare(const ArrayAdd* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(array(), E->array()); if (Cmp.notTrue(Ct)) return Ct; @@ -1223,12 +1159,13 @@ public: } private: - SExprRef Array; - SExprRef Index; + SExpr* Array; + SExpr* Index; }; -// Simple unary operation -- e.g. !, ~, etc. +/// Simple arithmetic unary operations, e.g. negate and not. +/// These operations have no side-effects. class UnaryOp : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } @@ -1242,8 +1179,8 @@ public: return static_cast<TIL_UnaryOpcode>(Flags); } - SExpr *expr() { return Expr0.get(); } - const SExpr *expr() const { return Expr0.get(); } + SExpr *expr() { return Expr0; } + const SExpr *expr() const { return Expr0; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1251,7 +1188,8 @@ public: return Vs.reduceUnaryOp(*this, Ne); } - template <class C> typename C::CType compare(UnaryOp* E, C& Cmp) { + template <class C> + typename C::CType compare(const UnaryOp* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); if (Cmp.notTrue(Ct)) @@ -1260,11 +1198,12 @@ public: } private: - SExprRef Expr0; + SExpr* Expr0; }; -// Simple binary operation -- e.g. +, -, etc. +/// Simple arithmetic binary operations, e.g. +, -, etc. +/// These operations have no side effects. class BinaryOp : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } @@ -1282,11 +1221,11 @@ public: return static_cast<TIL_BinaryOpcode>(Flags); } - SExpr *expr0() { return Expr0.get(); } - const SExpr *expr0() const { return Expr0.get(); } + SExpr *expr0() { return Expr0; } + const SExpr *expr0() const { return Expr0; } - SExpr *expr1() { return Expr1.get(); } - const SExpr *expr1() const { return Expr1.get(); } + SExpr *expr1() { return Expr1; } + const SExpr *expr1() const { return Expr1; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1295,7 +1234,8 @@ public: return Vs.reduceBinaryOp(*this, Ne0, Ne1); } - template <class C> typename C::CType compare(BinaryOp* E, C& Cmp) { + template <class C> + typename C::CType compare(const BinaryOp* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); if (Cmp.notTrue(Ct)) @@ -1307,12 +1247,14 @@ public: } private: - SExprRef Expr0; - SExprRef Expr1; + SExpr* Expr0; + SExpr* Expr1; }; -// Cast expression +/// Cast expressions. +/// Cast expressions are essentially unary operations, but we treat them +/// as a distinct AST node because they only change the type of the result. class Cast : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } @@ -1324,8 +1266,8 @@ public: return static_cast<TIL_CastOpcode>(Flags); } - SExpr *expr() { return Expr0.get(); } - const SExpr *expr() const { return Expr0.get(); } + SExpr *expr() { return Expr0; } + const SExpr *expr() const { return Expr0; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1333,7 +1275,8 @@ public: return Vs.reduceCast(*this, Ne); } - template <class C> typename C::CType compare(Cast* E, C& Cmp) { + template <class C> + typename C::CType compare(const Cast* E, C& Cmp) const { typename C::CType Ct = Cmp.compareIntegers(castOpcode(), E->castOpcode()); if (Cmp.notTrue(Ct)) @@ -1342,16 +1285,18 @@ public: } private: - SExprRef Expr0; + SExpr* Expr0; }; class SCFG; +/// Phi Node, for code in SSA form. +/// Each Phi node has an array of possible values that it can take, +/// depending on where control flow comes from. class Phi : public SExpr { public: - // TODO: change to SExprRef typedef SimpleArray<SExpr *> ValArray; // In minimal SSA form, all Phi nodes are MultiVal. @@ -1365,9 +1310,12 @@ public: static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } - Phi() : SExpr(COP_Phi) {} - Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {} - Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {} + Phi() + : SExpr(COP_Phi), Cvdecl(nullptr) {} + Phi(MemRegionRef A, unsigned Nvals) + : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {} + Phi(const Phi &P, ValArray &&Vs) + : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {} const ValArray &values() const { return Values; } ValArray &values() { return Values; } @@ -1375,6 +1323,12 @@ public: Status status() const { return static_cast<Status>(Flags); } void setStatus(Status s) { Flags = s; } + /// Return the clang declaration of the variable for this Phi node, if any. + const clang::ValueDecl *clangDecl() const { return Cvdecl; } + + /// Set the clang variable associated with this Phi node. + void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; } + template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { typename V::template Container<typename V::R_SExpr> @@ -1386,72 +1340,268 @@ public: return Vs.reducePhi(*this, Nvs); } - template <class C> typename C::CType compare(Phi *E, C &Cmp) { + template <class C> + typename C::CType compare(const Phi *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: ValArray Values; + const clang::ValueDecl* Cvdecl; +}; + + +/// Base class for basic block terminators: Branch, Goto, and Return. +class Terminator : public SExpr { +public: + static bool classof(const SExpr *E) { + return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; + } + +protected: + Terminator(TIL_Opcode Op) : SExpr(Op) {} + Terminator(const SExpr &E) : SExpr(E) {} + +public: + /// Return the list of basic blocks that this terminator can branch to. + ArrayRef<BasicBlock*> successors(); + + ArrayRef<BasicBlock*> successors() const { + return const_cast<Terminator*>(this)->successors(); + } }; -// 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. +/// Jump to another basic block. +/// A goto instruction is essentially a tail-recursive call into another +/// block. In addition to the block pointer, it specifies an index into the +/// phi nodes of that block. The index can be used to retrieve the "arguments" +/// of the call. +class Goto : public Terminator { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } + + Goto(BasicBlock *B, unsigned I) + : Terminator(COP_Goto), TargetBlock(B), Index(I) {} + Goto(const Goto &G, BasicBlock *B, unsigned I) + : Terminator(COP_Goto), TargetBlock(B), Index(I) {} + + const BasicBlock *targetBlock() const { return TargetBlock; } + BasicBlock *targetBlock() { return TargetBlock; } + + /// Returns the index into the + unsigned index() const { return Index; } + + /// Return the list of basic blocks that this terminator can branch to. + ArrayRef<BasicBlock*> successors() { + return ArrayRef<BasicBlock*>(&TargetBlock, 1); + } + + template <class V> + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); + return Vs.reduceGoto(*this, Ntb); + } + + template <class C> + typename C::CType compare(const Goto *E, C &Cmp) const { + // TODO: implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + BasicBlock *TargetBlock; + unsigned Index; +}; + + +/// A conditional branch to two other blocks. +/// Note that unlike Goto, Branch does not have an index. The target blocks +/// must be child-blocks, and cannot have Phi nodes. +class Branch : public Terminator { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } + + Branch(SExpr *C, BasicBlock *T, BasicBlock *E) + : Terminator(COP_Branch), Condition(C) { + Branches[0] = T; + Branches[1] = E; + } + Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) + : Terminator(Br), Condition(C) { + Branches[0] = T; + Branches[1] = E; + } + + const SExpr *condition() const { return Condition; } + SExpr *condition() { return Condition; } + + const BasicBlock *thenBlock() const { return Branches[0]; } + BasicBlock *thenBlock() { return Branches[0]; } + + const BasicBlock *elseBlock() const { return Branches[1]; } + BasicBlock *elseBlock() { return Branches[1]; } + + /// Return the list of basic blocks that this terminator can branch to. + ArrayRef<BasicBlock*> successors() { + return ArrayRef<BasicBlock*>(Branches, 2); + } + + template <class V> + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); + BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); + BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); + return Vs.reduceBranch(*this, Nc, Ntb, Nte); + } + + template <class C> + typename C::CType compare(const Branch *E, C &Cmp) const { + // TODO: implement CFG comparisons + return Cmp.comparePointers(this, E); + } + +private: + SExpr* Condition; + BasicBlock *Branches[2]; +}; + + +/// Return from the enclosing function, passing the return value to the caller. +/// Only the exit block should end with a return statement. +class Return : public Terminator { +public: + static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } + + Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} + Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} + + /// Return an empty list. + ArrayRef<BasicBlock*> successors() { + return ArrayRef<BasicBlock*>(); + } + + SExpr *returnValue() { return Retval; } + const SExpr *returnValue() const { return Retval; } + + template <class V> + typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { + auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); + return Vs.reduceReturn(*this, Ne); + } + + template <class C> + typename C::CType compare(const Return *E, C &Cmp) const { + return Cmp.compare(Retval, E->Retval); + } + +private: + SExpr* Retval; +}; + + +inline ArrayRef<BasicBlock*> Terminator::successors() { + switch (opcode()) { + case COP_Goto: return cast<Goto>(this)->successors(); + case COP_Branch: return cast<Branch>(this)->successors(); + case COP_Return: return cast<Return>(this)->successors(); + default: + return ArrayRef<BasicBlock*>(); + } +} + + +/// A basic block is part of an SCFG. It can be treated as a function in +/// continuation passing style. A block consists of a sequence of phi nodes, +/// which are "arguments" to the function, followed by a sequence of +/// instructions. It ends with a Terminator, which is a Branch or Goto to +/// another basic block in the same SCFG. class BasicBlock : public SExpr { public: - typedef SimpleArray<Variable*> VarArray; + typedef SimpleArray<SExpr*> InstrArray; typedef SimpleArray<BasicBlock*> BlockArray; + // TopologyNodes are used to overlay tree structures on top of the CFG, + // such as dominator and postdominator trees. Each block is assigned an + // ID in the tree according to a depth-first search. Tree traversals are + // always up, towards the parents. + struct TopologyNode { + TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {} + + bool isParentOf(const TopologyNode& OtherNode) { + return OtherNode.NodeID > NodeID && + OtherNode.NodeID < NodeID + SizeOfSubTree; + } + + bool isParentOfOrEqual(const TopologyNode& OtherNode) { + return OtherNode.NodeID >= NodeID && + OtherNode.NodeID < NodeID + SizeOfSubTree; + } + + int NodeID; + int SizeOfSubTree; // Includes this node, so must be > 1. + BasicBlock *Parent; // Pointer to parent. + }; + static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } - explicit BasicBlock(MemRegionRef A, BasicBlock* P = nullptr) + explicit BasicBlock(MemRegionRef A) : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), - Parent(P), Terminator(nullptr) - { } - BasicBlock(BasicBlock &B, VarArray &&As, VarArray &&Is, SExpr *T) - : SExpr(COP_BasicBlock), Arena(B.Arena), CFGPtr(nullptr), BlockID(0), - Parent(nullptr), Args(std::move(As)), Instrs(std::move(Is)), - Terminator(T) - { } + Visited(0), TermInstr(nullptr) {} + BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, + Terminator *T) + : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0), + Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} + + /// Returns the block ID. Every block has a unique ID in the CFG. + int blockID() const { return BlockID; } - unsigned blockID() const { return BlockID; } - unsigned numPredecessors() const { return Predecessors.size(); } + /// Returns the number of predecessors. + size_t numPredecessors() const { return Predecessors.size(); } + size_t numSuccessors() const { return successors().size(); } const SCFG* cfg() const { return CFGPtr; } SCFG* cfg() { return CFGPtr; } - const BasicBlock *parent() const { return Parent; } - BasicBlock *parent() { return Parent; } + const BasicBlock *parent() const { return DominatorNode.Parent; } + BasicBlock *parent() { return DominatorNode.Parent; } - const VarArray &arguments() const { return Args; } - VarArray &arguments() { return Args; } + const InstrArray &arguments() const { return Args; } + InstrArray &arguments() { return Args; } - const VarArray &instructions() const { return Instrs; } - VarArray &instructions() { return Instrs; } + InstrArray &instructions() { return Instrs; } + const InstrArray &instructions() const { return Instrs; } - const BlockArray &predecessors() const { return Predecessors; } + /// Returns a list of predecessors. + /// The order of predecessors in the list is important; each phi node has + /// exactly one argument for each precessor, in the same order. BlockArray &predecessors() { return Predecessors; } + const BlockArray &predecessors() const { return Predecessors; } + + ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } + ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } + + const Terminator *terminator() const { return TermInstr; } + Terminator *terminator() { return TermInstr; } - const SExpr *terminator() const { return Terminator.get(); } - SExpr *terminator() { return Terminator.get(); } + void setTerminator(Terminator *E) { TermInstr = E; } - void setBlockID(unsigned i) { BlockID = i; } - void setParent(BasicBlock *P) { Parent = P; } - void setTerminator(SExpr *E) { Terminator.reset(E); } + bool Dominates(const BasicBlock &Other) { + return DominatorNode.isParentOfOrEqual(Other.DominatorNode); + } + + bool PostDominates(const BasicBlock &Other) { + return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); + } - // Add a new argument. V must define a phi-node. - void addArgument(Variable *V) { - V->setKind(Variable::VK_LetBB); + /// Add a new argument. + void addArgument(Phi *V) { Args.reserveCheck(1, Arena); Args.push_back(V); } - // Add a new instruction. - void addInstruction(Variable *V) { - V->setKind(Variable::VK_LetBB); + /// Add a new instruction. + void addInstruction(SExpr *V) { Instrs.reserveCheck(1, Arena); Instrs.push_back(V); } @@ -1468,34 +1618,29 @@ public: // Reserve space for NumPreds predecessors, including space in phi nodes. void reservePredecessors(unsigned NumPreds); - // Return the index of BB, or Predecessors.size if BB is not a predecessor. + /// Return the index of BB, or Predecessors.size if BB is not a predecessor. unsigned findPredecessorIndex(const BasicBlock *BB) const { auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB); return std::distance(Predecessors.cbegin(), I); } - // Set id numbers for variables. - void renumberVars(); - template <class V> typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { - typename V::template Container<Variable*> Nas(Vs, Args.size()); - typename V::template Container<Variable*> Nis(Vs, Instrs.size()); + typename V::template Container<SExpr*> Nas(Vs, Args.size()); + typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); // Entering the basic block should do any scope initialization. Vs.enterBasicBlock(*this); - for (auto *A : Args) { - auto Ne = Vs.traverse(A->Definition, Vs.subExprCtx(Ctx)); - Variable *Nvd = Vs.enterScope(*A, Ne); - Nas.push_back(Nvd); + for (auto *E : Args) { + auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); + Nas.push_back(Ne); } - for (auto *I : Instrs) { - auto Ne = Vs.traverse(I->Definition, Vs.subExprCtx(Ctx)); - Variable *Nvd = Vs.enterScope(*I, Ne); - Nis.push_back(Nvd); + for (auto *E : Instrs) { + auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); + Nis.push_back(Ne); } - auto Nt = Vs.traverse(Terminator, Ctx); + auto Nt = Vs.traverse(TermInstr, Ctx); // Exiting the basic block should handle any scope cleanup. Vs.exitBasicBlock(*this); @@ -1503,7 +1648,8 @@ public: return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); } - template <class C> typename C::CType compare(BasicBlock *E, C &Cmp) { + template <class C> + typename C::CType compare(const BasicBlock *E, C &Cmp) const { // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } @@ -1511,22 +1657,32 @@ public: private: friend class SCFG; - MemRegionRef Arena; + int renumberInstrs(int id); // assign unique ids to all instructions + int topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID); + int topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID); + void computeDominator(); + void computePostDominator(); - SCFG *CFGPtr; // The CFG that contains this block. - unsigned BlockID; // unique id for this BB in the containing CFG - BasicBlock *Parent; // The parent block is the enclosing lexical scope. - // The parent dominates this block. - BlockArray Predecessors; // Predecessor blocks in the CFG. - VarArray Args; // Phi nodes. One argument per predecessor. - VarArray Instrs; // Instructions. - SExprRef Terminator; // Branch or Goto +private: + MemRegionRef Arena; // The arena used to allocate this block. + SCFG *CFGPtr; // The CFG that contains this block. + int BlockID : 31; // unique id for this BB in the containing CFG. + // IDs are in topological order. + bool Visited : 1; // Bit to determine if a block has been visited + // during a traversal. + BlockArray Predecessors; // Predecessor blocks in the CFG. + InstrArray Args; // Phi nodes. One argument per predecessor. + InstrArray Instrs; // Instructions. + Terminator* TermInstr; // Terminating instruction + + TopologyNode DominatorNode; // The dominator tree + TopologyNode PostDominatorNode; // The post-dominator tree }; -// 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. +/// 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; @@ -1537,20 +1693,29 @@ public: SCFG(MemRegionRef A, unsigned Nblocks) : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), - Entry(nullptr), Exit(nullptr) { - Entry = new (A) BasicBlock(A, nullptr); - Exit = new (A) BasicBlock(A, Entry); - auto *V = new (A) Variable(new (A) Phi()); + Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { + Entry = new (A) BasicBlock(A); + Exit = new (A) BasicBlock(A); + auto *V = new (A) Phi(); Exit->addArgument(V); + Exit->setTerminator(new (A) Return(V)); add(Entry); add(Exit); } SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), - Entry(nullptr), Exit(nullptr) { + Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { // TODO: set entry and exit! } + /// Return true if this CFG is valid. + bool valid() const { return Entry && Exit && Blocks.size() > 0; } + + /// Return true if this CFG has been normalized. + /// After normalization, blocks are in topological order, and block and + /// instruction IDs have been assigned. + bool normal() const { return Normal; } + iterator begin() { return Blocks.begin(); } iterator end() { return Blocks.end(); } @@ -1565,9 +1730,17 @@ public: const BasicBlock *exit() const { return Exit; } BasicBlock *exit() { return Exit; } + /// Return the number of blocks in the CFG. + /// Block::blockID() will return a number less than numBlocks(); + size_t numBlocks() const { return Blocks.size(); } + + /// Return the total number of instructions in the CFG. + /// This is useful for building instruction side-tables; + /// A call to SExpr::id() will return a number less than numInstructions(). + unsigned numInstructions() { return NumInstructions; } + inline void add(BasicBlock *BB) { - assert(BB->CFGPtr == nullptr || BB->CFGPtr == this); - BB->setBlockID(Blocks.size()); + assert(BB->CFGPtr == nullptr); BB->CFGPtr = this; Blocks.reserveCheck(1, Arena); Blocks.push_back(BB); @@ -1576,13 +1749,13 @@ public: void setEntry(BasicBlock *BB) { Entry = BB; } void setExit(BasicBlock *BB) { Exit = BB; } - // Set varable ids in all blocks. - void renumberVars(); + void computeNormalForm(); template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { Vs.enterCFG(*this); typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); + for (auto *B : Blocks) { Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); } @@ -1590,100 +1763,28 @@ public: return Vs.reduceSCFG(*this, Bbs); } - template <class C> typename C::CType compare(SCFG *E, C &Cmp) { - // TODO -- implement CFG comparisons + template <class C> + typename C::CType compare(const SCFG *E, C &Cmp) const { + // TODO: implement CFG comparisons return Cmp.comparePointers(this, E); } private: + void renumberInstrs(); // assign unique ids to all instructions + +private: MemRegionRef Arena; BlockArray Blocks; BasicBlock *Entry; BasicBlock *Exit; + unsigned NumInstructions; + bool Normal; }; -class Goto : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } - - Goto(BasicBlock *B, unsigned I) - : SExpr(COP_Goto), TargetBlock(B), Index(I) {} - Goto(const Goto &G, BasicBlock *B, unsigned I) - : SExpr(COP_Goto), TargetBlock(B), Index(I) {} - const BasicBlock *targetBlock() const { return TargetBlock; } - BasicBlock *targetBlock() { return TargetBlock; } - - unsigned index() const { return Index; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); - return Vs.reduceGoto(*this, Ntb); - } - - 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, unsigned TI, unsigned EI) - : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), - ThenIndex(TI), ElseIndex(EI) - {} - Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E, - unsigned TI, unsigned EI) - : SExpr(COP_Branch), Condition(C), ThenBlock(T), ElseBlock(E), - ThenIndex(TI), ElseIndex(EI) - {} - - const SExpr *condition() const { return Condition; } - SExpr *condition() { return Condition; } - - const BasicBlock *thenBlock() const { return ThenBlock; } - BasicBlock *thenBlock() { return ThenBlock; } - - const BasicBlock *elseBlock() const { return ElseBlock; } - BasicBlock *elseBlock() { return ElseBlock; } - - unsigned thenIndex() const { return ThenIndex; } - unsigned elseIndex() const { return ElseIndex; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); - BasicBlock *Ntb = Vs.reduceBasicBlockRef(ThenBlock); - BasicBlock *Nte = Vs.reduceBasicBlockRef(ElseBlock); - return Vs.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; - unsigned ThenIndex; - unsigned ElseIndex; -}; - - -// An identifier, e.g. 'foo' or 'x'. -// This is a pseduo-term; it will be lowered to a variable or projection. +/// An identifier, e.g. 'foo' or 'x'. +/// This is a pseduo-term; it will be lowered to a variable or projection. class Identifier : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } @@ -1698,7 +1799,8 @@ public: return Vs.reduceIdentifier(*this); } - template <class C> typename C::CType compare(Identifier* E, C& Cmp) { + template <class C> + typename C::CType compare(const Identifier* E, C& Cmp) const { return Cmp.compareStrings(name(), E->name()); } @@ -1707,8 +1809,8 @@ private: }; -// An if-then-else expression. -// This is a pseduo-term; it will be lowered to a branch in a CFG. +/// An if-then-else expression. +/// This is a pseduo-term; it will be lowered to a branch in a CFG. class IfThenElse : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } @@ -1720,14 +1822,14 @@ public: : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) { } - SExpr *condition() { return Condition.get(); } // Address to store to - const SExpr *condition() const { return Condition.get(); } + SExpr *condition() { return Condition; } // Address to store to + const SExpr *condition() const { return Condition; } - SExpr *thenExpr() { return ThenExpr.get(); } // Value to store - const SExpr *thenExpr() const { return ThenExpr.get(); } + SExpr *thenExpr() { return ThenExpr; } // Value to store + const SExpr *thenExpr() const { return ThenExpr; } - SExpr *elseExpr() { return ElseExpr.get(); } // Value to store - const SExpr *elseExpr() const { return ElseExpr.get(); } + SExpr *elseExpr() { return ElseExpr; } // Value to store + const SExpr *elseExpr() const { return ElseExpr; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1737,7 +1839,8 @@ public: return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); } - template <class C> typename C::CType compare(IfThenElse* E, C& Cmp) { + template <class C> + typename C::CType compare(const IfThenElse* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(condition(), E->condition()); if (Cmp.notTrue(Ct)) return Ct; @@ -1748,14 +1851,14 @@ public: } private: - SExprRef Condition; - SExprRef ThenExpr; - SExprRef ElseExpr; + SExpr* Condition; + SExpr* ThenExpr; + SExpr* ElseExpr; }; -// A let-expression, e.g. let x=t; u. -// This is a pseduo-term; it will be lowered to instructions in a CFG. +/// A let-expression, e.g. let x=t; u. +/// This is a pseduo-term; it will be lowered to instructions in a CFG. class Let : public SExpr { public: static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } @@ -1770,8 +1873,8 @@ public: Variable *variableDecl() { return VarDecl; } const Variable *variableDecl() const { return VarDecl; } - SExpr *body() { return Body.get(); } - const SExpr *body() const { return Body.get(); } + SExpr *body() { return Body; } + const SExpr *body() const { return Body; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1784,7 +1887,8 @@ public: return Vs.reduceLet(*this, Nvd, E1); } - template <class C> typename C::CType compare(Let* E, C& Cmp) { + template <class C> + typename C::CType compare(const Let* E, C& Cmp) const { typename C::CType Ct = Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); if (Cmp.notTrue(Ct)) @@ -1797,17 +1901,18 @@ public: private: Variable *VarDecl; - SExprRef Body; + SExpr* Body; }; -SExpr *getCanonicalVal(SExpr *E); -void simplifyIncompleteArg(Variable *V, til::Phi *Ph); +const SExpr *getCanonicalVal(const SExpr *E); +SExpr* simplifyToCanonicalVal(SExpr *E); +void simplifyIncompleteArg(til::Phi *Ph); } // end namespace til } // end namespace threadSafety } // end namespace clang -#endif // LLVM_CLANG_THREAD_SAFETY_TIL_H +#endif diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index bc1490b4a448..705fe910d092 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -14,10 +14,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H -#define LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H #include "ThreadSafetyTIL.h" +#include <ostream> namespace clang { namespace threadSafety { @@ -56,11 +57,16 @@ public: // 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. - typename R::R_SExpr traverse(SExprRef &E, typename R::R_Ctx Ctx) { - return traverse(E.get(), Ctx); + // E is a reference, so this can be use for in-place updates. + // The type T must be a subclass of SExpr. + template <class T> + typename R::R_SExpr traverse(T* &E, typename R::R_Ctx Ctx) { + return traverseSExpr(E, Ctx); } - typename R::R_SExpr traverse(SExpr *E, typename R::R_Ctx Ctx) { + // Override this method to do something for every expression. + // Does not allow in-place updates. + typename R::R_SExpr traverseSExpr(SExpr *E, typename R::R_Ctx Ctx) { return traverseByCase(E, Ctx); } @@ -73,6 +79,7 @@ public: #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF } + return self()->reduceNull(); } // Traverse e, by static dispatch on the type "X" of e. @@ -90,10 +97,10 @@ public: class SimpleReducerBase { public: enum TraversalKind { - TRV_Normal, - TRV_Decl, - TRV_Lazy, - TRV_Type + TRV_Normal, // ordinary subexpressions + TRV_Decl, // declarations (e.g. function bodies) + TRV_Lazy, // expressions that require lazy evaluation + TRV_Type // type expressions }; // R_Ctx defines a "context" for the traversal, which encodes information @@ -145,153 +152,6 @@ protected: }; -// Implements a traversal 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. -template<class Self> -class CopyReducer : public Traversal<Self, CopyReducerBase>, - public CopyReducerBase { -public: - CopyReducer(MemRegionRef A) : CopyReducerBase(A) {} - -public: - R_SExpr reduceNull() { - return nullptr; - } - // 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); - } - template<class T> - R_SExpr reduceLiteralT(LiteralT<T> &Orig) { - return new (Arena) LiteralT<T>(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 reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) { - return new (Arena) Field(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 reduceArrayIndex(ArrayIndex &Orig, R_SExpr E0, R_SExpr E1) { - return new (Arena) ArrayIndex(Orig, E0, E1); - } - R_SExpr reduceArrayAdd(ArrayAdd &Orig, R_SExpr E0, R_SExpr E1) { - return new (Arena) ArrayAdd(Orig, E0, E1); - } - R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { - return new (Arena) UnaryOp(Orig, E0); - } - 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 nullptr; // FIXME: implement CFG rewriting - } - R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As, - Container<Variable *> &Is, R_SExpr T) { - return nullptr; // FIXME: implement CFG rewriting - } - R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) { - return new (Arena) Phi(Orig, std::move(As.Elems)); - } - R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { - return new (Arena) Goto(Orig, B, 0); // FIXME: set index - } - R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { - return new (Arena) Branch(O, C, B0, B1, 0, 0); // FIXME: set indices - } - - R_SExpr reduceIdentifier(Identifier &Orig) { - return new (Arena) Identifier(Orig); - } - R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) { - return new (Arena) IfThenElse(Orig, C, T, E); - } - R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) { - return new (Arena) Let(Orig, Nvd, B); - } - - // 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) {} - void enterBasicBlock(BasicBlock &BB) {} - void exitBasicBlock(BasicBlock &BB) {} - - // Map Variable references to their rewritten definitions. - Variable *reduceVariableRef(Variable *Ovd) { return Ovd; } - - // Map BasicBlock references to their rewritten definitions. - BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } -}; - - -class SExprCopier : public CopyReducer<SExprCopier> { -public: - typedef SExpr *R_SExpr; - - SExprCopier(MemRegionRef A) : CopyReducer(A) { } - - // Create a copy of e in region a. - static SExpr *copy(SExpr *E, MemRegionRef A) { - SExprCopier Copier(A); - return Copier.traverse(E, TRV_Normal); - } -}; - - - // Base class for visit traversals. class VisitReducerBase : public SimpleReducerBase { public: @@ -366,8 +226,8 @@ public: R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { return Bbs.Success; } - R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<Variable *> &As, - Container<Variable *> &Is, R_SExpr T) { + R_BasicBlock reduceBasicBlock(BasicBlock &Orig, Container<R_SExpr> &As, + Container<R_SExpr> &Is, R_SExpr T) { return (As.Success && Is.Success && T); } R_SExpr reducePhi(Phi &Orig, Container<R_SExpr> &As) { @@ -379,6 +239,9 @@ public: R_SExpr reduceBranch(Branch &O, R_SExpr C, BasicBlock *B0, BasicBlock *B1) { return C; } + R_SExpr reduceReturn(Return &O, R_SExpr E) { + return E; + } R_SExpr reduceIdentifier(Identifier &Orig) { return true; @@ -423,7 +286,7 @@ protected: Self *self() { return reinterpret_cast<Self *>(this); } public: - bool compareByCase(SExpr *E1, SExpr* E2) { + bool compareByCase(const SExpr *E1, const SExpr* E2) { switch (E1->opcode()) { #define TIL_OPCODE_DEF(X) \ case COP_##X: \ @@ -431,6 +294,7 @@ public: #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF } + return false; } }; @@ -449,38 +313,86 @@ public: bool compareStrings (StringRef s, StringRef r) { return s == r; } bool comparePointers(const void* P, const void* Q) { return P == Q; } - bool compare(SExpr *E1, SExpr* E2) { + bool compare(const SExpr *E1, const 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 enterScope(const Variable* V1, const Variable* V2) { } void leaveScope() { } - bool compareVariableRefs(Variable* V1, Variable* V2) { + bool compareVariableRefs(const Variable* V1, const Variable* V2) { return V1 == V2; } - static bool compareExprs(SExpr *E1, SExpr* E2) { + static bool compareExprs(const SExpr *E1, const SExpr* E2) { EqualsComparator Eq; return Eq.compare(E1, E2); } }; + +class MatchComparator : public Comparator<MatchComparator> { +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 compareStrings (StringRef s, StringRef r) { return s == r; } + bool comparePointers(const void* P, const void* Q) { return P == Q; } + + bool compare(const SExpr *E1, const SExpr* E2) { + // Wildcards match anything. + if (E1->opcode() == COP_Wildcard || E2->opcode() == COP_Wildcard) + return true; + // otherwise normal equality. + if (E1->opcode() != E2->opcode()) + return false; + return compareByCase(E1, E2); + } + + // TODO -- handle alpha-renaming of variables + void enterScope(const Variable* V1, const Variable* V2) { } + void leaveScope() { } + + bool compareVariableRefs(const Variable* V1, const Variable* V2) { + return V1 == V2; + } + + static bool compareExprs(const SExpr *E1, const SExpr* E2) { + MatchComparator Matcher; + return Matcher.compare(E1, E2); + } +}; + + + +// inline std::ostream& operator<<(std::ostream& SS, StringRef R) { +// return SS.write(R.data(), R.size()); +// } + // Pretty printer for TIL expressions template <typename Self, typename StreamType> class PrettyPrinter { private: bool Verbose; // Print out additional information bool Cleanup; // Omit redundant decls. + bool CStyle; // Print exprs in C-like syntax. public: - PrettyPrinter(bool V = false, bool C = true) : Verbose(V), Cleanup(C) { } + PrettyPrinter(bool V = false, bool C = true, bool CS = true) + : Verbose(V), Cleanup(C), CStyle(CS) + {} - static void print(SExpr *E, StreamType &SS) { + static void print(const SExpr *E, StreamType &SS) { Self printer; printer.printSExpr(E, SS, Prec_MAX); } @@ -502,7 +414,7 @@ protected: static const unsigned Prec_MAX = 6; // Return the precedence of a given node, for use in pretty printing. - unsigned precedence(SExpr *E) { + unsigned precedence(const SExpr *E) { switch (E->opcode()) { case COP_Future: return Prec_Atom; case COP_Undefined: return Prec_Atom; @@ -529,13 +441,14 @@ protected: case COP_UnaryOp: return Prec_Unary; case COP_BinaryOp: return Prec_Binary; - case COP_Cast: return Prec_Unary; + case COP_Cast: return Prec_Atom; case COP_SCFG: return Prec_Decl; case COP_BasicBlock: return Prec_MAX; case COP_Phi: return Prec_Atom; case COP_Goto: return Prec_Atom; case COP_Branch: return Prec_Atom; + case COP_Return: return Prec_Other; case COP_Identifier: return Prec_Atom; case COP_IfThenElse: return Prec_Other; @@ -544,22 +457,29 @@ protected: return Prec_MAX; } - void printBlockLabel(StreamType & SS, BasicBlock *BB, unsigned index) { + void printBlockLabel(StreamType & SS, const BasicBlock *BB, int index) { if (!BB) { SS << "BB_null"; return; } SS << "BB_"; SS << BB->blockID(); - SS << ":"; - SS << index; + if (index >= 0) { + SS << ":"; + SS << index; + } } - void printSExpr(SExpr *E, StreamType &SS, unsigned P) { + + void printSExpr(const SExpr *E, StreamType &SS, unsigned P, bool Sub=true) { if (!E) { self()->printNull(SS); return; } + if (Sub && E->block() && E->opcode() != COP_Variable) { + SS << "_x" << E->id(); + return; + } if (self()->precedence(E) > P) { // Wrap expr in () if necessary. SS << "("; @@ -582,28 +502,28 @@ protected: SS << "#null"; } - void printFuture(Future *E, StreamType &SS) { + void printFuture(const Future *E, StreamType &SS) { self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom); } - void printUndefined(Undefined *E, StreamType &SS) { + void printUndefined(const Undefined *E, StreamType &SS) { SS << "#undefined"; } - void printWildcard(Wildcard *E, StreamType &SS) { - SS << "_"; + void printWildcard(const Wildcard *E, StreamType &SS) { + SS << "*"; } template<class T> - void printLiteralT(LiteralT<T> *E, StreamType &SS) { + void printLiteralT(const LiteralT<T> *E, StreamType &SS) { SS << E->value(); } - void printLiteralT(LiteralT<uint8_t> *E, StreamType &SS) { + void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) { SS << "'" << E->value() << "'"; } - void printLiteral(Literal *E, StreamType &SS) { + void printLiteral(const Literal *E, StreamType &SS) { if (E->clangExpr()) { SS << getSourceLiteralString(E->clangExpr()); return; @@ -685,25 +605,18 @@ protected: SS << "#lit"; } - void printLiteralPtr(LiteralPtr *E, StreamType &SS) { + void printLiteralPtr(const LiteralPtr *E, StreamType &SS) { SS << E->clangDecl()->getNameAsString(); } - void printVariable(Variable *V, StreamType &SS, bool IsVarDecl = false) { - if (!IsVarDecl && Cleanup) { - SExpr* E = getCanonicalVal(V); - if (E != V) { - printSExpr(E, SS, Prec_Atom); - return; - } - } - if (V->kind() == Variable::VK_LetBB) - SS << V->name() << V->getBlockID() << "_" << V->getID(); + void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) { + if (CStyle && V->kind() == Variable::VK_SFun) + SS << "this"; else - SS << V->name() << V->getID(); + SS << V->name() << V->id(); } - void printFunction(Function *E, StreamType &SS, unsigned sugared = 0) { + void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) { switch (sugared) { default: SS << "\\("; // Lambda @@ -719,7 +632,7 @@ protected: SS << ": "; self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX); - SExpr *B = E->body(); + const SExpr *B = E->body(); if (B && B->opcode() == COP_Function) self()->printFunction(cast<Function>(B), SS, 2); else { @@ -728,29 +641,29 @@ protected: } } - void printSFunction(SFunction *E, StreamType &SS) { + void printSFunction(const SFunction *E, StreamType &SS) { SS << "@"; self()->printVariable(E->variableDecl(), SS, true); SS << " "; self()->printSExpr(E->body(), SS, Prec_Decl); } - void printCode(Code *E, StreamType &SS) { + void printCode(const Code *E, StreamType &SS) { SS << ": "; self()->printSExpr(E->returnType(), SS, Prec_Decl-1); SS << " -> "; self()->printSExpr(E->body(), SS, Prec_Decl); } - void printField(Field *E, StreamType &SS) { + void printField(const Field *E, StreamType &SS) { SS << ": "; self()->printSExpr(E->range(), 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(); + void printApply(const Apply *E, StreamType &SS, bool sugared = false) { + const SExpr *F = E->fun(); if (F->opcode() == COP_Apply) { printApply(cast<Apply>(F), SS, true); SS << ", "; @@ -763,7 +676,7 @@ protected: SS << ")$"; } - void printSApply(SApply *E, StreamType &SS) { + void printSApply(const SApply *E, StreamType &SS) { self()->printSExpr(E->sfun(), SS, Prec_Postfix); if (E->isDelegation()) { SS << "@("; @@ -772,14 +685,36 @@ protected: } } - void printProject(Project *E, StreamType &SS) { + void printProject(const Project *E, StreamType &SS) { + if (CStyle) { + // Omit the this-> + if (const SApply *SAP = dyn_cast<SApply>(E->record())) { + if (const Variable *V = dyn_cast<Variable>(SAP->sfun())) { + if (!SAP->isDelegation() && V->kind() == Variable::VK_SFun) { + SS << E->slotName(); + return; + } + } + } + if (isa<Wildcard>(E->record())) { + // handle existentials + SS << "&"; + SS << E->clangDecl()->getQualifiedNameAsString(); + return; + } + } self()->printSExpr(E->record(), SS, Prec_Postfix); - SS << "."; + if (CStyle && E->isArrow()) { + SS << "->"; + } + else { + SS << "."; + } SS << E->slotName(); } - void printCall(Call *E, StreamType &SS) { - SExpr *T = E->target(); + void printCall(const Call *E, StreamType &SS) { + const SExpr *T = E->target(); if (T->opcode() == COP_Apply) { self()->printApply(cast<Apply>(T), SS, true); SS << ")"; @@ -790,52 +725,60 @@ protected: } } - void printAlloc(Alloc *E, StreamType &SS) { + void printAlloc(const Alloc *E, StreamType &SS) { SS << "new "; self()->printSExpr(E->dataType(), SS, Prec_Other-1); } - void printLoad(Load *E, StreamType &SS) { + void printLoad(const Load *E, StreamType &SS) { self()->printSExpr(E->pointer(), SS, Prec_Postfix); - SS << "^"; + if (!CStyle) + SS << "^"; } - void printStore(Store *E, StreamType &SS) { + void printStore(const Store *E, StreamType &SS) { self()->printSExpr(E->destination(), SS, Prec_Other-1); SS << " := "; self()->printSExpr(E->source(), SS, Prec_Other-1); } - void printArrayIndex(ArrayIndex *E, StreamType &SS) { + void printArrayIndex(const ArrayIndex *E, StreamType &SS) { self()->printSExpr(E->array(), SS, Prec_Postfix); SS << "["; self()->printSExpr(E->index(), SS, Prec_MAX); SS << "]"; } - void printArrayAdd(ArrayAdd *E, StreamType &SS) { + void printArrayAdd(const ArrayAdd *E, StreamType &SS) { self()->printSExpr(E->array(), SS, Prec_Postfix); SS << " + "; self()->printSExpr(E->index(), SS, Prec_Atom); } - void printUnaryOp(UnaryOp *E, StreamType &SS) { + void printUnaryOp(const UnaryOp *E, StreamType &SS) { SS << getUnaryOpcodeString(E->unaryOpcode()); self()->printSExpr(E->expr(), SS, Prec_Unary); } - void printBinaryOp(BinaryOp *E, StreamType &SS) { + void printBinaryOp(const BinaryOp *E, StreamType &SS) { self()->printSExpr(E->expr0(), SS, Prec_Binary-1); SS << " " << getBinaryOpcodeString(E->binaryOpcode()) << " "; self()->printSExpr(E->expr1(), SS, Prec_Binary-1); } - void printCast(Cast *E, StreamType &SS) { - SS << "%"; + void printCast(const Cast *E, StreamType &SS) { + if (!CStyle) { + SS << "cast["; + SS << E->castOpcode(); + SS << "]("; + self()->printSExpr(E->expr(), SS, Prec_Unary); + SS << ")"; + return; + } self()->printSExpr(E->expr(), SS, Prec_Unary); } - void printSCFG(SCFG *E, StreamType &SS) { + void printSCFG(const SCFG *E, StreamType &SS) { SS << "CFG {\n"; for (auto BBI : *E) { printBasicBlock(BBI, SS); @@ -844,39 +787,45 @@ protected: newline(SS); } - void printBasicBlock(BasicBlock *E, StreamType &SS) { + + void printBBInstr(const SExpr *E, StreamType &SS) { + bool Sub = false; + if (E->opcode() == COP_Variable) { + auto *V = cast<Variable>(E); + SS << "let " << V->name() << V->id() << " = "; + E = V->definition(); + Sub = true; + } + else if (E->opcode() != COP_Store) { + SS << "let _x" << E->id() << " = "; + } + self()->printSExpr(E, SS, Prec_MAX, Sub); + SS << ";"; + newline(SS); + } + + void printBasicBlock(const BasicBlock *E, StreamType &SS) { SS << "BB_" << E->blockID() << ":"; if (E->parent()) SS << " BB_" << E->parent()->blockID(); newline(SS); - for (auto *A : E->arguments()) { - SS << "let "; - self()->printVariable(A, SS, true); - SS << " = "; - self()->printSExpr(A->definition(), SS, Prec_MAX); - SS << ";"; - newline(SS); - } - for (auto *I : E->instructions()) { - if (I->definition()->opcode() != COP_Store) { - SS << "let "; - self()->printVariable(I, SS, true); - SS << " = "; - } - self()->printSExpr(I->definition(), SS, Prec_MAX); - SS << ";"; - newline(SS); - } - SExpr *T = E->terminator(); + + for (auto *A : E->arguments()) + printBBInstr(A, SS); + + for (auto *I : E->instructions()) + printBBInstr(I, SS); + + const SExpr *T = E->terminator(); if (T) { - self()->printSExpr(T, SS, Prec_MAX); + self()->printSExpr(T, SS, Prec_MAX, false); SS << ";"; newline(SS); } newline(SS); } - void printPhi(Phi *E, StreamType &SS) { + void printPhi(const Phi *E, StreamType &SS) { SS << "phi("; if (E->status() == Phi::PH_SingleVal) self()->printSExpr(E->values()[0], SS, Prec_MAX); @@ -891,25 +840,38 @@ protected: SS << ")"; } - void printGoto(Goto *E, StreamType &SS) { + void printGoto(const Goto *E, StreamType &SS) { SS << "goto "; printBlockLabel(SS, E->targetBlock(), E->index()); } - void printBranch(Branch *E, StreamType &SS) { + void printBranch(const Branch *E, StreamType &SS) { SS << "branch ("; self()->printSExpr(E->condition(), SS, Prec_MAX); SS << ") "; - printBlockLabel(SS, E->thenBlock(), E->thenIndex()); + printBlockLabel(SS, E->thenBlock(), -1); SS << " "; - printBlockLabel(SS, E->elseBlock(), E->elseIndex()); + printBlockLabel(SS, E->elseBlock(), -1); } - void printIdentifier(Identifier *E, StreamType &SS) { + void printReturn(const Return *E, StreamType &SS) { + SS << "return "; + self()->printSExpr(E->returnValue(), SS, Prec_Other); + } + + void printIdentifier(const Identifier *E, StreamType &SS) { SS << E->name(); } - void printIfThenElse(IfThenElse *E, StreamType &SS) { + void printIfThenElse(const IfThenElse *E, StreamType &SS) { + if (CStyle) { + printSExpr(E->condition(), SS, Prec_Unary); + SS << " ? "; + printSExpr(E->thenExpr(), SS, Prec_Unary); + SS << " : "; + printSExpr(E->elseExpr(), SS, Prec_Unary); + return; + } SS << "if ("; printSExpr(E->condition(), SS, Prec_MAX); SS << ") then "; @@ -918,7 +880,7 @@ protected: printSExpr(E->elseExpr(), SS, Prec_Other); } - void printLet(Let *E, StreamType &SS) { + void printLet(const Let *E, StreamType &SS) { SS << "let "; printVariable(E->variableDecl(), SS, true); SS << " = "; @@ -929,6 +891,10 @@ protected: }; +class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> { }; + + + } // end namespace til } // end namespace threadSafety } // end namespace clang diff --git a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index 31200a3a7253..ba3e0e519b09 100644 --- a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -11,19 +11,19 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_THREAD_SAFETY_UTIL_H -#define LLVM_CLANG_THREAD_SAFETY_UTIL_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H +#include "clang/AST/ExprCXX.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/AlignOf.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" -#include "clang/AST/ExprCXX.h" - #include <cassert> #include <cstddef> -#include <vector> +#include <ostream> #include <utility> +#include <vector> namespace clang { namespace threadSafety { @@ -142,18 +142,35 @@ public: assert(i < Size && "Array index out of bounds."); return Data[i]; } + T &back() { + assert(Size && "No elements in the array."); + return Data[Size - 1]; + } + const T &back() const { + assert(Size && "No elements in the array."); + return Data[Size - 1]; + } iterator begin() { return Data; } - iterator end() { return Data + Size; } + iterator end() { return Data + Size; } + + const_iterator begin() const { return Data; } + const_iterator end() const { return Data + Size; } const_iterator cbegin() const { return Data; } - const_iterator cend() const { return Data + Size; } + const_iterator cend() const { return Data + Size; } void push_back(const T &Elem) { assert(Size < Capacity); Data[Size++] = Elem; } + // drop last n elements from array + void drop(unsigned n = 0) { + assert(Size > n); + Size -= n; + } + void setValues(unsigned Sz, const T& C) { assert(Sz <= Capacity); Size = Sz; @@ -171,6 +188,37 @@ public: return J - Osz; } + // An adaptor to reverse a simple array + class ReverseAdaptor { + public: + ReverseAdaptor(SimpleArray &Array) : Array(Array) {} + // A reverse iterator used by the reverse adaptor + class Iterator { + public: + Iterator(T *Data) : Data(Data) {} + T &operator*() { return *Data; } + const T &operator*() const { return *Data; } + Iterator &operator++() { + --Data; + return *this; + } + bool operator!=(Iterator Other) { return Data != Other.Data; } + + private: + T *Data; + }; + Iterator begin() { return Array.end() - 1; } + Iterator end() { return Array.begin() - 1; } + const Iterator begin() const { return Array.end() - 1; } + const Iterator end() const { return Array.begin() - 1; } + + private: + SimpleArray &Array; + }; + + const ReverseAdaptor reverse() const { return ReverseAdaptor(*this); } + ReverseAdaptor reverse() { return ReverseAdaptor(*this); } + private: // std::max is annoying here, because it requires a reference, // thus forcing InitialCapacity to be initialized outside the .h file. @@ -185,6 +233,7 @@ private: size_t Capacity; }; + } // end namespace til @@ -310,6 +359,11 @@ private: }; +inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { + return ss.write(str.data(), str.size()); +} + + } // end namespace threadSafety } // end namespace clang diff --git a/include/clang/Analysis/Analyses/UninitializedValues.h b/include/clang/Analysis/Analyses/UninitializedValues.h index 188722d94b3a..53ff20c23560 100644 --- a/include/clang/Analysis/Analyses/UninitializedValues.h +++ b/include/clang/Analysis/Analyses/UninitializedValues.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_UNINIT_VALS_H -#define LLVM_CLANG_UNINIT_VALS_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H #include "clang/AST/Stmt.h" #include "llvm/ADT/SmallVector.h" diff --git a/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h index 08e335418ab7..0ebdf15f2c4e 100644 --- a/include/clang/Analysis/AnalysisContext.h +++ b/include/clang/Analysis/AnalysisContext.h @@ -17,6 +17,7 @@ #include "clang/AST/Decl.h" #include "clang/Analysis/CFG.h" +#include "clang/Analysis/CodeInjector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/Support/Allocator.h" @@ -143,6 +144,14 @@ public: /// \sa getBody bool isBodyAutosynthesized() const; + /// \brief Checks if the body of the Decl is generated by the BodyFarm from a + /// model file. + /// + /// Note, the lookup is not free. We are going to call getBody behind + /// the scenes. + /// \sa getBody + bool isBodyAutosynthesizedFromModelFile() const; + CFG *getCFG(); CFGStmtMap *getCFGStmtMap(); @@ -398,6 +407,10 @@ class AnalysisDeclContextManager { ContextMap Contexts; LocationContextManager LocContexts; CFG::BuildOptions cfgBuildOptions; + + /// Pointer to an interface that can provide function bodies for + /// declarations from external source. + std::unique_ptr<CodeInjector> Injector; /// Flag to indicate whether or not bodies should be synthesized /// for well-known functions. @@ -410,7 +423,8 @@ public: bool addTemporaryDtors = false, bool synthesizeBodies = false, bool addStaticInitBranches = false, - bool addCXXNewAllocator = true); + bool addCXXNewAllocator = true, + CodeInjector* injector = nullptr); ~AnalysisDeclContextManager(); diff --git a/include/clang/Analysis/AnalysisDiagnostic.h b/include/clang/Analysis/AnalysisDiagnostic.h index 33c940e7bbf0..8d28971cfe5c 100644 --- a/include/clang/Analysis/AnalysisDiagnostic.h +++ b/include/clang/Analysis/AnalysisDiagnostic.h @@ -7,8 +7,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_DIAGNOSTICANALYSIS_H -#define LLVM_CLANG_DIAGNOSTICANALYSIS_H +#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H +#define LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H #include "clang/Basic/Diagnostic.h" diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index 891fb90691f3..beea867228d6 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_CFG_H -#define LLVM_CLANG_CFG_H +#ifndef LLVM_CLANG_ANALYSIS_CFG_H +#define LLVM_CLANG_ANALYSIS_CFG_H #include "clang/AST/Stmt.h" #include "clang/Analysis/Support/BumpVector.h" @@ -811,10 +811,9 @@ public: ImplTy I; }; - /// buildCFG - Builds a CFG from an AST. The responsibility to free the - /// constructed CFG belongs to the caller. - static CFG* buildCFG(const Decl *D, Stmt *AST, ASTContext *C, - const BuildOptions &BO); + /// buildCFG - Builds a CFG from an AST. + static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, + const BuildOptions &BO); /// createBlock - Create a new block in the CFG. The CFG owns the block; /// the caller should not directly free it. diff --git a/include/clang/Analysis/CFGStmtMap.h b/include/clang/Analysis/CFGStmtMap.h index 6e8e140afb23..4dfa91df0f42 100644 --- a/include/clang/Analysis/CFGStmtMap.h +++ b/include/clang/Analysis/CFGStmtMap.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_CFGSTMTMAP_H -#define LLVM_CLANG_CFGSTMTMAP_H +#ifndef LLVM_CLANG_ANALYSIS_CFGSTMTMAP_H +#define LLVM_CLANG_ANALYSIS_CFGSTMTMAP_H #include "clang/Analysis/CFG.h" diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h index 593ba575c78e..eda22a57e8a5 100644 --- a/include/clang/Analysis/CallGraph.h +++ b/include/clang/Analysis/CallGraph.h @@ -14,8 +14,8 @@ // edges to all externally available functions. //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH -#define LLVM_CLANG_ANALYSIS_CALLGRAPH +#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H +#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H #include "clang/AST/DeclBase.h" #include "clang/AST/RecursiveASTVisitor.h" diff --git a/include/clang/Analysis/CodeInjector.h b/include/clang/Analysis/CodeInjector.h new file mode 100644 index 000000000000..413a55b05b07 --- /dev/null +++ b/include/clang/Analysis/CodeInjector.h @@ -0,0 +1,46 @@ +//===-- CodeInjector.h ------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief Defines the clang::CodeInjector interface which is responsible for +/// injecting AST of function definitions that may not be available in the +/// original source. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CODEINJECTOR_H +#define LLVM_CLANG_ANALYSIS_CODEINJECTOR_H + +namespace clang { + +class Stmt; +class FunctionDecl; +class ObjCMethodDecl; + +/// \brief CodeInjector is an interface which is responsible for injecting AST +/// of function definitions that may not be available in the original source. +/// +/// The getBody function will be called each time the static analyzer examines a +/// function call that has no definition available in the current translation +/// unit. If the returned statement is not a null pointer, it is assumed to be +/// the body of a function which will be used for the analysis. The source of +/// the body can be arbitrary, but it is advised to use memoization to avoid +/// unnecessary reparsing of the external source that provides the body of the +/// functions. +class CodeInjector { +public: + CodeInjector(); + virtual ~CodeInjector(); + + virtual Stmt *getBody(const FunctionDecl *D) = 0; + virtual Stmt *getBody(const ObjCMethodDecl *D) = 0; +}; +} + +#endif diff --git a/include/clang/Analysis/DomainSpecific/CocoaConventions.h b/include/clang/Analysis/DomainSpecific/CocoaConventions.h index e6a2f13a0b80..8b3fcff52d08 100644 --- a/include/clang/Analysis/DomainSpecific/CocoaConventions.h +++ b/include/clang/Analysis/DomainSpecific/CocoaConventions.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_DS_COCOA -#define LLVM_CLANG_ANALYSIS_DS_COCOA +#ifndef LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_COCOACONVENTIONS_H +#define LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_COCOACONVENTIONS_H #include "clang/Basic/LLVM.h" #include "llvm/ADT/StringRef.h" diff --git a/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h b/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h index 930c2bd0925b..f9e800a4a412 100644 --- a/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h +++ b/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_DS_OBJCNORETURN -#define LLVM_CLANG_ANALYSIS_DS_OBJCNORETURN +#ifndef LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_OBJCNORETURN_H +#define LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_OBJCNORETURN_H #include "clang/Basic/IdentifierTable.h" diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index 57324d042908..f87271550c20 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT -#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT +#ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H +#define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" diff --git a/include/clang/Analysis/Support/BumpVector.h b/include/clang/Analysis/Support/BumpVector.h index 6d0427ba92b5..841adf64557d 100644 --- a/include/clang/Analysis/Support/BumpVector.h +++ b/include/clang/Analysis/Support/BumpVector.h @@ -16,8 +16,8 @@ // refactor this core logic into something common that is shared between // the two. The main thing that is different is the allocation strategy. -#ifndef LLVM_CLANG_BUMP_VECTOR -#define LLVM_CLANG_BUMP_VECTOR +#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H +#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H #include "llvm/ADT/PointerIntPair.h" #include "llvm/Support/Allocator.h" @@ -241,4 +241,4 @@ void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { } } // end: clang namespace -#endif // end: LLVM_CLANG_BUMP_VECTOR +#endif |