[clang][Analysis] Handle && and || against variable and its negation as tautology

[hazohelet]

Summary

This patch introduces a new warning flag -Wtautological-negation-compare grouped in -Wtautological-compare that warns on the use of && or || operators against a variable and its negation.
e.g. x || !x and !x && x
This also makes the -Winfinite-recursion diagnose more cases.

Fixes https://github.com/llvm/llvm-project/issues/56035

[tbaeder]

Added some more reviewers based on lines owned in CFG.cpp.

[tbaeder]

clang/lib/Analysis/CFG.cpp

1106–1107

[hazohelet]

Address review comment

• NFC stylistic change

[hazohelet]

Ping

[hazohelet]

Ping

[thakis]

Seems like a nice idea to me, thanks!

Do you have any numbers on how often this fires in practice, and what the true positive rate is? (Build some large-ish open source project with this, and see what it finds.)
Did you verify that this has negligible compile time impact for building a large-ish project?

With that, looks good.

clang/lib/Analysis/CFG.cpp

1089

Do you want to IgnoreParens() on the ! subexpr too?

[hazohelet]

Do you have any numbers on how often this fires in practice, and what the true positive rate is? (Build some large-ish open source project with this, and see what it finds.)

I built rui314/mold and saw no new warnings emitted from this change. I searched several repositories to find only one instance in CBLAS code that this change could be relevant.
https://github.com/Reference-LAPACK/lapack/blob/c57e36a43bb1c25c7ec15a3c84f4800942a5ca43/CBLAS/src/cblas_xerbla.c#L69-L70
I'm not sure what exactly they are doing there, but the comment (Force link of our F77 error handler) suggests it is intentional, so it could be counted as false positive. But, I don't see any reason for not doing if (0) instead.

Did you verify that this has negligible compile time impact for building a large-ish project?

About the compile time impact, I don't expect this patch to have a noticeable change. The changes in this patch does not contain heavy computations like AST traversals. At least the build times of rui314/mold by clang ToT and patched clang did not have noticeable difference.

clang/lib/Analysis/CFG.cpp

1089

I wanted to, but it looks like most codes containing parentheses in negation subexpression are macros, so now I don't think we need it.
https://sourcegraph.com/search?q=context:global+/%21%5C%28%5Ba-zA-Z_%5D%2B%5C%29/+lang:C+lang:C%2B%2B&patternType=standard&case=yes&sm=1&groupBy=repo

[hazohelet]

Ping

[aaron.ballman]

Generally LGTM, just a minor suggestion on slightly rewording the diagnostics and combining them.

clang/include/clang/Basic/DiagnosticSemaKinds.td

9799–9804

Let's combine these if we can. I'm not 100% certain that %select is going to like &&||| though, so if there's an issue, separate is also fine.

[thakis]

lg with aaron's suggestion. thanks for the patch, and for your patience!

[hazohelet]

Address comments from Aaron

• Reworded diagnostic message

[hazohelet]

Thanks for the review

clang/include/clang/Basic/DiagnosticSemaKinds.td

9799–9804

%select(&&|||)0 doesn't seem to work as we want it to, so I kept it separated

clang/docs/ReleaseNotes.rst

 Improvements to Clang's diagnostics
 -----------------------------------
 - Clang constexpr evaluator now prints template arguments when displaying
   template-specialization function calls.
 - Clang contexpr evaluator now displays notes as well as an error when a constructor
   of a base class is not called in the constructor of its derived class.
 - Clang no longer emits ``-Wmissing-variable-declarations`` for variables declared
   with the ``register`` storage class.
+- Clang's ``-Wtautological-negation-compare`` flag now diagnoses logical
+  tautologies like ``x && !x`` and ``!x || x`` in expressions. This also
+  makes ``-Winfinite-recursion`` diagnose more cases.
+  (`#56035: <https://github.com/llvm/llvm-project/issues/56035>`_).
 
 Bug Fixes in This Version
 -------------------------
 - Fixed an issue where a class template specialization whose declaration is
   instantiated in one module and whose definition is instantiated in another
   module may end up with members associated with the wrong declaration of the
   class, which can result in miscompiles in some cases.
 - Fix crash on use of a variadic overloaded operator.

