Revert "[StaticAnalyzer] Completely unrolling specific loops with known bound option"

Revert r308561 and r308558.

Clang-ppc64be-linux seems to crash while running the test cases.

llvm-svn: 308592

5 files changed, 1 insertions, 235 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
index 4a581bddd9c..32040e71163 100644
--- a/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp
@@ -272,7 +272,6 @@ void ExprInspectionChecker::checkEndAnalysis(ExplodedGraph &G, BugReporter &BR,
 
     reportBug(llvm::to_string(NumTimesReached), BR, N);
   }
-  ReachedStats.clear();
 }
 
 void ExprInspectionChecker::analyzerCrash(const CallExpr *CE,
diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
index d5d6527f4fc..6f48fcb9e20 100644
--- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -375,12 +375,6 @@ bool AnalyzerOptions::shouldWidenLoops() {
   return WidenLoops.getValue();
 }
 
-bool AnalyzerOptions::shouldUnrollLoops() {
-  if (!UnrollLoops.hasValue())
-    UnrollLoops = getBooleanOption("unroll-loops", /*Default=*/false);
-  return UnrollLoops.getValue();
-}
-
 bool AnalyzerOptions::shouldDisplayNotesAsEvents() {
   if (!DisplayNotesAsEvents.hasValue())
     DisplayNotesAsEvents =
diff --git a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
index 5ac4f942f37..85878f5e96e 100644
--- a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
+++ b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
@@ -35,7 +35,6 @@ add_clang_library(clangStaticAnalyzerCore
   ExprEngineObjC.cpp
   FunctionSummary.cpp
   HTMLDiagnostics.cpp
-  LoopUnrolling.cpp
   LoopWidening.cpp
   MemRegion.cpp
   PathDiagnostic.cpp
@@ -55,7 +54,6 @@ add_clang_library(clangStaticAnalyzerCore
 
   LINK_LIBS
   clangAST
-  clangASTMatchers
   clangAnalysis
   clangBasic
   clangLex
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 409fe173e26..eee5400fe17 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -17,7 +17,6 @@
 #include "PrettyStackTraceLocationContext.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/AST/ParentMap.h"
-#include "clang/Analysis/CFGStmtMap.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/Basic/Builtins.h"
@@ -28,7 +27,6 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
@@ -1499,27 +1497,6 @@ 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()) {
-    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;
-    }
-
-    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.
@@ -1687,6 +1664,7 @@ void ExprEngine::processBranch(const Stmt *Condition, const Stmt *Term,
   const LocationContext *LCtx = Pred->getLocationContext();
   PrettyStackTraceLocationContext StackCrashInfo(LCtx);
   currBldrCtx = &BldCtx;
+
   // Check for NULL conditions; e.g. "for(;;)"
   if (!Condition) {
     BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
deleted file mode 100644
index 20e2526d1b8..00000000000
--- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
+++ /dev/null
@@ -1,203 +0,0 @@
-//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-///
-/// This file contains functions which are used to decide if a loop worth to be
-/// unrolled. Moreover contains function which mark the CFGBlocks which belongs
-/// to the unrolled loop and store them in ProgramState.
-///
-//===----------------------------------------------------------------------===//
-
-#include "clang/Analysis/CFGStmtMap.h"
-#include "clang/ASTMatchers/ASTMatchers.h"
-#include "clang/ASTMatchers/ASTMatchFinder.h"
-#include "clang/AST/ParentMap.h"
-#include "clang/AST/StmtVisitor.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
-#include "llvm/ADT/Statistic.h"
-
-using namespace clang;
-using namespace ento;
-using namespace clang::ast_matchers;
-
-#define DEBUG_TYPE "LoopUnrolling"
-
-STATISTIC(NumTimesLoopUnrolled,
-          "The # of times a loop has got completely unrolled");
-
-REGISTER_MAP_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *, const CFGStmtMap *)
-
-namespace clang {
-namespace ento {
-
-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())));
-}
-
-static internal::Matcher<Stmt> changeIntBoundNode(StringRef NodeName) {
-  return anyOf(hasDescendant(unaryOperator(
-                   anyOf(hasOperatorName("--"), hasOperatorName("++")),
-                   hasUnaryOperand(ignoringParenImpCasts(
-                       declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))),
-               hasDescendant(binaryOperator(
-                   anyOf(hasOperatorName("="), hasOperatorName("+="),
-                         hasOperatorName("/="), hasOperatorName("*="),
-                         hasOperatorName("-=")),
-                   hasLHS(ignoringParenImpCasts(
-                       declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
-}
-
-static internal::Matcher<Stmt> callByRef(StringRef NodeName) {
-  return hasDescendant(callExpr(forEachArgumentWithParam(
-      declRefExpr(to(varDecl(equalsBoundNode(NodeName)))),
-      parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))));
-}
-
-static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) {
-  return hasDescendant(varDecl(
-      allOf(hasType(referenceType()),
-            hasInitializer(anyOf(
-                initListExpr(has(
-                    declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))),
-                declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
-}
-
-static internal::Matcher<Stmt> getAddrTo(StringRef NodeName) {
-  return hasDescendant(unaryOperator(
-      hasOperatorName("&"),
-      hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName))))));
-}
-
-static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
-  return anyOf(hasDescendant(gotoStmt()), hasDescendant(switchStmt()),
-               // Escaping and not known mutation of the loop counter is handled
-               // by exclusion of assigning and address-of operators and
-               // pass-by-ref function calls on the loop counter from the body.
-               changeIntBoundNode(NodeName), callByRef(NodeName),
-               getAddrTo(NodeName), assignedToRef(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())))),
-             // 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");
-}
-
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) {
-
-  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);
-  return !Matches.empty();
-}
-
-namespace {
-class LoopBlockVisitor : public ConstStmtVisitor<LoopBlockVisitor> {
-public:
-  LoopBlockVisitor(llvm::SmallPtrSet<const CFGBlock *, 8> &BS) : BlockSet(BS) {}
-
-  void VisitChildren(const Stmt *S) {
-    for (const Stmt *Child : S->children())
-      if (Child)
-        Visit(Child);
-  }
-
-  void VisitStmt(const Stmt *S) {
-    // In case of nested loops we only unroll the inner loop if it's marked too.
-    if (!S || (isLoopStmt(S) && S != LoopStmt))
-      return;
-    BlockSet.insert(StmtToBlockMap->getBlock(S));
-    VisitChildren(S);
-  }
-
-  void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) {
-    BlockSet.clear();
-    StmtToBlockMap = M;
-    LoopStmt = Loop;
-    Visit(LoopStmt);
-  }
-
-private:
-  llvm::SmallPtrSet<const CFGBlock *, 8> &BlockSet;
-  const CFGStmtMap *StmtToBlockMap;
-  const Stmt *LoopStmt;
-};
-}
-// TODO: refactor this function using ScopeContext - once we have the
-// information when the simulation reaches the end of the loop we can cleanup
-// the state
-bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) {
-  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>()) {
-    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();
-    }
-
-    if (SearchedBlock)
-      return true;
-  }
-  return false;
-}
-
-ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
-                                   CFGStmtMap *StmtToBlockMap) {
-  if (State->contains<UnrolledLoops>(Term))
-    return State;
-
-  State = State->set<UnrolledLoops>(Term, StmtToBlockMap);
-  ++NumTimesLoopUnrolled;
-  return State;
-}
-}
-}