[StaticAnalyzer] LoopUnrolling: Excluding loops which splits the state

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.

Differential Revision: https://reviews.llvm.org/D36962

1 files changed, 26 insertions, 1 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
index 7db628aa077..7b52dd6ca43 100644
--- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
+++ b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
@@ -204,6 +204,26 @@ bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
   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) {
@@ -215,8 +235,13 @@ ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
 
   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));