Eliminate break/continue statements in loops

[Roland Leißa]

Hi,

I am currently working on a optimization algorithm. So far it works on
simple programs with a linear control flow, if-else-constructs, simple
while loops and simple do-while loops. The constructs may be nested.
With a simple loop I mean a loop which does not make use of continue,
break or even goto.

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.

Thanks in advance,
Roland Lei_a

[Martin Ward]

On Monday 07 Dec 2009 12:32, Roland LeiC a 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
mar...@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

[scoot...@gmail.com]

It's standard practice to invert the condition and jump to the loop
exit code to "eliminate breaks and continues.