[RFC] Extension of SIMPLE for Fortran 95

[RFC] Extension of SIMPLE for Fortran 95

[S. Bosscher]

Hello,

This weekend we discussed the Fortran CYCLE (eqv. of C 'continue') and EXIT
(eqv. of 'break') statements on the G95 mailing list. In Fortran 95, you can
have:

OUTER:  DO I=...
           ...
   INNER:  DO J=...
              ...
              IF (something) THEN
                 CYCLE OUTER
              ELSE IF (something else) THEN
                 EXIT OUTER
              ENDIF
              ...
           END DO INNER
           ...
            
        END DO OUTER

We want to lower our parse tree to SIMPLE, but we can't represent this kind
of CYCLE and EXIT statements in SIMPLE.

The back end *does* provide functions for expanding break/continue from
nested loops (http://cobolforgcc.sourceforge.net/cobol_14.html#SEC138), but
it seems that only g77 uses these routines to break from an outer loop, or
to continue a nested loop.

So I would like to propose an extension to the SIMPLE grammar:
How about adding an integer argument to the 'continue' and 'break'
statements, that gives how many loops to break or continue from. 'continue'
without argument would be the "normal" continue statement, 'continue 1'
would contine the second-innermost loop, etc.

I don't think this change would require a lot of changes in the existing
code, and it would make SIMPLE a little more language independent. It would
help G95, too ;-)

Sounds OK?

Greetz
Steven

Re: [RFC] Extension of SIMPLE for Fortran 95

[Daniel Berlin]

>
> I don't think this change would require a lot of changes in the existing
> code, and it would make SIMPLE a little more language independent.

Um, how many changes would it require to break and continue elimination?
See simple-break-elim.c

>  It would
> help G95, too ;-)
>
> Sounds OK?
>
> Greetz
> Steven
>

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Mon, 10 Jun 2002, S. Bosscher wrote:

> OUTER:  DO I=...
>            ...
>    INNER:  DO J=...
>               ...
>               IF (something) THEN
>                  CYCLE OUTER
>               ELSE IF (something else) THEN
>                  EXIT OUTER
>               ENDIF
>               ...
>            END DO INNER
>            ...
>             
>         END DO OUTER
> 
> We want to lower our parse tree to SIMPLE, but we can't represent this kind
> of CYCLE and EXIT statements in SIMPLE.
> 
Maybe we shouldn't have to.  Couldn't the above be modelled with
GOTOs?  The way I'd rather handle it is to have the g95
simplifier deal with things like this.

The way to approach this is to think about converting the above
to RTL.  If you can convert to RTL, then you can convert to
SIMPLE.  You merely need to expose all the language-dependent
semantics.


Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Tom Tromey]

>>>>> "Diego" == Diego Novillo <dnovillo@redhat.com> writes:

>> We want to lower our parse tree to SIMPLE, but we can't represent this kind
>> of CYCLE and EXIT statements in SIMPLE.

Diego> Maybe we shouldn't have to.  Couldn't the above be modelled
Diego> with GOTOs?  The way I'd rather handle it is to have the g95
Diego> simplifier deal with things like this.

FWIW, Java also has this feature.  I'm curious to know why it is you'd
prefer this be handled using GOTO.  Or to put it another way, why not
handle all continue/break using GOTO?

Tom

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Mon, 2002-06-10 at 12:03, Tom Tromey wrote:
> >>>>> "Diego" == Diego Novillo <dnovillo@redhat.com> writes:
> 
> >> We want to lower our parse tree to SIMPLE, but we can't represent this kind
> >> of CYCLE and EXIT statements in SIMPLE.
> 
> Diego> Maybe we shouldn't have to.  Couldn't the above be modelled
> Diego> with GOTOs?  The way I'd rather handle it is to have the g95
> Diego> simplifier deal with things like this.
> 
> FWIW, Java also has this feature.  I'm curious to know why it is you'd
> prefer this be handled using GOTO.
> 
I want to minimize implicit behaviour.  They only create problems when
doing language-independent transformations.


> Or to put it another way, why not handle all continue/break using GOTO?
>
I can only give you one pretty weak reason: the original SIMPLE grammar
allows them.  I wouldn't mind handling them using GOTO statements.


Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Michal Moskal]

On Mon, Jun 10, 2002 at 12:20:42PM -0400, Diego Novillo wrote:
> On Mon, 2002-06-10 at 12:03, Tom Tromey wrote:
> > Or to put it another way, why not handle all continue/break using GOTO?
> >
> I can only give you one pretty weak reason: the original SIMPLE grammar
> allows them.  I wouldn't mind handling them using GOTO statements.

