llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-static-analyzer-1 Author: Balázs Benics (balazs-benics-sonarsource) <details> <summary>Changes</summary> Out of the worst 500 entry points, 45 were improved by at least 10%. Out of these 45, 5 were improved by more than 50%. Out of these 45, 2 were improved by more than 80%. For example, for the `DelugeFirmware/src/OSLikeStuff/fault_handler/fault_handler.c` TU: - `printPointers` entry point was improved from 31.1 seconds to 1.1 second (28x). - `handle_cpu_fault` entry point was improved from 15.5 seconds to 3 seconds (5x). We had in total 3'037'085 entry points in the test pool. Out of these 390'156 were measured to run over a second.  CPP-6182 --- Patch is 40.01 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/144327.diff 12 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h (+12-12) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h (+13-12) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h (+108-58) - (modified) clang/lib/StaticAnalyzer/Checkers/Taint.cpp (+1-1) - (modified) clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp (+1-1) - (modified) clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp (+1-1) - (modified) clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp (+26-12) - (modified) clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp (+11-4) - (modified) clang/lib/StaticAnalyzer/Core/SValBuilder.cpp (+48-41) - (modified) clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp (+18-11) - (modified) clang/lib/StaticAnalyzer/Core/SymbolManager.cpp (+6) - (added) clang/test/Analysis/ensure-capped-symbol-complexity.cpp (+53) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h index 2911554de9d97..0458a6125db9a 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h @@ -57,6 +57,8 @@ class SValBuilder { protected: ASTContext &Context; + const AnalyzerOptions &AnOpts; + /// Manager of APSInt values. BasicValueFactory BasicVals; @@ -68,8 +70,6 @@ class SValBuilder { ProgramStateManager &StateMgr; - const AnalyzerOptions &AnOpts; - /// The scalar type to use for array indices. const QualType ArrayIndexTy; @@ -317,21 +317,21 @@ class SValBuilder { return nonloc::LocAsInteger(BasicVals.getPersistentSValWithData(loc, bits)); } - nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - APSIntPtr rhs, QualType type); + DefinedOrUnknownSVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + APSIntPtr rhs, QualType type); - nonloc::SymbolVal makeNonLoc(APSIntPtr rhs, BinaryOperator::Opcode op, - const SymExpr *lhs, QualType type); + DefinedOrUnknownSVal makeNonLoc(APSIntPtr rhs, BinaryOperator::Opcode op, + const SymExpr *lhs, QualType type); - nonloc::SymbolVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, - const SymExpr *rhs, QualType type); + DefinedOrUnknownSVal makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, + const SymExpr *rhs, QualType type); - NonLoc makeNonLoc(const SymExpr *operand, UnaryOperator::Opcode op, - QualType type); + DefinedOrUnknownSVal makeNonLoc(const SymExpr *operand, + UnaryOperator::Opcode op, QualType type); /// Create a NonLoc value for cast. - nonloc::SymbolVal makeNonLoc(const SymExpr *operand, QualType fromTy, - QualType toTy); + DefinedOrUnknownSVal makeNonLoc(const SymExpr *operand, QualType fromTy, + QualType toTy); nonloc::ConcreteInt makeTruthVal(bool b, QualType type) { return nonloc::ConcreteInt(BasicVals.getTruthValue(b, type)); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h index aca14cf813c4b..11d0a22a31c46 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h @@ -51,9 +51,11 @@ class SymExpr : public llvm::FoldingSetNode { /// Note, however, that it can't be used in Profile because SymbolManager /// needs to compute Profile before allocating SymExpr. const SymbolID Sym; + const unsigned Complexity; protected: - SymExpr(Kind k, SymbolID Sym) : K(k), Sym(Sym) {} + SymExpr(Kind k, SymbolID Sym, unsigned Complexity) + : K(k), Sym(Sym), Complexity(Complexity) {} static bool isValidTypeForSymbol(QualType T) { // FIXME: Depending on whether we choose to deprecate structural symbols, @@ -61,8 +63,6 @@ class SymExpr : public llvm::FoldingSetNode { return !T.isNull() && !T->isVoidType(); } - mutable unsigned Complexity = 0; - public: virtual ~SymExpr() = default; @@ -108,7 +108,7 @@ class SymExpr : public llvm::FoldingSetNode { return llvm::make_range(symbol_iterator(this), symbol_iterator()); } - virtual unsigned computeComplexity() const = 0; + unsigned complexity() const { return Complexity; } /// Find the region from which this symbol originates. /// @@ -136,10 +136,15 @@ using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>; /// A symbol representing data which can be stored in a memory location /// (region). class SymbolData : public SymExpr { + friend class SymbolManager; void anchor() override; protected: - SymbolData(Kind k, SymbolID sym) : SymExpr(k, sym) { assert(classof(this)); } + SymbolData(Kind k, SymbolID sym) : SymExpr(k, sym, computeComplexity()) { + assert(classof(this)); + } + + static unsigned computeComplexity(...) { return 1; } public: ~SymbolData() override = default; @@ -147,14 +152,10 @@ class SymbolData : public SymExpr { /// Get a string representation of the kind of the region. virtual StringRef getKindStr() const = 0; - unsigned computeComplexity() const override { - return 1; - }; - // Implement isa<T> support. - static inline bool classof(const SymExpr *SE) { - Kind k = SE->getKind(); - return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { + return K >= BEGIN_SYMBOLS && K <= END_SYMBOLS; } }; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index 86774ad5043dd..5239663788fb4 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -18,6 +18,7 @@ #include "clang/AST/Type.h" #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntPtr.h" #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" @@ -72,9 +73,9 @@ class SymbolRegionValue : public SymbolData { QualType getType() const override; // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolRegionValueKind; - } + static constexpr Kind ClassKind = SymbolRegionValueKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// A symbol representing the result of an expression in the case when we do @@ -128,9 +129,9 @@ class SymbolConjured : public SymbolData { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolConjuredKind; - } + static constexpr Kind ClassKind = SymbolConjuredKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// A symbol representing the value of a MemRegion whose parent region has @@ -172,9 +173,11 @@ class SymbolDerived : public SymbolData { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolDerivedKind; + static constexpr Kind ClassKind = SymbolDerivedKind; + static constexpr bool classof(const SymExpr *SE) { + return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// SymbolExtent - Represents the extent (size in bytes) of a bounded region. @@ -209,9 +212,9 @@ class SymbolExtent : public SymbolData { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolExtentKind; - } + static constexpr Kind ClassKind = SymbolExtentKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == SymbolExtentKind; } }; /// SymbolMetadata - Represents path-dependent metadata about a specific region. @@ -278,13 +281,14 @@ class SymbolMetadata : public SymbolData { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolMetadataKind; - } + static constexpr Kind ClassKind = SymbolMetadataKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// Represents a cast expression. class SymbolCast : public SymExpr { + friend class SymbolManager; const SymExpr *Operand; /// Type of the operand. @@ -295,20 +299,19 @@ class SymbolCast : public SymExpr { friend class SymExprAllocator; SymbolCast(SymbolID Sym, const SymExpr *In, QualType From, QualType To) - : SymExpr(SymbolCastKind, Sym), Operand(In), FromTy(From), ToTy(To) { + : SymExpr(SymbolCastKind, Sym, computeComplexity(In, From, To)), + Operand(In), FromTy(From), ToTy(To) { assert(In); assert(isValidTypeForSymbol(From)); // FIXME: GenericTaintChecker creates symbols of void type. // Otherwise, 'To' should also be a valid type. } -public: - unsigned computeComplexity() const override { - if (Complexity == 0) - Complexity = 1 + Operand->computeComplexity(); - return Complexity; + static unsigned computeComplexity(const SymExpr *In, QualType, QualType) { + return In->complexity() + 1; } +public: QualType getType() const override { return ToTy; } LLVM_ATTRIBUTE_RETURNS_NONNULL @@ -329,13 +332,14 @@ class SymbolCast : public SymExpr { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == SymbolCastKind; - } + static constexpr Kind ClassKind = SymbolCastKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// Represents a symbolic expression involving a unary operator. class UnarySymExpr : public SymExpr { + friend class SymbolManager; const SymExpr *Operand; UnaryOperator::Opcode Op; QualType T; @@ -343,7 +347,8 @@ class UnarySymExpr : public SymExpr { friend class SymExprAllocator; UnarySymExpr(SymbolID Sym, const SymExpr *In, UnaryOperator::Opcode Op, QualType T) - : SymExpr(UnarySymExprKind, Sym), Operand(In), Op(Op), T(T) { + : SymExpr(UnarySymExprKind, Sym, computeComplexity(In, Op, T)), + Operand(In), Op(Op), T(T) { // Note, some unary operators are modeled as a binary operator. E.g. ++x is // modeled as x + 1. assert((Op == UO_Minus || Op == UO_Not) && "non-supported unary expression"); @@ -354,13 +359,12 @@ class UnarySymExpr : public SymExpr { assert(!Loc::isLocType(T) && "unary symbol should be nonloc"); } -public: - unsigned computeComplexity() const override { - if (Complexity == 0) - Complexity = 1 + Operand->computeComplexity(); - return Complexity; + static unsigned computeComplexity(const SymExpr *In, UnaryOperator::Opcode, + QualType) { + return In->complexity() + 1; } +public: const SymExpr *getOperand() const { return Operand; } UnaryOperator::Opcode getOpcode() const { return Op; } QualType getType() const override { return T; } @@ -380,9 +384,9 @@ class UnarySymExpr : public SymExpr { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - return SE->getKind() == UnarySymExprKind; - } + static constexpr Kind ClassKind = UnarySymExprKind; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// Represents a symbolic expression involving a binary operator @@ -391,8 +395,9 @@ class BinarySymExpr : public SymExpr { QualType T; protected: - BinarySymExpr(SymbolID Sym, Kind k, BinaryOperator::Opcode op, QualType t) - : SymExpr(k, Sym), Op(op), T(t) { + BinarySymExpr(SymbolID Sym, Kind k, BinaryOperator::Opcode op, QualType t, + unsigned Complexity) + : SymExpr(k, Sym, Complexity), Op(op), T(t) { assert(classof(this)); // Binary expressions are results of arithmetic. Pointer arithmetic is not // handled by binary expressions, but it is instead handled by applying @@ -408,14 +413,14 @@ class BinarySymExpr : public SymExpr { BinaryOperator::Opcode getOpcode() const { return Op; } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { - Kind k = SE->getKind(); - return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { + return K >= BEGIN_BINARYSYMEXPRS && K <= END_BINARYSYMEXPRS; } protected: static unsigned computeOperandComplexity(const SymExpr *Value) { - return Value->computeComplexity(); + return Value->complexity(); } static unsigned computeOperandComplexity(const llvm::APSInt &Value) { return 1; @@ -430,19 +435,28 @@ class BinarySymExpr : public SymExpr { }; /// Template implementation for all binary symbolic expressions -template <class LHSTYPE, class RHSTYPE, SymExpr::Kind ClassKind> +template <class LHSTYPE, class RHSTYPE, SymExpr::Kind ClassK> class BinarySymExprImpl : public BinarySymExpr { + friend class SymbolManager; LHSTYPE LHS; RHSTYPE RHS; friend class SymExprAllocator; BinarySymExprImpl(SymbolID Sym, LHSTYPE lhs, BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) - : BinarySymExpr(Sym, ClassKind, op, t), LHS(lhs), RHS(rhs) { + : BinarySymExpr(Sym, ClassKind, op, t, + computeComplexity(lhs, op, rhs, t)), + LHS(lhs), RHS(rhs) { assert(getPointer(lhs)); assert(getPointer(rhs)); } + static unsigned computeComplexity(LHSTYPE lhs, BinaryOperator::Opcode, + RHSTYPE rhs, QualType) { + // FIXME: Should we add 1 to complexity? + return computeOperandComplexity(lhs) + computeOperandComplexity(rhs); + } + public: void dumpToStream(raw_ostream &os) const override { dumpToStreamImpl(os, LHS); @@ -453,13 +467,6 @@ class BinarySymExprImpl : public BinarySymExpr { LHSTYPE getLHS() const { return LHS; } RHSTYPE getRHS() const { return RHS; } - unsigned computeComplexity() const override { - if (Complexity == 0) - Complexity = - computeOperandComplexity(RHS) + computeOperandComplexity(LHS); - return Complexity; - } - static void Profile(llvm::FoldingSetNodeID &ID, LHSTYPE lhs, BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) { ID.AddInteger((unsigned)ClassKind); @@ -474,7 +481,9 @@ class BinarySymExprImpl : public BinarySymExpr { } // Implement isa<T> support. - static bool classof(const SymExpr *SE) { return SE->getKind() == ClassKind; } + static constexpr Kind ClassKind = ClassK; + static bool classof(const SymExpr *SE) { return classof(SE->getKind()); } + static constexpr bool classof(Kind K) { return K == ClassKind; } }; /// Represents a symbolic expression like 'x' + 3. @@ -489,6 +498,33 @@ using IntSymExpr = BinarySymExprImpl<APSIntPtr, const SymExpr *, using SymSymExpr = BinarySymExprImpl<const SymExpr *, const SymExpr *, SymExpr::Kind::SymSymExprKind>; +struct MaybeSymExpr { + MaybeSymExpr() = default; + explicit MaybeSymExpr(SymbolRef Sym) : Sym(Sym) {} + bool isValid() const { return Sym; } + bool isInvalid() const { return !isValid(); } + SymbolRef operator->() const { return Sym; } + + SymbolRef getOrNull() const { return Sym; } + template <typename SymT> const SymT *getOrNull() const { + return llvm::dyn_cast_if_present<SymT>(Sym); + } + + DefinedOrUnknownSVal getOrUnknown() const { + if (isInvalid()) + return UnknownVal(); + return nonloc::SymbolVal(Sym); + } + + nonloc::SymbolVal getOrAssert() const { + assert(Sym); + return nonloc::SymbolVal(Sym); + } + +private: + SymbolRef Sym = nullptr; +}; + class SymExprAllocator { SymbolID NextSymbolID = 0; llvm::BumpPtrAllocator &Alloc; @@ -518,27 +554,27 @@ class SymbolManager { SymExprAllocator Alloc; BasicValueFactory &BV; ASTContext &Ctx; + const unsigned MaxCompComplexity; public: SymbolManager(ASTContext &ctx, BasicValueFactory &bv, - llvm::BumpPtrAllocator &bpalloc) - : SymbolDependencies(16), Alloc(bpalloc), BV(bv), Ctx(ctx) {} + llvm::BumpPtrAllocator &bpalloc, const AnalyzerOptions &Opts) + : SymbolDependencies(16), Alloc(bpalloc), BV(bv), Ctx(ctx), + MaxCompComplexity(Opts.MaxSymbolComplexity) { + assert(MaxCompComplexity > 0 && "Zero max complexity doesn't make sense"); + } static bool canSymbolicate(QualType T); /// Create or retrieve a SymExpr of type \p SymExprT for the given arguments. /// Use the arguments to check for an existing SymExpr and return it, /// otherwise, create a new one and keep a pointer to it to avoid duplicates. - template <typename SymExprT, typename... Args> - const SymExprT *acquire(Args &&...args); + template <typename SymExprT, typename... Args> auto acquire(Args &&...args); const SymbolConjured *conjureSymbol(ConstCFGElementRef Elem, const LocationContext *LCtx, QualType T, unsigned VisitCount, - const void *SymbolTag = nullptr) { - - return acquire<SymbolConjured>(Elem, LCtx, T, VisitCount, SymbolTag); - } + const void *SymbolTag = nullptr); QualType getType(const SymExpr *SE) const { return SE->getType(); @@ -672,7 +708,16 @@ class SymbolVisitor { }; template <typename T, typename... Args> -const T *SymbolManager::acquire(Args &&...args) { +auto SymbolManager::acquire(Args &&...args) { + constexpr bool IsSymbolData = SymbolData::classof(T::ClassKind); + if constexpr (IsSymbolData) { + assert(T::computeComplexity(args...) == 1); + } else { + if (T::computeComplexity(args...) > MaxCompComplexity) { + return MaybeSymExpr(); + } + } + llvm::FoldingSetNodeID profile; T::Profile(profile, args...); void *InsertPos; @@ -681,7 +726,12 @@ const T *SymbolManager::acquire(Args &&...args) { SD = Alloc.make<T>(std::forward<Args>(args)...); DataSet.InsertNode(SD, InsertPos); } - return cast<T>(SD); + + if constexpr (IsSymbolData) { + return cast<T>(SD); + } else { + return MaybeSymExpr(SD); + } } } // namespace ento diff --git a/clang/lib/StaticAnalyzer/Checkers/Taint.cpp b/clang/lib/StaticAnalyzer/Checkers/Taint.cpp index e55d064253b84..f0dc889f15e7a 100644 --- a/clang/lib/StaticAnalyzer/Checkers/Taint.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/Taint.cpp @@ -267,7 +267,7 @@ std::vector<SymbolRef> taint::getTaintedSymbolsImpl(ProgramStateRef State, // HACK:https://discourse.llvm.org/t/rfc-make-istainted-and-complex-symbols-friends/79570 if (const auto &Opts = State->getAnalysisManager().getAnalyzerOptions(); - Sym->computeComplexity() > Opts.MaxTaintedSymbolComplexity) { + Sym->complexity() > Opts.MaxTaintedSymbolComplexity) { return {}; } diff --git a/clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp index e2f8bd541c967..ab0e3d8f56d86 100644 --- a/clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/TrustNonnullChecker.cpp @@ -66,7 +66,7 @@ class TrustNonnullChecker : public Checker<check::PostCall, SVal Cond, bool Assumption) const { const SymbolRef CondS = Cond.getAsSymbol(); - if (!CondS || CondS->computeComplexity() > ComplexityThreshold) + if (!CondS || CondS->complexity() > ComplexityThreshold) return State; for (SymbolRef Antecedent : CondS->symbols()) { diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp index fa8e669b6bb2f..3486485dcd686 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp @@ -67,7 +67,7 @@ void ExprEngine::VisitBinaryOperator(const BinaryOperator* B, if (RightV.isUnknown()) { unsigned Count = currBldrCtx->blockCount(); RightV = svalBuilder.conjureSymbolVal(nullptr, getCFGElementRef(), LCtx, - Count); + RHS->getType(), Count); } // Simulate the effects of a "store": bind the value of the RHS // to the L-Valu... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/144327 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
