[Analyzer] Unroll for-loops where the upper boundary is a variable with know value

[baloghadamsoftware]

Summary

For-loops with a variable upper boundary do not differ very much from for-loops with integer literals if the value of the variable is known. Unroll these loops as well, similarly to them. This was a TODO anyway.

[Szelethus]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

216–218

Alright, I stood on top of this for longer than I'd like to admit, what's happening here? Like, CondExpr, with the given testfile, should be i < n, right? Then BoundExpr is supposed to be i, and if that is equal to Matches[0].getNodeAs<Expr>("boundVarOperand") (which I guess is supposed to n), which I'm not sure how it could ever happen, we assign the RHS of the assignment to BoundExpr?

What does this do? Why is it needed? Which 2 test cases cover these lines?

223–232

I don't see obvious test case for which BoundNumVal would be unknown, am I wrong?

[NoQ]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

216–218

I think this is about i < n vs. n > i.

223–232

We need an ExprInspection method that reliably produces an UnknownVal, because there's no truly valid reason to produce UnknownVal apart from "something is unimplemented".

[Szelethus]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

216–218

If that is the case, I'd be more comfortable seeing a test for it (there doesn't seem to be any) before landing this.

223–232

For this too.

[baloghadamsoftware]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

223–232

Wrong request! :-) The test case is there. Actually we need a test case for which 'BoundNumVal' is not unknown. That I still fail to produce.

[baloghadamsoftware]

Test case added for loop conditions written in reverse order and code fixed to make the test pass.

[baloghadamsoftware]

I am a bit afraid of the performance of the feature because of the extensive use of matchers. Based on my previous experiences matcher creation and disposition are expensive operations. Matchers are meant to be a kind of "static" structures created only once and destroyed at the end. Using them in the core infrastructure may negatively affect the execution time of the whole analysis. Maybe we should get rid of them before turning on this feature as default (which is the ultimate goal).

[Szelethus]

I think you forgot to remove /* */ and clang formatting before uploading the patch.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

216–218

I'd appreciate a few lines of comment, given that there's evidence that it might not be obvious what's happening here :^)

[NoQ]

/me has just noticed that this isn't D34812.

[Szelethus]

In D63279#1590676, @NoQ wrote:

/me has just noticed that this isn't D34812.

Oh great find! Is it worth seizing commandeering @baloghadamsoftware?

[baloghadamsoftware]

In D63279#1590676, @NoQ wrote:

/me has just noticed that this isn't D34812.

Oh, I just noticed that there was already an attempt to fix this :-) However, it seems that the review there died because the author left the work on the analyzer. My fix attempt is an answer to a user request. This patch does not intend to solve other problems, just the symbols with known value. However we are also interested in finalizing this project so it could be enabled as default in future versions of the analyzer. Maybe we should further discuss the open problems regarding it on cfe-dev or maybe in a personal meeting on Skype.

[baloghadamsoftware]

Fix wrong upload.

[baloghadamsoftware]

For me it is all the same whether to continue this patch or taking over Péter's.

[Szelethus]

In D63279#1606063, @baloghadamsoftware wrote:

For me it is all the same whether to continue this patch or taking over Péter's.

Well, there are plenty of comments I'm not sure ever got addressed. We could take an inventory of that as a start. @NoQ, do you have any *immediate* suggestion about the direction of this effort? If not, I'd be happy to dive deeper into the archaeology with Ádám and follow up with this later.

[NoQ]

A quick archaeological dig suggests that i had no concerns with turning on unrolling by default back in 2017: http://lists.llvm.org/pipermail/cfe-dev/2017-August/055221.html - and i don't think i had any new concerns since then. I guess it'll be beneficial to make one more large-codebase run to make sure it still works, but other than that the only reason it's not enabled by default yet is because we forgot to do that :( This patch is good but not a must-have to turn loop unrolling on by default.

[Szelethus]

In D63279#1630491, @NoQ wrote:

the only reason it's not enabled by default yet is because we forgot to do that :(

Damn, thats a bummer. It wouldn't be too much trouble to run an analysis and check out whether everything works correctly, so I might enable this myself.

[Szelethus]

In D63279#1630510, @Szelethus wrote:

In D63279#1630491, @NoQ wrote:

the only reason it's not enabled by default yet is because we forgot to do that :(

