This is the mail archive of the
mailing list for the GCC project.
Re: [tree-ssa] AST optimizer in C++?
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: Chris Lattner <sabre at nondot dot org>
- Cc: Diego Novillo <dnovillo at redhat dot com>,Pop Sébastian <pop at gauvain dot u-strasbg dot fr>,<gcc at gcc dot gnu dot org>
- Date: Mon, 26 Aug 2002 20:40:18 -0400 (EDT)
- Subject: Re: [tree-ssa] AST optimizer in C++?
- Reply-to: dberlin at dberlin dot org
On Mon, 26 Aug 2002, Chris Lattner wrote:
> On Sun, 25 Aug 2002, Daniel Berlin wrote:
> > > Is there a reason that you'd like to have a SIMPLE form that is not in
> > > SSA?
> > Um, yes.
> > It artificially limits us to that representation.
> > Say later, someone wants to use some other form of SSA, or non-SSA
> > (dependence flow graph, etc).
> > If you make it actually part of the trees, they now have to care about
> > it.
> > If it's just annotations, only what wants to look at those annotations
> > look at it.
> Actually, that's not true at all. Using SSA as the base representation is
> just like using a conventional register based underlying representation:
> you can still layer other representations ON TOP of SSA, you just need to
> keep the SSA up-to-date as you transform the layered representation (just
> as you must do with the register based representation).
No kidding, which is the problem.
> In practice, there are several simple extensions to SSA that are
> representable as direct extensions to the representation [eta nodes, pi
> nodes from the ABCE paper, etc], which don't require a layered
> representation. Other representations are really major extensions of SSA
> which are enhanced by having SSA as the base representation.
Not necessarily true at all.
But i'm also not saying SSA is a bad base, i just don't think we need to
make it the *actual* IR.
> Of course, I'm sure there are others I'm not familiar with, but worst
> case, you just have to keep the base representation up to date with the
> layered representation, which is nothing different than the current
> situation with SSA.
This has nothing to do with keeping it up to date. It has to do with the
fact that other things would need to know about PHI nodes, etc.
We can easily just rebuild the SSA form if we want to run a non-SSA pass
in between two SSA ones (or whatever). But it's quicker to be able to just
*RUN* that pass without having to drop PHI nodes, insert copies, etc, just
so that non-SSA pass doesn't get confused.
> The key difference with using SSA as the base representation, however, is
> that almost ALL transformations benefit from it. SSA will probably be the
> _most_ commonly used representation when the tree-ssa branch is finally
> mature (hence the name), beating out the register based representation by
> a lot. I'm not really sure when and if other representations would
> actually be useful, and if their usefulness is worth the cost of creating
> and maintaining the representation: whether layered on top of registers or
DFG, PDG, etc are generally worth the cost of creating.
> > Plus, there are optimization passes that might not be run on SSA (some
> > loop optimizations).
> Loop optimizations generally work wonderfully on SSA form. The PHI nodes
> encapsulates a lot of the information you need directly in the code, which
> is _quite_ convenient.
> > Once again, forcing SSA on the representation itself means they have to
> > care about it (or you've limited when they can be run), while annotations
> > have no such limitations.
> Sure, of course. If, however, they don't understand the annotations, they
> will be corrupted by the pass. This means that you have to destroy and
> regenerate the SSA annotations.
The other option is to not be able to run the pass at all.
Why limit ourselves by making sure we can't run that other pass, when we
get no actual *benefit* from doing so?
> This is greatly expensive, which means
> that the transformation will be updated to use SSA anyway (often making it
> more efficient). While forcing SSA from the start makes it harder to
> transfer legacy code,
It's not necessarily legacy code.
All the world is not SSA.
Even if it was, it may not stay that way forever.
> simplifies the code. Again, I can show many examples of simplified
> 3. Destroying and regenerating SSA information is quite expensive when
> it's unneccesary. Keeping track of whether or not SSA is created is
> also painful, hurting modularity.
> > There is no good reason to actually make it part of the form, other than
> > having to insert copies yourself. But all algorithms i've seen that are
> > written to keep SSA form up to date do this anyway, or make it easy to do.
> I'm not sure if I understand what you're saying here... it seems as though
> you are contradicting yourself by saying that SSA _is_ easy to keep
> up-to-date (which I believe it is, of course :) What am I
You keep missing the actual point.
1. There is no benefit to putting SSA in the trees, as opposed to
2. There is a cost to putting SSA in the trees, regardless of whether
you feel the things that aren't SSA, are worth squat.
Thus, given this, *why* do it?
What does it buy us?
That's what i want to know.