So remove them (break & continue). It will save you questions like:
which one is more efficient, so should I check if, in my language,
`break foobar' break inner or outer loop so I should use break or
goto?

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [RFC] Extension of SIMPLE for Fortran 95

[Daniel Berlin]

On 10 Jun 2002, Diego Novillo wrote:

> On Mon, 2002-06-10 at 12:03, Tom Tromey wrote:
> > >>>>> "Diego" == Diego Novillo <dnovillo@redhat.com> writes:
> > 
> > >> We want to lower our parse tree to SIMPLE, but we can't represent this kind
> > >> of CYCLE and EXIT statements in SIMPLE.
> > 
> > Diego> Maybe we shouldn't have to.  Couldn't the above be modelled
> > Diego> with GOTOs?  The way I'd rather handle it is to have the g95
> > Diego> simplifier deal with things like this.
> > 
> > FWIW, Java also has this feature.  I'm curious to know why it is you'd
> > prefer this be handled using GOTO.
> > 
> I want to minimize implicit behaviour.  They only create problems when
> doing language-independent transformations.
For reference, i know of two java optimizers that handle this by creating 
explicit gotos (and then they use goto elimination, but that's a side 
issue).

> 
> 
> > Or to put it another way, why not handle all continue/break using GOTO?
> >
> I can only give you one pretty weak reason: the original SIMPLE grammar
> allows them.  I wouldn't mind handling them using GOTO statements.

For a point of reference, as i showed Diego, intel's compiler transforms 
all continue/break to goto before anything gets ahold of it.
 Then again, they also transform all for loops to whiles, and then the 
whiles to if/gotos.

example:

int main(void)
{
        int i;
        for (i = 0; i < 50; i++)
        {
                continue;
        }
}

---- (proton/phase2/csi_not.c:251, List number: 1) Graph before COMPLEX_Lower_Il
0:
2       0           entry extern main_V$0  main
                    {
4       2               i_1_V$1 = 0(SI32);
4       5               while ( i_1_V$1 < 50(SI32) )
                        {
6       3                   goto L1;
8       1           L1:
4       4                   i_1_V$1 = i_1_V$1 + 1(SI32);
                        }
8       6               return ( 0(SI32) );
8       7               return ;
                    }


---- (proton/phase2/csi_not.c:259, List number: 2) Graph before Lower:
2       0           entry extern main_V$0  main
                    {
4       2               i_1_V$1 = 0(SI32);
4       5               while ( i_1_V$1 < 50(SI32) )
                        {
6       3                   goto L1;
8       1           L1:
4       4                   i_1_V$1 = i_1_V$1 + 1(SI32);
                        }
8       6               return ( 0(SI32) );
8       7               return ;
                    }


---- (proton/phase2/csi_not.c:279, List number: 3) Graph after Lower:
2       0           entry extern main_V$0  main
                    {
4       2               i_1_V$1 = 0(SI32);
4       10          L10:
4       8               if ( i_1_V$1 < 50(SI32) )
                        {
6       3                   goto L1;
8       1           L1:
4       4                   i_1_V$1 = i_1_V$1 + 1(SI32);
4       9                   goto L10;
                        }
8       6               return ( 0(SI32) );
8       7               return ;
                    }


> 
> 
> Diego.
> 
> 
> 

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Mon, 2002-06-10 at 12:34, Michal Moskal wrote:
> On Mon, Jun 10, 2002 at 12:20:42PM -0400, Diego Novillo wrote:
> > On Mon, 2002-06-10 at 12:03, Tom Tromey wrote:
> > > Or to put it another way, why not handle all continue/break using GOTO?
> > >
> > I can only give you one pretty weak reason: the original SIMPLE grammar
> > allows them.  I wouldn't mind handling them using GOTO statements.
> 
> So remove them (break & continue). It will save you questions like:
> which one is more efficient, so should I check if, in my language,
> `break foobar' break inner or outer loop so I should use break or
> goto?
> 
As usual, patches welcome.  The issue still hasn't piqued my interest
and it will be mildly annoying to change the simplifier and the
flowgraph builder.


Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Steven Bosscher]

Op ma 10-06-2002, om 18:20 schreef Diego Novillo:
> On Mon, 2002-06-10 at 12:03, Tom Tromey wrote:
---- 8< ----
> > Or to put it another way, why not handle all continue/break using GOTO?
> >
> I can only give you one pretty weak reason: the original SIMPLE grammar
> allows them.  I wouldn't mind handling them using GOTO statements.
> 
> 
> Diego.

