[COMMITTED,range-op] Take known set bits into account in popcount [PR107053]
Checks
Commit Message
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
Comments
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
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
@@ -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;
}
new file mode 100644
@@ -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" } }