[StaticAnalyzer] LoopUnrolling: Handling conditions with known value variables

[szepet]

Summary

In order to completely unroll loops with known bound I moved the marking process (markLoopASUnrolled() function call, etc.) to the processBranch callback which takes place after the bound is already modeled. This way the bound can be checked to be known. Test cases added.

[NoQ]

While this wasn't necessary in the first patch, i think here we should start cleaning up the UnrolledLoops map when we exit the loop. Because next time we encounter the loop, we may no longer want to unroll it - the value may no longer be concrete.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

148–149

There's a FIXME in getKnownValue() that says that it doesn't work in some cases, eg. $x + 1 where $x$ is constrained to a constant.

Could you see if this affects your code and add a test case? We can probably fix it later because now we have simplifySVal().

[NoQ]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

148–149

I mean $x.

[NoQ]

Am i understanding correctly that this patch is waiting to be rebased on top of D35684?

[szepet]

In D34812#822645, @NoQ wrote:

Am i understanding correctly that this patch is waiting to be rebased on top of D35684?

Yes, you understand correctly and this raises a lot of problem which I could not solve.

If I move the updateLoopStack function call to the processBranch then it means that in processCFGBlockEntrance we wont have the information if the entered block is unrolled.
It could be OK since the loop is visited at least once so we will reach processBranch and add the loop to the LoopStack. However, in case of a nested loop, the second time we would enter the inner loop we will see that the BlockVisit counter is already higher than maxBlockVisitOnPath. So we wont even enter the block even if we would mark it as a unrolled loop.

so in the following example we wont enter the inner (and unrolled) loop the second time:

for (int i=0;i<2;i++){
  int& j = i; // outer loop not unrolled
  for (int j=0;j<5;j++){ //unrolled
      magic_stuff();
  }
}

Just to summarize the problem: the LoopStack would be updated later then we enter the first block of the loop. However, we check the counter when the block is entered.
I don't see a correct solution for that right know. The best I could come up to mark the blocks what was already unrolled and handle them as a special case.

[xazax.hun]

lib/StaticAnalyzer/Core/ExprEngine.cpp

1507

Asterisk on the wrong side.

1689

Maybe moving this check to the next if would reduce the indentation.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

47

Why did you introduce expr? Wouldn't binding to the declRefExpr part be sufficient?

135

This comment is not clear enough for me. Don't you already check for changes and escapes of the induction variable?

150

So you do not want to introduce a hard limit on the loop bound in this patch?

include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h

 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 
 namespace clang {
 namespace ento {
-    ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
-                                       CFGStmtMap *StmtToBlockMap);
-    bool isUnrolledLoopBlock(const CFGBlock *Block,
-                             ExplodedNode *Prev);
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx);
+bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev);
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                            ExplodedNode* Pred, SValBuilder &SVB);
 
 } // end namespace ento
 } // end namespace clang
 
 #endif

lib/StaticAnalyzer/Core/ExprEngine.cpp

 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   // If this block is terminated by a loop which has a known bound (and meets
   // other constraints) then consider completely unrolling it.
   if (AMgr.options.shouldUnrollLoops()) {
-    const CFGBlock *ActualBlock = nodeBuilder.getContext().getBlock();
-    const Stmt *Term = ActualBlock->getTerminator();
-    if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext())) {
-      ProgramStateRef UnrolledState =
-              markLoopAsUnrolled(Term, Pred->getState(), Pred->getLocationContext()->getAnalysisDeclContext()->getCFGStmtMap());
-      if (UnrolledState != Pred->getState())
-        nodeBuilder.generateNode(UnrolledState, Pred);
-      return;
-    }
-
+    const CFGBlock* ActualBlock = nodeBuilder.getContext().getBlock();
     if (isUnrolledLoopBlock(ActualBlock, Pred))
       return;
     if (ActualBlock->empty())
       return;
   }
 
   // If this block is terminated by a loop and it has already been visited the
   // maximum number of times, widen the loop.
void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
   // Check for NULL conditions; e.g. "for(;;)"
   if (!Condition) {
     BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
     NullCondBldr.markInfeasible(false);
     NullCondBldr.generateNode(Pred->getState(), true, Pred);
     return;
   }
 
+  if (AMgr.options.shouldUnrollLoops()) {
+    if (shouldCompletelyUnroll(Term, AMgr.getASTContext(), Pred, svalBuilder)) {
+      ProgramStateRef UnrolledState =
+              markLoopAsUnrolled(Term, Pred->getState(),
+                                 Pred->getLocationContext()->
+                                 getAnalysisDeclContext()->getCFGStmtMap());
+      if(UnrolledState != Pred->getState()) {
+        NodeBuilder UnrolledStateBldr(Pred, Dst, BldCtx);
+        UnrolledStateBldr.generateNode(Pred->getLocation(), UnrolledState,
+                                       Pred);
+        assert(Dst.size() == 1);
+        Pred = *Dst.begin();
+        Dst.clear();
+      }
+    }
+  }
+
   if (const Expr *Ex = dyn_cast<Expr>(Condition))
     Condition = Ex->IgnoreParens();
 
   Condition = ResolveCondition(Condition, BldCtx.getBlock());
   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
                                 Condition->getLocStart(),
                                 "Error evaluating branch");
 

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 static bool isLoopStmt(const Stmt *S) {
   return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
 }
 
 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())));
