[Bug tree-optimization/95424] New: Failure to optimize division with numerator of 1

[Bug tree-optimization/95424] New: Failure to optimize division with numerator of 1

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

            Bug ID: 95424
           Summary: Failure to optimize division with numerator of 1
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

unsigned f(unsigned x)
{
    return 1 / x;
}

This can be optimized to `return (x == 1);`, and for `int` to `return
(unsigned)(x + 1) < 3 ? x : 0;`. This transformation is done by LLVM, but not
by GCC.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-06-02
     Ever confirmed|0                           |1

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
   Last reconfirmed|2020-06-02 00:00:00         |2021-8-14

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

--- Comment #1 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Created attachment 52091
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52091&action=edit
Tested patch for the case of unsigned integer X

I tried to tackle the unsigned integer X case by adding an optimization in
match.pd. I suppose it can be done similarly for the signed integer X case as
well, but I'll need more time to look into that.

I've attached the proposed patch. With this patch, GCC generates the same
assembly output as Clang.

int f(unsigned int x) {
        return 1 / x;
}


.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        cmpl    $1, %edi
        sete    %al
        ret

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Zhao Wei Liew <zhaoweiliew at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #52091|0                           |1
        is obsolete|                            |

--- Comment #2 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Created attachment 52097
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52097&action=edit
Optimization for both unsigned and signed integer X

I've attached a new patch which does the optimization for both the unsigned and
the signed case.

With this patch, x86-64 gcc -std=c++20 -O3 produces the following assembly:

f(int):
        lea eax, [rdi + 1]
        cmp eax, 2
        mov eax, 0
        cmovbe eax, edi
        ret
f(unsigned int):
        xor eax, eax
        cmp edi, 1
        sete al
        ret

which is virtually identical to the following assembly produced by clang++
-std=c++20 -O3:

f(int):
        lea ecx, [rdi + 1]
        xor eax, eax
        cmp ecx, 3
        cmovb eax, edi
        ret
f(unsigned int):
        xor eax, eax
        cmp edi, 1
        sete al
        ret

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

--- Comment #3 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Comment on attachment 52097
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52097
Optimization for both unsigned and signed integer X

diff --git a/gcc/match.pd b/gcc/match.pd
index 0d7b8dd1334..6fbf1071a97 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -349,6 +349,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (op @0 integer_onep)
     (non_lvalue @0)))

