Index: clang/include/clang/AST/Expr.h =================================================================== --- clang/include/clang/AST/Expr.h +++ clang/include/clang/AST/Expr.h @@ -906,6 +906,12 @@ return skipRValueSubobjectAdjustments(CommaLHSs, Adjustments); } + // When the current Expr is a series of of casts on D, attempt to evaluate + // the Expr as if InitValue was substituted in for D and output resulting + // value to Result. + bool SubstituteValueWithCasts(ASTContext &Context, const APValue InitValue, + const VarDecl *D, APValue &Result) const; + /// Checks that the two Expr's will refer to the same value as a comparison /// operand. The caller must ensure that the values referenced by the Expr's /// are not modified between E1 and E2 or the result my be invalid. Index: clang/include/clang/Basic/DiagnosticSemaKinds.td =================================================================== --- clang/include/clang/Basic/DiagnosticSemaKinds.td +++ clang/include/clang/Basic/DiagnosticSemaKinds.td @@ -27,6 +27,13 @@ "and in the loop body">, InGroup, DefaultIgnore; def note_loop_iteration_here : Note<"%select{decremented|incremented}0 here">; +def warn_loop_never_run : Warning< + "variable %0 is set to value %1 on loop initialization, " + "but comparing %1 to %2 in the loop condition is false and " + "the loop body will never run">, + InGroup, DefaultIgnore; +def note_loop_condition_silence : Note< + "place parentheses around the condition to silence this warning">; def warn_duplicate_enum_values : Warning< "element %0 has been implicitly assigned %1 which another element has " Index: clang/lib/AST/ExprConstant.cpp =================================================================== --- clang/lib/AST/ExprConstant.cpp +++ clang/lib/AST/ExprConstant.cpp @@ -2351,9 +2351,10 @@ Result = APSInt(DestWidth, !DestSigned); bool ignored; - if (Value.convertToInteger(Result, llvm::APFloat::rmTowardZero, &ignored) - & APFloat::opInvalidOp) - return HandleOverflow(Info, E, Value, DestType); + if (Value.convertToInteger(Result, llvm::APFloat::rmTowardZero, &ignored) & + APFloat::opInvalidOp) + if (E) + return HandleOverflow(Info, E, Value, DestType); return true; } @@ -14489,3 +14490,89 @@ EvalInfo Info(Ctx, Status, EvalInfo::EM_ConstantFold); return tryEvaluateBuiltinObjectSize(this, Type, Info, Result); } + +// Recursively apply casts from E to InitValue and return resulting value. +static bool AdjustCastValue(EvalInfo &Info, const Expr *E, + const APValue InitValue, const VarDecl *D, + APValue &Result) { + const auto *Cast = dyn_cast(E->IgnoreParens()); + if (!Cast) + return false; + switch (Cast->getCastKind()) { + default: + return false; + case CK_LValueToRValue: + // Base case, just return InitValue. + if (const auto *DRE = dyn_cast(Cast->getSubExpr())) { + if (DRE->getDecl() == D) { + Result = InitValue; + return true; + } + } + return false; + case CK_NoOp: + return AdjustCastValue(Info, Cast->getSubExpr(), InitValue, D, Result); + case CK_IntegralCast: + case CK_IntegralToBoolean: + case CK_IntegralToFloating: + case CK_FloatingToIntegral: + case CK_FloatingToBoolean: + case CK_FloatingCast: + break; + } + + // Casts need to be applied in reverse order they are encountered, so + // process the sub-expression first. + const auto* SubE = Cast->getSubExpr(); + if (!AdjustCastValue(Info, SubE, InitValue, D, Result)) + return false; + + const QualType SourceType = SubE->getType(); + const QualType DestType = E->getType(); + + switch (Cast->getCastKind()) { + default: + llvm_unreachable("Unhandled cast kind"); + case CK_IntegralCast: { + APSInt Init = Result.getInt(); + Result.setInt( + HandleIntToIntCast(Info, nullptr, DestType, SourceType, Init)); + return true; + } + case CK_IntegralToFloating: { + APValue Init(APFloat(0.f)); + Init.swap(Result); + return HandleIntToFloatCast(Info, nullptr, SourceType, Init.getInt(), + DestType, Result.getFloat()); + } + case CK_FloatingToIntegral: { + APValue Init((APSInt())); + Init.swap(Result); + return HandleFloatToIntCast(Info, nullptr, SourceType, Init.getFloat(), + DestType, Result.getInt()); + } + case CK_IntegralToBoolean: + case CK_FloatingToBoolean: { + bool BoolResult; + if (!HandleConversionToBool(Result, BoolResult)) + return false; + APValue Bool(APSInt(1, true)); + Bool.getInt() = BoolResult; + Result = Bool; + + return true; + } + case CK_FloatingCast: + return HandleFloatToFloatCast(Info, nullptr, SourceType, DestType, + Result.getFloat()); + } +} + +bool Expr::SubstituteValueWithCasts(ASTContext &Context, + const APValue InitValue, const VarDecl *D, + APValue &Result) const { + EvalStatus Status; + EvalInfo Info(Context, Status, EvalInfo::EM_IgnoreSideEffects); + return AdjustCastValue(Info, this, InitValue, D, Result); +} + Index: clang/lib/Sema/SemaStmt.cpp =================================================================== --- clang/lib/Sema/SemaStmt.cpp +++ clang/lib/Sema/SemaStmt.cpp @@ -19,6 +19,7 @@ #include "clang/AST/CXXInheritance.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/EvaluatedExprVisitor.h" +#include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/RecursiveASTVisitor.h" @@ -1739,6 +1740,258 @@ << LoopIncrement; } + // Look for any array access of the form array[x] where 'x' is a given Decl + // and array is constant array with given size. + class ArrayFinder : public ConstEvaluatedExprVisitor { + // Tracking boolean + bool FoundArray; + // Decl used as array index + const VarDecl *VD; + // Target size for array + llvm::APInt Size; + + public: + typedef ConstEvaluatedExprVisitor Inherited; + ArrayFinder(const ASTContext &Context) : Inherited(Context) { } + + bool CheckForArrays(const Stmt *Body, llvm::APInt TargetArraySize, + const VarDecl *D) { + FoundArray = false; + Size = TargetArraySize; + VD = D; + Visit(Body); + return FoundArray; + } + + void VisitArraySubscriptExpr(const ArraySubscriptExpr *E) { + if (CheckArrayType(E->getBase()) && CheckIndex(E->getIdx())) { + FoundArray = true; + } + Inherited::VisitArraySubscriptExpr(E); + } + + private: + // Helper function for checking array access. + bool CheckArrayType(const Expr *E) { + QualType ArrayTy = E->IgnoreImpCasts()->getType(); + if (!ArrayTy->isConstantArrayType()) + return false; + const ConstantArrayType *CAT = Context.getAsConstantArrayType(ArrayTy); + if (!CAT) + return false; + if (!llvm::APInt::isSameValue(CAT->getSize(), Size)) + return false; + return true; + } + + // Helper function for checking array access. + bool CheckIndex(const Expr *E) { + const DeclRefExpr *DRE = dyn_cast(E->IgnoreImpCasts()); + return DRE && DRE->getDecl() == VD; + } + + }; + + // Emit a warning when the condition of a for-loop is false on the first + // iteration, making the loop body never executed. Conditions in parenthesis + // will silence the warning. Loop variables used as array accesses are also + // skipped. + void CheckFirstIterationCondition(Sema &S, const Stmt *First, + const Expr *Second, const Stmt *Body) { + if (!First || !Second || Second->isTypeDependent() || + Second->isValueDependent()) + return; + if (S.inTemplateInstantiation()) + return; + if (Second->getExprLoc().isMacroID()) + return; + + if (S.Diags.isIgnored(diag::warn_loop_never_run, Second->getBeginLoc())) + return; + + // Only work on loop conditions that are comparisons. + const BinaryOperator *CompareBO = dyn_cast(Second); + if (!CompareBO || !CompareBO->isComparisonOp()) + return; + + // Examine the loop initilization and extract the single Decl used and its + // initial value. + const VarDecl *D = nullptr; + APValue InitValue; + if (const DeclStmt *DS = dyn_cast(First)) { + // A loop variable being declared. + if (!DS->isSingleDecl()) + return; + D = dyn_cast(DS->getSingleDecl()); + if (!D || !D->getInit()) + return; + Expr::EvalResult Result; + if (!D->getInit()->EvaluateAsRValue(Result, S.Context)) + return; + InitValue = Result.Val; + } else if (const Expr *E = dyn_cast(First)) { + // A variable from outside the loop is being assigned a value. + const BinaryOperator *BO = dyn_cast(E->IgnoreParens()); + if (!BO || BO->getOpcode() != BO_Assign) + return; + const DeclRefExpr *DRE = dyn_cast(BO->getLHS()); + if (!DRE || !DRE->getDecl()) + return; + D = dyn_cast(DRE->getDecl()); + if (!D) + return; + Expr::EvalResult Result; + if (!BO->getRHS()->EvaluateAsRValue(Result, S.Context)) + return; + InitValue = Result.Val; + } else { + // Skip any other cases in the initialization. + return; + } + + auto isVariable = [](const Expr *E, const Decl *D) { + E = E->IgnoreParenCasts(); + const DeclRefExpr *DRE = dyn_cast(E); + if (!DRE) + return false; + return DRE->getDecl() == D; + }; + + // Check that the variable from the initilization is one of the + // comparison operands. + const bool LHSisVariable = isVariable(CompareBO->getLHS(), D); + const bool RHSisVariable = isVariable(CompareBO->getRHS(), D); + if (!LHSisVariable && !RHSisVariable) + return; + if (LHSisVariable && RHSisVariable) + return; + + // Normalize to Variable Opc Constant. + const auto Opc = + LHSisVariable + ? CompareBO->getOpcode() + : BinaryOperator::reverseComparisonOp(CompareBO->getOpcode()); + + const Expr *Variable = + LHSisVariable ? CompareBO->getLHS() : CompareBO->getRHS(); + const Expr *Constant = + LHSisVariable ? CompareBO->getRHS() : CompareBO->getLHS(); + + // Convert the initial value of the variable from the variable type to + // the type used in the comparision. For instance, signed/unsigned + // conversions or float/int conversions. + APValue ConvertedValue; + if (!Variable->SubstituteValueWithCasts(S.Context, InitValue, D, + ConvertedValue)) + return; + + // Evaluate the constant operand of the compare expression. + Expr::EvalResult Result; + if (!Constant->EvaluateAsRValue(Result, S.Context)) + return; + APValue CompareValue = Result.Val; + + // Perform the first iteration comparison. + if (CompareValue.isFloat()) { + auto FloatCompareResult = + ConvertedValue.getFloat().compare(CompareValue.getFloat()); + if (FloatCompareResult == llvm::APFloat::cmpUnordered) + return; + switch (Opc) { + default: + llvm_unreachable("Unexpected operator kind"); + case BO_LT: + if (FloatCompareResult == llvm::APFloat::cmpLessThan) + return; + break; + case BO_GT: + if (FloatCompareResult == llvm::APFloat::cmpGreaterThan) + return; + break; + case BO_LE: + if (FloatCompareResult == llvm::APFloat::cmpLessThan || + FloatCompareResult == llvm::APFloat::cmpEqual) + return; + break; + case BO_GE: + if (FloatCompareResult == llvm::APFloat::cmpGreaterThan || + FloatCompareResult == llvm::APFloat::cmpEqual) + return; + break; + case BO_EQ: + if (FloatCompareResult == llvm::APFloat::cmpEqual) + return; + break; + case BO_NE: + if (FloatCompareResult == llvm::APFloat::cmpLessThan || + FloatCompareResult == llvm::APFloat::cmpGreaterThan) + return; + break; + } + } else if (CompareValue.isInt()) { + switch (Opc) { + default: + llvm_unreachable("Unexpected operator kind"); + case BO_LT: + if (ConvertedValue.getInt() < CompareValue.getInt()) + return; + break; + case BO_GT: + if (ConvertedValue.getInt() > CompareValue.getInt()) + return; + break; + case BO_LE: + if (ConvertedValue.getInt() <= CompareValue.getInt()) + return; + break; + case BO_GE: + if (ConvertedValue.getInt() >= CompareValue.getInt()) + return; + break; + case BO_EQ: + if (ConvertedValue.getInt() == CompareValue.getInt()) + return; + break; + case BO_NE: + if (ConvertedValue.getInt() != CompareValue.getInt()) + return; + break; + } + } else { + // Constant is neither an int of a float. + return; + } + + // Exclude loops where: + // The loop variable is used as an index for array access + // The comparison operator is less than + // The constant comparison operand is the same as the array size + if (Body && CompareValue.isInt() && Opc == BO_LT) { + llvm::APSInt UpperRange = CompareValue.getInt(); + if (UpperRange.isNonNegative() && UpperRange.getMinSignedBits() <= 64) { + if (ArrayFinder(S.Context).CheckForArrays(Body, UpperRange, D)) { + return; + } + } + } + + auto PartialDiag = + S.PDiag(diag::warn_loop_never_run) + << D << InitValue.getAsString(S.Context, D->getType()) + << CompareValue.getAsString(S.Context, Constant->getType()) + << Second->getSourceRange(); + S.DiagRuntimeBehavior(Second->getExprLoc(), Second, PartialDiag); + + SourceLocation Open = Second->getBeginLoc(); + SourceLocation Close = + S.getLocForEndOfToken(Second->getSourceRange().getEnd()); + auto PartialDiagNote = S.PDiag(diag::note_loop_condition_silence) + << Second->getSourceRange() + << FixItHint::CreateInsertion(Open, "(") + << FixItHint::CreateInsertion(Close, ")"); + S.DiagRuntimeBehavior(Second->getExprLoc(), Second, PartialDiagNote); + } + } // end namespace @@ -1791,6 +2044,7 @@ CheckForLoopConditionalStatement(*this, Second.get().second, third.get(), Body); CheckForRedundantIteration(*this, third.get(), Body); + CheckFirstIterationCondition(*this, First, Second.get().second, Body); if (Second.get().second && !Diags.isIgnored(diag::warn_comma_operator, Index: clang/test/SemaCXX/warn-loop-analysis-first-condition.cpp =================================================================== --- /dev/null +++ clang/test/SemaCXX/warn-loop-analysis-first-condition.cpp @@ -0,0 +1,202 @@ +// RUN: %clang_cc1 %s -Wfor-loop-analysis -verify +// RUN: %clang_cc1 %s -Wall -verify + +#define OneHundred 100 + +void test() { + // Loop variable + for (int i = OneHundred; i < 50; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 100 on loop initialization, but comparing 100 to 50 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = OneHundred; i > 50; --i) {} + + // Outside variable + int j; + for (j = OneHundred; j < 50; ++j) {} + // expected-warning@-1{{variable 'j' is set to value 100 on loop initialization, but comparing 100 to 50 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (j = OneHundred; j > 50; --j) {} + + // int->float conversion + for (int i = OneHundred; i < 5e1; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 100 on loop initialization, but comparing 100 to 5.000000e+01 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = OneHundred; i > 5e1; --i) {} + + // const values + const int kStart = 0; + const int kInterval = 10; + for (int i = kStart; i < kStart; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 0 on loop initialization, but comparing 0 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = kStart; i < kStart + kInterval; ++i) {} + + // Reversed comparison operator + for (int i = 100; i <= 1; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 100 on loop initialization, but comparing 100 to 1 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = 100; i >= 1; --i) {} + + // Range endpoints mistakes + const int kMin = 0; + const int kMax = 8; + for (int i = kMin; i < kMin; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 0 on loop initialization, but comparing 0 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = kMax; i < kMin; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 8 on loop initialization, but comparing 8 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = kMin; i < kMax; ++i) {} + + for (int i = 16; i < 16; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 16 on loop initialization, but comparing 16 to 16 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = 8; i < 16; ++i) {} + + for (int i = 1; i <= (1 >> 5); ++i) {} + // expected-warning@-1{{variable 'i' is set to value 1 on loop initialization, but comparing 1 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = 1; i <= (1 << 5); ++i) {} + + // Complex comparion operand + const int TwoK = 1024 * 2; + for (int i = 2048; i < TwoK; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 2048 on loop initialization, but comparing 2048 to 2048 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int i = 1024; i < TwoK; ++i) {} + + // Signedness mistake + for (unsigned i = -5; i < 5; ++i) {} + // expected-warning@-1{{variable 'i' is set to value 4294967291 on loop initialization, but comparing 4294967291 to 5 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (signed i = -5; i < 5; ++i) {} + + for (int i = 0xffffffff; i > 10; i -= 10) {} + // expected-warning@-1{{variable 'i' is set to value -1 on loop initialization, but comparing -1 to 10 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (unsigned int i = 0xffffffff; i > 10; i -= 10) {} + + // Floating point + for (double x = 0; x > 10; x += .5) {} + // expected-warning@-1{{variable 'x' is set to value 0.000000e+00 on loop initialization, but comparing 0.000000e+00 to 1.000000e+01 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (double x = 0; x < 10; x += .5) {} + + // Typos + for (int x = 0; x < 0000; ++x) {}; + // expected-warning@-1{{variable 'x' is set to value 0 on loop initialization, but comparing 0 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int x = 0; x < 10000; ++x) {}; + + for (char c = '0'; c <= 9; ++c) {} + // expected-warning@-1{{variable 'c' is set to value 48 on loop initialization, but comparing 48 to 9 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (char c = '0'; c <= '9'; ++c) {} + + int array[10]; + for (int x = 5; x < 1; ++x) { array[x] = x; } + // expected-warning@-1{{variable 'x' is set to value 5 on loop initialization, but comparing 5 to 1 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + for (int x = 5; x < 10; ++x) { array[x] = x; } +} + +void testConversions() { + // No conversion + for (int x = 0; x > 5; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0 on loop initialization, but comparing 0 to 5 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Int conversion + for (short x = 0; x > 5; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0 on loop initialization, but comparing 0 to 5 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Float conversion + for (float x = 0; x > 5.0; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0.000000e+00 on loop initialization, but comparing 0.000000e+00 to 5.000000e+00 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Float to Int conversion + for (double x = 0; static_cast(x) > 5; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0.000000e+00 on loop initialization, but comparing 0.000000e+00 to 5 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Int to Float conversion + for (int x = 0; x > 5.0; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0 on loop initialization, but comparing 0 to 5.000000e+00 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Bool to Int conversion + for (bool x = false; x > 0; x = !x) {} + // expected-warning@-1{{variable 'x' is set to value false on loop initialization, but comparing false to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Bool to Float conversion + for (bool x = false; x > 0.0; x = !x) {} + // expected-warning@-1{{variable 'x' is set to value false on loop initialization, but comparing false to 0.000000e+00 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Float to Bool conversion + for (float x = 0; static_cast(x) > 0; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0.000000e+00 on loop initialization, but comparing 0.000000e+00 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} + + // Int to Bool conversion + for (int x = 0; static_cast(x) > 0; ++x) {} + // expected-warning@-1{{variable 'x' is set to value 0 on loop initialization, but comparing 0 to 0 in the loop condition is false and the loop body will never run}} + // expected-note@-2{{place parentheses around the condition to silence this warning}} +} + +#define size1(X) (sizeof(X) / sizeof(X[0])) +#define size2(X) (sizeof(X) / sizeof(X[0])) / 1 +#define size3(X) sizeof(array_helper(X)) + +using size_t = decltype(sizeof(int)); +template +auto array_helper(const T (&X)[N]) -> char (&)[N]; + +const int MIN = 10; +const int MAX = 5; + +void no_warning () { + // Parentheses to silence warning. + for (int x = 0; (x > 10); ++x) {} + + int array[] = {}; + // Processing empty array. + for (int x = 0; x < size1(array); ++x) { + array[x] = x; + } + for (int x = 0; x < size2(array); ++x) { + array[x] = x; + } + for (int x = 0; x < sizeof(array); ++x) { + array[x] = x; + } + for (int x = 0; x < sizeof(array)/sizeof(*array); ++x) { + array[x] = x; + } + + int array1[] = {5}; + // Skip first array element. + for (int x = 1; x < size1(array1); ++x) { + array1[x] = array[x - 1]; + } + for (int x = 1; x < size2(array1); ++x) { + array1[x] = array[x - 1]; + } + for (int x = 1; x < size3(array1); ++x) { + array1[x] = array[x - 1]; + } + for (int x = 1; x < sizeof(array1); ++x) { + array1[x] = array[x - 1]; + } + for (int x = 1; x < sizeof(array1)/sizeof(*array); ++x) { + array1[x] = array[x - 1]; + } + + // Code flow never reaches the loop. + if (MIN < MAX) { + for (int x = MIN; x < MAX; ++x) {} + } +}