Some review issues were fixed.
http://reviews.llvm.org/D5102
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
lib/StaticAnalyzer/Core/CoreEngine.cpp
lib/StaticAnalyzer/Core/ExprEngine.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
lib/StaticAnalyzer/Core/SimpleConstraintManager.h
test/Analysis/switch-case.c
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
@@ -99,6 +99,32 @@
return ProgramStatePair(StTrue, StFalse);
}
+ virtual ProgramStateRef assumeBound(ProgramStateRef State, NonLoc Value,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ bool InBound) = 0;
+
+ virtual ProgramStatePair assumeBoundDual(ProgramStateRef State, NonLoc Value,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To) {
+ ProgramStateRef StInBound = assumeBound(State, Value, From, To, true);
+
+ // If StTrue is infeasible, asserting the falseness of Cond is unnecessary
+ // because the existing constraints already establish this.
+ if (!StInBound)
+ return ProgramStatePair((ProgramStateRef)nullptr, State);
+
+ ProgramStateRef StOutOfBounds = assumeBound(State, Value, From, To, false);
+ if (!StOutOfBounds) {
+ // We are careful to return the original state, /not/ StTrue,
+ // because we want to avoid having callers generate a new node
+ // in the ExplodedGraph.
+ return ProgramStatePair(State, (ProgramStateRef)nullptr);
+ }
+
+ return ProgramStatePair(StInBound, StOutOfBounds);
+ }
+
/// \brief If a symbol is perfectly constrained to a constant, attempt
/// to return the concrete value.
///
Index: include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -30,6 +30,7 @@
namespace ento {
class NodeBuilder;
+struct NodeBuilderContext;
//===----------------------------------------------------------------------===//
/// CoreEngine - Implements the core logic of the graph-reachability
@@ -90,7 +91,8 @@
void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
- void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
+ void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred,
+ NodeBuilderContext *Ctx);
void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
@@ -498,11 +500,13 @@
const CFGBlock *Src;
const Expr *Condition;
ExplodedNode *Pred;
+ NodeBuilderContext *Ctx;
public:
SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
- const Expr *condition, CoreEngine* eng)
- : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
+ const Expr *condition, CoreEngine* eng,
+ NodeBuilderContext *C)
+ : Eng(*eng), Src(src), Condition(condition), Pred(pred), Ctx(C) {}
class iterator {
CFGBlock::const_succ_reverse_iterator I;
@@ -544,6 +548,8 @@
const LocationContext *getLocationContext() const {
return Pred->getLocationContext();
}
+
+ const NodeBuilderContext *getBuilderContext() { return Ctx; }
};
} // end ento namespace
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -331,15 +331,15 @@
WList->setBlockCounter(Counter);
// Process the entrance of the block.
- if (Optional<CFGElement> E = L.getFirstElement()) {
- NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
+ NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
+ if (Optional<CFGElement> E = L.getFirstElement())
SubEng.processCFGElement(*E, Pred, 0, &Ctx);
- }
else
- HandleBlockExit(L.getBlock(), Pred);
+ HandleBlockExit(L.getBlock(), Pred, &Ctx);
}
-void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
+void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred,
+ NodeBuilderContext *Ctx) {
if (const Stmt *Term = B->getTerminator()) {
switch (Term->getStmtClass()) {
@@ -431,7 +431,7 @@
case Stmt::SwitchStmtClass: {
SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
- this);
+ this, Ctx);
SubEng.processSwitch(builder);
return;
@@ -479,12 +479,11 @@
assert(B);
assert(!B->empty());
+ NodeBuilderContext Ctx(*this, B, Pred);
if (StmtIdx == B->size())
- HandleBlockExit(B, Pred);
- else {
- NodeBuilderContext Ctx(*this, B, Pred);
+ HandleBlockExit(B, Pred, &Ctx);
+ else
SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
- }
}
/// generateNode - Utility method to generate nodes, hook up successors,
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -1631,8 +1631,9 @@
void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
typedef SwitchNodeBuilder::iterator iterator;
ProgramStateRef state = builder.getState();
+ const LocationContext *LCtx = builder.getLocationContext();
const Expr *CondE = builder.getCondition();
- SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
+ SVal CondV_untested = state->getSVal(CondE, LCtx);
if (CondV_untested.isUndef()) {
//ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
@@ -1642,6 +1643,11 @@
return;
}
DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
+ if (CondV.isUnknown()) {
+ CondV = state->getStateManager().getSValBuilder().conjureSymbolVal(nullptr,
+ CondE, LCtx, builder.getBuilderContext()->blockCount());
+ state = state->BindExpr(CondE, LCtx, CondV);
+ }
ProgramStateRef DefaultSt = state;
@@ -1666,47 +1672,23 @@
else
V2 = V1;
- // FIXME: Eventually we should replace the logic below with a range
- // comparison, rather than concretize the values within the range.
- // This should be easy once we have "ranges" for NonLVals.
-
- do {
- nonloc::ConcreteInt CaseVal(getBasicVals().getValue(V1));
- DefinedOrUnknownSVal Res = svalBuilder.evalEQ(DefaultSt ? DefaultSt : state,
- CondV, CaseVal);
-
- // Now "assume" that the case matches.
- if (ProgramStateRef stateNew = state->assume(Res, true)) {
- builder.generateCaseStmtNode(I, stateNew);
-
- // If CondV evaluates to a constant, then we know that this
- // is the *only* case that we can take, so stop evaluating the
- // others.
- if (CondV.getAs<nonloc::ConcreteInt>())
- return;
- }
-
- // Now "assume" that the case doesn't match. Add this state
- // to the default state (if it is feasible).
- if (DefaultSt) {
- if (ProgramStateRef stateNew = DefaultSt->assume(Res, false)) {
- defaultIsFeasible = true;
- DefaultSt = stateNew;
- }
- else {
- defaultIsFeasible = false;
- DefaultSt = nullptr;
- }
- }
-
- // Concretize the next value in the range.
- if (V1 == V2)
- break;
-
- ++V1;
- assert (V1 <= V2);
-
- } while (true);
+ ProgramStateRef StateCase;
+ assert(CondV.getAs<NonLoc>());
+ NonLoc NL = CondV.castAs<NonLoc>();
+ std::tie(StateCase, DefaultSt) = DefaultSt->getConstraintManager()
+ .assumeBoundDual(DefaultSt, NL, V1, V2);
+
+ if (StateCase)
+ builder.generateCaseStmtNode(I, StateCase);
+
+ // Now "assume" that the case doesn't match. Add this state
+ // to the default state (if it is feasible).
+ if (DefaultSt)
+ defaultIsFeasible = true;
+ else {
+ defaultIsFeasible = false;
+ break;
+ }
}
if (!defaultIsFeasible)
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -81,6 +81,15 @@
RangeSet(PrimRangeSet RS) : ranges(RS) {}
+ /// Create a new set with all ranges of this set and RS.
+ /// Possible intersections are not checked here.
+ RangeSet addRange(Factory &F, const RangeSet &RS) {
+ PrimRangeSet Ranges(RS.ranges);
+ for (auto range : ranges)
+ Ranges = F.add(Ranges, range);
+ return RangeSet(Ranges);
+ }
+
iterator begin() const { return ranges.begin(); }
iterator end() const { return ranges.end(); }
@@ -312,6 +321,16 @@
const llvm::APSInt& Int,
const llvm::APSInt& Adjustment) override;
+ ProgramStateRef assumeSymInBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) override;
+
+ ProgramStateRef assumeSymOutOfBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) override;
+
const llvm::APSInt* getSymVal(ProgramStateRef St,
SymbolRef sym) const override;
ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
@@ -566,6 +585,31 @@
return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
}
+ProgramStateRef
+RangeConstraintManager::assumeSymInBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) {
+ ProgramStateRef St = assumeSymGE(State, Sym, From, Adjustment);
+ if (St)
+ St = assumeSymLE(St, Sym, To, Adjustment);
+ return St;
+}
+
+ProgramStateRef
+RangeConstraintManager::assumeSymOutOfBound(ProgramStateRef State,
+ SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) {
+ ProgramStateRef St1 = assumeSymLT(State, Sym, From, Adjustment);
+ ProgramStateRef St2 = assumeSymGT(State, Sym, To, Adjustment);
+ RangeSet Range1 = St1 ? GetRange(St1, Sym) : F.getEmptySet();
+ RangeSet Range2 = St2 ? GetRange(St2, Sym) : F.getEmptySet();
+ RangeSet New(Range1.addRange(F, Range2));
+ return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New);
+}
+
//===------------------------------------------------------------------------===
// Pretty-printing.
//===------------------------------------------------------------------------===/
Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
===================================================================
--- lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
@@ -190,6 +190,38 @@
} // end switch
}
+ProgramStateRef SimpleConstraintManager::assumeBound(ProgramStateRef State,
+ NonLoc Value,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ bool InBound) {
+
+ if (!canReasonAbout(Value)) {
+ // Just add the constraint to the expression without trying to simplify.
+ SymbolRef Sym = Value.getAsSymExpr();
+ return assumeSymBound(State, Sym, From, To, InBound);
+ }
+
+ switch (Value.getSubKind()) {
+ default:
+ llvm_unreachable("'AssumeBound' not implemented for this NonLoc");
+
+ case nonloc::LocAsIntegerKind:
+ case nonloc::SymbolValKind: {
+ if (SymbolRef Sym = Value.getAsSymbol())
+ return assumeSymBound(State, Sym, From, To, InBound);
+ return State;
+ } // end switch
+
+ case nonloc::ConcreteIntKind: {
+ const llvm::APSInt &IntVal = Value.castAs<nonloc::ConcreteInt>().getValue();
+ bool IsInBound = IntVal >= From && IntVal <= To;
+ bool isFeasible = (IsInBound == InBound);
+ return isFeasible ? State : nullptr;
+ }
+ } // end switch
+}
+
static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment) {
// Is it a "($sym+constant1)" expression?
if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
@@ -262,6 +294,36 @@
} // end switch
}
+ProgramStateRef
+SimpleConstraintManager::assumeSymBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ bool InBound) {
+ // Get the type used for calculating wraparound.
+ BasicValueFactory &BVF = getBasicVals();
+ APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
+
+ llvm::APSInt Adjustment = WraparoundType.getZeroValue();
+ SymbolRef AdjustedSym = Sym;
+ computeAdjustment(AdjustedSym, Adjustment);
+
+ // Convert the right-hand side integer as necessary.
+ APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From));
+ llvm::APSInt ConvertedFrom = ComparisonType.convert(From);
+ llvm::APSInt ConvertedTo = ComparisonType.convert(To);
+
+ // Prefer unsigned comparisons.
+ if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
+ ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
+ Adjustment.setIsSigned(false);
+
+ if (InBound)
+ return assumeSymInBound(State, AdjustedSym, ConvertedFrom, ConvertedTo,
+ Adjustment);
+ return assumeSymOutOfBound(State, AdjustedSym, ConvertedFrom, ConvertedTo,
+ Adjustment);
+}
+
} // end of namespace ento
} // end of namespace clang
Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.h
===================================================================
--- lib/StaticAnalyzer/Core/SimpleConstraintManager.h
+++ lib/StaticAnalyzer/Core/SimpleConstraintManager.h
@@ -38,11 +38,20 @@
ProgramStateRef assume(ProgramStateRef state, NonLoc Cond, bool Assumption);
+ ProgramStateRef assumeBound(ProgramStateRef State, NonLoc Value,
+ const llvm::APSInt &From, const llvm::APSInt &To,
+ bool InBound) override;
+
ProgramStateRef assumeSymRel(ProgramStateRef state,
const SymExpr *LHS,
BinaryOperator::Opcode op,
const llvm::APSInt& Int);
+ ProgramStateRef assumeSymBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To, bool InBound);
+
+
protected:
//===------------------------------------------------------------------===//
@@ -75,6 +84,17 @@
const llvm::APSInt& V,
const llvm::APSInt& Adjustment) = 0;
+
+ virtual ProgramStateRef assumeSymInBound(ProgramStateRef State, SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) = 0;
+
+ virtual ProgramStateRef assumeSymOutOfBound(ProgramStateRef state,
+ SymbolRef Sym,
+ const llvm::APSInt &From,
+ const llvm::APSInt &To,
+ const llvm::APSInt &Adjustment) = 0;
//===------------------------------------------------------------------===//
// Internal implementation.
//===------------------------------------------------------------------===//
Index: test/Analysis/switch-case.c
===================================================================
--- /dev/null
+++ test/Analysis/switch-case.c
@@ -0,0 +1,140 @@
+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+#define INT_MIN 0x80000000
+#define INT_MAX 0x7fffffff
+
+// PR16833: Analyzer consumes memory until killed by kernel OOM killer
+// while analyzing large case ranges.
+void PR16833(unsigned op) {
+ switch (op) {
+ case 0x02 << 26 ... 0x03 << 26: // Analyzer should not hang here.
+ return;
+ }
+}
+
+void testAdjustment(int t) {
+ switch (t + 1) {
+ case 2:
+ clang_analyzer_eval(t == 1); // expected-warning{{TRUE}}
+ break;
+ case 3 ... 10:
+ clang_analyzer_eval(t > 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(t + 2 <= 11); // expected-warning{{TRUE}}
+ clang_analyzer_eval(t + 1 == 3); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(t + 1 == 10); // expected-warning{{UNKNOWN}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ }
+}
+
+void testUnknownVal(int value, int mask) {
+ // Once ConstraintManager will process '&' and this test will require some changes.
+ switch (value & mask) {
+ case 1:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ break;
+ case 3 ... 10:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ }
+}
+
+void testSwitchCond(int arg) {
+ if (arg > 10) {
+ switch (arg) {
+ case INT_MIN ... 10:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 11 ... 20:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ }
+
+ switch (arg) {
+ case INT_MIN ... 9:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 10 ... 20:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg > 10); // expected-warning{{TRUE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ }
+ } // arg > 10
+}
+
+void testDefaultUnreachable(int arg) {
+ if (arg > 10) {
+ switch (arg) {
+ case INT_MIN ... 9:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 10 ... INT_MAX:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg > 10); // expected-warning{{TRUE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // no-warning
+ }
+ }
+}
+
+void testBranchReachability(int arg) {
+ if (arg > 10 && arg < 20) {
+ switch (arg) {
+ case INT_MIN ... 4:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 5 ... 9:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 10 ... 15:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg > 10 && arg <= 15); // expected-warning{{TRUE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 17 ... 25:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg >= 17 && arg < 20); // expected-warning{{TRUE}}
+ break;
+ case 26 ... INT_MAX:
+ clang_analyzer_warnIfReached(); // no-warning
+ break;
+ case 16:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg == 16); // expected-warning{{TRUE}}
+ break;
+ }
+ }
+}
+
+void testDefaultBrachRange(int arg) {
+ switch (arg) {
+ case INT_MIN ... 9:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ break;
+ case 20 ... INT_MAX:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg >= 20); // expected-warning{{TRUE}}
+ break;
+ default:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ clang_analyzer_eval(arg == 16); // expected-warning{{FALSE}}
+ clang_analyzer_eval(arg > 9); // expected-warning{{TRUE}}
+ clang_analyzer_eval(arg <= 20); // expected-warning{{TRUE}}
+
+ case 16:
+ clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+ }
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
