Re: [PATCH][v2] tree-optimization: Fold (type)X / (type)Y [PR103855]

[Zhao Wei Liew <zhaoweiliew@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3309 bytes --]

Thanks for the detailed review. I have uploaded patch v2 based on the review.

v1: https://gcc.gnu.org/pipermail/gcc-patches/2022-February/590604.html
Changes since v1:
1. Add patterns for the cases CST / (T)x and (T)x / CST as well. Fix
test regressions caused by those patterns.
2. Support signed integers except for the possible INT_MIN / -1 case.
3. Support cases where X and Y have different precisions.

On Tue, 22 Feb 2022 at 15:54, Richard Biener <richard.guenther@gmail.com> wrote:
> +/* (type)X / (type)Y -> (type)(X / Y)
> +   when the resulting type is at least precise as the original types
> +   and when all the types are unsigned integral types. */
> +(simplify
> + (trunc_div (convert @0) (convert @1))
> + (if (INTEGRAL_TYPE_P (type)
> +      && INTEGRAL_TYPE_P (TREE_TYPE (@0))
> +      && INTEGRAL_TYPE_P (TREE_TYPE (@1))
> +      && TYPE_UNSIGNED (type)
> +      && TYPE_UNSIGNED (TREE_TYPE (@0))
> +      && TYPE_UNSIGNED (TREE_TYPE (@1))
> +      && TYPE_PRECISION (TREE_TYPE (@0)) == TYPE_PRECISION (TREE_TYPE (@1))
> +      && TYPE_PRECISION (type) >= TYPE_PRECISION (TREE_TYPE (@0)))
> +  (convert (trunc_div @0 @1))))
>
> since you are requiring the types of @0 and @1 to match it's easier to write
>
>      && types_match (TREE_TYPE(@0), TREE_TYPE (@1))
>

Thanks. In the new patch, TREE_TYPE (@0) and TREE_TYPE (@1) can now
have different precisions, so I believe that I can't use types_match()
anymore.

> that allows you to elide checks on either @0 or @1.  I suppose the transform
> does not work for signed types because of the -INT_MIN / -1 overflow case?
> It might be possible to use expr_not_equal_to (@0, -INT_MIN) ||
> expr_not_equal_to (@1, -1)
> (correctly written, lookup the existing examples in match.pd for the X
> % -Y transform)

That's right. I have made changes to support signed types except for
the INT_MIN / -1 case.

> I'll note that as written the transform will not catch CST / (T)x or
> (T)x / CST since
> you'll not see conversions around constants.  I'm not sure whether
> using (convert[12]? ...)
> or writing special patterns with INTEGER_CST operands is more convenient.
> There is int_fits_type_p to check whether a constant will fit in a
> type without truncation
> or sign change.

I see. I couldn't find an easy way to use (convert[12]? ...) in this
case so I added 2 other patterns for the CST / (T)x and (T)x / CST
cases.

> When @0 and @1 do not have the same type there might still be a common type
> that can be used and is smaller than 'type', it might be as simple as using
> build_nonstandard_integer_type (MIN (@0-prec, @1-prec), 1 /*unsigned_p*/).

Thanks for the tip. I've made a similar change, but using either
TREE_TYPE (@0) or TREE_TYPE (@1) instead of
build_nonstandard_integer_type().

>
> In the past there have been attempts to more globally narrow operations using
> a new pass rather than using individual patterns.  So for more complicated cases
> that might be the way to go.  There's now also the ISEL pass which does
> pre-RTL expansion transforms that need some global context and for example
> can look at SSA uses.

I had wanted to do something similar to handle all integral
trunc_divs, but I'm not sure where/how to start. It seems out of my
league at this moment. I'll gladly explore it after this change
though!

