Re: Language-independent functions-as-trees representation

[Jason Merrill <jason at redhat dot com>]

On Sat, 27 Jul 2002 08:56:47 +0200, Pop Sebastian <pop@gauvain.u-strasbg.fr> wrote:

> On Tue, Jul 23, 2002 at 06:13:51PM +0100, Jason Merrill wrote:

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

Yep, that's the idea.

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

Yes.

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

Certainly.  But then, I wonder, why bother reducing it in the first place?

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

That would make sense, but I still wonder which form is more appropriate
for SIMPLE.  The flat representation requires less knowledge of loop
structure from other passes, but requires more intelligence from the loop
optimizer; if we want to rotate the loop, which we basically always do, we
would need to re-derive the loop structure, at least the
prologue/precondition bits.

Hmm.  This structured form still isn't expressive enough to handle C++
loops with condition declarations, as the cleanup for the condition
variable needs to wrap the body and epilogue.  So we would need to flatten
such loops anyway.  So perhaps it makes sense to do that for all SIMPLE
loops.

Jason