Re: Language-independent functions-as-trees representation

[Pop Sébastian <pop at gauvain dot u-strasbg dot fr>]

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

Agree.  

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
>    non-compound-stmt:
>      block
>      | loop-stmt
>      | if-stmt
>      | switch-stmt
>      | labeled-block-stmt
>      | jump-stmt
>      | label-stmt
>      | try-stmt
>      | modify-stmt
>      | call-stmt
>    loop-stmt:
>      LOOP_EXPR
>        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
> 'break'.
> 
>    if-stmt:
>      COND_EXPR
>        op0 -> condition
>        op1 -> stmt
>        op2 -> stmt
>    switch-stmt:
>      SWITCH_EXPR
>        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
tree...

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