[-- Attachment #2: 0001-tree-optimization-PR103855-Fold-type-X-type-Y.patch.txt --]
[-- Type: text/plain, Size: 6817 bytes --]

From f5f768b55f6cadcd9eba459561abfc1d7e28f94e Mon Sep 17 00:00:00 2001
From: Zhao Wei Liew <zhaoweiliew@gmail.com>
Date: Sat, 19 Feb 2022 16:28:38 +0800
Subject: [PATCH] tree-optimization: [PR103855] Fold (type)X / (type)Y

This pattern converts (trunc_div (convert X) (convert Y)) to
(convert (trunc_div X Y)) when:

1. type, X, and Y are all INTEGRAL_TYPES with the same signedness.
2. type has TYPE_PRECISION at least as large as those of X and Y.
3. the result of the division is guaranteed to fit in either
   the type of Y or the type of Y.

This patch also adds corresponding patterns for CST / (type)Y
and (type)X / CST.

These patterns useful as wider divisions are typically more expensive.

Bootstrapped and regression tested on x86_64-pc-linux-gnu.

Signed-off-by: Zhao Wei Liew <zhaoweiliew@gmail.com>

	PR tree-optimization/103855

gcc/ChangeLog:

	* match.pd: Add patterns for (type)X / (type)Y,
          CST / (type)Y, and (type)X / CST.

gcc/testsuite/ChangeLog:

	* gcc.dg/ipa/pr91088.c: Fix a test regression.
	* gcc.dg/tree-ssa/divide-8.c: New test.
---
 gcc/match.pd                             | 57 ++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/ipa/pr91088.c       |  4 +-
 gcc/testsuite/gcc.dg/tree-ssa/divide-8.c | 45 +++++++++++++++++++
 3 files changed, 104 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/divide-8.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 8b44b5cc92c..b0bfb94f506 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -687,6 +687,63 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
   (convert (trunc_mod @0 @1))))
 
