Re: [tree-ssa] Out of SSA status and issues

[Daniel Berlin <dberlin at dberlin dot org>]

On Wednesday, May 14, 2003, at 02:33  PM, Diego Novillo wrote:

> On Tue, 2003-05-13 at 13:29, Jan Vroonhof wrote:
>
> > However, Not treating this as a PRE problem might have the tendency to
> > move the load towards entry and the store towards exit too much,
> > increasing register pressure and putting loads and stores in codepaths
> > that previously didn't have them. This seems to suggest leaving it to 
> > PRE.
> Exactly.  This is what we are converging to.  In my initial design, I
> had thought that by treating INDIRECT_REF nodes like regular variables
> would simplify the implementation and give us the extra benefit of 
> being
> able to do the same transformations we do to any other variable.  Boy,
> was I wrong!
>
> INDIRECT_REF nodes are like any other unary expression (OK, they have
> slightly different semantics as they can be on the LHS of an
> assignment)

This is why there is an ELEFT tree expression (in fact, specifically 
for this reason).

> , so the expression-SSA built by SSAPRE is perfect for them.
> All we need is to do is build the SSA form for expressions and let that
> framework handle them.
>
> Daniel, how clean is the separation between the expression-SSA and the
> PRE specific bits in SSAPRE?  It'd be nice if we have a clean 
> separation
> between the infrastructure proper and the various passes we want to do
> that operate on expressions.

Besides the fact that there are SSAPRE specific fields in the various 
E* structures, into-ESSA and PRE are cleanly separated.
You could stop after the call to rename_1, and you'd have ESSA 
structures available in expr_info.
We don't tack the EUSE/EDEF onto statements, for lack of any point in 
doing so for SSAPRE (we always walk them in pre-order, DT order, and 
keep pointers to all of them in an array).
The statement associated with a node is available from an E* node.
We do, however, tack ephi nodes onto BB's.

Remember also that we build ESSA for one lexical expression at a time, 
optimize the expression's occurrences, then move out of ESSA and move 
to the next lexical expression.  So if you are expecting to build ESSA 
for all expressions at once, it would
1. Be heavy on memory, most likely (in particular, the number of phi 
nodes would be high, since you have a phi node everywhere any variable  
in the expression has a phi, in addition to the IDF of the statement).
2. Probably require changes to the helper routines, but not much.

An ESSA optimization pass should probably be working one lexical 
expression at a time anyway.

The ESSA structures are factored (IE linked), but the version number is 
stored in the structures explicitly if one wants it (we use it for 
available expression determination).

Out-of-ESSA isn't really the same as out-of-SSA, because these are 
expressions, not variables, and thus they never occur on the LHS except 
for load PRE.  Out-of-ESSA is quite simple as a result.  It expects 
something else to set the save and reload flags on the EUSE's, and it 
just saves to and reloads from, temporaries, where told to.  It also 
creates phis for the ephis.


I'm not sure you can come up with an ESSA pass that is useful besides 
PRE, that runs after PRE.  Value numbering can easily be done on ESSA 
if you want (Open64 has a value numbering pass formulated using the 
SSAPRE pieces to do the work of renaming and saving). Past that, it's 
hard to come up with a useful pass.
Since load PRE is promoting pointer accesses into temporaries where 
possible/profitable, the regular SSA optimizers can take care of 
working on pointers by working on the temporaries.  Value numbering 
would take care of the constant loads/stores.
Other than that, let's see:
1.  All partially redundant expressions are eliminated
2.  Constant propagation on non-pointer expressions is the same as 
constant propagation on the variables *in* the expression.
3.  Whatever copy-prop you can do can be integrated into the 
code_motion pass (it's on my todo list).

--Dan
> Diego.