[gcc r13-3688] Set nonzero bits for multiplication and divisions by a power of 2.

[gcc r13-3688] Set nonzero bits for multiplication and divisions by a power of 2.

[Aldy Hernandez]

https://gcc.gnu.org/g:679be32e66428f0ba81d1c1b55f7bd47f01cb295

commit r13-3688-g679be32e66428f0ba81d1c1b55f7bd47f01cb295
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Nov 4 10:20:46 2022 +0100

    Set nonzero bits for multiplication and divisions by a power of 2.
    
    We're missing a lot of TLC in keeping track of nonzero bits across
    range-ops.  It isn't an oversight, but just limited amount of hours to
    implement stuff.
    
    This patch keeps better track of the nonzero mask (really
    maybe_nonzero bits as discussed) across multiplication and division
    when the RHS is a power of 2.
    
    It fixes PR107342 and also touches on PR55157.  In the latter, the
    nonzero mask is being set quite late (CCP2) but could be set by evrp
    time if we enhanced range-ops.  I have added tests from both PRs.
    
    Tested
    
            PR tree-optimization/107342
    
    gcc/ChangeLog:
    
            * range-op.cc (operator_mult::fold_range): New.
            (operator_div::fold_range): New.
    
    gcc/testsuite/ChangeLog:
    
            * gcc.dg/tree-ssa/vrp122.c: New test.
            * gcc.dg/tree-ssa/vrp123.c: New test.

Diff:
---
 gcc/range-op.cc                        | 59 ++++++++++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/vrp122.c | 19 +++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/vrp123.c | 18 +++++++++++
 3 files changed, 96 insertions(+)

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 49ee7be3d3b..25c004d8287 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1742,9 +1742,13 @@ cross_product_operator::wi_cross_product (irange &r, tree type,
 
 class operator_mult : public cross_product_operator
 {
+  using range_operator::fold_range;
   using range_operator::op1_range;
   using range_operator::op2_range;
 public:
+  virtual bool fold_range (irange &r, tree type,
+			   const irange &lh, const irange &rh,
+			   relation_trio = TRIO_VARYING) const final override;
   virtual void wi_fold (irange &r, tree type,
 		        const wide_int &lh_lb,
 		        const wide_int &lh_ub,
@@ -1762,6 +1766,32 @@ public:
 			  relation_trio) const;
 } op_mult;
 
+bool
+operator_mult::fold_range (irange &r, tree type,
+			   const irange &lh, const irange &rh,
+			   relation_trio trio) const
+{
+  if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
+    return false;
+
+  if (lh.undefined_p ())
+    return true;
+
+  tree t;
+  if (rh.singleton_p (&t))
+    {
+      wide_int w = wi::to_wide (t);
+      int shift = wi::exact_log2 (w);
+      if (shift != -1)
+	{
+	  wide_int nz = lh.get_nonzero_bits ();
+	  nz = wi::lshift (nz, shift);
+	  r.set_nonzero_bits (nz);
+	}
+    }
+  return true;
+}
+
 bool
 operator_mult::op1_range (irange &r, tree type,
 			  const irange &lhs, const irange &op2,
@@ -1902,10 +1932,39 @@ public:
 		        const wide_int &rh_ub) const;
   virtual bool wi_op_overflows (wide_int &res, tree type,
 				const wide_int &, const wide_int &) const;
+  virtual bool fold_range (irange &r, tree type,
+			   const irange &lh, const irange &rh,
+			   relation_trio trio) const final override;
 private:
   enum tree_code code;
 };
 
+bool
+operator_div::fold_range (irange &r, tree type,
+			  const irange &lh, const irange &rh,
+			  relation_trio trio) const
+{
+  if (!cross_product_operator::fold_range (r, type, lh, rh, trio))
+    return false;
+
+  if (lh.undefined_p ())
+    return true;
+
+  tree t;
+  if (rh.singleton_p (&t))
+    {
+      wide_int wi = wi::to_wide (t);
+      int shift = wi::exact_log2 (wi);
+      if (shift != -1)
+	{
+	  wide_int nz = lh.get_nonzero_bits ();
+	  nz = wi::rshift (nz, shift, TYPE_SIGN (type));
+	  r.set_nonzero_bits (nz);
+	}
+    }
+  return true;
+}
+
 bool
 operator_div::wi_op_overflows (wide_int &res, tree type,
 			       const wide_int &w0, const wide_int &w1) const
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c
new file mode 100644
index 00000000000..b2ddcda023c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp122.c
@@ -0,0 +1,19 @@
+// { dg-do compile }
+// { dg-options "-O2 -fdump-tree-evrp-details" }
+
+void gg(void);
+int f(unsigned t)
+{
+  unsigned g = t*16;
+  if (g==0)  return 1;
+  gg();
+  gg();
+  gg();
+  gg();
+  gg();
+  gg();
+  if (g<=4)  return 1;
+  return 0;
+}
+
+// { dg-final { scan-tree-dump "Global Exported: g_.* NONZERO 0x.*fff0" "evrp" } }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp123.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp123.c
new file mode 100644
index 00000000000..1ad3caa4384
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp123.c
@@ -0,0 +1,18 @@
+// { dg-options "-O1 -fdump-tree-dom3-raw" }
+
+extern int
+__attribute__((const))
+foo4b (int);
+
+int f4b (unsigned int r)
+{
+  if (foo4b (r))
+    r *= 8U;
+
+  if ((r / 2U) & 2U)
+    r += foo4b (r);
+
+  return r;
+}
+
+// { dg-final { scan-tree-dump-times {gimple_call <foo4b,} 1 dom3 } }