Author: dcoughlin Date: Tue Sep 22 15:31:19 2015 New Revision: 248318 URL: http://llvm.org/viewvc/llvm-project?rev=248318&view=rev Log: [analyzer] Create one state for a range switch case instead of multiple.
This fixes PR16833, in which the analyzer was using large amounts of memory for switch statements with large case ranges. rdar://problem/14685772 A patch by Aleksei Sidorin! Differential Revision: http://reviews.llvm.org/D5102 Added: cfe/trunk/test/Analysis/switch-case.c Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h cfe/trunk/lib/Analysis/CFG.cpp cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.h Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h Tue Sep 22 15:31:19 2015 @@ -99,6 +99,35 @@ public: return ProgramStatePair(StTrue, StFalse); } + virtual ProgramStateRef assumeWithinInclusiveRange(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InBound) = 0; + + virtual ProgramStatePair assumeWithinInclusiveRangeDual( + ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, + const llvm::APSInt &To) { + ProgramStateRef StInRange = assumeWithinInclusiveRange(State, Value, From, + To, true); + + // If StTrue is infeasible, asserting the falseness of Cond is unnecessary + // because the existing constraints already establish this. + if (!StInRange) + return ProgramStatePair((ProgramStateRef)nullptr, State); + + ProgramStateRef StOutOfRange = assumeWithinInclusiveRange(State, Value, + From, To, false); + if (!StOutOfRange) { + // 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(StInRange, StOutOfRange); + } + /// \brief If a symbol is perfectly constrained to a constant, attempt /// to return the concrete value. /// Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h Tue Sep 22 15:31:19 2015 @@ -190,6 +190,27 @@ public: DefinedOrUnknownSVal upperBound, bool assumption, QualType IndexType = QualType()) const; + + /// Assumes that the value of \p Val is bounded with [\p From; \p To] + /// (if \p assumption is "true") or it is fully out of this range + /// (if \p assumption is "false"). + /// + /// This returns a new state with the added constraint on \p cond. + /// If no new state is feasible, NULL is returned. + ProgramStateRef assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool assumption) const; + + /// Assumes given range both "true" and "false" for \p Val, and returns both + /// corresponding states (respectively). + /// + /// This is more efficient than calling assume() twice. Note that one (but not + /// both) of the returned states may be NULL. + std::pair<ProgramStateRef, ProgramStateRef> + assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, const llvm::APSInt &From, + const llvm::APSInt &To) const; + /// \brief Check if the given SVal is constrained to zero or is a zero /// constant. @@ -636,6 +657,33 @@ ProgramState::assume(DefinedOrUnknownSVa ->assumeDual(this, Cond.castAs<DefinedSVal>()); } +inline ProgramStateRef +ProgramState::assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool Assumption) const { + if (Val.isUnknown()) + return this; + + assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); + + return getStateManager().ConstraintMgr->assumeWithinInclusiveRange( + this, Val.castAs<NonLoc>(), From, To, Assumption); +} + +inline std::pair<ProgramStateRef, ProgramStateRef> +ProgramState::assumeWithinInclusiveRange(DefinedOrUnknownSVal Val, + const llvm::APSInt &From, + const llvm::APSInt &To) const { + if (Val.isUnknown()) + return std::make_pair(this, this); + + assert(Val.getAs<NonLoc>() && "Only NonLocs are supported!"); + + return getStateManager().ConstraintMgr + ->assumeWithinInclusiveRangeDual(this, Val.castAs<NonLoc>(), From, To); +} + inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { if (Optional<Loc> L = LV.getAs<Loc>()) return bindLoc(*L, V); Modified: cfe/trunk/lib/Analysis/CFG.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/CFG.cpp?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/lib/Analysis/CFG.cpp (original) +++ cfe/trunk/lib/Analysis/CFG.cpp Tue Sep 22 15:31:19 2015 @@ -3101,11 +3101,11 @@ static bool shouldAddCase(bool &switchEx addCase = true; switchExclusivelyCovered = true; } - else if (condInt < lhsInt) { + else if (condInt > lhsInt) { if (const Expr *RHS = CS->getRHS()) { // Evaluate the RHS of the case value. const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx); - if (V2 <= condInt) { + if (V2 >= condInt) { addCase = true; switchExclusivelyCovered = true; } Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Tue Sep 22 15:31:19 2015 @@ -1784,47 +1784,24 @@ void ExprEngine::processSwitch(SwitchNod 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; + if (Optional<NonLoc> NL = CondV.getAs<NonLoc>()) + std::tie(StateCase, DefaultSt) = + DefaultSt->assumeWithinInclusiveRange(*NL, V1, V2); + else // UnknownVal + StateCase = DefaultSt; + + 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) Modified: cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp Tue Sep 22 15:31:19 2015 @@ -81,6 +81,15 @@ public: 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 (const 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,14 @@ public: const llvm::APSInt& Int, const llvm::APSInt& Adjustment) override; + ProgramStateRef assumeSymbolWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) override; + + ProgramStateRef assumeSymbolOutOfInclusiveRange( + 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; @@ -324,6 +341,20 @@ public: private: RangeSet::Factory F; + RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymLERange(const RangeSet &RS, const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); + RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment); }; } // end anonymous namespace @@ -450,122 +481,199 @@ RangeConstraintManager::assumeSymEQ(Prog return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); } -ProgramStateRef -RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, - const llvm::APSInt &Int, - const llvm::APSInt &Adjustment) { +RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St, + SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: - return nullptr; + return F.getEmptySet(); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return St; + return GetRange(St, Sym); } // Special case for Int == Min. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) - return nullptr; + return F.getEmptySet(); - llvm::APSInt Lower = Min-Adjustment; - llvm::APSInt Upper = ComparisonVal-Adjustment; + llvm::APSInt Lower = Min - Adjustment; + llvm::APSInt Upper = ComparisonVal - Adjustment; --Upper; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); - return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef -RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, +RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { + RangeSet New = getSymLTRange(St, Sym, Int, Adjustment); + return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); +} + +RangeSet +RangeConstraintManager::getSymGTRange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: - return St; + return GetRange(St, Sym); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return nullptr; + return F.getEmptySet(); } // Special case for Int == Max. This is always false. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) - return nullptr; + return F.getEmptySet(); - llvm::APSInt Lower = ComparisonVal-Adjustment; - llvm::APSInt Upper = Max-Adjustment; + llvm::APSInt Lower = ComparisonVal - Adjustment; + llvm::APSInt Upper = Max - Adjustment; ++Lower; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); - return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef -RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, +RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { + RangeSet New = getSymGTRange(St, Sym, Int, Adjustment); + return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); +} + +RangeSet +RangeConstraintManager::getSymGERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: - return St; + return GetRange(St, Sym); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return nullptr; + return F.getEmptySet(); } // Special case for Int == Min. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Min = AdjustmentType.getMinValue(); if (ComparisonVal == Min) - return St; + return GetRange(St, Sym); llvm::APSInt Max = AdjustmentType.getMaxValue(); - llvm::APSInt Lower = ComparisonVal-Adjustment; - llvm::APSInt Upper = Max-Adjustment; + llvm::APSInt Lower = ComparisonVal - Adjustment; + llvm::APSInt Upper = Max - Adjustment; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); - return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } ProgramStateRef -RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, +RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { + RangeSet New = getSymGERange(St, Sym, Int, Adjustment); + return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); +} + +RangeSet +RangeConstraintManager::getSymLERange(const RangeSet &RS, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); switch (AdjustmentType.testInRange(Int, true)) { case APSIntType::RTR_Below: - return nullptr; + return F.getEmptySet(); case APSIntType::RTR_Within: break; case APSIntType::RTR_Above: - return St; + return RS; } // Special case for Int == Max. This is always feasible. llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); llvm::APSInt Max = AdjustmentType.getMaxValue(); if (ComparisonVal == Max) - return St; + return RS; + + llvm::APSInt Min = AdjustmentType.getMinValue(); + llvm::APSInt Lower = Min - Adjustment; + llvm::APSInt Upper = ComparisonVal - Adjustment; + + return RS.Intersect(getBasicVals(), F, Lower, Upper); +} + +RangeSet +RangeConstraintManager::getSymLERange(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { + // Before we do any real work, see if the value can even show up. + APSIntType AdjustmentType(Adjustment); + switch (AdjustmentType.testInRange(Int, true)) { + case APSIntType::RTR_Below: + return F.getEmptySet(); + case APSIntType::RTR_Within: + break; + case APSIntType::RTR_Above: + return GetRange(St, Sym); + } + + // Special case for Int == Max. This is always feasible. + llvm::APSInt ComparisonVal = AdjustmentType.convert(Int); + llvm::APSInt Max = AdjustmentType.getMaxValue(); + if (ComparisonVal == Max) + return GetRange(St, Sym); llvm::APSInt Min = AdjustmentType.getMinValue(); - llvm::APSInt Lower = Min-Adjustment; - llvm::APSInt Upper = ComparisonVal-Adjustment; + llvm::APSInt Lower = Min - Adjustment; + llvm::APSInt Upper = ComparisonVal - Adjustment; - RangeSet New = GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); +} + +ProgramStateRef +RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, + const llvm::APSInt &Int, + const llvm::APSInt &Adjustment) { + RangeSet New = getSymLERange(St, Sym, Int, Adjustment); return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New); } +ProgramStateRef +RangeConstraintManager::assumeSymbolWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) { + RangeSet New = getSymGERange(State, Sym, From, Adjustment); + if (New.isEmpty()) + return nullptr; + New = getSymLERange(New, To, Adjustment); + return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); +} + +ProgramStateRef +RangeConstraintManager::assumeSymbolOutOfInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) { + RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment); + RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment); + RangeSet New(RangeLT.addRange(F, RangeGT)); + return New.isEmpty() ? nullptr : State->set<ConstraintRange>(Sym, New); +} + //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ Modified: cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp Tue Sep 22 15:31:19 2015 @@ -190,6 +190,42 @@ ProgramStateRef SimpleConstraintManager: } // end switch } +ProgramStateRef SimpleConstraintManager::assumeWithinInclusiveRange( + ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, + const llvm::APSInt &To, bool InRange) { + + assert(From.isUnsigned() == To.isUnsigned() && + From.getBitWidth() == To.getBitWidth() && + "Values should have same types!"); + + if (!canReasonAbout(Value)) { + // Just add the constraint to the expression without trying to simplify. + SymbolRef Sym = Value.getAsSymExpr(); + assert(Sym); + return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange); + } + + switch (Value.getSubKind()) { + default: + llvm_unreachable("'assumeWithinInclusiveRange' is not implemented" + "for this NonLoc"); + + case nonloc::LocAsIntegerKind: + case nonloc::SymbolValKind: { + if (SymbolRef Sym = Value.getAsSymbol()) + return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange); + return State; + } // end switch + + case nonloc::ConcreteIntKind: { + const llvm::APSInt &IntVal = Value.castAs<nonloc::ConcreteInt>().getValue(); + bool IsInRange = IntVal >= From && IntVal <= To; + bool isFeasible = (IsInRange == InRange); + 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 +298,37 @@ ProgramStateRef SimpleConstraintManager: } // end switch } +ProgramStateRef +SimpleConstraintManager::assumeSymWithinInclusiveRange(ProgramStateRef State, + SymbolRef Sym, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) { + // 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 (InRange) + return assumeSymbolWithinInclusiveRange(State, AdjustedSym, ConvertedFrom, + ConvertedTo, Adjustment); + return assumeSymbolOutOfInclusiveRange(State, AdjustedSym, ConvertedFrom, + ConvertedTo, Adjustment); +} + } // end of namespace ento } // end of namespace clang Modified: cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.h?rev=248318&r1=248317&r2=248318&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.h (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/SimpleConstraintManager.h Tue Sep 22 15:31:19 2015 @@ -38,11 +38,24 @@ public: ProgramStateRef assume(ProgramStateRef state, NonLoc Cond, bool Assumption); + ProgramStateRef assumeWithinInclusiveRange(ProgramStateRef State, + NonLoc Value, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange) override; + ProgramStateRef assumeSymRel(ProgramStateRef state, const SymExpr *LHS, BinaryOperator::Opcode op, const llvm::APSInt& Int); + ProgramStateRef assumeSymWithinInclusiveRange(ProgramStateRef State, + SymbolRef Sym, + const llvm::APSInt &From, + const llvm::APSInt &To, + bool InRange); + + protected: //===------------------------------------------------------------------===// @@ -75,6 +88,14 @@ protected: const llvm::APSInt& V, const llvm::APSInt& Adjustment) = 0; + + virtual ProgramStateRef assumeSymbolWithinInclusiveRange( + ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; + + virtual ProgramStateRef assumeSymbolOutOfInclusiveRange( + ProgramStateRef state, SymbolRef Sym, const llvm::APSInt &From, + const llvm::APSInt &To, const llvm::APSInt &Adjustment) = 0; //===------------------------------------------------------------------===// // Internal implementation. //===------------------------------------------------------------------===// Added: cfe/trunk/test/Analysis/switch-case.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/switch-case.c?rev=248318&view=auto ============================================================================== --- cfe/trunk/test/Analysis/switch-case.c (added) +++ cfe/trunk/test/Analysis/switch-case.c Tue Sep 22 15:31:19 2015 @@ -0,0 +1,220 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=core,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 > 2); // expected-warning{{UNKNOWN}} + 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 testDefaultBranchRange(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}} + } +} + +void testAllUnreachableButDefault(int arg) { + if (arg < 0) { + switch (arg) { + case 0 ... 9: + clang_analyzer_warnIfReached(); // no-warning + break; + case 20 ... INT_MAX: + clang_analyzer_warnIfReached(); // no-warning + break; + default: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + case 16: + clang_analyzer_warnIfReached(); // no-warning + } + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + } +} + +void testAllUnreachable(int arg) { + if (arg < 0) { + switch (arg) { + case 0 ... 9: + clang_analyzer_warnIfReached(); // no-warning + break; + case 20 ... INT_MAX: + clang_analyzer_warnIfReached(); // no-warning + break; + case 16: + clang_analyzer_warnIfReached(); // no-warning + } + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + } +} + +void testDifferentTypes(int arg) { + switch (arg) { + case -1U ... 400000000LL: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + default: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + } +} + +void testDifferentTypes2(unsigned long arg) { + switch (arg) { + case 1UL ... 400000000UL: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + default: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + } +} + +void testDifferentTypes3(int arg) { + switch (arg) { + case 1UL ... 400000000UL: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + default: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + } +} + +void testConstant() { + switch (3) { + case 1 ... 5: + clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}} + break; + default: + clang_analyzer_warnIfReached(); // no-warning + break; + } +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
