From a239a63f868e29e9276088e7c0fb00804c2903ba Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Fri, 4 Nov 2022 22:24:42 +0100
Subject: Improve multiplication by powers of 2 in range-ops.

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 2b5db0c..a13e888 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -1911,8 +1911,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 0000000..bbdda45
--- /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" } }
-- 
cgit v1.1