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,35 @@ 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. /// 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: include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h =================================================================== --- include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -189,6 +189,27 @@ 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 + 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. @@ -649,6 +670,33 @@ ->assumeDual(this, Cond.castAs()); } +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() && "Only NonLocs are supported!"); + + return getStateManager().ConstraintMgr->assumeWithinInclusiveRange( + this, Val.castAs(), From, To, Assumption); +} + +inline std::pair +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() && "Only NonLocs are supported!"); + + return getStateManager().ConstraintMgr + ->assumeWithinInclusiveRangeDual(this, Val.castAs(), From, To); +} + inline ProgramStateRef ProgramState::bindLoc(SVal LV, SVal V) const { if (Optional L = LV.getAs()) return bindLoc(*L, V); 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->assumeWithinInclusiveRange(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,14 @@ 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 @@ 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 @@ -365,7 +396,7 @@ /// Scan all symbols referenced by the constraints. If the symbol is not alive /// as marked in LSymbols, mark it as dead in DSymbols. -ProgramStateRef +ProgramStateRef RangeConstraintManager::removeDeadBindings(ProgramStateRef state, SymbolReaper& SymReaper) { @@ -415,7 +446,7 @@ // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, // UINT_MAX, 0, 1, and 2. -ProgramStateRef +ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { @@ -435,7 +466,7 @@ return New.isEmpty() ? nullptr : St->set(Sym, New); } -ProgramStateRef +ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment) { @@ -450,122 +481,199 @@ return New.isEmpty() ? nullptr : St->set(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(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } -ProgramStateRef -RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym, +ProgramStateRef +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(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(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } -ProgramStateRef -RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym, +ProgramStateRef +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(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(Sym, New); + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); } -ProgramStateRef -RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym, +ProgramStateRef +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(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; + + return GetRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper); +} - RangeSet New = 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(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(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(Sym, New); +} + //===------------------------------------------------------------------------=== // Pretty-printing. //===------------------------------------------------------------------------===/ Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.h =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.h +++ lib/StaticAnalyzer/Core/SimpleConstraintManager.h @@ -38,11 +38,24 @@ 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 @@ 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. //===------------------------------------------------------------------===// Index: lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp =================================================================== --- lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp +++ lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp @@ -190,6 +190,40 @@ } // end switch } +ProgramStateRef SimpleConstraintManager::assumeWithinInclusiveRange( + ProgramStateRef State, NonLoc Value, const llvm::APSInt &From, + const llvm::APSInt &To, bool InRange) { + + if (!canReasonAbout(Value)) { + // Just add the constraint to the expression without trying to simplify. + SymbolRef Sym = Value.getAsSymExpr(); + return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange); + } + + assert(From.isUnsigned() == To.isUnsigned() && + "Types of bounds should match!"); + + 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().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(Sym)) { @@ -262,6 +296,37 @@ } // 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 Index: test/Analysis/switch-case.c =================================================================== --- /dev/null +++ test/Analysis/switch-case.c @@ -0,0 +1,175 @@ +// 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}} + } +} + +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}} + } +}