[analyzer] Unroll loops of compile-time upper-bounded loops

[steakhal]

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

[llvmbot]

@llvm/pr-subscribers-clang

@llvm/pr-subscribers-clang-static-analyzer-1

Author: Balázs Benics (steakhal)

Changes

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

---

Full diff: https://github.com/llvm/llvm-project/pull/169400.diff

2 Files Affected:

• (modified) clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp (+17-12)
• (modified) clang/test/Analysis/loop-unrolling.cpp (+20-2)

diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
index 01d87b02fcdbd..6148b22d74240 100644
--- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
+++ b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
@@ -84,15 +84,17 @@ ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
 
 static internal::Matcher<Stmt> simpleCondition(StringRef BindName,
                                                StringRef RefName) {
+  auto LoopVariable = ignoringParenImpCasts(
+      declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName)))
+          .bind(RefName));
+  auto UpperBound = ignoringParenImpCasts(expr().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");
 }
 
@@ -271,23 +273,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}}
+  }
+}

[steakhal]

This hunk was just hoisted, and hasEitherOperand was replaced by an explicit matching to LHS and RHS because the patterns are somewhat overlapping due to the expr() matcher.

[steakhal]

These outcomes would be 4 without the patch, due to the block count limit which is relied upon in case loop unrolling is not applicable.

[Xazax-hun]

Overall, looks good. One question inline.