The reason why the SIMPLE grammar has break and continue is mentioned in
many papers about the McCat compiler. To pick one of them, from "A
Goto-Elimination Method And Its Implementation For The McCat Compiler"
(Erosa, 1995, 2 citations):

"Another important point is that we have chosen to directly support
break and continue statements. Even though these statements represent a
form of control flow similar to gotos, they can be easily handled by our
structured data flow analysis 6 methods [Sri92, Ema93] Break and
continue statements do not change the controlflow of the programs
outside the scope of the closest enclosing loop structure. In this sense
the program remains compositional, the meaning of the program structure
is given by the meaning of its components."

I have to admit, though, that this may not be very relevant for GCC...

Greetz
Steven

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Mon, 2002-06-10 at 12:52, Daniel Berlin wrote:

> Then again, they also transform all for loops to whiles, and then the 
> whiles to if/gotos.
> 
This also comes up every now and again.  Coalescing loop constructs into
a single loop representation.  In principle, I would like to maintain at
least FOR_STMT to facilitate high-level loop transformations (known
bounds, controlling loop variable easy to spot).  In fact, I'd like to
have a pass to canonicalize DO_STMT and WHILE_STMT into FOR_STMTs
whenever possible.

I intend to delay these decisions until we start building loop
transformations.


Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Daniel Berlin]

On Monday, June 10, 2002, at 01:16  PM, Diego Novillo wrote:

> On Mon, 2002-06-10 at 12:52, Daniel Berlin wrote:
>
>> Then again, they also transform all for loops to whiles, and then the
>> whiles to if/gotos.
>>
> This also comes up every now and again.  Coalescing loop constructs into
> a single loop representation.  In principle, I would like to maintain at
> least FOR_STMT to facilitate high-level loop transformations (known
> bounds, controlling loop variable easy to spot).  In fact, I'd like to
> have a pass to canonicalize DO_STMT and WHILE_STMT into FOR_STMTs
> whenever possible.
I agree.
Did I mention the cuter part, that the IA-64 compiler actually rebuilds while loops from the if's/goto's about half way through optimization passes?
(The IA32 compiler doesn't).

>
> I intend to delay these decisions until we start building loop
> transformations.


>
> Diego.
>
>

Re: [RFC] Extension of SIMPLE for Fortran 95

[Tim Prince]

On Monday 10 June 2002 02:14, S. Bosscher wrote:
> Hello,
>
> This weekend we discussed the Fortran CYCLE (eqv. of C 'continue') and EXIT
> (eqv. of 'break') statements on the G95 mailing list. In Fortran 95, you
> can have:
>
> OUTER:  DO I=...
>            ...
>    INNER:  DO J=...
>               ...
>               IF (something) THEN
>                  CYCLE OUTER
>               ELSE IF (something else) THEN
>                  EXIT OUTER
>               ENDIF
>               ...
>            END DO INNER
>            ...
>
>         END DO OUTER
>
> We want to lower our parse tree to SIMPLE, but we can't represent this kind
> of CYCLE and EXIT statements in SIMPLE.
>
> The back end *does* provide functions for expanding break/continue from
> nested loops (http://cobolforgcc.sourceforge.net/cobol_14.html#SEC138), but
> it seems that only g77 uses these routines to break from an outer loop, or
> to continue a nested loop.
>
> So I would like to propose an extension to the SIMPLE grammar:
> How about adding an integer argument to the 'continue' and 'break'
> statements, that gives how many loops to break or continue from. 'continue'
> without argument would be the "normal" continue statement, 'continue 1'
> would contine the second-innermost loop, etc.
>
> I don't think this change would require a lot of changes in the existing
> code, and it would make SIMPLE a little more language independent. It would
> help G95, too ;-)
>
> Sounds OK?
>
> Greetz
> Steven
I understand the motivation for this, and it should fit in with my automatic 
pretty-formatting system, but I have doubts about adding extensions to g77 
(or g95) which aren't covered by the Fortran standard.  
-- 
Tim Prince

Re: [RFC] Extension of SIMPLE for Fortran 95

[Richard Henderson]

> On Monday 10 June 2002 02:14, S. Bosscher wrote:
> > So I would like to propose an extension to the SIMPLE grammar:
> > How about adding an integer argument to the 'continue' and 'break'
> > statements, that gives how many loops to break or continue from. 'continue'
> > without argument would be the "normal" continue statement, 'continue 1'
> > would contine the second-innermost loop, etc.

Supposing that Diego doesn't decide to remove break entirely,
I suggest not using a number, but rather have the break/continue
reference the tree node for the loop directly.


r~

Re: [RFC] Extension of SIMPLE for Fortran 95

[Jan Hubicka]

> > On Monday 10 June 2002 02:14, S. Bosscher wrote:
> > > So I would like to propose an extension to the SIMPLE grammar:
> > > How about adding an integer argument to the 'continue' and 'break'
> > > statements, that gives how many loops to break or continue from. 'continue'
> > > without argument would be the "normal" continue statement, 'continue 1'
> > > would contine the second-innermost loop, etc.
> 
> Supposing that Diego doesn't decide to remove break entirely,

Isn't this done already?  I think the simpleyfing pass already
canonicalizes loop to break/continue less forms.

Honza
> I suggest not using a number, but rather have the break/continue
> reference the tree node for the loop directly.
> 
> 
> r~

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Tue, 2002-06-11 at 06:38, Jan Hubicka wrote:
> > > On Monday 10 June 2002 02:14, S. Bosscher wrote:
> > > > So I would like to propose an extension to the SIMPLE grammar:
> > > > How about adding an integer argument to the 'continue' and 'break'
> > > > statements, that gives how many loops to break or continue from. 'continue'
> > > > without argument would be the "normal" continue statement, 'continue 1'
> > > > would contine the second-innermost loop, etc.
> > 
> > Supposing that Diego doesn't decide to remove break entirely,
> 
> Isn't this done already?  I think the simpleyfing pass already
> canonicalizes loop to break/continue less forms.
> 
No.  There are two separate passes that deal with this.  But they are
not enabled by default.


Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Jan Hubicka]

