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 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), 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: 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: 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/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/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(LoopStmt)->getCond(); + case Stmt::WhileStmtClass: + return cast(LoopStmt)->getCond(); + case Stmt::DoStmtClass: + return cast(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(Ex)) { + return getCastedVariable(CE->getSubExpr()); + } + if (const DeclRefExpr *DR = dyn_cast(Ex)) { + return dyn_cast(DR->getDecl()); + } + return NULL; +} + +typedef Optional 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()) { + CurVal = NLI->getValue(); + } + else if (auto LI = CurSV.getAs()) { + 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(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: 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: 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/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}} +} +