This is the mail archive of the
mailing list for the GCC project.
Re: [tree-ssa] AST optimizer in C++?
- From: Chris Lattner <sabre at nondot dot org>
- To: Daniel Berlin <dberlin at dberlin 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: Tue, 27 Aug 2002 11:30:00 -0500 (CDT)
- Subject: Re: [tree-ssa] AST optimizer in C++?
On Mon, 26 Aug 2002, Daniel Berlin wrote:
> >> 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?
I'm sorry, I mis-typed. I meant that if you want to do a non-register
based representation today, you have to deal with layering. When I say
layering, I mean a layer of annotations on the side that basically exist
over the top of a base representation.
If SSA was your base representation and you wanted a PDG, f.e., you could
have the annotations on the side of SSA just like you would a register
based representation. Sorry for the confusion! :)
> > 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?
I'm not sure what you mean by "inserting copies". If SSA is the base
representation there is absolutely no need for a copy instruction (LLVM
doesn't have one, for example). If SSA is layered on top of a register
based representation (with annotations), of course then you have to insert
copies into the register based representation, but that's only one of the
ways you have to modify it to keep it up to date...
Could you please explain a bit what you mean by this? Sorry if I'm
missing something obvious. :)
> > 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.
I'm not sure what you mean by this. You still have to regenerate the SSA
annotations after transformations on the alternative representation if you
don't update the SSA. If you do update the SSA, that's case #5 below.
> 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.
Or, in your scheme, the SSA representation would effectively get garbage
collected away, and regenerated later, which is basically as expensive as
running unssa anyway. Unssa is a quite fast and simple transformation
when you don't have to worry about RTL level issues.
> > 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.
So my point was that _if_ SSA is the primary representation [ie, used by
most transformations], then it make sense to make it the base
representation as well.
> > ... 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.
It is not _hard_ persay, see the end of the email.
> > 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.
Certainly, just as the hardness of layering on top of a register based
representation depends on how close you are to a register based rep. I
think that you would agree that "new" representations tend to be more
about encoding flow and dependance information into the representation
than they do about modeling explicit registers, along with all four
> > 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:
Here are some of the costs that I can think of:
1. Actively working on (updating, traversing) two seperate representations
at the same time implies that you have less effectively cache
capacity available to you. This includes L1, L2, TLB, and all of the
other problems people are tackling.
2. Because you _must_ add extra layers of abstraction on top of things to
make it easy to update the SSA information, your icache is less
effective. In addition, the code is harder to understand because there
is more abstraction involved.
3. Some things you cannot abstract out, for example, generalized updates
the the representation.
4. Having two representations active at the same time means that potential
contributors have to be aware and understand the rules and semantics of
BOTH of them. In this case, it means that they have to know how and
when to update the base representation and what exactly the abstraction
functions are doing.
5. Speaking from experience, having the representation in SSA form only
makes it much easier to manipulate instruction nodes, understand the
lifetime of the underlying representation, and therefore have simple
rules for when and how memory can be leaked. This is something that
GCC has lacked for a long time (not just in the optimizer), which is
what makes the garbage collector effectively neccesary.
6. Having a layered representation makes it much less convenient to define
you intermediate representation as a _language_ in it's own right which
gives you all kinds of nice advantages.
Note that this all depends on having a top-notch abstraction interface.
If you don't have a good abstraction interface, then there really is no
> 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.
I'm sorry, I'm not familiar with the term "factored edges". What are they
> > 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.
Sure, because SSA makes a lot of sense for a lot of optimizations. You
still haven't given me any examples about optimizations that are difficult
to write in SSA, f.e. Most of the other representations are tuned to a
particular class of problem, making them less generally useful. I would
argue that _this_ is why SSA caught on so fast.
> > 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
> I've written 1.5 of the 2 SSA optimizers on the tree-ssa branch.
> You have written 0.
True, but I have written ~30 SSA optimizers in LLVM, plus many "analyses"
as well (dominators, natural loops, intervals, alias analysis, data
structure analysis, etc). I do have some experience, and I do have some
idea what I'm talking about. The fact that LLVM didn't exist at all two
years ago is a testament to how fast it has been progressing.
> Is this because SSA is not the IR?
This is for several reasons:
1. There is a huge learning curve to working on GCC
2. There is [basically] no documentation on the tree-ssa branch
3. I'm not paid to work on GCC, and all my free time is taken working on
That said, I _would_ like to be able to work on GCC, contributing
enhancements here and there. I _am_ somewhat familiar with other parts of
GCC, just because of the backend work I have done to get LLVM coming out
of GCC. If the infrastructure was more mature and inviting, I would be
contributing. A good start would be porting over some of the
transformations from LLVM.
> 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.
I understand your viewpoint. The fact is, however, that you are an expert
in GCC and an expert in the SSA representation used. For people who
aren't, having two representations to deal with is painful and hard to
deal with. This makes it less likely that you will get _external_
contributions, which I'd argue is what free software is all about.
> 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.
I'm having a hard time getting access to those files. subversion.gcc.org
doesn't seem to like displaying branches in viewcvs, and those files don't
show up here:
> 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.
I'm not arguing that SSA isn't the IR. :) I'm arguing that because it's
not the BASE IR that there are some disadvantages, that's all...