Re: Language-independent functions-as-trees representation

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

On Tue, Jul 23, 2002 at 06:13:51PM +0100, Jason Merrill wrote:
> Well, I basically see two options.
> 
> 1) Leave for and do-while loops in their natural structure, and wait for
>    the loop optimizer to decompose them completely.  Or,
> 
> 2) Lower all C loops at simplification time into infinite loops, so that
> 
>   for (init; cond; incr)
>     {
>       body1
>         continue;
>       body2
>     }
> 
> would turn into something like
> 
>   init
>   while (true)
>     {
>       if (! cond)
>         break;
>       {
>         body1
>           goto cont;
>         body2
>       }
>      cont:
>       incr
>     }
> 
> ...where the goto could be expressed by something like an EXIT_BLOCK_EXPR;
> would that be easier to deal with in optimizers?
> 

Solution 2 will flatten all loop structures to a unique loop structure
without any distinction.  I think that in combination with an induction 
variable detector we can promote an infinite loop to a higher loop structure
(fortran's DO loop).  If these higher level loops can only be produced by 
the analyzer, then the loop nest optimizer could concentrate only on these
higher forms of loops and discard all others loops.

I think that the goal of the simplifier is to lower expressions and statements
to a normal form for reducing the number of allowed forms for the same concept
(reducing syntactic sugar :-) ).  This normal form reduces analyzer's 
complexity.  Analyzers promote expressions and statements to a higher level 
that contains more intrinsic information destined to optimizers.

> If we stay with option 1, the way to avoid the duplication problem is to
> let the condition and increment fields contain an arbitrary block of code,
> not just an expression.
> 
> I suppose my question is which approach is really simpler.  In one of the
> earlier threads rth referred to FOR_INIT_STMT as a useless abstraction,
> suggesting that the only useful forms were the infinite loop and the
> FORTRAN-like do-loop, with a strong induction variable.  On the other hand,
> we currently denote the condition and continue blocks in the RTL, so it
> might make sense to do so in the trees as well.
> 
> Of course, the jump-elimination pass needs something like a while loop; an
> infinite loop won't do, since to get out you need break, which is a jump...
> 

We could promote an infinite loop to a conditional loop after jump-elimination.

> Stepping back, the chunks of a C loop are:
> 
>  Code run before the first iteration (for-init-stmt), not really part of
>    the loop
> Top of loop
>  Code run before each iteration (anything in a for or while condition
>    before the actual test)
>  A conditional exit (in a for or while)
>  The body
> Continue point
>  Code run after each iteration (the for increment expression, anything in a
>    do-while condition before the actual test)
>  A conditional exit (in a do-while)
>  Jump to top
> 
> So a generic LOOP_STMT/LOOP_EXPR would have LOOP_EXPR_PROLOGUE (arbitrary
> code), LOOP_EXPR_PRECONDITION (condexpr), LOOP_EXPR_BODY (arbitrary code),
> LOOP_EXPR_EPILOGUE (arbitrary code), LOOP_EXPR_POSTCONDITION (condexpr).
> This seems like a useful form; what do others think?
> 

These EXPRs/STMTs could be good candidates for a GENERIC loop?