Revert r251621 "[Analyzer] Widening loops which do not exit" (bot failure)

Seems to be causing clang-cmake-mips build bot to fail (timeout)

http://lab.llvm.org:8011/builders/clang-cmake-mips/builds/10299

llvm-svn: 251697

9 files changed, 3 insertions, 332 deletions

diff --git a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
index 3959de24d43..a6e56107150 100644
--- a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -262,9 +262,6 @@ private:
   /// \sa shouldInlineLambdas
   Optional<bool> InlineLambdas;
 
-  /// \sa shouldWidenLoops
-  Optional<bool> WidenLoops;
-
   /// A helper function that retrieves option for a given full-qualified
   /// checker name.
   /// Options for checkers can be specified via 'analyzer-config' command-line
@@ -529,10 +526,6 @@ public:
   /// generated each time a LambdaExpr is visited.
   bool shouldInlineLambdas();
 
-  /// Returns true if the analysis should try to widen loops.
-  /// This is controlled by the 'widen-loops' config option.
-  bool shouldWidenLoops();
-
 public:
   AnalyzerOptions() :
     AnalysisStoreOpt(RegionStoreModel),
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
deleted file mode 100644
index aac600c67a2..00000000000
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
+++ /dev/null
@@ -1,37 +0,0 @@
-//===--- LoopWidening.h - Instruction class definition ----------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-///
-/// This header contains the declarations of functions which are used to widen
-/// loops which do not otherwise exit. The widening is done by invalidating
-/// anything which might be modified by the body of the loop.
-///
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
-#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
-
-#include "clang/Analysis/CFG.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
-
-namespace clang {
-namespace ento {
-
-/// \brief Get the states that result from widening the loop.
-///
-/// Widen the loop by invalidating anything that might be modified
-/// by the loop body in any iteration.
-ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
-                                    const LocationContext *LCtx,
-                                    unsigned BlockCount,
-                                    const Stmt *LoopStmt);
-
-} // end namespace ento
-} // end namespace clang
-
-#endif
diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
index 54c668cd2d6..bf8369ea35f 100644
--- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -338,9 +338,3 @@ bool AnalyzerOptions::shouldInlineLambdas() {
     InlineLambdas = getBooleanOption("inline-lambdas", /*Default=*/true);
   return InlineLambdas.getValue();
 }
