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++?


No kidding, which is the problem.

Just to be clear, i mean the fact that we have to layer things on top of
it is the problem. not the updating.
I understand exactly what you're saying. My point is that if you want to
do a non-SSA representation TODAY, that you have to deal with layering.
No you don't, you can just add your own annotations.
No layering needed.
Where did you get the idea you need to touch SSA at all to write a seperate representation?

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 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.
This has everything to do with keeping it up to date. This is the
situation as it exists today with a layered SSA reprsentation:

1. All SSA transformations are penalized by having to update both SSA form
and standard register form. This makes SSA transformations harder and
less likely to be written
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?
.
2. Alternative representations can be represented just like SSA is now,
   layered.
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
   rebuilt.
Well, not quite.
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 can
certainly add noticably to compile time. If dominator information is
also out of date then things get really slow for big codes.
5. Transformations on alternative representations can either be aware of
SSA or not. If they aren't, then they suffer the same problems as #4.
If they are, then they have to maintain and manipulate _3_ different
representations, keeping them up to date.
Not they directly necessarily, but yes, SSA needs to be kept up to date or rebuilt.

... and this is the situation with SSA built into the representation:

1. SSA transformations just update the one true representation. There is
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 layers
on top of the SSA representation. There isn't a huge difference
between this case and a register based representation.
The hardness of this step depends on how close to SSA your representation is.

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

Please do.
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 performing
optimizations on, and therefore you want to make writing these
optimizations easier. If it makes the less common case a bit harder, then
that's ok, because it's not common.
Not common *right now*.
Look how quickly SSA took over.

Sorta like profile guided
optimization I suppose, were we are optimizing initial development and
ongoing maintenance instead of execution time.

In terms of initial development time, i think i can offer some actual data:
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.

-Chris






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