This is the mail archive of the
mailing list for the GCC project.
Re: Higher level RTL issues
- To: law at redhat dot com
- Subject: Re: Higher level RTL issues
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Wed, 10 Oct 2001 00:18:04 -0400
- Cc: gcc at gcc dot gnu dot org
On Tuesday, October 9, 2001, at 10:48 PM, firstname.lastname@example.org 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.
> that optimization path I'm initially looking at the following
> * 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
> set gives us a good idea of the kinds of optimization problems I want to
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.
Because the main optimizations needed right now relate to memory and
You can perform very interesting loop and memory optimizations in SSA
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
> 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.
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
> 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