Re: Eliminate break/continue statements in loops

On Monday 07 Dec 2009 12:32, Roland LeiCa wrote:
> I know that irreducible CFGs can be transformed to reducible ones by
> node splitting. So I don't have to worry about cross edges if I
> implement that. But my question is whether there has been done some
> research to eliminate continue and break statements out of loops so an
> equivalent program results which does only make use of simple loops.


I have done some work on this, but it has not been published
(except as source code: see below).


The WSL language includes loops with multiple EXITs, where an EXIT(n)
statement terminates the n enclosing nested loops. So this is the same
as a multi-level break statement. Note that the "n" in EXIT(n) must be
a positive integer: not a variable or an expression.


A continue statement can be implemented using EXITs by doubling the loop
if necessary. For instance:


DO ...
      continue
      ... OD


becomes:


DO DO ...
            EXIT(1)
            ... OD OD


where all the original EXIT(n) statements in the loop are incremented
to EXIT(n+1), to ensure that they terminate the same number of enclosing
nested loops.


In the FermaT transformation system, WSL is compiled into Scheme
which in turn is compiled into C using the Hobbit Scheme compiler.
The hobbit compiler generally produces very efficient C code,
but does not compile call-with-current-continuation efficiently
(and this is used to implement loops with EXIT statements).


So the transformation Floop_To_While is applied before compiling
to transform all Floops (loops with EXITs) to equivalent WHILE loops:
possibly using a flag variable if necessary.


Note that in the worst case, this transformation (as with node splitting
in general) can lead to an exponential growth in the size of the program.


The FermaT source code is available here:


http://www.cse.dmu.ac.uk/~mward/fermat.html
http://www.gkc.org.uk/fermat.html


--
Martin


STRL Senior Research Fellow and Royal Society Industry Fellow
martin@gkc.org.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4
Mirrors: http://www.gkc.org.uk and http://www.gkc.org.uk/gkc

Return to the comp.compilers page.
Search the comp.compilers archives again.