[COMMITTED] [range-op] Take known set bits into account in popcount [PR107053]

[COMMITTED] [range-op] Take known set bits into account in popcount [PR107053]

[Aldy Hernandez]

This patch teaches popcount about known set bits which are now
available in the irange.

	PR tree-optimization/107053

gcc/ChangeLog:

	* gimple-range-op.cc (cfn_popcount): Use known set bits.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/pr107053.c: New test.
---
 gcc/gimple-range-op.cc                   | 11 +++++++----
 gcc/testsuite/gcc.dg/tree-ssa/pr107053.c | 13 +++++++++++++
 2 files changed, 20 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr107053.c

diff --git a/gcc/gimple-range-op.cc b/gcc/gimple-range-op.cc
index 72c7b866f90..67b3c3d015e 100644
--- a/gcc/gimple-range-op.cc
+++ b/gcc/gimple-range-op.cc
@@ -880,17 +880,20 @@ public:
     if (lh.undefined_p ())
       return false;
     unsigned prec = TYPE_PRECISION (type);
-    wide_int nz = lh.get_nonzero_bits ();
-    wide_int pop = wi::shwi (wi::popcount (nz), prec);
+    irange_bitmask bm = lh.get_bitmask ();
+    wide_int nz = bm.get_nonzero_bits ();
+    wide_int high = wi::shwi (wi::popcount (nz), prec);
     // Calculating the popcount of a singleton is trivial.
     if (lh.singleton_p ())
       {
-	r.set (type, pop, pop);
+	r.set (type, high, high);
 	return true;
       }
     if (cfn_ffs::fold_range (r, type, lh, rh, rel))
       {
-	int_range<2> tmp (type, wi::zero (prec), pop);
+	wide_int known_ones = ~bm.mask () & bm.value ();
+	wide_int low = wi::shwi (wi::popcount (known_ones), prec);
+	int_range<2> tmp (type, low, high);
 	r.intersect (tmp);
 	return true;
       }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr107053.c b/gcc/testsuite/gcc.dg/tree-ssa/pr107053.c
new file mode 100644
index 00000000000..8195d0f57b4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr107053.c
@@ -0,0 +1,13 @@
+// { dg-do compile }
+// { dg-options "-O2 -fdump-tree-evrp" }
+
+void link_failure();
+void f(int a)
+{
+    a |= 0x300;
+    int b =  __builtin_popcount(a);
+    if (b < 2)
+        link_failure();
+}
+
+// { dg-final { scan-tree-dump-not "link_failure" "evrp" } }
-- 
2.40.1

[COMMITTED] [range-op] Take known mask into account for bitwise ands [PR107043]

[Aldy Hernandez]

	PR tree-optimization/107043

gcc/ChangeLog:

	* range-op.cc (operator_bitwise_and::op1_range): Update bitmask.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/pr107043.c: New test.
---
 gcc/range-op.cc                          |  8 ++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr107043.c | 22 ++++++++++++++++++++++
 2 files changed, 30 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr107043.c

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 56e80c9f3ae..6b5d4f2accd 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -3463,6 +3463,14 @@ operator_bitwise_and::op1_range (irange &r, tree type,
   if (r.undefined_p ())
     set_nonzero_range_from_mask (r, type, lhs);
 
+  // For MASK == op1 & MASK, all the bits in MASK must be set in op1.
+  wide_int mask;
+  if (lhs == op2 && lhs.singleton_p (mask))
+    {
+      r.update_bitmask (irange_bitmask (mask, ~mask));
+      return true;
+    }
+
   // For 0 = op1 & MASK, op1 is ~MASK.
   if (lhs.zero_p () && op2.singleton_p ())
     {
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr107043.c b/gcc/testsuite/gcc.dg/tree-ssa/pr107043.c
new file mode 100644
index 00000000000..af5df225746
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr107043.c
@@ -0,0 +1,22 @@
+// { dg-do compile }
+// { dg-options "-O2 -fdump-tree-evrp" }
+
+int g0(int n)
+{
+  int n1 = n & 0x8000;
+  if (n1 == 0)
+    return 1;
+  // n1 will be 0x8000 here.
+  return (n1 >> 15) & 0x1;
+}
+
+int g1(int n)
+{
+  int n1 = n & 0x8000;
+  if (n1 == 0)
+    return 1;
+  // n>>15 will be xxxxxx1 here.
+  return (n >> 15) & 0x1;
+}
+
+// { dg-final { scan-tree-dump-times "return 1;" 2 "evrp" } }
-- 
2.40.1

Re: [COMMITTED] [range-op] Take known set bits into account in popcount [PR107053]

[Jeff Law]

On 7/12/23 15:15, Aldy Hernandez via Gcc-patches wrote:
> This patch teaches popcount about known set bits which are now
> available in the irange.
> 
> 	PR tree-optimization/107053
> 
> gcc/ChangeLog:
> 
> 	* gimple-range-op.cc (cfn_popcount): Use known set bits.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/pr107053.c: New test.
You could probably play similar games with ctz/clz, though it's hard to 
know if it's worth the effort.

One way to find out might be to build jemalloc which uses those idioms 
heavily.  Similarly for deepsjeng from spec2017.

Jeff

Re: [COMMITTED] [range-op] Take known set bits into account in popcount [PR107053]

[Aldy Hernandez]

On 7/12/23 23:50, Jeff Law wrote:
> 
> 
> On 7/12/23 15:15, Aldy Hernandez via Gcc-patches wrote:
>> This patch teaches popcount about known set bits which are now
>> available in the irange.
>>
>>     PR tree-optimization/107053
>>
>> gcc/ChangeLog:
>>
>>     * gimple-range-op.cc (cfn_popcount): Use known set bits.
>>
>> gcc/testsuite/ChangeLog:
>>
>>     * gcc.dg/tree-ssa/pr107053.c: New test.
> You could probably play similar games with ctz/clz, though it's hard to 
> know if it's worth the effort.
> 
> One way to find out might be to build jemalloc which uses those idioms 
> heavily.  Similarly for deepsjeng from spec2017.
> 
> Jeff
> 

See class cfn_clz and class cfn_ctz in gimple-range-op.cc.  There's 
already code for both of these, although they're throwback from the VRP 
era, so there's definitely room for improvement.  I think they came from 
vr-values.cc.

Aldy