Author: Donát Nagy Date: 2026-10-12T12:57:46+02:00 New Revision: 6a6534c9b036bc897c55f74e014afe7911f7c987
URL: https://github.com/llvm/llvm-project/commit/6a6534c9b036bc897c55f74e014afe7911f7c987 DIFF: https://github.com/llvm/llvm-project/commit/6a6534c9b036bc897c55f74e014afe7911f7c987.diff LOG: [analyzer] Respect symbol complexity bound in tryRearrange (#227367) The `tryRearrange` logic of the `SValBuilder` lets the analyzer engine conclude e.g. that `(x + 1) - x` is equal to 1. Unfortunately it had to be disabled by default because it used low-level `SymMgr.acquire` calls to construct symbols, which did not respect the symbol complexity limit and could cause exponential slowdowns in corner cases. This commit switches to using `SValBuilder::makeSymExprValNN` instead of those `acquire` calls, because that higher-level method respects the symbol complexity limits. This patch only affects the analysis in the case when off-by-default option aggressive-binary-operation-simplification is enabled. In the future I intend to enable this simplification by default, at least for the case of additive operations (which are mathematically "simpler"). Added: clang/test/Analysis/aggressive-binop-simpl-complexity.c Modified: clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp clang/test/Analysis/PR38208.c Removed: ################################################################################ diff --git a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp index 7d154cbc840ac..d8fe3b32b6f1a 100644 --- a/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp +++ b/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp @@ -289,14 +289,14 @@ static std::pair<SymbolRef, APSIntPtr> decomposeSymbol(SymbolRef Sym, // Simplify "(LSym + LInt) Op (RSym + RInt)" assuming all values are of the // same signed integral type and no overflows occur (which should be checked -// by the caller). -static NonLoc doRearrangeUnchecked(ProgramStateRef State, - BinaryOperator::Opcode Op, - SymbolRef LSym, llvm::APSInt LInt, - SymbolRef RSym, llvm::APSInt RInt) { +// by the caller). May return UnknownVal if the symbol complexity threshold is +// reached. +static SVal doRearrangeUnchecked(ProgramStateRef State, + BinaryOperator::Opcode Op, SymbolRef LSym, + llvm::APSInt LInt, SymbolRef RSym, + llvm::APSInt RInt) { SValBuilder &SVB = State->getStateManager().getSValBuilder(); BasicValueFactory &BV = SVB.getBasicValueFactory(); - SymbolManager &SymMgr = SVB.getSymbolManager(); QualType SymTy = LSym->getType(); assert(SymTy == RSym->getType() && @@ -320,7 +320,13 @@ static NonLoc doRearrangeUnchecked(ProgramStateRef State, nonloc::ConcreteInt(BV.getValue(RInt)), ResultTy) .castAs<NonLoc>(); - SymbolRef ResultSym = nullptr; + auto MakeSymExprVal = [&SVB, SymTy](SymbolRef Lhs, BinaryOperatorKind Op, + SymbolRef Rhs) { + return SVB.makeSymExprValNN(Op, nonloc::SymbolVal(Lhs), + nonloc::SymbolVal(Rhs), SymTy); + }; + + SVal ResultSV = UnknownVal(); BinaryOperator::Opcode ResultOp; llvm::APSInt ResultInt; if (BinaryOperator::isComparisonOp(Op)) { @@ -328,16 +334,16 @@ static NonLoc doRearrangeUnchecked(ProgramStateRef State, // FIXME: Maybe it'd be better to have consistency in // "$x - $y" vs. "$y - $x" because those are solver's keys. if (LInt > RInt) { - ResultSym = SymMgr.acquire<SymSymExpr>(RSym, BO_Sub, LSym, SymTy); + ResultSV = MakeSymExprVal(RSym, BO_Sub, LSym); ResultOp = BinaryOperator::reverseComparisonOp(Op); ResultInt = LInt - RInt; // Opposite order! } else { - ResultSym = SymMgr.acquire<SymSymExpr>(LSym, BO_Sub, RSym, SymTy); + ResultSV = MakeSymExprVal(LSym, BO_Sub, RSym); ResultOp = Op; ResultInt = RInt - LInt; // Opposite order! } } else { - ResultSym = SymMgr.acquire<SymSymExpr>(LSym, Op, RSym, SymTy); + ResultSV = MakeSymExprVal(LSym, Op, RSym); ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt); ResultOp = BO_Add; // Bring back the cosmetic diff erence. @@ -346,12 +352,14 @@ static NonLoc doRearrangeUnchecked(ProgramStateRef State, ResultOp = BO_Sub; } else if (ResultInt == 0) { // Shortcut: Simplify "$x + 0" to "$x". - return nonloc::SymbolVal(ResultSym); + return ResultSV; } } - APSIntPtr PersistentResultInt = BV.getValue(ResultInt); - return nonloc::SymbolVal(SymMgr.acquire<SymIntExpr>( - ResultSym, ResultOp, PersistentResultInt, ResultTy)); + if (auto ResultNL = ResultSV.getAs<NonLoc>()) { + nonloc::ConcreteInt ResultCI(BV.getValue(ResultInt)); + return SVB.makeSymExprValNN(ResultOp, *ResultNL, ResultCI, ResultTy); + } + return UnknownVal(); } // Rearrange if symbol type matches the result type and if the operator is a @@ -374,9 +382,7 @@ static std::optional<NonLoc> tryRearrange(ProgramStateRef State, // We expect everything to be of the same type - this type. QualType SingleTy; - // FIXME: After putting complexity threshold to the symbols we can always - // rearrange additive operations but rearrange comparisons only if - // option is set. + // FIXME: This should be enabled by default, at least for additive operations. if (!SVB.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) return std::nullopt; @@ -401,6 +407,7 @@ static std::optional<NonLoc> tryRearrange(ProgramStateRef State, assert(!SingleTy.isNull() && "We should have figured out the type by now!"); // Rearrange signed symbolic expressions only + // FIXME: This should also handle unsigned, at least for additive operations. if (!SingleTy->isSignedIntegerOrEnumerationType()) return std::nullopt; @@ -417,7 +424,8 @@ static std::optional<NonLoc> tryRearrange(ProgramStateRef State, return std::nullopt; // We know that no overflows can occur anymore. - return doRearrangeUnchecked(State, Op, LSym, LInt, RSym, RInt); + return doRearrangeUnchecked(State, Op, LSym, LInt, RSym, RInt) + .getAs<NonLoc>(); } SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state, diff --git a/clang/test/Analysis/PR38208.c b/clang/test/Analysis/PR38208.c index 750cbc50cc749..e1039ee75a0f4 100644 --- a/clang/test/Analysis/PR38208.c +++ b/clang/test/Analysis/PR38208.c @@ -1,11 +1,14 @@ // RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-config aggressive-binary-operation-simplification=true -verify %s // expected-no-diagnostics // This test case used to demonstrate a huge slowdown regression. // Reported in https://bugs.llvm.org/show_bug.cgi?id=38208 -// Caused by 2bbccca9f75b6bce08d77cf19abfb206d0c3bc2e aka. "aggressive-binary-operation-simplification" -// Fixed by dcde8acc32f1355f37d3bc2814c528fdc2ca5f94 +// Caused by bad logic in 2bbccca9f75b6bce08d77cf19abfb206d0c3bc2e aka. +// "aggressive-binary-operation-simplification", which created symbols without +// respecting the symbol complexity limit. This was originally avoided by +// disabling that feature, but now the underlying cause is also eliminated. int foo(int a, int b) { a += b; b -= a; diff --git a/clang/test/Analysis/aggressive-binop-simpl-complexity.c b/clang/test/Analysis/aggressive-binop-simpl-complexity.c new file mode 100644 index 0000000000000..618c81d7d2b80 --- /dev/null +++ b/clang/test/Analysis/aggressive-binop-simpl-complexity.c @@ -0,0 +1,30 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -verify %s + +// Verify that symbols created by the 'tryRearrange' logic respect the symbol +// complexity threshold. This is adapted from the older test PR38208.c to show +// a clear failure instead of a hanging analysis (exponential runtime). + +void clang_analyzer_dump(int); + +int foo(int x, int y) { + int a = x; int b = y; // complexity: 1, 1 + a += b; b -= a; // complexity: 2, 3 + a += b; b -= a; // complexity: 5, 8 + a += b; b -= a; // complexity: 13, 21 + a += b; b -= a; // complexity: 34, would be 55 + + // We assume concrete values for 'x' and 'y' only after the calculations, to + // ensure that the calculations were performed symbolically. + if (x == 0 && y == 0) { + // The symbolic expression for 'a' has complexity 34, which is not above + // the threshold (35), so the analyzer can remember the connection between + // 'a' and the arguments 'x' and 'y'. + clang_analyzer_dump(a); //expected-warning {{0 S32}} + // The symbolic expression for 'b' would have complexity 55, which is above + // the threshold (35), so the analyzer conjured a fresh symbol, which is + // totally unrelated to 'x' and 'y'. + clang_analyzer_dump(b); //expected-warning {{conj_}} + } + return a; +} _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
