[clang-tidy] Misc redundant expression checker updated for ineffective bitwise operator expressions

[barancsuk]

Summary

Redundant Expression Checker is updated to find ineffective or redundant bitwise operator expressions.

The checker targets bitwise operator expressions with a symbolic expression and an integer literal as operands, where the expression always evaluates to the same numeric constant or leaves the symbolic expression unaltered.

Examples:

• Always evaluates to 0:

int X;
if(0 & X) return;

• Always evaluates to ~0:

int Y;
if(Y | ~0) return;

• The symbol is unmodified:

int Z;
Z &= ~0;

The checker matches bitwise OR, bitwise AND and their corresponding assignment operators.

[xazax.hun]

I really like these additions. Found some nits otherwise looks good.

clang-tidy/misc/RedundantExpressionCheck.cpp

800

Maybe this could be called like exprEvaluatesToConstant, since it might actually be evaluated to zero based on the other operand, right?

801

The parens around ~Value are redundant.

806

Maybe I would name this differently, like exprIdempotentOperation.

809

Same as above.

852

Redundant parens here as well.

866

The ConstExprText is not quoted in the error message.

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

806

Never mind, Idempotent is not the correct term here.

[Eugene.Zelenko]

It'll be good idea to mention improvement in Release Notes.

[barancsuk]

Address review comments

[barancsuk]

clang-tidy/misc/RedundantExpressionCheck.cpp

800

The 'not zero' in the function name means a 'bitwise not zero' or 'negated zero' (~0), which has a bit representation containing only ones.

The function itself checks whether this value is used in a bitwise OR expression as an operand, because in this case the expression always evaluates to ~0 independently from the other operand's value.

I changed the function name to exprEvaluatesToNegatedZero.

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

866

I would eliminate this local variable, it does not convey additional information. Also, it does not start with a capital letter.

876

Same as above.

[barancsuk]

Address latest review comments

[xazax.hun]

clang-tidy/misc/RedundantExpressionCheck.cpp

142

I would eliminate this new line.

143

Please initialize this variable.

147

Maybe you could ignore the casts here instead of bellow.

150

This will dereference a null pointer (after you initialized this variable above) if the condition above fails.

482

Maybe this is an artifact from a missing rebase. I like the original code snippet here better.

795

The outermost parens are redundant.

799

The outermost parens are redundant.

803

Maybe you could rewrite this function as:

return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
      ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);

846

You could move this declaration close to its use.

docs/clang-tidy/checks/misc-redundant-expression.rst

28

This is confusing. Maybe it would be better to have two separate example here.

[barancsuk]

Address latest review comments

clang-tidy/misc/RedundantExpressionCheck.cpp

150

The entire function ignoreCastsAndCopyConstructorCalls is unnecessary, since when the test cases with operators that take arguments by value were removed. My bad! I eliminated the function.

[xazax.hun]

LGTM! But wait one more reviewer to be sure :)

[aaron.ballman]

clang-tidy/misc/RedundantExpressionCheck.cpp

516–517

Spurious formatting change?

677–678

No real need for these locals, is there?

Also, having "ineff-bitwise" along with "ineffective-bitwise" is a bit odd. Can you pick a more clearly distinct name?

[barancsuk]

Address review comments

[aaron.ballman]

LGTM!

[aaron.ballman]

This patch needs to be rebased off trunk before it can be applied cleanly.

[xazax.hun]

In D39285#932013, @aaron.ballman wrote:

This patch needs to be rebased off trunk before it can be applied cleanly.

https://reviews.llvm.org/D39243 is set as a dependency, so I suspect this can be applied cleanly once https://reviews.llvm.org/D39243 landed.

[aaron.ballman]

In D39285#932032, @xazax.hun wrote:

In D39285#932013, @aaron.ballman wrote:

This patch needs to be rebased off trunk before it can be applied cleanly.

https://reviews.llvm.org/D39243 is set as a dependency, so I suspect this can be applied cleanly once https://reviews.llvm.org/D39243 landed.

I have to admit that this stack of interdependent changes makes it *very* hard to effectively review what's going on.

