[StaticAnalyzer] LoopUnrolling: Excluding loops which splits the state (make more branches)

[szepet]

Summary

Added check if the execution of the last step of the given unrolled loop has generated more branches. If yes, than treat it as a normal (non-unrolled) loop in the remaining part of the analysis.

[NoQ]

The heuristic makes perfect sense to me.

I think we could use some tests here.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

218–223

Could you comment on whether it's possible that both ifs happen (LoopStmt's node has more than one successor) and if it is, why do we behave correctly in this case?

[szepet]

Testfiles and function updated.

[szepet]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

218–223

Hmm I ve intended to write BlockEntrance instead of BlockEdge and in this case it wont happen that both of the ifStmts is true.

[NoQ]

LGTM!

I guess later it'd be great to comment on every numTimesReached() why is it supposed to be reached exactly that many times, as it's often unclear, especially with tricky control flow. Because if somebody accidentally breaks the test, they'd have no idea what it tests or why it should work this way.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

if (Matches.empty())
     return false;
 
   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
 
   // Check if the counter of the loop is not escaped before.
   return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
 }
 
+bool madeNewBranch(ExplodedNode* N, const Stmt* LoopStmt) {
+  const Stmt* S = nullptr;
+  while (!N->pred_empty())
+  {
+    if (N->succ_size() > 1)
+      return true;
+
+    ProgramPoint P = N->getLocation();
+    if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
+      S = BE->getBlock()->getTerminator();
+
+    if (S == LoopStmt)
+      return false;
+
+    N = N->getFirstPred();
+  }
+
+  llvm_unreachable("Reached root without encountering the previous step");
+}
+
 // updateLoopStack is called on every basic block, therefore it needs to be fast
 ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
                                 ExplodedNode* Pred) {
   auto State = Pred->getState();
   auto LCtx = Pred->getLocationContext();
 
   if (!isLoopStmt(LoopStmt))
     return State;
 
   auto LS = State->get<LoopStack>();
   if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
-      LCtx == LS.getHead().getLocationContext())
+      LCtx == LS.getHead().getLocationContext()) {
+    if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
+      State = State->set<LoopStack>(LS.getTail());
+      State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
+    }
     return State;
+  }
 
   if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) {
     State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
     return State;
   }
 
   State = State->add<LoopStack>(LoopState::getUnrolled(LoopStmt, LCtx));
   return State;

test/Analysis/loop-unrolling.cpp

 // RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 %s
 
 void clang_analyzer_numTimesReached();
+void clang_analyzer_warnIfReached();
 
 int getNum();
 void foo(int &);
 // Testing for loops.
 int simple_unroll1() {
   int a[9];
   int k = 42;
   for (int i = 0; i < 9; i++) {
int simple_no_unroll2() {
   }
   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
   return 0;
 }
 
 int simple_no_unroll3() {
   int a[9];
   int k = 42;
-  int i;
-  for (i = 0; i < 9; i++) {
+  for (int i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
     a[i] = 42;
     (void)&i;
   }
   int b = 22 / (k - 42); // no-warning
   return 0;
 }
 
for (i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
     a[i] = 42;
     int &j{i};
   }
   int b = 22 / (k - 42); // no-warning
   return 0;
 }
 
+int make_new_branches_loop_cached() {
+  for (int i = 0; i < 8; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    if(getNum()){
+        (void) i; // Since this Stmt does not change the State the analyzer
+                  // won't make a new execution path but reuse the earlier nodes.
+      }
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+  return 0;
+}
+
+int make_new_branches_loop_uncached() {
+  int l = 2;
+  for (int i = 0; i < 8; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    if(getNum()){
+      ++l;
+    }
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+  return 0;
+}
+
+int make_new_branches_loop_uncached2() {
+  int l = 2;
+  for (int i = 0; i < 8; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    if(getNum()){
+      ++l;
+    }
+    (void)&i; // This ensures that the loop won't be unrolled.
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+  return 0;
+}
+
+
 int escape_before_loop_no_unroll1() {
   int a[9];
   int k = 42;
   int i;
   int &j = i;
   for (i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
     a[i] = 42;
int escape_before_loop_no_unroll3() {
   return 0;
 }
 
 int nested_outer_unrolled() {
   int a[9];
   int k = 42;
   int j = 0;
   for (int i = 0; i < 9; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{16}}
-    for (j = 0; j < getNum(); ++j) {
-      clang_analyzer_numTimesReached(); // expected-warning {{15}}
+    clang_analyzer_numTimesReached(); // expected-warning {{1}}
+    for (j = 0; j < 9; ++j) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
       a[j] = 22;
+      (void) &j; // ensures that the inner loop won't be unrolled
     }
     a[i] = 42;
   }
   int b = 22 / (k - 42); // no-warning
   return 0;
 }
 
 int nested_inner_unrolled() {
int nested_inlined_unroll1() {
   }
   int a = 22 / k; // expected-warning {{Division by zero}}
   return 0;
 }
 
 int nested_inlined_no_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{26}}
-    k = simple_unknown_bound_loop();  // reevaluation without inlining
+    clang_analyzer_numTimesReached(); // expected-warning {{15}}
+    k = simple_unknown_bound_loop();  // reevaluation without inlining, splits the state as well
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
 
 int recursion_unroll1(bool b) {
   int k = 2;
   for (int i = 0; i < 5; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{14}}
-    if(i == 0 && b)
+    clang_analyzer_numTimesReached(); // expected-warning {{13}}
+    if(i == 0 && b) // Splits the state in the first iteration but the recursion
+                    // call will be unrolled anyway since the condition is known there.
       recursion_unroll1(false);
-    clang_analyzer_numTimesReached(); // expected-warning {{15}}
+    clang_analyzer_numTimesReached(); // expected-warning {{14}}
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
 int recursion_unroll2(bool b) {
   int k = 0;
   for (int i = 0; i < 5; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    clang_analyzer_numTimesReached(); // expected-warning {{9}}
     if(i == 0 && b)
       recursion_unroll2(false);
-    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    clang_analyzer_numTimesReached(); // expected-warning {{9}}
   }
   int a = 22 / k; // expected-warning {{Division by zero}}
   return 0;
 }
 
 int recursion_unroll3(bool b) {
   int k = 2;
   for (int i = 0; i < 5; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{10}}
     if(i == 4 && b) {
       recursion_unroll3(false);
       break;
     }
     clang_analyzer_numTimesReached(); // expected-warning {{10}}
   }
   int a = 22 / k;
   return 0;
 }
 
 int recursion_unroll4(bool b) {
   int k = 2;
   for (int i = 0; i < 5; i++) {
-    clang_analyzer_numTimesReached(); // expected-warning {{14}}
+    clang_analyzer_numTimesReached(); // expected-warning {{13}}
     if(i == 0 && b) {
       recursion_unroll4(false);
       continue;
     }
-    clang_analyzer_numTimesReached(); // expected-warning {{14}}
+    clang_analyzer_numTimesReached(); // expected-warning {{13}}
   }
   int a = 22 / k;
   return 0;
 }
 
 int num_steps_on_limit() {
   for (int i = 0; i < 128; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{128}}
   }
   clang_analyzer_numTimesReached(); // expected-warning {{1}}
   return 0;
-}
+}