+/* 1 / X -> X == 1 for unsigned integer X
+   1 / X -> X >= -1 && X <= 1 ? X : 0 for signed integer X */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+  (simplify
+    (div integer_onep@0 @1)
+    (switch
+      /* 1 / X -> X == 1 for unsigned integer X */
+      (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@1))
+          && TYPE_UNSIGNED (TREE_TYPE (@1)))
+        (eq @0 @1))
+      /* 1 / X -> X >= -1 && X <= 1 ? X : 0 for signed integer X */
+      (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@1))
+          && !TYPE_UNSIGNED (TREE_TYPE (@1)))
+       (cond (bit_and (ge @1 { build_minus_one_cst (integer_type_node); })
+                      (le @1 { build_one_cst (integer_type_node); }))
+              @1 { build_zero_cst (type); })))))
+
 /* (A / (1 << B)) -> (A >> B).
    Only for unsigned A.  For signed A, this would not preserve rounding
    toward zero.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

--- Comment #4 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Comment on attachment 52097
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52097
Optimization for both unsigned and signed integer X

diff --git a/gcc/match.pd b/gcc/match.pd
index 0d7b8dd1334..6fbf1071a97 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -349,6 +349,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     (op @0 integer_onep)
     (non_lvalue @0)))

+/* 1 / X -> X == 1 for unsigned integer X
+   1 / X -> X >= -1 && X <= 1 ? X : 0 for signed integer X */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+  (simplify
+    (div integer_onep@0 @1)
+    (switch
+      /* 1 / X -> X == 1 for unsigned integer X */
+      (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@1))
+          && TYPE_UNSIGNED (TREE_TYPE (@1)))
+        (eq @0 @1))
+      /* 1 / X -> X >= -1 && X <= 1 ? X : 0 for signed integer X */
+      (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@1))
+          && !TYPE_UNSIGNED (TREE_TYPE (@1)))
+       (cond (bit_and (ge @1 { build_minus_one_cst (integer_type_node); })
+                      (le @1 { build_one_cst (integer_type_node); }))
+              @1 { build_zero_cst (type); })))))
+
 /* (A / (1 << B)) -> (A >> B).
    Only for unsigned A.  For signed A, this would not preserve rounding
    toward zero.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Zhao Wei Liew <zhaoweiliew at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #52097|0                           |1
        is obsolete|                            |

--- Comment #5 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Created attachment 52098
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52098&action=edit
Optimization patch for both unsigned and signed integer X

Oops, I uploaded the wrong patch previously. I apologise for the spam. Here,
I've fixed the patch.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[zhaoweiliew at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Zhao Wei Liew <zhaoweiliew at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #52098|0                           |1
        is obsolete|                            |

--- Comment #6 from Zhao Wei Liew <zhaoweiliew at gmail dot com> ---
Created attachment 52126
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52126&action=edit
Optimize 1 / X for integer X

Here's a new patch along with test cases.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jeff Law <law@gcc.gnu.org>:

https://gcc.gnu.org/g:c2b610e7c6c89fd422c5c31f01023bcddf3cf4a5

commit r12-6924-gc2b610e7c6c89fd422c5c31f01023bcddf3cf4a5
Author: Zhao Wei Liew <zhaoweiliew@gmail.com>
Date:   Fri Jan 28 13:36:39 2022 -0500

    match.pd: Simplify 1 / X for integer X [PR95424]

    This patch implements an optimization for the following C++ code:

    int f(int x) {
        return 1 / x;
    }

    int f(unsigned int x) {
        return 1 / x;
    }

    Before this patch, x86-64 gcc -std=c++20 -O3 produces the following
assembly:

    f(int):
        xor edx, edx
        mov eax, 1
        idiv edi
        ret
    f(unsigned int):
        xor edx, edx
        mov eax, 1
        div edi
        ret

    In comparison, clang++ -std=c++20 -O3 produces the following assembly:

    f(int):
        lea ecx, [rdi + 1]
        xor eax, eax
        cmp ecx, 3
        cmovb eax, edi
        ret
    f(unsigned int):
        xor eax, eax
        cmp edi, 1
        sete al
        ret

    Clang's output is more efficient as it avoids expensive div operations.

    With this patch, GCC now produces the following assembly:

    f(int):
        lea eax, [rdi + 1]
        cmp eax, 2
        mov eax, 0
        cmovbe eax, edi
        ret
    f(unsigned int):
        xor eax, eax
        cmp edi, 1
        sete al
        ret

    which is virtually identical to Clang's assembly output. Any slight
differences
    in the output for f(int) is possibly related to a different missed
optimization.

    v2: https://gcc.gnu.org/pipermail/gcc-patches/2022-January/587751.html
    Changes from v2:
    1. Refactor from using a switch statement to using the built-in
    if-else statement.

    v1: https://gcc.gnu.org/pipermail/gcc-patches/2022-January/587634.html
    Changes from v1:
    1. Refactor common if conditions.
    2. Use build_[minus_]one_cst (type) to get -1/1 of the correct type.
    3. Match only for TRUNC_DIV_EXPR and TYPE_PRECISION (type) > 1.

    gcc/ChangeLog:

            PR tree-optimization/95424
            * match.pd: Simplify 1 / X where X is an integer.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[law at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu.org
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Fixed on the trunk.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

--- Comment #9 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:3d41939c8799a51b1cd7f4610c06771bf6d52f15

commit r12-6932-g3d41939c8799a51b1cd7f4610c06771bf6d52f15
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Sat Jan 29 17:55:51 2022 +0100

    testsuite: Fix up tree-ssa/divide-7.c testcase [PR95424]

    This test fails everywhere, because ? doesn't match literal ?.
    It should use \\? instead.  I've also changed those .s in there.

    2022-01-29  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/95424
            * gcc.dg/tree-ssa/divide-7.c: Fix up regexps in
scan-tree-dump{,-not}.

[Bug tree-optimization/95424] Failure to optimize division with numerator of 1

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95424

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0