This is the mail archive of the
mailing list for the GCC project.
Re: Language-independent functions-as-trees representation
- From: Pop Sébastian <pop at gauvain dot u-strasbg dot fr>
- To: Jason Merrill <jason at redhat dot com>
- Cc: gcc at gcc dot gnu dot org
- Date: Fri, 23 Aug 2002 17:21:58 +0200
- Subject: Re: Language-independent functions-as-trees representation
- References: <email@example.com> <firstname.lastname@example.org>
On Fri, Aug 23, 2002 at 01:41:28PM +0100, Jason Merrill wrote:
> It seems to me that these fundamental design questions need to be
> straightened out now, before we build anything more on top of the current
> IR, or we're just digging ourselves a deeper hole. As long as we're
> building something new, we should take the time to do it right. Do others
But we have to try to implement some trivial optimisations in order
to see what tools we'll need further. As a trivial example I see the
double-chaining without which goto-elimination is much harder to implement.
Another example is the problem on which I stopped to develop an improvement
for the switch to binary search : I just needed a vector of CASE_LABELs
on which I need a simple fast sorting based on the value of the CASE_LABEL.
vector<tree> then a simple std::sort (), or even better: vector<case_label> :-)
I can imagine how hard it will be to implement all the loop nest
optimizations _without_ the support of a high level programming language.
But that's another story...
> Basically, I'm wondering if other people are interested enough in this
> change to 1) help with the design for the IR and 2) help with porting the
> existing tree optimizers to the new IR.
I'm ready for giving of my free time for both tasks :-)
> It seems to me that double-chaining could be provided by using the
> TREE_CHAIN of the COMPOUND_EXPRs.
Hmm, interesting, I never thought to this solution.
I have another solution:
since we'll need this double chaining only in the optimizer,
and if we decide to write this optimizer in C++,
then we could use a map<stmt, stmt> for keeping the information
about previous statements.
This could be a solution for keeping SSA information as well ...
> stmt: compound-stmt | non-compound-stmt
> | loop-stmt
> | if-stmt
> | switch-stmt
> | labeled-block-stmt
> | jump-stmt
> | label-stmt
> | try-stmt
> | modify-stmt
> | call-stmt
> LOOP_EXPR_BODY -> stmt | NULL_TREE
> | DO_LOOP_EXPR
> (to be defined later)
> The Java loop has 1 (or 0) EXIT_EXPR, used to express the loop condition.
> This makes it easy to distinguish from 'break's, which are expressed
> with EXIT_BLOCK_EXPR.
> EXIT_EXPR is a bit backwards for this purpose, as its sense is opposite to
> that of the loop condition, so we end up calling invert_truthvalue twice in
> the process of generating and expanding it. But that's not a big deal.
> From an optimization perspective, are LABELED_BLOCK_EXPR/EXIT_BLOCK_EXPR
> easier to deal with than plain gotos? I assume they're preferable to the
> current loosely bound BREAK_STMT, which has no information about what it's
> exiting. EXIT_EXPR would have the same problem if it were used to express
> op0 -> condition
> op1 -> stmt
> op2 -> stmt
> op0 -> val
> op1 -> stmt
> The McCAT SIMPLE requires the simplifier to make case labels disjoint by
> copying shared code around, allowing a more structured representation of a
> switch. I think this is too dubious an optimization to be performed by
> default, but might be interesting as part of a goto-elimination pass;
Agree. This would just copy too much code. I think this optimization
should take also some arbitrary bounds (ie. no more than 20 cases, and
no more than k copied statements). Otherwise we could end with a huge
> I've attached my current patch below; it's still in the toy stages, but
> gives an idea of my implementation strategy.
I'll take a look.