diff options
Diffstat (limited to 'include/clang/Analysis/Analyses')
16 files changed, 0 insertions, 5753 deletions
diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h deleted file mode 100644 index cc14c7b..0000000 --- a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h +++ /dev/null @@ -1,49 +0,0 @@ -//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines a flow-sensitive, (mostly) path-insensitive reachability -// analysis based on Clang's CFGs. Clients can query if a given basic block -// is reachable within the CFG. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_CFGREACHABILITYANALYSIS_H - -#include "llvm/ADT/BitVector.h" -#include "llvm/ADT/DenseMap.h" - -namespace clang { - -class CFG; -class CFGBlock; - -// A class that performs reachability queries for CFGBlocks. Several internal -// checks in this checker require reachability information. The requests all -// tend to have a common destination, so we lazily do a predecessor search -// from the destination node and cache the results to prevent work -// duplication. -class CFGReverseBlockReachabilityAnalysis { - typedef llvm::BitVector ReachableSet; - typedef llvm::DenseMap<unsigned, ReachableSet> ReachableMap; - ReachableSet analyzed; - ReachableMap reachable; -public: - CFGReverseBlockReachabilityAnalysis(const CFG &cfg); - - /// Returns true if the block 'Dst' can be reached from block 'Src'. - bool isReachable(const CFGBlock *Src, const CFGBlock *Dst); - -private: - void mapReachability(const CFGBlock *Dst); -}; - -} - -#endif diff --git a/include/clang/Analysis/Analyses/Consumed.h b/include/clang/Analysis/Analyses/Consumed.h deleted file mode 100644 index 1f5aa12..0000000 --- a/include/clang/Analysis/Analyses/Consumed.h +++ /dev/null @@ -1,269 +0,0 @@ -//===- Consumed.h ----------------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// A intra-procedural analysis for checking consumed properties. This is based, -// in part, on research on linear types. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H - -#include "clang/AST/DeclCXX.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/StmtCXX.h" -#include "clang/Analysis/Analyses/PostOrderCFGView.h" -#include "clang/Analysis/AnalysisContext.h" -#include "clang/Basic/SourceLocation.h" - -namespace clang { -namespace consumed { - - enum ConsumedState { - // No state information for the given variable. - CS_None, - - CS_Unknown, - CS_Unconsumed, - CS_Consumed - }; - - class ConsumedStmtVisitor; - - typedef SmallVector<PartialDiagnosticAt, 1> OptionalNotes; - typedef std::pair<PartialDiagnosticAt, OptionalNotes> DelayedDiag; - typedef std::list<DelayedDiag> DiagList; - - class ConsumedWarningsHandlerBase { - - public: - - virtual ~ConsumedWarningsHandlerBase(); - - /// \brief Emit the warnings and notes left by the analysis. - virtual void emitDiagnostics() {} - - /// \brief Warn that a variable's state doesn't match at the entry and exit - /// of a loop. - /// - /// \param Loc -- The location of the end of the loop. - /// - /// \param VariableName -- The name of the variable that has a mismatched - /// state. - virtual void warnLoopStateMismatch(SourceLocation Loc, - StringRef VariableName) {} - - /// \brief Warn about parameter typestate mismatches upon return. - /// - /// \param Loc -- The SourceLocation of the return statement. - /// - /// \param ExpectedState -- The state the return value was expected to be - /// in. - /// - /// \param ObservedState -- The state the return value was observed to be - /// in. - virtual void warnParamReturnTypestateMismatch(SourceLocation Loc, - StringRef VariableName, - StringRef ExpectedState, - StringRef ObservedState) {} - - // FIXME: Add documentation. - virtual void warnParamTypestateMismatch(SourceLocation LOC, - StringRef ExpectedState, - StringRef ObservedState) {} - - // FIXME: This can be removed when the attr propagation fix for templated - // classes lands. - /// \brief Warn about return typestates set for unconsumable types. - /// - /// \param Loc -- The location of the attributes. - /// - /// \param TypeName -- The name of the unconsumable type. - virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc, - StringRef TypeName) {} - - /// \brief Warn about return typestate mismatches. - /// - /// \param Loc -- The SourceLocation of the return statement. - /// - /// \param ExpectedState -- The state the return value was expected to be - /// in. - /// - /// \param ObservedState -- The state the return value was observed to be - /// in. - virtual void warnReturnTypestateMismatch(SourceLocation Loc, - StringRef ExpectedState, - StringRef ObservedState) {} - - /// \brief Warn about use-while-consumed errors. - /// \param MethodName -- The name of the method that was incorrectly - /// invoked. - /// - /// \param State -- The state the object was used in. - /// - /// \param Loc -- The SourceLocation of the method invocation. - virtual void warnUseOfTempInInvalidState(StringRef MethodName, - StringRef State, - SourceLocation Loc) {} - - /// \brief Warn about use-while-consumed errors. - /// \param MethodName -- The name of the method that was incorrectly - /// invoked. - /// - /// \param State -- The state the object was used in. - /// - /// \param VariableName -- The name of the variable that holds the unique - /// value. - /// - /// \param Loc -- The SourceLocation of the method invocation. - virtual void warnUseInInvalidState(StringRef MethodName, - StringRef VariableName, - StringRef State, - SourceLocation Loc) {} - }; - - class ConsumedStateMap { - - typedef llvm::DenseMap<const VarDecl *, ConsumedState> VarMapType; - typedef llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState> - TmpMapType; - - protected: - - bool Reachable; - const Stmt *From; - VarMapType VarMap; - TmpMapType TmpMap; - - public: - ConsumedStateMap() : Reachable(true), From(nullptr) {} - ConsumedStateMap(const ConsumedStateMap &Other) - : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), - TmpMap() {} - - /// \brief Warn if any of the parameters being tracked are not in the state - /// they were declared to be in upon return from a function. - void checkParamsForReturnTypestate(SourceLocation BlameLoc, - ConsumedWarningsHandlerBase &WarningsHandler) const; - - /// \brief Clear the TmpMap. - void clearTemporaries(); - - /// \brief Get the consumed state of a given variable. - ConsumedState getState(const VarDecl *Var) const; - - /// \brief Get the consumed state of a given temporary value. - ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const; - - /// \brief Merge this state map with another map. - void intersect(const ConsumedStateMap &Other); - - void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack, - const ConsumedStateMap *LoopBackStates, - ConsumedWarningsHandlerBase &WarningsHandler); - - /// \brief Return true if this block is reachable. - bool isReachable() const { return Reachable; } - - /// \brief Mark the block as unreachable. - void markUnreachable(); - - /// \brief Set the source for a decision about the branching of states. - /// \param Source -- The statement that was the origin of a branching - /// decision. - void setSource(const Stmt *Source) { this->From = Source; } - - /// \brief Set the consumed state of a given variable. - void setState(const VarDecl *Var, ConsumedState State); - - /// \brief Set the consumed state of a given temporary value. - void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State); - - /// \brief Remove the temporary value from our state map. - void remove(const CXXBindTemporaryExpr *Tmp); - - /// \brief Tests to see if there is a mismatch in the states stored in two - /// maps. - /// - /// \param Other -- The second map to compare against. - bool operator!=(const ConsumedStateMap *Other) const; - }; - - class ConsumedBlockInfo { - std::vector<std::unique_ptr<ConsumedStateMap>> StateMapsArray; - std::vector<unsigned int> VisitOrder; - - public: - ConsumedBlockInfo() = default; - ConsumedBlockInfo &operator=(ConsumedBlockInfo &&Other) { - StateMapsArray = std::move(Other.StateMapsArray); - VisitOrder = std::move(Other.VisitOrder); - return *this; - } - - ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) - : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) { - unsigned int VisitOrderCounter = 0; - for (PostOrderCFGView::iterator BI = SortedGraph->begin(), - BE = SortedGraph->end(); BI != BE; ++BI) { - VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++; - } - } - - bool allBackEdgesVisited(const CFGBlock *CurrBlock, - const CFGBlock *TargetBlock); - - void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap, - std::unique_ptr<ConsumedStateMap> &OwnedStateMap); - void addInfo(const CFGBlock *Block, - std::unique_ptr<ConsumedStateMap> StateMap); - - ConsumedStateMap* borrowInfo(const CFGBlock *Block); - - void discardInfo(const CFGBlock *Block); - - std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block); - - bool isBackEdge(const CFGBlock *From, const CFGBlock *To); - bool isBackEdgeTarget(const CFGBlock *Block); - }; - - /// A class that handles the analysis of uniqueness violations. - class ConsumedAnalyzer { - - ConsumedBlockInfo BlockInfo; - std::unique_ptr<ConsumedStateMap> CurrStates; - - ConsumedState ExpectedReturnState; - - void determineExpectedReturnState(AnalysisDeclContext &AC, - const FunctionDecl *D); - bool splitState(const CFGBlock *CurrBlock, - const ConsumedStmtVisitor &Visitor); - - public: - - ConsumedWarningsHandlerBase &WarningsHandler; - - ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) - : WarningsHandler(WarningsHandler) {} - - ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } - - /// \brief Check a function's CFG for consumed violations. - /// - /// We traverse the blocks in the CFG, keeping track of the state of each - /// value who's type has uniquness annotations. If methods are invoked in - /// the wrong state a warning is issued. Each block in the CFG is traversed - /// exactly once. - void run(AnalysisDeclContext &AC); - }; -}} // end namespace clang::consumed - -#endif diff --git a/include/clang/Analysis/Analyses/Dominators.h b/include/clang/Analysis/Analyses/Dominators.h deleted file mode 100644 index 4524aeb..0000000 --- a/include/clang/Analysis/Analyses/Dominators.h +++ /dev/null @@ -1,210 +0,0 @@ -//==- Dominators.h - Implementation of dominators tree for Clang CFG C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the dominators tree functionality for Clang CFGs. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H - -#include "clang/Analysis/AnalysisContext.h" -#include "clang/Analysis/CFG.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/Support/GenericDomTree.h" -#include "llvm/Support/GenericDomTreeConstruction.h" - -// FIXME: There is no good reason for the domtree to require a print method -// which accepts an LLVM Module, so remove this (and the method's argument that -// needs it) when that is fixed. -namespace llvm { -class Module; -} - -namespace clang { - -class CFGBlock; -typedef llvm::DomTreeNodeBase<CFGBlock> DomTreeNode; - -/// \brief Concrete subclass of DominatorTreeBase for Clang -/// This class implements the dominators tree functionality given a Clang CFG. -/// -class DominatorTree : public ManagedAnalysis { - virtual void anchor(); -public: - llvm::DominatorTreeBase<CFGBlock>* DT; - - DominatorTree() { - DT = new llvm::DominatorTreeBase<CFGBlock>(false); - } - - ~DominatorTree() override { delete DT; } - - llvm::DominatorTreeBase<CFGBlock>& getBase() { return *DT; } - - /// \brief This method returns the root CFGBlock of the dominators tree. - /// - inline CFGBlock *getRoot() const { - return DT->getRoot(); - } - - /// \brief This method returns the root DomTreeNode, which is the wrapper - /// for CFGBlock. - inline DomTreeNode *getRootNode() const { - return DT->getRootNode(); - } - - /// \brief This method compares two dominator trees. - /// The method returns false if the other dominator tree matches this - /// dominator tree, otherwise returns true. - /// - inline bool compare(DominatorTree &Other) const { - DomTreeNode *R = getRootNode(); - DomTreeNode *OtherR = Other.getRootNode(); - - if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) - return true; - - if (DT->compare(Other.getBase())) - return true; - - return false; - } - - /// \brief This method builds the dominator tree for a given CFG - /// The CFG information is passed via AnalysisDeclContext - /// - void buildDominatorTree(AnalysisDeclContext &AC) { - cfg = AC.getCFG(); - DT->recalculate(*cfg); - } - - /// \brief This method dumps immediate dominators for each block, - /// mainly used for debug purposes. - /// - void dump() { - llvm::errs() << "Immediate dominance tree (Node#,IDom#):\n"; - for (CFG::const_iterator I = cfg->begin(), - E = cfg->end(); I != E; ++I) { - if(DT->getNode(*I)->getIDom()) - llvm::errs() << "(" << (*I)->getBlockID() - << "," - << DT->getNode(*I)->getIDom()->getBlock()->getBlockID() - << ")\n"; - else llvm::errs() << "(" << (*I)->getBlockID() - << "," << (*I)->getBlockID() << ")\n"; - } - } - - /// \brief This method tests if one CFGBlock dominates the other. - /// The method return true if A dominates B, false otherwise. - /// Note a block always dominates itself. - /// - inline bool dominates(const CFGBlock* A, const CFGBlock* B) const { - return DT->dominates(A, B); - } - - /// \brief This method tests if one CFGBlock properly dominates the other. - /// The method return true if A properly dominates B, false otherwise. - /// - bool properlyDominates(const CFGBlock*A, const CFGBlock*B) const { - return DT->properlyDominates(A, B); - } - - /// \brief This method finds the nearest common dominator CFG block - /// for CFG block A and B. If there is no such block then return NULL. - /// - inline CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { - return DT->findNearestCommonDominator(A, B); - } - - inline const CFGBlock *findNearestCommonDominator(const CFGBlock *A, - const CFGBlock *B) { - return DT->findNearestCommonDominator(A, B); - } - - /// \brief This method is used to update the dominator - /// tree information when a node's immediate dominator changes. - /// - inline void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { - DT->changeImmediateDominator(N, NewIDom); - } - - /// \brief This method tests if the given CFGBlock can be reachable from root. - /// Returns true if reachable, false otherwise. - /// - bool isReachableFromEntry(const CFGBlock *A) { - return DT->isReachableFromEntry(A); - } - - /// \brief This method releases the memory held by the dominator tree. - /// - virtual void releaseMemory() { - DT->releaseMemory(); - } - - /// \brief This method converts the dominator tree to human readable form. - /// - virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { - DT->print(OS); - } - -private: - CFG *cfg; -}; - -} // end namespace clang - -//===------------------------------------- -/// DominatorTree GraphTraits specialization so the DominatorTree can be -/// iterable by generic graph iterators. -/// -namespace llvm { -template <> struct GraphTraits< ::clang::DomTreeNode* > { - typedef ::clang::DomTreeNode NodeType; - typedef NodeType::iterator ChildIteratorType; - - static NodeType *getEntryNode(NodeType *N) { - return N; - } - static inline ChildIteratorType child_begin(NodeType *N) { - return N->begin(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->end(); - } - - typedef df_iterator< ::clang::DomTreeNode* > nodes_iterator; - - static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { - return df_begin(getEntryNode(N)); - } - - static nodes_iterator nodes_end(::clang::DomTreeNode *N) { - return df_end(getEntryNode(N)); - } -}; - -template <> struct GraphTraits< ::clang::DominatorTree* > - : public GraphTraits< ::clang::DomTreeNode* > { - static NodeType *getEntryNode(::clang::DominatorTree *DT) { - return DT->getRootNode(); - } - - static nodes_iterator nodes_begin(::clang::DominatorTree *N) { - return df_begin(getEntryNode(N)); - } - - static nodes_iterator nodes_end(::clang::DominatorTree *N) { - return df_end(getEntryNode(N)); - } -}; -} // end namespace llvm - -#endif diff --git a/include/clang/Analysis/Analyses/FormatString.h b/include/clang/Analysis/Analyses/FormatString.h deleted file mode 100644 index 4471311..0000000 --- a/include/clang/Analysis/Analyses/FormatString.h +++ /dev/null @@ -1,679 +0,0 @@ -//= FormatString.h - Analysis of printf/fprintf format strings --*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines APIs for analyzing the format strings of printf, fscanf, -// and friends. -// -// The structure of format strings for fprintf are described in C99 7.19.6.1. -// -// The structure of format strings for fscanf are described in C99 7.19.6.2. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_FORMATSTRING_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_FORMATSTRING_H - -#include "clang/AST/CanonicalType.h" - -namespace clang { - -class TargetInfo; - -//===----------------------------------------------------------------------===// -/// Common components of both fprintf and fscanf format strings. -namespace analyze_format_string { - -/// Class representing optional flags with location and representation -/// information. -class OptionalFlag { -public: - OptionalFlag(const char *Representation) - : representation(Representation), flag(false) {} - bool isSet() { return flag; } - void set() { flag = true; } - void clear() { flag = false; } - void setPosition(const char *position) { - assert(position); - flag = true; - this->position = position; - } - const char *getPosition() const { - assert(position); - return position; - } - const char *toString() const { return representation; } - - // Overloaded operators for bool like qualities - explicit operator bool() const { return flag; } - OptionalFlag& operator=(const bool &rhs) { - flag = rhs; - return *this; // Return a reference to myself. - } -private: - const char *representation; - const char *position; - bool flag; -}; - -/// Represents the length modifier in a format string in scanf/printf. -class LengthModifier { -public: - enum Kind { - None, - AsChar, // 'hh' - AsShort, // 'h' - AsLong, // 'l' - AsLongLong, // 'll' - AsQuad, // 'q' (BSD, deprecated, for 64-bit integer types) - AsIntMax, // 'j' - AsSizeT, // 'z' - AsPtrDiff, // 't' - AsInt32, // 'I32' (MSVCRT, like __int32) - AsInt3264, // 'I' (MSVCRT, like __int3264 from MIDL) - AsInt64, // 'I64' (MSVCRT, like __int64) - 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 - }; - - LengthModifier() - : Position(nullptr), kind(None) {} - LengthModifier(const char *pos, Kind k) - : Position(pos), kind(k) {} - - const char *getStart() const { - return Position; - } - - unsigned getLength() const { - switch (kind) { - default: - return 1; - case AsLongLong: - case AsChar: - return 2; - case AsInt32: - case AsInt64: - return 3; - case None: - return 0; - } - } - - Kind getKind() const { return kind; } - void setKind(Kind k) { kind = k; } - - const char *toString() const; - -private: - const char *Position; - Kind kind; -}; - -class ConversionSpecifier { -public: - enum Kind { - InvalidSpecifier = 0, - // C99 conversion specifiers. - cArg, - dArg, - DArg, // Apple extension - iArg, - IntArgBeg = dArg, IntArgEnd = iArg, - - oArg, - OArg, // Apple extension - uArg, - UArg, // Apple extension - xArg, - XArg, - UIntArgBeg = oArg, UIntArgEnd = XArg, - - fArg, - FArg, - eArg, - EArg, - gArg, - GArg, - aArg, - AArg, - DoubleArgBeg = fArg, DoubleArgEnd = AArg, - - sArg, - pArg, - nArg, - PercentArg, - CArg, - SArg, - - // ** Printf-specific ** - - ZArg, // MS extension - - // Objective-C specific specifiers. - ObjCObjArg, // '@' - ObjCBeg = ObjCObjArg, ObjCEnd = ObjCObjArg, - - // FreeBSD kernel specific specifiers. - FreeBSDbArg, - FreeBSDDArg, - FreeBSDrArg, - FreeBSDyArg, - - // GlibC specific specifiers. - PrintErrno, // 'm' - - PrintfConvBeg = ObjCObjArg, PrintfConvEnd = PrintErrno, - - // ** Scanf-specific ** - ScanListArg, // '[' - ScanfConvBeg = ScanListArg, ScanfConvEnd = ScanListArg - }; - - ConversionSpecifier(bool isPrintf = true) - : IsPrintf(isPrintf), Position(nullptr), EndScanList(nullptr), - kind(InvalidSpecifier) {} - - ConversionSpecifier(bool isPrintf, const char *pos, Kind k) - : IsPrintf(isPrintf), Position(pos), EndScanList(nullptr), kind(k) {} - - const char *getStart() const { - return Position; - } - - StringRef getCharacters() const { - return StringRef(getStart(), getLength()); - } - - bool consumesDataArgument() const { - switch (kind) { - case PrintErrno: - assert(IsPrintf); - return false; - case PercentArg: - return false; - default: - return true; - } - } - - Kind getKind() const { return kind; } - void setKind(Kind k) { kind = k; } - unsigned getLength() const { - return EndScanList ? EndScanList - Position : 1; - } - - bool isIntArg() const { return (kind >= IntArgBeg && kind <= IntArgEnd) || - kind == FreeBSDrArg || kind == FreeBSDyArg; } - bool isUIntArg() const { return kind >= UIntArgBeg && kind <= UIntArgEnd; } - bool isAnyIntArg() const { return kind >= IntArgBeg && kind <= UIntArgEnd; } - const char *toString() const; - - bool isPrintfKind() const { return IsPrintf; } - - Optional<ConversionSpecifier> getStandardSpecifier() const; - -protected: - bool IsPrintf; - const char *Position; - const char *EndScanList; - Kind kind; -}; - -class ArgType { -public: - enum Kind { UnknownTy, InvalidTy, SpecificTy, ObjCPointerTy, CPointerTy, - AnyCharTy, CStrTy, WCStrTy, WIntTy }; - - enum MatchKind { NoMatch = 0, Match = 1, NoMatchPedantic }; - -private: - const Kind K; - QualType T; - const char *Name; - bool Ptr; -public: - ArgType(Kind k = UnknownTy, const char *n = nullptr) - : K(k), Name(n), Ptr(false) {} - ArgType(QualType t, const char *n = nullptr) - : K(SpecificTy), T(t), Name(n), Ptr(false) {} - ArgType(CanQualType t) : K(SpecificTy), T(t), Name(nullptr), Ptr(false) {} - - static ArgType Invalid() { return ArgType(InvalidTy); } - bool isValid() const { return K != InvalidTy; } - - /// Create an ArgType which corresponds to the type pointer to A. - static ArgType PtrTo(const ArgType& A) { - assert(A.K >= InvalidTy && "ArgType cannot be pointer to invalid/unknown"); - ArgType Res = A; - Res.Ptr = true; - return Res; - } - - MatchKind matchesType(ASTContext &C, QualType argTy) const; - - QualType getRepresentativeType(ASTContext &C) const; - - std::string getRepresentativeTypeName(ASTContext &C) const; -}; - -class OptionalAmount { -public: - enum HowSpecified { NotSpecified, Constant, Arg, Invalid }; - - OptionalAmount(HowSpecified howSpecified, - unsigned amount, - const char *amountStart, - unsigned amountLength, - bool usesPositionalArg) - : start(amountStart), length(amountLength), hs(howSpecified), amt(amount), - UsesPositionalArg(usesPositionalArg), UsesDotPrefix(0) {} - - OptionalAmount(bool valid = true) - : start(nullptr),length(0), hs(valid ? NotSpecified : Invalid), amt(0), - UsesPositionalArg(0), UsesDotPrefix(0) {} - - bool isInvalid() const { - return hs == Invalid; - } - - HowSpecified getHowSpecified() const { return hs; } - void setHowSpecified(HowSpecified h) { hs = h; } - - bool hasDataArgument() const { return hs == Arg; } - - unsigned getArgIndex() const { - assert(hasDataArgument()); - return amt; - } - - unsigned getConstantAmount() const { - assert(hs == Constant); - return amt; - } - - const char *getStart() const { - // We include the . character if it is given. - return start - UsesDotPrefix; - } - - unsigned getConstantLength() const { - assert(hs == Constant); - return length + UsesDotPrefix; - } - - ArgType getArgType(ASTContext &Ctx) const; - - void toString(raw_ostream &os) const; - - bool usesPositionalArg() const { return (bool) UsesPositionalArg; } - unsigned getPositionalArgIndex() const { - assert(hasDataArgument()); - return amt + 1; - } - - bool usesDotPrefix() const { return UsesDotPrefix; } - void setUsesDotPrefix() { UsesDotPrefix = true; } - -private: - const char *start; - unsigned length; - HowSpecified hs; - unsigned amt; - bool UsesPositionalArg : 1; - bool UsesDotPrefix; -}; - - -class FormatSpecifier { -protected: - LengthModifier LM; - OptionalAmount FieldWidth; - ConversionSpecifier CS; - /// Positional arguments, an IEEE extension: - /// IEEE Std 1003.1, 2004 Edition - /// http://www.opengroup.org/onlinepubs/009695399/functions/printf.html - bool UsesPositionalArg; - unsigned argIndex; -public: - FormatSpecifier(bool isPrintf) - : CS(isPrintf), UsesPositionalArg(false), argIndex(0) {} - - void setLengthModifier(LengthModifier lm) { - LM = lm; - } - - void setUsesPositionalArg() { UsesPositionalArg = true; } - - void setArgIndex(unsigned i) { - argIndex = i; - } - - unsigned getArgIndex() const { - return argIndex; - } - - unsigned getPositionalArgIndex() const { - return argIndex + 1; - } - - const LengthModifier &getLengthModifier() const { - return LM; - } - - const OptionalAmount &getFieldWidth() const { - return FieldWidth; - } - - void setFieldWidth(const OptionalAmount &Amt) { - FieldWidth = Amt; - } - - bool usesPositionalArg() const { return UsesPositionalArg; } - - bool hasValidLengthModifier(const TargetInfo &Target) const; - - bool hasStandardLengthModifier() const; - - Optional<LengthModifier> getCorrectedLengthModifier() const; - - bool hasStandardConversionSpecifier(const LangOptions &LangOpt) const; - - bool hasStandardLengthConversionCombination() const; - - /// For a TypedefType QT, if it is a named integer type such as size_t, - /// assign the appropriate value to LM and return true. - static bool namedTypeToLengthModifier(QualType QT, LengthModifier &LM); -}; - -} // end analyze_format_string namespace - -//===----------------------------------------------------------------------===// -/// Pieces specific to fprintf format strings. - -namespace analyze_printf { - -class PrintfConversionSpecifier : - public analyze_format_string::ConversionSpecifier { -public: - PrintfConversionSpecifier() - : ConversionSpecifier(true, nullptr, InvalidSpecifier) {} - - PrintfConversionSpecifier(const char *pos, Kind k) - : ConversionSpecifier(true, pos, k) {} - - bool isObjCArg() const { return kind >= ObjCBeg && kind <= ObjCEnd; } - bool isDoubleArg() const { return kind >= DoubleArgBeg && - kind <= DoubleArgEnd; } - unsigned getLength() const { - // Conversion specifiers currently only are represented by - // single characters, but we be flexible. - return 1; - } - - static bool classof(const analyze_format_string::ConversionSpecifier *CS) { - return CS->isPrintfKind(); - } -}; - -using analyze_format_string::ArgType; -using analyze_format_string::LengthModifier; -using analyze_format_string::OptionalAmount; -using analyze_format_string::OptionalFlag; - -class PrintfSpecifier : public analyze_format_string::FormatSpecifier { - OptionalFlag HasThousandsGrouping; // ''', POSIX extension. - OptionalFlag IsLeftJustified; // '-' - OptionalFlag HasPlusPrefix; // '+' - OptionalFlag HasSpacePrefix; // ' ' - OptionalFlag HasAlternativeForm; // '#' - OptionalFlag HasLeadingZeroes; // '0' - OptionalFlag HasObjCTechnicalTerm; // '[tt]' - OptionalAmount Precision; -public: - PrintfSpecifier() : - FormatSpecifier(/* isPrintf = */ true), - HasThousandsGrouping("'"), IsLeftJustified("-"), HasPlusPrefix("+"), - HasSpacePrefix(" "), HasAlternativeForm("#"), HasLeadingZeroes("0"), - HasObjCTechnicalTerm("tt") {} - - static PrintfSpecifier Parse(const char *beg, const char *end); - - // Methods for incrementally constructing the PrintfSpecifier. - void setConversionSpecifier(const PrintfConversionSpecifier &cs) { - CS = cs; - } - void setHasThousandsGrouping(const char *position) { - HasThousandsGrouping.setPosition(position); - } - void setIsLeftJustified(const char *position) { - IsLeftJustified.setPosition(position); - } - void setHasPlusPrefix(const char *position) { - HasPlusPrefix.setPosition(position); - } - void setHasSpacePrefix(const char *position) { - HasSpacePrefix.setPosition(position); - } - void setHasAlternativeForm(const char *position) { - HasAlternativeForm.setPosition(position); - } - void setHasLeadingZeros(const char *position) { - HasLeadingZeroes.setPosition(position); - } - void setHasObjCTechnicalTerm(const char *position) { - HasObjCTechnicalTerm.setPosition(position); - } - void setUsesPositionalArg() { UsesPositionalArg = true; } - - // Methods for querying the format specifier. - - const PrintfConversionSpecifier &getConversionSpecifier() const { - return cast<PrintfConversionSpecifier>(CS); - } - - void setPrecision(const OptionalAmount &Amt) { - Precision = Amt; - Precision.setUsesDotPrefix(); - } - - const OptionalAmount &getPrecision() const { - return Precision; - } - - bool consumesDataArgument() const { - return getConversionSpecifier().consumesDataArgument(); - } - - /// \brief Returns the builtin type that a data argument - /// paired with this format specifier should have. This method - /// will return null if the format specifier does not have - /// a matching data argument or the matching argument matches - /// more than one type. - ArgType getArgType(ASTContext &Ctx, bool IsObjCLiteral) const; - - const OptionalFlag &hasThousandsGrouping() const { - return HasThousandsGrouping; - } - const OptionalFlag &isLeftJustified() const { return IsLeftJustified; } - const OptionalFlag &hasPlusPrefix() const { return HasPlusPrefix; } - const OptionalFlag &hasAlternativeForm() const { return HasAlternativeForm; } - const OptionalFlag &hasLeadingZeros() const { return HasLeadingZeroes; } - const OptionalFlag &hasSpacePrefix() const { return HasSpacePrefix; } - const OptionalFlag &hasObjCTechnicalTerm() const { return HasObjCTechnicalTerm; } - bool usesPositionalArg() const { return UsesPositionalArg; } - - /// Changes the specifier and length according to a QualType, retaining any - /// flags or options. Returns true on success, or false when a conversion - /// was not successful. - bool fixType(QualType QT, const LangOptions &LangOpt, ASTContext &Ctx, - bool IsObjCLiteral); - - void toString(raw_ostream &os) const; - - // Validation methods - to check if any element results in undefined behavior - bool hasValidPlusPrefix() const; - bool hasValidAlternativeForm() const; - bool hasValidLeadingZeros() const; - bool hasValidSpacePrefix() const; - bool hasValidLeftJustified() const; - bool hasValidThousandsGroupingPrefix() const; - - bool hasValidPrecision() const; - bool hasValidFieldWidth() const; -}; -} // end analyze_printf namespace - -//===----------------------------------------------------------------------===// -/// Pieces specific to fscanf format strings. - -namespace analyze_scanf { - -class ScanfConversionSpecifier : - public analyze_format_string::ConversionSpecifier { -public: - ScanfConversionSpecifier() - : ConversionSpecifier(false, nullptr, InvalidSpecifier) {} - - ScanfConversionSpecifier(const char *pos, Kind k) - : ConversionSpecifier(false, pos, k) {} - - void setEndScanList(const char *pos) { EndScanList = pos; } - - static bool classof(const analyze_format_string::ConversionSpecifier *CS) { - return !CS->isPrintfKind(); - } -}; - -using analyze_format_string::ArgType; -using analyze_format_string::LengthModifier; -using analyze_format_string::OptionalAmount; -using analyze_format_string::OptionalFlag; - -class ScanfSpecifier : public analyze_format_string::FormatSpecifier { - OptionalFlag SuppressAssignment; // '*' -public: - ScanfSpecifier() : - FormatSpecifier(/* isPrintf = */ false), - SuppressAssignment("*") {} - - void setSuppressAssignment(const char *position) { - SuppressAssignment.setPosition(position); - } - - const OptionalFlag &getSuppressAssignment() const { - return SuppressAssignment; - } - - void setConversionSpecifier(const ScanfConversionSpecifier &cs) { - CS = cs; - } - - const ScanfConversionSpecifier &getConversionSpecifier() const { - return cast<ScanfConversionSpecifier>(CS); - } - - bool consumesDataArgument() const { - return CS.consumesDataArgument() && !SuppressAssignment; - } - - ArgType getArgType(ASTContext &Ctx) const; - - bool fixType(QualType QT, QualType RawQT, const LangOptions &LangOpt, - ASTContext &Ctx); - - void toString(raw_ostream &os) const; - - static ScanfSpecifier Parse(const char *beg, const char *end); -}; - -} // end analyze_scanf namespace - -//===----------------------------------------------------------------------===// -// Parsing and processing of format strings (both fprintf and fscanf). - -namespace analyze_format_string { - -enum PositionContext { FieldWidthPos = 0, PrecisionPos = 1 }; - -class FormatStringHandler { -public: - FormatStringHandler() {} - virtual ~FormatStringHandler(); - - virtual void HandleNullChar(const char *nullCharacter) {} - - virtual void HandlePosition(const char *startPos, unsigned posLen) {} - - virtual void HandleInvalidPosition(const char *startPos, unsigned posLen, - PositionContext p) {} - - virtual void HandleZeroPosition(const char *startPos, unsigned posLen) {} - - virtual void HandleIncompleteSpecifier(const char *startSpecifier, - unsigned specifierLen) {} - - virtual void HandleEmptyObjCModifierFlag(const char *startFlags, - unsigned flagsLen) {} - - virtual void HandleInvalidObjCModifierFlag(const char *startFlag, - unsigned flagLen) {} - - virtual void HandleObjCFlagsWithNonObjCConversion(const char *flagsStart, - const char *flagsEnd, - const char *conversionPosition) {} - // Printf-specific handlers. - - virtual bool HandleInvalidPrintfConversionSpecifier( - const analyze_printf::PrintfSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { - return true; - } - - virtual bool HandlePrintfSpecifier(const analyze_printf::PrintfSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { - return true; - } - - // Scanf-specific handlers. - - virtual bool HandleInvalidScanfConversionSpecifier( - const analyze_scanf::ScanfSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { - return true; - } - - virtual bool HandleScanfSpecifier(const analyze_scanf::ScanfSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { - return true; - } - - virtual void HandleIncompleteScanList(const char *start, const char *end) {} -}; - -bool ParsePrintfString(FormatStringHandler &H, - const char *beg, const char *end, const LangOptions &LO, - const TargetInfo &Target, bool isFreeBSDKPrintf); - -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, - const TargetInfo &Target); - -} // end analyze_format_string namespace -} // end clang namespace -#endif diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h deleted file mode 100644 index e17f73a6..0000000 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ /dev/null @@ -1,117 +0,0 @@ -//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements Live Variables analysis for source-level CFGs. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_LIVEVARIABLES_H - -#include "clang/AST/Decl.h" -#include "clang/Analysis/AnalysisContext.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/ImmutableSet.h" - -namespace clang { - -class CFG; -class CFGBlock; -class Stmt; -class DeclRefExpr; -class SourceManager; - -class LiveVariables : public ManagedAnalysis { -public: - class LivenessValues { - public: - - llvm::ImmutableSet<const Stmt *> liveStmts; - llvm::ImmutableSet<const VarDecl *> liveDecls; - - bool equals(const LivenessValues &V) const; - - LivenessValues() - : liveStmts(nullptr), liveDecls(nullptr) {} - - LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts, - llvm::ImmutableSet<const VarDecl *> LiveDecls) - : liveStmts(LiveStmts), liveDecls(LiveDecls) {} - - bool isLive(const Stmt *S) const; - bool isLive(const VarDecl *D) const; - - friend class LiveVariables; - }; - - class Observer { - virtual void anchor(); - public: - virtual ~Observer() {} - - /// A callback invoked right before invoking the - /// liveness transfer function on the given statement. - virtual void observeStmt(const Stmt *S, - const CFGBlock *currentBlock, - const LivenessValues& V) {} - - /// Called when the live variables analysis registers - /// that a variable is killed. - virtual void observerKill(const DeclRefExpr *DR) {} - }; - - ~LiveVariables() override; - - /// Compute the liveness information for a given CFG. - static LiveVariables *computeLiveness(AnalysisDeclContext &analysisContext, - bool killAtAssign); - - /// Return true if a variable is live at the end of a - /// specified block. - bool isLive(const CFGBlock *B, const VarDecl *D); - - /// Returns true if a variable is live at the beginning of the - /// the statement. This query only works if liveness information - /// has been recorded at the statement level (see runOnAllBlocks), and - /// only returns liveness information for block-level expressions. - bool isLive(const Stmt *S, const VarDecl *D); - - /// Returns true the block-level expression "value" is live - /// before the given block-level expression (see runOnAllBlocks). - bool isLive(const Stmt *Loc, const Stmt *StmtVal); - - /// Print to stderr the liveness information associated with - /// each basic block. - void dumpBlockLiveness(const SourceManager& M); - - void runOnAllBlocks(Observer &obs); - - static LiveVariables *create(AnalysisDeclContext &analysisContext) { - return computeLiveness(analysisContext, true); - } - - static const void *getTag(); - -private: - LiveVariables(void *impl); - void *impl; -}; - -class RelaxedLiveVariables : public LiveVariables { -public: - static LiveVariables *create(AnalysisDeclContext &analysisContext) { - return computeLiveness(analysisContext, false); - } - - static const void *getTag(); -}; - -} // end namespace clang - -#endif diff --git a/include/clang/Analysis/Analyses/PostOrderCFGView.h b/include/clang/Analysis/Analyses/PostOrderCFGView.h deleted file mode 100644 index a1c6504..0000000 --- a/include/clang/Analysis/Analyses/PostOrderCFGView.h +++ /dev/null @@ -1,115 +0,0 @@ -//===- PostOrderCFGView.h - Post order view of CFG blocks ---------*- C++ --*-// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements post order view of the blocks in a CFG. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_POSTORDERCFGVIEW_H - -#include <vector> -//#include <algorithm> - -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/BitVector.h" - -#include "clang/Analysis/AnalysisContext.h" -#include "clang/Analysis/CFG.h" - -namespace clang { - -class PostOrderCFGView : public ManagedAnalysis { - virtual void anchor(); -public: - /// \brief Implements a set of CFGBlocks using a BitVector. - /// - /// This class contains a minimal interface, primarily dictated by the SetType - /// template parameter of the llvm::po_iterator template, as used with - /// external storage. We also use this set to keep track of which CFGBlocks we - /// visit during the analysis. - class CFGBlockSet { - llvm::BitVector VisitedBlockIDs; - public: - // po_iterator requires this iterator, but the only interface needed is the - // value_type typedef. - struct iterator { typedef const CFGBlock *value_type; }; - - CFGBlockSet() {} - CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} - - /// \brief Set the bit associated with a particular CFGBlock. - /// This is the important method for the SetType template parameter. - 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 std::make_pair(None, false); // if an edge is trivially false. - if (VisitedBlockIDs.test(Block->getBlockID())) - return std::make_pair(None, false); - VisitedBlockIDs.set(Block->getBlockID()); - return std::make_pair(None, true); - } - - /// \brief Check if the bit for a CFGBlock has been already set. - /// This method is for tracking visited blocks in the main threadsafety - /// loop. Block must not be null. - bool alreadySet(const CFGBlock *Block) { - return VisitedBlockIDs.test(Block->getBlockID()); - } - }; - -private: - typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; - std::vector<const CFGBlock*> Blocks; - - typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy; - BlockOrderTy BlockOrder; - -public: - typedef std::vector<const CFGBlock *>::reverse_iterator iterator; - typedef std::vector<const CFGBlock *>::const_reverse_iterator const_iterator; - - PostOrderCFGView(const CFG *cfg); - - iterator begin() { return Blocks.rbegin(); } - iterator end() { return Blocks.rend(); } - - const_iterator begin() const { return Blocks.rbegin(); } - const_iterator end() const { return Blocks.rend(); } - - bool empty() const { return begin() == end(); } - - struct BlockOrderCompare; - friend struct BlockOrderCompare; - - struct BlockOrderCompare { - const PostOrderCFGView &POV; - public: - BlockOrderCompare(const PostOrderCFGView &pov) : POV(pov) {} - bool operator()(const CFGBlock *b1, const CFGBlock *b2) const; - }; - - BlockOrderCompare getComparator() const { - return BlockOrderCompare(*this); - } - - // Used by AnalyisContext to construct this object. - static const void *getTag(); - - static PostOrderCFGView *create(AnalysisDeclContext &analysisContext); -}; - -} // end clang namespace - -#endif - diff --git a/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h b/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h deleted file mode 100644 index c4ec2f2..0000000 --- a/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h +++ /dev/null @@ -1,45 +0,0 @@ -//== PseudoConstantAnalysis.h - Find Pseudo-constants in the AST -*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file tracks the usage of variables in a Decl body to see if they are -// never written to, implying that they constant. This is useful in static -// analysis to see if a developer might have intended a variable to be const. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_PSEUDOCONSTANTANALYSIS_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_PSEUDOCONSTANTANALYSIS_H - -#include "clang/AST/Stmt.h" - -namespace clang { - -class PseudoConstantAnalysis { -public: - PseudoConstantAnalysis(const Stmt *DeclBody); - ~PseudoConstantAnalysis(); - - bool isPseudoConstant(const VarDecl *VD); - bool wasReferenced(const VarDecl *VD); - -private: - void RunAnalysis(); - inline static const Decl *getDecl(const Expr *E); - - // for storing the result of analyzed ValueDecls - void *NonConstantsImpl; - void *UsedVarsImpl; - - const Stmt *DeclBody; - bool Analyzed; -}; - -} - -#endif diff --git a/include/clang/Analysis/Analyses/ReachableCode.h b/include/clang/Analysis/Analyses/ReachableCode.h deleted file mode 100644 index 4c523bf..0000000 --- a/include/clang/Analysis/Analyses/ReachableCode.h +++ /dev/null @@ -1,69 +0,0 @@ -//===- ReachableCode.h -----------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// A flow-sensitive, path-insensitive analysis of unreachable code. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_REACHABLECODE_H - -#include "clang/Basic/SourceLocation.h" - -//===----------------------------------------------------------------------===// -// Forward declarations. -//===----------------------------------------------------------------------===// - -namespace llvm { - class BitVector; -} - -namespace clang { - class AnalysisDeclContext; - class CFGBlock; - class Preprocessor; -} - -//===----------------------------------------------------------------------===// -// API. -//===----------------------------------------------------------------------===// - -namespace clang { -namespace reachable_code { - -/// Classifications of unreachable code. -enum UnreachableKind { - UK_Return, - UK_Break, - UK_Loop_Increment, - UK_Other -}; - -class Callback { - virtual void anchor(); -public: - virtual ~Callback() {} - virtual void HandleUnreachable(UnreachableKind UK, - SourceLocation L, - SourceRange ConditionVal, - SourceRange R1, - SourceRange R2) = 0; -}; - -/// ScanReachableFromBlock - Mark all blocks reachable from Start. -/// Returns the total number of blocks that were marked reachable. -unsigned ScanReachableFromBlock(const CFGBlock *Start, - llvm::BitVector &Reachable); - -void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, - Callback &CB); - -}} // end namespace clang::reachable_code - -#endif diff --git a/include/clang/Analysis/Analyses/ThreadSafety.h b/include/clang/Analysis/Analyses/ThreadSafety.h deleted file mode 100644 index 22694a7..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafety.h +++ /dev/null @@ -1,226 +0,0 @@ -//===- ThreadSafety.h ------------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// -// A intra-procedural analysis for thread safety (e.g. deadlocks and race -// conditions), based off of an annotation system. -// -// See http://clang.llvm.org/docs/LanguageExtensions.html#thread-safety-annotation-checking -// for more information. -// -//===----------------------------------------------------------------------===// - -#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 threadSafety { - -class BeforeSet; - -/// 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_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_Exclusive, ///< Exclusive/writer lock of a mutex. - LK_Generic ///< Can be either Shared or Exclusive -}; - -/// This enum distinguishes between different ways to access (read or write) a -/// variable. -enum AccessKind { - AK_Read, ///< Reading a variable. - AK_Written ///< Writing a variable. -}; - -/// This enum distinguishes between different situations where we warn due to -/// inconsistent locking. -/// \enum SK_LockedSomeLoopIterations -- a mutex is locked for some but not all -/// loop iterations. -/// \enum SK_LockedSomePredecessors -- a mutex is locked in some but not all -/// predecessors of a CFGBlock. -/// \enum SK_LockedAtEndOfFunction -- a mutex is still locked at the end of a -/// function. -enum LockErrorKind { - LEK_LockedSomeLoopIterations, - LEK_LockedSomePredecessors, - LEK_LockedAtEndOfFunction, - LEK_NotLockedAtEndOfFunction -}; - -/// Handler class for thread safety warnings. -class ThreadSafetyHandler { -public: - typedef StringRef Name; - ThreadSafetyHandler() : IssueBetaWarnings(false) { } - virtual ~ThreadSafetyHandler(); - - /// Warn about lock expressions which fail to resolve to lockable objects. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param Loc -- the SourceLocation of the unresolved expression. - virtual void handleInvalidLockExp(StringRef Kind, SourceLocation Loc) {} - - /// Warn about unlock function calls that do not have a prior matching lock - /// expression. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param Loc -- The SourceLocation of the Unlock - virtual void handleUnmatchedUnlock(StringRef Kind, Name LockName, - SourceLocation Loc) {} - - /// Warn about an unlock function call that attempts to unlock a lock with - /// the incorrect lock kind. For instance, a shared lock being unlocked - /// exclusively, or vice versa. - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param Expected -- the kind of lock expected. - /// \param Received -- the kind of lock received. - /// \param Loc -- The SourceLocation of the Unlock. - virtual void handleIncorrectUnlockKind(StringRef Kind, Name LockName, - LockKind Expected, LockKind Received, - SourceLocation Loc) {} - - /// Warn about lock function calls for locks which are already held. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param Loc -- The location of the second lock expression. - virtual void handleDoubleLock(StringRef Kind, Name LockName, - SourceLocation Loc) {} - - /// Warn about situations where a mutex is sometimes held and sometimes not. - /// The three situations are: - /// 1. a mutex is locked on an "if" branch but not the "else" branch, - /// 2, or a mutex is only held at the start of some loop iterations, - /// 3. or when a mutex is locked but not unlocked inside a function. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param LocLocked -- The location of the lock expression where the mutex is - /// locked - /// \param LocEndOfScope -- The location of the end of the scope where the - /// mutex is no longer held - /// \param LEK -- which of the three above cases we should warn for - virtual void handleMutexHeldEndOfScope(StringRef Kind, Name LockName, - SourceLocation LocLocked, - SourceLocation LocEndOfScope, - LockErrorKind LEK) {} - - /// Warn when a mutex is held exclusively and shared at the same point. For - /// example, if a mutex is locked exclusively during an if branch and shared - /// during the else branch. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param Loc1 -- The location of the first lock expression. - /// \param Loc2 -- The location of the second lock expression. - virtual void handleExclusiveAndShared(StringRef Kind, Name LockName, - SourceLocation Loc1, - SourceLocation Loc2) {} - - /// Warn when a protected operation occurs while no locks are held. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param D -- The decl for the protected variable or function - /// \param POK -- The kind of protected operation (e.g. variable access) - /// \param AK -- The kind of access (i.e. read or write) that occurred - /// \param Loc -- The location of the protected operation. - virtual void handleNoMutexHeld(StringRef Kind, const NamedDecl *D, - ProtectedOperationKind POK, AccessKind AK, - SourceLocation Loc) {} - - /// Warn when a protected operation occurs while the specific mutex protecting - /// the operation is not locked. - /// \param Kind -- the capability's name parameter (role, mutex, etc). - /// \param D -- The decl for the protected variable or function - /// \param POK -- The kind of protected operation (e.g. variable access) - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param LK -- The kind of access (i.e. read or write) that occurred - /// \param Loc -- The location of the protected operation. - virtual void handleMutexNotHeld(StringRef Kind, const NamedDecl *D, - ProtectedOperationKind POK, Name LockName, - 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). - /// \param FunName -- The name of the function - /// \param LockName -- A StringRef name for the lock expression, to be printed - /// in the error message. - /// \param Loc -- The location of the function call. - virtual void handleFunExcludesLock(StringRef Kind, Name FunName, - Name LockName, SourceLocation Loc) {} - - - /// Warn that L1 cannot be acquired before L2. - virtual void handleLockAcquiredBefore(StringRef Kind, Name L1Name, - Name L2Name, SourceLocation Loc) {} - - /// Warn that there is a cycle in acquired_before/after dependencies. - virtual void handleBeforeAfterCycle(Name L1Name, 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; } - -private: - bool IssueBetaWarnings; -}; - -/// \brief Check a function's CFG for thread-safety violations. -/// -/// We traverse the blocks in the CFG, compute the set of mutexes that are held -/// at the end of each block, and issue warnings for thread safety violations. -/// Each block in the CFG is traversed exactly once. -void runThreadSafetyAnalysis(AnalysisDeclContext &AC, - ThreadSafetyHandler &Handler, - BeforeSet **Bset); - -void threadSafetyCleanup(BeforeSet *Cache); - -/// \brief Helper function that returns a LockKind required for the given level -/// of access. -LockKind getLockKindFromAccessKind(AccessKind AK); - -}} // end namespace clang::threadSafety -#endif diff --git a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/include/clang/Analysis/Analyses/ThreadSafetyCommon.h deleted file mode 100644 index e357013..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ /dev/null @@ -1,505 +0,0 @@ -//===- ThreadSafetyCommon.h ------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Parts of thread safety analysis that are not specific to thread safety -// itself have been factored into classes here, where they can be potentially -// used by other analyses. Currently these include: -// -// * Generalize clang CFG visitors. -// * Conversion of the clang CFG to SSA form. -// * Translation of clang Exprs to TIL SExprs -// -// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. -// -//===----------------------------------------------------------------------===// - -#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. -class CFGVisitor { - // Enter the CFG for Decl D, and perform any initial setup operations. - void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} - - // Enter a CFGBlock. - void enterCFGBlock(const CFGBlock *B) {} - - // Returns true if this visitor implements handlePredecessor - bool visitPredecessors() { return true; } - - // Process a predecessor edge. - void handlePredecessor(const CFGBlock *Pred) {} - - // Process a successor back edge to a previously visited block. - void handlePredecessorBackEdge(const CFGBlock *Pred) {} - - // Called just before processing statements. - void enterCFGBlockBody(const CFGBlock *B) {} - - // Process an ordinary statement. - void handleStatement(const Stmt *S) {} - - // Process a destructor call - void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} - - // Called after all statements have been handled. - void exitCFGBlockBody(const CFGBlock *B) {} - - // Return true - bool visitSuccessors() { return true; } - - // Process a successor edge. - void handleSuccessor(const CFGBlock *Succ) {} - - // Process a successor back edge to a previously visited block. - void handleSuccessorBackEdge(const CFGBlock *Succ) {} - - // Leave a CFGBlock. - void exitCFGBlock(const CFGBlock *B) {} - - // Leave the CFG, and perform any final cleanup operations. - void exitCFG(const CFGBlock *Last) {} -}; - - -// Walks the clang CFG, and invokes methods on a given CFGVisitor. -class CFGWalker { -public: - CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {} - - // Initialize the CFGWalker. This setup only needs to be done once, even - // if there are multiple passes over the CFG. - bool init(AnalysisDeclContext &AC) { - ACtx = &AC; - CFGraph = AC.getCFG(); - if (!CFGraph) - return false; - - // Ignore anonymous functions. - if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) - return false; - - SortedGraph = AC.getAnalysis<PostOrderCFGView>(); - if (!SortedGraph) - return false; - - return true; - } - - // Traverse the CFG, calling methods on V as appropriate. - template <class Visitor> - void walk(Visitor &V) { - PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); - - V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); - - for (const auto *CurrBlock : *SortedGraph) { - VisitedBlocks.insert(CurrBlock); - - V.enterCFGBlock(CurrBlock); - - // Process predecessors, handling back edges last - if (V.visitPredecessors()) { - SmallVector<CFGBlock*, 4> BackEdges; - // Process successors - for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), - SE = CurrBlock->pred_end(); - SI != SE; ++SI) { - if (*SI == nullptr) - continue; - - if (!VisitedBlocks.alreadySet(*SI)) { - BackEdges.push_back(*SI); - continue; - } - V.handlePredecessor(*SI); - } - - for (auto *Blk : BackEdges) - V.handlePredecessorBackEdge(Blk); - } - - V.enterCFGBlockBody(CurrBlock); - - // Process statements - for (const auto &BI : *CurrBlock) { - switch (BI.getKind()) { - case CFGElement::Statement: { - V.handleStatement(BI.castAs<CFGStmt>().getStmt()); - break; - } - case CFGElement::AutomaticObjectDtor: { - CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); - CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( - AD.getDestructorDecl(ACtx->getASTContext())); - VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); - V.handleDestructorCall(VD, DD); - break; - } - default: - break; - } - } - - V.exitCFGBlockBody(CurrBlock); - - // Process successors, handling back edges first. - if (V.visitSuccessors()) { - SmallVector<CFGBlock*, 8> ForwardEdges; - - // Process successors - for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), - SE = CurrBlock->succ_end(); - SI != SE; ++SI) { - if (*SI == nullptr) - continue; - - if (!VisitedBlocks.alreadySet(*SI)) { - ForwardEdges.push_back(*SI); - continue; - } - V.handleSuccessorBackEdge(*SI); - } - - for (auto *Blk : ForwardEdges) - V.handleSuccessor(Blk); - } - - V.exitCFGBlock(CurrBlock); - } - V.exitCFG(&CFGraph->getExit()); - } - - const CFG *getGraph() const { return CFGraph; } - CFG *getGraph() { return CFGraph; } - - const NamedDecl *getDecl() const { - return dyn_cast<NamedDecl>(ACtx->getDecl()); - } - - const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } - -private: - CFG *CFGraph; - AnalysisDeclContext *ACtx; - PostOrderCFGView *SortedGraph; -}; - - - - -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); - } - - const ValueDecl* valueDecl() const { - if (Negated || CapExpr == nullptr) - return nullptr; - if (auto *P = dyn_cast<til::Project>(CapExpr)) - return P->clangDecl(); - if (auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) - return P->clangDecl(); - return nullptr; - } - - 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: - /// \brief Encapsulates the lexical context of a function call. The lexical - /// context includes the arguments to the call, including the implicit object - /// argument. When an attribute containing a mutex expression is attached to - /// a method, the expression may refer to formal parameters of the method. - /// Actual arguments must be substituted for formal parameters to derive - /// the appropriate mutex expression in the lexical context where the function - /// is called. PrevCtx holds the context in which the arguments themselves - /// should be evaluated; multiple calling contexts can be chained together - /// by the lock_returned attribute. - struct CallingContext { - 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 - bool SelfArrow; // is Self referred to with -> or .? - - CallingContext(CallingContext *P, const NamedDecl *D = nullptr) - : Prev(P), AttrDecl(D), SelfArg(nullptr), - NumArgs(0), FunArgs(nullptr), SelfArrow(false) - {} - }; - - SExprBuilder(til::MemRegionRef A) - : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), - CurrentBlockInfo(nullptr) { - // FIXME: we don't always have a self-variable. - SelfVar = new (Arena) til::Variable(nullptr); - 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. - til::SExpr *translate(const Stmt *S, CallingContext *Ctx); - til::SCFG *buildCFG(CFGWalker &Walker); - - til::SExpr *lookupStmt(const Stmt *S); - - til::BasicBlock *lookupBlock(const CFGBlock *B) { - return BlockMap[B->getBlockID()]; - } - - const til::SCFG *getCFG() const { return Scfg; } - til::SCFG *getCFG() { return Scfg; } - -private: - til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, - CallingContext *Ctx) ; - til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); - til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); - til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, - const Expr *SelfE = nullptr); - til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, - CallingContext *Ctx); - til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, - CallingContext *Ctx); - til::SExpr *translateUnaryOperator(const UnaryOperator *UO, - CallingContext *Ctx); - til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, - const BinaryOperator *BO, - CallingContext *Ctx, bool Reverse = false); - til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, - const BinaryOperator *BO, - CallingContext *Ctx, bool Assign = false); - til::SExpr *translateBinaryOperator(const BinaryOperator *BO, - CallingContext *Ctx); - til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); - til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, - CallingContext *Ctx); - til::SExpr *translateAbstractConditionalOperator( - const AbstractConditionalOperator *C, CallingContext *Ctx); - - til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); - - // Map from statements in the clang CFG to SExprs in the til::SCFG. - typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; - - // Map from clang local variables to indices in a LVarDefinitionMap. - typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; - - // Map from local variable indices to SSA variables (or constants). - typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; - typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; - - struct BlockInfo { - LVarDefinitionMap ExitMap; - bool HasBackEdges; - unsigned UnprocessedSuccessors; // Successors yet to be processed - unsigned ProcessedPredecessors; // Predecessors already processed - - BlockInfo() - : HasBackEdges(false), UnprocessedSuccessors(0), - ProcessedPredecessors(0) {} - BlockInfo(BlockInfo &&RHS) - : ExitMap(std::move(RHS.ExitMap)), - HasBackEdges(RHS.HasBackEdges), - UnprocessedSuccessors(RHS.UnprocessedSuccessors), - ProcessedPredecessors(RHS.ProcessedPredecessors) {} - - BlockInfo &operator=(BlockInfo &&RHS) { - if (this != &RHS) { - ExitMap = std::move(RHS.ExitMap); - HasBackEdges = RHS.HasBackEdges; - UnprocessedSuccessors = RHS.UnprocessedSuccessors; - ProcessedPredecessors = RHS.ProcessedPredecessors; - } - return *this; - } - - private: - BlockInfo(const BlockInfo &) = delete; - void operator=(const BlockInfo &) = delete; - }; - - // We implement the CFGVisitor API - friend class CFGWalker; - - void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); - void enterCFGBlock(const CFGBlock *B); - bool visitPredecessors() { return true; } - void handlePredecessor(const CFGBlock *Pred); - void handlePredecessorBackEdge(const CFGBlock *Pred); - void enterCFGBlockBody(const CFGBlock *B); - void handleStatement(const Stmt *S); - void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); - void exitCFGBlockBody(const CFGBlock *B); - bool visitSuccessors() { return true; } - void handleSuccessor(const CFGBlock *Succ); - void handleSuccessorBackEdge(const CFGBlock *Succ); - void exitCFGBlock(const CFGBlock *B); - void exitCFG(const CFGBlock *Last); - - void insertStmt(const Stmt *S, til::SExpr *E) { - SMap.insert(std::make_pair(S, E)); - } - til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); - - til::SExpr *addStatement(til::SExpr *E, const Stmt *S, - const ValueDecl *VD = nullptr); - til::SExpr *lookupVarDecl(const ValueDecl *VD); - til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); - til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); - - void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); - void mergeEntryMap(LVarDefinitionMap Map); - void mergeEntryMapBackEdge(); - 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; - 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. - - LVarDefinitionMap CurrentLVarMap; - std::vector<til::Phi*> CurrentArguments; - std::vector<til::SExpr*> CurrentInstructions; - std::vector<til::Phi*> IncompleteArgs; - til::BasicBlock *CurrentBB; - BlockInfo *CurrentBlockInfo; -}; - - -// Dump an SCFG to llvm::errs(). -void printSCFG(CFGWalker &Walker); - - -} // end namespace threadSafety - -} // end namespace clang - -#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h b/include/clang/Analysis/Analyses/ThreadSafetyLogical.h deleted file mode 100644 index bc78021..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyLogical.h +++ /dev/null @@ -1,108 +0,0 @@ -//===- ThreadSafetyLogical.h -----------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// This file defines a representation for logical expressions with SExpr leaves -// that are used as part of fact-checking capability expressions. -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYLOGICAL_H - -#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" - -namespace clang { -namespace threadSafety { -namespace lexpr { - -class LExpr { -public: - enum Opcode { - Terminal, - And, - Or, - Not - }; - Opcode kind() const { return Kind; } - - /// \brief Logical implication. Returns true if the LExpr implies RHS, i.e. if - /// the LExpr holds, then RHS must hold. For example, (A & B) implies A. - inline bool implies(const LExpr *RHS) const; - -protected: - LExpr(Opcode Kind) : Kind(Kind) {} - -private: - Opcode Kind; -}; - -class Terminal : public LExpr { - til::SExpr *Expr; - -public: - Terminal(til::SExpr *Expr) : LExpr(LExpr::Terminal), Expr(Expr) {} - - const til::SExpr *expr() const { return Expr; } - til::SExpr *expr() { return Expr; } - - static bool classof(const LExpr *E) { return E->kind() == LExpr::Terminal; } -}; - -class BinOp : public LExpr { - LExpr *LHS, *RHS; - -protected: - BinOp(LExpr *LHS, LExpr *RHS, Opcode Code) : LExpr(Code), LHS(LHS), RHS(RHS) {} - -public: - const LExpr *left() const { return LHS; } - LExpr *left() { return LHS; } - - const LExpr *right() const { return RHS; } - LExpr *right() { return RHS; } -}; - -class And : public BinOp { -public: - And(LExpr *LHS, LExpr *RHS) : BinOp(LHS, RHS, LExpr::And) {} - - static bool classof(const LExpr *E) { return E->kind() == LExpr::And; } -}; - -class Or : public BinOp { -public: - Or(LExpr *LHS, LExpr *RHS) : BinOp(LHS, RHS, LExpr::Or) {} - - static bool classof(const LExpr *E) { return E->kind() == LExpr::Or; } -}; - -class Not : public LExpr { - LExpr *Exp; - -public: - Not(LExpr *Exp) : LExpr(LExpr::Not), Exp(Exp) {} - - const LExpr *exp() const { return Exp; } - LExpr *exp() { return Exp; } - - static bool classof(const LExpr *E) { return E->kind() == LExpr::Not; } -}; - -/// \brief Logical implication. Returns true if LHS implies RHS, i.e. if LHS -/// holds, then RHS must hold. For example, (A & B) implies A. -bool implies(const LExpr *LHS, const LExpr *RHS); - -bool LExpr::implies(const LExpr *RHS) const { - return lexpr::implies(this, RHS); -} - -} -} -} - -#endif - diff --git a/include/clang/Analysis/Analyses/ThreadSafetyOps.def b/include/clang/Analysis/Analyses/ThreadSafetyOps.def deleted file mode 100644 index 0d2458b..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyOps.def +++ /dev/null @@ -1,57 +0,0 @@ -//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the list of core opcodes for the Thread Safety -// Typed Intermediate language. Please see ThreadSafetyTIL.h for more -// information. -// -//===----------------------------------------------------------------------===// - - -TIL_OPCODE_DEF(Future) -TIL_OPCODE_DEF(Undefined) -TIL_OPCODE_DEF(Wildcard) - -TIL_OPCODE_DEF(Literal) -TIL_OPCODE_DEF(LiteralPtr) -TIL_OPCODE_DEF(Variable) -TIL_OPCODE_DEF(Function) -TIL_OPCODE_DEF(SFunction) -TIL_OPCODE_DEF(Code) -TIL_OPCODE_DEF(Field) - -TIL_OPCODE_DEF(Apply) -TIL_OPCODE_DEF(SApply) -TIL_OPCODE_DEF(Project) - -TIL_OPCODE_DEF(Call) -TIL_OPCODE_DEF(Alloc) -TIL_OPCODE_DEF(Load) -TIL_OPCODE_DEF(Store) -TIL_OPCODE_DEF(ArrayIndex) -TIL_OPCODE_DEF(ArrayAdd) - -TIL_OPCODE_DEF(UnaryOp) -TIL_OPCODE_DEF(BinaryOp) -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) -TIL_OPCODE_DEF(IfThenElse) -TIL_OPCODE_DEF(Let) - diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/include/clang/Analysis/Analyses/ThreadSafetyTIL.h deleted file mode 100644 index be8a710..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ /dev/null @@ -1,1918 +0,0 @@ -//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT in the llvm repository for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines a simple Typed Intermediate Language, or TIL, that is used -// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended -// to be largely independent of clang, in the hope that the analysis can be -// reused for other non-C++ languages. All dependencies on clang/llvm should -// go in ThreadSafetyUtil.h. -// -// Thread safety analysis works by comparing mutex expressions, e.g. -// -// class A { Mutex mu; int dat GUARDED_BY(this->mu); } -// class B { A a; } -// -// void foo(B* b) { -// (*b).a.mu.lock(); // locks (*b).a.mu -// b->a.dat = 0; // substitute &b->a for 'this'; -// // requires lock on (&b->a)->mu -// (b->a.mu).unlock(); // unlocks (b->a.mu) -// } -// -// As illustrated by the above example, clang Exprs are not well-suited to -// represent mutex expressions directly, since there is no easy way to compare -// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs -// into a simple intermediate language (IL). The IL supports: -// -// (1) comparisons for semantic equality of expressions -// (2) SSA renaming of variables -// (3) wildcards and pattern matching over expressions -// (4) hash-based expression lookup -// -// The TIL is currently very experimental, is intended only for use within -// the thread safety analysis, and is subject to change without notice. -// After the API stabilizes and matures, it may be appropriate to make this -// more generally available to other analyses. -// -// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_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 <algorithm> -#include <cassert> -#include <cstddef> -#include <stdint.h> -#include <utility> - - -namespace clang { -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_Shl, // << - BOP_Shr, // >> - BOP_BitAnd, // & - BOP_BitXor, // ^ - BOP_BitOr, // | - BOP_Eq, // == - BOP_Neq, // != - BOP_Lt, // < - BOP_Leq, // <= - 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_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 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, - BT_Bool, - BT_Int, - BT_Float, - BT_String, // String literals - BT_Pointer, - BT_ValueRef - }; - - enum SizeType : unsigned char { - ST_0 = 0, - ST_1, - ST_8, - ST_16, - ST_32, - ST_64, - ST_128 - }; - - inline static SizeType getSizeType(unsigned nbytes); - - template <class T> - inline static ValueType getValueType(); - - ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) - : Base(B), Size(Sz), Signed(S), VectSize(VS) - { } - - BaseType Base; - SizeType Size; - bool Signed; - unsigned char VectSize; // 0 for scalar, otherwise num elements in vector -}; - - -inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { - switch (nbytes) { - case 1: return ST_8; - case 2: return ST_16; - case 4: return ST_32; - case 8: return ST_64; - case 16: return ST_128; - default: return ST_0; - } -} - - -template<> -inline ValueType ValueType::getValueType<void>() { - return ValueType(BT_Void, ST_0, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<bool>() { - return ValueType(BT_Bool, ST_1, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<int8_t>() { - return ValueType(BT_Int, ST_8, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<uint8_t>() { - return ValueType(BT_Int, ST_8, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<int16_t>() { - return ValueType(BT_Int, ST_16, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<uint16_t>() { - return ValueType(BT_Int, ST_16, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<int32_t>() { - return ValueType(BT_Int, ST_32, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<uint32_t>() { - return ValueType(BT_Int, ST_32, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<int64_t>() { - return ValueType(BT_Int, ST_64, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<uint64_t>() { - return ValueType(BT_Int, ST_64, false, 0); -} - -template<> -inline ValueType ValueType::getValueType<float>() { - return ValueType(BT_Float, ST_32, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<double>() { - return ValueType(BT_Float, ST_64, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<long double>() { - return ValueType(BT_Float, ST_128, true, 0); -} - -template<> -inline ValueType ValueType::getValueType<StringRef>() { - return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); -} - -template<> -inline ValueType ValueType::getValueType<void*>() { - return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); -} - - -class BasicBlock; - - -/// Base class for AST nodes in the typed intermediate language. -class SExpr { -public: - TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } - - // Subclasses of SExpr must define the following: - // - // This(const This& E, ...) { - // copy constructor: construct copy of E, with some additional arguments. - // } - // - // template <class V> - // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - // traverse all subexpressions, following the traversal/rewriter interface. - // } - // - // template <class C> typename C::CType compare(CType* E, C& Cmp) { - // compare all subexpressions, following the comparator interface - // } - void *operator new(size_t S, MemRegionRef &R) { - return ::operator new(S, R); - } - - /// 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 *) = delete; - - /// 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), 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() = delete; - - /// SExpr objects must be created in an arena. - void *operator new(size_t) = delete; -}; - - -// Contains various helper functions for SExprs. -namespace ThreadSafetyTIL { - inline bool isTrivial(const SExpr *E) { - unsigned Op = E->opcode(); - return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; - } -} - -// Nodes which declare variables -class Function; -class SFunction; -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. -class Variable : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } - - enum VariableKind { - VK_Let, ///< Let-variable - VK_Fun, ///< Function parameter - VK_SFun ///< SFunction (self) parameter - }; - - 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); } - - /// Return the name of the variable, if any. - StringRef name() const { return Name; } - - /// Return the clang declaration for this variable, if any. - const clang::ValueDecl *clangDecl() const { return Cvdecl; } - - /// 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 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) { - // This routine is only called for variable references. - return Vs.reduceVariableRef(this); - } - - template <class C> - typename C::CType compare(const Variable* E, C& Cmp) const { - return Cmp.compareVariableRefs(this, E); - } - -private: - friend class Function; - friend class SFunction; - friend class BasicBlock; - friend class Let; - - StringRef Name; // The name of the variable. - SExpr* Definition; // The TIL type or definition - const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. -}; - - -/// Placeholder for an expression that has not yet been created. -/// Used to implement lazy copy and rewriting strategies. -class Future : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } - - enum FutureStatus { - FS_pending, - FS_evaluating, - FS_done - }; - - Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {} - -private: - virtual ~Future() = delete; - -public: - // A lazy rewriting strategy should subclass Future and override this method. - virtual SExpr *compute() { return nullptr; } - - // Return the result of this future if it exists, otherwise return null. - SExpr *maybeGetResult() const { - return Result; - } - - // Return the result of this future; forcing it if necessary. - SExpr *result() { - switch (Status) { - case FS_pending: - return force(); - case FS_evaluating: - return nullptr; // infinite loop; illegal recursion. - case FS_done: - return Result; - } - } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - assert(Result && "Cannot traverse Future that has not been forced."); - return Vs.traverse(Result, Ctx); - } - - 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: - SExpr* force(); - - FutureStatus Status; - SExpr *Result; -}; - - -/// 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; } - - Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} - Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - return Vs.reduceUndefined(*this); - } - - template <class C> - typename C::CType compare(const Undefined* E, C& Cmp) const { - return Cmp.trueResult(); - } - -private: - const clang::Stmt *Cstmt; -}; - - -/// Placeholder for a wildcard that matches any other expression. -class Wildcard : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } - - Wildcard() : SExpr(COP_Wildcard) {} - Wildcard(const Wildcard &W) : SExpr(W) {} - - template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - return Vs.reduceWildcard(*this); - } - - template <class C> - typename C::CType compare(const Wildcard* E, C& Cmp) const { - return Cmp.trueResult(); - } -}; - - -template <class T> class LiteralT; - -// Base class for literal values. -class Literal : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } - - Literal(const clang::Expr *C) - : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) - { } - Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {} - Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {} - - // The clang expression for this literal. - const clang::Expr *clangExpr() const { return Cexpr; } - - ValueType valueType() const { return ValType; } - - template<class T> const LiteralT<T>& as() const { - return *static_cast<const LiteralT<T>*>(this); - } - template<class T> LiteralT<T>& as() { - return *static_cast<LiteralT<T>*>(this); - } - - template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); - - template <class C> - typename C::CType compare(const Literal* E, C& Cmp) const { - // TODO: defer actual comparison to LiteralT - return Cmp.trueResult(); - } - -private: - const ValueType ValType; - const clang::Expr *Cexpr; -}; - - -// Derived class for literal values, which stores the actual value. -template<class T> -class LiteralT : public Literal { -public: - LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { } - LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { } - - T value() const { return Val;} - T& value() { return Val; } - -private: - T Val; -}; - - - -template <class V> -typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { - if (Cexpr) - return Vs.reduceLiteral(*this); - - switch (ValType.Base) { - case ValueType::BT_Void: - break; - case ValueType::BT_Bool: - return Vs.reduceLiteralT(as<bool>()); - case ValueType::BT_Int: { - switch (ValType.Size) { - case ValueType::ST_8: - if (ValType.Signed) - return Vs.reduceLiteralT(as<int8_t>()); - else - return Vs.reduceLiteralT(as<uint8_t>()); - case ValueType::ST_16: - if (ValType.Signed) - return Vs.reduceLiteralT(as<int16_t>()); - else - return Vs.reduceLiteralT(as<uint16_t>()); - case ValueType::ST_32: - if (ValType.Signed) - return Vs.reduceLiteralT(as<int32_t>()); - else - return Vs.reduceLiteralT(as<uint32_t>()); - case ValueType::ST_64: - if (ValType.Signed) - return Vs.reduceLiteralT(as<int64_t>()); - else - return Vs.reduceLiteralT(as<uint64_t>()); - default: - break; - } - } - case ValueType::BT_Float: { - switch (ValType.Size) { - case ValueType::ST_32: - return Vs.reduceLiteralT(as<float>()); - case ValueType::ST_64: - return Vs.reduceLiteralT(as<double>()); - default: - break; - } - } - case ValueType::BT_String: - return Vs.reduceLiteralT(as<StringRef>()); - case ValueType::BT_Pointer: - return Vs.reduceLiteralT(as<void*>()); - case ValueType::BT_ValueRef: - break; - } - return Vs.reduceLiteral(*this); -} - - -/// 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; } - - LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} - LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} - - // The clang declaration for the value that this pointer points to. - const clang::ValueDecl *clangDecl() const { return Cvdecl; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - return Vs.reduceLiteralPtr(*this); - } - - template <class C> - typename C::CType compare(const LiteralPtr* E, C& Cmp) const { - return Cmp.comparePointers(Cvdecl, E->Cvdecl); - } - -private: - const clang::ValueDecl *Cvdecl; -}; - - -/// 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; } - - Function(Variable *Vd, SExpr *Bd) - : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { - Vd->setKind(Variable::VK_Fun); - } - Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor - : SExpr(F), VarDecl(Vd), Body(Bd) { - Vd->setKind(Variable::VK_Fun); - } - - Variable *variableDecl() { return VarDecl; } - const Variable *variableDecl() const { return VarDecl; } - - 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) { - // This is a variable declaration, so traverse the definition. - auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); - // Tell the rewriter to enter the scope of the function. - Variable *Nvd = Vs.enterScope(*VarDecl, E0); - auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); - Vs.exitScope(*VarDecl); - return Vs.reduceFunction(*this, Nvd, E1); - } - - 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)) - return Ct; - Cmp.enterScope(variableDecl(), E->variableDecl()); - Ct = Cmp.compare(body(), E->body()); - Cmp.leaveScope(); - return Ct; - } - -private: - Variable *VarDecl; - SExpr* Body; -}; - - -/// A self-applicable function. -/// A self-applicable function can be applied to itself. It's useful for -/// implementing objects and late binding. -class SFunction : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } - - SFunction(Variable *Vd, SExpr *B) - : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { - assert(Vd->Definition == nullptr); - Vd->setKind(Variable::VK_SFun); - Vd->Definition = this; - } - SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor - : SExpr(F), VarDecl(Vd), Body(B) { - assert(Vd->Definition == nullptr); - Vd->setKind(Variable::VK_SFun); - Vd->Definition = this; - } - - Variable *variableDecl() { return VarDecl; } - const Variable *variableDecl() const { return VarDecl; } - - 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) { - // A self-variable points to the SFunction itself. - // A rewrite must introduce the variable with a null definition, and update - // it after 'this' has been rewritten. - Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); - auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); - Vs.exitScope(*VarDecl); - // A rewrite operation will call SFun constructor to set Vvd->Definition. - return Vs.reduceSFunction(*this, Nvd, E1); - } - - 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(); - return Ct; - } - -private: - Variable *VarDecl; - SExpr* Body; -}; - - -/// A block of code -- e.g. the body of a function. -class Code : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } - - Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} - Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor - : SExpr(C), ReturnType(T), Body(B) {} - - SExpr *returnType() { return ReturnType; } - const SExpr *returnType() const { return ReturnType; } - - 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) { - auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); - auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); - return Vs.reduceCode(*this, Nt, Nb); - } - - 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; - return Cmp.compare(body(), E->body()); - } - -private: - SExpr* ReturnType; - SExpr* Body; -}; - - -/// A typed, writable location in memory -class Field : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } - - Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} - Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor - : SExpr(C), Range(R), Body(B) {} - - SExpr *range() { return Range; } - const SExpr *range() const { return Range; } - - 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) { - auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); - auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); - return Vs.reduceField(*this, Nr, Nb); - } - - 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; - return Cmp.compare(body(), E->body()); - } - -private: - SExpr* Range; - SExpr* Body; -}; - - -/// 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; } - - Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} - Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor - : SExpr(A), Fun(F), Arg(Ar) - {} - - SExpr *fun() { return Fun; } - const SExpr *fun() const { return Fun; } - - 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) { - auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); - auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); - return Vs.reduceApply(*this, Nf, Na); - } - - 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; - return Cmp.compare(arg(), E->arg()); - } - -private: - SExpr* Fun; - SExpr* Arg; -}; - - -/// Apply a self-argument to a self-applicable function. -class SApply : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } - - SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} - SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor - : SExpr(A), Sfun(Sf), Arg(Ar) {} - - SExpr *sfun() { return Sfun; } - const SExpr *sfun() const { return Sfun; } - - SExpr *arg() { return Arg ? Arg : Sfun; } - const SExpr *arg() const { return Arg ? Arg : Sfun; } - - 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 ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) - : nullptr; - return Vs.reduceSApply(*this, Nf, Na); - } - - 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; - return Cmp.compare(arg(), E->arg()); - } - -private: - SExpr* Sfun; - SExpr* Arg; -}; - - -/// Project a named slot from a C++ struct or class. -class Project : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } - - Project(SExpr *R, StringRef SName) - : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr) - { } - 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; } - const SExpr *record() const { return Rec; } - - const clang::ValueDecl *clangDecl() 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) - return Cvdecl->getName(); - else - return SlotName; - } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); - return Vs.reduceProject(*this, Nr); - } - - 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; - return Cmp.comparePointers(Cvdecl, E->Cvdecl); - } - -private: - SExpr* Rec; - StringRef SlotName; - const clang::ValueDecl *Cvdecl; -}; - - -/// Call a function (after all arguments have been applied). -class Call : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } - - Call(SExpr *T, const clang::CallExpr *Ce = nullptr) - : SExpr(COP_Call), Target(T), Cexpr(Ce) {} - Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} - - SExpr *target() { return Target; } - const SExpr *target() const { return Target; } - - const clang::CallExpr *clangCallExpr() const { return Cexpr; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); - return Vs.reduceCall(*this, Nt); - } - - template <class C> - typename C::CType compare(const Call* E, C& Cmp) const { - return Cmp.compare(target(), E->target()); - } - -private: - SExpr* Target; - const clang::CallExpr *Cexpr; -}; - - -/// Allocate memory for a new value on the heap or stack. -class Alloc : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } - - enum AllocKind { - AK_Stack, - AK_Heap - }; - - Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } - Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } - - AllocKind kind() const { return static_cast<AllocKind>(Flags); } - - SExpr *dataType() { return Dtype; } - const SExpr *dataType() const { return Dtype; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); - return Vs.reduceAlloc(*this, Nd); - } - - 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; - return Cmp.compare(dataType(), E->dataType()); - } - -private: - SExpr* Dtype; -}; - - -/// Load a value from memory. -class Load : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } - - Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} - Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} - - SExpr *pointer() { return Ptr; } - const SExpr *pointer() const { return Ptr; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); - return Vs.reduceLoad(*this, Np); - } - - template <class C> - typename C::CType compare(const Load* E, C& Cmp) const { - return Cmp.compare(pointer(), E->pointer()); - } - -private: - SExpr* Ptr; -}; - - -/// 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; } - - 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; } // Address to store to - const SExpr *destination() const { return Dest; } - - 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) { - auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); - auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); - return Vs.reduceStore(*this, Np, Nv); - } - - 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; - return Cmp.compare(source(), E->source()); - } - -private: - SExpr* Dest; - SExpr* Source; -}; - - -/// 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; } - - ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} - ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) - : SExpr(E), Array(A), Index(N) {} - - SExpr *array() { return Array; } - const SExpr *array() const { return Array; } - - 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) { - auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); - auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); - return Vs.reduceArrayIndex(*this, Na, Ni); - } - - 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; - return Cmp.compare(index(), E->index()); - } - -private: - 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. -class ArrayAdd : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } - - ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} - ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) - : SExpr(E), Array(A), Index(N) {} - - SExpr *array() { return Array; } - const SExpr *array() const { return Array; } - - 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) { - auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); - auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); - return Vs.reduceArrayAdd(*this, Na, Ni); - } - - 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; - return Cmp.compare(index(), E->index()); - } - -private: - SExpr* Array; - SExpr* Index; -}; - - -/// 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; } - - UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { - Flags = Op; - } - UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } - - TIL_UnaryOpcode unaryOpcode() const { - return static_cast<TIL_UnaryOpcode>(Flags); - } - - 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) { - auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); - return Vs.reduceUnaryOp(*this, Ne); - } - - 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)) - return Ct; - return Cmp.compare(expr(), E->expr()); - } - -private: - SExpr* Expr0; -}; - - -/// 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; } - - BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) - : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { - Flags = Op; - } - BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) - : SExpr(B), Expr0(E0), Expr1(E1) { - Flags = B.Flags; - } - - TIL_BinaryOpcode binaryOpcode() const { - return static_cast<TIL_BinaryOpcode>(Flags); - } - - SExpr *expr0() { return Expr0; } - const SExpr *expr0() const { return Expr0; } - - 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) { - auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); - auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); - return Vs.reduceBinaryOp(*this, Ne0, Ne1); - } - - 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)) - return Ct; - Ct = Cmp.compare(expr0(), E->expr0()); - if (Cmp.notTrue(Ct)) - return Ct; - return Cmp.compare(expr1(), E->expr1()); - } - -private: - SExpr* Expr0; - SExpr* Expr1; -}; - - -/// Cast 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; } - - Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } - Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } - - TIL_CastOpcode castOpcode() const { - return static_cast<TIL_CastOpcode>(Flags); - } - - 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) { - auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); - return Vs.reduceCast(*this, Ne); - } - - 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)) - return Ct; - return Cmp.compare(expr(), E->expr()); - } - -private: - 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: - typedef SimpleArray<SExpr *> ValArray; - - // In minimal SSA form, all Phi nodes are MultiVal. - // During conversion to SSA, incomplete Phi nodes may be introduced, which - // are later determined to be SingleVal, and are thus redundant. - enum Status { - PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) - PH_SingleVal, // Phi node has one distinct value, and can be eliminated - PH_Incomplete // Phi node is incomplete - }; - - static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } - - 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; } - - 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> - Nvs(Vs, Values.size()); - - for (auto *Val : Values) { - Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); - } - return Vs.reducePhi(*this, Nvs); - } - - 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(); - } -}; - - -/// 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 TargetBlock; - } - - 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 llvm::makeArrayRef(Branches); - } - - 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 None; - } - - 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 None; - } -} - - -/// 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<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) - : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), - 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; } - - /// 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 DominatorNode.Parent; } - BasicBlock *parent() { return DominatorNode.Parent; } - - const InstrArray &arguments() const { return Args; } - InstrArray &arguments() { return Args; } - - InstrArray &instructions() { return Instrs; } - const InstrArray &instructions() const { return Instrs; } - - /// 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; } - - void setTerminator(Terminator *E) { TermInstr = 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. - void addArgument(Phi *V) { - Args.reserveCheck(1, Arena); - Args.push_back(V); - } - /// Add a new instruction. - void addInstruction(SExpr *V) { - Instrs.reserveCheck(1, Arena); - Instrs.push_back(V); - } - // Add a new predecessor, and return the phi-node index for it. - // Will add an argument to all phi-nodes, initialized to nullptr. - unsigned addPredecessor(BasicBlock *Pred); - - // Reserve space for Nargs arguments. - void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } - - // Reserve space for Nins instructions. - void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } - - // 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. - unsigned findPredecessorIndex(const BasicBlock *BB) const { - auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB); - return std::distance(Predecessors.cbegin(), I); - } - - template <class V> - typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { - 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 *E : Args) { - auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); - Nas.push_back(Ne); - } - for (auto *E : Instrs) { - auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); - Nis.push_back(Ne); - } - auto Nt = Vs.traverse(TermInstr, Ctx); - - // Exiting the basic block should handle any scope cleanup. - Vs.exitBasicBlock(*this); - - return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); - } - - template <class C> - typename C::CType compare(const BasicBlock *E, C &Cmp) const { - // TODO: implement CFG comparisons - return Cmp.comparePointers(this, E); - } - -private: - friend class SCFG; - - 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(); - -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. -class SCFG : public SExpr { -public: - typedef SimpleArray<BasicBlock *> BlockArray; - typedef BlockArray::iterator iterator; - typedef BlockArray::const_iterator const_iterator; - - static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } - - SCFG(MemRegionRef A, unsigned Nblocks) - : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), - 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), 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(); } - - const_iterator begin() const { return cbegin(); } - const_iterator end() const { return cend(); } - - const_iterator cbegin() const { return Blocks.cbegin(); } - const_iterator cend() const { return Blocks.cend(); } - - const BasicBlock *entry() const { return Entry; } - BasicBlock *entry() { return Entry; } - 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; - Blocks.reserveCheck(1, Arena); - Blocks.push_back(BB); - } - - void setEntry(BasicBlock *BB) { Entry = BB; } - void setExit(BasicBlock *BB) { Exit = BB; } - - 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)) ); - } - Vs.exitCFG(*this); - return Vs.reduceSCFG(*this, Bbs); - } - - 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; -}; - - - -/// 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; } - - Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { } - Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { } - - StringRef name() const { return Name; } - - template <class V> - typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { - return Vs.reduceIdentifier(*this); - } - - template <class C> - typename C::CType compare(const Identifier* E, C& Cmp) const { - return Cmp.compareStrings(name(), E->name()); - } - -private: - StringRef Name; -}; - - -/// 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; } - - IfThenElse(SExpr *C, SExpr *T, SExpr *E) - : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) - { } - IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) - : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) - { } - - SExpr *condition() { return Condition; } // Address to store to - const SExpr *condition() const { return Condition; } - - SExpr *thenExpr() { return ThenExpr; } // Value to store - const SExpr *thenExpr() const { return ThenExpr; } - - 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) { - auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); - auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); - auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); - return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); - } - - 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; - Ct = Cmp.compare(thenExpr(), E->thenExpr()); - if (Cmp.notTrue(Ct)) - return Ct; - return Cmp.compare(elseExpr(), E->elseExpr()); - } - -private: - 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. -class Let : public SExpr { -public: - static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } - - Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { - Vd->setKind(Variable::VK_Let); - } - Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { - Vd->setKind(Variable::VK_Let); - } - - Variable *variableDecl() { return VarDecl; } - const Variable *variableDecl() const { return VarDecl; } - - 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) { - // This is a variable declaration, so traverse the definition. - auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); - // Tell the rewriter to enter the scope of the let variable. - Variable *Nvd = Vs.enterScope(*VarDecl, E0); - auto E1 = Vs.traverse(Body, Ctx); - Vs.exitScope(*VarDecl); - return Vs.reduceLet(*this, Nvd, E1); - } - - 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)) - return Ct; - Cmp.enterScope(variableDecl(), E->variableDecl()); - Ct = Cmp.compare(body(), E->body()); - Cmp.leaveScope(); - return Ct; - } - -private: - Variable *VarDecl; - SExpr* Body; -}; - - - -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 diff --git a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h deleted file mode 100644 index 705fe91..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ /dev/null @@ -1,902 +0,0 @@ -//===- ThreadSafetyTraverse.h ----------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines a framework for doing generic traversals and rewriting -// operations over the Thread Safety TIL. -// -// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTRAVERSE_H - -#include "ThreadSafetyTIL.h" -#include <ostream> - -namespace clang { -namespace threadSafety { -namespace til { - -// Defines an interface used to traverse SExprs. Traversals have been made as -// generic as possible, and are intended to handle any kind of pass over the -// AST, e.g. visiters, copying, non-destructive rewriting, destructive -// (in-place) rewriting, hashing, typing, etc. -// -// Traversals implement the functional notion of a "fold" operation on SExprs. -// Each SExpr class provides a traverse method, which does the following: -// * e->traverse(v): -// // compute a result r_i for each subexpression e_i -// for (i = 1..n) r_i = v.traverse(e_i); -// // combine results into a result for e, where X is the class of e -// return v.reduceX(*e, r_1, .. r_n). -// -// A visitor can control the traversal by overriding the following methods: -// * v.traverse(e): -// return v.traverseByCase(e), which returns v.traverseX(e) -// * v.traverseX(e): (X is the class of e) -// return e->traverse(v). -// * v.reduceX(*e, r_1, .. r_n): -// compute a result for a node of type X -// -// The reduceX methods control the kind of traversal (visitor, copy, etc.). -// They are defined in derived classes. -// -// Class R defines the basic interface types (R_SExpr). -template <class Self, class R> -class Traversal { -public: - Self *self() { return static_cast<Self *>(this); } - - // Traverse an expression -- returning a result of type R_SExpr. - // Override this method to do something for every expression, regardless - // of which kind it is. - // 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); - } - - // 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); - } - - // Helper method to call traverseX(e) on the appropriate type. - typename R::R_SExpr traverseByCase(SExpr *E, typename R::R_Ctx Ctx) { - switch (E->opcode()) { -#define TIL_OPCODE_DEF(X) \ - case COP_##X: \ - return self()->traverse##X(cast<X>(E), Ctx); -#include "ThreadSafetyOps.def" -#undef TIL_OPCODE_DEF - } - return self()->reduceNull(); - } - -// Traverse e, by static dispatch on the type "X" of e. -// Override these methods to do something for a particular kind of term. -#define TIL_OPCODE_DEF(X) \ - typename R::R_SExpr traverse##X(X *e, typename R::R_Ctx Ctx) { \ - return e->traverse(*self(), Ctx); \ - } -#include "ThreadSafetyOps.def" -#undef TIL_OPCODE_DEF -}; - - -// Base class for simple reducers that don't much care about the context. -class SimpleReducerBase { -public: - enum TraversalKind { - 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 - // about where a term appears. This can be used to encoding the - // "current continuation" for CPS transforms, or other information. - typedef TraversalKind R_Ctx; - - // Create context for an ordinary subexpression. - R_Ctx subExprCtx(R_Ctx Ctx) { return TRV_Normal; } - - // Create context for a subexpression that occurs in a declaration position - // (e.g. function body). - R_Ctx declCtx(R_Ctx Ctx) { return TRV_Decl; } - - // Create context for a subexpression that occurs in a position that - // should be reduced lazily. (e.g. code body). - R_Ctx lazyCtx(R_Ctx Ctx) { return TRV_Lazy; } - - // Create context for a subexpression that occurs in a type position. - R_Ctx typeCtx(R_Ctx Ctx) { return TRV_Type; } -}; - - -// Base class for traversals that rewrite an SExpr to another SExpr. -class CopyReducerBase : public SimpleReducerBase { -public: - // R_SExpr is the result type for a traversal. - // A copy or non-destructive rewrite returns a newly allocated term. - typedef SExpr *R_SExpr; - typedef BasicBlock *R_BasicBlock; - - // Container is a minimal interface used to store results when traversing - // SExprs of variable arity, such as Phi, Goto, and SCFG. - template <class T> class Container { - public: - // Allocate a new container with a capacity for n elements. - Container(CopyReducerBase &S, unsigned N) : Elems(S.Arena, N) {} - - // Push a new element onto the container. - void push_back(T E) { Elems.push_back(E); } - - SimpleArray<T> Elems; - }; - - CopyReducerBase(MemRegionRef A) : Arena(A) {} - -protected: - MemRegionRef Arena; -}; - - -// Base class for visit traversals. -class VisitReducerBase : public SimpleReducerBase { -public: - // A visitor returns a bool, representing success or failure. - typedef bool R_SExpr; - typedef bool R_BasicBlock; - - // A visitor "container" is a single bool, which accumulates success. - template <class T> class Container { - public: - Container(VisitReducerBase &S, unsigned N) : Success(true) {} - void push_back(bool E) { Success = Success && E; } - - bool Success; - }; -}; - - -// Implements a traversal that visits each subexpression, and returns either -// true or false. -template <class Self> -class VisitReducer : public Traversal<Self, VisitReducerBase>, - public VisitReducerBase { -public: - VisitReducer() {} - -public: - R_SExpr reduceNull() { return true; } - R_SExpr reduceUndefined(Undefined &Orig) { return true; } - R_SExpr reduceWildcard(Wildcard &Orig) { return true; } - - R_SExpr reduceLiteral(Literal &Orig) { return true; } - template<class T> - R_SExpr reduceLiteralT(LiteralT<T> &Orig) { return true; } - R_SExpr reduceLiteralPtr(Literal &Orig) { return true; } - - R_SExpr reduceFunction(Function &Orig, Variable *Nvd, R_SExpr E0) { - return Nvd && E0; - } - R_SExpr reduceSFunction(SFunction &Orig, Variable *Nvd, R_SExpr E0) { - return Nvd && E0; - } - R_SExpr reduceCode(Code &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceField(Field &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceApply(Apply &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceSApply(SApply &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceProject(Project &Orig, R_SExpr E0) { return E0; } - R_SExpr reduceCall(Call &Orig, R_SExpr E0) { return E0; } - R_SExpr reduceAlloc(Alloc &Orig, R_SExpr E0) { return E0; } - R_SExpr reduceLoad(Load &Orig, R_SExpr E0) { return E0; } - R_SExpr reduceStore(Store &Orig, R_SExpr E0, R_SExpr E1) { return E0 && E1; } - R_SExpr reduceArrayIndex(Store &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceArrayAdd(Store &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceUnaryOp(UnaryOp &Orig, R_SExpr E0) { return E0; } - R_SExpr reduceBinaryOp(BinaryOp &Orig, R_SExpr E0, R_SExpr E1) { - return E0 && E1; - } - R_SExpr reduceCast(Cast &Orig, R_SExpr E0) { return E0; } - - R_SExpr reduceSCFG(SCFG &Orig, Container<BasicBlock *> Bbs) { - return Bbs.Success; - } - R_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) { - return As.Success; - } - R_SExpr reduceGoto(Goto &Orig, BasicBlock *B) { - return true; - } - 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; - } - R_SExpr reduceIfThenElse(IfThenElse &Orig, R_SExpr C, R_SExpr T, R_SExpr E) { - return C && T && E; - } - R_SExpr reduceLet(Let &Orig, Variable *Nvd, R_SExpr B) { - return Nvd && B; - } - - Variable *enterScope(Variable &Orig, R_SExpr E0) { return &Orig; } - void exitScope(const Variable &Orig) {} - void enterCFG(SCFG &Cfg) {} - void exitCFG(SCFG &Cfg) {} - void enterBasicBlock(BasicBlock &BB) {} - void exitBasicBlock(BasicBlock &BB) {} - - Variable *reduceVariableRef (Variable *Ovd) { return Ovd; } - BasicBlock *reduceBasicBlockRef(BasicBlock *Obb) { return Obb; } - -public: - bool traverse(SExpr *E, TraversalKind K = TRV_Normal) { - Success = Success && this->traverseByCase(E); - return Success; - } - - static bool visit(SExpr *E) { - Self Visitor; - return Visitor.traverse(E, TRV_Normal); - } - -private: - bool Success; -}; - - -// Basic class for comparison operations over expressions. -template <typename Self> -class Comparator { -protected: - Self *self() { return reinterpret_cast<Self *>(this); } - -public: - bool compareByCase(const SExpr *E1, const SExpr* E2) { - switch (E1->opcode()) { -#define TIL_OPCODE_DEF(X) \ - case COP_##X: \ - return cast<X>(E1)->compare(cast<X>(E2), *self()); -#include "ThreadSafetyOps.def" -#undef TIL_OPCODE_DEF - } - return false; - } -}; - - -class EqualsComparator : public Comparator<EqualsComparator> { -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) { - 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) { - 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, bool CS = true) - : Verbose(V), Cleanup(C), CStyle(CS) - {} - - static void print(const SExpr *E, StreamType &SS) { - Self printer; - printer.printSExpr(E, SS, Prec_MAX); - } - -protected: - Self *self() { return reinterpret_cast<Self *>(this); } - - void newline(StreamType &SS) { - SS << "\n"; - } - - // TODO: further distinguish between binary operations. - static const unsigned Prec_Atom = 0; - static const unsigned Prec_Postfix = 1; - static const unsigned Prec_Unary = 2; - static const unsigned Prec_Binary = 3; - static const unsigned Prec_Other = 4; - static const unsigned Prec_Decl = 5; - static const unsigned Prec_MAX = 6; - - // Return the precedence of a given node, for use in pretty printing. - unsigned precedence(const SExpr *E) { - switch (E->opcode()) { - case COP_Future: return Prec_Atom; - case COP_Undefined: return Prec_Atom; - case COP_Wildcard: return Prec_Atom; - - case COP_Literal: return Prec_Atom; - case COP_LiteralPtr: return Prec_Atom; - case COP_Variable: return Prec_Atom; - case COP_Function: return Prec_Decl; - case COP_SFunction: return Prec_Decl; - case COP_Code: return Prec_Decl; - case COP_Field: return Prec_Decl; - - case COP_Apply: return Prec_Postfix; - case COP_SApply: return Prec_Postfix; - case COP_Project: return Prec_Postfix; - - case COP_Call: return Prec_Postfix; - case COP_Alloc: return Prec_Other; - case COP_Load: return Prec_Postfix; - case COP_Store: return Prec_Other; - case COP_ArrayIndex: return Prec_Postfix; - case COP_ArrayAdd: return Prec_Postfix; - - case COP_UnaryOp: return Prec_Unary; - case COP_BinaryOp: return Prec_Binary; - 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; - case COP_Let: return Prec_Decl; - } - return Prec_MAX; - } - - void printBlockLabel(StreamType & SS, const BasicBlock *BB, int index) { - if (!BB) { - SS << "BB_null"; - return; - } - SS << "BB_"; - SS << BB->blockID(); - if (index >= 0) { - SS << ":"; - SS << index; - } - } - - - 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 << "("; - self()->printSExpr(E, SS, Prec_MAX); - SS << ")"; - return; - } - - switch (E->opcode()) { -#define TIL_OPCODE_DEF(X) \ - case COP_##X: \ - self()->print##X(cast<X>(E), SS); \ - return; -#include "ThreadSafetyOps.def" -#undef TIL_OPCODE_DEF - } - } - - void printNull(StreamType &SS) { - SS << "#null"; - } - - void printFuture(const Future *E, StreamType &SS) { - self()->printSExpr(E->maybeGetResult(), SS, Prec_Atom); - } - - void printUndefined(const Undefined *E, StreamType &SS) { - SS << "#undefined"; - } - - void printWildcard(const Wildcard *E, StreamType &SS) { - SS << "*"; - } - - template<class T> - void printLiteralT(const LiteralT<T> *E, StreamType &SS) { - SS << E->value(); - } - - void printLiteralT(const LiteralT<uint8_t> *E, StreamType &SS) { - SS << "'" << E->value() << "'"; - } - - void printLiteral(const Literal *E, StreamType &SS) { - if (E->clangExpr()) { - SS << getSourceLiteralString(E->clangExpr()); - return; - } - else { - ValueType VT = E->valueType(); - switch (VT.Base) { - case ValueType::BT_Void: { - SS << "void"; - return; - } - case ValueType::BT_Bool: { - if (E->as<bool>().value()) - SS << "true"; - else - SS << "false"; - return; - } - case ValueType::BT_Int: { - switch (VT.Size) { - case ValueType::ST_8: - if (VT.Signed) - printLiteralT(&E->as<int8_t>(), SS); - else - printLiteralT(&E->as<uint8_t>(), SS); - return; - case ValueType::ST_16: - if (VT.Signed) - printLiteralT(&E->as<int16_t>(), SS); - else - printLiteralT(&E->as<uint16_t>(), SS); - return; - case ValueType::ST_32: - if (VT.Signed) - printLiteralT(&E->as<int32_t>(), SS); - else - printLiteralT(&E->as<uint32_t>(), SS); - return; - case ValueType::ST_64: - if (VT.Signed) - printLiteralT(&E->as<int64_t>(), SS); - else - printLiteralT(&E->as<uint64_t>(), SS); - return; - default: - break; - } - break; - } - case ValueType::BT_Float: { - switch (VT.Size) { - case ValueType::ST_32: - printLiteralT(&E->as<float>(), SS); - return; - case ValueType::ST_64: - printLiteralT(&E->as<double>(), SS); - return; - default: - break; - } - break; - } - case ValueType::BT_String: { - SS << "\""; - printLiteralT(&E->as<StringRef>(), SS); - SS << "\""; - return; - } - case ValueType::BT_Pointer: { - SS << "#ptr"; - return; - } - case ValueType::BT_ValueRef: { - SS << "#vref"; - return; - } - } - } - SS << "#lit"; - } - - void printLiteralPtr(const LiteralPtr *E, StreamType &SS) { - SS << E->clangDecl()->getNameAsString(); - } - - void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) { - if (CStyle && V->kind() == Variable::VK_SFun) - SS << "this"; - else - SS << V->name() << V->id(); - } - - void printFunction(const Function *E, StreamType &SS, unsigned sugared = 0) { - switch (sugared) { - default: - SS << "\\("; // Lambda - break; - case 1: - SS << "("; // Slot declarations - break; - case 2: - SS << ", "; // Curried functions - break; - } - self()->printVariable(E->variableDecl(), SS, true); - SS << ": "; - self()->printSExpr(E->variableDecl()->definition(), SS, Prec_MAX); - - const SExpr *B = E->body(); - if (B && B->opcode() == COP_Function) - self()->printFunction(cast<Function>(B), SS, 2); - else { - SS << ")"; - self()->printSExpr(B, SS, Prec_Decl); - } - } - - void printSFunction(const SFunction *E, StreamType &SS) { - SS << "@"; - self()->printVariable(E->variableDecl(), SS, true); - SS << " "; - self()->printSExpr(E->body(), SS, Prec_Decl); - } - - 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(const Field *E, StreamType &SS) { - SS << ": "; - self()->printSExpr(E->range(), SS, Prec_Decl-1); - SS << " = "; - self()->printSExpr(E->body(), SS, Prec_Decl); - } - - 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 << ", "; - } else { - self()->printSExpr(F, SS, Prec_Postfix); - SS << "("; - } - self()->printSExpr(E->arg(), SS, Prec_MAX); - if (!sugared) - SS << ")$"; - } - - void printSApply(const SApply *E, StreamType &SS) { - self()->printSExpr(E->sfun(), SS, Prec_Postfix); - if (E->isDelegation()) { - SS << "@("; - self()->printSExpr(E->arg(), SS, Prec_MAX); - 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); - if (CStyle && E->isArrow()) { - SS << "->"; - } - else { - SS << "."; - } - SS << E->slotName(); - } - - 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 << ")"; - } - else { - self()->printSExpr(T, SS, Prec_Postfix); - SS << "()"; - } - } - - void printAlloc(const Alloc *E, StreamType &SS) { - SS << "new "; - self()->printSExpr(E->dataType(), SS, Prec_Other-1); - } - - void printLoad(const Load *E, StreamType &SS) { - self()->printSExpr(E->pointer(), SS, Prec_Postfix); - if (!CStyle) - 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(const ArrayIndex *E, StreamType &SS) { - self()->printSExpr(E->array(), SS, Prec_Postfix); - SS << "["; - self()->printSExpr(E->index(), SS, Prec_MAX); - 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(const UnaryOp *E, StreamType &SS) { - SS << getUnaryOpcodeString(E->unaryOpcode()); - self()->printSExpr(E->expr(), SS, Prec_Unary); - } - - 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(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(const SCFG *E, StreamType &SS) { - SS << "CFG {\n"; - for (auto BBI : *E) { - printBasicBlock(BBI, SS); - } - SS << "}"; - newline(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()) - printBBInstr(A, SS); - - for (auto *I : E->instructions()) - printBBInstr(I, SS); - - const SExpr *T = E->terminator(); - if (T) { - self()->printSExpr(T, SS, Prec_MAX, false); - SS << ";"; - newline(SS); - } - newline(SS); - } - - void printPhi(const Phi *E, StreamType &SS) { - SS << "phi("; - if (E->status() == Phi::PH_SingleVal) - self()->printSExpr(E->values()[0], SS, Prec_MAX); - else { - unsigned i = 0; - for (auto V : E->values()) { - if (i++ > 0) - SS << ", "; - self()->printSExpr(V, SS, Prec_MAX); - } - } - SS << ")"; - } - - void printGoto(const Goto *E, StreamType &SS) { - SS << "goto "; - printBlockLabel(SS, E->targetBlock(), E->index()); - } - - void printBranch(const Branch *E, StreamType &SS) { - SS << "branch ("; - self()->printSExpr(E->condition(), SS, Prec_MAX); - SS << ") "; - printBlockLabel(SS, E->thenBlock(), -1); - SS << " "; - printBlockLabel(SS, E->elseBlock(), -1); - } - - 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(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 "; - printSExpr(E->thenExpr(), SS, Prec_Other); - SS << " else "; - printSExpr(E->elseExpr(), SS, Prec_Other); - } - - void printLet(const Let *E, StreamType &SS) { - SS << "let "; - printVariable(E->variableDecl(), SS, true); - SS << " = "; - printSExpr(E->variableDecl()->definition(), SS, Prec_Decl-1); - SS << "; "; - printSExpr(E->body(), SS, Prec_Decl-1); - } -}; - - -class StdPrinter : public PrettyPrinter<StdPrinter, std::ostream> { }; - - - -} // end namespace til -} // end namespace threadSafety -} // end namespace clang - -#endif // LLVM_CLANG_THREAD_SAFETY_TRAVERSE_H diff --git a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/include/clang/Analysis/Analyses/ThreadSafetyUtil.h deleted file mode 100644 index 4d3402f..0000000 --- a/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ /dev/null @@ -1,358 +0,0 @@ -//===- ThreadSafetyUtil.h --------------------------------------*- C++ --*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines some basic utility classes for use by ThreadSafetyTIL.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 <cassert> -#include <cstddef> -#include <ostream> -#include <utility> -#include <vector> - -namespace clang { -namespace threadSafety { -namespace til { - -// Simple wrapper class to abstract away from the details of memory management. -// SExprs are allocated in pools, and deallocated all at once. -class MemRegionRef { -private: - union AlignmentType { - double d; - void *p; - long double dd; - long long ii; - }; - -public: - MemRegionRef() : Allocator(nullptr) {} - MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} - - void *allocate(size_t Sz) { - return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment); - } - - template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } - - template <typename T> T *allocateT(size_t NumElems) { - return Allocator->Allocate<T>(NumElems); - } - -private: - llvm::BumpPtrAllocator *Allocator; -}; - - -} // end namespace til -} // end namespace threadSafety -} // end namespace clang - - -inline void *operator new(size_t Sz, - clang::threadSafety::til::MemRegionRef &R) { - return R.allocate(Sz); -} - - -namespace clang { -namespace threadSafety { - -std::string getSourceLiteralString(const clang::Expr *CE); - -using llvm::StringRef; -using clang::SourceLocation; - -namespace til { - - -// A simple fixed size array class that does not manage its own memory, -// suitable for use with bump pointer allocation. -template <class T> class SimpleArray { -public: - SimpleArray() : Data(nullptr), Size(0), Capacity(0) {} - SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) - : Data(Dat), Size(Sz), Capacity(Cp) {} - SimpleArray(MemRegionRef A, size_t Cp) - : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {} - SimpleArray(SimpleArray<T> &&A) - : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { - A.Data = nullptr; - A.Size = 0; - A.Capacity = 0; - } - - SimpleArray &operator=(SimpleArray &&RHS) { - if (this != &RHS) { - Data = RHS.Data; - Size = RHS.Size; - Capacity = RHS.Capacity; - - RHS.Data = nullptr; - RHS.Size = RHS.Capacity = 0; - } - return *this; - } - - // Reserve space for at least Ncp items, reallocating if necessary. - void reserve(size_t Ncp, MemRegionRef A) { - if (Ncp <= Capacity) - return; - T *Odata = Data; - Data = A.allocateT<T>(Ncp); - Capacity = Ncp; - memcpy(Data, Odata, sizeof(T) * Size); - return; - } - - // Reserve space for at least N more items. - void reserveCheck(size_t N, MemRegionRef A) { - if (Capacity == 0) - reserve(u_max(InitialCapacity, N), A); - else if (Size + N < Capacity) - reserve(u_max(Size + N, Capacity * 2), A); - } - - typedef T *iterator; - typedef const T *const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - - size_t size() const { return Size; } - size_t capacity() const { return Capacity; } - - T &operator[](unsigned i) { - assert(i < Size && "Array index out of bounds."); - return Data[i]; - } - const T &operator[](unsigned i) const { - 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; } - - 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; } - - reverse_iterator rbegin() { return reverse_iterator(end()); } - reverse_iterator rend() { return reverse_iterator(begin()); } - - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - - 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; - for (unsigned i = 0; i < Sz; ++i) { - Data[i] = C; - } - } - - template <class Iter> unsigned append(Iter I, Iter E) { - size_t Osz = Size; - size_t J = Osz; - for (; J < Capacity && I != E; ++J, ++I) - Data[J] = *I; - Size = J; - return J - Osz; - } - - llvm::iterator_range<reverse_iterator> reverse() { - return llvm::make_range(rbegin(), rend()); - } - llvm::iterator_range<const_reverse_iterator> reverse() const { - return llvm::make_range(rbegin(), rend()); - } - -private: - // std::max is annoying here, because it requires a reference, - // thus forcing InitialCapacity to be initialized outside the .h file. - size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; } - - static const size_t InitialCapacity = 4; - - SimpleArray(const SimpleArray<T> &A) = delete; - - T *Data; - size_t Size; - size_t Capacity; -}; - - -} // end namespace til - - -// A copy on write vector. -// The vector can be in one of three states: -// * invalid -- no operations are permitted. -// * read-only -- read operations are permitted. -// * writable -- read and write operations are permitted. -// The init(), destroy(), and makeWritable() methods will change state. -template<typename T> -class CopyOnWriteVector { - class VectorData { - public: - VectorData() : NumRefs(1) { } - VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { } - - unsigned NumRefs; - std::vector<T> Vect; - }; - - // No copy constructor or copy assignment. Use clone() with move assignment. - CopyOnWriteVector(const CopyOnWriteVector &V) = delete; - void operator=(const CopyOnWriteVector &V) = delete; - -public: - CopyOnWriteVector() : Data(nullptr) {} - CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } - ~CopyOnWriteVector() { destroy(); } - - // Returns true if this holds a valid vector. - bool valid() const { return Data; } - - // Returns true if this vector is writable. - bool writable() const { return Data && Data->NumRefs == 1; } - - // If this vector is not valid, initialize it to a valid vector. - void init() { - if (!Data) { - Data = new VectorData(); - } - } - - // Destroy this vector; thus making it invalid. - void destroy() { - if (!Data) - return; - if (Data->NumRefs <= 1) - delete Data; - else - --Data->NumRefs; - Data = nullptr; - } - - // Make this vector writable, creating a copy if needed. - void makeWritable() { - if (!Data) { - Data = new VectorData(); - return; - } - if (Data->NumRefs == 1) - return; // already writeable. - --Data->NumRefs; - Data = new VectorData(*Data); - } - - // Create a lazy copy of this vector. - CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } - - CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { - destroy(); - Data = V.Data; - V.Data = nullptr; - return *this; - } - - typedef typename std::vector<T>::const_iterator const_iterator; - - const std::vector<T> &elements() const { return Data->Vect; } - - const_iterator begin() const { return elements().cbegin(); } - const_iterator end() const { return elements().cend(); } - - const T& operator[](unsigned i) const { return elements()[i]; } - - unsigned size() const { return Data ? elements().size() : 0; } - - // Return true if V and this vector refer to the same data. - bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; } - - // Clear vector. The vector must be writable. - void clear() { - assert(writable() && "Vector is not writable!"); - Data->Vect.clear(); - } - - // Push a new element onto the end. The vector must be writable. - void push_back(const T &Elem) { - assert(writable() && "Vector is not writable!"); - Data->Vect.push_back(Elem); - } - - // Gets a mutable reference to the element at index(i). - // The vector must be writable. - T& elem(unsigned i) { - assert(writable() && "Vector is not writable!"); - return Data->Vect[i]; - } - - // Drops elements from the back until the vector has size i. - void downsize(unsigned i) { - assert(writable() && "Vector is not writable!"); - Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); - } - -private: - CopyOnWriteVector(VectorData *D) : Data(D) { - if (!Data) - return; - ++Data->NumRefs; - } - - VectorData *Data; -}; - - -inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { - return ss.write(str.data(), str.size()); -} - - -} // end namespace threadSafety -} // end namespace clang - -#endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H diff --git a/include/clang/Analysis/Analyses/UninitializedValues.h b/include/clang/Analysis/Analyses/UninitializedValues.h deleted file mode 100644 index 53ff20c..0000000 --- a/include/clang/Analysis/Analyses/UninitializedValues.h +++ /dev/null @@ -1,126 +0,0 @@ -//= UninitializedValues.h - Finding uses of uninitialized values -*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines APIs for invoking and reported uninitialized values -// warnings. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H -#define LLVM_CLANG_ANALYSIS_ANALYSES_UNINITIALIZEDVALUES_H - -#include "clang/AST/Stmt.h" -#include "llvm/ADT/SmallVector.h" - -namespace clang { - -class AnalysisDeclContext; -class CFG; -class DeclContext; -class Expr; -class VarDecl; - -/// A use of a variable, which might be uninitialized. -class UninitUse { -public: - struct Branch { - const Stmt *Terminator; - unsigned Output; - }; - -private: - /// The expression which uses this variable. - const Expr *User; - - /// Is this use uninitialized whenever the function is called? - bool UninitAfterCall; - - /// Is this use uninitialized whenever the variable declaration is reached? - bool UninitAfterDecl; - - /// Does this use always see an uninitialized value? - bool AlwaysUninit; - - /// This use is always uninitialized if it occurs after any of these branches - /// is taken. - SmallVector<Branch, 2> UninitBranches; - -public: - UninitUse(const Expr *User, bool AlwaysUninit) - : User(User), UninitAfterCall(false), UninitAfterDecl(false), - AlwaysUninit(AlwaysUninit) {} - - void addUninitBranch(Branch B) { - UninitBranches.push_back(B); - } - - void setUninitAfterCall() { UninitAfterCall = true; } - void setUninitAfterDecl() { UninitAfterDecl = true; } - - /// Get the expression containing the uninitialized use. - const Expr *getUser() const { return User; } - - /// The kind of uninitialized use. - enum Kind { - /// The use might be uninitialized. - Maybe, - /// The use is uninitialized whenever a certain branch is taken. - Sometimes, - /// The use is uninitialized the first time it is reached after we reach - /// the variable's declaration. - AfterDecl, - /// The use is uninitialized the first time it is reached after the function - /// is called. - AfterCall, - /// The use is always uninitialized. - Always - }; - - /// Get the kind of uninitialized use. - Kind getKind() const { - return AlwaysUninit ? Always : - UninitAfterCall ? AfterCall : - UninitAfterDecl ? AfterDecl : - !branch_empty() ? Sometimes : Maybe; - } - - typedef SmallVectorImpl<Branch>::const_iterator branch_iterator; - /// Branches which inevitably result in the variable being used uninitialized. - branch_iterator branch_begin() const { return UninitBranches.begin(); } - branch_iterator branch_end() const { return UninitBranches.end(); } - bool branch_empty() const { return UninitBranches.empty(); } -}; - -class UninitVariablesHandler { -public: - UninitVariablesHandler() {} - virtual ~UninitVariablesHandler(); - - /// Called when the uninitialized variable is used at the given expression. - virtual void handleUseOfUninitVariable(const VarDecl *vd, - const UninitUse &use) {} - - /// Called when the uninitialized variable analysis detects the - /// idiom 'int x = x'. All other uses of 'x' within the initializer - /// are handled by handleUseOfUninitVariable. - virtual void handleSelfInit(const VarDecl *vd) {} -}; - -struct UninitVariablesAnalysisStats { - unsigned NumVariablesAnalyzed; - unsigned NumBlockVisits; -}; - -void runUninitializedVariablesAnalysis(const DeclContext &dc, const CFG &cfg, - AnalysisDeclContext &ac, - UninitVariablesHandler &handler, - UninitVariablesAnalysisStats &stats); - -} -#endif |
