[Bug optimization/11781] New: superfluous jumps generated

[Bug optimization/11781] New: superfluous jumps generated

[anton at mips dot complang dot tuwien dot ac dot at]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781

           Summary: superfluous jumps generated
           Product: gcc
           Version: 3.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: anton at mips dot complang dot tuwien dot ac dot at
                CC: bernd dot paysan at gmx dot de,gcc-bugs at gcc dot gnu
                    dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu

The preprocessed source code for demonstrating this issue is at

http://www.complang.tuwien.ac.at/anton/tmp/engine-fast.i

(where has the upload button on this form gone?)

When compiled with

gcc  -I./../arch/386 -I. -Wall -O2 -fomit-frame-pointer -fforce-addr -fforce-mem
-march=pentium -DHAVE_CONFIG_H
-DDEFAULTPATH=\".:/usr/local/lib/gforth/site-forth:/usr/local/share/gforth/site-forth:/usr/local/lib/gforth/0.6.1:/usr/local/share/gforth/0.6.1\"
-fno-gcse -fno-strict-aliasing -fno-crossjumping -fno-defer-pop -fcaller-saves
-fno-inline -o engine-fast.s -S ./engine-fast.i

from this source code (reformatted for slightly improved readability):

I_question_branch:
{
  Cell * a_target;
  Bool f;
  ;
  ((a_target)=(Cell *)(((*(ip)))));
  ((f)=(Bool)(spTOS));
  ({ ip+=(1);});
  sp += 1;
  {
    if (f==0) {
      ({ip=((Xt *)a_target); ;});
      ;
      (ip++);
      spTOS = sp[0];
      ({asm("":"=X"(cfa)); goto **(ip-1);});
    }
    ;
  }
  ;
  (ip++);
  spTOS = sp[0];
  K_question_branch:
  asm("#" "question_branch");
  ({asm("":"=X"(cfa)); goto **(ip-1);});
}

gcc produces the following assembly code:

...
	.long	.L347
...
	jmp	*%edx
.L347:
#APP
	#question_branch
#NO_APP
	movl	-4(%ebp), %edx
	jmp	*%edx
...
.L26:
	movl	636(%esp), %edx
	movl	(%ebp), %eax
	addl	$4, %edi
	addl	$4, %ebp
	testl	%edx, %edx
	jne	.L979
	leal	4(%eax), %ebp
	movl	(%edi), %eax
	movl	%eax, 636(%esp)
	movl	-4(%ebp), %edx
	jmp	*%edx
.L666:
...
.L979:
	movl	(%edi), %edx
	addl	$4, %ebp
	movl	%edx, 636(%esp)
	jmp	.L347
...

This fragment includes all occurences of .L347.  The "jmp .L347" could
be easily avoided by just appending the block starting at .L347 to the
block starting at .L979.  In the source code this code is consecutive,
so the jump must have been introduced by optimization.

If you try to reproduce this with another gcc version, search for
"#question_branch" to find the appropriate label for ".L347".

As an aside: It would be very helpful for Gforth and other
interpreters using dynamic superinstructions (aka selective inlining,
PLDI'98 p. 291), and for systems like Tempo (a partial
evaluator/run-time specializer for C), if the basic blocks would stay
in source order where possible (i.e., in the example above: .L26,
.L979, .L347, and only then something else).  These systems work by
copying code between two labels (as-values) at run-time; if the code
is not consecutive, these systems will not work; in Gforth we have a
fall-back but more ambitious approaches like Tempo may be confined to
using gcc-2.x unless you give them a way to control the order of the
machine code.

[Bug optimization/11781] superfluous jumps generated

[anton at mips dot complang dot tuwien dot ac dot at]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781



------- Additional Comments From anton at mips dot complang dot tuwien dot ac dot at  2003-08-03 09:49 -------
Created an attachment (id=4553)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=4553&action=view)
test case

[Bug optimization/11781] superfluous jumps generated

