optimization/8092: cross-jump triggers too often

[Bernd Paysan]

On Monday 07 October 2002 00:19, Daniel Berlin wrote:
> In your case, all blocks have abnormal edges to all other blocks. This
> requires it to end up inserting everywhere because all blocks lead
> to all other blocks.
> It's still optimal, given this CFG.
> You just "know" more than the compiler, so you think it's wrong.

I agree that I know more than the compiler. However, I can provide benchmark 
results that this is a pessimation - it's not just that I'm just "thinking" 
that it's wrong. The code forms a threaded interpreter, and each basic 
block has to be considered as an "instruction" of that interpreter. Moving 
code from one instruction to all others makes each instruction more 
expensive, except the one the instruction is moved out from.

> Because it's lifetime optimal, so it can't possibly have made the
> expression live longer than it used to, and thus, it has always improved
> the code (in terms of number of calculations).

Ah, no. The expression in one control flow branch might not live at all. 
There's just a chance that it gets computed. By copying the expression to 
all other branches, it will be computed. Always.

> Not necessarily. You assume the code is completely straight line.
> GCSE should never make an expression be calculated *more times* than it
> used to be (probably some corner case i'm forgetting about).
> That's the whole point.
> GCSE makes the number of calculations along a given path optimal in
> number, not in cost.

Since it increases the number of calculations along another path, there must 
be something wrong.

The example I gave had pathes like that

          /- return calc---\
          |- calc sterr----|
          |- calc stdout---|
goto *ip -|- calc stdin----|-reiterate
          |- calc 12-------|
          |- calc 123------|
          \- calc 1234-----/

And it becomes

          /- return calc-------------------------\
          |- calc sterr, stdout, stdin-----------|
          |- calc sterr, stdout, stdin-----------|
goto *ip -|- calc sterr, stdout, stdin-----------|-\
     ^    |- calc sterr, stdout, stdin, 12-------| |
     |    |- calc sterr, stdout, stdin, 123------| |
     |    \- calc sterr, stdout, stdin, 1234-----/ /
     \____________________________________________/

Now you tell me that this doesn't increase the number of calculations done 
in a path. I can't follow you here.

> Cost optimal code motion often makes the lifetime of an expression way
> too long.
>
> I suggest you read papers on Lazy Code Motion, and cost optimal code
> motion.

I suggest doing some benchmarks. E.g. with Gforth. The slowdown by doing the 
"lazy code motion" are tremendous. Primitives that have 3 instructions grow 
to 50 or more. This increases code size and execution time by a huge amount 
(ok, cross-jump reduces the size, but the execution time increases even 
further). Sometimes, the real world differs from assumptions in papers ;-).

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/