-
-bool AnalyzerOptions::shouldWidenLoops() {
-  if (!WidenLoops.hasValue())
-    WidenLoops = getBooleanOption("widen-loops", /*Default=*/false);
-  return WidenLoops.getValue();
-}
diff --git a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
index aaffb0b82ce..4499323de93 100644
--- a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
+++ b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
@@ -28,7 +28,6 @@ add_clang_library(clangStaticAnalyzerCore
   ExprEngineObjC.cpp
   FunctionSummary.cpp
   HTMLDiagnostics.cpp
-  LoopWidening.cpp
   MemRegion.cpp
   PathDiagnostic.cpp
   PlistDiagnostics.cpp
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index b6aed88c600..f6129a963f8 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -26,7 +26,6 @@
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
 #include "llvm/ADT/ImmutableList.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/raw_ostream.h"
@@ -1396,25 +1395,8 @@ void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
 
-  // If this block is terminated by a loop and it has already been visited the
-  // maximum number of times, widen the loop.
-  unsigned int BlockCount = nodeBuilder.getContext().blockCount();
-  if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
-      AMgr.options.shouldWidenLoops()) {
-    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
-    if (!(Term &&
-          (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
-      return;
-    // Widen.
-    const LocationContext *LCtx = Pred->getLocationContext();
-    ProgramStateRef WidenedState =
-        getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
-    nodeBuilder.generateNode(WidenedState, Pred);
-    return;
-  }
-
   // FIXME: Refactor this into a checker.
-  if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
+  if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
     static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
     const ExplodedNode *Sink =
                    nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
diff --git a/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp b/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp
deleted file mode 100644
index 1fc871f60be..00000000000
--- a/clang/lib/StaticAnalyzer/Core/LoopWidening.cpp
+++ /dev/null
@@ -1,68 +0,0 @@
-//===--- LoopWidening.cpp - Instruction class definition --------*- 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 widen loops. A loop may be
-/// widened to approximate the exit state(s), without analyzing every
-/// iteration. The widening is done by invalidating anything which might be
-/// modified by the body of the loop.
-///
-//===----------------------------------------------------------------------===//
-
-#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
-
-using namespace clang;
-using namespace ento;
-
-/// Return the loops condition Stmt or NULL if LoopStmt is not a loop
-static const Expr *getLoopCondition(const Stmt *LoopStmt) {
-  switch (LoopStmt->getStmtClass()) {
-  default:
-    return NULL;
-  case Stmt::ForStmtClass:
-    return cast<ForStmt>(LoopStmt)->getCond();
-  case Stmt::WhileStmtClass:
-    return cast<WhileStmt>(LoopStmt)->getCond();
-  case Stmt::DoStmtClass:
-    return cast<DoStmt>(LoopStmt)->getCond();
-  }
-}
-
-namespace clang {
-namespace ento {
-
-ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
-                                    const LocationContext *LCtx,
-                                    unsigned BlockCount, const Stmt *LoopStmt) {
-
-  assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
-         isa<DoStmt>(LoopStmt));
-
-  // Invalidate values in the current state.
-  // TODO Make this more conservative by only invalidating values that might
-  //      be modified by the body of the loop.
-  // TODO Nested loops are currently widened as a result of the invalidation
-  //      being so inprecise. When the invalidation is improved, the handling
-  //      of nested loops will also need to be improved.
-  const StackFrameContext *STC = LCtx->getCurrentStackFrame();
-  MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
-  const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
-                                MRMgr.getStackArgumentsRegion(STC),
-                                MRMgr.getGlobalsRegion()};
-  RegionAndSymbolInvalidationTraits ITraits;
-  for (auto *Region : Regions) {
-    ITraits.setTrait(Region,
-                     RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
-  }
-  return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
-                                      BlockCount, LCtx, true, nullptr, nullptr,
-                                      &ITraits);
-}
-
-} // end namespace ento
-} // end namespace clang
diff --git a/clang/test/Analysis/analyzer-config.c b/clang/test/Analysis/analyzer-config.c
index 6faeeb3bf73..5fe53249d77 100644
--- a/clang/test/Analysis/analyzer-config.c
+++ b/clang/test/Analysis/analyzer-config.c
@@ -25,7 +25,6 @@ void foo() {
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
-// CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 15
+// CHECK-NEXT: num-entries = 14
 
diff --git a/clang/test/Analysis/analyzer-config.cpp b/clang/test/Analysis/analyzer-config.cpp
index 23f08286eb7..57913321f42 100644
--- a/clang/test/Analysis/analyzer-config.cpp
+++ b/clang/test/Analysis/analyzer-config.cpp
@@ -36,6 +36,5 @@ public:
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
-// CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 20
+// CHECK-NEXT: num-entries = 19
diff --git a/clang/test/Analysis/loop-widening.c b/clang/test/Analysis/loop-widening.c
deleted file mode 100644
index 0b9bf708087..00000000000
--- a/clang/test/Analysis/loop-widening.c
+++ /dev/null
@@ -1,190 +0,0 @@
-// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %s
-
-void clang_analyzer_eval(int);
-void clang_analyzer_warnIfReached();
-
-typedef __typeof(sizeof(int)) size_t;
-void *malloc(size_t);
-void free(void *);
-
-void loop_which_iterates_limit_times_not_widened() {
-  int i;
-  int x = 1;
-  // Check loop isn't widened by checking x isn't invalidated
-  for (i = 0; i < 1; ++i) {}
-  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
-  for (i = 0; i < 2; ++i) {}
-  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
-  for (i = 0; i < 3; ++i) {}
-  // FIXME loss of precision as a result of evaluating the widened loop body
-  //       *instead* of the last iteration.
-  clang_analyzer_eval(x == 1); // expected-warning {{UNKNOWN}}
-}
-
-int a_global;
-
-void loop_evaluated_before_widening() {
-  int i;
-  a_global = 1;
-  for (i = 0; i < 10; ++i) {
-    if (i == 2) {
-      // True before widening then unknown after.
-      clang_analyzer_eval(a_global == 1); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}}
-    }
-  }
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void warnings_after_loop() {
-  int i;
-  for (i = 0; i < 10; ++i) {}
-  char *m = (char*)malloc(12);
-} // expected-warning {{Potential leak of memory pointed to by 'm'}}
-
-void for_loop_exits() {
-  int i;
-  for (i = 0; i < 10; ++i) {}
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void while_loop_exits() {
-  int i = 0;
-  while (i < 10) {++i;}
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void do_while_loop_exits() {
-  int i = 0;
-  do {++i;} while (i < 10);
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void loop_body_is_widened() {
-  int i = 0;
-  while (i < 100) {
-    if (i > 10) {
-      clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-    }
-    ++i;
-  }
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void invariably_infinite_loop() {
-  int i = 0;
-  while (1) { ++i; }
-  clang_analyzer_warnIfReached(); // no-warning
-}
-
-void invariably_infinite_break_loop() {
-  int i = 0;
-  while (1) {
-    ++i;
-    int x = 1;
-    if (!x) break;
-  }
-  clang_analyzer_warnIfReached(); // no-warning
-}
-
-void reachable_break_loop() {
-  int i = 0;
-  while (1) {
-    ++i;
-    if (i == 100) break;
-  }
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void condition_constrained_true_in_loop() {
-  int i = 0;
-  while (i < 50) {
-    clang_analyzer_eval(i < 50); // expected-warning {{TRUE}}
-    ++i;
-  }
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void condition_constrained_false_after_loop() {
-  int i = 0;
-  while (i < 50) {
-    ++i;
-  }
-  clang_analyzer_eval(i >= 50); // expected-warning {{TRUE}}
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void multiple_exit_test() {
-  int x = 0;
-  int i = 0;
-  while (i < 50) {
-    if (x) {
-      i = 10;
-      break;
-    }
-    ++i;
-  }
-  // Reachable by 'normal' exit
-  if (i == 50) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-  // Reachable by break point
-  if (i == 10) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-  // Not reachable
-  if (i < 10) clang_analyzer_warnIfReached(); // no-warning
-  if (i > 10 && i < 50) clang_analyzer_warnIfReached(); // no-warning
-}
-
-void pointer_doesnt_leak_from_loop() {
-  int *h_ptr = (int *) malloc(sizeof(int));
-  for (int i = 0; i < 2; ++i) {}
-  for (int i = 0; i < 10; ++i) {} // no-warning
-  free(h_ptr);
-}
-
-int g_global;
-
-void unknown_after_loop(int s_arg) {
-  g_global = 0;
-  s_arg = 1;
-  int s_local = 2;
-  int *h_ptr = malloc(sizeof(int));
-
-  for (int i = 0; i < 10; ++i) {}
-
-  clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(s_arg); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(s_local); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(h_ptr == 0); // expected-warning {{UNKNOWN}}
-  free(h_ptr);
-}
-
-void variable_bound_exiting_loops_widened(int x) {
-  int i = 0;
-  int t = 1;
-  while (i < x) {
-    ++i;
-  }
-  clang_analyzer_eval(t == 1); // expected-warning {{TRUE}} // expected-warning {{UNKNOWN}}
-}
-
-void nested_loop_outer_widen() {
-  int i = 0, j = 0;
-  for (i = 0; i < 10; i++) {
-    clang_analyzer_eval(i < 10); // expected-warning {{TRUE}}
-    for (j = 0; j < 2; j++) {
-      clang_analyzer_eval(j < 2); // expected-warning {{TRUE}}
-    }
-    clang_analyzer_eval(j >= 2); // expected-warning {{TRUE}}
-  }
-  clang_analyzer_eval(i >= 10); // expected-warning {{TRUE}}
-}
-
-void nested_loop_inner_widen() {
-  int i = 0, j = 0;
-  for (i = 0; i < 2; i++) {
-    clang_analyzer_eval(i < 2); // expected-warning {{TRUE}}
-    for (j = 0; j < 10; j++) {
-      clang_analyzer_eval(j < 10); // expected-warning {{TRUE}}
-    }
-    clang_analyzer_eval(j >= 10); // expected-warning {{TRUE}}
-  }
-  clang_analyzer_eval(i >= 2); // expected-warning {{TRUE}}
-}