Re: [tree-ssa-branch] simplify builtins

[Daniel Berlin <dberlin at dberlin dot org>]

On Sat, 29 Jun 2002, Aldy Hernandez wrote:

> On Sat, Jun 29, 2002 at 03:55:39PM -0400, Diego Novillo wrote:
> > On Sat, 29 Jun 2002, Aldy Hernandez wrote:
> > 
> > > what's the slowness factor in the compiler now?
> > > 
> > Bootstrap times are roughly 2x.  Yes, it's disgraceful.
> 
> have you benchmarked this to find out where most of the time is being
> spent?
> 
> is it in the simplification or in the ssa building?  or both?
> 
> are we running ssa on the simplified trees only?  are we doing the
> ssa-on-rtl thing as well?
> 
> *puts speculation hat on*
> 
> hmmmm, this seems like something worth looking into.  i doubt anyone's
> going to be too inclined to use these optimizations if there's a 2X
> slowdown.

Most of the slowdown comes from RTL expansion of the extra trees, 
actually, i've already profiled it some.

This is largely because we have no simple copy/constant propagation to 
get rid of even completely useless copies.

It probably actually makes sense to run quick copy prop before SSA 
creation so we don't waste memory on references, and time on SSA building, 
of things we will remove really quickly anyway.
> 
> perhaps when we start disabling rtl optimizers and replacing them with
> simple-tree optimizers we can see an increase in speed?  or at least
> a decrease that's not as bad :)
> 
> now that we have everything simpliable for C, perhaps we can implement
> one entire optimization pass (constant propagation or PRE ?

Um, SSAPRE is already implemented, and working well from an algorithmic 
standpoint.
But there are not-easy-to-solve problems in tree sharing that cause it 
to screw up when replacing expressions.
In particular, it can't tell what part of the expression it needs to start copying from when doing 
replacements.  Nothing right now gives us that information.  So if you 
have a situation where we have an expression like:


NOP_EXPR
	PLUS_EXPR
		5
		a
and the NOP_EXPR is shared with something else, when we go to replace 
PLUS_EXPR (5, a), we've accidently screwed that something else.  But we 
only know that the "a" belongs to the PLUS_EXPR (it's all the SSA 
references tell us). We have no idea that the NOP_EXPR is shared.
Easy to solve, right?
Now think what happens if you just blindly copy from the statement 
(guaranteed to be not-shared) on down, and happen to have a pointer to an 
expression somewhere *else* in that statement. No longer the right 
pointer to be modifying.

But there is nothing SSAPRE itself can do about this, it's an 
implementation thing that should be handled in the expression replacement 
functions SSAPRE calls (replace_expr_in_tree).

So SSAPRE works great, replacement sometimes f*cks us.  Thus, you can't 
bootstrap with it on, because we run into these complex  statements that 
are shared.

However, i've run it on plenty of test cases, and real applications 
(though i've sometimes had to help it along), and it works great.

You run into the same problem with copy propagation, of course.
I've already got SSA copy propagation going and working, and as soon as 
replacing during sharing is handled, i'll submit it.

> on trees and disable the rtl counterparts.  that should give us an idea
> of how bad things are going to look ;-).
> 
> aldy
> 
>