* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
@ 2007-08-23 20:10 ` eweddington at cso dot atmel dot com
2007-11-02 14:18 ` rask at gcc dot gnu dot org
` (5 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: eweddington at cso dot atmel dot com @ 2007-08-23 20:10 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from eweddington at cso dot atmel dot com 2007-08-23 20:10 -------
Confirmed for AVR. GCC 4.2.1 for avr generates this:
foo:
/* prologue: frame size=0 */
push r14
push r15
push r16
push r17
/* prologue end (size=4) */
movw r14,r22
movw r16,r24
sub r14,r18
sbc r15,r19
sbc r16,r20
sbc r17,r21
cp r22,r18
cpc r23,r19
cpc r24,r20
cpc r25,r21
brsh .L2
ldi r24,lo8(100)
ldi r25,hi8(100)
ldi r26,hlo8(100)
ldi r27,hhi8(100)
add r14,r24
adc r15,r25
adc r16,r26
adc r17,r27
.L2:
movw r24,r16
movw r22,r14
/* epilogue: frame size=0 */
pop r17
pop r16
pop r15
pop r14
ret
Ideally it should be something like:
foo:
/* prologue: frame size=0 */
sub r22,r18
sbc r23,r19
sbc r24,r20
sbc r25,r21
brcc .L2
ldi r18,lo8(100)
ldi r19,hi8(100)
ldi r20,hlo8(100)
ldi r21,hhi8(100)
add r22,r18
adc r23,r19
adc r24,r20
adc r25,r21
.L2:
/* epilogue: frame size=0 */
ret
Which is less than half the number of instructions.
Changing summary and target fields
--
eweddington at cso dot atmel dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
GCC target triplet|i386-linux, powerpc-*-* |i386-linux, powerpc-*-*,
| |avr-*-*
Last reconfirmed|2006-03-05 03:13:08 |2007-08-23 20:10:25
date| |
Summary|appalling optimisation with |appalling optimisation with
|sub/cmp on i386 |sub/cmp on multiple targets
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
2007-08-23 20:10 ` [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets eweddington at cso dot atmel dot com
@ 2007-11-02 14:18 ` rask at gcc dot gnu dot org
2007-11-27 18:04 ` rask at gcc dot gnu dot org
` (4 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: rask at gcc dot gnu dot org @ 2007-11-02 14:18 UTC (permalink / raw)
To: gcc-bugs
--
rask at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |rask at gcc dot gnu dot org
|dot org |
Status|NEW |ASSIGNED
Last reconfirmed|2007-08-23 20:10:25 |2007-11-02 14:17:51
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
2007-08-23 20:10 ` [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets eweddington at cso dot atmel dot com
2007-11-02 14:18 ` rask at gcc dot gnu dot org
@ 2007-11-27 18:04 ` rask at gcc dot gnu dot org
2007-11-28 18:01 ` rask at gcc dot gnu dot org
` (3 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: rask at gcc dot gnu dot org @ 2007-11-27 18:04 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from rask at gcc dot gnu dot org 2007-11-27 18:04 -------
Created an attachment (id=14647)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14647&action=view)
Patch to enhance cse.c
The attached patch can optimize this testcase:
void foo (int);
int bar2 (int a, int b)
{
int c = a - b;
if (a < b)
{
foo (c);
}
return c;
}
Before:
bar2:
pushl %ebx # 33 *pushsi2 [length = 1]
subl $8, %esp # 34 pro_epilogue_adjust_stack_1/1 [length
= 3]
movl 16(%esp), %edx # 2 *movsi_1/1 [length = 4]
movl 20(%esp), %eax # 3 *movsi_1/1 [length = 4]
movl %edx, %ebx # 32 *movsi_1/1 [length = 2]
subl %eax, %ebx # 7 *subsi_1/1 [length = 2]
cmpl %eax, %edx # 8 *cmpsi_1_insn/1 [length = 2]
jge .L2 # 9 *jcc_1 [length = 2]
movl %ebx, (%esp) # 11 *movsi_1/2 [length = 3]
call foo # 12 *call_0 [length = 5]
.L2:
movl %ebx, %eax # 19 *movsi_1/1 [length = 2]
addl $8, %esp # 37 pro_epilogue_adjust_stack_1/1 [length
= 3]
popl %ebx # 38 popsi1 [length = 1]
ret # 39 return_internal [length = 1]
After:
bar2:
pushl %ebx # 33 *pushsi2 [length = 1]
subl $8, %esp # 34 pro_epilogue_adjust_stack_1/1 [length
= 3]
movl 16(%esp), %eax # 2 *movsi_1/1 [length = 4]
movl %eax, %ebx # 32 *movsi_1/1 [length = 2]
subl 20(%esp), %ebx # 8 *subsi_2/2 [length = 4]
jns .L2 # 9 *jcc_1 [length = 2]
movl %ebx, (%esp) # 11 *movsi_1/2 [length = 3]
call foo # 12 *call_0 [length = 5]
.L2:
movl %ebx, %eax # 19 *movsi_1/1 [length = 2]
addl $8, %esp # 37 pro_epilogue_adjust_stack_1/1 [length
= 3]
popl %ebx # 38 popsi1 [length = 1]
ret # 39 return_internal [length = 1]
One of the difficulties is that by the time the code gets to the cse1 pass, the
statement "c = a - b" might have been moved below the "a < b" test, making it
harder to optimize. The "bar2" testcase was crafted so this doesn't happen. But
given the need to potentially replace both the sub/cmp insn and the jump insn,
it would be better to move this optimization to combine.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2007-11-27 18:04 ` rask at gcc dot gnu dot org
@ 2007-11-28 18:01 ` rask at gcc dot gnu dot org
2007-11-28 22:02 ` steven at gcc dot gnu dot org
` (2 subsequent siblings)
6 siblings, 0 replies; 12+ messages in thread
From: rask at gcc dot gnu dot org @ 2007-11-28 18:01 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from rask at gcc dot gnu dot org 2007-11-28 18:01 -------
Created an attachment (id=14657)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14657&action=view)
Patch v2 to enhance cse.c
This patch also handles unsigned comparisons and thus optimizes the original
testcase too. Before:
foo:
movl 4(%esp), %edx # 2 *movsi_1/1 [length = 4]
movl 8(%esp), %eax # 3 *movsi_1/1 [length = 4]
movl %edx, %ecx # 35 *movsi_1/1 [length = 2]
subl %eax, %ecx # 7 *subsi_1/1 [length = 2]
cmpl %eax, %edx # 8 *cmpsi_1_insn/1 [length = 2]
jae .L2 # 9 *jcc_1 [length = 2]
addl $100, %ecx # 11 *addsi_1/1 [length = 3]
.L2:
movl %ecx, %eax # 18 *movsi_1/1 [length = 2]
ret # 38 return_internal [length = 1]
After:
foo:
movl 4(%esp), %eax # 2 *movsi_1/1 [length = 4]
subl 8(%esp), %eax # 8 *subsi3_cc_overflow/2 [length = 4]
jae .L2 # 9 *jcc_1 [length = 2]
addl $100, %eax # 11 *addsi_1/1 [length = 3]
.L2:
rep # 39 return_internal_long [length = 1]
ret
I was going to abandon this patch, but maybe it deserves a second chance. :-)
--
rask at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #14647|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2007-11-28 18:01 ` rask at gcc dot gnu dot org
@ 2007-11-28 22:02 ` steven at gcc dot gnu dot org
2007-11-29 0:10 ` rask at gcc dot gnu dot org
2007-11-29 11:43 ` bonzini at gnu dot org
6 siblings, 0 replies; 12+ messages in thread
From: steven at gcc dot gnu dot org @ 2007-11-28 22:02 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from steven at gcc dot gnu dot org 2007-11-28 22:02 -------
> + for (defs = DF_INSN_DEFS (insn);
> + *defs && DF_REF_REGNO (*defs) != REGNO (x);
> + defs++)
> + ;
Are you aware of df_find_def() ?
> + if (minus_elt)
> + cmp = cse_find_comparison_use (dest, insn);
Formatting.
IMNSHO, computing DEF-USE chains for this niche optimization loses in the
cost/benefit trade-off. The whole patch looks like a hack to me to
specifically deal with this particular bug report. You could, of course, show
that this is actually a very important optimization...
I wonder if you can't just integrate this optimization in cse.c as-is by
recording an equivalence "a < b" == "signof(c)" when you process "a - b".
In any case, adding this optimization to cse.c is Just Wrong (tm). I don't
understand why you didn't even try to optimize this in one of the tree
optimizers instead. I thought it was clear GCC is trying to reduce its
dependency on RTL optimizations?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
` (4 preceding siblings ...)
2007-11-28 22:02 ` steven at gcc dot gnu dot org
@ 2007-11-29 0:10 ` rask at gcc dot gnu dot org
2007-11-29 11:43 ` bonzini at gnu dot org
6 siblings, 0 replies; 12+ messages in thread
From: rask at gcc dot gnu dot org @ 2007-11-29 0:10 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from rask at gcc dot gnu dot org 2007-11-29 00:09 -------
In reply to comment #10 from Steven Bosscher 2007-11-28 22:02:
> > + for (defs = DF_INSN_DEFS (insn);
> > + *defs && DF_REF_REGNO (*defs) != REGNO (x);
> > + defs++)
> > + ;
> Are you aware of df_find_def() ?
Not until now, and it won't work either, because it uses rtx_equal_p() and
the mode of DF_REF_REG() doesn't match that of the REG rtx in the insn. See
also <URL:http://gcc.gnu.org/ml/gcc/2007-11/msg00719.html>.
> IMNSHO, computing DEF-USE chains for this niche optimization loses in the
> cost/benefit trade-off.
The split of the comparison setter and the comparison user across two
insns with no link between them is an interesting case of poor
infrastructure. Most back ends can't emit the setter before they know what
the user looks like and therefore always emit the two back-to-back. At the
same time, several passes need to find one from the other but can't rely on
them to be back-to-back and because there's no link between them (except if
by DEF-USE/USE-DEF), they have to roll their own means of doing so.
(So yes, it's been done without DEF-USE before and it can be done without
DEF-USE again.)
> I wonder if you can't just integrate this optimization in cse.c as-is by
> recording an equivalence "a < b" == "signof(c)" when you process "a - b".
That doesn't catch the unsigned comparison. Actually, how would I even
know if it is unsigned or not?
> In any case, adding this optimization to cse.c is Just Wrong (tm). I
> don't understand why you didn't even try to optimize this in one of the
> tree optimizers instead. I thought it was clear GCC is trying to reduce
> its dependency on RTL optimizations?
There's no way to optimize the signed case with -fwrapv (e.g. Java) at
the tree level, because we can't arrange for a - b to be computed in the
same instruction as a < b. At the RTL level, it is merely difficult. That
makes it less interesting to work on this optimization at the tree level.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-98@http.gcc.gnu.org/bugzilla/>
` (5 preceding siblings ...)
2007-11-29 0:10 ` rask at gcc dot gnu dot org
@ 2007-11-29 11:43 ` bonzini at gnu dot org
6 siblings, 0 replies; 12+ messages in thread
From: bonzini at gnu dot org @ 2007-11-29 11:43 UTC (permalink / raw)
To: gcc-bugs
------- Comment #12 from bonzini at gnu dot org 2007-11-29 11:43 -------
I think this should use find_comparison_args.
--
bonzini at gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |bonzini at gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-4@http.gcc.gnu.org/bugzilla/>
@ 2012-07-10 10:24 ` daniel.santos at pobox dot com
2012-07-10 10:55 ` owner at bugs dot debian.org
` (3 subsequent siblings)
4 siblings, 0 replies; 12+ messages in thread
From: daniel.santos at pobox dot com @ 2012-07-10 10:24 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
Daniel Santos <daniel.santos at pobox dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |daniel.santos at pobox dot
| |com
--- Comment #13 from Daniel Santos <daniel.santos at pobox dot com> 2012-07-10 10:23:08 UTC ---
Well here's another test case for the same problem:
extern print_gt(void);
extern print_lt(void);
extern print_eq(void);
void cmp_and_branch(long a, long b)
{
long diff = a - b;
if (diff > 0) {
print_gt();
} else if (diff < 0) {
print_lt();
} else {
print_eq();
}
}
In this case, the result of the subtraction is directly used in the branch
code. However, gcc -O2 -S still generates this output:
.file "gcc_cmp_and_branch_test2.c"
.text
.p2align 4,,15
.globl cmp_and_branch
.type cmp_and_branch, @function
cmp_and_branch:
.LFB0:
.cfi_startproc
subq %rsi, %rdi
cmpq $0, %rdi
jg .L5
jne .L6
jmp print_eq
.p2align 4,,10
.p2align 3
.L5:
jmp print_gt
.p2align 4,,10
.p2align 3
.L6:
jmp print_lt
.cfi_endproc
.LFE0:
.size cmp_and_branch, .-cmp_and_branch
.ident "GCC: (Gentoo 4.7.1) 4.7.1"
.section .note.GNU-stack,"",@progbits
I'm using Gentoo x86_64:
Using built-in specs.
COLLECT_GCC=/usr/x86_64-pc-linux-gnu/gcc-bin/4.7.1/gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-pc-linux-gnu/4.7.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /tmp/portage/sys-devel/gcc-4.7.1/work/gcc-4.7.1/configure
--prefix=/usr --bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/4.7.1
--includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.1/include
--datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.7.1
--mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.7.1/man
--infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.7.1/info
--with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.7.1/include/g++-v4
--host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --disable-altivec
--disable-fixed-point --with-ppl --with-cloog --disable-ppl-version-check
--with-cloog-include=/usr/include/cloog-ppl --enable-lto --enable-nls
--without-included-gettext --with-system-zlib --enable-obsolete
--disable-werror --enable-secureplt --enable-multilib
--with-multilib-list=m32,m64 --enable-libmudflap --disable-libssp
--enable-libgomp
--with-python-dir=/share/gcc-data/x86_64-pc-linux-gnu/4.7.1/python
--enable-checking=release --enable-java-awt=gtk --enable-objc-gc
--enable-languages=c,c++,java,objc,obj-c++,fortran --enable-shared
--enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu
--enable-targets=all --with-bugurl=http://bugs.gentoo.org/
--with-pkgversion='Gentoo 4.7.1'
Thread model: posix
gcc version 4.7.1 (Gentoo 4.7.1)
I do hope this can be addressed sometime soon. Thanks.
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-4@http.gcc.gnu.org/bugzilla/>
2012-07-10 10:24 ` daniel.santos at pobox dot com
@ 2012-07-10 10:55 ` owner at bugs dot debian.org
2020-07-22 16:51 ` josephcsible at gmail dot com
` (2 subsequent siblings)
4 siblings, 0 replies; 12+ messages in thread
From: owner at bugs dot debian.org @ 2012-07-10 10:55 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
--- Comment #14 from owner at bugs dot debian.org 2012-07-10 10:54:26 UTC ---
Thank you for the additional information you have supplied regarding
this Bug report.
This is an automatically generated reply to let you know your message
has been received.
Your message has not been forwarded to the package maintainers or
other interested parties; you should ensure that the developers are
aware of the problem you have entered into the system - preferably
quoting the Bug reference number, #75773.
If you wish to submit further information on this problem, please
send it to 75773-quiet@bugs.debian.org.
Please do not send mail to owner@bugs.debian.org unless you wish
to report a problem with the Bug-tracking system.
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-4@http.gcc.gnu.org/bugzilla/>
2012-07-10 10:24 ` daniel.santos at pobox dot com
2012-07-10 10:55 ` owner at bugs dot debian.org
@ 2020-07-22 16:51 ` josephcsible at gmail dot com
2021-06-15 6:24 ` vanyacpp at gmail dot com
2023-05-13 5:55 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 12+ messages in thread
From: josephcsible at gmail dot com @ 2020-07-22 16:51 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
Joseph C. Sible <josephcsible at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |josephcsible at gmail dot com
--- Comment #59 from Joseph C. Sible <josephcsible at gmail dot com> ---
x86_64-*-* should be added to the target list. With the original test case, GCC
10.1 produces this:
foo:
movq %rdi, %rax
subq %rsi, %rax
cmpq %rsi, %rdi
leaq 100(%rax), %rdx
cmovb %rdx, %rax
ret
It should instead produce this:
foo:
subq %rsi, %rdi
leaq 100(%rdi), %rax
cmovae %rdi, %rax
ret
By the way, I thought that using __builtin_usubl_overflow might be a useful
workaround for this bug, but it turns out that it currently isn't really, since
it has a different missed optimization of its own: bug #96289
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-4@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2020-07-22 16:51 ` josephcsible at gmail dot com
@ 2021-06-15 6:24 ` vanyacpp at gmail dot com
2023-05-13 5:55 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 12+ messages in thread
From: vanyacpp at gmail dot com @ 2021-06-15 6:24 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
Ivan Sorokin <vanyacpp at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |vanyacpp at gmail dot com
--- Comment #60 from Ivan Sorokin <vanyacpp at gmail dot com> ---
Another similar case. On this function:
unsigned wrap(unsigned index, unsigned limit)
{
if (index >= limit)
index -= limit;
return index;
}
GCC 11.1 -O2 generates:
wrap(unsigned int, unsigned int):
mov edx, edi
mov eax, edi
sub edx, esi
cmp edi, esi
cmovnb eax, edx
ret
I believe cmp here is redundant as the flags are already set after sub. After
removing cmp we get:
wrap(unsigned int, unsigned int):
mov edx, edi
mov eax, edi
sub edx, esi
cmovnb eax, edx
ret
Now the register edx becomes unneeded:
wrap(unsigned int, unsigned int):
mov eax, edi
sub edi, esi
cmovnb eax, edi
ret
^ permalink raw reply [flat|nested] 12+ messages in thread* [Bug rtl-optimization/3507] appalling optimisation with sub/cmp on multiple targets
[not found] <bug-3507-4@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2021-06-15 6:24 ` vanyacpp at gmail dot com
@ 2023-05-13 5:55 ` pinskia at gcc dot gnu.org
4 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-05-13 5:55 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507
Andrew Pinski <pinskia at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |NEW
Assignee|rask at gcc dot gnu.org |unassigned at gcc dot gnu.org
--- Comment #61 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Rask Ingemann Lambertsen has not been around working on GCC for over 10 years
so unassigning.
^ permalink raw reply [flat|nested] 12+ messages in thread