This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [tree-ssa] AST optimizer in C++?


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).

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.

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.

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
SSA.

> 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.  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, I think this is actually a good thing for a couple
of reasons:

1. The code should be rewritten anyway, because the IR is different, there
   are different tradeoffs, and different cases to handle.
2. Writing a transformation taking advantage of SSA often _greatly_
   simplifies the code.  Again, I can show many examples of simplified
   transformations.
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
misinterpreting?

-Chris

http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]