{StaticAnalyzer} LoopUnrolling: Keep track the maximum number of steps for each loop

[szepet]

Summary

This way the unrolling can be restricted for loops which will take at most a given number of steps. It is defined as 128 in this patch and it seems to have a good number for that purpose.

[NoQ]

LGTM, thanks! Minor nit included. I hope our matchers actually cover all the cases (not a big deal if they don't though).

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

26 ↗

(On Diff #112789)

I'd prefer a (static) const int, dealing preprocessor doesn't seem to be necessary here.

[szepet]

Updated to use static int.

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

 class AnalysisManager;
 
 /// Returns if the given State indicates that is inside a completely unrolled
 /// loop.
 bool isUnrolledState(ProgramStateRef State);
 
 /// Updates the stack of loops contained by the ProgramState.
 ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
-                                ExplodedNode* Pred);
+                                ExplodedNode* Pred, unsigned maxVisitOnPath);
 
 /// Updates the given ProgramState. In current implementation it removes the top
 /// element of the stack of loops.
 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State);
 
 } // end namespace ento
 } // end namespace clang
 
 #endif

cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp

 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   // If we reach a loop which has a known bound (and meets
   // other constraints) then consider completely unrolling it.
   if(AMgr.options.shouldUnrollLoops()) {
+    unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
     if (Term) {
       ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
-                                                 Pred);
+                                                 Pred, maxBlockVisitOnPath);
       if (NewState != Pred->getState()) {
         ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
         if (!UpdatedNode)
           return;
         Pred = UpdatedNode;
       }
     }
     // Is we are inside an unrolled loop then no need the check the counters.

cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 #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 {
 private:
   enum Kind { Normal, Unrolled } K;
   const Stmt *LoopStmt;
   const LocationContext *LCtx;
-  LoopState(Kind InK, const Stmt *S, const LocationContext *L)
-      : K(InK), LoopStmt(S), LCtx(L) {}
+  unsigned maxStep;
+  LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N)
+      : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
 
 public:
-  static LoopState getNormal(const Stmt *S, const LocationContext *L) {
-    return LoopState(Normal, S, L);
-  }
-  static LoopState getUnrolled(const Stmt *S, const LocationContext *L) {
-    return LoopState(Unrolled, S, L);
+  static LoopState getNormal(const Stmt *S, const LocationContext *L,
+                             unsigned N) {
+    return LoopState(Normal, S, L, N);
+  }
+  static LoopState getUnrolled(const Stmt *S, const LocationContext *L,
+                               unsigned N) {
+    return LoopState(Unrolled, S, L, N);
   }
   bool isUnrolled() const { return K == Unrolled; }
+  unsigned getMaxStep() const { return maxStep; }
   const Stmt *getLoopStmt() const { return LoopStmt; }
   const LocationContext *getLocationContext() const { return LCtx; }
   bool operator==(const LoopState &X) const {
     return K == X.K && LoopStmt == X.LoopStmt;
   }
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.AddInteger(K);
     ID.AddPointer(LoopStmt);
     ID.AddPointer(LCtx);
+    ID.AddInteger(maxStep);
   }
 };
 
 // The tracked stack of loops. The stack indicates that which loops the
 // simulated element contained by. The loops are marked depending if we decided
 // to unroll them.
 // TODO: The loop stack should not need to be in the program state since it is
 // lexical in nature. Instead, the stack of loops should be tracked in the

 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("!=")),
+  return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
+                              hasOperatorName("<="), hasOperatorName(">="),
+                              hasOperatorName("!=")),
+                        hasEitherOperand(ignoringParenImpCasts(declRefExpr(
+                            to(varDecl(hasType(isInteger())).bind(BindName))))),
                         hasEitherOperand(ignoringParenImpCasts(
-          declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))),
-      hasEitherOperand(ignoringParenImpCasts(integerLiteral())));
+                            integerLiteral().bind("boundNum"))))
+      .bind("conditionOperator");
 }
 
 static internal::Matcher<Stmt>
 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
   return anyOf(
       unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
                     hasUnaryOperand(ignoringParenImpCasts(
                         declRefExpr(to(varDecl(VarNodeMatcher)))))),