+      hasEitherOperand(expr(ignoringParenImpCasts(declRefExpr(
+                           to(varDecl(hasType(isInteger())).bind(BindName)))))
+                           .bind("CounterExp")),
+      hasEitherOperand(
+          expr(unless(equalsBoundNode("CounterExp"))).bind("BoundExp")));
 }
 
 static internal::Matcher<Stmt> changeIntBoundNode(StringRef NodeName) {
   return hasDescendant(binaryOperator(
       anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="),
             hasOperatorName("*="), hasOperatorName("-=")),
       hasLHS(ignoringParenImpCasts(
           declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))));
return doStmt(hasCondition(simpleCondition("initVarName")),
                     changeIntBoundNode("initVarName"), callByRef("initVarName"),
                     getAddrTo("initVarName"))))).bind("whileLoop");
 }
 
 static internal::Matcher<Stmt> loopMatcher() {
   return anyOf(doWhileLoopMatcher(), whileLoopMatcher(), forLoopMatcher());
 }
 
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) {
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                            ExplodedNode *Pred, SValBuilder &SVB) {
 
   if (!isLoopStmt(LoopStmt))
     return false;
 
-  // TODO: In cases of while and do..while statements the value of initVarName
-  // should be checked to be known
-  // TODO: Match the cases where the bound is not a concrete literal but an
-  // integer with known value
+  // TODO: Check for possibilities of changing the bound expression.
 
   auto Matches = match(loopMatcher(), *LoopStmt, ASTCtx);
-  return !Matches.empty();
+  if (Matches.empty())
+    return false;
+
+  const Expr *BoundExp = Matches[0].getNodeAs<Expr>("BoundExp");
+  const Expr *CounterExp = Matches[0].getNodeAs<Expr>("CounterExp");
+  auto State = Pred->getState();
+  auto LCtx = Pred->getLocationContext();
+  SVal BoundVal = State->getSVal(BoundExp, LCtx);
+  SVal CounterVal = State->getSVal(CounterExp, LCtx);
+
+  if (!SVB.getKnownValue(State, BoundVal) ||
+      !SVB.getKnownValue(State, CounterVal))
+    return false;
+
+  return true;
 }
 
 namespace {
 class LoopBlockVisitor : public ConstStmtVisitor<LoopBlockVisitor> {
 public:
   LoopBlockVisitor(llvm::SmallPtrSet<const CFGBlock *, 8> &BS)
       : BlockSet(BS), Found(false) {}
 
private:
   llvm::SmallPtrSet<const CFGBlock *, 8> &BlockSet;
   bool Found;
   const CFGStmtMap *StmtToBlockMap;
   const Stmt *LoopStmt;
 };
 }
 
 bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) {
-  const Stmt* Term = Block->getTerminator();
+  const Stmt *Term = Block->getTerminator();
   auto State = Prev->getState();
   // In case of nested loops in an inlined function should not be unrolled only
   // if the inner loop is marked.
   if (Term && isLoopStmt(Term) && !State->contains<UnrolledLoops>(Term))
     return false;
 
   const CFGBlock *SearchedBlock;
   llvm::SmallPtrSet<const CFGBlock *, 8> BlockSet;
   LoopBlockVisitor LBV(BlockSet);
   // Check the CFGBlocks of every marked loop.
-  for (auto& E : State->get<UnrolledLoops>()) {
+  for (auto &E : State->get<UnrolledLoops>()) {
     SearchedBlock = Block;
     const StackFrameContext *StackFrame = Prev->getStackFrame();
     LBV.setBlocksOfLoop(E.first, E.second);
     // In case of an inlined function call check if any of its callSiteBlock is
     // marked.
     while (SearchedBlock && BlockSet.find(SearchedBlock) == BlockSet.end()) {
       SearchedBlock = StackFrame->getCallSiteBlock();
       StackFrame = StackFrame->getParent()->getCurrentStackFrame();

test/Analysis/loop-unrolling.cpp

int nested_inlined_no_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
     k = simple_unknown_bound_loop(); // reevaluation without inlining
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
+int known_variable_unroll() {
+  int a[9];
+  int k = 42;
+  for (int i = 0; i < k; i++) {
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int known_variable_unroll2() {
+  int a[9];
+  int k = 42;
+  for (int i = 0; i < k / 2 + 12; i++) {
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
 // Testing while loops.
 int simple_unroll3() {
   int a[9];
   int k = 42;
   int i = 0;
   while (i < 9) {
     a[i] = 42 * i;
     ++i;
int simple_unroll6() {
   do {
     a[i] = 42 * i;
     --i;
   } while (i > 7);
   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
   return 0;
 }
 
+int known_variable_unroll3() {
+  int a[9];
+  int k = 42;
+  int i = 2;
+  do {
+    a[i] = 42 * i;
+    ++i;
+  } while (i < 9);
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
 int simple_no_unroll5() {
   int a[9];
   int k = 42;
   int i = 0;
   do {
     a[i] = 42 * i;
     i += getNum();
   } while (i < 9);
   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
   return 0;
 }
 
+int unknown_var_no_unroll1() {
+  int a[9];
+  int k = 42;
+  int i = getNum();
+  do {
+    a[i] = 42 * i;
+    ++i;
+  } while (i < 9);
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
 // CHECK: ... Statistics Collected ...
 // CHECK: 5 ExprEngine       - The # of times we re-evaluated a call without inlining
-// CHECK: 13 LoopUnrolling    - The # of times a loop has got completely unrolled
+// CHECK: 16 LoopUnrolling    - The # of times a loop has got completely unrolled