Author: Balázs Benics Date: 2025-11-25T12:16:56Z New Revision: 17b19c50349053ed7721357f806233d633696bf0
URL: https://github.com/llvm/llvm-project/commit/17b19c50349053ed7721357f806233d633696bf0 DIFF: https://github.com/llvm/llvm-project/commit/17b19c50349053ed7721357f806233d633696bf0.diff LOG: [analyzer] Unroll loops of compile-time upper-bounded loops (#169400) Previously, only literal upper-bounded loops were recognized. This patch relaxes this matching to accept any compile-time deducible constant expression. It would be better to rely on the SVals (values from the symbolic domain), as those could potentially have more accurate answers, but this one is much simpler. Note that at the time we calculate this value, we have not evaluated the sub-exprs of the condition, consequently, we can't just query the Environment for the folded SVal. Because of this, the next best tool in our toolbox is comp-time evaluating the Expr. rdar://165363923 Added: Modified: clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp clang/test/Analysis/loop-unrolling.cpp Removed: ################################################################################ diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp index 01d87b02fcdbd..5803cbd9f7229 100644 --- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp +++ b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp @@ -23,6 +23,8 @@ using namespace clang; using namespace ento; using namespace clang::ast_matchers; +using ast_matchers::internal::Matcher; + static const int MAXIMUM_STEP_UNROLLED = 128; namespace { @@ -69,6 +71,11 @@ struct LoopState { REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) namespace clang { +namespace { +AST_MATCHER(QualType, isIntegralOrEnumerationType) { + return Node->isIntegralOrEnumerationType(); +} +} // namespace namespace ento { static bool isLoopStmt(const Stmt *S) { @@ -82,22 +89,23 @@ ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { return State; } -static internal::Matcher<Stmt> simpleCondition(StringRef BindName, - StringRef RefName) { +static Matcher<Stmt> simpleCondition(StringRef BindName, StringRef RefName) { + auto LoopVariable = ignoringParenImpCasts( + declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))) + .bind(RefName)); + auto UpperBound = ignoringParenImpCasts( + expr(hasType(isIntegralOrEnumerationType())).bind("boundNum")); + return binaryOperator( anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), hasOperatorName(">="), hasOperatorName("!=")), - hasEitherOperand(ignoringParenImpCasts( - declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))) - .bind(RefName))), - hasEitherOperand( - ignoringParenImpCasts(integerLiteral().bind("boundNum")))) + anyOf(binaryOperator(hasLHS(LoopVariable), hasRHS(UpperBound)), + binaryOperator(hasRHS(LoopVariable), hasLHS(UpperBound)))) .bind("conditionOperator"); } -static internal::Matcher<Stmt> -changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { +static Matcher<Stmt> changeIntBoundNode(Matcher<Decl> VarNodeMatcher) { return anyOf( unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), hasUnaryOperand(ignoringParenImpCasts( @@ -107,15 +115,13 @@ changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { declRefExpr(to(varDecl(VarNodeMatcher))))))); } -static internal::Matcher<Stmt> -callByRef(internal::Matcher<Decl> VarNodeMatcher) { +static Matcher<Stmt> callByRef(Matcher<Decl> VarNodeMatcher) { return callExpr(forEachArgumentWithParam( declRefExpr(to(varDecl(VarNodeMatcher))), parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); } -static internal::Matcher<Stmt> -assignedToRef(internal::Matcher<Decl> VarNodeMatcher) { +static Matcher<Stmt> assignedToRef(Matcher<Decl> VarNodeMatcher) { return declStmt(hasDescendant(varDecl( allOf(hasType(referenceType()), hasInitializer(anyOf( @@ -123,14 +129,13 @@ assignedToRef(internal::Matcher<Decl> VarNodeMatcher) { declRefExpr(to(varDecl(VarNodeMatcher))))))))); } -static internal::Matcher<Stmt> -getAddrTo(internal::Matcher<Decl> VarNodeMatcher) { +static Matcher<Stmt> getAddrTo(Matcher<Decl> VarNodeMatcher) { return unaryOperator( hasOperatorName("&"), hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); } -static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { +static Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { return hasDescendant(stmt( anyOf(gotoStmt(), switchStmt(), returnStmt(), // Escaping and not known mutation of the loop counter is handled @@ -142,7 +147,7 @@ static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { assignedToRef(equalsBoundNode(std::string(NodeName)))))); } -static internal::Matcher<Stmt> forLoopMatcher() { +static Matcher<Stmt> forLoopMatcher() { return forStmt( hasCondition(simpleCondition("initVarName", "initVarRef")), // Initialization should match the form: 'int i = 6' or 'i = 42'. @@ -271,23 +276,26 @@ static bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, if (!isLoopStmt(LoopStmt)) return false; - // TODO: Match the cases where the bound is not a concrete literal but an - // integer with known value auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); if (Matches.empty()) return false; const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef"); - llvm::APInt BoundNum = - Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue(); + const Expr *BoundNumExpr = Matches[0].getNodeAs<Expr>("boundNum"); + + Expr::EvalResult BoundNumResult; + if (!BoundNumExpr || !BoundNumExpr->EvaluateAsInt(BoundNumResult, ASTCtx, + Expr::SE_NoSideEffects)) { + return false; + } llvm::APInt InitNum = Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); - unsigned MaxWidth = std::max(InitNum.getBitWidth(), BoundNum.getBitWidth()); + unsigned MaxWidth = std::max(InitNum.getBitWidth(), + BoundNumResult.Val.getInt().getBitWidth()); InitNum = InitNum.zext(MaxWidth); - BoundNum = BoundNum.zext(MaxWidth); - + llvm::APInt BoundNum = BoundNumResult.Val.getInt().zext(MaxWidth); if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); else diff --git a/clang/test/Analysis/loop-unrolling.cpp b/clang/test/Analysis/loop-unrolling.cpp index ebae81e000c7a..8a4690b9b6c98 100644 --- a/clang/test/Analysis/loop-unrolling.cpp +++ b/clang/test/Analysis/loop-unrolling.cpp @@ -1,5 +1,5 @@ -// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify=expected,default -std=c++14 -analyzer-config exploration_strategy=unexplored_first_queue %s -// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify=expected,dfs -std=c++14 %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify=expected,default -std=c++17 -analyzer-config exploration_strategy=unexplored_first_queue %s +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify=expected,dfs -std=c++17 %s void clang_analyzer_numTimesReached(); void clang_analyzer_warnIfReached(); @@ -580,3 +580,21 @@ void test_escaping_on_var_before_switch_case_no_crash(int c) { } } } + +template <int Val> struct Integer { + static constexpr int value = Val; +}; + +void complicated_compile_time_upper_bound() { + static_assert((sizeof(char) * Integer<4>::value + 3) == 7); + for (int i = 0; i < (sizeof(char) * Integer<4>::value + (((3)))); ++i) { + clang_analyzer_numTimesReached(); // expected-warning {{7}} + } +} + +void complicated_compile_time_upper_bound_indirect() { + using Seven = Integer<(sizeof(char) * Integer<4>::value + 3)>; + for (int i = 0; i < ((Seven::value)); ++i) { + clang_analyzer_numTimesReached(); // expected-warning {{7}} + } +} _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
