Re: optimization/8092: cross-jump triggers too often

[Bernd Paysan <bernd dot paysan at gmx dot de>]

The following reply was made to PR optimization/8092; it has been noted by GNATS.

From: Bernd Paysan <bernd.paysan@gmx.de>
To: Daniel Berlin <dberlin@dberlin.org>
Cc: anton@mips.complang.tuwien.ac.at,
        Anton Ertl <anton@a0.complang.tuwien.ac.at>, <rth@gcc.gnu.org>,
        <gcc-bugs@gcc.gnu.org>, <gcc-gnats@gcc.gnu.org>
Subject: Re: optimization/8092: cross-jump triggers too often
Date: Mon, 7 Oct 2002 13:25:22 +0200

 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 benchm=
 ark=20
 results that this is a pessimation - it's not just that I'm just "thinkin=
 g"=20
 that it's wrong. The code forms a threaded interpreter, and each basic=20
 block has to be considered as an "instruction" of that interpreter. Movin=
 g=20
 code from one instruction to all others makes each instruction more=20
 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 improve=
 d
 > the code (in terms of number of calculations).
 
 Ah, no. The expression in one control flow branch might not live at all.=20
 There's just a chance that it gets computed. By copying the expression to=
 =20
 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 m=
 ust=20
 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 don=
 e=20
 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=20
 "lazy code motion" are tremendous. Primitives that have 3 instructions gr=
 ow=20
 to 50 or more. This increases code size and execution time by a huge amou=
 nt=20
 (ok, cross-jump reduces the size, but the execution time increases even=20
 further). Sometimes, the real world differs from assumptions in papers ;-=
 ).
 
 --=20
 Bernd Paysan
 "If you want it done right, you have to do it yourself"
 http://www.jwdt.com/~paysan/