clang/include/clang/Analysis/CFG.h

 
 /// CFGCallback defines methods that should be called when a logical
 /// operator error is found when building the CFG.
 class CFGCallback {
 public:
   CFGCallback() = default;
   virtual ~CFGCallback() = default;
 
+  virtual void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
   virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
   virtual void compareBitwiseEquality(const BinaryOperator *B,
                                       bool isAlwaysTrue) {}
   virtual void compareBitwiseOr(const BinaryOperator *B) {}
 };
 
 /// Represents a source-level, intra-procedural CFG that represents the
 ///  control-flow of a Stmt.  The Stmt can represent an entire function body,

clang/include/clang/Basic/DiagnosticGroups.td

 def TautologicalOutOfRangeCompare : DiagGroup<"tautological-constant-out-of-range-compare">;
 def TautologicalConstantCompare : DiagGroup<"tautological-constant-compare",
                                             [TautologicalOutOfRangeCompare]>;
 def TautologicalPointerCompare : DiagGroup<"tautological-pointer-compare">;
 def TautologicalOverlapCompare : DiagGroup<"tautological-overlap-compare">;
 def TautologicalBitwiseCompare : DiagGroup<"tautological-bitwise-compare">;
 def TautologicalUndefinedCompare : DiagGroup<"tautological-undefined-compare">;
 def TautologicalObjCBoolCompare : DiagGroup<"tautological-objc-bool-compare">;
+def TautologicalNegationCompare : DiagGroup<"tautological-negation-compare">;
 def TautologicalCompare : DiagGroup<"tautological-compare",
                                     [TautologicalConstantCompare,
                                      TautologicalPointerCompare,
                                      TautologicalOverlapCompare,
                                      TautologicalBitwiseCompare,
                                      TautologicalUndefinedCompare,
-                                     TautologicalObjCBoolCompare]>;
+                                     TautologicalObjCBoolCompare,
+                                     TautologicalNegationCompare]>;
 def HeaderHygiene : DiagGroup<"header-hygiene">;
 def DuplicateDeclSpecifier : DiagGroup<"duplicate-decl-specifier">;
 def CompareDistinctPointerType : DiagGroup<"compare-distinct-pointer-types">;
 def GNUUnionCast : DiagGroup<"gnu-union-cast">;
 def GNUVariableSizedTypeNotAtEnd : DiagGroup<"gnu-variable-sized-type-not-at-end">;
 def Varargs : DiagGroup<"varargs">;
 def XorUsedAsPow : DiagGroup<"xor-used-as-pow">;
 

clang/include/clang/Basic/DiagnosticSemaKinds.td

def warn_comparison_always : Warning<
   "%select{a constant|true|false|'std::strong_ordering::equal'}1">,
   InGroup<TautologicalCompare>;
 def warn_comparison_bitwise_always : Warning<
   "bitwise comparison always evaluates to %select{false|true}0">,
   InGroup<TautologicalBitwiseCompare>, DefaultIgnore;
 def warn_comparison_bitwise_or : Warning<
   "bitwise or with non-zero value always evaluates to true">,
   InGroup<TautologicalBitwiseCompare>, DefaultIgnore;
+def warn_tautological_negation_and_compare: Warning<
+  "'&&' of a value and its negation always evaluates to false">,
+  InGroup<TautologicalNegationCompare>, DefaultIgnore;
+def warn_tautological_negation_or_compare: Warning<
+  "'||' of a value and its negation always evaluates to true">,
+  InGroup<TautologicalNegationCompare>, DefaultIgnore;
 def warn_tautological_overlap_comparison : Warning<
   "overlapping comparisons always evaluate to %select{false|true}0">,
   InGroup<TautologicalOverlapCompare>, DefaultIgnore;
 def warn_depr_array_comparison : Warning<
   "comparison between two arrays is deprecated; "
   "to compare array addresses, use unary '+' to decay operands to pointers">,
   InGroup<DeprecatedArrayCompare>;
 

clang/lib/Analysis/CFG.cpp

switch (Relation) {
         return TryResult(Value1 <= Value2);
       case BO_GT:
         return TryResult(Value1 >  Value2);
       case BO_GE:
         return TryResult(Value1 >= Value2);
     }
   }
 
-  /// Find a pair of comparison expressions with or without parentheses
+  /// There are two checks handled by this function:
+  /// 1. Find a law-of-excluded-middle or law-of-noncontradiction expression
+  /// e.g. if (x || !x), if (x && !x)
+  /// 2. Find a pair of comparison expressions with or without parentheses
   /// with a shared variable and constants and a logical operator between them
   /// that always evaluates to either true or false.
   /// e.g. if (x != 3 || x != 4)
   TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
     assert(B->isLogicalOp());
