rtrieu created this revision.
This is a proposed warning to be added to -Wfor-loop-analysis, which is part of
-Wall. This warning will catch instances where the condition will be false on
the first iteration and the loop body will never be run. The warning will be
emitted when:
1. The for-loop initializes or sets the value of a single variable to a
constant value
2. The condition is a simple comparison between the variable and another
constant value
3. If the initial value of the variable substituted into the comparison would
cause the comparison to be false
In order to make step 3 work, the constant value from step 1 may need to be
casted to a different type. The casts can be extracted from the comparison
operand. This allows the warning to work with both integer and floating point
types, as well as mixing types.
Two exceptions to this warning.
1. Parentheses around the condition will silence this warning. This is
suggested in a note.
2. If the variable is used as an array index in the body, and the condition is
less than a value the same as the array size.
Example:
https://reviews.llvm.org/D48498
This warning would have caught the issue that lebedev.ri brought up about the
loop not running.
https://reviews.llvm.org/D71503
Files:
clang/include/clang/AST/Expr.h
clang/include/clang/Basic/DiagnosticSemaKinds.td
clang/lib/AST/ExprConstant.cpp
clang/lib/Sema/SemaStmt.cpp
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<ArrayFinder> {
+ // Tracking boolean
+ bool FoundArray;
+ // Decl used as array index
+ const VarDecl *VD;
+ // Target size for array
+ llvm::APInt Size;
+
+ public:
+ typedef ConstEvaluatedExprVisitor<ArrayFinder> 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<DeclRefExpr>(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<BinaryOperator>(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<DeclStmt>(First)) {
+ // A loop variable being declared.
+ if (!DS->isSingleDecl())
+ return;
+ D = dyn_cast<VarDecl>(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<Expr>(First)) {
+ // A variable from outside the loop is being assigned a value.
+ const BinaryOperator *BO = dyn_cast<BinaryOperator>(E->IgnoreParens());
+ if (!BO || BO->getOpcode() != BO_Assign)
+ return;
+ const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(BO->getLHS());
+ if (!DRE || !DRE->getDecl())
+ return;
+ D = dyn_cast<VarDecl>(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<DeclRefExpr>(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/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<CastExpr>(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<DeclRefExpr>(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/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<ForLoopAnalysis>, 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<ForLoopAnalysis>, 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/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.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