Damn, thats a bummer. It wouldn't be too much trouble to run an analysis and check out whether everything works correctly, so I might enable this myself.

Alright, I just started an analysis on this. Never too late, eh? I'll expect to have results in a day or two to see whether everything works as expected.

[NoQ]

In D63279#1901272, @Szelethus wrote:

Alright, I just started an analysis on this. Never too late, eh? I'll expect to have results in a day or two to see whether everything works as expected.

Do want!

[Szelethus]

(note: I forgot to submit this a couple weeks ago)

LLVM is crashing on me due to the issue mentioned in D75678, but on Bitcoin, Xerces, CppCheck and Rtags I observed no difference in between the 2 runs. I recall that others mentioned that @szepet used to run his analyses with other configurations. I'll read final report and take another look later.

http://lists.llvm.org/pipermail/cfe-dev/2017-August/055259.html

[xazax.hun]

In D63279#1939349, @Szelethus wrote:

(note: I forgot to submit this a couple weeks ago)

LLVM is crashing on me due to the issue mentioned in D75678, but on Bitcoin, Xerces, CppCheck and Rtags I observed no difference in between the 2 runs. I recall that others mentioned that @szepet used to run his analyses with other configurations. I'll read final report and take another look later.

http://lists.llvm.org/pipermail/cfe-dev/2017-August/055259.html

You mean no difference in the reports? It is very unlikely to get lucky and gain/loose reports. Peter used to check the statistics emitted by the analyzer such as basic block coverage.

[Szelethus]

In D63279#1939435, @xazax.hun wrote:

In D63279#1939349, @Szelethus wrote:

(note: I forgot to submit this a couple weeks ago)

LLVM is crashing on me due to the issue mentioned in D75678, but on Bitcoin, Xerces, CppCheck and Rtags I observed no difference in between the 2 runs. I recall that others mentioned that @szepet used to run his analyses with other configurations. I'll read final report and take another look later.

http://lists.llvm.org/pipermail/cfe-dev/2017-August/055259.html

You mean no difference in the reports? It is very unlikely to get lucky and gain/loose reports. Peter used to check the statistics emitted by the analyzer such as basic block coverage.

I'll be honest, I don't see myself redoing his evaluation anytime soon -- since its not crashing, I guess we could just enable it?

[martong]

FYI, I am working on repeating and reevaluating Peter's measurements with the current master. And if possible then I'd like to extend the measures for new C and C++ projects. I am planning to share the statistics and run-time results.