-    const BinaryOperator *LHS =
-        dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens());
-    const BinaryOperator *RHS =
-        dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens());
+    const Expr *LHSExpr = B->getLHS()->IgnoreParens();
+    const Expr *RHSExpr = B->getRHS()->IgnoreParens();
+
+    auto CheckLogicalOpWithNegatedVariable = [this, B](const Expr *E1,
+                                                       const Expr *E2) {
+      if (const auto *Negate = dyn_cast<UnaryOperator>(E1)) {
+        if (Negate->getOpcode() == UO_LNot &&
+            Expr::isSameComparisonOperand(Negate->getSubExpr(), E2)) {
+          bool AlwaysTrue = B->getOpcode() == BO_LOr;
+          if (BuildOpts.Observer)
+            BuildOpts.Observer->logicAlwaysTrue(B, AlwaysTrue);
+          return TryResult(AlwaysTrue);
+        }
+      }
+      return TryResult();
+    };
+
+    TryResult Result = CheckLogicalOpWithNegatedVariable(LHSExpr, RHSExpr);
+    if (Result.isKnown())
+        return Result;
+    Result = CheckLogicalOpWithNegatedVariable(RHSExpr, LHSExpr);
+    if (Result.isKnown())
+        return Result;
+
+    const auto *LHS = dyn_cast<BinaryOperator>(LHSExpr);
+    const auto *RHS = dyn_cast<BinaryOperator>(RHSExpr);
     if (!LHS || !RHS)
       return {};
 
     if (!LHS->isComparisonOp() || !RHS->isComparisonOp())
       return {};
 
     const Expr *DeclExpr1;
     const Expr *NumExpr1;

clang/lib/Sema/AnalysisBasedWarnings.cpp

static bool HasMacroID(const Expr *E) {
     for (const Stmt *SubStmt : E->children())
       if (const Expr *SubExpr = dyn_cast_or_null<Expr>(SubStmt))
         if (HasMacroID(SubExpr))
           return true;
 
     return false;
   }
 
+  void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) override {
+    if (HasMacroID(B))
+      return;
+
+    unsigned DiagID = isAlwaysTrue
+                          ? diag::warn_tautological_negation_or_compare
+                          : diag::warn_tautological_negation_and_compare;
+    SourceRange DiagRange = B->getSourceRange();
+    S.Diag(B->getExprLoc(), DiagID) << DiagRange;
+  }
+
   void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) override {
     if (HasMacroID(B))
       return;
 
     SourceRange DiagRange = B->getSourceRange();
     S.Diag(B->getExprLoc(), diag::warn_tautological_overlap_comparison)
         << DiagRange << isAlwaysTrue;
   }
void compareBitwiseOr(const BinaryOperator *B) override {
 
     SourceRange DiagRange = B->getSourceRange();
     S.Diag(B->getExprLoc(), diag::warn_comparison_bitwise_or) << DiagRange;
   }
 
   static bool hasActiveDiagnostics(DiagnosticsEngine &Diags,
                                    SourceLocation Loc) {
     return !Diags.isIgnored(diag::warn_tautological_overlap_comparison, Loc) ||
-           !Diags.isIgnored(diag::warn_comparison_bitwise_or, Loc);
+           !Diags.isIgnored(diag::warn_comparison_bitwise_or, Loc) ||
+           !Diags.isIgnored(diag::warn_tautological_negation_and_compare, Loc);
   }
 };
 } // anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // Check for infinite self-recursion in functions
 //===----------------------------------------------------------------------===//
 

clang/test/Analysis/temp-obj-dtors-cfg-output.cpp

 // CHECK:     Preds (1): B3
 // CHECK:     Succs (1): B0
 // CHECK:   [B3]
 // CHECK:     T: if [B5.1]
 // CHECK:     Preds (2): B4(Unreachable) B5
 // CHECK:     Succs (2): B2 B1
 // CHECK:   [B4 (NORETURN)]
 // CHECK:     1: ~NoReturn() (Temporary object destructor)
-// CHECK:     Preds (1): B5
+// CHECK:     Preds (1): B5(Unreachable)
 // CHECK:     Succs (1): B0
 // CHECK:   [B5]
 // CHECK:     1: [B8.3] || [B7.2] || [B6.7]
 // CHECK:     T: (Temp Dtor) [B6.4]
 // CHECK:     Preds (3): B6 B7 B8
