[Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz

[Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz

[gabravier at gmail dot com]

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

            Bug ID: 94802
           Summary: Failure to recognize identities with __builtin_clz
           Product: gcc
           Version: 10.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: ---

bool f(int a, int b)
{
    return __builtin_clz(a - b);
}

This is equivalent to `return a >= b`. This transformation is done by LLVM, but
not by GCC.

Comparison here : https://godbolt.org/z/jvahPh

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[gabravier at gmail dot com]

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

--- Comment #1 from Gabriel Ravier <gabravier at gmail dot com> ---
Also, there are also patterns like `__builtin_clz(a - b) == 31`, which can be
optimized to `(a - b) == 1`

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |easyhack,
                   |                            |missed-optimization
   Last reconfirmed|                            |2020-04-27
                 CC|                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
For the first one, guess __builtin_clz (x) == 0 can be transformed into (int) x
< 0 and similarly __builtin_clz (x) != 0 to (int) x >= 0.
Not sure if we should check CLZ_DEFINED_VALUE_AT_ZERO if it isn't 0 (or
precision-1) for these transformations, while the documentation says that the
builtin is undefined at zero, e.g. if CLZ_DEFINED_VALUE_AT_ZERO returns 2 then
even at GIMPLE the == 0 guard for it could have been optimized away already.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 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:d2eb616a0f7bea78164912aa438c29fe1ef5774a

commit r11-6378-gd2eb616a0f7bea78164912aa438c29fe1ef5774a
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Dec 31 11:09:26 2020 +0100

    match.pd: Add clz(X) == 0 -> (int)X < 0 etc. simpifications [PR94802]

    The following patch adds some clz simplifications.  If
    clz is 0, then the MSB of the argument is set, and if clz is prec-1, then
    the argument is 1.

    2020-12-31  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/94802
            * match.pd (clz(X) == 0 -> (int)X < 0): New simplification.
            (clz(X) == (prec-1) -> X == 1): Likewise.

            * gcc.dg/tree-ssa/pr94802-1.c: New test.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Not fixed completely yet, (a - b) < 0 is not optimized into a < b yet.
The following patch does that, but it regresses 
--- gcc/match.pd.jj     2020-12-30 17:04:27.340815135 +0100
+++ gcc/match.pd        2020-12-30 17:41:44.393443188 +0100
@@ -3966,6 +3966,16 @@ (define_operator_list COND_TERNARY
    (cmp (sub@2 @0 @1) integer_zerop)
    (if (single_use (@2))
     (cmp @0 @1)))))
+#if GIMPLE
+(for cmp (lt le gt ge)
+ (for sub (minus pointer_diff)
+  (simplify
+   (cmp (sub@2 @0 @1) integer_zerop)
+   (if (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+       && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))
+       && single_use (@2))
+    (cmp @0 @1)))))
+#endif

 /* Transform comparisons of the form X * C1 CMP 0 to X CMP 0 in the
    signed arithmetic case.  That form is created by the compiler
the following test:
+FAIL: gcc.dg/tree-ssa/pr45397.c scan-tree-dump-not evrp " & 255;"
+FAIL: gcc.dg/tree-ssa/pr45397.c scan-tree-dump-not phiopt2 "if "
+FAIL: gcc.dg/tree-ssa/pr45397.c scan-tree-dump-times phiopt2 "MAX_EXPR" 3
+FAIL: gcc.dg/tree-ssa/pr45397.c scan-tree-dump-times phiopt2 "MIN_EXPR" 3
so some more work will be needed.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Even when the optimization is restricted to GIMPLE only, the single_use in
there doesn't work really well before fre1 optimizes it, because the above
mentioned testcase doesn't reuse the same expression, but has a different
subtraction that just needs to be CSEd first.
An alternative would be to treat (signed undefined overflow) x >= y and x - y
interchangeably by SCCVN, i.e. hash them the same and if we find both forms (in
either order), transform the x >= y back into (x - y) >= 0 (similar for other
non-equality comparisons).  I guess that would fix both that testcase and
PR94798 which also suffers from that:
int
foo (int a, int b)
{
  return (b >= a) ? (b - a) : 0;
}

int
bar (int a, int b)
{
  return ((b - a) >= 0) ? (b - a) : 0;
}

bar is optimized more than foo - but in this case it is a user that wrote it in
two different forms rather than one.

Another option is to enable the x - y op 0 to x op y canonicalization only
after SCCVN got a chance to CSE stuff after inlining, while that would fix the
por45397.c testcase, it wouldn't the above PR94798 one.

Richi, any thoughts on this?

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
We can't really hash them the same but what is possible is at elimination time
see whether x - y is available when x >= y is encountered and replace the
latter with avail >= 0.  If x - y is not available at the point x>= y is
computed (but only later) then I fear we cannot do this since computing
x - y before might overflow.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Which means it won't help for foo():

  <bb 2> :
  if (b_2(D) >= a_3(D))
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  iftmp.0_5 = b_2(D) - a_3(D);

  <bb 4> :
  # iftmp.0_1 = PHI <iftmp.0_5(3), 0(2)>
  return iftmp.0_1;

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |uros at gcc dot gnu.org

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So shall we deal with that at the RTL level instead then?

Given testcase1:
/* PR tree-optimization/94802 */
/* { dg-do compile } */
/* { dg-options "-O2" } */

