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 21:46:23 -0400
- Subject: Re: [tree-ssa] AST optimizer in C++?
No you don't, you can just add your own annotations.
No kidding, which is the problem.
Just to be clear, i mean the fact that we have to layer things on top
I understand exactly what you're saying. My point is that if you want
it is the problem. not the updating.
do a non-SSA representation TODAY, that you have to deal with layering.
No layering needed.
Where did you get the idea you need to touch SSA at all to write a
How does it make it harder, given that any transformation that keeps
the SSA form up to date must necessarily be inserting the proper copies
into the "standard" form and whatnot anyway?
Changing the base representation to SSA form doesn't change this fact.
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
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
This has everything to do with keeping it up to date. This is 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
in between two SSA ones (or whatever). But it's quicker to be able to
*RUN* that pass without having to drop PHI nodes, insert copies, etc,
so that non-SSA pass doesn't get confused.
situation as it exists today with a layered SSA reprsentation:
1. All SSA transformations are penalized by having to update both SSA
and standard register form. This makes SSA transformations harder
less likely to be written
Well, not quite.
2. Alternative representations can be represented just like SSA is now,
3. Non-SSA transformations don't have to deal with SSA at all, they can
just ignore it and have it garbage collected away.
4. Non-SSA transformations cause a huge compile-time performance hit,
because they invalidate the SSA information, requiring it to be
You can incrementally update it without the non-SSA pass having to
worry about it if you really think it's that big a hit.
Or, we could run the optimizers outside the SSA ones, but with your
scheme, this adds an unssa pass. Not that this is slow, but just
"another" thing to worry about.
SSA generation isn't SLOW, but regenerating it frequently canNot they directly necessarily, but yes, SSA needs to be kept up to date
certainly add noticably to compile time. If dominator information
also out of date then things get really slow for big codes.
5. Transformations on alternative representations can either be aware
SSA or not. If they aren't, then they suffer the same problems as
If they are, then they have to maintain and manipulate _3_ different
representations, keeping them up to date.
... and this is the situation with SSA built into the representation:
1. SSA transformations just update the one true representation. There
nothing to get out of date, and they are simple to write.
I still don't see how it was hard in the first place.
2. Transformation in alternative representations are implemented as
layersThe hardness of this step depends on how close to SSA your
on top of the SSA representation. There isn't a huge difference
between this case and a register based representation.
Obviously because maintaining the representation on the side has costs,
costs that you seem to be ignoring.
If you want me to enumerate some of
them, I can.
The location of SSA information, be it in annotations, in the IR, or on
some remote computer in budapest, should not affect the cost of
implementation (IE the "hardness" that will prevent SSA opts from being
written) as long as the abstraction is good.
Maybe the cost of runtime, but even then, consider this:
Even if we made SSA the IR, we still need the annotations to generate
the factored edges, unless you are suggesting we get rid of these too
(which, I should point out, Pro64 and friends have and use).
If we get rid of those, we'd have to have nice large arrays that
multimap defs to uses, map defs to uses, etc.
Unless you want to throw those annotations *directly* in the tree
structure, which would be another fight with other people.
The whole point is that SSA is a very nice representation for
optimizations on, and therefore you want to make writing these
optimizations easier. If it makes the less common case a bit harder,
that's ok, because it's not common.
Not common *right now*.
Look how quickly SSA took over.
In terms of initial development time, i think i can offer some actual
Sorta like profile guided
optimization I suppose, were we are optimizing initial development and
ongoing maintenance instead of execution time.
I've written 1.5 of the 2 SSA optimizers on the tree-ssa branch.
You have written 0.
Is this because SSA is not the IR?
Honestly, I don't see how making SSA the IR would make me want to write
3 instead of 5, or would make it any easier.
Maybe you could work up a patch to tree-ssa-ccp or tree-ssa-pre.c that
shows how much easier it would be if we had it in the IR?
No need to actually make it *work*, i just want to see an actual
benefit in terms of what the code looks like, or how short it is, etc,
rather than all theoretical junk.
It seems to me that all it would buy us in either is that the macros
might have different names, or access different structure fields.
For all intents and purposes, except for the fact that we don't
directly represent the versions in the names (nor does Pro64), and phi
nodes don't exist in trees, SSA *is* the IR.