-// CHECK:     Succs (2): B4 B3
+// CHECK:     Succs (2): B4(Unreachable) B3
 // CHECK:   [B6]
 // CHECK:     1: check
 // CHECK:     2: [B6.1] (ImplicitCastExpr, FunctionToPointerDecay, _Bool (*)(const NoReturn &))
 // WARNINGS:     3: NoReturn() (CXXConstructExpr, NoReturn)
 // ANALYZER:     3: NoReturn() (CXXConstructExpr, [B6.4], [B6.6], NoReturn)
 // CHECK:     4: [B6.3] (BindTemporary)
 // CHECK:     5: [B6.4] (ImplicitCastExpr, NoOp, const NoReturn)
 // CHECK:     6: [B6.5]

clang/test/Misc/warning-wall.c

 CHECK-NEXT:    -Wtautological-compare
 CHECK-NEXT:      -Wtautological-constant-compare
 CHECK-NEXT:        -Wtautological-constant-out-of-range-compare
 CHECK-NEXT:      -Wtautological-pointer-compare
 CHECK-NEXT:      -Wtautological-overlap-compare
 CHECK-NEXT:      -Wtautological-bitwise-compare
 CHECK-NEXT:      -Wtautological-undefined-compare
 CHECK-NEXT:      -Wtautological-objc-bool-compare
+CHECK-NEXT:      -Wtautological-negation-compare
 CHECK-NEXT:    -Wtrigraphs
 CHECK-NEXT:    -Wuninitialized
 CHECK-NEXT:      -Wsometimes-uninitialized
 CHECK-NEXT:      -Wstatic-self-init
 CHECK-NEXT:      -Wuninitialized-const-reference
 CHECK-NEXT:    -Wunknown-pragmas
 CHECK-NEXT:    -Wunused
 CHECK-NEXT:      -Wunused-argument

clang/test/SemaCXX/tautological-negation-compare.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify -Wtautological-negation-compare -Wno-constant-logical-operand %s
+// RUN: %clang_cc1 -fsyntax-only -verify -Wtautological-compare -Wno-constant-logical-operand %s
+// RUN: %clang_cc1 -fsyntax-only -verify -Wall -Wno-unused -Wno-loop-analysis -Wno-constant-logical-operand %s
+
+#define COPY(x) x
+
+void test_int(int x) {
+  if (x || !x) {} // expected-warning {{'||' of a value and its negation always evaluates to true}}
+  if (!x || x) {} // expected-warning {{'||' of a value and its negation always evaluates to true}}
+  if (x && !x) {} // expected-warning {{'&&' of a value and its negation always evaluates to false}}
+  if (!x && x) {} // expected-warning {{'&&' of a value and its negation always evaluates to false}}
+
+  // parentheses are ignored
+  if (x || (!x)) {} // expected-warning {{'||' of a value and its negation always evaluates to true}}
+  if (!(x) || x) {} // expected-warning {{'||' of a value and its negation always evaluates to true}}
+
+  // don't warn on macros
+  if (COPY(x) || !x) {}
+  if (!x || COPY(x)) {}
+  if (x && COPY(!x)) {}
+  if (COPY(!x && x)) {}
+
+  // dont' warn on literals
+  if (1 || !1) {}
+  if (!42 && 42) {}
+
+
+  // don't warn on overloads
+  struct Foo{
+    int val;
+    Foo operator!() const { return Foo{!val}; }
+    bool operator||(const Foo other) const { return val || other.val; }
+    bool operator&&(const Foo other) const { return val && other.val; }
+  };
+
+  Foo f{3};
+  if (f || !f) {}
+  if (!f || f) {}
+  if (f.val || !f.val) {} // expected-warning {{'||' of a value and its negation always evaluates to true}}
+  if (!f.val && f.val) {} // expected-warning {{'&&' of a value and its negation always evaluates to false}}
+}

clang/test/SemaCXX/warn-infinite-recursion.cpp

Q &evaluated_recursive_function(int x) {         // expected-warning{{call itself}}
   (void)typeid(evaluated_recursive_function(x)); // expected-warning {{expression with side effects will be evaluated despite being used as an operand to 'typeid'}}
   return q;
 }
 
 int unevaluated_recursive_function() {
   (void)typeid(unevaluated_recursive_function());
   return 0;
 }
+
+void func1(int i) { // expected-warning {{call itself}}
+  if (i || !i)
+    func1(i);
+}
+void func2(int i) { // expected-warning {{call itself}}
+  if (!i && i) {}
+  else
+    func2(i);
+}