* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
@ 2020-04-27 15:14 ` gabravier at gmail dot com
2020-04-27 15:22 ` jakub at gcc dot gnu.org
` (11 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: gabravier at gmail dot com @ 2020-04-27 15:14 UTC (permalink / raw)
To: gcc-bugs
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`
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
2020-04-27 15:14 ` [Bug tree-optimization/94802] " gabravier at gmail dot com
@ 2020-04-27 15:22 ` jakub at gcc dot gnu.org
2020-12-31 10:10 ` cvs-commit at gcc dot gnu.org
` (10 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2020-04-27 15:22 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
2020-04-27 15:14 ` [Bug tree-optimization/94802] " gabravier at gmail dot com
2020-04-27 15:22 ` jakub at gcc dot gnu.org
@ 2020-12-31 10:10 ` cvs-commit at gcc dot gnu.org
2020-12-31 10:15 ` jakub at gcc dot gnu.org
` (9 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2020-12-31 10:10 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (2 preceding siblings ...)
2020-12-31 10:10 ` cvs-commit at gcc dot gnu.org
@ 2020-12-31 10:15 ` jakub at gcc dot gnu.org
2021-01-02 8:44 ` jakub at gcc dot gnu.org
` (8 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2020-12-31 10:15 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (3 preceding siblings ...)
2020-12-31 10:15 ` jakub at gcc dot gnu.org
@ 2021-01-02 8:44 ` jakub at gcc dot gnu.org
2021-01-05 10:25 ` rguenth at gcc dot gnu.org
` (7 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-02 8:44 UTC (permalink / raw)
To: gcc-bugs
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?
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (4 preceding siblings ...)
2021-01-02 8:44 ` jakub at gcc dot gnu.org
@ 2021-01-05 10:25 ` rguenth at gcc dot gnu.org
2021-01-05 10:28 ` rguenth at gcc dot gnu.org
` (6 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-01-05 10:25 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (5 preceding siblings ...)
2021-01-05 10:25 ` rguenth at gcc dot gnu.org
@ 2021-01-05 10:28 ` rguenth at gcc dot gnu.org
2021-01-05 11:18 ` jakub at gcc dot gnu.org
` (5 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: rguenth at gcc dot gnu.org @ 2021-01-05 10:28 UTC (permalink / raw)
To: gcc-bugs
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;
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (6 preceding siblings ...)
2021-01-05 10:28 ` rguenth at gcc dot gnu.org
@ 2021-01-05 11:18 ` jakub at gcc dot gnu.org
2021-01-05 12:13 ` jakub at gcc dot gnu.org
` (4 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-05 11:18 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (7 preceding siblings ...)
2021-01-05 11:18 ` jakub at gcc dot gnu.org
@ 2021-01-05 12:13 ` jakub at gcc dot gnu.org
2021-01-05 14:32 ` denis.campredon at gmail dot com
` (3 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-05 12:13 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (8 preceding siblings ...)
2021-01-05 12:13 ` jakub at gcc dot gnu.org
@ 2021-01-05 14:32 ` denis.campredon at gmail dot com
2021-01-05 18:14 ` cvs-commit at gcc dot gnu.org
` (2 subsequent siblings)
12 siblings, 0 replies; 14+ messages in thread
From: denis.campredon at gmail dot com @ 2021-01-05 14:32 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (9 preceding siblings ...)
2021-01-05 14:32 ` denis.campredon at gmail dot com
@ 2021-01-05 18:14 ` cvs-commit at gcc dot gnu.org
2021-01-05 18:16 ` jakub at gcc dot gnu.org
2021-08-14 22:29 ` pinskia at gcc dot gnu.org
12 siblings, 0 replies; 14+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-01-05 18:14 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (10 preceding siblings ...)
2021-01-05 18:14 ` cvs-commit at gcc dot gnu.org
@ 2021-01-05 18:16 ` jakub at gcc dot gnu.org
2021-08-14 22:29 ` pinskia at gcc dot gnu.org
12 siblings, 0 replies; 14+ messages in thread
From: jakub at gcc dot gnu.org @ 2021-01-05 18:16 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [Bug tree-optimization/94802] Failure to recognize identities with __builtin_clz
2020-04-27 15:10 [Bug tree-optimization/94802] New: Failure to recognize identities with __builtin_clz gabravier at gmail dot com
` (11 preceding siblings ...)
2021-01-05 18:16 ` jakub at gcc dot gnu.org
@ 2021-08-14 22:29 ` pinskia at gcc dot gnu.org
12 siblings, 0 replies; 14+ messages in thread
From: pinskia at gcc dot gnu.org @ 2021-08-14 22:29 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 14+ messages in thread