diff options
Diffstat (limited to 'include/clang/Analysis')
27 files changed, 0 insertions, 8939 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 diff --git a/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h deleted file mode 100644 index 931190e..0000000 --- a/include/clang/Analysis/AnalysisContext.h +++ /dev/null @@ -1,480 +0,0 @@ -//=== AnalysisContext.h - Analysis context for Path Sens 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 AnalysisDeclContext, a class that manages the analysis -// context data for path sensitive analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H -#define LLVM_CLANG_ANALYSIS_ANALYSISCONTEXT_H - -#include "clang/AST/Decl.h" -#include "clang/Analysis/CFG.h" -#include "clang/Analysis/CodeInjector.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/Support/Allocator.h" -#include <memory> - -namespace clang { - -class Stmt; -class CFGReverseBlockReachabilityAnalysis; -class CFGStmtMap; -class LiveVariables; -class ManagedAnalysis; -class ParentMap; -class PseudoConstantAnalysis; -class LocationContextManager; -class StackFrameContext; -class BlockInvocationContext; -class AnalysisDeclContextManager; -class LocationContext; - -namespace idx { class TranslationUnit; } - -/// The base class of a hierarchy of objects representing analyses tied -/// to AnalysisDeclContext. -class ManagedAnalysis { -protected: - ManagedAnalysis() {} -public: - virtual ~ManagedAnalysis(); - - // Subclasses need to implement: - // - // static const void *getTag(); - // - // Which returns a fixed pointer address to distinguish classes of - // analysis objects. They also need to implement: - // - // static [Derived*] create(AnalysisDeclContext &Ctx); - // - // which creates the analysis object given an AnalysisDeclContext. -}; - - -/// AnalysisDeclContext contains the context data for the function or method -/// under analysis. -class AnalysisDeclContext { - /// Backpoint to the AnalysisManager object that created this - /// AnalysisDeclContext. This may be null. - AnalysisDeclContextManager *Manager; - - const Decl * const D; - - std::unique_ptr<CFG> cfg, completeCFG; - std::unique_ptr<CFGStmtMap> cfgStmtMap; - - CFG::BuildOptions cfgBuildOptions; - CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; - - bool builtCFG, builtCompleteCFG; - std::unique_ptr<ParentMap> PM; - std::unique_ptr<PseudoConstantAnalysis> PCA; - std::unique_ptr<CFGReverseBlockReachabilityAnalysis> CFA; - - llvm::BumpPtrAllocator A; - - llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; - - void *ManagedAnalyses; - -public: - AnalysisDeclContext(AnalysisDeclContextManager *Mgr, - const Decl *D); - - AnalysisDeclContext(AnalysisDeclContextManager *Mgr, - const Decl *D, - const CFG::BuildOptions &BuildOptions); - - ~AnalysisDeclContext(); - - ASTContext &getASTContext() const { return D->getASTContext(); } - const Decl *getDecl() const { return D; } - - /// Return the AnalysisDeclContextManager (if any) that created - /// this AnalysisDeclContext. - AnalysisDeclContextManager *getManager() const { - return Manager; - } - - /// Return the build options used to construct the CFG. - CFG::BuildOptions &getCFGBuildOptions() { - return cfgBuildOptions; - } - - const CFG::BuildOptions &getCFGBuildOptions() const { - return cfgBuildOptions; - } - - /// getAddEHEdges - Return true iff we are adding exceptional edges from - /// callExprs. If this is false, then try/catch statements and blocks - /// reachable from them can appear to be dead in the CFG, analysis passes must - /// cope with that. - bool getAddEHEdges() const { return cfgBuildOptions.AddEHEdges; } - bool getUseUnoptimizedCFG() const { - return !cfgBuildOptions.PruneTriviallyFalseEdges; - } - bool getAddImplicitDtors() const { return cfgBuildOptions.AddImplicitDtors; } - bool getAddInitializers() const { return cfgBuildOptions.AddInitializers; } - - void registerForcedBlockExpression(const Stmt *stmt); - const CFGBlock *getBlockForRegisteredExpression(const Stmt *stmt); - - /// \brief Get the body of the Declaration. - Stmt *getBody() const; - - /// \brief Get the body of the Declaration. - /// \param[out] IsAutosynthesized Specifies if the body is auto-generated - /// by the BodyFarm. - Stmt *getBody(bool &IsAutosynthesized) const; - - /// \brief Checks if the body of the Decl is generated by the BodyFarm. - /// - /// Note, the lookup is not free. We are going to call getBody behind - /// the scenes. - /// \sa getBody - bool isBodyAutosynthesized() const; - - /// \brief Checks if the body of the Decl is generated by the BodyFarm from a - /// model file. - /// - /// Note, the lookup is not free. We are going to call getBody behind - /// the scenes. - /// \sa getBody - bool isBodyAutosynthesizedFromModelFile() const; - - CFG *getCFG(); - - CFGStmtMap *getCFGStmtMap(); - - CFGReverseBlockReachabilityAnalysis *getCFGReachablityAnalysis(); - - /// Return a version of the CFG without any edges pruned. - CFG *getUnoptimizedCFG(); - - void dumpCFG(bool ShowColors); - - /// \brief Returns true if we have built a CFG for this analysis context. - /// Note that this doesn't correspond to whether or not a valid CFG exists, it - /// corresponds to whether we *attempted* to build one. - bool isCFGBuilt() const { return builtCFG; } - - ParentMap &getParentMap(); - PseudoConstantAnalysis *getPseudoConstantAnalysis(); - - typedef const VarDecl * const * referenced_decls_iterator; - - llvm::iterator_range<referenced_decls_iterator> - getReferencedBlockVars(const BlockDecl *BD); - - /// Return the ImplicitParamDecl* associated with 'self' if this - /// AnalysisDeclContext wraps an ObjCMethodDecl. Returns NULL otherwise. - const ImplicitParamDecl *getSelfDecl() const; - - const StackFrameContext *getStackFrame(LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx); - - const BlockInvocationContext * - getBlockInvocationContext(const LocationContext *parent, - const BlockDecl *BD, - const void *ContextData); - - /// Return the specified analysis object, lazily running the analysis if - /// necessary. Return NULL if the analysis could not run. - template <typename T> - T *getAnalysis() { - const void *tag = T::getTag(); - ManagedAnalysis *&data = getAnalysisImpl(tag); - if (!data) { - data = T::create(*this); - } - return static_cast<T*>(data); - } -private: - ManagedAnalysis *&getAnalysisImpl(const void* tag); - - LocationContextManager &getLocationContextManager(); -}; - -class LocationContext : public llvm::FoldingSetNode { -public: - enum ContextKind { StackFrame, Scope, Block }; - -private: - ContextKind Kind; - - // AnalysisDeclContext can't be const since some methods may modify its - // member. - AnalysisDeclContext *Ctx; - - const LocationContext *Parent; - -protected: - LocationContext(ContextKind k, AnalysisDeclContext *ctx, - const LocationContext *parent) - : Kind(k), Ctx(ctx), Parent(parent) {} - -public: - virtual ~LocationContext(); - - ContextKind getKind() const { return Kind; } - - AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } - - const LocationContext *getParent() const { return Parent; } - - bool isParentOf(const LocationContext *LC) const; - - const Decl *getDecl() const { return getAnalysisDeclContext()->getDecl(); } - - CFG *getCFG() const { return getAnalysisDeclContext()->getCFG(); } - - template <typename T> - T *getAnalysis() const { - return getAnalysisDeclContext()->getAnalysis<T>(); - } - - ParentMap &getParentMap() const { - return getAnalysisDeclContext()->getParentMap(); - } - - const ImplicitParamDecl *getSelfDecl() const { - return Ctx->getSelfDecl(); - } - - const StackFrameContext *getCurrentStackFrame() const; - - /// Return true if the current LocationContext has no caller context. - virtual bool inTopFrame() const; - - virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; - - void dumpStack(raw_ostream &OS, StringRef Indent = "") const; - void dumpStack() const; - -public: - static void ProfileCommon(llvm::FoldingSetNodeID &ID, - ContextKind ck, - AnalysisDeclContext *ctx, - const LocationContext *parent, - const void *data); -}; - -class StackFrameContext : public LocationContext { - // The callsite where this stack frame is established. - const Stmt *CallSite; - - // The parent block of the callsite. - const CFGBlock *Block; - - // The index of the callsite in the CFGBlock. - unsigned Index; - - friend class LocationContextManager; - StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, - const Stmt *s, const CFGBlock *blk, - unsigned idx) - : LocationContext(StackFrame, ctx, parent), CallSite(s), - Block(blk), Index(idx) {} - -public: - ~StackFrameContext() override {} - - const Stmt *getCallSite() const { return CallSite; } - - const CFGBlock *getCallSiteBlock() const { return Block; } - - /// Return true if the current LocationContext has no caller context. - bool inTopFrame() const override { return getParent() == nullptr; } - - unsigned getIndex() const { return Index; } - - void Profile(llvm::FoldingSetNodeID &ID) override; - - static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, - const LocationContext *parent, const Stmt *s, - const CFGBlock *blk, unsigned idx) { - ProfileCommon(ID, StackFrame, ctx, parent, s); - ID.AddPointer(blk); - ID.AddInteger(idx); - } - - static bool classof(const LocationContext *Ctx) { - return Ctx->getKind() == StackFrame; - } -}; - -class ScopeContext : public LocationContext { - const Stmt *Enter; - - friend class LocationContextManager; - ScopeContext(AnalysisDeclContext *ctx, const LocationContext *parent, - const Stmt *s) - : LocationContext(Scope, ctx, parent), Enter(s) {} - -public: - ~ScopeContext() override {} - - void Profile(llvm::FoldingSetNodeID &ID) override; - - static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, - const LocationContext *parent, const Stmt *s) { - ProfileCommon(ID, Scope, ctx, parent, s); - } - - static bool classof(const LocationContext *Ctx) { - return Ctx->getKind() == Scope; - } -}; - -class BlockInvocationContext : public LocationContext { - const BlockDecl *BD; - - // FIXME: Come up with a more type-safe way to model context-sensitivity. - const void *ContextData; - - friend class LocationContextManager; - - BlockInvocationContext(AnalysisDeclContext *ctx, - const LocationContext *parent, - const BlockDecl *bd, const void *contextData) - : LocationContext(Block, ctx, parent), BD(bd), ContextData(contextData) {} - -public: - ~BlockInvocationContext() override {} - - const BlockDecl *getBlockDecl() const { return BD; } - - const void *getContextData() const { return ContextData; } - - void Profile(llvm::FoldingSetNodeID &ID) override; - - static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, - const LocationContext *parent, const BlockDecl *bd, - const void *contextData) { - ProfileCommon(ID, Block, ctx, parent, bd); - ID.AddPointer(contextData); - } - - static bool classof(const LocationContext *Ctx) { - return Ctx->getKind() == Block; - } -}; - -class LocationContextManager { - llvm::FoldingSet<LocationContext> Contexts; -public: - ~LocationContextManager(); - - const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, - const LocationContext *parent, - const Stmt *s, - const CFGBlock *blk, unsigned idx); - - const ScopeContext *getScope(AnalysisDeclContext *ctx, - const LocationContext *parent, - const Stmt *s); - - const BlockInvocationContext * - getBlockInvocationContext(AnalysisDeclContext *ctx, - const LocationContext *parent, - const BlockDecl *BD, - const void *ContextData); - - /// Discard all previously created LocationContext objects. - void clear(); -private: - template <typename LOC, typename DATA> - const LOC *getLocationContext(AnalysisDeclContext *ctx, - const LocationContext *parent, - const DATA *d); -}; - -class AnalysisDeclContextManager { - typedef llvm::DenseMap<const Decl*, AnalysisDeclContext*> ContextMap; - - ContextMap Contexts; - LocationContextManager LocContexts; - CFG::BuildOptions cfgBuildOptions; - - /// Pointer to an interface that can provide function bodies for - /// declarations from external source. - std::unique_ptr<CodeInjector> Injector; - - /// Flag to indicate whether or not bodies should be synthesized - /// for well-known functions. - bool SynthesizeBodies; - -public: - AnalysisDeclContextManager(bool useUnoptimizedCFG = false, - bool addImplicitDtors = false, - bool addInitializers = false, - bool addTemporaryDtors = false, - bool synthesizeBodies = false, - bool addStaticInitBranches = false, - bool addCXXNewAllocator = true, - CodeInjector* injector = nullptr); - - ~AnalysisDeclContextManager(); - - AnalysisDeclContext *getContext(const Decl *D); - - bool getUseUnoptimizedCFG() const { - return !cfgBuildOptions.PruneTriviallyFalseEdges; - } - - CFG::BuildOptions &getCFGBuildOptions() { - return cfgBuildOptions; - } - - /// Return true if faux bodies should be synthesized for well-known - /// functions. - bool synthesizeBodies() const { return SynthesizeBodies; } - - const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, - LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx) { - return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); - } - - // Get the top level stack frame. - const StackFrameContext *getStackFrame(const Decl *D) { - return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr, - 0); - } - - // Get a stack frame with parent. - StackFrameContext const *getStackFrame(const Decl *D, - LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx) { - return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); - } - - /// Discard all previously created AnalysisDeclContexts. - void clear(); - -private: - friend class AnalysisDeclContext; - - LocationContextManager &getLocationContextManager() { - return LocContexts; - } -}; - -} // end clang namespace -#endif diff --git a/include/clang/Analysis/AnalysisDiagnostic.h b/include/clang/Analysis/AnalysisDiagnostic.h deleted file mode 100644 index 8d28971..0000000 --- a/include/clang/Analysis/AnalysisDiagnostic.h +++ /dev/null @@ -1,28 +0,0 @@ -//===--- DiagnosticAnalysis.h - Diagnostics for libanalysis -----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H -#define LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H - -#include "clang/Basic/Diagnostic.h" - -namespace clang { - namespace diag { - enum { -#define DIAG(ENUM,FLAGS,DEFAULT_MAPPING,DESC,GROUP,\ - SFINAE,NOWERROR,SHOWINSYSHEADER,CATEGORY) ENUM, -#define ANALYSISSTART -#include "clang/Basic/DiagnosticAnalysisKinds.inc" -#undef DIAG - NUM_BUILTIN_ANALYSIS_DIAGNOSTICS - }; - } // end namespace diag -} // end namespace clang - -#endif diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h deleted file mode 100644 index 293990c..0000000 --- a/include/clang/Analysis/CFG.h +++ /dev/null @@ -1,1113 +0,0 @@ -//===--- CFG.h - Classes for representing and building 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 defines the CFG and CFGBuilder classes for representing and -// building Control-Flow Graphs (CFGs) from ASTs. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_CFG_H -#define LLVM_CLANG_ANALYSIS_CFG_H - -#include "clang/AST/Stmt.h" -#include "clang/Analysis/Support/BumpVector.h" -#include "clang/Basic/SourceLocation.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/raw_ostream.h" -#include <bitset> -#include <cassert> -#include <iterator> -#include <memory> - -namespace clang { - class CXXDestructorDecl; - class Decl; - class Stmt; - class Expr; - class FieldDecl; - class VarDecl; - class CXXCtorInitializer; - class CXXBaseSpecifier; - class CXXBindTemporaryExpr; - class CFG; - class PrinterHelper; - class LangOptions; - class ASTContext; - class CXXRecordDecl; - class CXXDeleteExpr; - class CXXNewExpr; - class BinaryOperator; - -/// CFGElement - Represents a top-level expression in a basic block. -class CFGElement { -public: - enum Kind { - // main kind - Statement, - Initializer, - NewAllocator, - // dtor kind - AutomaticObjectDtor, - DeleteDtor, - BaseDtor, - MemberDtor, - TemporaryDtor, - DTOR_BEGIN = AutomaticObjectDtor, - DTOR_END = TemporaryDtor - }; - -protected: - // The int bits are used to mark the kind. - llvm::PointerIntPair<void *, 2> Data1; - llvm::PointerIntPair<void *, 2> Data2; - - CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr) - : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), - Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) { - assert(getKind() == kind); - } - - CFGElement() {} -public: - - /// \brief Convert to the specified CFGElement type, asserting that this - /// CFGElement is of the desired type. - template<typename T> - T castAs() const { - assert(T::isKind(*this)); - T t; - CFGElement& e = t; - e = *this; - return t; - } - - /// \brief Convert to the specified CFGElement type, returning None if this - /// CFGElement is not of the desired type. - template<typename T> - Optional<T> getAs() const { - if (!T::isKind(*this)) - return None; - T t; - CFGElement& e = t; - e = *this; - return t; - } - - Kind getKind() const { - unsigned x = Data2.getInt(); - x <<= 2; - x |= Data1.getInt(); - return (Kind) x; - } -}; - -class CFGStmt : public CFGElement { -public: - CFGStmt(Stmt *S) : CFGElement(Statement, S) {} - - const Stmt *getStmt() const { - return static_cast<const Stmt *>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGStmt() {} - static bool isKind(const CFGElement &E) { - return E.getKind() == Statement; - } -}; - -/// CFGInitializer - Represents C++ base or member initializer from -/// constructor's initialization list. -class CFGInitializer : public CFGElement { -public: - CFGInitializer(CXXCtorInitializer *initializer) - : CFGElement(Initializer, initializer) {} - - CXXCtorInitializer* getInitializer() const { - return static_cast<CXXCtorInitializer*>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGInitializer() {} - static bool isKind(const CFGElement &E) { - return E.getKind() == Initializer; - } -}; - -/// CFGNewAllocator - Represents C++ allocator call. -class CFGNewAllocator : public CFGElement { -public: - explicit CFGNewAllocator(const CXXNewExpr *S) - : CFGElement(NewAllocator, S) {} - - // Get the new expression. - const CXXNewExpr *getAllocatorExpr() const { - return static_cast<CXXNewExpr *>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGNewAllocator() {} - static bool isKind(const CFGElement &elem) { - return elem.getKind() == NewAllocator; - } -}; - -/// CFGImplicitDtor - Represents C++ object destructor implicitly generated -/// by compiler on various occasions. -class CFGImplicitDtor : public CFGElement { -protected: - CFGImplicitDtor() {} - CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) - : CFGElement(kind, data1, data2) { - assert(kind >= DTOR_BEGIN && kind <= DTOR_END); - } - -public: - const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; - bool isNoReturn(ASTContext &astContext) const; - -private: - friend class CFGElement; - static bool isKind(const CFGElement &E) { - Kind kind = E.getKind(); - return kind >= DTOR_BEGIN && kind <= DTOR_END; - } -}; - -/// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated -/// for automatic object or temporary bound to const reference at the point -/// of leaving its local scope. -class CFGAutomaticObjDtor: public CFGImplicitDtor { -public: - CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) - : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} - - const VarDecl *getVarDecl() const { - return static_cast<VarDecl*>(Data1.getPointer()); - } - - // Get statement end of which triggered the destructor call. - const Stmt *getTriggerStmt() const { - return static_cast<Stmt*>(Data2.getPointer()); - } - -private: - friend class CFGElement; - CFGAutomaticObjDtor() {} - static bool isKind(const CFGElement &elem) { - return elem.getKind() == AutomaticObjectDtor; - } -}; - -/// CFGDeleteDtor - Represents C++ object destructor generated -/// from a call to delete. -class CFGDeleteDtor : public CFGImplicitDtor { -public: - CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) - : CFGImplicitDtor(DeleteDtor, RD, DE) {} - - const CXXRecordDecl *getCXXRecordDecl() const { - return static_cast<CXXRecordDecl*>(Data1.getPointer()); - } - - // Get Delete expression which triggered the destructor call. - const CXXDeleteExpr *getDeleteExpr() const { - return static_cast<CXXDeleteExpr *>(Data2.getPointer()); - } - -private: - friend class CFGElement; - CFGDeleteDtor() {} - static bool isKind(const CFGElement &elem) { - return elem.getKind() == DeleteDtor; - } -}; - -/// CFGBaseDtor - Represents C++ object destructor implicitly generated for -/// base object in destructor. -class CFGBaseDtor : public CFGImplicitDtor { -public: - CFGBaseDtor(const CXXBaseSpecifier *base) - : CFGImplicitDtor(BaseDtor, base) {} - - const CXXBaseSpecifier *getBaseSpecifier() const { - return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGBaseDtor() {} - static bool isKind(const CFGElement &E) { - return E.getKind() == BaseDtor; - } -}; - -/// CFGMemberDtor - Represents C++ object destructor implicitly generated for -/// member object in destructor. -class CFGMemberDtor : public CFGImplicitDtor { -public: - CFGMemberDtor(const FieldDecl *field) - : CFGImplicitDtor(MemberDtor, field, nullptr) {} - - const FieldDecl *getFieldDecl() const { - return static_cast<const FieldDecl*>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGMemberDtor() {} - static bool isKind(const CFGElement &E) { - return E.getKind() == MemberDtor; - } -}; - -/// CFGTemporaryDtor - Represents C++ object destructor implicitly generated -/// at the end of full expression for temporary object. -class CFGTemporaryDtor : public CFGImplicitDtor { -public: - CFGTemporaryDtor(CXXBindTemporaryExpr *expr) - : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} - - const CXXBindTemporaryExpr *getBindTemporaryExpr() const { - return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); - } - -private: - friend class CFGElement; - CFGTemporaryDtor() {} - static bool isKind(const CFGElement &E) { - return E.getKind() == TemporaryDtor; - } -}; - -/// CFGTerminator - Represents CFGBlock terminator statement. -/// -/// TemporaryDtorsBranch bit is set to true if the terminator marks a branch -/// in control flow of destructors of temporaries. In this case terminator -/// statement is the same statement that branches control flow in evaluation -/// of matching full expression. -class CFGTerminator { - llvm::PointerIntPair<Stmt *, 1> Data; -public: - CFGTerminator() {} - CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false) - : Data(S, TemporaryDtorsBranch) {} - - Stmt *getStmt() { return Data.getPointer(); } - const Stmt *getStmt() const { return Data.getPointer(); } - - bool isTemporaryDtorsBranch() const { return Data.getInt(); } - - operator Stmt *() { return getStmt(); } - operator const Stmt *() const { return getStmt(); } - - Stmt *operator->() { return getStmt(); } - const Stmt *operator->() const { return getStmt(); } - - Stmt &operator*() { return *getStmt(); } - const Stmt &operator*() const { return *getStmt(); } - - explicit operator bool() const { return getStmt(); } -}; - -/// CFGBlock - Represents a single basic block in a source-level CFG. -/// It consists of: -/// -/// (1) A set of statements/expressions (which may contain subexpressions). -/// (2) A "terminator" statement (not in the set of statements). -/// (3) A list of successors and predecessors. -/// -/// Terminator: The terminator represents the type of control-flow that occurs -/// at the end of the basic block. The terminator is a Stmt* referring to an -/// AST node that has control-flow: if-statements, breaks, loops, etc. -/// If the control-flow is conditional, the condition expression will appear -/// within the set of statements in the block (usually the last statement). -/// -/// Predecessors: the order in the set of predecessors is arbitrary. -/// -/// Successors: the order in the set of successors is NOT arbitrary. We -/// currently have the following orderings based on the terminator: -/// -/// Terminator Successor Ordering -/// ----------------------------------------------------- -/// if Then Block; Else Block -/// ? operator LHS expression; RHS expression -/// &&, || expression that uses result of && or ||, RHS -/// -/// But note that any of that may be NULL in case of optimized-out edges. -/// -class CFGBlock { - class ElementList { - typedef BumpVector<CFGElement> ImplTy; - ImplTy Impl; - public: - ElementList(BumpVectorContext &C) : Impl(C, 4) {} - - typedef std::reverse_iterator<ImplTy::iterator> iterator; - typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator; - typedef ImplTy::iterator reverse_iterator; - typedef ImplTy::const_iterator const_reverse_iterator; - typedef ImplTy::const_reference const_reference; - - void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } - reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, - BumpVectorContext &C) { - return Impl.insert(I, Cnt, E, C); - } - - const_reference front() const { return Impl.back(); } - const_reference back() const { return Impl.front(); } - - iterator begin() { return Impl.rbegin(); } - iterator end() { return Impl.rend(); } - const_iterator begin() const { return Impl.rbegin(); } - const_iterator end() const { return Impl.rend(); } - reverse_iterator rbegin() { return Impl.begin(); } - reverse_iterator rend() { return Impl.end(); } - const_reverse_iterator rbegin() const { return Impl.begin(); } - const_reverse_iterator rend() const { return Impl.end(); } - - CFGElement operator[](size_t i) const { - assert(i < Impl.size()); - return Impl[Impl.size() - 1 - i]; - } - - size_t size() const { return Impl.size(); } - bool empty() const { return Impl.empty(); } - }; - - /// Stmts - The set of statements in the basic block. - ElementList Elements; - - /// Label - An (optional) label that prefixes the executable - /// statements in the block. When this variable is non-NULL, it is - /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt. - Stmt *Label; - - /// Terminator - The terminator for a basic block that - /// indicates the type of control-flow that occurs between a block - /// and its successors. - CFGTerminator Terminator; - - /// LoopTarget - Some blocks are used to represent the "loop edge" to - /// the start of a loop from within the loop body. This Stmt* will be - /// refer to the loop statement for such blocks (and be null otherwise). - const Stmt *LoopTarget; - - /// BlockID - A numerical ID assigned to a CFGBlock during construction - /// of the CFG. - unsigned BlockID; - -public: - /// This class represents a potential adjacent block in the CFG. It encodes - /// whether or not the block is actually reachable, or can be proved to be - /// trivially unreachable. For some cases it allows one to encode scenarios - /// where a block was substituted because the original (now alternate) block - /// is unreachable. - class AdjacentBlock { - enum Kind { - AB_Normal, - AB_Unreachable, - AB_Alternate - }; - - CFGBlock *ReachableBlock; - llvm::PointerIntPair<CFGBlock*, 2> UnreachableBlock; - - public: - /// Construct an AdjacentBlock with a possibly unreachable block. - AdjacentBlock(CFGBlock *B, bool IsReachable); - - /// Construct an AdjacentBlock with a reachable block and an alternate - /// unreachable block. - AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock); - - /// Get the reachable block, if one exists. - CFGBlock *getReachableBlock() const { - return ReachableBlock; - } - - /// Get the potentially unreachable block. - CFGBlock *getPossiblyUnreachableBlock() const { - return UnreachableBlock.getPointer(); - } - - /// Provide an implicit conversion to CFGBlock* so that - /// AdjacentBlock can be substituted for CFGBlock*. - operator CFGBlock*() const { - return getReachableBlock(); - } - - CFGBlock& operator *() const { - return *getReachableBlock(); - } - - CFGBlock* operator ->() const { - return getReachableBlock(); - } - - bool isReachable() const { - Kind K = (Kind) UnreachableBlock.getInt(); - return K == AB_Normal || K == AB_Alternate; - } - }; - -private: - /// Predecessors/Successors - Keep track of the predecessor / successor - /// CFG blocks. - typedef BumpVector<AdjacentBlock> AdjacentBlocks; - AdjacentBlocks Preds; - AdjacentBlocks Succs; - - /// NoReturn - This bit is set when the basic block contains a function call - /// or implicit destructor that is attributed as 'noreturn'. In that case, - /// control cannot technically ever proceed past this block. All such blocks - /// will have a single immediate successor: the exit block. This allows them - /// to be easily reached from the exit block and using this bit quickly - /// recognized without scanning the contents of the block. - /// - /// Optimization Note: This bit could be profitably folded with Terminator's - /// storage if the memory usage of CFGBlock becomes an issue. - unsigned HasNoReturnElement : 1; - - /// Parent - The parent CFG that owns this CFGBlock. - CFG *Parent; - -public: - explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) - : Elements(C), Label(nullptr), Terminator(nullptr), LoopTarget(nullptr), - BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false), - Parent(parent) {} - - // Statement iterators - typedef ElementList::iterator iterator; - typedef ElementList::const_iterator const_iterator; - typedef ElementList::reverse_iterator reverse_iterator; - typedef ElementList::const_reverse_iterator const_reverse_iterator; - - CFGElement front() const { return Elements.front(); } - CFGElement back() const { return Elements.back(); } - - iterator begin() { return Elements.begin(); } - iterator end() { return Elements.end(); } - const_iterator begin() const { return Elements.begin(); } - const_iterator end() const { return Elements.end(); } - - reverse_iterator rbegin() { return Elements.rbegin(); } - reverse_iterator rend() { return Elements.rend(); } - const_reverse_iterator rbegin() const { return Elements.rbegin(); } - const_reverse_iterator rend() const { return Elements.rend(); } - - unsigned size() const { return Elements.size(); } - bool empty() const { return Elements.empty(); } - - CFGElement operator[](size_t i) const { return Elements[i]; } - - // CFG iterators - typedef AdjacentBlocks::iterator pred_iterator; - typedef AdjacentBlocks::const_iterator const_pred_iterator; - typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator; - typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator; - - typedef AdjacentBlocks::iterator succ_iterator; - typedef AdjacentBlocks::const_iterator const_succ_iterator; - typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator; - typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator; - - pred_iterator pred_begin() { return Preds.begin(); } - pred_iterator pred_end() { return Preds.end(); } - const_pred_iterator pred_begin() const { return Preds.begin(); } - const_pred_iterator pred_end() const { return Preds.end(); } - - pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } - pred_reverse_iterator pred_rend() { return Preds.rend(); } - const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } - const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } - - succ_iterator succ_begin() { return Succs.begin(); } - succ_iterator succ_end() { return Succs.end(); } - const_succ_iterator succ_begin() const { return Succs.begin(); } - const_succ_iterator succ_end() const { return Succs.end(); } - - succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } - succ_reverse_iterator succ_rend() { return Succs.rend(); } - const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } - const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } - - unsigned succ_size() const { return Succs.size(); } - bool succ_empty() const { return Succs.empty(); } - - unsigned pred_size() const { return Preds.size(); } - bool pred_empty() const { return Preds.empty(); } - - - class FilterOptions { - public: - FilterOptions() { - IgnoreNullPredecessors = 1; - IgnoreDefaultsWithCoveredEnums = 0; - } - - unsigned IgnoreNullPredecessors : 1; - unsigned IgnoreDefaultsWithCoveredEnums : 1; - }; - - static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, - const CFGBlock *Dst); - - template <typename IMPL, bool IsPred> - class FilteredCFGBlockIterator { - private: - IMPL I, E; - const FilterOptions F; - const CFGBlock *From; - public: - explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, - const CFGBlock *from, - const FilterOptions &f) - : I(i), E(e), F(f), From(from) { - while (hasMore() && Filter(*I)) - ++I; - } - - bool hasMore() const { return I != E; } - - FilteredCFGBlockIterator &operator++() { - do { ++I; } while (hasMore() && Filter(*I)); - return *this; - } - - const CFGBlock *operator*() const { return *I; } - private: - bool Filter(const CFGBlock *To) { - return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To); - } - }; - - typedef FilteredCFGBlockIterator<const_pred_iterator, true> - filtered_pred_iterator; - - typedef FilteredCFGBlockIterator<const_succ_iterator, false> - filtered_succ_iterator; - - filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { - return filtered_pred_iterator(pred_begin(), pred_end(), this, f); - } - - filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { - return filtered_succ_iterator(succ_begin(), succ_end(), this, f); - } - - // Manipulation of block contents - - void setTerminator(CFGTerminator Term) { Terminator = Term; } - void setLabel(Stmt *Statement) { Label = Statement; } - void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } - void setHasNoReturnElement() { HasNoReturnElement = true; } - - CFGTerminator getTerminator() { return Terminator; } - const CFGTerminator getTerminator() const { return Terminator; } - - Stmt *getTerminatorCondition(bool StripParens = true); - - const Stmt *getTerminatorCondition(bool StripParens = true) const { - return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens); - } - - const Stmt *getLoopTarget() const { return LoopTarget; } - - Stmt *getLabel() { return Label; } - const Stmt *getLabel() const { return Label; } - - bool hasNoReturnElement() const { return HasNoReturnElement; } - - unsigned getBlockID() const { return BlockID; } - - CFG *getParent() const { return Parent; } - - void dump() const; - - void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; - void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, - bool ShowColors) const; - void printTerminator(raw_ostream &OS, const LangOptions &LO) const; - void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { - OS << "BB#" << getBlockID(); - } - - /// Adds a (potentially unreachable) successor block to the current block. - void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C); - - void appendStmt(Stmt *statement, BumpVectorContext &C) { - Elements.push_back(CFGStmt(statement), C); - } - - void appendInitializer(CXXCtorInitializer *initializer, - BumpVectorContext &C) { - Elements.push_back(CFGInitializer(initializer), C); - } - - void appendNewAllocator(CXXNewExpr *NE, - BumpVectorContext &C) { - Elements.push_back(CFGNewAllocator(NE), C); - } - - void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { - Elements.push_back(CFGBaseDtor(BS), C); - } - - void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { - Elements.push_back(CFGMemberDtor(FD), C); - } - - void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { - Elements.push_back(CFGTemporaryDtor(E), C); - } - - void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { - Elements.push_back(CFGAutomaticObjDtor(VD, S), C); - } - - void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { - Elements.push_back(CFGDeleteDtor(RD, DE), C); - } - - // Destructors must be inserted in reversed order. So insertion is in two - // steps. First we prepare space for some number of elements, then we insert - // the elements beginning at the last position in prepared space. - iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, - BumpVectorContext &C) { - return iterator(Elements.insert(I.base(), Cnt, - CFGAutomaticObjDtor(nullptr, nullptr), C)); - } - iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { - *I = CFGAutomaticObjDtor(VD, S); - return ++I; - } -}; - -/// \brief CFGCallback defines methods that should be called when a logical -/// operator error is found when building the CFG. -class CFGCallback { -public: - CFGCallback() {} - virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} - virtual void compareBitwiseEquality(const BinaryOperator *B, - bool isAlwaysTrue) {} - virtual ~CFGCallback() {} -}; - -/// CFG - Represents a source-level, intra-procedural CFG that represents the -/// control-flow of a Stmt. The Stmt can represent an entire function body, -/// or a single expression. A CFG will always contain one empty block that -/// represents the Exit point of the CFG. A CFG will also contain a designated -/// Entry block. The CFG solely represents control-flow; it consists of -/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG -/// was constructed from. -class CFG { -public: - //===--------------------------------------------------------------------===// - // CFG Construction & Manipulation. - //===--------------------------------------------------------------------===// - - class BuildOptions { - std::bitset<Stmt::lastStmtConstant> alwaysAddMask; - public: - typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs; - ForcedBlkExprs **forcedBlkExprs; - CFGCallback *Observer; - bool PruneTriviallyFalseEdges; - bool AddEHEdges; - bool AddInitializers; - bool AddImplicitDtors; - bool AddTemporaryDtors; - bool AddStaticInitBranches; - bool AddCXXNewAllocator; - bool AddCXXDefaultInitExprInCtors; - - bool alwaysAdd(const Stmt *stmt) const { - return alwaysAddMask[stmt->getStmtClass()]; - } - - BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { - alwaysAddMask[stmtClass] = val; - return *this; - } - - BuildOptions &setAllAlwaysAdd() { - alwaysAddMask.set(); - return *this; - } - - BuildOptions() - : forcedBlkExprs(nullptr), Observer(nullptr), - PruneTriviallyFalseEdges(true), AddEHEdges(false), - AddInitializers(false), AddImplicitDtors(false), - AddTemporaryDtors(false), AddStaticInitBranches(false), - AddCXXNewAllocator(false), AddCXXDefaultInitExprInCtors(false) {} - }; - - /// \brief Provides a custom implementation of the iterator class to have the - /// same interface as Function::iterator - iterator returns CFGBlock - /// (not a pointer to CFGBlock). - class graph_iterator { - public: - typedef CFGBlock value_type; - typedef value_type& reference; - typedef value_type* pointer; - typedef BumpVector<CFGBlock*>::iterator ImplTy; - - graph_iterator(const ImplTy &i) : I(i) {} - - bool operator==(const graph_iterator &X) const { return I == X.I; } - bool operator!=(const graph_iterator &X) const { return I != X.I; } - - reference operator*() const { return **I; } - pointer operator->() const { return *I; } - operator CFGBlock* () { return *I; } - - graph_iterator &operator++() { ++I; return *this; } - graph_iterator &operator--() { --I; return *this; } - - private: - ImplTy I; - }; - - class const_graph_iterator { - public: - typedef const CFGBlock value_type; - typedef value_type& reference; - typedef value_type* pointer; - typedef BumpVector<CFGBlock*>::const_iterator ImplTy; - - const_graph_iterator(const ImplTy &i) : I(i) {} - - bool operator==(const const_graph_iterator &X) const { return I == X.I; } - bool operator!=(const const_graph_iterator &X) const { return I != X.I; } - - reference operator*() const { return **I; } - pointer operator->() const { return *I; } - operator CFGBlock* () const { return *I; } - - const_graph_iterator &operator++() { ++I; return *this; } - const_graph_iterator &operator--() { --I; return *this; } - - private: - ImplTy I; - }; - - /// buildCFG - Builds a CFG from an AST. - static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, - const BuildOptions &BO); - - /// createBlock - Create a new block in the CFG. The CFG owns the block; - /// the caller should not directly free it. - CFGBlock *createBlock(); - - /// setEntry - Set the entry block of the CFG. This is typically used - /// only during CFG construction. Most CFG clients expect that the - /// entry block has no predecessors and contains no statements. - void setEntry(CFGBlock *B) { Entry = B; } - - /// setIndirectGotoBlock - Set the block used for indirect goto jumps. - /// This is typically used only during CFG construction. - void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } - - //===--------------------------------------------------------------------===// - // Block Iterators - //===--------------------------------------------------------------------===// - - typedef BumpVector<CFGBlock*> CFGBlockListTy; - typedef CFGBlockListTy::iterator iterator; - typedef CFGBlockListTy::const_iterator const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - - CFGBlock & front() { return *Blocks.front(); } - CFGBlock & back() { return *Blocks.back(); } - - iterator begin() { return Blocks.begin(); } - iterator end() { return Blocks.end(); } - const_iterator begin() const { return Blocks.begin(); } - const_iterator end() const { return Blocks.end(); } - - graph_iterator nodes_begin() { return graph_iterator(Blocks.begin()); } - graph_iterator nodes_end() { return graph_iterator(Blocks.end()); } - const_graph_iterator nodes_begin() const { - return const_graph_iterator(Blocks.begin()); - } - const_graph_iterator nodes_end() const { - return const_graph_iterator(Blocks.end()); - } - - reverse_iterator rbegin() { return Blocks.rbegin(); } - reverse_iterator rend() { return Blocks.rend(); } - const_reverse_iterator rbegin() const { return Blocks.rbegin(); } - const_reverse_iterator rend() const { return Blocks.rend(); } - - CFGBlock & getEntry() { return *Entry; } - const CFGBlock & getEntry() const { return *Entry; } - CFGBlock & getExit() { return *Exit; } - const CFGBlock & getExit() const { return *Exit; } - - CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } - const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } - - typedef std::vector<const CFGBlock*>::const_iterator try_block_iterator; - try_block_iterator try_blocks_begin() const { - return TryDispatchBlocks.begin(); - } - try_block_iterator try_blocks_end() const { - return TryDispatchBlocks.end(); - } - - void addTryDispatchBlock(const CFGBlock *block) { - TryDispatchBlocks.push_back(block); - } - - /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. - /// - /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains - /// multiple decls. - void addSyntheticDeclStmt(const DeclStmt *Synthetic, - const DeclStmt *Source) { - assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); - assert(Synthetic != Source && "Don't include original DeclStmts in map"); - assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); - SyntheticDeclStmts[Synthetic] = Source; - } - - typedef llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator - synthetic_stmt_iterator; - - /// Iterates over synthetic DeclStmts in the CFG. - /// - /// Each element is a (synthetic statement, source statement) pair. - /// - /// \sa addSyntheticDeclStmt - synthetic_stmt_iterator synthetic_stmt_begin() const { - return SyntheticDeclStmts.begin(); - } - - /// \sa synthetic_stmt_begin - synthetic_stmt_iterator synthetic_stmt_end() const { - return SyntheticDeclStmts.end(); - } - - //===--------------------------------------------------------------------===// - // Member templates useful for various batch operations over CFGs. - //===--------------------------------------------------------------------===// - - template <typename CALLBACK> - void VisitBlockStmts(CALLBACK& O) const { - for (const_iterator I=begin(), E=end(); I != E; ++I) - for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end(); - BI != BE; ++BI) { - if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) - O(const_cast<Stmt*>(stmt->getStmt())); - } - } - - //===--------------------------------------------------------------------===// - // CFG Introspection. - //===--------------------------------------------------------------------===// - - /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which - /// start at 0). - unsigned getNumBlockIDs() const { return NumBlockIDs; } - - /// size - Return the total number of CFGBlocks within the CFG - /// This is simply a renaming of the getNumBlockIDs(). This is necessary - /// because the dominator implementation needs such an interface. - unsigned size() const { return NumBlockIDs; } - - //===--------------------------------------------------------------------===// - // CFG Debugging: Pretty-Printing and Visualization. - //===--------------------------------------------------------------------===// - - void viewCFG(const LangOptions &LO) const; - void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; - void dump(const LangOptions &LO, bool ShowColors) const; - - //===--------------------------------------------------------------------===// - // Internal: constructors and data. - //===--------------------------------------------------------------------===// - - CFG() - : Entry(nullptr), Exit(nullptr), IndirectGotoBlock(nullptr), NumBlockIDs(0), - Blocks(BlkBVC, 10) {} - - llvm::BumpPtrAllocator& getAllocator() { - return BlkBVC.getAllocator(); - } - - BumpVectorContext &getBumpVectorContext() { - return BlkBVC; - } - -private: - CFGBlock *Entry; - CFGBlock *Exit; - CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch - // for indirect gotos - unsigned NumBlockIDs; - - BumpVectorContext BlkBVC; - - CFGBlockListTy Blocks; - - /// C++ 'try' statements are modeled with an indirect dispatch block. - /// This is the collection of such blocks present in the CFG. - std::vector<const CFGBlock *> TryDispatchBlocks; - - /// Collects DeclStmts synthesized for this CFG and maps each one back to its - /// source DeclStmt. - llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; -}; -} // end namespace clang - -//===----------------------------------------------------------------------===// -// GraphTraits specializations for CFG basic block graphs (source-level CFGs) -//===----------------------------------------------------------------------===// - -namespace llvm { - -/// Implement simplify_type for CFGTerminator, so that we can dyn_cast from -/// CFGTerminator to a specific Stmt class. -template <> struct simplify_type< ::clang::CFGTerminator> { - typedef ::clang::Stmt *SimpleType; - static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { - return Val.getStmt(); - } -}; - -// Traits for: CFGBlock - -template <> struct GraphTraits< ::clang::CFGBlock *> { - typedef ::clang::CFGBlock NodeType; - typedef ::clang::CFGBlock::succ_iterator ChildIteratorType; - - static NodeType* getEntryNode(::clang::CFGBlock *BB) - { return BB; } - - static inline ChildIteratorType child_begin(NodeType* N) - { return N->succ_begin(); } - - static inline ChildIteratorType child_end(NodeType* N) - { return N->succ_end(); } -}; - -template <> struct GraphTraits< const ::clang::CFGBlock *> { - typedef const ::clang::CFGBlock NodeType; - typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType; - - static NodeType* getEntryNode(const clang::CFGBlock *BB) - { return BB; } - - static inline ChildIteratorType child_begin(NodeType* N) - { return N->succ_begin(); } - - static inline ChildIteratorType child_end(NodeType* N) - { return N->succ_end(); } -}; - -template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > { - typedef ::clang::CFGBlock NodeType; - typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; - - static NodeType *getEntryNode(Inverse< ::clang::CFGBlock*> G) - { return G.Graph; } - - static inline ChildIteratorType child_begin(NodeType* N) - { return N->pred_begin(); } - - static inline ChildIteratorType child_end(NodeType* N) - { return N->pred_end(); } -}; - -template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > { - typedef const ::clang::CFGBlock NodeType; - typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; - - static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G) - { return G.Graph; } - - static inline ChildIteratorType child_begin(NodeType* N) - { return N->pred_begin(); } - - static inline ChildIteratorType child_end(NodeType* N) - { return N->pred_end(); } -}; - -// Traits for: CFG - -template <> struct GraphTraits< ::clang::CFG* > - : public GraphTraits< ::clang::CFGBlock *> { - - typedef ::clang::CFG::graph_iterator nodes_iterator; - - static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); } - static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} - static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } - static unsigned size(::clang::CFG* F) { return F->size(); } -}; - -template <> struct GraphTraits<const ::clang::CFG* > - : public GraphTraits<const ::clang::CFGBlock *> { - - typedef ::clang::CFG::const_graph_iterator nodes_iterator; - - static NodeType *getEntryNode( const ::clang::CFG* F) { - return &F->getEntry(); - } - static nodes_iterator nodes_begin( const ::clang::CFG* F) { - return F->nodes_begin(); - } - static nodes_iterator nodes_end( const ::clang::CFG* F) { - return F->nodes_end(); - } - static unsigned size(const ::clang::CFG* F) { - return F->size(); - } -}; - -template <> struct GraphTraits<Inverse< ::clang::CFG*> > - : public GraphTraits<Inverse< ::clang::CFGBlock*> > { - - typedef ::clang::CFG::graph_iterator nodes_iterator; - - static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); } - static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} - static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } -}; - -template <> struct GraphTraits<Inverse<const ::clang::CFG*> > - : public GraphTraits<Inverse<const ::clang::CFGBlock*> > { - - typedef ::clang::CFG::const_graph_iterator nodes_iterator; - - static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); } - static nodes_iterator nodes_begin(const ::clang::CFG* F) { - return F->nodes_begin(); - } - static nodes_iterator nodes_end(const ::clang::CFG* F) { - return F->nodes_end(); - } -}; -} // end llvm namespace - -#endif // LLVM_CLANG_ANALYSIS_CFG_H diff --git a/include/clang/Analysis/CFGStmtMap.h b/include/clang/Analysis/CFGStmtMap.h deleted file mode 100644 index 4dfa91d..0000000 --- a/include/clang/Analysis/CFGStmtMap.h +++ /dev/null @@ -1,52 +0,0 @@ -//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- 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 CFGStmtMap class, which defines a mapping from -// Stmt* to CFGBlock* -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_CFGSTMTMAP_H -#define LLVM_CLANG_ANALYSIS_CFGSTMTMAP_H - -#include "clang/Analysis/CFG.h" - -namespace clang { - -class CFG; -class CFGBlock; -class ParentMap; -class Stmt; - -class CFGStmtMap { - ParentMap *PM; - void *M; - - CFGStmtMap(ParentMap *pm, void *m) : PM(pm), M(m) {} - -public: - ~CFGStmtMap(); - - /// Returns a new CFGMap for the given CFG. It is the caller's - /// responsibility to 'delete' this object when done using it. - static CFGStmtMap *Build(CFG* C, ParentMap *PM); - - /// Returns the CFGBlock the specified Stmt* appears in. For Stmt* that - /// are terminators, the CFGBlock is the block they appear as a terminator, - /// and not the block they appear as a block-level expression (e.g, '&&'). - /// CaseStmts and LabelStmts map to the CFGBlock they label. - CFGBlock *getBlock(Stmt * S); - - const CFGBlock *getBlock(const Stmt * S) const { - return const_cast<CFGStmtMap*>(this)->getBlock(const_cast<Stmt*>(S)); - } -}; - -} // end clang namespace -#endif diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h deleted file mode 100644 index eda22a5..0000000 --- a/include/clang/Analysis/CallGraph.h +++ /dev/null @@ -1,253 +0,0 @@ -//== CallGraph.h - AST-based Call graph ------------------------*- C++ -*--==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file declares the AST-based CallGraph. -// -// A call graph for functions whose definitions/bodies are available in the -// current translation unit. The graph has a "virtual" root node that contains -// edges to all externally available functions. -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H -#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H - -#include "clang/AST/DeclBase.h" -#include "clang/AST/RecursiveASTVisitor.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SetVector.h" - -namespace clang { -class CallGraphNode; - -/// \brief The AST-based call graph. -/// -/// The call graph extends itself with the given declarations by implementing -/// the recursive AST visitor, which constructs the graph by visiting the given -/// declarations. -class CallGraph : public RecursiveASTVisitor<CallGraph> { - friend class CallGraphNode; - - typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy; - - /// FunctionMap owns all CallGraphNodes. - FunctionMapTy FunctionMap; - - /// This is a virtual root node that has edges to all the functions. - CallGraphNode *Root; - -public: - CallGraph(); - ~CallGraph(); - - /// \brief Populate the call graph with the functions in the given - /// declaration. - /// - /// Recursively walks the declaration to find all the dependent Decls as well. - void addToCallGraph(Decl *D) { - TraverseDecl(D); - } - - /// \brief Determine if a declaration should be included in the graph. - static bool includeInGraph(const Decl *D); - - /// \brief Lookup the node for the given declaration. - CallGraphNode *getNode(const Decl *) const; - - /// \brief Lookup the node for the given declaration. If none found, insert - /// one into the graph. - CallGraphNode *getOrInsertNode(Decl *); - - /// Iterators through all the elements in the graph. Note, this gives - /// non-deterministic order. - typedef FunctionMapTy::iterator iterator; - typedef FunctionMapTy::const_iterator const_iterator; - iterator begin() { return FunctionMap.begin(); } - iterator end() { return FunctionMap.end(); } - const_iterator begin() const { return FunctionMap.begin(); } - const_iterator end() const { return FunctionMap.end(); } - - /// \brief Get the number of nodes in the graph. - unsigned size() const { return FunctionMap.size(); } - - /// \ brief Get the virtual root of the graph, all the functions available - /// externally are represented as callees of the node. - CallGraphNode *getRoot() const { return Root; } - - /// Iterators through all the nodes of the graph that have no parent. These - /// are the unreachable nodes, which are either unused or are due to us - /// failing to add a call edge due to the analysis imprecision. - typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; - typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; - - void print(raw_ostream &os) const; - void dump() const; - void viewGraph() const; - - void addNodesForBlocks(DeclContext *D); - - /// Part of recursive declaration visitation. We recursively visit all the - /// declarations to collect the root functions. - bool VisitFunctionDecl(FunctionDecl *FD) { - // We skip function template definitions, as their semantics is - // only determined when they are instantiated. - if (includeInGraph(FD)) { - // Add all blocks declared inside this function to the graph. - addNodesForBlocks(FD); - // If this function has external linkage, anything could call it. - // Note, we are not precise here. For example, the function could have - // its address taken. - addNodeForDecl(FD, FD->isGlobal()); - } - return true; - } - - /// Part of recursive declaration visitation. - bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { - if (includeInGraph(MD)) { - addNodesForBlocks(MD); - addNodeForDecl(MD, true); - } - return true; - } - - // We are only collecting the declarations, so do not step into the bodies. - bool TraverseStmt(Stmt *S) { return true; } - - bool shouldWalkTypesOfTypeLocs() const { return false; } - -private: - /// \brief Add the given declaration to the call graph. - void addNodeForDecl(Decl *D, bool IsGlobal); - - /// \brief Allocate a new node in the graph. - CallGraphNode *allocateNewNode(Decl *); -}; - -class CallGraphNode { -public: - typedef CallGraphNode* CallRecord; - -private: - /// \brief The function/method declaration. - Decl *FD; - - /// \brief The list of functions called from this node. - SmallVector<CallRecord, 5> CalledFunctions; - -public: - CallGraphNode(Decl *D) : FD(D) {} - - typedef SmallVectorImpl<CallRecord>::iterator iterator; - typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator; - - /// Iterators through all the callees/children of the node. - inline iterator begin() { return CalledFunctions.begin(); } - inline iterator end() { return CalledFunctions.end(); } - inline const_iterator begin() const { return CalledFunctions.begin(); } - inline const_iterator end() const { return CalledFunctions.end(); } - - inline bool empty() const {return CalledFunctions.empty(); } - inline unsigned size() const {return CalledFunctions.size(); } - - void addCallee(CallGraphNode *N, CallGraph *CG) { - CalledFunctions.push_back(N); - } - - Decl *getDecl() const { return FD; } - - void print(raw_ostream &os) const; - void dump() const; -}; - -} // end clang namespace - -// Graph traits for iteration, viewing. -namespace llvm { -template <> struct GraphTraits<clang::CallGraphNode*> { - typedef clang::CallGraphNode NodeType; - typedef clang::CallGraphNode::CallRecord CallRecordTy; - typedef std::pointer_to_unary_function<CallRecordTy, - clang::CallGraphNode*> CGNDerefFun; - static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } - typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; - static inline ChildIteratorType child_begin(NodeType *N) { - return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); - } - static inline ChildIteratorType child_end (NodeType *N) { - return map_iterator(N->end(), CGNDerefFun(CGNDeref)); - } - static clang::CallGraphNode *CGNDeref(CallRecordTy P) { - return P; - } -}; - -template <> struct GraphTraits<const clang::CallGraphNode*> { - typedef const clang::CallGraphNode NodeType; - typedef NodeType::const_iterator ChildIteratorType; - static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } - static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} - static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } -}; - -template <> struct GraphTraits<clang::CallGraph*> - : public GraphTraits<clang::CallGraphNode*> { - - static NodeType *getEntryNode(clang::CallGraph *CGN) { - return CGN->getRoot(); // Start at the external node! - } - typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; - typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; - // nodes_iterator/begin/end - Allow iteration over all nodes in the graph - typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; - - static nodes_iterator nodes_begin(clang::CallGraph *CG) { - return map_iterator(CG->begin(), DerefFun(CGdereference)); - } - static nodes_iterator nodes_end (clang::CallGraph *CG) { - return map_iterator(CG->end(), DerefFun(CGdereference)); - } - static clang::CallGraphNode &CGdereference(PairTy P) { - return *(P.second); - } - - static unsigned size(clang::CallGraph *CG) { - return CG->size(); - } -}; - -template <> struct GraphTraits<const clang::CallGraph*> : - public GraphTraits<const clang::CallGraphNode*> { - static NodeType *getEntryNode(const clang::CallGraph *CGN) { - return CGN->getRoot(); - } - typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; - typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; - // nodes_iterator/begin/end - Allow iteration over all nodes in the graph - typedef mapped_iterator<clang::CallGraph::const_iterator, - DerefFun> nodes_iterator; - - static nodes_iterator nodes_begin(const clang::CallGraph *CG) { - return map_iterator(CG->begin(), DerefFun(CGdereference)); - } - static nodes_iterator nodes_end(const clang::CallGraph *CG) { - return map_iterator(CG->end(), DerefFun(CGdereference)); - } - static clang::CallGraphNode &CGdereference(PairTy P) { - return *(P.second); - } - - static unsigned size(const clang::CallGraph *CG) { - return CG->size(); - } -}; - -} // end llvm namespace - -#endif diff --git a/include/clang/Analysis/CodeInjector.h b/include/clang/Analysis/CodeInjector.h deleted file mode 100644 index 413a55b..0000000 --- a/include/clang/Analysis/CodeInjector.h +++ /dev/null @@ -1,46 +0,0 @@ -//===-- CodeInjector.h ------------------------------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// \brief Defines the clang::CodeInjector interface which is responsible for -/// injecting AST of function definitions that may not be available in the -/// original source. -/// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_CODEINJECTOR_H -#define LLVM_CLANG_ANALYSIS_CODEINJECTOR_H - -namespace clang { - -class Stmt; -class FunctionDecl; -class ObjCMethodDecl; - -/// \brief CodeInjector is an interface which is responsible for injecting AST -/// of function definitions that may not be available in the original source. -/// -/// The getBody function will be called each time the static analyzer examines a -/// function call that has no definition available in the current translation -/// unit. If the returned statement is not a null pointer, it is assumed to be -/// the body of a function which will be used for the analysis. The source of -/// the body can be arbitrary, but it is advised to use memoization to avoid -/// unnecessary reparsing of the external source that provides the body of the -/// functions. -class CodeInjector { -public: - CodeInjector(); - virtual ~CodeInjector(); - - virtual Stmt *getBody(const FunctionDecl *D) = 0; - virtual Stmt *getBody(const ObjCMethodDecl *D) = 0; -}; -} - -#endif diff --git a/include/clang/Analysis/DomainSpecific/CocoaConventions.h b/include/clang/Analysis/DomainSpecific/CocoaConventions.h deleted file mode 100644 index 8b3fcff..0000000 --- a/include/clang/Analysis/DomainSpecific/CocoaConventions.h +++ /dev/null @@ -1,42 +0,0 @@ -//===- CocoaConventions.h - Special handling of Cocoa conventions -*- 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 cocoa naming convention analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_COCOACONVENTIONS_H -#define LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_COCOACONVENTIONS_H - -#include "clang/Basic/LLVM.h" -#include "llvm/ADT/StringRef.h" - -namespace clang { -class FunctionDecl; -class QualType; - -namespace ento { -namespace cocoa { - - bool isRefType(QualType RetTy, StringRef Prefix, - StringRef Name = StringRef()); - - bool isCocoaObjectRef(QualType T); - -} - -namespace coreFoundation { - bool isCFObjectRef(QualType T); - - bool followsCreateRule(const FunctionDecl *FD); -} - -}} // end: "clang:ento" - -#endif diff --git a/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h b/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h deleted file mode 100644 index f9e800a..0000000 --- a/include/clang/Analysis/DomainSpecific/ObjCNoReturn.h +++ /dev/null @@ -1,46 +0,0 @@ -//= ObjCNoReturn.h - Handling of Cocoa APIs known not to return --*- 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 special handling of recognizing ObjC API hooks that -// do not return but aren't marked as such in API headers. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_OBJCNORETURN_H -#define LLVM_CLANG_ANALYSIS_DOMAINSPECIFIC_OBJCNORETURN_H - -#include "clang/Basic/IdentifierTable.h" - -namespace clang { - -class ASTContext; -class ObjCMessageExpr; - -class ObjCNoReturn { - /// Cached "raise" selector. - Selector RaiseSel; - - /// Cached identifier for "NSException". - IdentifierInfo *NSExceptionII; - - enum { NUM_RAISE_SELECTORS = 2 }; - - /// Cached set of selectors in NSException that are 'noreturn'. - Selector NSExceptionInstanceRaiseSelectors[NUM_RAISE_SELECTORS]; - -public: - ObjCNoReturn(ASTContext &C); - - /// Return true if the given message expression is known to never - /// return. - bool isImplicitNoReturn(const ObjCMessageExpr *ME); -}; -} - -#endif diff --git a/include/clang/Analysis/FlowSensitive/DataflowValues.h b/include/clang/Analysis/FlowSensitive/DataflowValues.h deleted file mode 100644 index f86b2b0..0000000 --- a/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ /dev/null @@ -1,172 +0,0 @@ -//===--- DataflowValues.h - Data structure for dataflow 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 a skeleton data structure for encapsulating the dataflow -// values for a CFG. Typically this is subclassed to provide methods for -// computing these values from a CFG. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_VALUES -#define LLVM_CLANG_ANALYSES_DATAFLOW_VALUES - -#include "clang/Analysis/CFG.h" -#include "clang/Analysis/ProgramPoint.h" -#include "llvm/ADT/DenseMap.h" - -//===----------------------------------------------------------------------===// -/// Dataflow Directional Tag Classes. These are used for tag dispatching -/// within the dataflow solver/transfer functions to determine what direction -/// a dataflow analysis flows. -//===----------------------------------------------------------------------===// - -namespace clang { -namespace dataflow { - struct forward_analysis_tag {}; - struct backward_analysis_tag {}; -} // end namespace dataflow - -//===----------------------------------------------------------------------===// -/// DataflowValues. Container class to store dataflow values for a CFG. -//===----------------------------------------------------------------------===// - -template <typename ValueTypes, - typename _AnalysisDirTag = dataflow::forward_analysis_tag > -class DataflowValues { - - //===--------------------------------------------------------------------===// - // Type declarations. - //===--------------------------------------------------------------------===// - -public: - typedef typename ValueTypes::ValTy ValTy; - typedef typename ValueTypes::AnalysisDataTy AnalysisDataTy; - typedef _AnalysisDirTag AnalysisDirTag; - typedef llvm::DenseMap<ProgramPoint, ValTy> EdgeDataMapTy; - typedef llvm::DenseMap<const CFGBlock*, ValTy> BlockDataMapTy; - typedef llvm::DenseMap<const Stmt*, ValTy> StmtDataMapTy; - - //===--------------------------------------------------------------------===// - // Predicates. - //===--------------------------------------------------------------------===// - -public: - /// isForwardAnalysis - Returns true if the dataflow values are computed - /// from a forward analysis. - bool isForwardAnalysis() { return isForwardAnalysis(AnalysisDirTag()); } - - /// isBackwardAnalysis - Returns true if the dataflow values are computed - /// from a backward analysis. - bool isBackwardAnalysis() { return !isForwardAnalysis(); } - -private: - bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } - bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } - - //===--------------------------------------------------------------------===// - // Initialization and accessors methods. - //===--------------------------------------------------------------------===// - -public: - DataflowValues() : StmtDataMap(NULL) {} - ~DataflowValues() { delete StmtDataMap; } - - /// InitializeValues - Invoked by the solver to initialize state needed for - /// dataflow analysis. This method is usually specialized by subclasses. - void InitializeValues(const CFG& cfg) {} - - - /// getEdgeData - Retrieves the dataflow values associated with a - /// CFG edge. - ValTy& getEdgeData(const BlockEdge &E) { - typename EdgeDataMapTy::iterator I = EdgeDataMap.find(E); - assert (I != EdgeDataMap.end() && "No data associated with Edge."); - return I->second; - } - - const ValTy& getEdgeData(const BlockEdge &E) const { - return reinterpret_cast<DataflowValues*>(this)->getEdgeData(E); - } - - /// getBlockData - Retrieves the dataflow values associated with a - /// specified CFGBlock. If the dataflow analysis is a forward analysis, - /// this data is associated with the END of the block. If the analysis - /// is a backwards analysis, it is associated with the ENTRY of the block. - ValTy& getBlockData(const CFGBlock *B) { - typename BlockDataMapTy::iterator I = BlockDataMap.find(B); - assert (I != BlockDataMap.end() && "No data associated with block."); - return I->second; - } - - const ValTy& getBlockData(const CFGBlock *B) const { - return const_cast<DataflowValues*>(this)->getBlockData(B); - } - - /// getStmtData - Retrieves the dataflow values associated with a - /// specified Stmt. If the dataflow analysis is a forward analysis, - /// this data corresponds to the point immediately before a Stmt. - /// If the analysis is a backwards analysis, it is associated with - /// the point after a Stmt. This data is only computed for block-level - /// expressions, and only when requested when the analysis is executed. - ValTy& getStmtData(const Stmt *S) { - assert (StmtDataMap && "Dataflow values were not computed for statements."); - typename StmtDataMapTy::iterator I = StmtDataMap->find(S); - assert (I != StmtDataMap->end() && "No data associated with statement."); - return I->second; - } - - const ValTy& getStmtData(const Stmt *S) const { - return const_cast<DataflowValues*>(this)->getStmtData(S); - } - - /// getEdgeDataMap - Retrieves the internal map between CFG edges and - /// dataflow values. Usually used by a dataflow solver to compute - /// values for blocks. - EdgeDataMapTy& getEdgeDataMap() { return EdgeDataMap; } - const EdgeDataMapTy& getEdgeDataMap() const { return EdgeDataMap; } - - /// getBlockDataMap - Retrieves the internal map between CFGBlocks and - /// dataflow values. If the dataflow analysis operates in the forward - /// direction, the values correspond to the dataflow values at the start - /// of the block. Otherwise, for a backward analysis, the values correpsond - /// to the dataflow values at the end of the block. - BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } - const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } - - /// getStmtDataMap - Retrieves the internal map between Stmts and - /// dataflow values. - StmtDataMapTy& getStmtDataMap() { - if (!StmtDataMap) StmtDataMap = new StmtDataMapTy(); - return *StmtDataMap; - } - - const StmtDataMapTy& getStmtDataMap() const { - return const_cast<DataflowValues*>(this)->getStmtDataMap(); - } - - /// getAnalysisData - Retrieves the meta data associated with a - /// dataflow analysis for analyzing a particular CFG. - /// This is typically consumed by transfer function code (via the solver). - /// This can also be used by subclasses to interpret the dataflow values. - AnalysisDataTy& getAnalysisData() { return AnalysisData; } - const AnalysisDataTy& getAnalysisData() const { return AnalysisData; } - - //===--------------------------------------------------------------------===// - // Internal data. - //===--------------------------------------------------------------------===// - -protected: - EdgeDataMapTy EdgeDataMap; - BlockDataMapTy BlockDataMap; - StmtDataMapTy* StmtDataMap; - AnalysisDataTy AnalysisData; -}; - -} // end namespace clang -#endif diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h deleted file mode 100644 index 6d816fd..0000000 --- a/include/clang/Analysis/ProgramPoint.h +++ /dev/null @@ -1,704 +0,0 @@ -//==- ProgramPoint.h - Program Points for Path-Sensitive 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 the interface ProgramPoint, which identifies a -// distinct location in a function. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H -#define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H - -#include "clang/Analysis/AnalysisContext.h" -#include "clang/Analysis/CFG.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/Support/Casting.h" -#include "llvm/Support/DataTypes.h" -#include <cassert> -#include <string> -#include <utility> - -namespace clang { - -class AnalysisDeclContext; -class FunctionDecl; -class LocationContext; - -/// ProgramPoints can be "tagged" as representing points specific to a given -/// analysis entity. Tags are abstract annotations, with an associated -/// description and potentially other information. -class ProgramPointTag { -public: - ProgramPointTag(void *tagKind = nullptr) : TagKind(tagKind) {} - virtual ~ProgramPointTag(); - virtual StringRef getTagDescription() const = 0; - -protected: - /// Used to implement 'isKind' in subclasses. - const void *getTagKind() { return TagKind; } - -private: - const void *TagKind; -}; - -class SimpleProgramPointTag : public ProgramPointTag { - std::string Desc; -public: - SimpleProgramPointTag(StringRef MsgProvider, StringRef Msg); - StringRef getTagDescription() const override; -}; - -class ProgramPoint { -public: - enum Kind { BlockEdgeKind, - BlockEntranceKind, - BlockExitKind, - PreStmtKind, - PreStmtPurgeDeadSymbolsKind, - PostStmtPurgeDeadSymbolsKind, - PostStmtKind, - PreLoadKind, - PostLoadKind, - PreStoreKind, - PostStoreKind, - PostConditionKind, - PostLValueKind, - MinPostStmtKind = PostStmtKind, - MaxPostStmtKind = PostLValueKind, - PostInitializerKind, - CallEnterKind, - CallExitBeginKind, - CallExitEndKind, - PreImplicitCallKind, - PostImplicitCallKind, - MinImplicitCallKind = PreImplicitCallKind, - MaxImplicitCallKind = PostImplicitCallKind, - EpsilonKind}; - -private: - const void *Data1; - llvm::PointerIntPair<const void *, 2, unsigned> Data2; - - // The LocationContext could be NULL to allow ProgramPoint to be used in - // context insensitive analysis. - llvm::PointerIntPair<const LocationContext *, 2, unsigned> L; - - llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag; - -protected: - ProgramPoint() {} - ProgramPoint(const void *P, - Kind k, - const LocationContext *l, - const ProgramPointTag *tag = nullptr) - : Data1(P), - Data2(nullptr, (((unsigned) k) >> 0) & 0x3), - L(l, (((unsigned) k) >> 2) & 0x3), - Tag(tag, (((unsigned) k) >> 4) & 0x3) { - assert(getKind() == k); - assert(getLocationContext() == l); - assert(getData1() == P); - } - - ProgramPoint(const void *P1, - const void *P2, - Kind k, - const LocationContext *l, - const ProgramPointTag *tag = nullptr) - : Data1(P1), - Data2(P2, (((unsigned) k) >> 0) & 0x3), - L(l, (((unsigned) k) >> 2) & 0x3), - Tag(tag, (((unsigned) k) >> 4) & 0x3) {} - -protected: - const void *getData1() const { return Data1; } - const void *getData2() const { return Data2.getPointer(); } - void setData2(const void *d) { Data2.setPointer(d); } - -public: - /// Create a new ProgramPoint object that is the same as the original - /// except for using the specified tag value. - ProgramPoint withTag(const ProgramPointTag *tag) const { - return ProgramPoint(getData1(), getData2(), getKind(), - getLocationContext(), tag); - } - - /// \brief Convert to the specified ProgramPoint type, asserting that this - /// ProgramPoint is of the desired type. - template<typename T> - T castAs() const { - assert(T::isKind(*this)); - T t; - ProgramPoint& PP = t; - PP = *this; - return t; - } - - /// \brief Convert to the specified ProgramPoint type, returning None if this - /// ProgramPoint is not of the desired type. - template<typename T> - Optional<T> getAs() const { - if (!T::isKind(*this)) - return None; - T t; - ProgramPoint& PP = t; - PP = *this; - return t; - } - - Kind getKind() const { - unsigned x = Tag.getInt(); - x <<= 2; - x |= L.getInt(); - x <<= 2; - x |= Data2.getInt(); - return (Kind) x; - } - - /// \brief Is this a program point corresponding to purge/removal of dead - /// symbols and bindings. - bool isPurgeKind() { - Kind K = getKind(); - return (K == PostStmtPurgeDeadSymbolsKind || - K == PreStmtPurgeDeadSymbolsKind); - } - - const ProgramPointTag *getTag() const { return Tag.getPointer(); } - - const LocationContext *getLocationContext() const { - return L.getPointer(); - } - - // For use with DenseMap. This hash is probably slow. - unsigned getHashValue() const { - llvm::FoldingSetNodeID ID; - Profile(ID); - return ID.ComputeHash(); - } - - bool operator==(const ProgramPoint & RHS) const { - return Data1 == RHS.Data1 && - Data2 == RHS.Data2 && - L == RHS.L && - Tag == RHS.Tag; - } - - bool operator!=(const ProgramPoint &RHS) const { - return Data1 != RHS.Data1 || - Data2 != RHS.Data2 || - L != RHS.L || - Tag != RHS.Tag; - } - - void Profile(llvm::FoldingSetNodeID& ID) const { - ID.AddInteger((unsigned) getKind()); - ID.AddPointer(getData1()); - ID.AddPointer(getData2()); - ID.AddPointer(getLocationContext()); - ID.AddPointer(getTag()); - } - - static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, - const LocationContext *LC, - const ProgramPointTag *tag); -}; - -class BlockEntrance : public ProgramPoint { -public: - BlockEntrance(const CFGBlock *B, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : ProgramPoint(B, BlockEntranceKind, L, tag) { - assert(B && "BlockEntrance requires non-null block"); - } - - const CFGBlock *getBlock() const { - return reinterpret_cast<const CFGBlock*>(getData1()); - } - - Optional<CFGElement> getFirstElement() const { - const CFGBlock *B = getBlock(); - return B->empty() ? Optional<CFGElement>() : B->front(); - } - -private: - friend class ProgramPoint; - BlockEntrance() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == BlockEntranceKind; - } -}; - -class BlockExit : public ProgramPoint { -public: - BlockExit(const CFGBlock *B, const LocationContext *L) - : ProgramPoint(B, BlockExitKind, L) {} - - const CFGBlock *getBlock() const { - return reinterpret_cast<const CFGBlock*>(getData1()); - } - - const Stmt *getTerminator() const { - return getBlock()->getTerminator(); - } - -private: - friend class ProgramPoint; - BlockExit() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == BlockExitKind; - } -}; - -class StmtPoint : public ProgramPoint { -public: - StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, - const ProgramPointTag *tag) - : ProgramPoint(S, p2, k, L, tag) { - assert(S); - } - - const Stmt *getStmt() const { return (const Stmt*) getData1(); } - - template <typename T> - const T* getStmtAs() const { return dyn_cast<T>(getStmt()); } - -protected: - StmtPoint() {} -private: - friend class ProgramPoint; - static bool isKind(const ProgramPoint &Location) { - unsigned k = Location.getKind(); - return k >= PreStmtKind && k <= MaxPostStmtKind; - } -}; - - -class PreStmt : public StmtPoint { -public: - PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag, - const Stmt *SubStmt = nullptr) - : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} - - const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } - -private: - friend class ProgramPoint; - PreStmt() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PreStmtKind; - } -}; - -class PostStmt : public StmtPoint { -protected: - PostStmt() {} - PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : StmtPoint(S, data, k, L, tag) {} - -public: - explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : StmtPoint(S, nullptr, k, L, tag) {} - - explicit PostStmt(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : StmtPoint(S, nullptr, PostStmtKind, L, tag) {} - -private: - friend class ProgramPoint; - static bool isKind(const ProgramPoint &Location) { - unsigned k = Location.getKind(); - return k >= MinPostStmtKind && k <= MaxPostStmtKind; - } -}; - -// PostCondition represents the post program point of a branch condition. -class PostCondition : public PostStmt { -public: - PostCondition(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : PostStmt(S, PostConditionKind, L, tag) {} - -private: - friend class ProgramPoint; - PostCondition() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostConditionKind; - } -}; - -class LocationCheck : public StmtPoint { -protected: - LocationCheck() {} - LocationCheck(const Stmt *S, const LocationContext *L, - ProgramPoint::Kind K, const ProgramPointTag *tag) - : StmtPoint(S, nullptr, K, L, tag) {} - -private: - friend class ProgramPoint; - static bool isKind(const ProgramPoint &location) { - unsigned k = location.getKind(); - return k == PreLoadKind || k == PreStoreKind; - } -}; - -class PreLoad : public LocationCheck { -public: - PreLoad(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : LocationCheck(S, L, PreLoadKind, tag) {} - -private: - friend class ProgramPoint; - PreLoad() {} - static bool isKind(const ProgramPoint &location) { - return location.getKind() == PreLoadKind; - } -}; - -class PreStore : public LocationCheck { -public: - PreStore(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : LocationCheck(S, L, PreStoreKind, tag) {} - -private: - friend class ProgramPoint; - PreStore() {} - static bool isKind(const ProgramPoint &location) { - return location.getKind() == PreStoreKind; - } -}; - -class PostLoad : public PostStmt { -public: - PostLoad(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : PostStmt(S, PostLoadKind, L, tag) {} - -private: - friend class ProgramPoint; - PostLoad() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostLoadKind; - } -}; - -/// \brief Represents a program point after a store evaluation. -class PostStore : public PostStmt { -public: - /// Construct the post store point. - /// \param Loc can be used to store the information about the location - /// used in the form it was uttered in the code. - PostStore(const Stmt *S, const LocationContext *L, const void *Loc, - const ProgramPointTag *tag = nullptr) - : PostStmt(S, PostStoreKind, L, tag) { - assert(getData2() == nullptr); - setData2(Loc); - } - - /// \brief Returns the information about the location used in the store, - /// how it was uttered in the code. - const void *getLocationValue() const { - return getData2(); - } - -private: - friend class ProgramPoint; - PostStore() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostStoreKind; - } -}; - -class PostLValue : public PostStmt { -public: - PostLValue(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : PostStmt(S, PostLValueKind, L, tag) {} - -private: - friend class ProgramPoint; - PostLValue() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostLValueKind; - } -}; - -/// Represents a point after we ran remove dead bindings BEFORE -/// processing the given statement. -class PreStmtPurgeDeadSymbols : public StmtPoint { -public: - PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { } - -private: - friend class ProgramPoint; - PreStmtPurgeDeadSymbols() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PreStmtPurgeDeadSymbolsKind; - } -}; - -/// Represents a point after we ran remove dead bindings AFTER -/// processing the given statement. -class PostStmtPurgeDeadSymbols : public StmtPoint { -public: - PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, - const ProgramPointTag *tag = nullptr) - : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { } - -private: - friend class ProgramPoint; - PostStmtPurgeDeadSymbols() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostStmtPurgeDeadSymbolsKind; - } -}; - -class BlockEdge : public ProgramPoint { -public: - BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L) - : ProgramPoint(B1, B2, BlockEdgeKind, L) { - assert(B1 && "BlockEdge: source block must be non-null"); - assert(B2 && "BlockEdge: destination block must be non-null"); - } - - const CFGBlock *getSrc() const { - return static_cast<const CFGBlock*>(getData1()); - } - - const CFGBlock *getDst() const { - return static_cast<const CFGBlock*>(getData2()); - } - -private: - friend class ProgramPoint; - BlockEdge() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == BlockEdgeKind; - } -}; - -class PostInitializer : public ProgramPoint { -public: - /// \brief Construct a PostInitializer point that represents a location after - /// CXXCtorInitializer expression evaluation. - /// - /// \param I The initializer. - /// \param Loc The location of the field being initialized. - PostInitializer(const CXXCtorInitializer *I, - const void *Loc, - const LocationContext *L) - : ProgramPoint(I, Loc, PostInitializerKind, L) {} - - const CXXCtorInitializer *getInitializer() const { - return static_cast<const CXXCtorInitializer *>(getData1()); - } - - /// \brief Returns the location of the field. - const void *getLocationValue() const { - return getData2(); - } - -private: - friend class ProgramPoint; - PostInitializer() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostInitializerKind; - } -}; - -/// Represents an implicit call event. -/// -/// The nearest statement is provided for diagnostic purposes. -class ImplicitCallPoint : public ProgramPoint { -public: - ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K, - const LocationContext *L, const ProgramPointTag *Tag) - : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {} - - const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); } - SourceLocation getLocation() const { - return SourceLocation::getFromPtrEncoding(getData1()); - } - -protected: - ImplicitCallPoint() {} -private: - friend class ProgramPoint; - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() >= MinImplicitCallKind && - Location.getKind() <= MaxImplicitCallKind; - } -}; - -/// Represents a program point just before an implicit call event. -/// -/// Explicit calls will appear as PreStmt program points. -class PreImplicitCall : public ImplicitCallPoint { -public: - PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, - const ProgramPointTag *Tag = nullptr) - : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {} - -private: - friend class ProgramPoint; - PreImplicitCall() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PreImplicitCallKind; - } -}; - -/// Represents a program point just after an implicit call event. -/// -/// Explicit calls will appear as PostStmt program points. -class PostImplicitCall : public ImplicitCallPoint { -public: - PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, - const ProgramPointTag *Tag = nullptr) - : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {} - -private: - friend class ProgramPoint; - PostImplicitCall() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == PostImplicitCallKind; - } -}; - -/// Represents a point when we begin processing an inlined call. -/// CallEnter uses the caller's location context. -class CallEnter : public ProgramPoint { -public: - CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, - const LocationContext *callerCtx) - : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {} - - const Stmt *getCallExpr() const { - return static_cast<const Stmt *>(getData1()); - } - - const StackFrameContext *getCalleeContext() const { - return static_cast<const StackFrameContext *>(getData2()); - } - -private: - friend class ProgramPoint; - CallEnter() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == CallEnterKind; - } -}; - -/// Represents a point when we start the call exit sequence (for inlined call). -/// -/// The call exit is simulated with a sequence of nodes, which occur between -/// CallExitBegin and CallExitEnd. The following operations occur between the -/// two program points: -/// - CallExitBegin -/// - Bind the return value -/// - Run Remove dead bindings (to clean up the dead symbols from the callee). -/// - CallExitEnd -class CallExitBegin : public ProgramPoint { -public: - // CallExitBegin uses the callee's location context. - CallExitBegin(const StackFrameContext *L) - : ProgramPoint(nullptr, CallExitBeginKind, L, nullptr) {} - -private: - friend class ProgramPoint; - CallExitBegin() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == CallExitBeginKind; - } -}; - -/// Represents a point when we finish the call exit sequence (for inlined call). -/// \sa CallExitBegin -class CallExitEnd : public ProgramPoint { -public: - // CallExitEnd uses the caller's location context. - CallExitEnd(const StackFrameContext *CalleeCtx, - const LocationContext *CallerCtx) - : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {} - - const StackFrameContext *getCalleeContext() const { - return static_cast<const StackFrameContext *>(getData1()); - } - -private: - friend class ProgramPoint; - CallExitEnd() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == CallExitEndKind; - } -}; - -/// This is a meta program point, which should be skipped by all the diagnostic -/// reasoning etc. -class EpsilonPoint : public ProgramPoint { -public: - EpsilonPoint(const LocationContext *L, const void *Data1, - const void *Data2 = nullptr, - const ProgramPointTag *tag = nullptr) - : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {} - - const void *getData() const { return getData1(); } - -private: - friend class ProgramPoint; - EpsilonPoint() {} - static bool isKind(const ProgramPoint &Location) { - return Location.getKind() == EpsilonKind; - } -}; - -} // end namespace clang - - -namespace llvm { // Traits specialization for DenseMap - -template <> struct DenseMapInfo<clang::ProgramPoint> { - -static inline clang::ProgramPoint getEmptyKey() { - uintptr_t x = - reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; - return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr); -} - -static inline clang::ProgramPoint getTombstoneKey() { - uintptr_t x = - reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; - return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr); -} - -static unsigned getHashValue(const clang::ProgramPoint &Loc) { - return Loc.getHashValue(); -} - -static bool isEqual(const clang::ProgramPoint &L, - const clang::ProgramPoint &R) { - return L == R; -} - -}; - -template <> -struct isPodLike<clang::ProgramPoint> { static const bool value = true; }; - -} // end namespace llvm - -#endif diff --git a/include/clang/Analysis/Support/BumpVector.h b/include/clang/Analysis/Support/BumpVector.h deleted file mode 100644 index 591d17b..0000000 --- a/include/clang/Analysis/Support/BumpVector.h +++ /dev/null @@ -1,250 +0,0 @@ -//===-- BumpVector.h - Vector-like ADT that uses bump allocation --*- C++ -*-=// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file provides BumpVector, a vector-like ADT whose contents are -// allocated from a BumpPtrAllocator. -// -//===----------------------------------------------------------------------===// - -// FIXME: Most of this is copy-and-paste from SmallVector.h. We can -// refactor this core logic into something common that is shared between -// the two. The main thing that is different is the allocation strategy. - -#ifndef LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H -#define LLVM_CLANG_ANALYSIS_SUPPORT_BUMPVECTOR_H - -#include "llvm/ADT/PointerIntPair.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/type_traits.h" -#include <algorithm> -#include <cstring> -#include <iterator> -#include <memory> - -namespace clang { - -class BumpVectorContext { - llvm::PointerIntPair<llvm::BumpPtrAllocator*, 1> Alloc; -public: - /// Construct a new BumpVectorContext that creates a new BumpPtrAllocator - /// and destroys it when the BumpVectorContext object is destroyed. - BumpVectorContext() : Alloc(new llvm::BumpPtrAllocator(), 1) {} - - BumpVectorContext(BumpVectorContext &&Other) : Alloc(Other.Alloc) { - Other.Alloc.setInt(false); - Other.Alloc.setPointer(nullptr); - } - - /// Construct a new BumpVectorContext that reuses an existing - /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the - /// BumpVectorContext object is destroyed. - BumpVectorContext(llvm::BumpPtrAllocator &A) : Alloc(&A, 0) {} - - ~BumpVectorContext() { - if (Alloc.getInt()) - delete Alloc.getPointer(); - } - - llvm::BumpPtrAllocator &getAllocator() { return *Alloc.getPointer(); } -}; - -template<typename T> -class BumpVector { - T *Begin, *End, *Capacity; -public: - // Default ctor - Initialize to empty. - explicit BumpVector(BumpVectorContext &C, unsigned N) - : Begin(nullptr), End(nullptr), Capacity(nullptr) { - reserve(C, N); - } - - ~BumpVector() { - if (std::is_class<T>::value) { - // Destroy the constructed elements in the vector. - destroy_range(Begin, End); - } - } - - typedef size_t size_type; - typedef ptrdiff_t difference_type; - typedef T value_type; - typedef T* iterator; - typedef const T* const_iterator; - - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - - typedef T& reference; - typedef const T& const_reference; - typedef T* pointer; - typedef const T* const_pointer; - - // forward iterator creation methods. - iterator begin() { return Begin; } - const_iterator begin() const { return Begin; } - iterator end() { return End; } - const_iterator end() const { return End; } - - // reverse iterator creation methods. - reverse_iterator rbegin() { return reverse_iterator(end()); } - const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } - reverse_iterator rend() { return reverse_iterator(begin()); } - const_reverse_iterator rend() const { return const_reverse_iterator(begin());} - - bool empty() const { return Begin == End; } - size_type size() const { return End-Begin; } - - reference operator[](unsigned idx) { - assert(Begin + idx < End); - return Begin[idx]; - } - const_reference operator[](unsigned idx) const { - assert(Begin + idx < End); - return Begin[idx]; - } - - reference front() { - return begin()[0]; - } - const_reference front() const { - return begin()[0]; - } - - reference back() { - return end()[-1]; - } - const_reference back() const { - return end()[-1]; - } - - void pop_back() { - --End; - End->~T(); - } - - T pop_back_val() { - T Result = back(); - pop_back(); - return Result; - } - - void clear() { - if (std::is_class<T>::value) { - destroy_range(Begin, End); - } - End = Begin; - } - - /// data - Return a pointer to the vector's buffer, even if empty(). - pointer data() { - return pointer(Begin); - } - - /// data - Return a pointer to the vector's buffer, even if empty(). - const_pointer data() const { - return const_pointer(Begin); - } - - void push_back(const_reference Elt, BumpVectorContext &C) { - if (End < Capacity) { - Retry: - new (End) T(Elt); - ++End; - return; - } - grow(C); - goto Retry; - } - - /// insert - Insert some number of copies of element into a position. Return - /// iterator to position after last inserted copy. - iterator insert(iterator I, size_t Cnt, const_reference E, - BumpVectorContext &C) { - assert (I >= Begin && I <= End && "Iterator out of bounds."); - if (End + Cnt <= Capacity) { - Retry: - move_range_right(I, End, Cnt); - construct_range(I, I + Cnt, E); - End += Cnt; - return I + Cnt; - } - ptrdiff_t D = I - Begin; - grow(C, size() + Cnt); - I = Begin + D; - goto Retry; - } - - void reserve(BumpVectorContext &C, unsigned N) { - if (unsigned(Capacity-Begin) < N) - grow(C, N); - } - - /// capacity - Return the total number of elements in the currently allocated - /// buffer. - size_t capacity() const { return Capacity - Begin; } - -private: - /// grow - double the size of the allocated memory, guaranteeing space for at - /// least one more element or MinSize if specified. - void grow(BumpVectorContext &C, size_type MinSize = 1); - - void construct_range(T *S, T *E, const T &Elt) { - for (; S != E; ++S) - new (S) T(Elt); - } - - void destroy_range(T *S, T *E) { - while (S != E) { - --E; - E->~T(); - } - } - - void move_range_right(T *S, T *E, size_t D) { - for (T *I = E + D - 1, *IL = S + D - 1; I != IL; --I) { - --E; - new (I) T(*E); - E->~T(); - } - } -}; - -// Define this out-of-line to dissuade the C++ compiler from inlining it. -template <typename T> -void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { - size_t CurCapacity = Capacity-Begin; - size_t CurSize = size(); - size_t NewCapacity = 2*CurCapacity; - if (NewCapacity < MinSize) - NewCapacity = MinSize; - - // Allocate the memory from the BumpPtrAllocator. - T *NewElts = C.getAllocator().template Allocate<T>(NewCapacity); - - // Copy the elements over. - if (Begin != End) { - if (std::is_class<T>::value) { - std::uninitialized_copy(Begin, End, NewElts); - // Destroy the original elements. - destroy_range(Begin, End); - } else { - // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove). - memcpy(NewElts, Begin, CurSize * sizeof(T)); - } - } - - // For now, leak 'Begin'. We can add it back to a freelist in - // BumpVectorContext. - Begin = NewElts; - End = NewElts+CurSize; - Capacity = Begin+NewCapacity; -} - -} // end: clang namespace -#endif |
