public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c/39284] New: Computed gotos combined too aggressively
@ 2009-02-23 22:42 jyasskin at gmail dot com
2009-02-23 22:44 ` [Bug c/39284] " jyasskin at gmail dot com
` (10 more replies)
0 siblings, 11 replies; 12+ messages in thread
From: jyasskin at gmail dot com @ 2009-02-23 22:42 UTC (permalink / raw)
To: gcc-bugs
The following uses a file "ceval.i" that I'll upload shortly and a nightly
build of gcc-4.4.0-20090223. The file is a version of Python's core
interpretation loop modified to use computed gotos in order to help the
processor's branch predictor do a better job than with a switch statement.
However, gcc combines the computed gotos into only a few instructions,
producing a result nearly as bad as the switch.
The computed gotos are all of the form "goto *next_label;". About half of the
instances counted are reachable, as measured by the asm volatile farther down.
$ grep -c -F 'goto *next_label' ceval.i
256
I compile with -fno-gcse because
http://gcc.gnu.org/onlinedocs/gcc-4.3.3/gcc/Optimize-Options.html#index-fgcse-646
says it helps and with "--param max-goto-duplication-insns=100000" because
Diego Novillo suggested tweaking that parameter.
$ gcc-4.4 -m32 -pthread -fno-strict-aliasing -g -fwrapv -O3 -Wall
-Wstrict-prototypes -fno-gcse --param max-goto-duplication-insns=100000 -S -dA
ceval.i -o ceval.s
$ egrep -c 'jmp[[:space:]]*\*' ceval.s
4
I tried to make the common instruction sequence leading up to the indirection
jump shorter by putting an asm volatile before it, but that didn't work. You
can see the result by running:
$ sed 's!goto \*next_label!asm volatile ("/* Computed goto */":::"memory");goto
*next_label!' < ceval.i > ceval-asm.i
$ gcc-4.4 -m32 -pthread -fno-strict-aliasing -g -fwrapv -O3 -fno-gcse --param
max-goto-duplication-insns=100000 -S -dA ceval-asm.i -o ceval-asm.s
$ egrep -c 'Computed goto' ceval-asm.s
130
$ egrep -c 'jmp[[:space:]]*\*' ceval-asm.s
4
One of the relevant bits of assembly (search for "Computed goto" in
ceval-asm.s) is:
.L1125:
# basic block 66
.LBE835:
# ../src/Python/ceval.c:1000
.loc 1 1000 0
jmp *-72(%ebp)
.LVL558:
.p2align 4,,7
.p2align 3
.L1433:
# basic block 67
...
# basic block 114
#APP
# 11 "../src/Include/ceval-vm.i" 1
/* Computed goto */
# 0 "" 2
#NO_APP
movl %esi, %ebx
.LVL599:
.p2align 4,,7
.p2align 3
.L484:
# basic block 115
# ../src/Python/ceval.c:1000
.loc 1 1000 0
movl $1, %eax
.LVL600:
movl %ebx, %esi
.LVL601:
jmp .L1125
The documentation for max-goto-duplication-insns says:
The maximum number of instructions to duplicate to a block that jumps to a
computed goto. To avoid O(N^2) behavior in a number of passes, GCC factors
computed gotos early in the compilation process, and unfactors them as late as
possible. Only computed jumps at the end of a basic blocks with no more than
max-goto-duplication-insns are unfactored. The default value is 8.
Since .L1125 and basic block 66 have only a single instruction, the computed
goto should have been unfactored.
$ gcc-4.4 -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: /home/dnovillo/perf/sbox/gcc/local.x86_64/src/configure
--prefix=/home/dnovillo/perf/sbox/gcc/local.x86_64/inst
--srcdir=/home/dnovillo/perf/sbox/gcc/local.x86_64/src
--with-gmp=/home/dnovillo/i686 --with-mpfr=/home/dnovillo/i686
--build=i686-pc-linux-gnu --enable-languages=c++,fortran,objc,obj-c++
Thread model: posix
gcc version 4.4.0 20090223 (experimental) (GCC)
--
Summary: Computed gotos combined too aggressively
Product: gcc
Version: 4.4.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: jyasskin at gmail dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
@ 2009-02-23 22:44 ` jyasskin at gmail dot com
2009-02-23 22:46 ` [Bug middle-end/39284] " pinskia at gcc dot gnu dot org
` (9 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: jyasskin at gmail dot com @ 2009-02-23 22:44 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from jyasskin at gmail dot com 2009-02-23 22:44 -------
Created an attachment (id=17354)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=17354&action=view)
ceval.i
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
2009-02-23 22:44 ` [Bug c/39284] " jyasskin at gmail dot com
@ 2009-02-23 22:46 ` pinskia at gcc dot gnu dot org
2009-02-23 22:49 ` pinskia at gcc dot gnu dot org
` (8 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2009-02-23 22:46 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from pinskia at gcc dot gnu dot org 2009-02-23 22:46 -------
This is by design; GCSE is the one which pulls back the computed gotos IIRC.
--
pinskia at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Component|c |middle-end
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
2009-02-23 22:44 ` [Bug c/39284] " jyasskin at gmail dot com
2009-02-23 22:46 ` [Bug middle-end/39284] " pinskia at gcc dot gnu dot org
@ 2009-02-23 22:49 ` pinskia at gcc dot gnu dot org
2009-02-23 22:58 ` jyasskin at gmail dot com
` (7 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2009-02-23 22:49 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from pinskia at gcc dot gnu dot org 2009-02-23 22:48 -------
It says may but not will get better performance.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (2 preceding siblings ...)
2009-02-23 22:49 ` pinskia at gcc dot gnu dot org
@ 2009-02-23 22:58 ` jyasskin at gmail dot com
2009-02-23 23:19 ` steven at gcc dot gnu dot org
` (6 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: jyasskin at gmail dot com @ 2009-02-23 22:58 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from jyasskin at gmail dot com 2009-02-23 22:58 -------
Taking out -fno-gcse doesn't change the result.
$ gcc-4.4 -m32 -pthread -fno-strict-aliasing -g -fwrapv -O3 --param
max-goto-duplication-insns=100000 -S -dA ceval.i -o ceval.s
$ egrep -c 'jmp[[:space:]]*\*' ceval.s
4
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (3 preceding siblings ...)
2009-02-23 22:58 ` jyasskin at gmail dot com
@ 2009-02-23 23:19 ` steven at gcc dot gnu dot org
2009-02-24 10:17 ` rguenth at gcc dot gnu dot org
` (5 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: steven at gcc dot gnu dot org @ 2009-02-23 23:19 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from steven at gcc dot gnu dot org 2009-02-23 23:19 -------
Should unfactor. We have pass_duplicate_computed_gotos for this. We should
look into this, see why it doesn't work.
Someone added a "optimize_for_size_p()" check in duplicate_computed_gotos().
That is just *stupid*. If there should be a check like that, it should be per
function, not per basic block. I bet that's the cause.
--
steven at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2009-02-23 23:19:12
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (4 preceding siblings ...)
2009-02-23 23:19 ` steven at gcc dot gnu dot org
@ 2009-02-24 10:17 ` rguenth at gcc dot gnu dot org
2009-02-24 15:26 ` jyasskin at gmail dot com
` (4 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2009-02-24 10:17 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from rguenth at gcc dot gnu dot org 2009-02-24 10:17 -------
rguenther@murzim:/tmp> gcc-4.4 -m32 -fno-strict-aliasing -fwrapv -O3 --param
max-goto-duplication-insns=100000 -S ceval.i
rguenther@murzim:/tmp> egrep -c 'jmp[[:space:]]*\*' ceval.s
4
rguenther@murzim:/tmp> gcc-4.3 -m32 -fno-strict-aliasing -fwrapv -O3 --param
max-goto-duplication-insns=100000 -S ceval.i
rguenther@murzim:/tmp> egrep -c 'jmp[[:space:]]*\*' ceval.s
5
rguenther@murzim:/tmp> gcc-4.2 -m32 -fno-strict-aliasing -fwrapv -O3 --param
max-goto-duplication-insns=100000 -S ceval.i
rguenther@murzim:/tmp> egrep -c 'jmp[[:space:]]*\*' ceval.s
5
rguenther@murzim:/tmp> gcc-4.1 -m32 -fno-strict-aliasing -fwrapv -O3 --param
max-goto-duplication-insns=100000 -S ceval.i
rguenther@murzim:/tmp> egrep -c 'jmp[[:space:]]*\*' ceval.s
19
How many gotos do you expect?
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |hubicka at gcc dot gnu dot
| |org
Keywords| |missed-optimization
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (5 preceding siblings ...)
2009-02-24 10:17 ` rguenth at gcc dot gnu dot org
@ 2009-02-24 15:26 ` jyasskin at gmail dot com
2009-06-08 20:56 ` hubicka at gcc dot gnu dot org
` (3 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: jyasskin at gmail dot com @ 2009-02-24 15:26 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from jyasskin at gmail dot com 2009-02-24 15:26 -------
I'd like to get gcc not to combine any of them, which I believe would produce
130, as many as the asm volatiles that survived optimization.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (6 preceding siblings ...)
2009-02-24 15:26 ` jyasskin at gmail dot com
@ 2009-06-08 20:56 ` hubicka at gcc dot gnu dot org
2009-06-08 22:43 ` steven at gcc dot gnu dot org
` (2 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2009-06-08 20:56 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from hubicka at gcc dot gnu dot org 2009-06-08 20:55 -------
Hmm,
the conditional is bogus, there should not be !
but still after patching this we don't duplicate. The reason is that the BB 71
(containing conditional jump) is reached via 2 BBs containing memory load. I
guess it is result of crossjumping.
I will send patch fixing the conditional, but it makes little difference.
Honza
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (7 preceding siblings ...)
2009-06-08 20:56 ` hubicka at gcc dot gnu dot org
@ 2009-06-08 22:43 ` steven at gcc dot gnu dot org
2009-06-08 22:46 ` steven at gcc dot gnu dot org
2009-06-09 15:19 ` hubicka at gcc dot gnu dot org
10 siblings, 0 replies; 12+ messages in thread
From: steven at gcc dot gnu dot org @ 2009-06-08 22:43 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from steven at gcc dot gnu dot org 2009-06-08 22:43 -------
There shouldn't be a "!". Just make use optimize_function_for_speed_p(cfun).
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (8 preceding siblings ...)
2009-06-08 22:43 ` steven at gcc dot gnu dot org
@ 2009-06-08 22:46 ` steven at gcc dot gnu dot org
2009-06-09 15:19 ` hubicka at gcc dot gnu dot org
10 siblings, 0 replies; 12+ messages in thread
From: steven at gcc dot gnu dot org @ 2009-06-08 22:46 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from steven at gcc dot gnu dot org 2009-06-08 22:45 -------
Honza, what do the basic blocks 2 and 71 look like for you, exactly? I see no
memory load. But I have local crossjumping patches -- as you know ;-) -- so I
am probably not looking at the same dumps as you are.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug middle-end/39284] Computed gotos combined too aggressively
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
` (9 preceding siblings ...)
2009-06-08 22:46 ` steven at gcc dot gnu dot org
@ 2009-06-09 15:19 ` hubicka at gcc dot gnu dot org
10 siblings, 0 replies; 12+ messages in thread
From: hubicka at gcc dot gnu dot org @ 2009-06-09 15:19 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from hubicka at gcc dot gnu dot org 2009-06-09 15:18 -------
Hmm, it is not exactly load. In first case I get:
(code_label 12524 16482 12523 70 1249 "" [4 uses])
(note 12523 12524 149 70 [bb 70] NOTE_INSN_BASIC_BLOCK)
(insn:TI 149 12523 13690 70 ../src/Include/ceval-vm.i:47 (set (mem/c:SI
(plus:SI (reg/f:SI 6 bp)
(const_int -64 [0xffffffffffffffc0])) [72 %sfp+-40 S4 A32])
(const_int 1 [0x1])) 47 {*movsi_1} (expr_list:REG_EQUAL (const_int 1
[0x1])
(nil)))
(insn 13690 149 1351 70 (set (reg/v:SI 0 ax [orig:155 why ] [155])
(const_int 1 [0x1])) 47 {*movsi_1} (nil))
(code_label 1351 13690 1352 71 382 "" [0 uses])
(note 1352 1351 1353 71 [bb 71] NOTE_INSN_BASIC_BLOCK)
(jump_insn:TI 1353 1352 1354 71 ../src/Python/ceval.c:1000 (set (pc)
(mem/c:SI (plus:SI (reg/f:SI 6 bp)
(const_int -60 [0xffffffffffffffc4])) [72 %sfp+-36 S4 A32]))
640 {*indirect_jump} (nil))
(barrier 1354 1353 1477)
So there are 4 edges reaching WHY set. In the second case it is move of WHY to
1:
(code_label 1363 1365 1349 150 384 "" [127 uses])
(note 1349 1363 1350 150 [bb 150] NOTE_INSN_BASIC_BLOCK)
(insn:TI 1350 1349 19980 150 ../src/Python/ceval.c:1000 (set (reg/v:SI 0 ax
[orig:155 why ] [155])
(const_int 1 [0x1])) 47 {*movsi_1} (nil))
(note 19980 1350 19979 151 [bb 151] NOTE_INSN_BASIC_BLOCK)
(jump_insn 19979 19980 19982 151 ../src/Python/ceval.c:1000 (set (pc)
(mem/c:SI (plus:SI (reg/f:SI 6 bp)
(const_int -60 [0xffffffffffffffc4])) [72 %sfp+-36 S4 A32]))
640 {*indirect_jump} (nil))
(barrier 19982 19979 1373)
that prevents duplicating. Probably ordirnary bb-reorder should be convincable
to handle this well?
This don't seem to happen at 64bit compilation.
I also posted the patch fixing optimize_for_size check
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39284
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2009-06-09 15:19 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-02-23 22:42 [Bug c/39284] New: Computed gotos combined too aggressively jyasskin at gmail dot com
2009-02-23 22:44 ` [Bug c/39284] " jyasskin at gmail dot com
2009-02-23 22:46 ` [Bug middle-end/39284] " pinskia at gcc dot gnu dot org
2009-02-23 22:49 ` pinskia at gcc dot gnu dot org
2009-02-23 22:58 ` jyasskin at gmail dot com
2009-02-23 23:19 ` steven at gcc dot gnu dot org
2009-02-24 10:17 ` rguenth at gcc dot gnu dot org
2009-02-24 15:26 ` jyasskin at gmail dot com
2009-06-08 20:56 ` hubicka at gcc dot gnu dot org
2009-06-08 22:43 ` steven at gcc dot gnu dot org
2009-06-08 22:46 ` steven at gcc dot gnu dot org
2009-06-09 15:19 ` hubicka at gcc dot gnu dot org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).