[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

1113–1114

[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

1096

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

1096

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

9726–9731

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

9726–9731

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

clang/docs/ReleaseNotes.rst

- Clang now correctly diagnoses when the argument to ``alignas`` or ``_Alignas``
   is an incomplete type.
   (`#55175: <https://github.com/llvm/llvm-project/issues/55175>`_, and fixes an
   incorrect mention of ``alignof`` in a diagnostic about ``alignas``).
 - Clang will now show a margin with line numbers to the left of each line
   of code it prints for diagnostics. This can be disabled using
   ``-fno-diagnostics-show-line-numbers``. At the same time, the maximum
   number of code lines it prints has been increased from 1 to 16. This
   can be controlled using ``-fcaret-diagnostics-max-lines=``.
+- 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
 -------------------------
 
 - Fix segfault while running clang-rename on a non existing file.
   (`#36471 <https://github.com/llvm/llvm-project/issues/36471>`_)
 - Fix crash when diagnosing incorrect usage of ``_Nullable`` involving alias
   templates.

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<
+  "'&&' against a variable and its negation always evaluates to false">,
+  InGroup<TautologicalNegationCompare>, DefaultIgnore;
+def warn_tautological_negation_or_compare: Warning<
+  "'||' against a variable 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 BinaryOperator *LHS = dyn_cast<BinaryOperator>(LHSExpr);
+    const BinaryOperator *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 {{'||' against a variable and its negation always evaluates to true}}
+  if (!x || x) {} // expected-warning {{'||' against a variable and its negation always evaluates to true}}
+  if (x && !x) {} // expected-warning {{'&&' against a variable and its negation always evaluates to false}}
+  if (!x && x) {} // expected-warning {{'&&' against a variable and its negation always evaluates to false}}
+
+  // parentheses are ignored
+  if (x || (!x)) {} // expected-warning {{'||' against a variable and its negation always evaluates to true}}
+  if (!(x) || x) {} // expected-warning {{'||' against a variable 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 {{'||' against a variable and its negation always evaluates to true}}
+  if (!f.val && f.val) {} // expected-warning {{'&&' against a variable 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);
+}