[barancsuk]

:( My initial intention was to simplify the review process by splitting the change-set into small patches, but it seems that this idea fell flat...

[xazax.hun]

In D39285#932815, @barancsuk wrote:

:( My initial intention was to simplify the review process by splitting the change-set into small patches, but it seems that this idea fell flat...

I could not apply the patch after commiting the dependent revision. Could you rebase this on top of tree clang tidy?

[alexfh]

clang-tidy/misc/RedundantExpressionCheck.cpp

871

This can be a StringRef to avoid unnecessary copies. Same above.

875

I'd use clang diagnostic formatting facilities here to avoid unnecessary temporary strings:

diag(Loc, "expression ... '%0'") << ExprText;

Same above.

[barancsuk]

Address review comments

[xazax.hun]

There was two accepts and the comments found by Alex were resolved, so I went ahead committing this. In case there are further comments, we can address them separately.

clang-tidy/misc/RedundantExpressionCheck.cpp

 }
 
 // For a given expression 'x', returns whether the ranges covered by the
 // relational operators are equivalent (i.e.  x <= 4 is equivalent to x < 5).
 static bool areEquivalentRanges(BinaryOperatorKind OpcodeLHS,
                                 const APSInt &ValueLHS,
                                 BinaryOperatorKind OpcodeRHS,
                                 const APSInt &ValueRHS) {
   assert(APSInt::compareValues(ValueLHS, ValueRHS) <= 0 &&
          "Values must be ordered");
   // Handle the case where constants are the same: x <= 4  <==>  x <= 4.
   if (APSInt::compareValues(ValueLHS, ValueRHS) == 0)
     return OpcodeLHS == OpcodeRHS;
 
   // Handle the case where constants are off by one: x <= 4  <==>  x < 5.
   APSInt ValueLHS_plus1;
   return ((OpcodeLHS == BO_LE && OpcodeRHS == BO_LT) ||
           (OpcodeLHS == BO_GT && OpcodeRHS == BO_GE)) &&
          incrementWithoutOverflow(ValueLHS, ValueLHS_plus1) &&
          APSInt::compareValues(ValueLHS_plus1, ValueRHS) == 0;
 }
 
 // For a given expression 'x', returns whether the ranges covered by the
 // relational operators are fully disjoint (i.e. x < 4  and  x > 7).
 static bool areExclusiveRanges(BinaryOperatorKind OpcodeLHS,
canOverloadedOperatorArgsBeModified(const FunctionDecl *OperatorDecl,
   unsigned ParamCount = OperatorDecl->getNumParams();
   assert(ParamCount >= 1 &&
          "The function does not have enough parameters to check.");
 
   // Overloaded operators declared inside a class have only one param.
   // These functions must be declared const in order to not be able to modify
   // the instance of the class they are called through.
   if (ParamCount == 1 &&
       !OperatorDecl->getType()->getAs<FunctionType>()->isConst())
     return true;
 
   if (isNonConstReferenceType(OperatorDecl->getParamDecl(0)->getType()))
     return true;
 
   return checkSecondParam && ParamCount == 2 &&
          isNonConstReferenceType(OperatorDecl->getParamDecl(1)->getType());
 }
if (const auto *Bin = Result.Nodes.getNodeAs<BinaryOperator>(Id)) {
     if (!retrieveIntegerConstantExpr(Result, Id, Value, ConstExpr))
       return false;
   } else if (const auto *Cast = Result.Nodes.getNodeAs<CastExpr>(CastId)) {
     // Operand received with implicit comparator (cast).
     Opcode = BO_NE;
     OperandExpr = Cast;
     Value = APSInt(32, false);
   } else if (const auto *OverloadedOperatorExpr =
                  Result.Nodes.getNodeAs<CXXOperatorCallExpr>(OverloadId)) {
     const auto *OverloadedFunctionDecl = dyn_cast_or_null<FunctionDecl>(OverloadedOperatorExpr->getCalleeDecl());
     if (!OverloadedFunctionDecl)
       return false;
 
-    if (canOverloadedOperatorArgsBeModified(OverloadedFunctionDecl, false))
-      return false;
-
     if (!OverloadedOperatorExpr->getArg(1)->isIntegerConstantExpr(
             Value, *Result.Context))
       return false;
 
     Symbol = OverloadedOperatorExpr->getArg(0);
     OperandExpr = OverloadedOperatorExpr;
     Opcode = BinaryOperator::getOverloadedOpcode(OverloadedOperatorExpr->getOperator());
 
Finder->addMatcher(
               hasOverloadedOperatorName("&&"), hasOverloadedOperatorName("||"),
               hasOverloadedOperatorName("=")),
           parametersAreEquivalent(),
           // Filter noisy false positives.
           unless(isMacro()), unless(isInTemplateInstantiation()))
           .bind("call"),
       this);
 
+  // Match ineffective bitwise operator expressions like: x & 0 or x |= ~0.
+  Finder->addMatcher(
+      binaryOperator(anyOf(hasOperatorName("|"), hasOperatorName("&"),
+                           hasOperatorName("|="), hasOperatorName("&=")),
+                     hasEitherOperand(matchIntegerConstantExpr("ineffective-bitwise")),
+                     hasEitherOperand(matchSymbolicExpr("ineffective-bitwise")))
+          .bind("ineffective-bitwise"),
+      this);
+
   // Match common expressions and apply more checks to find redundant
   // sub-expressions.
   //   a) Expr <op> K1 == K2
   //   b) Expr <op> K1 == Expr
   //   c) Expr <op> K1 == Expr <op> K2
   // see: 'checkArithmeticExpr' and 'checkBitwiseExpr'
   const auto BinOpCstLeft = matchBinOpIntegerConstantExpr("lhs");
   const auto BinOpCstRight = matchBinOpIntegerConstantExpr("rhs");
if (LhsOpcode == BO_Add && RhsOpcode == BO_Add) {
                   APSInt::compareValues(LhsValue, RhsValue) == 0)) {
         diag(ComparisonOperator->getOperatorLoc(),
              "logical expression is always false");
       }
     }
   }
 }
 
