[Bug optimization/8092] cross-jump triggers too often

[Bug optimization/8092] cross-jump triggers too often

[pinskia@physics.uc.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=8092


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |anton@mips.complang.tuwien.a
                   |                            |c.at


------- Additional Comments From pinskia@physics.uc.edu  2003-06-01 23:01 -------
*** Bug 7953 has been marked as a duplicate of this bug. ***



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug optimization/8092] cross-jump triggers too often

[pinskia@physics.uc.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=8092



------- Additional Comments From pinskia@physics.uc.edu  2003-06-01 23:05 -------
*** Bug 3436 has been marked as a duplicate of this bug. ***



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[dhazeghi at yahoo dot com]

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

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


dhazeghi at yahoo dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ice-on-valid-code
   Last reconfirmed|2003-05-28 19:22:56         |2003-07-10 01:20:49
               date|                            |
            Summary|cross-jump triggers too     |[3.3/3.4 regression] cross-
                   |often                       |jump triggers too often
   Target Milestone|---                         |3.3.2


------- Additional Comments From dhazeghi at yahoo dot com  2003-07-10 01:20 -------
Should have been marked as a regression from 2.95.3. Stills ICEs with 
mainline today.

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[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=8092


pinskia at physics dot uc dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|ice-on-valid-code           |


------- Additional Comments From pinskia at physics dot uc dot edu  2003-07-10 01:33 -------
The ICE on valid code is in 11001 which this already depends on.

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[mmitchel 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=8092


mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.3.2                       |3.4


------- Additional Comments From mmitchel at gcc dot gnu dot org  2003-10-16 02:38 -------
Postponed until GCC 3.4.

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[bernd dot paysan at gmx dot de]

------- Additional Comments From bernd dot paysan at gmx dot de  2003-12-26 21:11 -------
The "too often" triggered crossjumping has partly been resolved with the 
-fno-crossjumping option. However, this doesn't include computed gotos, GCC 
still produces (from 3.3 on) crossjumps to computed gotos. Looking closer at 
the code, this is intentional. The following patch fixes the problem when you 
don't want crossjumping by not emitting a central dispatcher for computed 
gotos. A central dispatcher is *bad*, because the branch predictor can not make 
up any correlation between jump location and jump target. 
 
--- gcc-3.4-20031217/gcc/stmt.c.orig	2003-12-05 12:11:05.000000000 +0100 
+++ gcc-3.4-20031217/gcc/stmt.c	2003-12-26 21:54:32.000000000 +0100 
@@ -523,7 +523,15 @@ 
  
   emit_queue (); 
  
-  if (! cfun->computed_goto_common_label) 
+  if (!flag_crossjumping) 
+    { 
+      emit_queue (); 
+      do_pending_stack_adjust (); 
+      emit_indirect_jump (x); 
+       
+      current_function_has_computed_jump = 1; 
+    } 
+  else if (! cfun->computed_goto_common_label) 
     { 
       cfun->computed_goto_common_reg = copy_to_mode_reg (Pmode, x); 
       cfun->computed_goto_common_label = gen_label_rtx (); 
 

-- 


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

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[rth at redhat dot com]

------- Additional Comments From rth at redhat dot com  2003-12-27 05:02 -------
Subject: Re:  [3.3/3.4 regression] cross-jump triggers too often

On Fri, Dec 26, 2003 at 09:11:55PM -0000, bernd dot paysan at gmx dot de wrote:
> A central dispatcher is *bad*, because the branch predictor can not make 
> up any correlation between jump location and jump target. 

No, this causes unacceptable compile-time problems.  Did you not
see the bits in bb-reorder that undo this?  Are they not working
for some reason?


r~


-- 


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

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[bernd dot paysan at gmx dot de]

------- Additional Comments From bernd dot paysan at gmx dot de  2003-12-27 20:43 -------
Subject: Re:  [3.3/3.4 regression] cross-jump triggers too often

Hi rth at redhat dot com,

On Saturday 27 December 2003 06:02, you wrote:
> ------- Additional Comments From rth at redhat dot com  2003-12-27 05:02
> ------- Subject: Re:  [3.3/3.4 regression] cross-jump triggers too often
>
> On Fri, Dec 26, 2003 at 09:11:55PM -0000, bernd dot paysan at gmx dot de 
wrote:
> > A central dispatcher is *bad*, because the branch predictor can not make
> > up any correlation between jump location and jump target.
>
> No, this causes unacceptable compile-time problems.  Did you not
> see the bits in bb-reorder that undo this?  Are they not working
> for some reason?

They are not working when you do -fno-reorder-blocks, since that skips the 
phase completely. This is the current status of the problem here: 
-fno-crossjumping and -fno-reorder-blocks together leaves the central 
dispatcher in place.

BTW: The cleanup stuff in bb-reorder.c is after the instruction combining 
stuff, so the computed goto doesn't get combined with previous instructions, 
though it could be combined. Example: You want to jump through a pointer, 
goto **pointer. This ends up (on x86) as

mov (%reg1),%reg2
jmp %reg2

instead of doing

jmp (%reg1)



-- 


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

[Bug optimization/8092] [3.3/3.4 regression] cross-jump triggers too often

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-04 08:59 -------
pessimizes-code is not branch blocking.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal


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

[Bug optimization/8092] [3.3/3.4/3.5 regression] cross-jump triggers too often

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-01-25 02:00 -------
Actually what is happening here is that abnormal edges are put into their own basic 
block which is done on purpose to speed up the compiler's DCE and DOM, I do not think 
this was not done on acident, it was done as part of a design of the pass which causes 
this.  I think this will be fixed on the tree-ssa though iff Steven B.'s DCE goes in.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |minor


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

[Bug optimization/8092] [3.3/3.4/3.5 regression] cross-jump triggers too often

[mmitchel at gcc dot gnu dot org]

------- Additional Comments From mmitchel at gcc dot gnu dot org  2004-03-21 18:07 -------
I'm going to close this PR.

AFAICT, the complaint is that when using computed gotos with -fno-reorder-blocks
and -fno-crossjumping, we generate inferior code (i.e., code that uses a
crossjump).  However, the current behavior is due to the fact that we've made
changes that make the compiler run efficiently when compiling big functions with
computed gotos.  Furthermore, with -freorder-blocks, the problem goes away.

If there's a problem here, then, it is that the submitter cannot use
-freorder-blocks.  If that's the case, let's have a new PR explaining that.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


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

[Bug optimization/8092] [3.3/3.4/3.5 regression] cross-jump triggers too often

[bernd dot paysan at gmx dot de]

------- Additional Comments From bernd dot paysan at gmx dot de  2004-03-24 15:09 -------
Subject: Re:  [3.3/3.4/3.5 regression] cross-jump triggers too often

On Sunday 21 March 2004 19:07, mmitchel at gcc dot gnu dot org wrote:
> ------- Additional Comments From mmitchel at gcc dot gnu dot org 
> 2004-03-21 18:07 ------- I'm going to close this PR.
>
> AFAICT, the complaint is that when using computed gotos with
> -fno-reorder-blocks and -fno-crossjumping, we generate inferior code
> (i.e., code that uses a crossjump).  However, the current behavior is due
> to the fact that we've made changes that make the compiler run
> efficiently when compiling big functions with computed gotos. 
> Furthermore, with -freorder-blocks, the problem goes away.
>
> If there's a problem here, then, it is that the submitter cannot use
> -freorder-blocks.  If that's the case, let's have a new PR explaining
> that.

Ok, let me explain what we do: We generate code for a VM with GCC. We use 
the computed goto to dispatch the next VM instruction. However, we also 
"abuse" GCC to generate blocks for a just in time compiler. In this mode, 
we just strip the computed goto instruction from the block (i.e. what is 
between two consecutive labels). We can cope mostly with -freorder-blocks, 
since we can sort the labels by address. This is what we do now. 
Unfortunately, not all VM instructions are a single basic block, because 
some contain conditional code (like branch or loop instructions). These 
instructions may be reordered (e.g. GCC finds out that the part before the 
conditional jump is different, but the part afterwards is the same in all 
cases, and merge that part). We detect this reordering, so our VM code 
won't fail. But it will run slower. GCC 2.95.3 is still the GCC which 
compiles the fastest code.

I agree that the optimization does improve compile time, especially for our 
case. The main issue here is that we deliberately told GCC to do something 
(don't create crossjumps, don't reorder), and it didn't. I can live with a 
higher compile time when GCC does what it is told to. These switches are 
not the default, so only applications that need both (not reorder blocks 
and no crossjumping) would suffer from the increased compile time (which is 
significant). So a solution would be to disable the optimization when both 
-fno-reorder-blocks and -fno-crossjumping is selected (this is easy to 
implement; I can send you a few-lines patch which does exactly that).

However, there is a tradeoff of the optimization you do, anyway. Normally, 
GCC can combine loads and jumps, e.g. in our case, it's (on x86)

mov -4(%reg1), %reg2
jmp %reg2

which becomes

jmp -4(%reg1)

without the compile time optimization. One register less used, one 
instruction less. This combination doesn't work with -freorder-block, since 
the reordering happens late in the compile step, and no further peephole 
optimization is made at that phase (also, the registers are already 
allocated, so freeing %reg2 at that stage wouldn't allow to allocate it for 
other purposes).

My humble comment to this optimization: This is a kludge. What you want is 
to reduce the control flow graph by introducing a central dispatcher (the 
crossjumped computed goto). This collapses the high fan-in-fan-out of each 
labeled block (where the label address is taken as value) with computed 
goto as exit into one block with a high fan-out (the dispatcher), and many 
blocks with high fan-ins (labeled blocks).

Another solution could be to treat computed gotos as equal during control 
flow evaluation. I.e. instead of computing a control flow graph edge for 
each of them, reuse the first computed (all computed goto edges are 
identical, anyway). You can't do much with such an edge, anyway. You can't 
move things beyond the computed goto (because of the high fan-out), and you 
can't move something before the label (high fan-in) - or at least, it's 
very unlikely that you'll find something worth to move around (and ATM, GCC 
lacks the necessary stuff to do software pipelining here, like modulo 
register allocation and things like that).

This is quite likely more work than the current solution ;-).



-- 


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

[Bug optimization/8092] [3.3/3.4/3.5 regression] cross-jump triggers too often

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-04-02 00:36 -------
*** Bug 14816 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mj_ at gazeta dot pl


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