This is the mail archive of the 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: Language-independent functions-as-trees representation

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?  


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

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