[COMMITTED 2/2] PR tree-optimization/111766 - Adjust operators equal and not_equal to check bitmasks against constants

[COMMITTED 2/2] PR tree-optimization/111766 - Adjust operators equal and not_equal to check bitmasks against constants

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 760 bytes --]

When we compare a range against a constant for equality or inequality, 
there is currently no attempt made to utilize the known bits.

This patch adds a method to the irange_bitmask class to ask if a 
specific value satisfies the known bit pattern.  Operators equal and 
not_equal then utilize it when comparing to a constant eliiminating a 
class of cases we don;t currently get. ie.

if (x & 1) return;
if (x == 97657) foo()

will eliminate the call to foo, even though we do not remove all the odd 
numbers from the range.  THe bit pattern comparison for
   [irange] unsigned int [0, 0] [2, +INF] MASK 0xfffffffe VALUE 0x1  
will indicate that any even constants will be false.

Bootstraps on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew


[-- Attachment #2: 0002-Adjust-operators-equal-and-not_equal-to-check-bitmas.patch --]
[-- Type: text/x-patch, Size: 4572 bytes --]

From eb899fee35b8326b2105c04f58fd58bbdeca9d3b Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 25 Oct 2023 09:46:50 -0400
Subject: [PATCH 2/2] Adjust operators equal and not_equal to check bitmasks
 against constants

Check to see if a comparison to a constant can be determined to always
be not-equal based on the bitmask.

	PR tree-optimization/111766
	gcc/
	* range-op.cc (operator_equal::fold_range): Check constants
	against the bitmask.
	(operator_not_equal::fold_range): Ditto.
	* value-range.h (irange_bitmask::member_p): New.

	gcc/testsuite/
	* gcc.dg/pr111766.c: New.
---
 gcc/range-op.cc                 | 20 ++++++++++++++++----
 gcc/testsuite/gcc.dg/pr111766.c | 13 +++++++++++++
 gcc/value-range.h               | 14 ++++++++++++++
 3 files changed, 43 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr111766.c

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 33b193be7d0..6137f2aeed3 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -931,8 +931,9 @@ operator_equal::fold_range (irange &r, tree type,
 
   // We can be sure the values are always equal or not if both ranges
   // consist of a single value, and then compare them.
-  if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
-      && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
+  bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
+  bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
+  if (op1_const && op2_const)
     {
       if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
 	r = range_true (type);
@@ -947,6 +948,11 @@ operator_equal::fold_range (irange &r, tree type,
       tmp.intersect (op2);
       if (tmp.undefined_p ())
 	r = range_false (type);
+      // Check if a constant cannot satisfy the bitmask requirements.
+      else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
+	 r = range_false (type);
+      else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
+	 r = range_false (type);
       else
 	r = range_true_and_false (type);
     }
@@ -1033,8 +1039,9 @@ operator_not_equal::fold_range (irange &r, tree type,
 
   // We can be sure the values are always equal or not if both ranges
   // consist of a single value, and then compare them.
-  if (wi::eq_p (op1.lower_bound (), op1.upper_bound ())
-      && wi::eq_p (op2.lower_bound (), op2.upper_bound ()))
+  bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
+  bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
+  if (op1_const && op2_const)
     {
       if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
 	r = range_true (type);
@@ -1049,6 +1056,11 @@ operator_not_equal::fold_range (irange &r, tree type,
       tmp.intersect (op2);
       if (tmp.undefined_p ())
 	r = range_true (type);
+      // Check if a constant cannot satisfy the bitmask requirements.
+      else if (op2_const && !op1.get_bitmask ().member_p (op2.lower_bound ()))
+	 r = range_true (type);
+      else if (op1_const && !op2.get_bitmask ().member_p (op1.lower_bound ()))
+	 r = range_true (type);
       else
 	r = range_true_and_false (type);
     }
diff --git a/gcc/testsuite/gcc.dg/pr111766.c b/gcc/testsuite/gcc.dg/pr111766.c
new file mode 100644
index 00000000000..c27a029c772
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr111766.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int
+foo3n(int c, int bb)
+{
+  if ((bb & ~3)!=0) __builtin_unreachable(); // bb = [0,3]
+  if ((bb & 1)==0) __builtin_unreachable(); // bb&1 == 0 // [0],[3]
+  if(bb == 2) __builtin_trap();
+  return bb;
+}
+
+/* { dg-final { scan-tree-dump-not "trap" "evrp" } } */
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 84f65ffb591..330e6f70c6b 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -139,6 +139,7 @@ public:
   void verify_mask () const;
   void dump (FILE *) const;
 
+  bool member_p (const wide_int &val) const;
   void adjust_range (irange &r) const;
 
   // Convenience functions for nonzero bitmask compatibility.
@@ -202,6 +203,19 @@ irange_bitmask::set_nonzero_bits (const wide_int &bits)
     verify_mask ();
 }
 
+// Return TRUE if val could be a valid value with this bitmask.
+
+inline bool
+irange_bitmask::member_p (const wide_int &val) const
+{
+  if (unknown_p ())
+    return true;
+  wide_int res = m_mask & val;
+  if (m_value != 0)
+    res |= ~m_mask & m_value;
+  return res == val;
+}
+
 inline bool
 irange_bitmask::operator== (const irange_bitmask &src) const
 {
-- 
2.41.0