+/* (type)X / (type)Y -> (type)(X / Y)
+   when all types are integral and have the same sign and
+   the resulting type is at least precise as the original types, */
+(simplify
+ (trunc_div (convert @0) (convert @1))
+ (if (INTEGRAL_TYPE_P (type)
+      && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+      && INTEGRAL_TYPE_P (TREE_TYPE (@1))
+      && TYPE_PRECISION (type) >= TYPE_PRECISION (TREE_TYPE (@0))
+      && TYPE_PRECISION (type) >= TYPE_PRECISION (TREE_TYPE (@1))
+      && TYPE_UNSIGNED (type) == TYPE_UNSIGNED (TREE_TYPE (@0))
+      && TYPE_UNSIGNED (type) == TYPE_UNSIGNED (TREE_TYPE (@1)))
+  (with
+   {
+    tree stype = TYPE_PRECISION (TREE_TYPE (@0)) > TYPE_PRECISION (TREE_TYPE (@1))
+                 ? TREE_TYPE (@0) : TREE_TYPE (@1);
+   }
+   (if (TYPE_UNSIGNED (type)
+        /* Avoid this transformation if X might be INT_MIN of the larger type or
+           Y might be -1 because the result might overflow. */
+        || TYPE_PRECISION (TREE_TYPE (@0)) < TYPE_PRECISION (stype)
+        || expr_not_equal_to (@0, wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (@0))))
+        || expr_not_equal_to (@1, wi::minus_one (TYPE_PRECISION (TREE_TYPE (@1)))))
+    (convert (trunc_div (convert:stype @0) (convert:stype @1)))))))
+
+/* (type)X / CST -> (type)(X / CST) */
+(simplify
+ (trunc_div (convert @0) INTEGER_CST@1)
+ (if (INTEGRAL_TYPE_P (type)
+      && INTEGRAL_TYPE_P (TREE_TYPE (@0))
+      && TYPE_UNSIGNED (TREE_TYPE (@0)) == TYPE_UNSIGNED (type)
+      && int_fits_type_p (@1, TREE_TYPE (@0))
+      && TYPE_PRECISION (type) >= TYPE_PRECISION (TREE_TYPE (@0))
+      && (TYPE_UNSIGNED (type)
+       /* Avoid this transformation if X might be MIN_VALUE or
+          Y might be -1 because the result might overflow. */
+       || expr_not_equal_to (@0, wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (@0))))
+       || wi::to_wide (@1) != -1))
+   (with { tree stype = TREE_TYPE (@0); }
+    (convert (trunc_div @0 (convert:stype @1))))))
+
+/* CST / (type)Y -> (type)(CST / Y) */
+(simplify
+ (trunc_div INTEGER_CST@0 (convert @1))
+ (if (INTEGRAL_TYPE_P (type)
+      && INTEGRAL_TYPE_P (TREE_TYPE (@1))
+      && TYPE_UNSIGNED (TREE_TYPE (@1)) == TYPE_UNSIGNED (type)
+      && int_fits_type_p (@0, TREE_TYPE (@1))
+      && TYPE_PRECISION (type) >= TYPE_PRECISION (TREE_TYPE (@1))
+      && (TYPE_UNSIGNED (type)
+          /* Avoid this transformation if X might be MIN_VALUE or
+             Y might be -1 because the result might overflow. */
+          || !tree_int_cst_equal (TYPE_MIN_VALUE (TREE_TYPE (@1)), @0)
+          || expr_not_equal_to (@1, wi::minus_one (TYPE_PRECISION (TREE_TYPE (@1))))))
+   (with { tree stype = TREE_TYPE (@1); }
+    (convert (trunc_div (convert:stype @0) @1)))))
+
 /* x * (1 + y / x) - y -> x - y % x */
 (simplify
  (minus (mult:cs @0 (plus:s (trunc_div:s @1 @0) integer_onep)) @1)
diff --git a/gcc/testsuite/gcc.dg/ipa/pr91088.c b/gcc/testsuite/gcc.dg/ipa/pr91088.c
index cc146a88134..d7332974e37 100644
--- a/gcc/testsuite/gcc.dg/ipa/pr91088.c
+++ b/gcc/testsuite/gcc.dg/ipa/pr91088.c
@@ -60,7 +60,7 @@ int callee1 (struct A a)
   if ((a.f2 + 7) & 17)
     foo ();
 
-  if ((1300 / (short)a.f3) == 19)
+  if ((1300 / (a.f3 & 0xffff)) == 19)
     large_code;
 
   return 1;
@@ -115,6 +115,6 @@ int caller ()
 /* { dg-final { scan-ipa-dump-times "Creating a specialized node of callee1" 1 "cp" } } */
 /* { dg-final { scan-ipa-dump-times "Creating a specialized node of callee2" 1 "cp" } } */
 /* { dg-final { scan-ipa-dump-times "Creating a specialized node of callee3" 1 "cp" } } */
-/* { dg-final { scan-ipa-dump "op0\\\[offset: 32],\\(\\(short int\\) #\\),\\(\\(int\\) #\\),\\(1300 / #\\) == 19" "cp" } } */
+/* { dg-final { scan-ipa-dump "op0\\\[offset: 32],\\(# & 65535\\),\\(1300 / #\\) == 19" "cp" } } */
 /* { dg-final { scan-ipa-dump "op0\\\[ref offset: 0],\\(# \\^ 1\\) <" "cp" } } */
 /* { dg-final { scan-ipa-dump "op0,\\(# & 255\\),\\(1 - #\\),\\(# \\* 3\\),\\(27 % #\\) <" "cp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/divide-8.c b/gcc/testsuite/gcc.dg/tree-ssa/divide-8.c
new file mode 100644
index 00000000000..e389e85a04f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/divide-8.c
@@ -0,0 +1,45 @@
+/* PR tree-optimization/103855 */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+unsigned int f1(unsigned int a, unsigned int b) {
+	unsigned long long all = a;
+	return all / b;
+}
+
+unsigned int f2(unsigned char a, unsigned int b) {
+	unsigned long long all = a;
+	return all / b;
+}
+
+unsigned int f3(unsigned int a, unsigned char b) {
+	unsigned long long all = a;
+	return all / b;
+}
+
+int f4(char a, int b) {
+	long long all = a;
+	return all / b;
+}
+
+unsigned int f5(unsigned int a) {
+	unsigned long long all = a;
+	return all / 123456789;
+}
+
+unsigned int f6(unsigned int b) {
+	unsigned long long bll = b;
+	return 123456789 / bll;
+}
+
+int f7(int a) {
+  long long all = a;
+	return all / 123456789;
+}
+
+int f8(int b) {
+	long long bll = b;
+	return 123456789 / bll;
+}
+
+/* { dg-final { scan-tree-dump-not "\\\(long long unsigned int\\\)" "optimized" } } */
+/* { dg-final { scan-tree-dump-not "\\\(long long int\\\)" "optimized" } } */
-- 
2.25.1