diff options
author | dim <dim@FreeBSD.org> | 2010-09-17 15:54:40 +0000 |
---|---|---|
committer | dim <dim@FreeBSD.org> | 2010-09-17 15:54:40 +0000 |
commit | 36c49e3f258dced101949edabd72e9bc3f1dedc4 (patch) | |
tree | 0bbe07708f7571f8b5291f6d7b96c102b7c99dee /include/clang/Analysis | |
parent | fc84956ac8b7cd244ef30e7a4d4d38a58dec5904 (diff) | |
download | FreeBSD-src-36c49e3f258dced101949edabd72e9bc3f1dedc4.zip FreeBSD-src-36c49e3f258dced101949edabd72e9bc3f1dedc4.tar.gz |
Vendor import of clang r114020 (from the release_28 branch):
http://llvm.org/svn/llvm-project/cfe/branches/release_28@114020
Approved by: rpaulo (mentor)
Diffstat (limited to 'include/clang/Analysis')
-rw-r--r-- | include/clang/Analysis/Analyses/FormatString.h | 595 | ||||
-rw-r--r-- | include/clang/Analysis/Analyses/LiveVariables.h | 5 | ||||
-rw-r--r-- | include/clang/Analysis/Analyses/PrintfFormatString.h | 445 | ||||
-rw-r--r-- | include/clang/Analysis/Analyses/PseudoConstantAnalysis.h | 45 | ||||
-rw-r--r-- | include/clang/Analysis/AnalysisContext.h | 53 | ||||
-rw-r--r-- | include/clang/Analysis/CFG.h | 19 | ||||
-rw-r--r-- | include/clang/Analysis/CFGStmtMap.h | 52 | ||||
-rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowSolver.h | 17 | ||||
-rw-r--r-- | include/clang/Analysis/ProgramPoint.h | 39 | ||||
-rw-r--r-- | include/clang/Analysis/Visitors/CFGStmtVisitor.h | 4 |
10 files changed, 780 insertions, 494 deletions
diff --git a/include/clang/Analysis/Analyses/FormatString.h b/include/clang/Analysis/Analyses/FormatString.h new file mode 100644 index 0000000..280b126 --- /dev/null +++ b/include/clang/Analysis/Analyses/FormatString.h @@ -0,0 +1,595 @@ +//= 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', 'q' (BSD, deprecated) + AsIntMax, // 'j' + AsSizeT, // 'z' + AsPtrDiff, // 't' + AsLongDouble, // 'L' + 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; + } + + llvm::StringRef getCharacters() const { + return llvm::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; + } + + 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, + CStrTy, WCStrTy, WIntTy }; +private: + const Kind K; + QualType T; + ArgTypeResult(bool) : K(InvalidTy) {} +public: + ArgTypeResult(Kind k = UnknownTy) : K(k) {} + ArgTypeResult(QualType t) : K(SpecificTy), T(t) {} + ArgTypeResult(CanQualType t) : K(SpecificTy), T(t) {} + + 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; +}; + +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(llvm::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; +}; + +} // 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 isUIntArg() const { return kind >= UIntArgBeg && kind <= UIntArgEnd; } + bool isDoubleArg() const { return kind >= DoubleArgBeg && + kind <= DoubleArgBeg; } + 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 IsLeftJustified; // '-' + OptionalFlag HasPlusPrefix; // '+' + OptionalFlag HasSpacePrefix; // ' ' + OptionalFlag HasAlternativeForm; // '#' + OptionalFlag HasLeadingZeroes; // '0' + OptionalAmount Precision; +public: + PrintfSpecifier() : + FormatSpecifier(/* isPrintf = */ true), + 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 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) const; + + 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); + + void toString(llvm::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 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::LengthModifier; +using analyze_format_string::OptionalAmount; +using analyze_format_string::OptionalFlag; + +class ScanfSpecifier : public analyze_format_string::FormatSpecifier { + OptionalFlag SuppressAssignment; // '*' +public: + ScanfSpecifier() : + FormatSpecifier(/* isPrintf = */ false), + SuppressAssignment("*") {} + + void setSuppressAssignment(const char *position) { + SuppressAssignment = 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; + } + + 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 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); + +bool ParseScanfString(FormatStringHandler &H, + const char *beg, const char *end); + +} // end analyze_format_string namespace +} // end clang namespace +#endif diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index 44ab080..237fe14 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -41,8 +41,9 @@ struct LiveVariables_ValueTypes { ObserverTy* Observer; ValTy AlwaysLive; AnalysisContext *AC; + bool killAtAssign; - AnalysisDataTy() : Observer(NULL), AC(NULL) {} + AnalysisDataTy() : Observer(NULL), AC(NULL), killAtAssign(true) {} }; //===-----------------------------------------------------===// @@ -68,7 +69,7 @@ class LiveVariables : public DataflowValues<LiveVariables_ValueTypes, public: typedef LiveVariables_ValueTypes::ObserverTy ObserverTy; - LiveVariables(AnalysisContext &AC); + LiveVariables(AnalysisContext &AC, bool killAtAssign = true); /// IsLive - Return true if a variable is live at the end of a /// specified block. diff --git a/include/clang/Analysis/Analyses/PrintfFormatString.h b/include/clang/Analysis/Analyses/PrintfFormatString.h deleted file mode 100644 index d907637..0000000 --- a/include/clang/Analysis/Analyses/PrintfFormatString.h +++ /dev/null @@ -1,445 +0,0 @@ -//==- PrintfFormatStrings.h - Analysis of printf format strings --*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Handling of format string in printf and friends. The structure of format -// strings for fprintf() are described in C99 7.19.6.1. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_FPRINTF_FORMAT_H -#define LLVM_CLANG_FPRINTF_FORMAT_H - -#include "clang/AST/CanonicalType.h" - -namespace clang { - -class ASTContext; - -namespace analyze_printf { - -class ArgTypeResult { -public: - enum Kind { UnknownTy, InvalidTy, SpecificTy, ObjCPointerTy, CPointerTy, - CStrTy, WCStrTy }; -private: - const Kind K; - QualType T; - ArgTypeResult(bool) : K(InvalidTy) {} -public: - ArgTypeResult(Kind k = UnknownTy) : K(k) {} - ArgTypeResult(QualType t) : K(SpecificTy), T(t) {} - ArgTypeResult(CanQualType t) : K(SpecificTy), T(t) {} - - 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; -}; - -class ConversionSpecifier { -public: - enum Kind { - InvalidSpecifier = 0, - // C99 conversion specifiers. - dArg, // 'd' - IntAsCharArg, // 'c' - iArg, // 'i', - oArg, // 'o', - uArg, // 'u', - xArg, // 'x', - XArg, // 'X', - fArg, // 'f', - FArg, // 'F', - eArg, // 'e', - EArg, // 'E', - gArg, // 'g', - GArg, // 'G', - aArg, // 'a', - AArg, // 'A', - CStrArg, // 's' - VoidPtrArg, // 'p' - OutIntPtrArg, // 'n' - PercentArg, // '%' - // MacOS X unicode extensions. - CArg, // 'C' - UnicodeStrArg, // 'S' - // Objective-C specific specifiers. - ObjCObjArg, // '@' - // GlibC specific specifiers. - PrintErrno, // 'm' - // Specifier ranges. - IntArgBeg = dArg, - IntArgEnd = iArg, - UIntArgBeg = oArg, - UIntArgEnd = XArg, - DoubleArgBeg = fArg, - DoubleArgEnd = AArg, - C99Beg = IntArgBeg, - C99End = DoubleArgEnd, - ObjCBeg = ObjCObjArg, - ObjCEnd = ObjCObjArg - }; - - ConversionSpecifier() - : Position(0), kind(InvalidSpecifier) {} - - ConversionSpecifier(const char *pos, Kind k) - : Position(pos), kind(k) {} - - const char *getStart() const { - return Position; - } - - llvm::StringRef getCharacters() const { - return llvm::StringRef(getStart(), getLength()); - } - - bool consumesDataArgument() const { - switch (kind) { - case PercentArg: - case PrintErrno: - return false; - default: - return true; - } - } - - bool isObjCArg() const { return kind >= ObjCBeg && kind <= ObjCEnd; } - bool isIntArg() const { return kind >= dArg && kind <= iArg; } - bool isUIntArg() const { return kind >= oArg && kind <= XArg; } - bool isDoubleArg() const { return kind >= fArg && kind <= AArg; } - Kind getKind() const { return kind; } - void setKind(Kind k) { kind = k; } - unsigned getLength() const { - // Conversion specifiers currently only are represented by - // single characters, but we be flexible. - return 1; - } - const char *toString() const; - -private: - const char *Position; - Kind kind; -}; - -class LengthModifier { -public: - enum Kind { - None, - AsChar, // 'hh' - AsShort, // 'h' - AsLong, // 'l' - AsLongLong, // 'll', 'q' (BSD, deprecated) - AsIntMax, // 'j' - AsSizeT, // 'z' - AsPtrDiff, // 't' - AsLongDouble, // 'L' - AsWideChar = AsLong // for '%ls' - }; - - 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 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(llvm::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 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; -}; - -class FormatSpecifier { - LengthModifier LM; - OptionalFlag IsLeftJustified; // '-' - OptionalFlag HasPlusPrefix; // '+' - OptionalFlag HasSpacePrefix; // ' ' - OptionalFlag HasAlternativeForm; // '#' - OptionalFlag HasLeadingZeroes; // '0' - /// Positional arguments, an IEEE extension: - /// IEEE Std 1003.1, 2004 Edition - /// http://www.opengroup.org/onlinepubs/009695399/functions/printf.html - bool UsesPositionalArg; - unsigned argIndex; - ConversionSpecifier CS; - OptionalAmount FieldWidth; - OptionalAmount Precision; -public: - FormatSpecifier() : - IsLeftJustified("-"), HasPlusPrefix("+"), HasSpacePrefix(" "), - HasAlternativeForm("#"), HasLeadingZeroes("0"), UsesPositionalArg(false), - argIndex(0) {} - - static FormatSpecifier Parse(const char *beg, const char *end); - - // Methods for incrementally constructing the FormatSpecifier. - void setConversionSpecifier(const ConversionSpecifier &cs) { - CS = cs; - } - void setLengthModifier(LengthModifier lm) { - LM = lm; - } - 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; } - - void setArgIndex(unsigned i) { - assert(CS.consumesDataArgument()); - argIndex = i; - } - - unsigned getArgIndex() const { - assert(CS.consumesDataArgument()); - return argIndex; - } - - unsigned getPositionalArgIndex() const { - assert(CS.consumesDataArgument()); - return argIndex + 1; - } - - // Methods for querying the format specifier. - - const ConversionSpecifier &getConversionSpecifier() const { - return CS; - } - - const LengthModifier &getLengthModifier() const { - return LM; - } - - const OptionalAmount &getFieldWidth() const { - return FieldWidth; - } - - void setFieldWidth(const OptionalAmount &Amt) { - FieldWidth = Amt; - } - - void setPrecision(const OptionalAmount &Amt) { - Precision = Amt; - Precision.setUsesDotPrefix(); - } - - const OptionalAmount &getPrecision() const { - return Precision; - } - - /// \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) const; - - 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); - - void toString(llvm::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 hasValidLengthModifier() const; - bool hasValidPrecision() const; - bool hasValidFieldWidth() const; -}; - -enum PositionContext { FieldWidthPos = 0, PrecisionPos = 1 }; - -class FormatStringHandler { -public: - FormatStringHandler() {} - virtual ~FormatStringHandler(); - - virtual void HandleIncompleteFormatSpecifier(const char *startSpecifier, - unsigned specifierLen) {} - - virtual void HandleNullChar(const char *nullCharacter) {} - - virtual void HandleInvalidPosition(const char *startPos, unsigned posLen, - PositionContext p) {} - - virtual void HandleZeroPosition(const char *startPos, unsigned posLen) {} - - virtual bool - HandleInvalidConversionSpecifier(const analyze_printf::FormatSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { return true; } - - virtual bool HandleFormatSpecifier(const analyze_printf::FormatSpecifier &FS, - const char *startSpecifier, - unsigned specifierLen) { - return true; - } -}; - -bool ParseFormatString(FormatStringHandler &H, - const char *beg, const char *end); - -} // end printf namespace -} // end clang namespace -#endif diff --git a/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h b/include/clang/Analysis/Analyses/PseudoConstantAnalysis.h new file mode 100644 index 0000000..cb73850 --- /dev/null +++ b/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/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h index 9ebd93b..7d4d25f 100644 --- a/include/clang/Analysis/AnalysisContext.h +++ b/include/clang/Analysis/AnalysisContext.h @@ -30,41 +30,67 @@ class CFG; class CFGBlock; class LiveVariables; class ParentMap; +class PseudoConstantAnalysis; class ImplicitParamDecl; class LocationContextManager; class StackFrameContext; +namespace idx { class TranslationUnit; } + /// AnalysisContext contains the context data for the function or method under /// analysis. class AnalysisContext { const Decl *D; + // TranslationUnit is NULL if we don't have multiple translation units. + idx::TranslationUnit *TU; + // AnalysisContext owns the following data. - CFG *cfg; - bool builtCFG; + CFG *cfg, *completeCFG; + bool builtCFG, builtCompleteCFG; LiveVariables *liveness; + LiveVariables *relaxedLiveness; ParentMap *PM; + PseudoConstantAnalysis *PCA; llvm::DenseMap<const BlockDecl*,void*> *ReferencedBlockVars; llvm::BumpPtrAllocator A; + bool UseUnoptimizedCFG; bool AddEHEdges; public: - AnalysisContext(const Decl *d, bool addehedges = false) - : D(d), cfg(0), builtCFG(false), liveness(0), PM(0), - ReferencedBlockVars(0), AddEHEdges(addehedges) {} + AnalysisContext(const Decl *d, idx::TranslationUnit *tu, + bool useUnoptimizedCFG = false, + bool addehedges = false) + : D(d), TU(tu), cfg(0), completeCFG(0), + builtCFG(false), builtCompleteCFG(false), + liveness(0), relaxedLiveness(0), PM(0), PCA(0), + ReferencedBlockVars(0), UseUnoptimizedCFG(useUnoptimizedCFG), + AddEHEdges(addehedges) {} ~AnalysisContext(); ASTContext &getASTContext() { return D->getASTContext(); } - const Decl *getDecl() { return D; } + const Decl *getDecl() const { return D; } + + idx::TranslationUnit *getTranslationUnit() const { return TU; } + /// 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 AddEHEdges; } + + bool getUseUnoptimizedCFG() const { return UseUnoptimizedCFG; } + Stmt *getBody(); CFG *getCFG(); + + /// Return a version of the CFG without any edges pruned. + CFG *getUnoptimizedCFG(); + ParentMap &getParentMap(); + PseudoConstantAnalysis *getPseudoConstantAnalysis(); LiveVariables *getLiveVariables(); + LiveVariables *getRelaxedLiveVariables(); typedef const VarDecl * const * referenced_decls_iterator; @@ -79,10 +105,16 @@ public: class AnalysisContextManager { typedef llvm::DenseMap<const Decl*, AnalysisContext*> ContextMap; ContextMap Contexts; + bool UseUnoptimizedCFG; public: + AnalysisContextManager(bool useUnoptimizedCFG = false) + : UseUnoptimizedCFG(useUnoptimizedCFG) {} + ~AnalysisContextManager(); - AnalysisContext *getContext(const Decl *D); + AnalysisContext *getContext(const Decl *D, idx::TranslationUnit *TU = 0); + + bool getUseUnoptimizedCFG() const { return UseUnoptimizedCFG; } // Discard all previously created AnalysisContexts. void clear(); @@ -94,7 +126,10 @@ public: private: ContextKind Kind; + + // AnalysisContext can't be const since some methods may modify its member. AnalysisContext *Ctx; + const LocationContext *Parent; protected: @@ -109,6 +144,10 @@ public: AnalysisContext *getAnalysisContext() const { return Ctx; } + idx::TranslationUnit *getTranslationUnit() const { + return Ctx->getTranslationUnit(); + } + const LocationContext *getParent() const { return Parent; } bool isParentOf(const LocationContext *LC) const; diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index b7256c9..b7a8e11 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -35,22 +35,6 @@ namespace clang { class LangOptions; class ASTContext; -namespace { -// An element of the CFG for implicit descructor calls implied by the language -// rules. -class Dtor { - // Statement that introduces the variable. - Stmt *S; - // A token which ends the scope, return, goto, throw, }. - SourceLocation Loc; -public: - Dtor(Stmt *s, SourceLocation l) : S(s), Loc(l) { - } - SourceLocation getLoc() { return Loc; } - Stmt *getStmt() { return S; } -}; -} - /// CFGElement - Represents a top-level expression in a basic block. class CFGElement { llvm::PointerIntPair<Stmt *, 2> Data; @@ -59,7 +43,6 @@ public: explicit CFGElement() {} CFGElement(Stmt *S, bool lvalue) : Data(S, lvalue ? 1 : 0) {} CFGElement(Stmt *S, Type t) : Data(S, t == StartScope ? 2 : 3) {} - // CFGElement(Dtor *S, Type t) : Data(reinterpret_cast<Stmt*>(S), 4) {} Stmt *getStmt() const { return Data.getPointer(); } bool asLValue() const { return Data.getInt() == 1; } bool asStartScope() const { return Data.getInt() == 2; } @@ -67,7 +50,6 @@ public: bool asDtor() const { return Data.getInt() == 4; } operator Stmt*() const { return getStmt(); } operator bool() const { return getStmt() != 0; } - operator Dtor*() const { return reinterpret_cast<Dtor*>(getStmt()); } }; /// CFGBlock - Represents a single basic block in a source-level CFG. @@ -285,6 +267,7 @@ public: /// 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, + bool pruneTriviallyFalseEdges = true, bool AddEHEdges = false, bool AddScopes = false /* NOT FULLY IMPLEMENTED. NOT READY FOR GENERAL USE. */); diff --git a/include/clang/Analysis/CFGStmtMap.h b/include/clang/Analysis/CFGStmtMap.h new file mode 100644 index 0000000..6e8e140 --- /dev/null +++ b/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/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index 3c76201..9375db0 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -231,7 +231,7 @@ private: 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; @@ -243,6 +243,7 @@ private: M.find(ItrTraits::PrevEdge(B, PrevBlk)); if (EI != M.end()) { + noEdges = false; if (firstMerge) { firstMerge = false; V.copyValues(EI->second); @@ -252,8 +253,20 @@ private: } } + 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. - D.getBlockDataMap()[B].copyValues(V); + BI->second.copyValues(V); } /// ProcessBlock - Process the transfer functions for a given block. diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index 075838d..ba303de 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -15,6 +15,7 @@ #ifndef LLVM_CLANG_ANALYSIS_PROGRAM_POINT #define LLVM_CLANG_ANALYSIS_PROGRAM_POINT +#include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "llvm/System/DataTypes.h" #include "llvm/ADT/DenseMap.h" @@ -26,6 +27,7 @@ namespace clang { class LocationContext; +class AnalysisContext; class FunctionDecl; class ProgramPoint { @@ -45,7 +47,7 @@ public: CallEnterKind, CallExitKind, MinPostStmtKind = PostStmtKind, - MaxPostStmtKind = PostLValueKind }; + MaxPostStmtKind = CallExitKind }; private: std::pair<const void *, const void *> Data; @@ -107,16 +109,16 @@ public: const void *tag = 0) : ProgramPoint(B, BlockEntranceKind, L, tag) {} - CFGBlock* getBlock() const { - return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); + const CFGBlock* getBlock() const { + return reinterpret_cast<const CFGBlock*>(getData1()); } - CFGElement getFirstElement() const { + const CFGElement getFirstElement() const { const CFGBlock* B = getBlock(); return B->empty() ? CFGElement() : B->front(); } - Stmt *getFirstStmt() const { + const Stmt *getFirstStmt() const { return getFirstElement().getStmt(); } @@ -130,16 +132,16 @@ public: BlockExit(const CFGBlock* B, const LocationContext *L) : ProgramPoint(B, BlockExitKind, L) {} - CFGBlock* getBlock() const { - return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1())); + const CFGBlock* getBlock() const { + return reinterpret_cast<const CFGBlock*>(getData1()); } - Stmt* getLastStmt() const { + const Stmt* getLastStmt() const { const CFGBlock* B = getBlock(); return B->empty() ? CFGElement() : B->back(); } - Stmt* getTerminator() const { + const Stmt* getTerminator() const { return getBlock()->getTerminator(); } @@ -298,12 +300,12 @@ public: BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L) : ProgramPoint(B1, B2, BlockEdgeKind, L) {} - CFGBlock* getSrc() const { - return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData1())); + const CFGBlock* getSrc() const { + return static_cast<const CFGBlock*>(getData1()); } - CFGBlock* getDst() const { - return const_cast<CFGBlock*>(static_cast<const CFGBlock*>(getData2())); + const CFGBlock* getDst() const { + return static_cast<const CFGBlock*>(getData2()); } static bool classof(const ProgramPoint* Location) { @@ -313,16 +315,17 @@ public: class CallEnter : public StmtPoint { public: - // CallEnter uses the caller's location context. - CallEnter(const Stmt *S, const FunctionDecl *fd, const LocationContext *L) - : StmtPoint(S, fd, CallEnterKind, L, 0) {} + // L is caller's location context. AC is callee's AnalysisContext. + CallEnter(const Stmt *S, const AnalysisContext *AC, const LocationContext *L) + : StmtPoint(S, AC, CallEnterKind, L, 0) {} const Stmt *getCallExpr() const { return static_cast<const Stmt *>(getData1()); } - const FunctionDecl *getCallee() const { - return static_cast<const FunctionDecl *>(getData2()); + AnalysisContext *getCalleeContext() const { + return const_cast<AnalysisContext *>( + static_cast<const AnalysisContext *>(getData2())); } static bool classof(const ProgramPoint *Location) { diff --git a/include/clang/Analysis/Visitors/CFGStmtVisitor.h b/include/clang/Analysis/Visitors/CFGStmtVisitor.h index 8a85ec1..6421f18 100644 --- a/include/clang/Analysis/Visitors/CFGStmtVisitor.h +++ b/include/clang/Analysis/Visitors/CFGStmtVisitor.h @@ -86,7 +86,7 @@ public: BinaryOperator* B = cast<BinaryOperator>(S); if (B->isLogicalOp()) return static_cast<ImplClass*>(this)->BlockStmt_VisitLogicalOp(B); - else if (B->getOpcode() == BinaryOperator::Comma) + else if (B->getOpcode() == BO_Comma) return static_cast<ImplClass*>(this)->BlockStmt_VisitComma(B); // Fall through. } @@ -149,7 +149,7 @@ public: case Stmt::BinaryOperatorClass: { BinaryOperator* B = cast<BinaryOperator>(S); - if (B->getOpcode() != BinaryOperator::Comma) break; + if (B->getOpcode() != BO_Comma) break; static_cast<ImplClass*>(this)->Visit(B->getRHS()); return; } |