(Hopefully I'd be able to do measurements with this (or the alternative D34812) patch as well. And maybe for loop widening as well.)

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This file contains functions which are used to decide if a loop worth to be
 /// unrolled. Moreover, these functions manages the stack of loop which is
 /// tracked by the ProgramState.
 ///
 //===----------------------------------------------------------------------===//
 
-#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
 
 using namespace clang;
 using namespace ento;
 using namespace clang::ast_matchers;
 
 static const int MAXIMUM_STEP_UNROLLED = 128;
 
 struct LoopState {

 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
   auto LS = State->get<LoopStack>();
   if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
     State = State->set<LoopStack>(LS.getTail());
   return State;
 }
 
 static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
-  return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
-                              hasOperatorName("<="), hasOperatorName(">="),
-                              hasOperatorName("!=")),
-                        hasEitherOperand(ignoringParenImpCasts(declRefExpr(
-                            to(varDecl(hasType(isInteger())).bind(BindName))))),
-                        hasEitherOperand(ignoringParenImpCasts(
-                            integerLiteral().bind("boundNum"))))
+  return binaryOperator(
+             anyOf(hasOperatorName("<"), hasOperatorName(">"),
+                 declRefExpr(to(varDecl(allOf(hasType(isInteger()),
+                                              equalsBoundNode(BindName)))))
+                     .bind("boundVarOperand"))))
       .bind("conditionOperator");
 }
 
 static internal::Matcher<Stmt>
 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
   return anyOf(
       unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
                     hasUnaryOperand(ignoringParenImpCasts(
return hasDescendant(stmt(
             changeIntBoundNode(equalsBoundNode(NodeName)),
             callByRef(equalsBoundNode(NodeName)),
             getAddrTo(equalsBoundNode(NodeName)),
             assignedToRef(equalsBoundNode(NodeName)))));
 }
 
 static internal::Matcher<Stmt> forLoopMatcher() {
   return forStmt(
-             hasCondition(simpleCondition("initVarName")),
              // Initialization should match the form: 'int i = 6' or 'i = 42'.
-             hasLoopInit(
-                 anyOf(declStmt(hasSingleDecl(
-                           varDecl(allOf(hasInitializer(ignoringParenImpCasts(
-                                             integerLiteral().bind("initNum"))),
-                                         equalsBoundNode("initVarName"))))),
-                       binaryOperator(hasLHS(declRefExpr(to(varDecl(
-                                          equalsBoundNode("initVarName"))))),
-                                      hasRHS(ignoringParenImpCasts(
-                                          integerLiteral().bind("initNum")))))),
+             hasLoopInit(anyOf(
+                 declStmt(hasSingleDecl(
+                     varDecl(hasInitializer(ignoringParenImpCasts(
+                                 integerLiteral().bind("initNum"))))
+                         .bind("initVarName"))),
+                 binaryOperator(
+                     hasLHS(declRefExpr(to(varDecl().bind("initVarName")))),
+             hasCondition(simpleCondition("initVarName")),
              // Incrementation should be a simple increment or decrement
              // operator call.
              hasIncrement(unaryOperator(
                  anyOf(hasOperatorName("++"), hasOperatorName("--")),
                  hasUnaryOperand(declRefExpr(
                      to(varDecl(allOf(equalsBoundNode("initVarName"),
                                       hasType(isInteger())))))))),
-             unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
+             unless(hasBody(hasSuspiciousStmt("initVarName"))))
+      .bind("forLoop");
 }
 
 static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
   // Global variables assumed as escaped variables.
   if (VD->hasGlobalStorage())
     return true;
 
   while (!N->pred_empty()) {
while (!N->pred_empty()) {
 
     N = N->getFirstPred();
   }
   llvm_unreachable("Reached root without finding the declaration of VD");
 }
 
 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
                             ExplodedNode *Pred, unsigned &maxStep) {
-
   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 State = Pred->getState();
+  auto &SVB = State->getStateManager().getSValBuilder();
+
   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
-  llvm::APInt BoundNum =
-      Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
   llvm::APInt InitNum =
       Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
   auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
+
+  const Expr *BoundExpr = CondOp->getLHS()->IgnoreParenImpCasts();
+  if (BoundExpr == Matches[0].getNodeAs<Expr>("boundVarOperand"))
+    BoundExpr = CondOp->getRHS()->IgnoreParenImpCasts();
+  SVal BoundNumVal = Pred->getSVal(BoundExpr);
+
+  // If the value of the expression is unknown and it is a declaration
+  // reference then try to get the value of the declaration instead
+  if (BoundNumVal.isUnknown()) {
+    if (const auto *BoundDeclRefExpr = dyn_cast<DeclRefExpr>(BoundExpr)) {
+      // FIXME: Add other declarations such as Objective-C fields
+      if (const auto *BoundVarDecl =
+              dyn_cast<VarDecl>(BoundDeclRefExpr->getDecl())) {
+        BoundNumVal = State->getSVal(
+            State->getLValue(BoundVarDecl, Pred->getLocationContext()));
+      }
+    }
+  }
+  const llvm::APSInt *BoundNumPtr = SVB.getKnownValue(State, BoundNumVal);
+  if (!BoundNumPtr)
+    return false;
+  llvm::APInt BoundNum = *BoundNumPtr;
+
   if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
     InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
     BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
   }
 
   if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
     maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
   else

 }
 
 bool isUnrolledState(ProgramStateRef State) {
   auto LS = State->get<LoopStack>();
   if (LS.isEmpty() || !LS.getHead().isUnrolled())
     return false;
   return true;
 }
-}
-}
+} // namespace ento
+} // namespace clang

test/Analysis/loop-unrolling.cpp

 }
 
 
 void pr34943() {
   for (int i = 0; i < 6L; ++i) {
     clang_analyzer_numTimesReached(); // expected-warning {{6}}
   }
 }
+
+int unroll_known_value_of_variable1() {
+  int a[9];
+  int k = 42;
+  int n = 9;
+  for (int i = 0; i < n; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{9}}
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int unroll_known_value_of_variable2() {
+  int a[9];
+  int k = 42;
+  int n = 9;
+  for (int i = 0; n > i; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{9}}
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}