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

["bernd dot paysan at gmx dot de" <gcc-bugzilla at gcc dot gnu dot org>]

------- 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