Re: optimization/5738: GCSE missed optimization

[Daniel Berlin <dan at dberlin dot org>]

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

From: Daniel Berlin <dan@dberlin.org>
To: rth@gcc.gnu.org, <dann@godzilla.ics.uci.edu>, <gcc-bugs@gcc.gnu.org>,
   <gcc-prs@gcc.gnu.org>, <nobody@gcc.gnu.org>, <gcc-gnats@gcc.gnu.org>
Cc:  
Subject: Re: optimization/5738: GCSE missed optimization
Date: Wed, 3 Apr 2002 08:26:44 -0500 (EST)

 On Wed, 3 Apr 2002, Daniel Berlin wrote:
 
 > On 3 Apr 2002 rth@gcc.gnu.org wrote:
 > 
 > > Synopsis: GCSE missed optimization
 > > 
 > > State-Changed-From-To: open->closed
 > > State-Changed-By: rth
 > > State-Changed-When: Wed Apr  3 02:25:09 2002
 > > State-Changed-Why:
 > >     That's not how partial redundancy elimination (PRE) works.
 > >     The object with PRE is to minimize the number of evaluations
 > >     of an expression *along a path*. 
 > 
 > No, the main object of PRE (besides performing GCSE) is to suppress 
 > partial redundancies. 
 > IE expressions that are available along one or more paths, but missing from some path.
 > It does so by making it fully redundant, copying it to a block (or 
 > blocks) such that it reaches all of the paths.  It then eliminates the 
 > other copies.
 
 See, for instance http://www.cs.rice.edu/~keith/512/Lectures/LCM.pdf, 
 which explains this quite well in the first few pages.
  > 
 > 
 > >  There is already one
 > >     evaluation along each path, thus PRE considers things
 > >     optimal.
 > 
 > No it won't.
 > The expression is not in the earliest place possible, and is fully 
 > redundant.
 > It *should* copy it to the predecessor, and eliminate the other two 
 > copies.
 
 And for the record, I verified this by running the code through two other 
 compilers PRE passes.
 Both remove it.
 
 > 
 > >     
 > >     You want global value numbering or something, which we 
 > >     don't implement.
 > GVN wouldn't help here, actually.
 > GVN doesn't insert new copies, it only eliminates values that are really 
 > still available from some other block.
 
 I.E. if the code was
 
 a;
 if (b)
 {
 	a;
 	c;
 }
 else
 {
 	a;
 	d;
 }
 
 GVN would remove the a's inside the if block.
 
 Here, we have no value available yet.
 
 we have something like
 
 if (b)
 {
 	a;
 	c;
 }
 else
 {
 	a;
 	d;
 }
 
 which is a job for PRE.
 
 It should first notice a is locally available in both blocks.
 Global availability will tell a is available in all the blocks 
 afterwards.
 Transparency will say a is transparent everywhere.
 
 Computing antic will say a is anticipable everywhere (edgewise) 
 because of the transparency.
 
 Earliestness will say a could be placed anywhere as well.
 As will latest.
 
 So in this case,  it will eliminate both copies, and place a copy in the 
 successor of the if.
 
 if (b)
 {
 	c;
 }
 else
 {
 	d;
 }
 a;
 
 
 This is, of course, the placement when neither c, nor d, change or need 
 the value of a.
 
 It's still fully redundant in the example Dan gave, it just needs to be 
 placed earlier.
 
 > 
 > 
 > Please don't close this PR, it's correct.
 > --Dan
 > 
 >