seaneveson updated this revision to Diff 35216.
seaneveson added a comment.
The TK_EntireMemSpace trait is now used when invalidating. The trait was added
in http://reviews.llvm.org/D12993, thank you Devin for that patch.
Updated to the latest trunk.
http://reviews.llvm.org/D12358
Files:
include/clang/StaticAnalyzer/Core/AnalyzerOptions.h
include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h
lib/StaticAnalyzer/Core/AnalyzerOptions.cpp
lib/StaticAnalyzer/Core/CMakeLists.txt
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/LoopWidening.cpp
test/Analysis/analyzer-config.c
test/Analysis/analyzer-config.cpp
test/Analysis/constant-bound-loops.c
Index: test/Analysis/constant-bound-loops.c
===================================================================
--- test/Analysis/constant-bound-loops.c
+++ test/Analysis/constant-bound-loops.c
@@ -0,0 +1,178 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-store=region -analyzer-max-loop 4 -analyzer-config widen-constant-bound-loops=true -verify %s
+
+extern void clang_analyzer_eval(_Bool);
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+
+void incr_for_loop() {
+ int i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void decr_for_loop() {
+ int i;
+ for (i = 10; i > 0; --i) {}
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void incr_while_loop() {
+ int i = 0;
+ while (i < 10) {++i;}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void decr_while_loop() {
+ int i = 10;
+ while (i > 0) {--i;}
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void incr_do_while_loop() {
+ int i = 0;
+ do {++i;} while (i < 10);
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void decr_do_while_loop() {
+ int i = 10;
+ do {--i;} while (i > 0);
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void negative_incr_for_loop() {
+ int i;
+ for (i = -10; i < 5 - 10; ++i) {}
+ clang_analyzer_eval(i == -5); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void negative_decr_for_loop() {
+ int i;
+ for (i = 5 - 10; i > -20; --i) {}
+ clang_analyzer_eval(i == -20); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void larger_incr_for_loop() {
+ int i;
+ for (i = 0; i < 20; i += 3) {}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void larger_decr_for_loop() {
+ int i;
+ for (i = 20; i > 0; i -= 3) {}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void unsigned_incr_for_loop() {
+ unsigned i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void unsigned_decr_for_loop() {
+ unsigned i;
+ for (i = 10; i > 0; --i) {}
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void short_for_loop() {
+ short i;
+ for (i = 0; i < 10; ++i) {}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void lte_for_loop() {
+ int i;
+ for (i = 0; i <= 10; ++i) {}
+ clang_analyzer_eval(i == 11); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void gte_for_loop() {
+ int i;
+ for (i = 10; i >= 0; --i) {}
+ clang_analyzer_eval(i == -1); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void incr_ne_for_loop() {
+ int i;
+ for (i = 0; i != 10; ++i) {}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void decr_ne_for_loop() {
+ int i;
+ for (i = 10; i != 0; --i) {}
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void reversed_condition_for_loop() {
+ int i;
+ for (i = 0; 10 > i; ++i) {}
+ clang_analyzer_eval(i == 10); // expected-warning {{TRUE}}
+ for (i = 10; 0 < i; --i) {}
+ clang_analyzer_eval(i == 0); // expected-warning {{TRUE}}
+ for (i = 0; 10 >= i; ++i) {}
+ clang_analyzer_eval(i == 11); // expected-warning {{TRUE}}
+ for (i = 10; 0 <= i; --i) {}
+ clang_analyzer_eval(i == -1); // expected-warning {{TRUE}}
+ char *m = (char*)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void infinite_for_loop() {
+ int i;
+ for (i = 0; i < 1; i += 0) {}
+ char *m = (char*)malloc(12);
+} // no-warning
+
+void infinite_incr_for_loop() {
+ int i;
+ for (i = 1; i > 0; ++i) {}
+ char *m = (char*)malloc(12);
+} // no-warning
+
+void infinite_decr_for_loop() {
+ int i;
+ for (i = 0; i < 1; --i) {}
+ char *m = (char*)malloc(12);
+} // no-warning
+
+void infinite_while_loop() {
+ int i = 0;
+ while (i < 10) {
+ ++i;
+ --i;
+ }
+ char *m = (char*)malloc(12);
+} // no-warning
+
+int g_global;
+
+void unknown_after_loop(int s_arg) {
+ g_global = 0;
+ s_arg = 1;
+ int s_local = 2;
+
+ 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}}
+}
+
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-constant-bound-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-constant-bound-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,181 @@
+//===--- 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 constant bound loops.
+/// A loop may be widened to approximate the exit state(s), without analysing
+/// every iteration.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
+
+using namespace clang;
+using namespace ento;
+using llvm::APSInt;
+
+/// Return the loops condition Stmt or NULL if it 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();
+ }
+}
+
+/// If an expresion is a variable reference or a cast of one, return the
+/// variable decl, else return null
+static const VarDecl *getCastedVariable(const Expr *Ex) {
+ if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
+ return getCastedVariable(CE->getSubExpr());
+ }
+ if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) {
+ return dyn_cast<VarDecl>(DR->getDecl());
+ }
+ return NULL;
+}
+
+typedef Optional<BinaryOperator::Opcode> OptionalOpcode;
+
+/// Given a condition of the form (i != EdgeVal) where EdgeVal is constant,
+/// return the Opcode "<" if the current value of i is less than EdgeVal
+/// or ">" if the current value is greater.
+static OptionalOpcode convertNE(SVal CurSV, APSInt EdgeVal) {
+ // Get the current value of the loop variable
+ APSInt CurVal;
+ if (auto NLI = CurSV.getAs<nonloc::ConcreteInt>()) {
+ CurVal = NLI->getValue();
+ }
+ else if (auto LI = CurSV.getAs<loc::ConcreteInt>()) {
+ CurVal = LI->getValue();
+ }
+ else {
+ return OptionalOpcode();
+ }
+
+ // Check signedness and ensure matching bit widths
+ assert(CurVal.isSigned() == EdgeVal.isSigned() &&
+ "Signedness missmatch");
+ if (CurVal.getBitWidth() > EdgeVal.getBitWidth()) {
+ EdgeVal.extend(CurVal.getBitWidth());
+ }
+ else if (CurVal.getBitWidth() < EdgeVal.getBitWidth()) {
+ CurVal.extend(EdgeVal.getBitWidth());
+ }
+
+ // Compare with the edge value
+ assert(CurVal != EdgeVal && "Condition is already false");
+ if (CurVal < EdgeVal) {
+ return BO_LT;
+ }
+ return BO_GT;
+}
+
+namespace clang {
+namespace ento {
+ProgramStateRef getLastIterationState(const Stmt *Loop,
+ ProgramStateRef PrevState,
+ const LocationContext *LCtx,
+ unsigned BlockCount,
+ SValBuilder &svalBuilder,
+ ASTContext &Context) {
+ const Expr *Cond = getLoopCondition(Loop);
+ if (const BinaryOperator *BOCond = dyn_cast_or_null<BinaryOperator>(Cond)) {
+ // Look for conditions with a single variable on one side and a constant
+ // expression on the other
+ BinaryOperator::Opcode opCode = BOCond->getOpcode();
+ const VarDecl *LoopVariable;
+ const Expr *LoopVarExpr;
+ APSInt EdgeVal;
+
+ bool Success = false;
+ if ((LoopVariable = getCastedVariable(BOCond->getLHS())) != NULL) {
+ LoopVarExpr = BOCond->getLHS();
+ Success = BOCond->getRHS()->EvaluateAsInt(EdgeVal, Context);
+ }
+ else if ((LoopVariable = getCastedVariable(BOCond->getRHS())) != NULL) {
+ LoopVarExpr = BOCond->getRHS();
+ Success = BOCond->getLHS()->EvaluateAsInt(EdgeVal, Context);
+ if (Success) {
+ // change the opcode so the following code can treat the
+ // condition as if the varaible is always on the LHS
+ switch (opCode) {
+ default: break;
+ case BO_LT: opCode = BO_GT; break;
+ case BO_GT: opCode = BO_LT; break;
+ case BO_LE: opCode = BO_GE; break;
+ case BO_GE: opCode = BO_LE; break;
+ }
+ }
+ }
+ if (!Success) return NULL;
+
+ // Try to convert NE to LT or GT
+ if (opCode == BO_NE) {
+ SVal CurSV = PrevState->getSVal(LoopVarExpr, LCtx);
+ OptionalOpcode Converted = convertNE(CurSV, EdgeVal);
+ if (Converted) {
+ opCode = *Converted;
+ }
+ else {
+ return NULL;
+ }
+ }
+
+ // Set the value to the approximate last value of the loop condition
+ // and check the Opcode is supported
+ switch (opCode) {
+ default:
+ return NULL; // Unsupported Opcode
+ case BO_LT:
+ --EdgeVal;
+ break;
+ case BO_GT:
+ ++EdgeVal;
+ break;
+ case BO_LE:
+ case BO_GE:
+ break;
+ }
+
+ // 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
+ const StackFrameContext *STC = LCtx->getCurrentStackFrame();
+ MemRegionManager &MRMgr = svalBuilder.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);
+ }
+ ProgramStateRef State;
+ State = PrevState->invalidateRegions(Regions, Cond, BlockCount, LCtx,
+ false, nullptr, nullptr, &ITraits);
+
+ // Set the approximate value of the loop variable in the last itteration
+ Loc LVLoc = State->getLValue(LoopVariable, LCtx);
+ nonloc::ConcreteInt EndSV = svalBuilder.makeIntVal(EdgeVal);
+ return State->bindLoc(LVLoc, EndSV);
+
+ } // Cond is a BinaryOperator
+ return NULL;
+}
+
+} // 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"
@@ -1608,6 +1609,28 @@
ProgramStateRef StTrue, StFalse;
std::tie(StTrue, StFalse) = PrevState->assume(V);
+ // Try to get approximate last iteration for constant bound loops
+ if (AMgr.options.shouldWidenConstantBoundLoops() &&
+ builder.isFeasible(true) && StTrue &&
+ builder.isFeasible(false) && !StFalse &&
+ BldCtx.blockCount() == AMgr.options.maxBlockVisitOnPath - 1) {
+
+ ProgramStateRef StLast;
+ StLast = getLastIterationState(Term, PrevState,
+ PredI->getLocationContext(),
+ BldCtx.blockCount(), svalBuilder,
+ getContext());
+ if (StLast) {
+ // Generate a new node for the true branch (which must exist)
+ StLast = StLast->assume(V, true);
+ assert(StLast && "presumed last itteration is not possible");
+ builder.generateNode(StLast, true, PredI);
+ // Don't process the normal branches
+ currBldrCtx = nullptr;
+ return;
+ }
+ }
+
// Process the true branch.
if (builder.isFeasible(true)) {
if (StTrue)
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::shouldWidenConstantBoundLoops() {
+ return getBooleanOption("widen-constant-bound-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,36 @@
+//===--- 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 constant bound loops. A loop may be widened to approximate the
+/// exit state(s), without analysing every iteration.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPWIDENING_H
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+
+namespace clang {
+namespace ento {
+
+/// Approximate the state of the last iteration of a constant bound loop.
+/// Returns NULL in cases where no approximation could be made.
+ProgramStateRef getLastIterationState(const Stmt *Loop,
+ ProgramStateRef PrevState,
+ const LocationContext *LCtx,
+ unsigned BlockCount,
+ SValBuilder &svalBuilder,
+ ASTContext &Context);
+
+} // end namespace ento
+} // end namespace clang
+
+#endif
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 shouldWidenConstantBoundLoops
+ bool WidenConstantBoundLoops;
+
/// 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 constant bound loops.
+ ///
+ /// This is controlled by the 'widen-constant-bound-loops' config option.
+ bool shouldWidenConstantBoundLoops();
+
public:
AnalyzerOptions() :
AnalysisStoreOpt(RegionStoreModel),
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