> On Tue, 2002-06-11 at 06:38, Jan Hubicka wrote:
> > > > On Monday 10 June 2002 02:14, S. Bosscher wrote:
> > > > > So I would like to propose an extension to the SIMPLE grammar:
> > > > > How about adding an integer argument to the 'continue' and 'break'
> > > > > statements, that gives how many loops to break or continue from. 'continue'
> > > > > without argument would be the "normal" continue statement, 'continue 1'
> > > > > would contine the second-innermost loop, etc.
> > > 
> > > Supposing that Diego doesn't decide to remove break entirely,
> > 
> > Isn't this done already?  I think the simpleyfing pass already
> > canonicalizes loop to break/continue less forms.
> > 
> No.  There are two separate passes that deal with this.  But they are
> not enabled by default.

What are the consequences on code size/perfomrance of enabling these
bits?  I am always running into performance problems when I implement
some idea of reugualizing CFG on RTL level...

Honza
> 
> 
> Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Tue, 2002-06-11 at 09:50, Jan Hubicka wrote:

> What are the consequences on code size/perfomrance of enabling these
> bits?  I am always running into performance problems when I implement
> some idea of reugualizing CFG on RTL level...
> 
Dunno.  I haven't done any testing on these passes.  Sebastian mentioned
code growth, but I don't know of any systematic testing.

Diego.

Re: [RFC] Extension of SIMPLE for Fortran 95

[Diego Novillo]

On Tue, 2002-06-11 at 00:10, Richard Henderson wrote:
> > On Monday 10 June 2002 02:14, S. Bosscher wrote:
> > > So I would like to propose an extension to the SIMPLE grammar:
> > > How about adding an integer argument to the 'continue' and 'break'
> > > statements, that gives how many loops to break or continue from. 'continue'
> > > without argument would be the "normal" continue statement, 'continue 1'
> > > would contine the second-innermost loop, etc.
> 
> Supposing that Diego doesn't decide to remove break entirely,
> I suggest not using a number, but rather have the break/continue
> reference the tree node for the loop directly.
> 
Well, the breaking block has the exit edge pointing to the proper exit
node.  Also, basic blocks know who their control parent is.  That should
be enough info for the analysis routines.

Continue blocks are similarly handled, they point back to their loop
parent.  There are also routines to query control parents and
continue/exit points.

Diego.

RE: [RFC] Extension of SIMPLE for Fortran 95

[S. Bosscher]

> > Supposing that Diego doesn't decide to remove break entirely,
> 
> Isn't this done already?  I think the simpleyfing pass already
> canonicalizes loop to break/continue less forms.

A goto/break elimination pass has been implemented by Sebastian Pop,
but it was still '#if 0'-ed out last time I looked.

Greetz
Steven