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 E = L.getFirstElement()) { - NodeBuilderContext Ctx(*this, L.getBlock(), Pred); + NodeBuilderContext Ctx(*this, L.getBlock(), Pred); + if (Optional 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(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(); + 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()) - 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 NL = CondV.castAs(); + 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(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(Sym, New); +} + //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ 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: 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().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(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: 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}} + } +}