void foo (void);

int
f1 (int a, int b)
{
  return (a - b) >= 0;
}

int
f2 (int a, int b)
{
  return (a - b) > 0;
}

int
f3 (int a, int b)
{
  return (a - b) <= 0;
}

int
f4 (int a, int b)
{
  return (a - b) < 0;
}

void
f5 (int a, int b)
{
  if ((a - b) >= 0)
    foo ();
}

void
f6 (int a, int b)
{
  if ((a - b) > 0)
    foo ();
}

void
f7 (int a, int b)
{
  if ((a - b) <= 0)
    foo ();
}

void
f8 (int a, int b)
{
  if ((a - b) < 0)
    foo ();
}

and testcase2, it would be nice to emit the same or at least as good as code
for the first one as for the second one, but the testcase1 to testcase2
difference is:
@@ -6,10 +6,9 @@
 f1:
 .LFB0:
        .cfi_startproc
-       subl    %esi, %edi
-       notl    %edi
-       movl    %edi, %eax
-       shrl    $31, %eax
+       xorl    %eax, %eax
+       cmpl    %esi, %edi
+       setge   %al
        ret
        .cfi_endproc
 .LFE0:
@@ -20,9 +19,8 @@ f1:
 f2:
 .LFB1:
        .cfi_startproc
-       subl    %esi, %edi
        xorl    %eax, %eax
-       testl   %edi, %edi
+       cmpl    %esi, %edi
        setg    %al
        ret
        .cfi_endproc
@@ -34,9 +32,8 @@ f2:
 f3:
 .LFB2:
        .cfi_startproc
-       subl    %esi, %edi
        xorl    %eax, %eax
-       testl   %edi, %edi
+       cmpl    %esi, %edi
        setle   %al
        ret
        .cfi_endproc
@@ -48,9 +45,9 @@ f3:
 f4:
 .LFB3:
        .cfi_startproc
-       subl    %esi, %edi
-       movl    %edi, %eax
-       shrl    $31, %eax
+       xorl    %eax, %eax
+       cmpl    %esi, %edi
+       setl    %al
        ret
        .cfi_endproc
 .LFE3:
@@ -62,7 +59,7 @@ f5:
 .LFB4:
        .cfi_startproc
        cmpl    %esi, %edi
-       jns     .L8
+       jge     .L8
        ret
        .p2align 4,,10
        .p2align 3
@@ -77,8 +74,7 @@ f5:
 f6:
 .LFB5:
        .cfi_startproc
-       subl    %esi, %edi
-       testl   %edi, %edi
+       cmpl    %esi, %edi
        jg      .L11
        ret
        .p2align 4,,10
@@ -94,8 +90,7 @@ f6:
 f7:
 .LFB6:
        .cfi_startproc
-       subl    %esi, %edi
-       testl   %edi, %edi
+       cmpl    %esi, %edi
        jle     .L14
        ret
        .p2align 4,,10
@@ -112,7 +107,7 @@ f8:
 .LFB7:
        .cfi_startproc
        cmpl    %esi, %edi
-       js      .L17
+       jl      .L17
        ret
        .p2align 4,,10
        .p2align 3

We have *cmp<mode>_minus_1 that handles some of this, but not everything.
And now that I think more about it, it can't be done at the RTL level, because
we've lost the information that the subtraction has undefined overflow; when it
overflows, it has different behavior.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49884
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49884&action=edit
gcc11-pr94802.patch

Untested patch to do that during expansion.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[denis.campredon at gmail dot com]

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

denis.campredon at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |denis.campredon at gmail dot com

--- Comment #10 from denis.campredon at gmail dot com ---
PR98236 is also somewhat related, and half of the problems should be solved by
this patch.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 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:5de7bf5bc98ec9edc6838a443521204d0eca7605

commit r11-6482-g5de7bf5bc98ec9edc6838a443521204d0eca7605
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jan 5 19:13:29 2021 +0100

    expand: Fold x - y < 0 to x < y during expansion [PR94802]

    My earlier patch to simplify x - y < 0 etc. for signed subtraction
    with undefined overflow into x < y in match.pd regressed some tests,
    even when it was guarded to be post-IPA, the following patch thus
    attempts to optimize that during expansion instead (which is the last
    time we can do it, afterwards we lose the information whether it was
    x - y < 0 or (int) ((unsigned) x - y) < 0 for which we couldn't
    optimize it.

    2021-01-05  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/94802
            * expr.h (maybe_optimize_sub_cmp_0): Declare.
            * expr.c: Include tree-pretty-print.h and flags.h.
            (maybe_optimize_sub_cmp_0): New function.
            (do_store_flag): Use it.
            * cfgexpand.c (expand_gimple_cond): Likewise.

            * gcc.target/i386/pr94802.c: New test.
            * gcc.dg/Wstrict-overflow-25.c: Remove xfail.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.

[Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0