+static bool exprEvaluatesToZero(BinaryOperatorKind Opcode, APSInt Value) {
+  return (Opcode == BO_And || Opcode == BO_AndAssign) && Value == 0;
+}
+
+static bool exprEvaluatesToBitwiseNegatedZero(BinaryOperatorKind Opcode,
+                                              APSInt Value) {
+  return (Opcode == BO_Or || Opcode == BO_OrAssign) && ~Value == 0;
+}
+
+static bool exprEvaluatesToSymbolic(BinaryOperatorKind Opcode, APSInt Value) {
+  return ((Opcode == BO_Or || Opcode == BO_OrAssign) && Value == 0) ||
+         ((Opcode == BO_And || Opcode == BO_AndAssign) && ~Value == 0);
+}
+
 void RedundantExpressionCheck::checkBitwiseExpr(
     const MatchFinder::MatchResult &Result) {
   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
           "binop-const-compare-to-const")) {
     BinaryOperatorKind Opcode = ComparisonOperator->getOpcode();
 
     APSInt LhsValue, RhsValue;
     const Expr *LhsSymbol = nullptr;
     BinaryOperatorKind LhsOpcode;
     if (!retrieveBinOpIntegerConstantExpr(Result, "lhs", LhsOpcode, LhsSymbol,
if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
 
     // Check expression: x | k1 == k2  (i.e. x | 0xFF == 0xF00)
     if (LhsOpcode == BO_Or && (LhsConstant | RhsConstant) != RhsConstant) {
       if (Opcode == BO_EQ)
         diag(Loc, "logical expression is always false");
       else if (Opcode == BO_NE)
         diag(Loc, "logical expression is always true");
     }
+  } else if (const auto *IneffectiveOperator =
+                 Result.Nodes.getNodeAs<BinaryOperator>(
+                     "ineffective-bitwise")) {
+    APSInt Value;
+    const Expr *Sym = nullptr, *ConstExpr = nullptr;
+
+    if (!retrieveSymbolicExpr(Result, "ineffective-bitwise", Sym) ||
+        !retrieveIntegerConstantExpr(Result, "ineffective-bitwise", Value, ConstExpr))
+      return;
+
+    if((Value != 0 && ~Value != 0) || Sym->getExprLoc().isMacroID())
+        return;
+
+    SourceLocation Loc = IneffectiveOperator->getOperatorLoc();
+
+    BinaryOperatorKind Opcode = IneffectiveOperator->getOpcode();
+    if (exprEvaluatesToZero(Opcode, Value)) {
+      diag(Loc, "expression always evaluates to 0");
+    } else if (exprEvaluatesToBitwiseNegatedZero(Opcode, Value)) {
+      SourceRange ConstExprRange(ConstExpr->getLocStart(),
+                                 ConstExpr->getLocEnd());
+      std::string ConstExprText = Lexer::getSourceText(
+          CharSourceRange::getTokenRange(ConstExprRange), *Result.SourceManager,
+          Result.Context->getLangOpts());
+
+      diag(Loc,
+           "expression always evaluates to '" + ConstExprText + "'");
+    } else if (exprEvaluatesToSymbolic(Opcode, Value)) {
+      SourceRange SymExprRange(Sym->getLocStart(), Sym->getLocEnd());
+
+      std::string ExprText = Lexer::getSourceText(
+          CharSourceRange::getTokenRange(SymExprRange), *Result.SourceManager,
+          Result.Context->getLangOpts());
+
+      diag(Loc, "expression always evaluates to '" + ExprText + "'");
+    }
   }
 }
 
 void RedundantExpressionCheck::checkRelationalExpr(
     const MatchFinder::MatchResult &Result) {
   if (const auto *ComparisonOperator = Result.Nodes.getNodeAs<BinaryOperator>(
           "comparisons-of-symbol-and-const")) {
     // Matched expressions are: (x <op> k1) <REL> (x <op> k2).

docs/clang-tidy/checks/misc-redundant-expression.rst

 .. title:: clang-tidy - misc-redundant-expression
 
 misc-redundant-expression
 =========================
 
 Detect redundant expressions which are typically errors due to copy-paste.
 
 Depending on the operator expressions may be
 
 - redundant,
 
 - always ``true``,
 
 - always ``false``,
 
-- always a constant (zero or one).
+- always a constant (zero or one),
+
+- ineffective, the operation does not change the expression.
 
 Examples:
 
 .. code-block:: c++
 
   ((x+1) | (x+1))             // (x+1) is redundant
   (p->x == p->x)              // always true
   (p->x < p->x)               // always false
   (speed - speed + 1 == 12)   // speed - speed is always zero
+  x |= 0                      // operation does not change the value of x
+  x &= ~0                     // operation does not change the value of x

test/clang-tidy/misc-redundant-expression.cpp

int TestArithmetic(int X, int Y) {
   if (X + 1 == Y) return 1;
   if (X + 1 == Y + 1) return 1;
   if (X + 1 == Y + 2) return 1;
 
   return 0;
 }
 
 int TestBitwise(int X, int Y) {
+  if(0 & X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to 0
+  if(~0 | X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: expression always evaluates to '~0'
+
+  if(X & 0) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to 0
+  if(X | ~0) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to '~0'
+  if(X | 0xffffffff) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to '0xffffffff'
+
+  if(~0 & X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: expression always evaluates to 'X'
+  if(0 | X) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to 'X'
+
+  if(X & ~0) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to 'X'
+  if(X | 0) return 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:8: warning: expression always evaluates to 'X'
+
+  X &= ~0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to 'X'
+  X |= 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to 'X'
+
+  X &= 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to 0
+  X |= ~0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to '~0'
+  X |= 0xffffffff;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to '0xffffffff'
+  X |= -1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: expression always evaluates to '-1'
+
   if ((X & 0xFF) == 0xF00) return 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: logical expression is always false
   if ((X & 0xFF) != 0xF00) return 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: logical expression is always true
   if ((X | 0xFF) == 0xF00) return 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: logical expression is always false
   if ((X | 0xFF) != 0xF00) return 1;
   // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: logical expression is always true