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: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1666,47 +1666,24 @@ 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 stateNew; + assert(CondV.getAs()); + NonLoc NL = CondV.castAs(); + std::tie(stateNew, DefaultSt) = DefaultSt->getConstraintManager() + .assumeBoundDual(DefaultSt, NL, V1, V2); + + // Now "assume" that the case matches. + if (stateNew) + builder.generateCaseStmtNode(I, stateNew); + + // 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 (iterator I = begin(), E = end(); I != E; I++) + Ranges = F.add(Ranges, *I); + 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,30 @@ 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,39 @@ } // 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()) { + Value.dump(); + 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 b = IntVal >= From && IntVal <= To; + bool isFeasible = (b == 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 +295,34 @@ } // 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 Sym = sym; + computeAdjustment(Sym, 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, Sym, ConvertedFrom, ConvertedTo, Adjustment); + return assumeSymOutOfBound(state, Sym, ConvertedFrom, ConvertedTo, Adjustment); +} + } // end of namespace ento } // end of namespace clang Index: test/Analysis/misc-ps.c =================================================================== --- test/Analysis/misc-ps.c +++ test/Analysis/misc-ps.c @@ -191,3 +191,12 @@ clang_analyzer_eval(*ip == 42); // expected-warning{{TRUE}} clang_analyzer_eval(*(int *)&v == 42); // expected-warning{{TRUE}} } + +// 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; + } +}