Re: Higher level RTL issues

[Daniel Berlin <dan@cgsoftware.com>]

On Tuesday, October 9, 2001, at 10:48  PM, law@redhat.com wrote:

>
> I know folks have heard me mention the idea of a higher level RTL from
> time to time.  I must apologize for not posting this earlier -- oh well,
> life goes on.  I must also apologize as this isn't 100% complete, but
> given that I haven't posted anything about it already and the fact that
> I'm going on vacation tomorrow, I figured I'd at least get this info out
> and let folks chew on it while I'm gone.
>
> I don't think there's any significant disagreement that a higher level
> IL would be useful.
>  What is a subject of debate is whether we have
> a lower tree form, higher RTL form or some other form.  I think if we
> look at the set of problems we want to solve we can get a good feel for
> which of the 3 choices makes the most sense.
>
>
> I'm looking at the new IL as a way to enable an SSA optimization path.
Okey dokey.

>  On
> that optimization path I'm initially looking at the following 
> optimizations:
>
> 	* Sparse conditional constant propagation (ssa-ccp.c)
>
> 	* Traditional dead code elimination (ssa-dce.c)
>
> 	* Aggressive dead code elimination (ssa-dce.c)
>
> 	* Register coalescing and renaming (ssa.c)
>
> 	* Dominator based value numbering (will eventually be in ssa.c)
>
> Certainly there will be more optimizations in the future, but I think 
> this
> set gives us a good idea of the kinds of optimization problems I want to
> solve.
I don't think that these are representative of the type of problems we 
*should* be looking to solve.
These are pretty basic ssa optimizations, not something to look at when 
determining the type of IL you need.
If we only use these as the things to base requirements on, you'll never 
get much improvement in performance.
At least, as they exist now.
Why?
Because the main optimizations needed right now relate to memory and 
loops.
You can perform very interesting loop and memory optimizations in SSA 
form.
However, having simply a higher level RTL would not help them 
significantly (>5%, i'd guesstimate), unless you tackle the issues of 
array indices and memory.
So to not take this into account at all when designing an IR better for 
SSA (whether it be a higher level RTL or whatever), would be a shame.

>
> Let's first consider Tree SSA work Diego's doing vs our existing SSA
> translator.  The SSA naming discipline in Diego's work is merely a
> conceptual model -- we do not actually rewrite the tree structures to
> conform to SSA naming rules.  The nice thing about this model is you
> don't actually have to convert the IL into and out of SSA form.
>
> That model works fine for a class of optimization problems, but breaks 
> down
> with any optimization which potentially has two SSA names for the same
> variable live at the same point in the program.
>
>
Sorry, this isn't correrct.
Factored use-def chains are more powerful than traditional SSA form, 
it's an extended variant of SSA, because it can handle backwards 
problems as well.
To get the equivalent, you'd need to take traditional SSA form,and give 
unique names to uses as well.
Anything you can do in traditional SSA, you can do with fud chains. You 
can link defs->uses just as well as you can link the uses->defs.
It's absolutely trivial.
The point of FUD is to allow not doing phyiscal renaming (saving 
memory), and to give use-def chains as well, without the cost of the 
renaming, so you can solve backwards dataflow problems, as demand driven 
optimizations often require.
I.E. It allows you to do things like demand-driven constant propagation.
http://www.acm.org/pubs/articles/proceedings/sac/326619/p400-stoltz/p400-stoltz .
pdf

In short, use  def-use chains rather than use-def chains (we aren't 
currently creating them in tree-ssa, but this can be rectified very 
easily, i've already done it for SSA loop optimizations), and your 
problem is solved.

>   GVN and dominator based
> value numbering can create situations where we have two SSA names live 
> at
> the same time.
>  It's probably true that other interesting optimizations
> could create similar situations.  I believe this argues that either the
> tree SSA needs to do rewriting or that tree SSA is not suitable for the
> class of optimizations I'm trying to implement.
>
I believe you are incorrect on both counts.
It's trivial to extend the tree SSA to do what you want, and it 
*shouldn't* do rewriting
>
> jeff