seaneveson updated this revision to Diff 37462.
seaneveson added a comment.
Set CausedByPointerEscape to true
Check if the loop has already been exited before widening
Changed tests to use void clang_analyze_eval(int)
Added variable bound loop tests
Added nested loop tests
http://reviews.llvm.org/D12358
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CMakeLists.txt
lib/StaticAnalyzer/Core/CoreEngine.cpp
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/LoopWidening.cpp
test/Analysis/analyzer-config.c
test/Analysis/analyzer-config.cpp
test/Analysis/loop-widening.c
Index: test/Analysis/loop-widening.c
===================================================================
--- test/Analysis/loop-widening.c
+++ test/Analysis/loop-widening.c
@@ -0,0 +1,202 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-store=region -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_not_widened(int x) {
+ int i = 0;
+ int t = 1;
+ while (i < x) {
+ ++i;
+ }
+ clang_analyzer_eval(t == 1); // expected-warning {{TRUE}}
+}
+
+void variable_break_exiting_loops_not_widened(int x) {
+ int i = 0;
+ int t = 1;
+ while (1) {
+ ++i;
+ if (x) break;
+ }
+ clang_analyzer_eval(t == 1); // expected-warning {{TRUE}}
+}
+
+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}}
+ }
+ // FIXME This point is never reached as a sink is generated the second time
+ // the inner loop is visited.
+ clang_analyzer_eval(i >= 10); // no-warning
+}
+
+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}}
+}
Index: test/Analysis/analyzer-config.cpp
===================================================================
--- test/Analysis/analyzer-config.cpp
+++ test/Analysis/analyzer-config.cpp
@@ -36,5 +36,6 @@
// 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 = 19
+// CHECK-NEXT: num-entries = 20
Index: test/Analysis/analyzer-config.c
===================================================================
--- test/Analysis/analyzer-config.c
+++ test/Analysis/analyzer-config.c
@@ -25,6 +25,7 @@
// 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 = 14
+// CHECK-NEXT: num-entries = 15
Index: lib/StaticAnalyzer/Core/LoopWidening.cpp
===================================================================
--- lib/StaticAnalyzer/Core/LoopWidening.cpp
+++ lib/StaticAnalyzer/Core/LoopWidening.cpp
@@ -0,0 +1,108 @@
+//===--- 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();
+ }
+}
+
+typedef llvm::SmallPtrSet<const CFGBlock *, 8> CFGBlockSet;
+
+/// Recursivly look for break points until reaching an already visited block
+static const CFGBlock *getBreakBlock(const CFGBlock *Block,
+ CFGBlockSet *Visited) {
+ if (Visited->count(Block))
+ return nullptr;
+ Visited->insert(Block);
+ if (!Block->getTerminator().getStmt())
+ return nullptr;
+ if (Block->getTerminator()->getStmtClass() == Stmt::BreakStmtClass)
+ return Block;
+ // Recurse
+ const CFGBlock *result;
+ for (auto it = Block->succ_begin(), end = Block->succ_end();
+ it != end; ++it) {
+ if (result = getBreakBlock(*it, Visited))
+ return result;
+ }
+ return nullptr;
+}
+
+namespace clang {
+namespace ento {
+
+const CFGBlock *getBlockAfterLoop(const CFGBlock *LoopHead) {
+ // Get the ID of the block after the loop
+ const CFGBlock *FalseBranch = *(LoopHead->succ_begin()+1);
+ if (FalseBranch)
+ return FalseBranch;
+ // If there isn't a false branch we still have to check for break points
+ CFGBlockSet Visited;
+ Visited.insert(LoopHead);
+ const CFGBlock *BreakBlock = getBreakBlock(*(LoopHead->succ_begin()),
+ &Visited);
+ if (BreakBlock)
+ return *(BreakBlock->succ_begin());
+
+ return nullptr;
+}
+
+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 Fix nested loops.
+ const StackFrameContext *STC = LCtx->getCurrentStackFrame();
+ MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
+ const unsigned NumRegions = 3;
+ const MemRegion *Regions[NumRegions] = {
+ MRMgr.getStackLocalsRegion(STC),
+ MRMgr.getStackArgumentsRegion(STC),
+ MRMgr.getGlobalsRegion()
+ };
+ RegionAndSymbolInvalidationTraits ITraits;
+ for (int RegionIndex = 0; RegionIndex < NumRegions; ++ RegionIndex) {
+ ITraits.setTrait(Regions[RegionIndex],
+ RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
+ }
+ return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
+ BlockCount, LCtx, true, nullptr,
+ nullptr, &ITraits);
+}
+
+} // end namespace ento
+} // end namespace clang
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -26,6 +26,7 @@
#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"
@@ -1391,8 +1392,31 @@
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 without exiting, 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;
+ const LocationContext *LCtx = Pred->getLocationContext();
+ // Check the loop hasn't already been exited.
+ const CFGBlock *Following = getBlockAfterLoop(L.getDst());
+ if (Following && nodeBuilder.getContext().Eng.blockWasVisited(Following))
+ return;
+
+ // Widen.
+ ProgramStateRef WidenedState = getWidenedLoopState(Pred->getState(),
+ LCtx, BlockCount,
+ Term);
+ nodeBuilder.generateNode(WidenedState, Pred);
+ return;
+ }
+
// FIXME: Refactor this into a checker.
- if (nodeBuilder.getContext().blockCount() >= AMgr.options.maxBlockVisitOnPath) {
+ if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
const ExplodedNode *Sink =
nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -322,6 +322,7 @@
void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
ExplodedNode *Pred) {
+ blocksVisited.insert(L.getBlock());
// Increment the block counter.
const LocationContext *LC = Pred->getLocationContext();
Index: lib/StaticAnalyzer/Core/CMakeLists.txt
===================================================================
--- lib/StaticAnalyzer/Core/CMakeLists.txt
+++ lib/StaticAnalyzer/Core/CMakeLists.txt
@@ -27,6 +27,7 @@
ExprEngineObjC.cpp
FunctionSummary.cpp
HTMLDiagnostics.cpp
+ LoopWidening.cpp
MemRegion.cpp
PathDiagnostic.cpp
PlistDiagnostics.cpp
Index: lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
===================================================================
--- lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
+++ lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
@@ -338,3 +338,7 @@
InlineLambdas = getBooleanOption("inline-lambdas", /*Default=*/true);
return InlineLambdas.getValue();
}
+
+bool AnalyzerOptions::shouldWidenLoops() {
+ return getBooleanOption("widen-loops", false);
+}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
@@ -0,0 +1,41 @@
+//===--- 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"
+#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
+
+namespace clang {
+namespace ento {
+
+/// \brief Return the basic block that comes after the loop
+const CFGBlock *getBlockAfterLoop(const CFGBlock *LoopHead);
+
+/// \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
Index: include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -80,6 +80,9 @@
/// usually because it could not reason about something.
BlocksAborted blocksAborted;
+ /// The blocks that have been visited during analysis
+ llvm::DenseSet<const CFGBlock *> blocksVisited;
+
/// The information about functions shared by the whole translation unit.
/// (This data is owned by AnalysisConsumer.)
FunctionSummariesTy *FunctionSummaries;
@@ -139,6 +142,9 @@
WList->hasWork() ||
wasBlockAborted(); }
+ /// Check if a basic block was visited
+ bool blockWasVisited(const CFGBlock *B) const { return blocksVisited.count(B); }
+
/// Inform the CoreEngine that a basic block was aborted because
/// it could not be completely analyzed.
void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
Index: include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
===================================================================
--- include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
+++ include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
@@ -262,6 +262,9 @@
/// \sa shouldInlineLambdas
Optional<bool> InlineLambdas;
+ /// \sa shouldWidenLoops
+ 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
@@ -526,6 +529,11 @@
/// 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),
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
