Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -158,6 +158,11 @@ bool Assumption) override; protected: + struct ScalingFactor { + llvm::APSInt Val; + bool Reciprocal; + }; + /// Assume a constraint between a symbolic expression and a concrete integer. virtual ProgramStateRef assumeSymRel(ProgramStateRef State, SymbolRef Sym, BinaryOperator::Opcode op, @@ -172,10 +177,12 @@ virtual ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) = 0; virtual ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) = 0; virtual ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, @@ -207,6 +214,7 @@ //===------------------------------------------------------------------===// private: static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment); + static void computeScale(SymbolRef &Sym, ScalingFactor &Scale); }; } // end GR namespace Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -271,10 +271,12 @@ ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &V, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) override; ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym, @@ -324,6 +326,8 @@ const llvm::APSInt &Int, const llvm::APSInt &Adjustment); + bool rescale(llvm::APSInt &Int, const ScalingFactor &Scale, + const llvm::APSInt &Index); }; } // end anonymous namespace @@ -538,6 +542,39 @@ return nullptr; } +bool RangeConstraintManager::rescale(llvm::APSInt &Int, + const ScalingFactor &Scale, + const llvm::APSInt &Index) { + if (Scale.Val == 1) + return true; + + APSIntType ScaleType(Scale.Val); + APSIntType BigType(2 * ScaleType.getBitWidth(), ScaleType.isUnsigned()); + + if (Scale.Reciprocal) { + // Check whether the scaled value can show up + if(ScaleType.testInRange(BigType.convert(Int) * BigType.convert(Scale.Val), + true) != APSIntType::RTR_Within) + return false; + + Int = Int * Scale.Val; + return true; + } else { + llvm::APSInt Range = BigType.convert(ScaleType.getMaxValue()) - + BigType.convert(ScaleType.getMinValue()) + + BigType.getValue(1); + llvm::APSInt PeriodInt = Range / BigType.convert(Scale.Val); + llvm::APSInt PeriodFrac = Range % BigType.convert(Scale.Val); + llvm::APSInt Quotient = BigType.convert(Int) / BigType.convert(Scale.Val); + llvm::APSInt Remainder = BigType.convert(Int) % BigType.convert(Scale.Val); + llvm::APSInt Frac = Remainder + BigType.convert(Index) * PeriodFrac; + Int = ScaleType.convert(Quotient + BigType.convert(Index) * PeriodInt + + Frac / BigType.convert(Scale.Val)); + + return (Frac % BigType.convert(Scale.Val)).isNullValue(); + } +} + //===------------------------------------------------------------------------=== // assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ @@ -553,35 +590,80 @@ ProgramStateRef RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return St; - llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment; - llvm::APSInt Upper = Lower; - --Lower; - ++Upper; - - // [Int-Adjustment+1, Int-Adjustment-1] + // [(Int-Adjustment)/Scale+1, (Int-Adjustment)/Scale-1] // Notice that the lower bound is greater than the upper bound. - RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower); + llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; + + RangeSet New = getRange(St, Sym); + for (llvm::APSInt I = AdjustmentType.getZeroValue(); + I < (Scale.Reciprocal ? AdjustmentType.getValue(1) : Scale.Val); ++I) { + + llvm::APSInt ScInt = AdjInt; + if (!rescale(ScInt, Scale, I)) + continue; + + llvm::APSInt Lower = ScInt; + llvm::APSInt Upper = ScInt; + Lower--; + Upper++; + + if (Scale.Reciprocal) { + if (!AdjustmentType.isUnsigned() && ScInt <= 0) + Lower -= Scale.Val - AdjustmentType.getValue(1); + if (ScInt >= 0) + Upper += Scale.Val - AdjustmentType.getValue(1); + } + + New = New.Intersect(getBasicVals(), F, Upper, Lower); + + if (New.isEmpty()) + return nullptr; + } + return New.isEmpty() ? nullptr : St->set(Sym, New); } ProgramStateRef RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, + const ScalingFactor &Scale, const llvm::APSInt &Adjustment) { // Before we do any real work, see if the value can even show up. APSIntType AdjustmentType(Adjustment); if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within) return nullptr; - // [Int-Adjustment, Int-Adjustment] + // [(Int-Adjustment)/Scale, (Int-Adjustment)/Scale] llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment; - RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt); + + RangeSet New = F.getEmptySet(); + for (llvm::APSInt I = AdjustmentType.getZeroValue(); + I < (Scale.Reciprocal ? AdjustmentType.getValue(1) : Scale.Val); ++I) { + + llvm::APSInt ScInt = AdjInt; + if (!rescale(ScInt, Scale, I)) + continue; + + llvm::APSInt Lower = ScInt; + llvm::APSInt Upper = ScInt; + + if (Scale.Reciprocal) { + if (!AdjustmentType.isUnsigned() && ScInt <= 0) + Lower -= Scale.Val - AdjustmentType.getValue(1); + if (ScInt >= 0) + Upper += Scale.Val - AdjustmentType.getValue(1); + } + + New = New.addRange(F, getRange(St, Sym).Intersect(getBasicVals(), F, Lower, + Upper)); + } return New.isEmpty() ? nullptr : St->set(Sym, New); } Index: clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp @@ -110,10 +110,11 @@ // Reverse the operation and add directly to state. const llvm::APSInt &Zero = BVF.getValue(0, T); + const ScalingFactor One = {BVF.getValue(1, T), false}; if (Assumption) - return assumeSymNE(State, Sym, Zero, Zero); + return assumeSymNE(State, Sym, Zero, One, Zero); else - return assumeSymEQ(State, Sym, Zero, Zero); + return assumeSymEQ(State, Sym, Zero, One, Zero); } ProgramStateRef RangedConstraintManager::assumeSymRel(ProgramStateRef State, @@ -138,8 +139,10 @@ BasicValueFactory &BVF = getBasicVals(); APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType()); - // We only handle simple comparisons of the form "$sym == constant" - // or "($sym+constant1) == constant2". + // We only handle simple comparisons of the form "$sym == constant", + // "$sym*constant0 == constant2", "$sym+constant1 == constant2" and + // "($sym*constant0)+constant1 == constant2". + // The adjustment is "constant1" in the above expression. It's used to // "slide" the solution range around for modular arithmetic. For example, // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which @@ -148,24 +151,35 @@ llvm::APSInt Adjustment = WraparoundType.getZeroValue(); computeAdjustment(Sym, Adjustment); + // The scale is "constant0" in the above expression. It's used to + // "rescale" the solution range. It's up to the subclasses of + // SimpleConstraintManager to handle the scaling. + + ScalingFactor Scale = {WraparoundType.getValue(1), false}; + // FIXME: For now scaling only works for == and != + if (Op == BO_EQ || Op == BO_NE) + computeScale(Sym, Scale); + // Convert the right-hand side integer as necessary. APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int)); llvm::APSInt ConvertedInt = ComparisonType.convert(Int); // Prefer unsigned comparisons. if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && - ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) + ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) { + Scale.Val.setIsSigned(false); Adjustment.setIsSigned(false); + } switch (Op) { default: llvm_unreachable("invalid operation not caught by assertion above"); case BO_EQ: - return assumeSymEQ(State, Sym, ConvertedInt, Adjustment); + return assumeSymEQ(State, Sym, ConvertedInt, Scale, Adjustment); case BO_NE: - return assumeSymNE(State, Sym, ConvertedInt, Adjustment); + return assumeSymNE(State, Sym, ConvertedInt, Scale, Adjustment); case BO_GT: return assumeSymGT(State, Sym, ConvertedInt, Adjustment); @@ -181,6 +195,30 @@ } // end switch } +void RangedConstraintManager::computeScale(SymbolRef &Sym, + ScalingFactor &Scale) { + // Is it a "($sym*constant1)" expression? + if (const SymIntExpr *SE = dyn_cast(Sym)) { + BinaryOperator::Opcode Op = SE->getOpcode(); + if (Op == BO_Mul || Op == BO_Div) { + Sym = SE->getLHS(); + + // FIXME: We do not yet support multiplication/division by negative + if (SE->getRHS() < 0) + return; + + // We cannot handle too big multipliers + if (Op == BO_Mul && SE->getRHS() > 255) + return; + + Scale.Val = APSIntType(Scale.Val).convert(SE->getRHS()); + + // Don't forget to reciprocate the scale if it's being divided. + Scale.Reciprocal = (Op == BO_Div); + } + } +} + void RangedConstraintManager::computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment) { // Is it a "($sym+constant1)" expression? Index: clang/test/Analysis/multiplicative-folding.c =================================================================== --- /dev/null +++ clang/test/Analysis/multiplicative-folding.c @@ -0,0 +1,689 @@ +// RUN: %clang_analyze_cc1 --std=c11 -analyzer-checker=core,debug.ExprInspection -verify %s + +void clang_analyzer_eval(int); +void clang_analyzer_warnIfReached(void); + +#define UINT_MAX (~0U) +#define INT_MAX (int)(UINT_MAX & (UINT_MAX >> 1)) +#define INT_MIN (-INT_MAX - 1) + +#define ULONG_LONG_MAX (~0UL) +#define LONG_LONG_MAX (long long)(ULONG_LONG_MAX & (ULONG_LONG_MAX >> 1)) +#define LONG_LONG_MIN (-LONG_LONG_MAX - 1) + +extern void __assert_fail (__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__ ((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail (#expr, __FILE__, __LINE__, __func__)) + +typedef int int32_t; +typedef unsigned int uint32_t; +typedef long long int64_t; +typedef unsigned long long uint64_t; + +void signed_multiplication_eq(int32_t n) { + if (n * 2 == 3) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n * 2 == 4) { + const int32_t C1 = 0x80000002, C2 = 2; + + assert(C1 * 2 == 4); + assert(C2 * 2 == 4); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n * 3 == 4) { + const int32_t C1 = 0xaaaaaaac; + + assert(C1 * 3 == 4); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n * 4 == -5) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n * 4 == -8) { + const int32_t C1 = 0xbffffffe, C2 = 0xfffffffe, + C3 = 0x3ffffffe, C4 = 0x7ffffffe; + + assert(C1 * 4 == -8); + assert(C2 * 4 == -8); + assert(C3 * 4 == -8); + assert(C4 * 4 == -8); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C3 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C3); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C3 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C4 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C4); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C4 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n * 6 == -7) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n * 6 == -2) { + const int32_t C1 = 0xd5555555, C2 = 0x55555555; + + assert(C1 * 6 == -2); + assert(C2 * 6 == -2); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } +} + +void signed_multiplication_eq64(int64_t n) { + if (n * 2 == 4) { + const int64_t C1 = 0x8000000000000002, C2 = 2; + + assert(C1 * 2 == 4); + assert(C2 * 2 == 4); + + clang_analyzer_eval(n == LONG_LONG_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == LONG_LONG_MAX); //expected-warning{{FALSE}} + + } +} + +void signed_division_eq(int32_t n) { + if (n / 2 == 0) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n < -1); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= -1); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= 1); //expected-warning{{TRUE}} + clang_analyzer_eval(n > 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 2 == 3) { + const int32_t C = 6; + + assert(C / 2 == 3); + assert((C + 1) / 2 == 3); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= C); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= C + 1); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C + 2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 3 == -5) { + const int32_t C = -15; + + assert(C / 3 == -5); + assert((C - 2) / 3 == -5); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 3); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= C - 2); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= C); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 2 == INT_MAX / 2 + 1) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n / 3 == INT_MIN / 3 - 1) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n / 4 == INT_MAX) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n / 5 == INT_MIN) { + clang_analyzer_warnIfReached(); // no-warning + + } +} + +void unsigned_multiplication_eq(uint32_t n) { + if (n * 2 == 3) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n * 2 == 4) { + const uint32_t C1 = 2, C2 = 0x80000002; + + assert(C1 * 2 == 4); + assert(C2 * 2 == 4); + + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + + } else if (n * 3 == 4) { + const uint32_t C1 = 0xaaaaaaac; + + assert(C1 * 3 == 4); + + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + + } +} + +void unsigned_division_eq(uint32_t n) { + if (n / 2 == 0) { + clang_analyzer_eval(n <= 1); //expected-warning{{TRUE}} + clang_analyzer_eval(n > 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + + } else if (n / 2 == 3) { + const uint32_t C = 6; + + assert(C / 2 == 3); + assert((C + 1) / 2 == 3); + + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= C); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= C + 1); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C + 2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + + } else if (n / 2 == UINT_MAX / 2 + 1) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n / 3 == UINT_MAX) { + clang_analyzer_warnIfReached(); // no-warning + + } +} + +void signed_multiplication_ne(int32_t n) { + if (n * 2 != 3) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 3); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 2 != 4) { + const int32_t C1 = 0x80000002, C2 = 2; + + assert(C1 * 2 == 4); + assert(C2 * 2 == 4); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 3 != 4) { + const int32_t C1 = 0xaaaaaaac; + + assert(C1 * 3 == 4); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 4 != -5) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -5); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 4 != -8) { + const int32_t C1 = 0xbffffffe, C2 = 0xfffffffe, + C3 = 0x3ffffffe, C4 = 0x7ffffffe; + + assert(C1 * 4 == -8); + assert(C2 * 4 == -8); + assert(C3 * 4 == -8); + assert(C4 * 4 == -8); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C3 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C3); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C3 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C4 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C4); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C4 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 6 != -7) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 6 != -2) { + const int32_t C1 = 0xd5555555, C2 = 0x55555555; + + assert(C1 * 6 == -2); + assert(C2 * 6 == -2); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + } + } + } + } + } + } + } +} + +void signed_division_ne(int32_t n) { + if (n / 2 != 0) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == -1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 2 != 3) { + const int32_t C = 6; + + assert(C / 2 == 3); + assert((C + 1) / 2 == 3); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C + 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 3 != -5) { + const int32_t C = -15; + + assert(C / 3 == -5); + assert((C - 2) / 3 == -5); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C - 3); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C - 2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 2 != INT_MAX / 2 + 1) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX / 2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 3 != INT_MIN / 3 - 1) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MIN / 3 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 4 != INT_MAX) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 5 != INT_MIN) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + } + } + } + } + } + } + } +} + +void unsigned_multiplication_ne(uint32_t n) { + if (n * 2 != 3) { + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == 3); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 2 != 4) { + const uint32_t C1 = 2, C2 = 0x80000002; + + assert(C1 * 2 == 4); + assert(C2 * 2 == 4); + + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n * 3 != 4) { + const uint32_t C1 = 0xaaaaaaac; + + assert(C1 * 3 == 4); + + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + } + } + } +} + +void unsigned_division_ne(uint32_t n) { + if (n / 2 != 0) { + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 2 != 3) { + const uint32_t C = 6; + + assert(C / 2 == 3); + assert((C + 1) / 2 == 3); + + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C + 2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 2 != UINT_MAX / 2 + 1) { + clang_analyzer_eval(n == UINT_MAX / 2 + 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + if (n / 4 != UINT_MAX) { + clang_analyzer_eval(n == UINT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + } + } + } + } +} + +void additive(int32_t n) { + if (n * 2 + 1 == 4) { + clang_analyzer_warnIfReached(); // no-warning + + } else if (n * 4 - 1 == 15) { + const int32_t C1 = 0x80000004, C2 = 0xc0000004, C3 = 4, C4 = 0x40000004; + + assert(C1 * 4 - 1 == 15); + assert(C2 * 4 - 1 == 15); + assert(C3 * 4 - 1 == 15); + assert(C4 * 4 - 1 == 15); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C2); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C2 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C3 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C3); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C3 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C4 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C4); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == C4 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 6 + 3 == 7) { + const int32_t C = 24; + + assert(C / 6 + 3 == 7); + assert((C + 5) / 6 + 3 == 7); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= C); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= C + 5); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C + 6); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 5 - 2 == 4) { + const int32_t C = 30; + + assert(C / 5 - 2 == 4); + assert((C + 4) / 5 - 2 == 4); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n >= C); //expected-warning{{TRUE}} + clang_analyzer_eval(n <= C + 4); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C + 5); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n * 3 - INT_MIN == 7) { + const int32_t C1 = 0x2aaaaaad; + + assert(C1 * 3 - INT_MIN == 7); + + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1 - 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == C1); //expected-warning{{TRUE}} + clang_analyzer_eval(n == C1 + 1); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + + } else if (n / 2 + 1 == INT_MAX / 2 + 1) { + clang_analyzer_eval(n == INT_MIN); //expected-warning{{FALSE}} + clang_analyzer_eval(n == 0); //expected-warning{{FALSE}} + clang_analyzer_eval(n == INT_MAX - 1); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + clang_analyzer_eval(n == INT_MAX); //expected-warning{{FALSE}} + //expected-warning@-1{{TRUE}} + + } +} + +void mixed_signedness(int32_t n, uint32_t m) { + if (n * 2U == 4) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (n * 3 == 9U) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (n * 5U == 25U) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 2U == 4) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 3 == 9U) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 5 == 2) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } +} + +void mixed_size(int32_t n, int64_t m) { + if (n * 2L == 4) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (n * 3 == 9L) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (n * 5L == 25L) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 2L == 4) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 3 == 9L) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } else if (m * 5 == 2) { + clang_analyzer_warnIfReached(); //expected-warning{{REACHABLE}} + } +}