return hasDescendant(stmt(
             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(integerLiteral()),
-                                         equalsBoundNode("initVarName"))))),
-                       binaryOperator(hasLHS(declRefExpr(to(varDecl(
-                                          equalsBoundNode("initVarName"))))),
-                                      hasRHS(integerLiteral())))),
+             hasLoopInit(anyOf(
+                 declStmt(hasSingleDecl(varDecl(
+                     allOf(hasInitializer(integerLiteral().bind("initNum")),
+                 binaryOperator(hasLHS(declRefExpr(to(
+                                    varDecl(equalsBoundNode("initVarName"))))),
+                                hasRHS(integerLiteral().bind("initNum"))))),
              // 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");
if (!Match.empty())
       return true;
 
     N = N->getFirstPred();
   }
   llvm_unreachable("Reached root without finding the declaration of VD");
 }
 
 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
-                            ExplodedNode *Pred) {
+                            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;
 
   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
+  auto BoundNum = Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
+  auto InitNum = Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
+  auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
+  if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
+    maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
+  else
+    maxStep = (BoundNum - InitNum).abs().getZExtValue();
 
   // 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())
-  {
+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) {
+                                ExplodedNode *Pred, unsigned maxVisitOnPath) {
   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()) {
     if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
       State = State->set<LoopStack>(LS.getTail());
-      State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
+      State = State->add<LoopStack>(
+          LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
     }
     return State;
   }
-
-  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) {
-    State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
+  unsigned maxStep;
+  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
+    State = State->add<LoopStack>(
+        LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
     return State;
   }
 
-  State = State->add<LoopStack>(LoopState::getUnrolled(LoopStmt, LCtx));
+  unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
+
+  unsigned innerMaxStep = maxStep * outerStep;
+  if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
+    State = State->add<LoopStack>(
+        LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
+  else
+    State = State->add<LoopStack>(
+        LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
   return State;
 }
 
 bool isUnrolledState(ProgramStateRef State) {
   auto LS = State->get<LoopStack>();
   if (LS.isEmpty() || !LS.getHead().isUnrolled())
     return false;
   return true;
 }
 }
 }

cfe/trunk/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++) {
     clang_analyzer_numTimesReached(); // expected-warning {{9}}
     a[i] = 42;
   }
   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
int nested_inlined_no_unroll1() {
   for (int i = 0; i < 9; i++) {
     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 {{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 {{14}}
int recursion_unroll2(bool b) {
   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) {
+    if (i == 4 && b) {
       recursion_unroll3(false);
       break;
     }
     clang_analyzer_numTimesReached(); // expected-warning {{10}}
   }
   int a = 22 / k;
   return 0;
 }

 
 int loop_exit_while_empty_loop_stack() {
   if (getNum())
     for (int i = 1; i < 8; i++)
       ;
   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;
+}
+
+int num_steps_over_limit1() {
+  for (int i = 0; i < 129; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+  }
+  return 0;
+}
+
+int num_steps_on_limit2() {
+  for (int i = 0; i < 2; i++) {
+    for (int j = 0; j < 64; j++) {
+      clang_analyzer_numTimesReached(); // expected-warning {{128}}
+    }
+  }
+  return 0;
+}
+
+int num_steps_over_limit2() {
+  for (int i = 0; i < 2; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{1}}
+    for (int j = 0; j <= 64; j++) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  }
+  return 0;
+}
+
+int num_steps_on_limit3() {
+  for (int i = 0; i < getNum(); i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    for (int j = 0; j < 32; j++) {
+      clang_analyzer_numTimesReached(); // expected-warning {{128}}
+    }
+  }
+  return 0;
+}
+
+int num_steps_over_limit3() {
+  for (int i = 0; i < getNum(); i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{1}}
+    for (int j = 0; j < 33; j++) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  }
+  return 0;
+}
+