From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30059 invoked by alias); 7 Oct 2002 11:26:05 -0000 Mailing-List: contact gcc-prs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-prs-owner@gcc.gnu.org Received: (qmail 30044 invoked by uid 71); 7 Oct 2002 11:26:05 -0000 Date: Mon, 07 Oct 2002 04:26:00 -0000 Message-ID: <20021007112605.30043.qmail@sources.redhat.com> To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org, From: Bernd Paysan Subject: Re: optimization/8092: cross-jump triggers too often Reply-To: Bernd Paysan X-SW-Source: 2002-10/txt/msg00250.txt.bz2 List-Id: The following reply was made to PR optimization/8092; it has been noted by GNATS. From: Bernd Paysan To: Daniel Berlin Cc: anton@mips.complang.tuwien.ac.at, Anton Ertl , , , 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/