[COMMITTED] Improve multiplication by powers of 2 in range-ops.

[COMMITTED] Improve multiplication by powers of 2 in range-ops.

[Aldy Hernandez]

For unsigned numbers, multiplication by X, where X is a power of 2 is
[0,0][X,+INF].

This patch causes a regression to g++.dg/pr71488.C where
-Wstringop-overflow gets the same IL as before, but better ranges
cause it to issue a bogus warning.  I will create a PR with some
notes.

No discernible changes in performance.

Tested on x86-64 Linux.

	PR tree-optimization/55157

gcc/ChangeLog:

	* range-op.cc (operator_mult::wi_fold): Optimize multiplications
	by powers of 2.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/pr55157.c: New test.
---
 gcc/range-op.cc                         | 16 ++++++++++++++--
 gcc/testsuite/gcc.dg/tree-ssa/pr55157.c | 19 +++++++++++++++++++
 2 files changed, 33 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr55157.c

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index 25c004d8287..835b43fb747 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1910,8 +1910,20 @@ operator_mult::wi_fold (irange &r, tree type,
   // diff = max - min
   prod2 = prod3 - prod0;
   if (wi::geu_p (prod2, sizem1))
-    // The range covers all values.
-    r.set_varying (type);
+    {
+      // Multiplying by X, where X is a power of 2 is [0,0][X,+INF].
+      if (TYPE_UNSIGNED (type) && rh_lb == rh_ub
+	  && wi::exact_log2 (rh_lb) != -1 && prec > 1)
+	{
+	  r.set (type, rh_lb, wi::max_value (prec, sign));
+	  int_range<2> zero;
+	  zero.set_zero (type);
+	  r.union_ (zero);
+	}
+      else
+	// The range covers all values.
+	r.set_varying (type);
+    }
   else
     {
       wide_int new_lb = wide_int::from (prod0, prec, sign);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr55157.c b/gcc/testsuite/gcc.dg/tree-ssa/pr55157.c
new file mode 100644
index 00000000000..bbdda45bd64
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr55157.c
@@ -0,0 +1,19 @@
+// { dg-do compile }
+// { dg-options "-O2 -fdump-tree-evrp" }
+
+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-times " if " 1 "evrp" } }
-- 
2.38.1

Re: [COMMITTED] Improve multiplication by powers of 2 in range-ops.

[Aldy Hernandez]

On Mon, Nov 7, 2022 at 8:59 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> For unsigned numbers, multiplication by X, where X is a power of 2 is
> [0,0][X,+INF].
>
> This patch causes a regression to g++.dg/pr71488.C where
> -Wstringop-overflow gets the same IL as before, but better ranges
> cause it to issue a bogus warning.  I will create a PR with some
> notes.

PR107561