diff options
Diffstat (limited to 'clang/include/clang/Analysis')
42 files changed, 6283 insertions, 0 deletions
diff --git a/clang/include/clang/Analysis/Analyses/.#Interval.h b/clang/include/clang/Analysis/Analyses/.#Interval.h new file mode 120000 index 0000000..235903b --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/.#Interval.h @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h b/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h new file mode 120000 index 0000000..235903b --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/.#Interval_flymake.h @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/.#LiveVariables.h b/clang/include/clang/Analysis/Analyses/.#LiveVariables.h new file mode 120000 index 0000000..235903b --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/.#LiveVariables.h @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h b/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h new file mode 120000 index 0000000..235903b --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/.#LiveVariables_flymake.h @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.1585:1347012043
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h new file mode 100644 index 0000000..a61d9e4 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h @@ -0,0 +1,49 @@ +//==- 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 CLANG_ANALYSIS_CFG_REACHABILITY +#define CLANG_ANALYSIS_CFG_REACHABILITY + +#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/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h new file mode 100644 index 0000000..e9a431a --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/Dominators.h @@ -0,0 +1,212 @@ +//==- 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_DOMINATORS_H +#define LLVM_CLANG_DOMINATORS_H + +#include "clang/Analysis/AnalysisContext.h" + +#include "llvm/Module.h" +#include "llvm/ADT/GraphTraits.h" +#include "clang/Analysis/CFG.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DominatorInternals.h" + +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() { + 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= 0) const { + DT->print(OS); + } + +private: + CFG *cfg; +}; + +inline void WriteAsOperand(raw_ostream &OS, const CFGBlock *BB, + bool t) { + OS << "BB#" << BB->getBlockID(); +} + +} // 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/clang/include/clang/Analysis/Analyses/FormatString.h b/clang/include/clang/Analysis/Analyses/FormatString.h new file mode 100644 index 0000000..9ec27ce --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/FormatString.h @@ -0,0 +1,652 @@ +//= 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_FORMAT_H +#define LLVM_CLANG_FORMAT_H + +#include "clang/AST/CanonicalType.h" + +namespace clang { + +//===----------------------------------------------------------------------===// +/// 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); + this->position = position; + } + const char *getPosition() const { + assert(position); + return position; + } + const char *toString() const { return representation; } + + // Overloaded operators for bool like qualities + 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' + AsLongDouble, // 'L' + AsAllocate, // for '%as', GNU extension to C90 scanf + AsMAllocate, // for '%ms', GNU extension to scanf + AsWideChar = AsLong // for '%ls', only makes sense for printf + }; + + LengthModifier() + : Position(0), 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 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, + iArg, + IntArgBeg = cArg, IntArgEnd = iArg, + + oArg, + uArg, + 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 ** + + // Objective-C specific specifiers. + ObjCObjArg, // '@' + ObjCBeg = ObjCObjArg, ObjCEnd = ObjCObjArg, + + // GlibC specific specifiers. + PrintErrno, // 'm' + + PrintfConvBeg = ObjCObjArg, PrintfConvEnd = PrintErrno, + + // ** Scanf-specific ** + ScanListArg, // '[' + ScanfConvBeg = ScanListArg, ScanfConvEnd = ScanListArg + }; + + ConversionSpecifier(bool isPrintf) + : IsPrintf(isPrintf), Position(0), EndScanList(0), kind(InvalidSpecifier) {} + + ConversionSpecifier(bool isPrintf, const char *pos, Kind k) + : IsPrintf(isPrintf), Position(pos), EndScanList(0), kind(k) {} + + const char *getStart() const { + return Position; + } + + StringRef getCharacters() const { + return StringRef(getStart(), getLength()); + } + + bool consumesDataArgument() const { + switch (kind) { + case PrintErrno: + assert(IsPrintf); + 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 isUIntArg() const { return kind >= UIntArgBeg && kind <= UIntArgEnd; } + const char *toString() const; + + bool isPrintfKind() const { return IsPrintf; } + +protected: + bool IsPrintf; + const char *Position; + const char *EndScanList; + Kind kind; +}; + +class ArgTypeResult { +public: + enum Kind { UnknownTy, InvalidTy, SpecificTy, ObjCPointerTy, CPointerTy, + AnyCharTy, CStrTy, WCStrTy, WIntTy }; +private: + const Kind K; + QualType T; + const char *Name; + ArgTypeResult(bool) : K(InvalidTy), Name(0) {} +public: + ArgTypeResult(Kind k = UnknownTy) : K(k), Name(0) {} + ArgTypeResult(Kind k, const char *n) : K(k), Name(n) {} + ArgTypeResult(QualType t) : K(SpecificTy), T(t), Name(0) {} + ArgTypeResult(QualType t, const char *n) : K(SpecificTy), T(t), Name(n) {} + ArgTypeResult(CanQualType t) : K(SpecificTy), T(t), Name(0) {} + + static ArgTypeResult Invalid() { return ArgTypeResult(true); } + + bool isValid() const { return K != InvalidTy; } + + const QualType *getSpecificType() const { + return K == SpecificTy ? &T : 0; + } + + bool matchesType(ASTContext &C, QualType argTy) const; + + bool matchesAnyObjCObjectRef() const { return K == ObjCPointerTy; } + + 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(0),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; + } + + ArgTypeResult 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; + + bool hasStandardLengthModifier() const; + + bool hasStandardConversionSpecifier(const LangOptions &LangOpt) const; + + bool hasStandardLengthConversionCombination() const; +}; + +} // 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, 0, InvalidSpecifier) {} + + PrintfConversionSpecifier(const char *pos, Kind k) + : ConversionSpecifier(true, pos, k) {} + + bool isObjCArg() const { return kind >= ObjCBeg && kind <= ObjCEnd; } + bool isIntArg() const { return kind >= IntArgBeg && kind <= IntArgEnd; } + 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::ArgTypeResult; +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' + OptionalAmount Precision; +public: + PrintfSpecifier() : + FormatSpecifier(/* isPrintf = */ true), + HasThousandsGrouping("'"), IsLeftJustified("-"), HasPlusPrefix("+"), + HasSpacePrefix(" "), HasAlternativeForm("#"), HasLeadingZeroes("0") {} + + 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 = true; + HasThousandsGrouping.setPosition(position); + } + void setIsLeftJustified(const char *position) { + IsLeftJustified = true; + IsLeftJustified.setPosition(position); + } + void setHasPlusPrefix(const char *position) { + HasPlusPrefix = true; + HasPlusPrefix.setPosition(position); + } + void setHasSpacePrefix(const char *position) { + HasSpacePrefix = true; + HasSpacePrefix.setPosition(position); + } + void setHasAlternativeForm(const char *position) { + HasAlternativeForm = true; + HasAlternativeForm.setPosition(position); + } + void setHasLeadingZeros(const char *position) { + HasLeadingZeroes = true; + HasLeadingZeroes.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. + ArgTypeResult 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; } + 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, 0, 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::ArgTypeResult; +using analyze_format_string::LengthModifier; +using analyze_format_string::OptionalAmount; +using analyze_format_string::OptionalFlag; + +class ScanfArgTypeResult : public ArgTypeResult { +public: + enum Kind { UnknownTy, InvalidTy, CStrTy, WCStrTy, PtrToArgTypeResultTy }; +private: + Kind K; + ArgTypeResult A; + const char *Name; + QualType getRepresentativeType(ASTContext &C) const; +public: + ScanfArgTypeResult(Kind k = UnknownTy, const char* n = 0) : K(k), Name(n) {} + ScanfArgTypeResult(ArgTypeResult a, const char *n = 0) + : K(PtrToArgTypeResultTy), A(a), Name(n) { + assert(A.isValid()); + } + + static ScanfArgTypeResult Invalid() { return ScanfArgTypeResult(InvalidTy); } + + bool isValid() const { return K != InvalidTy; } + + bool matchesType(ASTContext& C, QualType argTy) const; + + std::string getRepresentativeTypeName(ASTContext& C) const; +}; + +class ScanfSpecifier : public analyze_format_string::FormatSpecifier { + OptionalFlag SuppressAssignment; // '*' +public: + ScanfSpecifier() : + FormatSpecifier(/* isPrintf = */ false), + SuppressAssignment("*") {} + + void setSuppressAssignment(const char *position) { + SuppressAssignment = true; + 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; + } + + ScanfArgTypeResult getArgType(ASTContext &Ctx) const; + + bool fixType(QualType QT, 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) {} + + // 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); + +bool ParseScanfString(FormatStringHandler &H, + const char *beg, const char *end, const LangOptions &LO); + +} // end analyze_format_string namespace +} // end clang namespace +#endif diff --git a/clang/include/clang/Analysis/Analyses/Interval.h b/clang/include/clang/Analysis/Analyses/Interval.h new file mode 100644 index 0000000..6c0d5cf --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/Interval.h @@ -0,0 +1,50 @@ +//===- Interval.h - Integer Interval 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_INTERVAL_ANALYSIS_H +#define LLVM_CLANG_INTERVAL_ANALYSIS_H + +#include "clang/Analysis/AnalysisContext.h" +#include "clang/AST/Decl.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ImmutableSet.h" + +namespace clang { + +class CFG; +class CFGBlock; +class Stmt; +class DeclRefExpr; +class SourceManager; + +class IntervalAnalysis : public ManagedAnalysis { +public: + + IntervalAnalysis(AnalysisDeclContext &analysisContext); + virtual ~IntervalAnalysis(); + + void runOnAllBlocks(); + + static IntervalAnalysis *create(AnalysisDeclContext &analysisContext) { + return new IntervalAnalysis(analysisContext); + } + + static const void *getTag(); + +private: + AnalysisDeclContext* context; +}; + +} // end namespace clang + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem.hpp new file mode 120000 index 0000000..56b9060 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem.hpp @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.4300:1348200365
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem_flymake.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem_flymake.hpp new file mode 120000 index 0000000..4dc56be --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#EquationSystem_flymake.hpp @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.9390:1348126501
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression.hpp new file mode 120000 index 0000000..4dc56be --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression.hpp @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.9390:1348126501
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression_flymake.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression_flymake.hpp new file mode 120000 index 0000000..4dc56be --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Expression_flymake.hpp @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.9390:1348126501
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Operator_flymake.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Operator_flymake.hpp new file mode 120000 index 0000000..4dc56be --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/.#Operator_flymake.hpp @@ -0,0 +1 @@ +carlo@pc-4w14-0.cs.usyd.edu.au.9390:1348126501
\ No newline at end of file diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp new file mode 100644 index 0000000..5219c9e --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Complete.hpp @@ -0,0 +1,128 @@ +#ifndef COMPLETE_HPP +#define COMPLETE_HPP + +#include <ostream> +#include <istream> + +template<typename T> +T infinity() { } + +template<typename T> +struct Complete { + Complete() + : _value(0), _infinity(false) { } + Complete(const T& value) + : _value(value), _infinity(false) { } + Complete(const T& value, const bool& infinity) + : _value(value), _infinity(infinity) { + if (value == 0 && infinity == true) { + std::cout << "throw exception" << *(char*)NULL; + //throw "Zero infinity? Die die die!"; + } + } + Complete(const Complete& other) + : _value(other._value), _infinity(other._infinity) { } + + Complete& operator=(const Complete& other) { + _value = other._value; + _infinity = other._infinity; + return *this; + } + Complete& operator+=(const Complete& other) { + return (*this) = (*this) + other; + } + Complete& operator-=(const Complete& other) { + return (*this) = (*this) - other; + } + Complete& operator*=(const Complete& other) { + return (*this) = (*this) * other; + } + + Complete operator-() const { + return Complete<T>(- _value, _infinity); + } + Complete operator+(const Complete& other) const { + if (_infinity) { + return *this; + } else if (other._infinity) { + return other; + } else { + return Complete(_value + other._value, false); + } + } + Complete operator-(const Complete& other) const { + return *this + (- other); + } + Complete operator*(const Complete& other) const { + return Complete(_value * other._value, (_infinity || other._infinity)); + } + + bool operator!() const { + return _value == 0; + } + bool operator<(const Complete& other) const { + if (*this == other) + return false; + if (_infinity) { + return _value < 0; + } else if (other._infinity) { + return other._value > 0; + } else { + return _value < other._value; + } + } + bool operator>=(const Complete& other) const { + return !(*this < other); + } + bool operator>(const Complete& other) const { + return other < *this; + } + bool operator<=(const Complete& other) const { + return !(*this > other); + } + bool operator==(const Complete& other) const { + if (_infinity) { + return other._infinity && ((_value < 0 && other._value < 0) || + (_value > 0 && other._value > 0)); + } else { + return !other._infinity && (_value == other._value); + } + } + bool operator!=(const Complete& other) const { + return !(*this == other); + } + + template<typename Z> + friend std::istream& operator<<(std::istream&, Complete<Z>&); + template<typename Z> + friend std::ostream& operator<<(std::ostream&, const Complete<Z>&); + + private: + T _value; + bool _infinity; +}; + +template<typename Z> +std::istream& operator>>(std::istream& cin, Complete<Z>& num) { + Z value; + cin >> value; + num = Complete<Z>(value, false); + return cin; +} + +template<typename Z> +std::ostream& operator<<(std::ostream& cout, const Complete<Z>& num) { + if (num._infinity) { + cout << (num._value > 0 ? "inf" : "-inf"); + } else { + cout << num._value; + } + return cout; +} + +template<> +Complete<int> infinity() { + return Complete<int>(1, true); +} + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp new file mode 100644 index 0000000..701da7c --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/EquationSystem.hpp @@ -0,0 +1,150 @@ +#ifndef EQUATION_SYSTEM_HPP +#define EQUATION_SYSTEM_HPP + +#include <vector> +#include <set> +#include <map> +#include "Operator.hpp" +#include "Expression.hpp" +#include "VariableAssignment.hpp" +#include "IdMap.hpp" + +template<typename Domain> +struct MaxStrategy; + +template<typename Domain> +struct EquationSystem { + EquationSystem() + : _expr_to_var(NULL) { } + + virtual ~EquationSystem() { + for (typename std::set<Expression<Domain>*>::iterator it = _expressions.begin(); + it != _expressions.end(); + ++it) { + delete *it; + } + for (typename std::set<Operator<Domain>*>::iterator it = _operators.begin(); + it != _operators.end(); + ++it) { + delete *it; + } + delete _expr_to_var; + } + + MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*>& arguments) { + unsigned int id = _max_expressions.size(); + Maximum<Domain>* max = new Maximum<Domain>(); + MaxExpression<Domain>* expr = new MaxExpression<Domain>(id, *max, arguments); + _operators.insert(max); + _max_expressions.push_back(expr); + _expressions.insert(expr); + return *expr; + } + MaxExpression<Domain>& maxExpression(unsigned int i) const { + return *_max_expressions[i]; + } + unsigned int maxExpressionCount() const { + return _max_expressions.size(); + } + + Expression<Domain>& expression(Operator<Domain>* op, const std::vector<Expression<Domain>*>& arguments) { + Expression<Domain>* expr = new OperatorExpression<Domain>(*op, arguments); + _operators.insert(op); + _expressions.insert(expr); + return *expr; + } + + Variable<Domain>& variable(const std::string& name) { + if (_variable_names.find(name) == _variable_names.end()) { + // not found - create a new variable and whatnot + unsigned int id = _variables.size(); + Variable<Domain>* var = new Variable<Domain>(id, name); + _variables.push_back(var); + _right_sides.push_back(NULL); + _expressions.insert(var); + _variable_names[name] = var; + return *var; + } else { + return *_variable_names[name]; + } + } + Variable<Domain>& variable(unsigned int id) const { + return *_variables[id]; + } + unsigned int variableCount() const { + return _variables.size(); + } + + Constant<Domain>& constant(const Domain& value) { + Constant<Domain>* constant = new Constant<Domain>(value); + _expressions.insert(constant); + return *constant; + } + + MaxExpression<Domain>* operator[](const Variable<Domain>& var) const { + return _right_sides[var.id()]; + } + MaxExpression<Domain>*& operator[](const Variable<Domain>& var) { + return _right_sides[var.id()]; + } + + void indexMaxExpressions() { + _expr_to_var = new IdMap<MaxExpression<Domain>,Variable<Domain>*>(maxExpressionCount(), NULL); + for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) { + _right_sides[i]->mapTo(*_variables[i], *_expr_to_var); + } + } + + Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const { + if (_expr_to_var) { // we've indexed: + const MaxExpression<Domain>* maxExpr = expr.toMaxExpression();//dynamic_cast<const MaxExpression<Domain>*>(&expr); + if (maxExpr) { + return (*_expr_to_var)[*maxExpr]; + } else { + return NULL; + } + } else { + std::cout << "throw exception" << *(char*)NULL; + return NULL; + //throw "Must index max expressions before attempting lookup"; + } + } + + virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const { + for (unsigned int i = 0, length = _variables.size(); + i < length; + ++i) { + const Variable<Domain>& var = *_variables[i]; + if (l[var] != r[var]) + return false; + } + return true; + } + + void print(std::ostream& cout) const { + for (unsigned int i = 0, length = _variables.size(); + i < length; + ++i) { + cout << *_variables[i] << " = " << *_right_sides[i] << std::endl; + } + } + + private: + std::set<Operator<Domain>*> _operators; + std::set<Expression<Domain>*> _expressions; + std::vector<Variable<Domain>*> _variables; + std::map<std::string, Variable<Domain>*> _variable_names; + IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var; + std::vector<MaxExpression<Domain>*> _max_expressions; + std::vector<MaxExpression<Domain>*> _right_sides; +}; + +template<typename T> +std::ostream& operator<<(std::ostream& cout, const EquationSystem<T>& system) { + system.print(cout); + return cout; +} + +#include "MaxStrategy.hpp" + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp new file mode 100644 index 0000000..7b0f2cf --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Expression.hpp @@ -0,0 +1,198 @@ +#ifndef EXPRESSION_HPP +#define EXPRESSION_HPP + +#include <string> +#include <vector> +#include <sstream> +#include "IdMap.hpp" +#include "Operator.hpp" + +template<typename Domain> +struct VariableAssignment; + +template<typename Domain> +struct MaxStrategy; + +template<typename Domain> +struct Variable; + +template<typename Domain> +struct MaxExpression; + +template<typename Domain> +struct Expression { + virtual ~Expression() { } + + virtual const MaxExpression<Domain>* toMaxExpression() const { + return NULL; + } + + virtual Domain eval(const VariableAssignment<Domain>&) const = 0; + virtual Domain eval(const VariableAssignment<Domain>& rho, + const MaxStrategy<Domain>&) const { + return eval(rho); + } + + virtual void mapTo(Variable<Domain>&, IdMap<MaxExpression<Domain>, Variable<Domain>*>&) const { + } + + virtual void print(std::ostream&) const = 0; +}; + +template<typename Domain> +struct Constant : public Expression<Domain> { + Constant(const Domain& value) + : _value(value) { } + + virtual Domain eval(const VariableAssignment<Domain>&) const { + return _value; + } + + void print(std::ostream& cout) const { + cout << _value; + } + + private: + Domain _value; +}; + +template<typename Domain> +struct Variable : public Expression<Domain> { + Variable(const unsigned int& id, const std::string& name) + : _id(id), _name(name) { } + + unsigned int id() const { + return _id; + } + std::string name() const { + return _name; + } + + virtual Domain eval(const VariableAssignment<Domain>& rho) const { + return rho[*this]; + } + + void print(std::ostream& cout) const { + cout << _name; + } + + private: + const unsigned int _id; + const std::string _name; +}; + +template<typename Domain> +struct OperatorExpression : public Expression<Domain> { + OperatorExpression(const Operator<Domain>& op, const std::vector<Expression<Domain>*>& arguments) + : _operator(op), _arguments(arguments) { } + + virtual Domain eval(const VariableAssignment<Domain>& rho) const { + std::vector<Domain> argumentValues; + for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin(); + it != _arguments.end(); + ++it) { + argumentValues.push_back((*it)->eval(rho)); + } + return _operator.eval(argumentValues); + } + + virtual Domain eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const { + std::vector<Domain> argumentValues; + for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin(); + it != _arguments.end(); + ++it) { + argumentValues.push_back((*it)->eval(rho, strat)); + } + return _operator.eval(argumentValues); + } + + const std::vector<Expression<Domain>*>& arguments() const { + return _arguments; + } + + const Operator<Domain>& op() const { + return _operator; + } + + virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>, Variable<Domain>*>& m) const { + for (unsigned int i = 0, length = _arguments.size(); + i < length; + ++i) { + _arguments[i]->mapTo(v, m); + } + } + + void print(std::ostream& cout) const { + cout << _operator << "("; + for (unsigned int i = 0, length = _arguments.size(); + i < length; + ++i) { + if (i > 0) + cout << ", "; + cout << *_arguments[i]; + } + cout << ")"; + } + + private: + const Operator<Domain>& _operator; + protected: + const std::vector<Expression<Domain>*> _arguments; +}; + +template<typename Domain> +struct MaxExpression : public OperatorExpression<Domain> { + MaxExpression(const unsigned int& id, const Maximum<Domain>& op, const std::vector<Expression<Domain>*>& arguments) + : OperatorExpression<Domain>(op, arguments), _id(id) { } + + + const MaxExpression* toMaxExpression() const { + return this; + } + + virtual Domain eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const { + return this->_arguments[strat.get(*this)]->eval(rho, strat); + } + + unsigned int bestStrategy(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const { + Domain bestValue = this->eval(rho, strat); + unsigned int bestIndex = strat.get(*this); + + for (unsigned int i = 0, length = this->_arguments.size(); + i < length; + ++i) { + const Domain value = this->_arguments[i]->eval(rho, strat); + if (bestValue < value) { + bestValue = value; + bestIndex = i; + } + } + return bestIndex; + } + + virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>, Variable<Domain>*>& m) const { + m[*this] = &v; + for (unsigned int i = 0, length = this->_arguments.size(); + i < length; + ++i) { + this->_arguments[i]->mapTo(v, m); + } + } + + unsigned int id() const { + return _id; + } + + private: + const unsigned int _id; +}; + +template<typename T> +std::ostream& operator<<(std::ostream& cout, const Expression<T>& exp) { + exp.print(cout); + return cout; +} + +#include "VariableAssignment.hpp" + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp new file mode 100644 index 0000000..27c0806 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdMap.hpp @@ -0,0 +1,82 @@ +#ifndef ID_MAP_HPP +#define ID_MAP_HPP + +#include <ostream> + +template<typename T, typename V> +struct IdMap { + IdMap(unsigned int length, V initial) + : _length(length), _assignment(new V[length]) { + for (unsigned int i = 0; i < _length; ++i) { + _assignment[i] = initial; + } + } + IdMap(const IdMap& other) + : _length(other._length), _assignment(new V[other._length]) { + for (unsigned int i = 0; i < _length; ++i) { + _assignment[i] = other._assignment[i]; + } + } + virtual ~IdMap() { + delete[] _assignment; + } + virtual IdMap& operator=(const IdMap& other) { + if (_length != other._length) { + delete[] _assignment; + _length = other._length; + _assignment = new V[_length]; + } + for (unsigned int i = 0; i < _length; ++i) { + _assignment[i] = other._assignment[i]; + } + return *this; + } + virtual const V& operator[] (const T& x) const { + if (x.id() >= _length) { + std::cout << "throw exception" << *(char*)NULL; + //throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + virtual V& operator[] (const T& x) { + if (x.id() >= _length) { + std::cout << "throw exception" << *(char*)NULL; + //throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + + virtual bool operator==(const IdMap& other) const { + if (_length != other._length) + return false; + for (unsigned int i = 0; i < _length; ++i) { + if (_assignment[i] != other._assignment[i]) { + return false; + } + } + return true; + } + virtual bool operator!=(const IdMap& other) const { + return !(*this == other); + } + + template<typename Q,typename Z> + friend std::ostream& operator<<(std::ostream& cout, const IdMap<Q, Z>& rho); + + protected: + unsigned int _length; + V* _assignment; +}; + +template<typename T, typename V> +std::ostream& operator<<(std::ostream& cout, const IdMap<T,V>& rho) { + cout << "{"; + for (unsigned int i = 0; i < rho._length; ++i) { + if (i != 0) cout << ", "; + cout << i << ": " << rho._assignment[i]; + } + cout << "}"; + return cout; +} + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp new file mode 100644 index 0000000..950b1e1 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/IdSet.hpp @@ -0,0 +1,116 @@ +#ifndef IDSET_HPP +#define IDSET_HPP + +#include <ostream> + +#define CELL_TYPE unsigned int +#define CELL_SIZE (8 * sizeof(CELL_TYPE)) +#define DIV_ROUND_UP(NUM, DEM) ((NUM + DEM - 1) / DEM) + +template<typename T> +class IdSet { + public: + IdSet() : _range(0) { } + IdSet(unsigned int length) + : _range(length) { } + + virtual ~IdSet() { + } + + IdSet(const IdSet& other) { + _range = other._range; + _set = other._set; + } + + IdSet& operator=(const IdSet& other) { + _range = other._range; + _set = other._set; + return *this; + } + + void invert() { + for (unsigned int i = 0; i < _range; ++i) { + iterator it = _set.find(i); + if (it == _set.end()) { + _set.insert(i); + } else { + _set.erase(it); + } + } + } + + IdSet inverse() const { + IdSet other(_range); + for (unsigned int i = 0; i < _range; ++i) { + if (_set.find(i) == _set.end()) { + other._set.insert(i); + } + } + return other; + } + + bool contains(const T& obj) const { + return _set.find(obj.id()) != _set.end(); + } + void insert(const T& obj) { + _set.insert(obj.id()); + } + void remove(const T& obj) { + _set.erase(obj.id()); + } + void clear() { + _set.clear(); + } + + void absorb(const IdSet& other) { + for (iterator it = other.begin(), end = other.end(); + it != end; + ++it) { + _set.insert(*it); + } + } + void filter(const IdSet& other) { + for (iterator it = other.begin(), end = other.end(); + it != end; + ++it) { + _set.erase(*it); + } + } + + bool operator==(const IdSet& other) const { + return _set == other._set; + } + bool operator!=(const IdSet& other) const { + return !(*this == other); + } + + typedef std::set<unsigned int>::const_iterator iterator; + iterator begin() const { + return _set.begin(); + } + iterator end() const { + return _set.end(); + } + + unsigned int size() const { + return _set.size(); + } + + private: + unsigned int _range; + std::set<unsigned int> _set; +}; + +template<typename T> +std::ostream& operator<<(std::ostream& cout, const IdSet<T>& set) { + cout << "{"; + for (typename IdSet<T>::iterator it = set.begin(); + it != set.end(); + ++it) { + cout << *it << ", "; + } + cout << "}"; + return cout; +} + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp new file mode 100644 index 0000000..f9af7f2 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Log.hpp @@ -0,0 +1,32 @@ +#ifndef LOG_HPP +#define LOG_HPP + +#include <string> +#include <iostream> +#include <map> +#include <cstdio> + +namespace solver_log { + + struct Logger : public std::ostream { + Logger(std::streambuf*, const std::string&) + : std::ostream(NULL) { } + + bool enabled() const { + return false; + } + + bool enabled(bool) { + return false; + } + + private: + }; + + Logger strategy(std::cerr.rdbuf(), "strategy"); + Logger fixpoint(std::cerr.rdbuf(), "fixpoint"); + Logger debug(std::cerr.rdbuf(), "debug"); + +} + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp new file mode 100644 index 0000000..f5cb0d8 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp @@ -0,0 +1,153 @@ +#ifndef MAX_EXPRESSION_HPP +#define MAX_EXPRESSION_HPP + +#include <ostream> +#include "Expression.hpp" +#include "EquationSystem.hpp" +#include "IdSet.hpp" + +template<typename Domain> +struct MaxStrategy { + virtual ~MaxStrategy() { } + virtual unsigned int get(const MaxExpression<Domain>& e) const = 0; +}; + +unsigned int stack_depth = 1; + +std::string indent() { + std::string result = ""; + for (unsigned int i = 0; i < stack_depth; ++i) { + result += '\t'; + } + return result; +} + +#include "VariableAssignment.hpp" + +template<typename Domain> +struct DynamicVariableAssignment; + +template<typename Domain> +struct DynamicMaxStrategy : public MaxStrategy<Domain> { + DynamicMaxStrategy( + const EquationSystem<Domain>& system + ) : _system(system), + _rho(NULL), + _values(system.maxExpressionCount(), 0), + _stable(system.maxExpressionCount()), + _influence(system.maxExpressionCount(), + IdSet<MaxExpression<Domain> >(system.maxExpressionCount())), + _var_influence(system.variableCount(), + IdSet<MaxExpression<Domain> >(system.maxExpressionCount())) + {} + + void setRho(DynamicVariableAssignment<Domain>& rho) { + _rho = ρ + } + + unsigned int get(const MaxExpression<Domain>& e) const { + solve(e); + return _values[e]; + } + + void invalidate(const Variable<Domain>& v) const { + solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; + _stable.filter(_var_influence[v]); + + for (typename IdSet<MaxExpression<Domain> >::iterator + it = _var_influence[v].begin(), + end = _var_influence[v].end(); + it != end; + ++it) { + solve(_system.maxExpression(*it)); + } + } + +private: + void solve(const MaxExpression<Domain>& x) const { + if (!_stable.contains(x)) { + _stable.insert(x); + solver_log::strategy << indent() << "Stabilise " << x << std::endl; + + stack_depth++; + unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x), + DependencyStrategy(*this, x)); + stack_depth--; + + if (val != _values[x]) { + solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl; + + IdSet<MaxExpression<Domain> > oldInfluence = _influence[x]; + _influence[x].clear(); + _values[x] = val; + + _rho->invalidate(*_system.varFromExpr(x)); + + _stable.filter(oldInfluence); + + for (typename IdSet<MaxExpression<Domain> >::iterator + it = oldInfluence.begin(), + end = oldInfluence.end(); + it != end; + ++it) { + solve(_system.maxExpression(*it)); + } + } else { + solver_log::strategy << indent() << x << " did not change" << std::endl; + } + } else { + solver_log::strategy << indent() << x << " is stable" << std::endl; + } + } + + struct DependencyAssignment : public VariableAssignment<Domain>{ + DependencyAssignment(const DynamicMaxStrategy& strat, + VariableAssignment<Domain>& rho, + const MaxExpression<Domain>& expr) + : _strat(strat), + _rho(rho), + _expr(expr) { + } + const Domain& operator[](const Variable<Domain>& var) const { + _strat._var_influence[var].insert(_expr); + return _rho[var]; + } + private: + const DynamicMaxStrategy& _strat; + VariableAssignment<Domain>& _rho; + const MaxExpression<Domain>& _expr; + }; + + struct DependencyStrategy : public MaxStrategy<Domain> { + DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) + : _strat(strat), + _expr(expr) { + } + unsigned int get(const MaxExpression<Domain>& e) const { + _strat.solve(e); + if (&_expr != &e) { + _strat._influence[e].insert(_expr); + } + return _strat._values[e]; + } + private: + const DynamicMaxStrategy& _strat; + const MaxExpression<Domain>& _expr; + }; + +private: + const EquationSystem<Domain>& _system; + mutable DynamicVariableAssignment<Domain>* _rho; + mutable IdMap<MaxExpression<Domain>,unsigned int> _values; + mutable IdSet<MaxExpression<Domain> > _stable; + mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence; + mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence; +}; + +/*template<typename Domain> +std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) { + strat.print(cout); + return cout; +}*/ + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp new file mode 100644 index 0000000..b67591f --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/Operator.hpp @@ -0,0 +1,168 @@ +#ifndef OPERATOR_HPP +#define OPERATOR_HPP + +#include <vector> + +template<typename Domain> +struct Operator { + virtual ~Operator() { } + + virtual Domain eval(const std::vector<Domain>&) const = 0; + + virtual void print(std::ostream&) const = 0; +}; + +template<typename Domain> +struct Maximum : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = -infinity<Domain>(); + for (typename std::vector<Domain>::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + result = (result < *it ? *it : result); + } + return result; + } + void print(std::ostream& cout) const { + cout << "max"; + } +}; + +template<typename Domain> +struct Minimum : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = infinity<Domain>(); + for (typename std::vector<Domain>::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + result = (*it < result ? *it : result); + } + return result; + } + void print(std::ostream& cout) const { + cout << "min"; + } +}; + +template<typename Domain> +struct Negation : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + if (arguments.size() > 1) + throw "Too many arguments to a negation."; + return -arguments[0]; + } + void print(std::ostream& cout) const { + cout << "-"; + } +}; + +template<typename Domain> +struct Addition : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = 0; + for (typename std::vector<Domain>::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + result += *it; + } + return result; + } + void print(std::ostream& cout) const { + cout << "add"; + } +}; + +template<typename Domain> +struct Subtraction : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = 0; + for (typename std::vector<Domain>::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + if (it == arguments.begin()) + result = *it; + else + result -= *it; + } + return result; + } + void print(std::ostream& cout) const { + cout << "sub"; + } +}; + +template<typename Domain> +struct Multiplication : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = 1; + for (typename std::vector<Domain>::const_iterator it = arguments.begin(), + end = arguments.end(); + it != end; + ++it) { + result *= *it; + } + return result; + } + void print(std::ostream& cout) const { + cout << "mult"; + } +}; + +template<typename Domain> +struct Comma : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + if (arguments[0] == -infinity<Domain>()) { + return -infinity<Domain>(); + } + return arguments[1]; + } + void print(std::ostream& cout) const { + cout << "comma"; + } +}; + +template<typename Domain> +struct Guard : public Operator<Domain> { + virtual Domain eval(const std::vector<Domain>& arguments) const { + Domain result = arguments[2]; + if (arguments[0] < arguments[1]) { + result = -infinity<Domain>(); + } + return result; + } + void print(std::ostream& cout) const { + cout << "guard"; + } +}; + +/*#include "TemplateConstraintMatrix.hpp" + +template<typename Domain> +struct MinimumCostFlow : public Operator<Domain> { + MinimumCostFlow() { + } + Domain solve(const Domain& d) const { + + } + virtual Domain eval(const std::vector<Domain>& arguments) const { + if (arguments.size() != 1) + throw "Incorrect number of arguments."; + return solve(arguments[0]); + } + void print(std::ostream& cout) const { + cout << "minCostFlow"; + } +private: + TemplateConstraintMatrix& constraint; // T + std::vector<Domain> guard; // c + std::vector<std::vector<Domain>> multiplication; //A + unsigned int row; +};*/ + +template<typename T> +std::ostream& operator<<(std::ostream& cout, const Operator<T>& op) { + op.print(cout); + return cout; +} + +#endif diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp new file mode 100644 index 0000000..d2adff5 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp @@ -0,0 +1,98 @@ +#ifndef VARIABLE_ASSIGNMENT_HPP +#define VARIABLE_ASSIGNMENT_HPP + +#include "Expression.hpp" +#include "IdMap.hpp" + +template<typename Domain> +struct VariableAssignment { + virtual ~VariableAssignment() { } + virtual const Domain& operator[](const Variable<Domain>&) const = 0; +}; + +#include "EquationSystem.hpp" + +template<typename Domain> +struct DynamicMaxStrategy; + +template<typename Domain> +struct DynamicVariableAssignment : public VariableAssignment<Domain> { + DynamicVariableAssignment( + const EquationSystem<Domain>& system, + const DynamicMaxStrategy<Domain>& strat + ) : _system(system), + _strategy(strat), + _values(system.variableCount(), infinity<Domain>()), + _stable(system.variableCount()), + _influence(system.variableCount(), + IdSet<Variable<Domain> >(system.variableCount())) + { } + + const Domain& operator[](const Variable<Domain>& var) const { + solve(var); + return _values[var]; + } + + void invalidate(const Variable<Domain>& x) const { + solver_log::fixpoint << indent() << "Invalidating " << x << std::endl; + _stable.remove(x); + _values[x] = infinity<Domain>(); + } + +private: + + void solve(const Variable<Domain>& x) const { + if (!_stable.contains(x)) { + _stable.insert(x); + solver_log::fixpoint << indent() << "Stabilise " << x << std::endl; + + stack_depth++; + Domain val = _system[x]->eval(DependencyAssignment(*this, x), + _strategy); + stack_depth--; + + if (val != _values[x]) { + solver_log::fixpoint << x << " = " << val << std::endl; + + IdSet<Variable<Domain> > oldInfluence = _influence[x]; + _influence[x].clear(); + _values[x] = val; + + _strategy.invalidate(x); + + _stable.filter(oldInfluence); + + for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin(); + it != oldInfluence.end(); + ++it) { + solve(_system.variable(*it)); + } + } else { + solver_log::fixpoint << indent() << x << " did not change" << std::endl; + } + } else { + solver_log::fixpoint << indent() << x << " is stable" << std::endl; + } + } + + struct DependencyAssignment : public VariableAssignment<Domain> { + DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var) + : _assignment(assignment), _var(var) { } + const Domain& operator[](const Variable<Domain>& x) const { + const Domain& result = _assignment[x]; + _assignment._influence[x].insert(_var); + return result; + } + private: + const DynamicVariableAssignment& _assignment; + const Variable<Domain>& _var; + }; + + const EquationSystem<Domain>& _system; + const DynamicMaxStrategy<Domain>& _strategy; + mutable IdMap<Variable<Domain>, Domain> _values; + mutable IdSet<Variable<Domain> > _stable; + mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence; +}; + +#endif diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h new file mode 100644 index 0000000..c9f39b4 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h @@ -0,0 +1,120 @@ +//===- 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_LIVEVARIABLES_H +#define LLVM_CLANG_LIVEVARIABLES_H + +#include "clang/Analysis/AnalysisContext.h" +#include "clang/AST/Decl.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(0), liveDecls(0) {} + + LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts, + llvm::ImmutableSet<const VarDecl *> LiveDecls) + : liveStmts(LiveStmts), liveDecls(LiveDecls) {} + + ~LivenessValues() {} + + 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) {} + }; + + + virtual ~LiveVariables(); + + /// 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/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h new file mode 100644 index 0000000..4e3244e --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h @@ -0,0 +1,111 @@ +//===- 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_POSTORDER_CFGVIEW +#define LLVM_CLANG_POSTORDER_CFGVIEW + +#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. + 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 == 0) + return false; // if an edge is trivially false. + if (VisitedBlockIDs.test(Block->getBlockID())) + return false; + VisitedBlockIDs.set(Block->getBlockID()); + return 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; + + PostOrderCFGView(const CFG *cfg); + + iterator begin() { return Blocks.rbegin(); } + iterator end() { return Blocks.rend(); } + + bool empty() { 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/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h b/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h new file mode 100644 index 0000000..cb73850 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h @@ -0,0 +1,45 @@ +//== 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_PSEUDOCONSTANTANALYSIS +#define LLVM_CLANG_ANALYSIS_PSEUDOCONSTANTANALYSIS + +#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/clang/include/clang/Analysis/Analyses/ReachableCode.h b/clang/include/clang/Analysis/Analyses/ReachableCode.h new file mode 100644 index 0000000..30c5b2d --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/ReachableCode.h @@ -0,0 +1,56 @@ +//===- 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_REACHABLECODE_H +#define LLVM_CLANG_REACHABLECODE_H + +#include "clang/Basic/SourceLocation.h" + +//===----------------------------------------------------------------------===// +// Forward declarations. +//===----------------------------------------------------------------------===// + +namespace llvm { + class BitVector; +} + +namespace clang { + class AnalysisDeclContext; + class CFGBlock; +} + +//===----------------------------------------------------------------------===// +// API. +//===----------------------------------------------------------------------===// + +namespace clang { +namespace reachable_code { + +class Callback { + virtual void anchor(); +public: + virtual ~Callback() {} + virtual void HandleUnreachable(SourceLocation L, 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, Callback &CB); + +}} // end namespace clang::reachable_code + +#endif diff --git a/clang/include/clang/Analysis/Analyses/ThreadSafety.h b/clang/include/clang/Analysis/Analyses/ThreadSafety.h new file mode 100644 index 0000000..26e258d --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/ThreadSafety.h @@ -0,0 +1,159 @@ +//===- 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#threadsafety for more +// information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_THREADSAFETY_H +#define LLVM_CLANG_THREADSAFETY_H + +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/StringRef.h" + +namespace clang { +namespace thread_safety { + +/// 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()) +}; + +/// 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 +}; + +/// 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 +}; + +/// Handler class for thread safety warnings. +class ThreadSafetyHandler { +public: + typedef llvm::StringRef Name; + virtual ~ThreadSafetyHandler(); + + /// Warn about lock expressions which fail to resolve to lockable objects. + /// \param Loc -- the SourceLocation of the unresolved expression. + virtual void handleInvalidLockExp(SourceLocation Loc) {} + + /// Warn about unlock function calls that do not have a prior matching lock + /// expression. + /// \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(Name LockName, SourceLocation Loc) {} + + /// Warn about lock function calls for locks which are already held. + /// \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(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 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(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 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(Name LockName, SourceLocation Loc1, + SourceLocation Loc2) {} + + /// Warn when a protected operation occurs while no locks are held. + /// \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(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 LockName -- A StringRef name for the lock expression, to be printed + /// in the error message. + /// \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 handleMutexNotHeld(const NamedDecl *D, + ProtectedOperationKind POK, Name LockName, + LockKind LK, 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 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(Name FunName, Name LockName, + SourceLocation Loc) {} +}; + +/// \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); + +/// \brief Helper function that returns a LockKind required for the given level +/// of access. +LockKind getLockKindFromAccessKind(AccessKind AK); + +}} // end namespace clang::thread_safety +#endif diff --git a/clang/include/clang/Analysis/Analyses/UninitializedValues.h b/clang/include/clang/Analysis/Analyses/UninitializedValues.h new file mode 100644 index 0000000..4ee6698 --- /dev/null +++ b/clang/include/clang/Analysis/Analyses/UninitializedValues.h @@ -0,0 +1,53 @@ +//= 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_UNINIT_VALS_H +#define LLVM_CLANG_UNINIT_VALS_H + +namespace clang { + +class AnalysisDeclContext; +class CFG; +class DeclContext; +class Expr; +class VarDecl; + +class UninitVariablesHandler { +public: + UninitVariablesHandler() {} + virtual ~UninitVariablesHandler(); + + /// Called when the uninitialized variable is used at the given expression. + virtual void handleUseOfUninitVariable(const Expr *ex, + const VarDecl *vd, + bool isAlwaysUninit) {} + + /// 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/clang/include/clang/Analysis/AnalysisContext.h b/clang/include/clang/Analysis/AnalysisContext.h new file mode 100644 index 0000000..6b6f8ef --- /dev/null +++ b/clang/include/clang/Analysis/AnalysisContext.h @@ -0,0 +1,432 @@ +//=== 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/AST/Expr.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/IntrusiveRefCntPtr.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Allocator.h" + +namespace clang { + +class Decl; +class Stmt; +class CFGReverseBlockReachabilityAnalysis; +class CFGStmtMap; +class LiveVariables; +class ManagedAnalysis; +class ParentMap; +class PseudoConstantAnalysis; +class ImplicitParamDecl; +class LocationContextManager; +class StackFrameContext; +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 *D; + + // TranslationUnit is NULL if we don't have multiple translation units. + idx::TranslationUnit *TU; + + OwningPtr<CFG> cfg, completeCFG; + OwningPtr<CFGStmtMap> cfgStmtMap; + + CFG::BuildOptions cfgBuildOptions; + CFG::BuildOptions::ForcedBlkExprs *forcedBlkExprs; + + bool builtCFG, builtCompleteCFG; + + OwningPtr<LiveVariables> liveness; + OwningPtr<LiveVariables> relaxedLiveness; + OwningPtr<ParentMap> PM; + OwningPtr<PseudoConstantAnalysis> PCA; + OwningPtr<CFGReverseBlockReachabilityAnalysis> CFA; + + llvm::BumpPtrAllocator A; + + llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; + + void *ManagedAnalyses; + +public: + AnalysisDeclContext(AnalysisDeclContextManager *Mgr, + const Decl *D, + idx::TranslationUnit *TU); + + AnalysisDeclContext(AnalysisDeclContextManager *Mgr, + const Decl *D, + idx::TranslationUnit *TU, + const CFG::BuildOptions &BuildOptions); + + ~AnalysisDeclContext(); + + ASTContext &getASTContext() { return D->getASTContext(); } + const Decl *getDecl() const { return D; } + + idx::TranslationUnit *getTranslationUnit() const { return TU; } + + /// 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); + + Stmt *getBody() 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; + + std::pair<referenced_decls_iterator, 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); + + /// 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; } + + idx::TranslationUnit *getTranslationUnit() const { + return Ctx->getTranslationUnit(); + } + + 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; + const StackFrameContext * + getStackFrameForDeclContext(const DeclContext *DC) const; + + virtual void Profile(llvm::FoldingSetNodeID &ID) = 0; + + static bool classof(const LocationContext*) { return true; } + +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() {} + + const Stmt *getCallSite() const { return CallSite; } + + const CFGBlock *getCallSiteBlock() const { return Block; } + + unsigned getIndex() const { return Index; } + + void Profile(llvm::FoldingSetNodeID &ID); + + 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() {} + + void Profile(llvm::FoldingSetNodeID &ID); + + 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 { + // FIXME: Add back context-sensivity (we don't want libAnalysis to know + // about MemRegion). + const BlockDecl *BD; + + friend class LocationContextManager; + + BlockInvocationContext(AnalysisDeclContext *ctx, + const LocationContext *parent, + const BlockDecl *bd) + : LocationContext(Block, ctx, parent), BD(bd) {} + +public: + ~BlockInvocationContext() {} + + const BlockDecl *getBlockDecl() const { return BD; } + + void Profile(llvm::FoldingSetNodeID &ID); + + static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, + const LocationContext *parent, const BlockDecl *bd) { + ProfileCommon(ID, Block, ctx, parent, bd); + } + + 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); + + /// 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; + +public: + AnalysisDeclContextManager(bool useUnoptimizedCFG = false, + bool addImplicitDtors = false, + bool addInitializers = false); + + ~AnalysisDeclContextManager(); + + AnalysisDeclContext *getContext(const Decl *D, idx::TranslationUnit *TU = 0); + + bool getUseUnoptimizedCFG() const { + return !cfgBuildOptions.PruneTriviallyFalseEdges; + } + + CFG::BuildOptions &getCFGBuildOptions() { + return cfgBuildOptions; + } + + 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(Decl const *D, + idx::TranslationUnit *TU) { + return LocContexts.getStackFrame(getContext(D, TU), 0, 0, 0, 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/clang/include/clang/Analysis/AnalysisDiagnostic.h b/clang/include/clang/Analysis/AnalysisDiagnostic.h new file mode 100644 index 0000000..d4e1f5f --- /dev/null +++ b/clang/include/clang/Analysis/AnalysisDiagnostic.h @@ -0,0 +1,28 @@ +//===--- 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_DIAGNOSTICANALYSIS_H +#define LLVM_CLANG_DIAGNOSTICANALYSIS_H + +#include "clang/Basic/Diagnostic.h" + +namespace clang { + namespace diag { + enum { +#define DIAG(ENUM,FLAGS,DEFAULT_MAPPING,DESC,GROUP,\ + SFINAE,ACCESS,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/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h new file mode 100644 index 0000000..27b22b8 --- /dev/null +++ b/clang/include/clang/Analysis/CFG.h @@ -0,0 +1,938 @@ +//===--- 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_CFG_H +#define LLVM_CLANG_CFG_H + +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/BitVector.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/Support/BumpVector.h" +#include "clang/Basic/SourceLocation.h" +#include <cassert> +#include <iterator> + +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; + +/// CFGElement - Represents a top-level expression in a basic block. +class CFGElement { +public: + enum Kind { + // main kind + Invalid, + Statement, + Initializer, + // dtor kind + AutomaticObjectDtor, + 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 = 0) + : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), + Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {} + +public: + CFGElement() {} + + Kind getKind() const { + unsigned x = Data2.getInt(); + x <<= 2; + x |= Data1.getInt(); + return (Kind) x; + } + + bool isValid() const { return getKind() != Invalid; } + + operator bool() const { return isValid(); } + + template<class ElemTy> const ElemTy *getAs() const { + if (llvm::isa<ElemTy>(this)) + return static_cast<const ElemTy*>(this); + return 0; + } + + static bool classof(const CFGElement *E) { return true; } +}; + +class CFGStmt : public CFGElement { +public: + CFGStmt(Stmt *S) : CFGElement(Statement, S) {} + + const Stmt *getStmt() const { + return static_cast<const Stmt *>(Data1.getPointer()); + } + + static bool classof(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()); + } + + static bool classof(const CFGElement *E) { + return E->getKind() == Initializer; + } +}; + +/// CFGImplicitDtor - Represents C++ object destructor implicitly generated +/// by compiler on various occasions. +class CFGImplicitDtor : public CFGElement { +protected: + CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = 0) + : CFGElement(kind, data1, data2) { + assert(kind >= DTOR_BEGIN && kind <= DTOR_END); + } + +public: + const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; + bool isNoReturn(ASTContext &astContext) const; + + static bool classof(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()); + } + + static bool classof(const CFGElement *elem) { + return elem->getKind() == AutomaticObjectDtor; + } +}; + +/// 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()); + } + + static bool classof(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, 0) {} + + const FieldDecl *getFieldDecl() const { + return static_cast<const FieldDecl*>(Data1.getPointer()); + } + + static bool classof(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, 0) {} + + const CXXBindTemporaryExpr *getBindTemporaryExpr() const { + return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); + } + + static bool classof(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(); } + + 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; + + 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); + } + + CFGElement front() const { return Impl.back(); } + CFGElement 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; + + /// Predecessors/Successors - Keep track of the predecessor / successor + /// CFG blocks. + typedef BumpVector<CFGBlock*> 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(NULL), Terminator(NULL), LoopTarget(NULL), + BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false), + Parent(parent) {} + ~CFGBlock() {} + + // 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() { + IgnoreDefaultsWithCoveredEnums = 0; + } + + 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) {} + + 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(Stmt *Statement) { Terminator = Statement; } + 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(); + + const Stmt *getTerminatorCondition() const { + return const_cast<CFGBlock*>(this)->getTerminatorCondition(); + } + + 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 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 addSuccessor(CFGBlock *Block, BumpVectorContext &C) { + if (Block) + Block->Preds.push_back(this, C); + Succs.push_back(Block, 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 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); + } + + // 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, CFGElement(), C)); + } + iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { + *I = CFGAutomaticObjDtor(VD, S); + return ++I; + } +}; + +/// 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 { + llvm::BitVector alwaysAddMask; + public: + typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs; + ForcedBlkExprs **forcedBlkExprs; + + bool PruneTriviallyFalseEdges; + bool AddEHEdges; + bool AddInitializers; + bool AddImplicitDtors; + + 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() + : alwaysAddMask(Stmt::lastStmtConstant, false) + ,forcedBlkExprs(0), PruneTriviallyFalseEdges(true) + ,AddEHEdges(false) + ,AddInitializers(false) + ,AddImplicitDtors(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 const 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. The responsibility to free the + /// constructed CFG belongs to the caller. + static 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); + } + + //===--------------------------------------------------------------------===// + // 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 (const CFGStmt *stmt = BI->getAs<CFGStmt>()) + O(const_cast<Stmt*>(stmt->getStmt())); + } + } + + //===--------------------------------------------------------------------===// + // CFG Introspection. + //===--------------------------------------------------------------------===// + + struct BlkExprNumTy { + const signed Idx; + explicit BlkExprNumTy(signed idx) : Idx(idx) {} + explicit BlkExprNumTy() : Idx(-1) {} + operator bool() const { return Idx >= 0; } + operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; } + }; + + bool isBlkExpr(const Stmt *S) { return getBlkExprNum(S); } + bool isBlkExpr(const Stmt *S) const { + return const_cast<CFG*>(this)->isBlkExpr(S); + } + BlkExprNumTy getBlkExprNum(const Stmt *S); + unsigned getNumBlkExprs(); + + /// 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(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0), + BlkExprMap(NULL), Blocks(BlkBVC, 10) {} + + ~CFG(); + + 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; + + // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h. + // It represents a map from Expr* to integers to record the set of + // block-level expressions and their "statement number" in the CFG. + void * BlkExprMap; + + 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; + +}; +} // 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<const ::clang::CFGTerminator> { + typedef const ::clang::Stmt *SimpleType; + static SimpleType getSimplifiedValue(const ::clang::CFGTerminator &Val) { + return Val.getStmt(); + } +}; + +template <> struct simplify_type< ::clang::CFGTerminator> { + typedef ::clang::Stmt *SimpleType; + static SimpleType getSimplifiedValue(const ::clang::CFGTerminator &Val) { + return const_cast<SimpleType>(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 diff --git a/clang/include/clang/Analysis/CFGStmtMap.h b/clang/include/clang/Analysis/CFGStmtMap.h new file mode 100644 index 0000000..6e8e140 --- /dev/null +++ b/clang/include/clang/Analysis/CFGStmtMap.h @@ -0,0 +1,52 @@ +//===--- 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_CFGSTMTMAP_H +#define LLVM_CLANG_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/clang/include/clang/Analysis/CallGraph.h b/clang/include/clang/Analysis/CallGraph.h new file mode 100644 index 0000000..9b68073 --- /dev/null +++ b/clang/include/clang/Analysis/CallGraph.h @@ -0,0 +1,257 @@ +//== 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 +#define LLVM_CLANG_ANALYSIS_CALLGRAPH + +#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; + +/// \class 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 global functions - + /// 'main' or functions accessible from other translation units. + CallGraphNode *Root; + + /// The list of nodes that have no parent. These are unreachable from Root. + /// Declarations can get to this list due to impressions in the graph, for + /// example, we do not track functions whose addresses were taken. + llvm::SetVector<CallGraphNode *> ParentlessNodes; + +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; + nodes_iterator parentless_begin() { return ParentlessNodes.begin(); } + nodes_iterator parentless_end() { return ParentlessNodes.end(); } + const_nodes_iterator + parentless_begin() const { return ParentlessNodes.begin(); } + const_nodes_iterator + parentless_end() const { return ParentlessNodes.end(); } + + void print(raw_ostream &os) const; + void dump() const; + void viewGraph() const; + + /// Part of recursive declaration visitation. + bool VisitFunctionDecl(FunctionDecl *FD) { + // We skip function template definitions, as their semantics is + // only determined when they are instantiated. + if (includeInGraph(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)) + addNodeForDecl(MD, true); + return true; + } + +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. + // Small vector might be more efficient since we are only tracking functions + // whose definition is in the current TU. + llvm::SmallVector<CallRecord, 5> CalledFunctions; + +public: + CallGraphNode(Decl *D) : FD(D) {} + + typedef llvm::SmallVector<CallRecord, 5>::iterator iterator; + typedef llvm::SmallVector<CallRecord, 5>::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); + CG->ParentlessNodes.remove(N); + } + + Decl *getDecl() const { return FD; } + + StringRef getName() const; + + 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/clang/include/clang/Analysis/DomainSpecific/CocoaConventions.h b/clang/include/clang/Analysis/DomainSpecific/CocoaConventions.h new file mode 100644 index 0000000..e6a2f13 --- /dev/null +++ b/clang/include/clang/Analysis/DomainSpecific/CocoaConventions.h @@ -0,0 +1,42 @@ +//===- 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_DS_COCOA +#define LLVM_CLANG_ANALYSIS_DS_COCOA + +#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/clang/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/clang/include/clang/Analysis/FlowSensitive/DataflowSolver.h new file mode 100644 index 0000000..017da63 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -0,0 +1,343 @@ +//===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- 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 skeleton code for implementing dataflow analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER +#define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER + +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/ProgramPoint.h" +#include "clang/Analysis/FlowSensitive/DataflowValues.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" +#include "functional" // STL + +namespace clang { + +//===----------------------------------------------------------------------===// +/// DataflowWorkListTy - Data structure representing the worklist used for +/// dataflow algorithms. +//===----------------------------------------------------------------------===// + +class DataflowWorkListTy { + llvm::DenseMap<const CFGBlock*, unsigned char> BlockSet; + SmallVector<const CFGBlock *, 10> BlockQueue; +public: + /// enqueue - Add a block to the worklist. Blocks already on the + /// worklist are not added a second time. + void enqueue(const CFGBlock *B) { + unsigned char &x = BlockSet[B]; + if (x == 1) + return; + x = 1; + BlockQueue.push_back(B); + } + + /// dequeue - Remove a block from the worklist. + const CFGBlock *dequeue() { + assert(!BlockQueue.empty()); + const CFGBlock *B = BlockQueue.back(); + BlockQueue.pop_back(); + BlockSet[B] = 0; + return B; + } + + /// isEmpty - Return true if the worklist is empty. + bool isEmpty() const { return BlockQueue.empty(); } +}; + +//===----------------------------------------------------------------------===// +// BlockItrTraits - Traits classes that allow transparent iteration +// over successors/predecessors of a block depending on the direction +// of our dataflow analysis. +//===----------------------------------------------------------------------===// + +namespace dataflow { +template<typename Tag> struct ItrTraits {}; + +template <> struct ItrTraits<forward_analysis_tag> { + typedef CFGBlock::const_pred_iterator PrevBItr; + typedef CFGBlock::const_succ_iterator NextBItr; + typedef CFGBlock::const_iterator StmtItr; + + static PrevBItr PrevBegin(const CFGBlock *B) { return B->pred_begin(); } + static PrevBItr PrevEnd(const CFGBlock *B) { return B->pred_end(); } + + static NextBItr NextBegin(const CFGBlock *B) { return B->succ_begin(); } + static NextBItr NextEnd(const CFGBlock *B) { return B->succ_end(); } + + static StmtItr StmtBegin(const CFGBlock *B) { return B->begin(); } + static StmtItr StmtEnd(const CFGBlock *B) { return B->end(); } + + static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) { + return BlockEdge(Prev, B, 0); + } + + static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) { + return BlockEdge(B, Next, 0); + } +}; + +template <> struct ItrTraits<backward_analysis_tag> { + typedef CFGBlock::const_succ_iterator PrevBItr; + typedef CFGBlock::const_pred_iterator NextBItr; + typedef CFGBlock::const_reverse_iterator StmtItr; + + static PrevBItr PrevBegin(const CFGBlock *B) { return B->succ_begin(); } + static PrevBItr PrevEnd(const CFGBlock *B) { return B->succ_end(); } + + static NextBItr NextBegin(const CFGBlock *B) { return B->pred_begin(); } + static NextBItr NextEnd(const CFGBlock *B) { return B->pred_end(); } + + static StmtItr StmtBegin(const CFGBlock *B) { return B->rbegin(); } + static StmtItr StmtEnd(const CFGBlock *B) { return B->rend(); } + + static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) { + return BlockEdge(B, Prev, 0); + } + + static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) { + return BlockEdge(Next, B, 0); + } +}; +} // end namespace dataflow + +//===----------------------------------------------------------------------===// +/// DataflowSolverTy - Generic dataflow solver. +//===----------------------------------------------------------------------===// + +template <typename _DFValuesTy, // Usually a subclass of DataflowValues + typename _TransferFuncsTy, + typename _MergeOperatorTy, + typename _Equal = std::equal_to<typename _DFValuesTy::ValTy> > +class DataflowSolver { + + //===----------------------------------------------------===// + // Type declarations. + //===----------------------------------------------------===// + +public: + typedef _DFValuesTy DFValuesTy; + typedef _TransferFuncsTy TransferFuncsTy; + typedef _MergeOperatorTy MergeOperatorTy; + + typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag; + typedef typename _DFValuesTy::ValTy ValTy; + typedef typename _DFValuesTy::EdgeDataMapTy EdgeDataMapTy; + typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; + + typedef dataflow::ItrTraits<AnalysisDirTag> ItrTraits; + typedef typename ItrTraits::NextBItr NextBItr; + typedef typename ItrTraits::PrevBItr PrevBItr; + typedef typename ItrTraits::StmtItr StmtItr; + + //===----------------------------------------------------===// + // External interface: constructing and running the solver. + //===----------------------------------------------------===// + +public: + DataflowSolver(DFValuesTy& d) : D(d), TF(d.getAnalysisData()) {} + ~DataflowSolver() {} + + /// runOnCFG - Computes dataflow values for all blocks in a CFG. + void runOnCFG(CFG& cfg, bool recordStmtValues = false) { + // Set initial dataflow values and boundary conditions. + D.InitializeValues(cfg); + // Solve the dataflow equations. This will populate D.EdgeDataMap + // with dataflow values. + SolveDataflowEquations(cfg, recordStmtValues); + } + + /// runOnBlock - Computes dataflow values for a given block. This + /// should usually be invoked only after previously computing + /// dataflow values using runOnCFG, as runOnBlock is intended to + /// only be used for querying the dataflow values within a block + /// with and Observer object. + void runOnBlock(const CFGBlock *B, bool recordStmtValues) { + BlockDataMapTy& M = D.getBlockDataMap(); + typename BlockDataMapTy::iterator I = M.find(B); + + if (I != M.end()) { + TF.getVal().copyValues(I->second); + ProcessBlock(B, recordStmtValues, AnalysisDirTag()); + } + } + + void runOnBlock(const CFGBlock &B, bool recordStmtValues) { + runOnBlock(&B, recordStmtValues); + } + void runOnBlock(CFG::iterator &I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } + void runOnBlock(CFG::const_iterator &I, bool recordStmtValues) { + runOnBlock(*I, recordStmtValues); + } + + void runOnAllBlocks(const CFG& cfg, bool recordStmtValues = false) { + for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) + runOnBlock(I, recordStmtValues); + } + + //===----------------------------------------------------===// + // Internal solver logic. + //===----------------------------------------------------===// + +private: + + /// SolveDataflowEquations - Perform the actual worklist algorithm + /// to compute dataflow values. + void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) { + EnqueueBlocksOnWorklist(cfg, AnalysisDirTag()); + + while (!WorkList.isEmpty()) { + const CFGBlock *B = WorkList.dequeue(); + ProcessMerge(cfg, B); + ProcessBlock(B, recordStmtValues, AnalysisDirTag()); + UpdateEdges(cfg, B, TF.getVal()); + } + } + + void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::forward_analysis_tag) { + // Enqueue all blocks to ensure the dataflow values are computed + // for every block. Not all blocks are guaranteed to reach the exit block. + for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) + WorkList.enqueue(&**I); + } + + void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::backward_analysis_tag) { + // Enqueue all blocks to ensure the dataflow values are computed + // for every block. Not all blocks are guaranteed to reach the exit block. + // Enqueue in reverse order since that will more likely match with + // the order they should ideally processed by the dataflow algorithm. + for (CFG::reverse_iterator I=cfg.rbegin(), E=cfg.rend(); I!=E; ++I) + WorkList.enqueue(&**I); + } + + void ProcessMerge(CFG& cfg, const CFGBlock *B) { + ValTy& V = TF.getVal(); + TF.SetTopValue(V); + + // Merge dataflow values from all predecessors of this block. + MergeOperatorTy Merge; + + EdgeDataMapTy& M = D.getEdgeDataMap(); + bool firstMerge = true; + bool noEdges = true; + for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){ + + CFGBlock *PrevBlk = *I; + + if (!PrevBlk) + continue; + + typename EdgeDataMapTy::iterator EI = + M.find(ItrTraits::PrevEdge(B, PrevBlk)); + + if (EI != M.end()) { + noEdges = false; + if (firstMerge) { + firstMerge = false; + V.copyValues(EI->second); + } + else + Merge(V, EI->second); + } + } + + bool isInitialized = true; + typename BlockDataMapTy::iterator BI = D.getBlockDataMap().find(B); + if(BI == D.getBlockDataMap().end()) { + isInitialized = false; + BI = D.getBlockDataMap().insert( std::make_pair(B,ValTy()) ).first; + } + // If no edges have been found, it means this is the first time the solver + // has been called on block B, we copy the initialization values (if any) + // as current value for V (which will be used as edge data) + if(noEdges && isInitialized) + Merge(V, BI->second); + + // Set the data for the block. + BI->second.copyValues(V); + } + + /// ProcessBlock - Process the transfer functions for a given block. + void ProcessBlock(const CFGBlock *B, bool recordStmtValues, + dataflow::forward_analysis_tag) { + + TF.setCurrentBlock(B); + + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { + CFGElement El = *I; + if (const CFGStmt *S = El.getAs<CFGStmt>()) + ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag()); + } + + TF.VisitTerminator(const_cast<CFGBlock*>(B)); + } + + void ProcessBlock(const CFGBlock *B, bool recordStmtValues, + dataflow::backward_analysis_tag) { + + TF.setCurrentBlock(B); + + TF.VisitTerminator(const_cast<CFGBlock*>(B)); + + for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { + CFGElement El = *I; + if (const CFGStmt *S = El.getAs<CFGStmt>()) + ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag()); + } + } + + void ProcessStmt(const Stmt *S, bool record, dataflow::forward_analysis_tag) { + if (record) D.getStmtDataMap()[S] = TF.getVal(); + TF.BlockStmt_Visit(const_cast<Stmt*>(S)); + } + + void ProcessStmt(const Stmt *S, bool record, dataflow::backward_analysis_tag){ + TF.BlockStmt_Visit(const_cast<Stmt*>(S)); + if (record) D.getStmtDataMap()[S] = TF.getVal(); + } + + /// UpdateEdges - After processing the transfer functions for a + /// block, update the dataflow value associated with the block's + /// outgoing/incoming edges (depending on whether we do a + // forward/backward analysis respectively) + void UpdateEdges(CFG& cfg, const CFGBlock *B, ValTy& V) { + for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I) + if (CFGBlock *NextBlk = *I) + UpdateEdgeValue(ItrTraits::NextEdge(B, NextBlk),V, NextBlk); + } + + /// UpdateEdgeValue - Update the value associated with a given edge. + void UpdateEdgeValue(BlockEdge E, ValTy& V, const CFGBlock *TargetBlock) { + EdgeDataMapTy& M = D.getEdgeDataMap(); + typename EdgeDataMapTy::iterator I = M.find(E); + + if (I == M.end()) { // First computed value for this edge? + M[E].copyValues(V); + WorkList.enqueue(TargetBlock); + } + else if (!_Equal()(V,I->second)) { + I->second.copyValues(V); + WorkList.enqueue(TargetBlock); + } + } + +private: + DFValuesTy& D; + DataflowWorkListTy WorkList; + TransferFuncsTy TF; +}; + +} // end namespace clang +#endif diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h b/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h new file mode 100644 index 0000000..f86b2b0 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -0,0 +1,172 @@ +//===--- 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/clang/include/clang/Analysis/ProgramPoint.h b/clang/include/clang/Analysis/ProgramPoint.h new file mode 100644 index 0000000..aa7a33c --- /dev/null +++ b/clang/include/clang/Analysis/ProgramPoint.h @@ -0,0 +1,490 @@ +//==- 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_PROGRAM_POINT +#define LLVM_CLANG_ANALYSIS_PROGRAM_POINT + +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/CFG.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/Support/Casting.h" +#include "llvm/ADT/StringRef.h" +#include <cassert> +#include <utility> +#include <string> + +namespace clang { + +class AnalysisDeclContext; +class FunctionDecl; +class LocationContext; +class ProgramPointTag; + +class ProgramPoint { +public: + enum Kind { BlockEdgeKind, + BlockEntranceKind, + BlockExitKind, + PreStmtKind, + PostStmtKind, + PreLoadKind, + PostLoadKind, + PreStoreKind, + PostStoreKind, + PostPurgeDeadSymbolsKind, + PostConditionKind, + PostLValueKind, + PostInitializerKind, + CallEnterKind, + CallExitKind, + MinPostStmtKind = PostStmtKind, + MaxPostStmtKind = CallExitKind, + EpsilonKind}; + +private: + llvm::PointerIntPair<const void *, 2, unsigned> 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; + + const ProgramPointTag *Tag; + + ProgramPoint(); + +protected: + ProgramPoint(const void *P, + Kind k, + const LocationContext *l, + const ProgramPointTag *tag = 0) + : Data1(P, ((unsigned) k) & 0x3), + Data2(0, (((unsigned) k) >> 2) & 0x3), + L(l, (((unsigned) k) >> 4) & 0x3), + Tag(tag) { + assert(getKind() == k); + assert(getLocationContext() == l); + assert(getData1() == P); + } + + ProgramPoint(const void *P1, + const void *P2, + Kind k, + const LocationContext *l, + const ProgramPointTag *tag = 0) + : Data1(P1, ((unsigned) k) & 0x3), + Data2(P2, (((unsigned) k) >> 2) & 0x3), + L(l, (((unsigned) k) >> 4) & 0x3), + Tag(tag) {} + +protected: + const void *getData1() const { return Data1.getPointer(); } + 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); + } + + Kind getKind() const { + unsigned x = L.getInt(); + x <<= 2; + x |= Data2.getInt(); + x <<= 2; + x |= Data1.getInt(); + return (Kind) x; + } + + const ProgramPointTag *getTag() const { return Tag; } + + 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(); + } + + static bool classof(const ProgramPoint*) { return true; } + + 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(Tag); + } + + 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 = 0) + : ProgramPoint(B, BlockEntranceKind, L, tag) { + assert(B && "BlockEntrance requires non-null block"); + } + + const CFGBlock *getBlock() const { + return reinterpret_cast<const CFGBlock*>(getData1()); + } + + const CFGElement getFirstElement() const { + const CFGBlock *B = getBlock(); + return B->empty() ? CFGElement() : B->front(); + } + + static bool classof(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(); + } + + static bool classof(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) {} + + const Stmt *getStmt() const { return (const Stmt*) getData1(); } + + template <typename T> + const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); } + + static bool classof(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 = 0) + : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} + + const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PreStmtKind; + } +}; + +class PostStmt : public StmtPoint { +protected: + PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, + const ProgramPointTag *tag = 0) + : StmtPoint(S, data, k, L, tag) {} + +public: + explicit PostStmt(const Stmt *S, Kind k, + const LocationContext *L, const ProgramPointTag *tag = 0) + : StmtPoint(S, NULL, k, L, tag) {} + + explicit PostStmt(const Stmt *S, const LocationContext *L, + const ProgramPointTag *tag = 0) + : StmtPoint(S, NULL, PostStmtKind, L, tag) {} + + static bool classof(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 = 0) + : PostStmt(S, PostConditionKind, L, tag) {} + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostConditionKind; + } +}; + +class LocationCheck : public StmtPoint { +protected: + LocationCheck(const Stmt *S, const LocationContext *L, + ProgramPoint::Kind K, const ProgramPointTag *tag) + : StmtPoint(S, NULL, K, L, tag) {} + + static bool classof(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 = 0) + : LocationCheck(S, L, PreLoadKind, tag) {} + + static bool classof(const ProgramPoint *location) { + return location->getKind() == PreLoadKind; + } +}; + +class PreStore : public LocationCheck { +public: + PreStore(const Stmt *S, const LocationContext *L, + const ProgramPointTag *tag = 0) + : LocationCheck(S, L, PreStoreKind, tag) {} + + static bool classof(const ProgramPoint *location) { + return location->getKind() == PreStoreKind; + } +}; + +class PostLoad : public PostStmt { +public: + PostLoad(const Stmt *S, const LocationContext *L, + const ProgramPointTag *tag = 0) + : PostStmt(S, PostLoadKind, L, tag) {} + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostLoadKind; + } +}; + +/// \class 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 = 0) + : PostStmt(S, PostStoreKind, L, tag) { + assert(getData2() == 0); + setData2(Loc); + } + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostStoreKind; + } + + /// \brief Returns the information about the location used in the store, + /// how it was uttered in the code. + const void *getLocationValue() const { + return getData2(); + } + +}; + +class PostLValue : public PostStmt { +public: + PostLValue(const Stmt *S, const LocationContext *L, + const ProgramPointTag *tag = 0) + : PostStmt(S, PostLValueKind, L, tag) {} + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostLValueKind; + } +}; + +class PostPurgeDeadSymbols : public PostStmt { +public: + PostPurgeDeadSymbols(const Stmt *S, const LocationContext *L, + const ProgramPointTag *tag = 0) + : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {} + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == PostPurgeDeadSymbolsKind; + } +}; + +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()); + } + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == BlockEdgeKind; + } +}; + +class PostInitializer : public ProgramPoint { +public: + PostInitializer(const CXXCtorInitializer *I, + const LocationContext *L) + : ProgramPoint(I, PostInitializerKind, L) {} + + static bool classof(const ProgramPoint *Location) { + return Location->getKind() == PostInitializerKind; + } +}; + +class CallEnter : public StmtPoint { +public: + CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, + const LocationContext *callerCtx) + : StmtPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {} + + const Stmt *getCallExpr() const { + return static_cast<const Stmt *>(getData1()); + } + + const StackFrameContext *getCalleeContext() const { + return static_cast<const StackFrameContext *>(getData2()); + } + + static bool classof(const ProgramPoint *Location) { + return Location->getKind() == CallEnterKind; + } +}; + +class CallExit : public StmtPoint { +public: + // CallExit uses the callee's location context. + CallExit(const Stmt *S, const LocationContext *L) + : StmtPoint(S, 0, CallExitKind, L, 0) {} + + static bool classof(const ProgramPoint *Location) { + return Location->getKind() == CallExitKind; + } +}; + +/// 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 = 0, const ProgramPointTag *tag = 0) + : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {} + + const void *getData() const { return getData1(); } + + static bool classof(const ProgramPoint* Location) { + return Location->getKind() == EpsilonKind; + } +}; + +/// 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 = 0) : TagKind(tagKind) {} + virtual ~ProgramPointTag(); + virtual StringRef getTagDescription() const = 0; + +protected: + /// Used to implement 'classof' in subclasses. + const void *getTagKind() { return TagKind; } + +private: + const void *TagKind; +}; + +class SimpleProgramPointTag : public ProgramPointTag { + std::string desc; +public: + SimpleProgramPointTag(StringRef description); + StringRef getTagDescription() const; +}; + +} // 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), 0); +} + +static inline clang::ProgramPoint getTombstoneKey() { + uintptr_t x = + reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; + return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0); +} + +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/clang/include/clang/Analysis/Support/BlkExprDeclBitVector.h b/clang/include/clang/Analysis/Support/BlkExprDeclBitVector.h new file mode 100644 index 0000000..d25b848 --- /dev/null +++ b/clang/include/clang/Analysis/Support/BlkExprDeclBitVector.h @@ -0,0 +1,307 @@ +// BlkExprDeclBitVector.h - Dataflow types for Bitvector 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 provides definition of dataflow types used by analyses such +// as LiveVariables and UninitializedValues. The underlying dataflow values +// are implemented as bitvectors, but the definitions in this file include +// the necessary boilerplate to use with our dataflow framework. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STMTDECLBVDVAL_H +#define LLVM_CLANG_STMTDECLBVDVAL_H + +#include "clang/Analysis/CFG.h" +#include "clang/AST/Decl.h" // for Decl* -> NamedDecl* conversion +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" + +namespace clang { + + class Stmt; + class ASTContext; + +struct DeclBitVector_Types { + + class Idx { + unsigned I; + public: + explicit Idx(unsigned i) : I(i) {} + Idx() : I(~0U) {} + + bool isValid() const { + return I != ~0U; + } + operator unsigned() const { + assert (isValid()); + return I; + } + }; + + //===--------------------------------------------------------------------===// + // AnalysisDataTy - Whole-function meta data. + //===--------------------------------------------------------------------===// + + class AnalysisDataTy { + public: + typedef llvm::DenseMap<const NamedDecl*, unsigned > DMapTy; + typedef DMapTy::const_iterator decl_iterator; + + protected: + DMapTy DMap; + unsigned NDecls; + + public: + + AnalysisDataTy() : NDecls(0) {} + virtual ~AnalysisDataTy() {} + + bool isTracked(const NamedDecl *SD) { return DMap.find(SD) != DMap.end(); } + + Idx getIdx(const NamedDecl *SD) const { + DMapTy::const_iterator I = DMap.find(SD); + return I == DMap.end() ? Idx() : Idx(I->second); + } + + unsigned getNumDecls() const { return NDecls; } + + void Register(const NamedDecl *SD) { + if (!isTracked(SD)) DMap[SD] = NDecls++; + } + + decl_iterator begin_decl() const { return DMap.begin(); } + decl_iterator end_decl() const { return DMap.end(); } + }; + + //===--------------------------------------------------------------------===// + // ValTy - Dataflow value. + //===--------------------------------------------------------------------===// + + class ValTy { + llvm::BitVector DeclBV; + public: + + void resetDeclValues(AnalysisDataTy& AD) { + DeclBV.resize(AD.getNumDecls()); + DeclBV.reset(); + } + + void setDeclValues(AnalysisDataTy& AD) { + DeclBV.resize(AD.getNumDecls()); + DeclBV.set(); + } + + void resetValues(AnalysisDataTy& AD) { + resetDeclValues(AD); + } + + bool operator==(const ValTy& RHS) const { + assert (sizesEqual(RHS)); + return DeclBV == RHS.DeclBV; + } + + void copyValues(const ValTy& RHS) { DeclBV = RHS.DeclBV; } + + llvm::BitVector::reference getBit(unsigned i) { + return DeclBV[i]; + } + + bool getBit(unsigned i) const { + return DeclBV[i]; + } + + llvm::BitVector::reference + operator()(const NamedDecl *ND, const AnalysisDataTy& AD) { + return getBit(AD.getIdx(ND)); + } + + bool operator()(const NamedDecl *ND, const AnalysisDataTy& AD) const { + return getBit(AD.getIdx(ND)); + } + + llvm::BitVector::reference getDeclBit(unsigned i) { return DeclBV[i]; } + const llvm::BitVector::reference getDeclBit(unsigned i) const { + return const_cast<llvm::BitVector&>(DeclBV)[i]; + } + + ValTy& operator|=(const ValTy& RHS) { + assert (sizesEqual(RHS)); + DeclBV |= RHS.DeclBV; + return *this; + } + + ValTy& operator&=(const ValTy& RHS) { + assert (sizesEqual(RHS)); + DeclBV &= RHS.DeclBV; + return *this; + } + + ValTy& OrDeclBits(const ValTy& RHS) { + return operator|=(RHS); + } + + ValTy& AndDeclBits(const ValTy& RHS) { + return operator&=(RHS); + } + + bool sizesEqual(const ValTy& RHS) const { + return DeclBV.size() == RHS.DeclBV.size(); + } + }; + + //===--------------------------------------------------------------------===// + // Some useful merge operations. + //===--------------------------------------------------------------------===// + + struct Union { void operator()(ValTy& Dst, ValTy& Src) { Dst |= Src; } }; + struct Intersect { void operator()(ValTy& Dst, ValTy& Src) { Dst &= Src; } }; +}; + + +struct StmtDeclBitVector_Types { + + //===--------------------------------------------------------------------===// + // AnalysisDataTy - Whole-function meta data. + //===--------------------------------------------------------------------===// + + class AnalysisDataTy : public DeclBitVector_Types::AnalysisDataTy { + ASTContext *ctx; + CFG* cfg; + public: + AnalysisDataTy() : ctx(0), cfg(0) {} + virtual ~AnalysisDataTy() {} + + void setContext(ASTContext &c) { ctx = &c; } + ASTContext &getContext() { + assert(ctx && "ASTContext should not be NULL."); + return *ctx; + } + + void setCFG(CFG& c) { cfg = &c; } + CFG& getCFG() { assert(cfg && "CFG should not be NULL."); return *cfg; } + + bool isTracked(const Stmt *S) { return cfg->isBlkExpr(S); } + using DeclBitVector_Types::AnalysisDataTy::isTracked; + + unsigned getIdx(const Stmt *S) const { + CFG::BlkExprNumTy I = cfg->getBlkExprNum(S); + assert(I && "Stmtession not tracked for bitvector."); + return I; + } + using DeclBitVector_Types::AnalysisDataTy::getIdx; + + unsigned getNumBlkExprs() const { return cfg->getNumBlkExprs(); } + }; + + //===--------------------------------------------------------------------===// + // ValTy - Dataflow value. + //===--------------------------------------------------------------------===// + + class ValTy : public DeclBitVector_Types::ValTy { + llvm::BitVector BlkExprBV; + typedef DeclBitVector_Types::ValTy ParentTy; + + static inline ParentTy& ParentRef(ValTy& X) { + return static_cast<ParentTy&>(X); + } + + static inline const ParentTy& ParentRef(const ValTy& X) { + return static_cast<const ParentTy&>(X); + } + + public: + + void resetBlkExprValues(AnalysisDataTy& AD) { + BlkExprBV.resize(AD.getNumBlkExprs()); + BlkExprBV.reset(); + } + + void setBlkExprValues(AnalysisDataTy& AD) { + BlkExprBV.resize(AD.getNumBlkExprs()); + BlkExprBV.set(); + } + + void resetValues(AnalysisDataTy& AD) { + resetDeclValues(AD); + resetBlkExprValues(AD); + } + + void setValues(AnalysisDataTy& AD) { + setDeclValues(AD); + setBlkExprValues(AD); + } + + bool operator==(const ValTy& RHS) const { + return ParentRef(*this) == ParentRef(RHS) + && BlkExprBV == RHS.BlkExprBV; + } + + void copyValues(const ValTy& RHS) { + ParentRef(*this).copyValues(ParentRef(RHS)); + BlkExprBV = RHS.BlkExprBV; + } + + llvm::BitVector::reference + operator()(const Stmt *S, const AnalysisDataTy& AD) { + return BlkExprBV[AD.getIdx(S)]; + } + const llvm::BitVector::reference + operator()(const Stmt *S, const AnalysisDataTy& AD) const { + return const_cast<ValTy&>(*this)(S,AD); + } + + using DeclBitVector_Types::ValTy::operator(); + + + llvm::BitVector::reference getStmtBit(unsigned i) { return BlkExprBV[i]; } + const llvm::BitVector::reference getStmtBit(unsigned i) const { + return const_cast<llvm::BitVector&>(BlkExprBV)[i]; + } + + ValTy& OrBlkExprBits(const ValTy& RHS) { + BlkExprBV |= RHS.BlkExprBV; + return *this; + } + + ValTy& AndBlkExprBits(const ValTy& RHS) { + BlkExprBV &= RHS.BlkExprBV; + return *this; + } + + ValTy& operator|=(const ValTy& RHS) { + assert (sizesEqual(RHS)); + ParentRef(*this) |= ParentRef(RHS); + BlkExprBV |= RHS.BlkExprBV; + return *this; + } + + ValTy& operator&=(const ValTy& RHS) { + assert (sizesEqual(RHS)); + ParentRef(*this) &= ParentRef(RHS); + BlkExprBV &= RHS.BlkExprBV; + return *this; + } + + bool sizesEqual(const ValTy& RHS) const { + return ParentRef(*this).sizesEqual(ParentRef(RHS)) + && BlkExprBV.size() == RHS.BlkExprBV.size(); + } + }; + + //===--------------------------------------------------------------------===// + // Some useful merge operations. + //===--------------------------------------------------------------------===// + + struct Union { void operator()(ValTy& Dst, ValTy& Src) { Dst |= Src; } }; + struct Intersect { void operator()(ValTy& Dst, ValTy& Src) { Dst &= Src; } }; + +}; +} // end namespace clang + +#endif diff --git a/clang/include/clang/Analysis/Support/BumpVector.h b/clang/include/clang/Analysis/Support/BumpVector.h new file mode 100644 index 0000000..83532e6 --- /dev/null +++ b/clang/include/clang/Analysis/Support/BumpVector.h @@ -0,0 +1,244 @@ +//===-- 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_BUMP_VECTOR +#define LLVM_CLANG_BUMP_VECTOR + +#include "llvm/Support/type_traits.h" +#include "llvm/Support/Allocator.h" +#include "llvm/ADT/PointerIntPair.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) {} + + /// 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(NULL), End(NULL), Capacity(NULL) { + reserve(C, N); + } + + ~BumpVector() { + if (llvm::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 (llvm::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 (llvm::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 // end: LLVM_CLANG_BUMP_VECTOR diff --git a/clang/include/clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h b/clang/include/clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h new file mode 100644 index 0000000..97eb287 --- /dev/null +++ b/clang/include/clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h @@ -0,0 +1,103 @@ +//= CFGRecStmtDeclVisitor - Recursive visitor of CFG stmts/decls -*- 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 template class CFGRecStmtDeclVisitor, which extends +// CFGRecStmtVisitor by implementing (typed) visitation of decls. +// +// FIXME: This may not be fully complete. We currently explore only subtypes +// of ScopedDecl. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CFG_REC_STMT_DECL_VISITOR_H +#define LLVM_CLANG_ANALYSIS_CFG_REC_STMT_DECL_VISITOR_H + +#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include "clang/AST/DeclCXX.h" + +#define DISPATCH_CASE(CLASS) \ +case Decl::CLASS: \ +static_cast<ImplClass*>(this)->Visit##CLASS##Decl( \ + static_cast<CLASS##Decl*>(D)); \ +break; + +#define DEFAULT_DISPATCH(CLASS) void Visit##CLASS##Decl(CLASS##Decl *D) {} +#define DEFAULT_DISPATCH_VARDECL(CLASS) void Visit##CLASS##Decl(CLASS##Decl *D)\ + { static_cast<ImplClass*>(this)->VisitVarDecl(D); } + + +namespace clang { +template <typename ImplClass> +class CFGRecStmtDeclVisitor : public CFGRecStmtVisitor<ImplClass> { +public: + + void VisitDeclRefExpr(DeclRefExpr *DR) { + static_cast<ImplClass*>(this)->VisitDecl(DR->getDecl()); + } + + void VisitDeclStmt(DeclStmt *DS) { + for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); + DI != DE; ++DI) { + Decl *D = *DI; + static_cast<ImplClass*>(this)->VisitDecl(D); + // Visit the initializer. + if (VarDecl *VD = dyn_cast<VarDecl>(D)) + if (Expr *I = VD->getInit()) + static_cast<ImplClass*>(this)->Visit(I); + } + } + + void VisitDecl(Decl *D) { + switch (D->getKind()) { + DISPATCH_CASE(Function) + DISPATCH_CASE(CXXMethod) + DISPATCH_CASE(Var) + DISPATCH_CASE(ParmVar) // FIXME: (same) + DISPATCH_CASE(ImplicitParam) + DISPATCH_CASE(EnumConstant) + DISPATCH_CASE(Typedef) + DISPATCH_CASE(Record) // FIXME: Refine. VisitStructDecl? + DISPATCH_CASE(CXXRecord) + DISPATCH_CASE(Enum) + DISPATCH_CASE(Field) + DISPATCH_CASE(UsingDirective) + DISPATCH_CASE(Using) + default: + llvm_unreachable("Subtype of ScopedDecl not handled."); + } + } + + DEFAULT_DISPATCH(Var) + DEFAULT_DISPATCH(Function) + DEFAULT_DISPATCH(CXXMethod) + DEFAULT_DISPATCH_VARDECL(ParmVar) + DEFAULT_DISPATCH(ImplicitParam) + DEFAULT_DISPATCH(EnumConstant) + DEFAULT_DISPATCH(Typedef) + DEFAULT_DISPATCH(Record) + DEFAULT_DISPATCH(Enum) + DEFAULT_DISPATCH(Field) + DEFAULT_DISPATCH(ObjCInterface) + DEFAULT_DISPATCH(ObjCMethod) + DEFAULT_DISPATCH(ObjCProtocol) + DEFAULT_DISPATCH(ObjCCategory) + DEFAULT_DISPATCH(UsingDirective) + DEFAULT_DISPATCH(Using) + + void VisitCXXRecordDecl(CXXRecordDecl *D) { + static_cast<ImplClass*>(this)->VisitRecordDecl(D); + } +}; + +} // end namespace clang + +#undef DISPATCH_CASE +#undef DEFAULT_DISPATCH +#endif diff --git a/clang/include/clang/Analysis/Visitors/CFGRecStmtVisitor.h b/clang/include/clang/Analysis/Visitors/CFGRecStmtVisitor.h new file mode 100644 index 0000000..4d1cabf --- /dev/null +++ b/clang/include/clang/Analysis/Visitors/CFGRecStmtVisitor.h @@ -0,0 +1,59 @@ +//==- CFGRecStmtVisitor - Recursive visitor of CFG statements ---*- 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 template class CFGRecStmtVisitor, which extends +// CFGStmtVisitor by implementing a default recursive visit of all statements. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CFG_REC_STMT_VISITOR_H +#define LLVM_CLANG_ANALYSIS_CFG_REC_STMT_VISITOR_H + +#include "clang/Analysis/Visitors/CFGStmtVisitor.h" + +namespace clang { +template <typename ImplClass> +class CFGRecStmtVisitor : public CFGStmtVisitor<ImplClass,void> { +public: + + void VisitStmt(Stmt *S) { + static_cast< ImplClass* >(this)->VisitChildren(S); + } + + void VisitCompoundStmt(CompoundStmt *S) { + // Do nothing. Everything in a CompoundStmt is inlined + // into the CFG. + } + + void VisitConditionVariableInit(Stmt *S) { + assert(S == this->getCurrentBlkStmt()); + VarDecl *CondVar = 0; + switch (S->getStmtClass()) { +#define CONDVAR_CASE(CLASS) \ +case Stmt::CLASS ## Class:\ +CondVar = cast<CLASS>(S)->getConditionVariable();\ +break; + CONDVAR_CASE(IfStmt) + CONDVAR_CASE(ForStmt) + CONDVAR_CASE(SwitchStmt) + CONDVAR_CASE(WhileStmt) +#undef CONDVAR_CASE + default: + llvm_unreachable("Infeasible"); + } + static_cast<ImplClass*>(this)->Visit(CondVar->getInit()); + } + + // Defining operator() allows the visitor to be used as a C++ style functor. + void operator()(Stmt *S) { static_cast<ImplClass*>(this)->BlockStmt_Visit(S);} +}; + +} // end namespace clang + +#endif diff --git a/clang/include/clang/Analysis/Visitors/CFGStmtVisitor.h b/clang/include/clang/Analysis/Visitors/CFGStmtVisitor.h new file mode 100644 index 0000000..b354ba7 --- /dev/null +++ b/clang/include/clang/Analysis/Visitors/CFGStmtVisitor.h @@ -0,0 +1,175 @@ +//===--- CFGStmtVisitor.h - Visitor for Stmts in a 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 defines the CFGStmtVisitor interface, which extends +// StmtVisitor. This interface is useful for visiting statements in a CFG +// where some statements have implicit control-flow and thus should +// be treated specially. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CFGSTMTVISITOR_H +#define LLVM_CLANG_ANALYSIS_CFGSTMTVISITOR_H + +#include "clang/AST/StmtVisitor.h" +#include "clang/Analysis/CFG.h" + +namespace clang { + +#define DISPATCH_CASE(CLASS) \ +case Stmt::CLASS ## Class: return \ +static_cast<ImplClass*>(this)->BlockStmt_Visit ## CLASS(static_cast<CLASS*>(S)); + +#define DEFAULT_BLOCKSTMT_VISIT(CLASS) RetTy BlockStmt_Visit ## CLASS(CLASS *S)\ +{ return\ + static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowExpr(\ + cast<Expr>(S)); } + +template <typename ImplClass, typename RetTy=void> +class CFGStmtVisitor : public StmtVisitor<ImplClass,RetTy> { + Stmt *CurrentBlkStmt; + + struct NullifyStmt { + Stmt*& S; + + NullifyStmt(Stmt*& s) : S(s) {} + ~NullifyStmt() { S = NULL; } + }; + +public: + CFGStmtVisitor() : CurrentBlkStmt(NULL) {} + + Stmt *getCurrentBlkStmt() const { return CurrentBlkStmt; } + + RetTy Visit(Stmt *S) { + if (S == CurrentBlkStmt || + !static_cast<ImplClass*>(this)->getCFG().isBlkExpr(S)) + return StmtVisitor<ImplClass,RetTy>::Visit(S); + else + return RetTy(); + } + + /// VisitConditionVariableInit - Handle the initialization of condition + /// variables at branches. Valid statements include IfStmt, ForStmt, + /// WhileStmt, and SwitchStmt. + RetTy VisitConditionVariableInit(Stmt *S) { + return RetTy(); + } + + /// BlockVisit_XXX - Visitor methods for visiting the "root" statements in + /// CFGBlocks. Root statements are the statements that appear explicitly in + /// the list of statements in a CFGBlock. For substatements, or when there + /// is no implementation provided for a BlockStmt_XXX method, we default + /// to using StmtVisitor's Visit method. + RetTy BlockStmt_Visit(Stmt *S) { + CurrentBlkStmt = S; + NullifyStmt cleanup(CurrentBlkStmt); + + switch (S->getStmtClass()) { + case Stmt::IfStmtClass: + case Stmt::ForStmtClass: + case Stmt::WhileStmtClass: + case Stmt::SwitchStmtClass: + return static_cast<ImplClass*>(this)->VisitConditionVariableInit(S); + + DISPATCH_CASE(StmtExpr) + DISPATCH_CASE(ConditionalOperator) + DISPATCH_CASE(BinaryConditionalOperator) + DISPATCH_CASE(ObjCForCollectionStmt) + DISPATCH_CASE(CXXForRangeStmt) + + case Stmt::BinaryOperatorClass: { + BinaryOperator* B = cast<BinaryOperator>(S); + if (B->isLogicalOp()) + return static_cast<ImplClass*>(this)->BlockStmt_VisitLogicalOp(B); + else if (B->getOpcode() == BO_Comma) + return static_cast<ImplClass*>(this)->BlockStmt_VisitComma(B); + // Fall through. + } + + default: + if (isa<Expr>(S)) + return + static_cast<ImplClass*>(this)->BlockStmt_VisitExpr(cast<Expr>(S)); + else + return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(S); + } + } + + DEFAULT_BLOCKSTMT_VISIT(StmtExpr) + DEFAULT_BLOCKSTMT_VISIT(ConditionalOperator) + DEFAULT_BLOCKSTMT_VISIT(BinaryConditionalOperator) + + RetTy BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { + return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(S); + } + + RetTy BlockStmt_VisitCXXForRangeStmt(CXXForRangeStmt *S) { + return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(S); + } + + RetTy BlockStmt_VisitImplicitControlFlowExpr(Expr *E) { + return static_cast<ImplClass*>(this)->BlockStmt_VisitExpr(E); + } + + RetTy BlockStmt_VisitExpr(Expr *E) { + return static_cast<ImplClass*>(this)->BlockStmt_VisitStmt(E); + } + + RetTy BlockStmt_VisitStmt(Stmt *S) { + return static_cast<ImplClass*>(this)->Visit(S); + } + + RetTy BlockStmt_VisitLogicalOp(BinaryOperator* B) { + return + static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowExpr(B); + } + + RetTy BlockStmt_VisitComma(BinaryOperator* B) { + return + static_cast<ImplClass*>(this)->BlockStmt_VisitImplicitControlFlowExpr(B); + } + + //===--------------------------------------------------------------------===// + // Utility methods. Not called by default (but subclasses may use them). + //===--------------------------------------------------------------------===// + + /// VisitChildren: Call "Visit" on each child of S. + void VisitChildren(Stmt *S) { + + switch (S->getStmtClass()) { + default: + break; + + case Stmt::StmtExprClass: { + CompoundStmt *CS = cast<StmtExpr>(S)->getSubStmt(); + if (CS->body_empty()) return; + static_cast<ImplClass*>(this)->Visit(CS->body_back()); + return; + } + + case Stmt::BinaryOperatorClass: { + BinaryOperator* B = cast<BinaryOperator>(S); + if (B->getOpcode() != BO_Comma) break; + static_cast<ImplClass*>(this)->Visit(B->getRHS()); + return; + } + } + + for (Stmt::child_range I = S->children(); I; ++I) + if (*I) static_cast<ImplClass*>(this)->Visit(*I); + } +}; + +#undef DEFAULT_BLOCKSTMT_VISIT +#undef DISPATCH_CASE + +} // end namespace clang + +#endif |