[falk at debian dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781



------- Additional Comments From falk at debian dot org  2003-08-03 11:59 -------
About the aside: does -fno-reorder-blocks not work? It seems to work for the
qemu project. It might also be worthwhile to try how -fno-reorder-blocks
affects the spurious jump.

[Bug optimization/11781] superfluous jumps generated

[pinskia at physics dot uc dot edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781


pinskia at physics dot uc dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


------- Additional Comments From pinskia at physics dot uc dot edu  2003-08-03 14:35 -------
Can you try the mainline of gcc where the basic block reordering has been rewritten and now it 
produces:
.L972:  
        movl    (%edi), %eax
        addl    $4, %ebp
        movl    %eax, 636(%esp)
.L340:
#APP
        #question_branch
#NO_APP 
        movl    -4(%ebp), %eax
        jmp     *%eax

Which looks correct.

[Bug optimization/11781] superfluous jumps generated

[anton at a0 dot complang dot tuwien dot ac dot at]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781



------- Additional Comments From anton at a0 dot complang dot tuwien dot ac dot at  2003-08-03 14:44 -------
Subject: Re:  superfluous jumps generated

falk at debian dot org wrote:
> About the aside: does -fno-reorder-blocks not work? It seems to work for the
> qemu project. It might also be worthwhile to try how -fno-reorder-blocks
> affects the spurious jump.

Thanks for the pointer, I had missed that.

Unfortunately, -fno-reorder-blocks seems to break -fno-crossjumping:

.L1215:
	jmp	*%edx
...
.L979:
	movl	(%edi), %edx
	addl	$4, %ebp
	movl	%edx, 636(%esp)
.L347:
#APP
	#question_branch
#NO_APP
	movl	-4(%ebp), %edx
	jmp	.L1215

[Bug optimization/11781] superfluous jumps generated

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781



------- Additional Comments From pinskia at gcc dot gnu dot org  2003-08-12 21:29 -------
Can you try the mainline (this question might have got missed after Falk asked his 
question) or a 3.4 snapshot?

[Bug optimization/11781] superfluous jumps generated

[anton at a0 dot complang dot tuwien dot ac dot at]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781



------- Additional Comments From anton at a0 dot complang dot tuwien dot ac dot at  2003-08-13 14:07 -------
Subject: Re:  superfluous jumps generated

pinskia at gcc dot gnu dot org wrote:
> Can you try the mainline (this question might have got missed after Falk asked his 
> question) or a 3.4 snapshot?

Ok, I have tried it with the snapshot gcc-3.4-20030806, and this
totally superfluous jump goes away.

I have also tried adding -fno-reorder-blocks, resulting in the command
line

/usr/local/src/gcc-3.4-20030806-build/gcc/xgcc -B /usr/local/src/gcc-3.4-20030806-build/gcc/ -I./../arch/386 -I. -Wall -O2 -fomit-frame-pointer -fforce-addr -fforce-mem -march=pentium -DHAVE_CONFIG_H -DDEFAULTPATH=\".:/usr/local/lib/gforth/site-forth:/usr/local/share/gforth/site-forth:/usr/local/lib/gforth/0.6.1:/usr/local/share/gforth/0.6.1\" -fno-gcse -fno-strict-aliasing -fno-crossjumping -fno-defer-pop -fcaller-saves -fno-inline -fno-reorder-blocks -o engine-fast.s -S ./engine-fast.i

As a result, gcc performs some pretty dumb cross-jumping again
(despite -fno-crossjumping):

.L1205:
	jmp	*%eax
...
.L661:
.L20:
	movl	636(%esp), %esi
	movl	(%ebp), %edx
	movl	4(%ebp), %eax
	addl	$4, %edi
	addl	$8, %ebp
	testl	%esi, %esi
	jne	.L973
	movl	644(%esp), %ebx
	leal	4(%edx), %ebp
	addl	%eax, %ebx
	movl	%ebx, 644(%esp)
	movl	(%edi), %edx
	movl	%edx, 636(%esp)
	movl	-4(%ebp), %eax
	jmp	.L1205
.L973:
	movl	(%edi), %ecx
	addl	$4, %ebp
	movl	%ecx, 636(%esp)
.L341:
#APP
	#question_branch_lp_plus_store_number
#NO_APP
	movl	-4(%ebp), %eax
	jmp	.L1205
.L662:

Note that the code at .L1205 is shorter than the jumps to .L1205.

This is essentially the same problem that was reported in PR 7953 and
PR 8092.  Should I create a new bug report?

- anton

[Bug optimization/11781] superfluous jumps generated

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11781


pinskia at gcc dot gnu dot org changed:

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


------- Additional Comments From pinskia at gcc dot gnu dot org  2003-08-13 14:11 -------
Closing as the problem reported in this bug is fixed in the mainline and the real problem behind 
this bug is already located in PR 8092.