Re: test at top ==> test at bottom

Max Hailperin <max@nic.gac.edu> writes:
>While working my way through the literature on certain forms of loop
>optimization, it occurred to me that I haven't seen much in the literature
>on transformations that will turn test-at-the-top loops into
>test-at-the-bottom loops. Yet unless you've done so, you can't safely
>assume the loop will be done at least once.


I haven't ever seen much besides 1-liners saying "just do it." Depending
on the source language, there may be several approaches. It's possible to
get the front end to generate the desired code for DO loops and WHILE
loops (DO - WHILEs or REPEAT - UNTILs are already fine). For example,
instead of translating


a
WHILE p DO b END
c


into


a
L1: if (!p) goto L2
b
goto L1
L2: c


we'd prefer to see


a
if (!p) goto L2
L1: b
if (p) goto L1
L2: c


which (as Hailperin points out) allows much more optimization. If you've
got a language like Fortran or C that allows programmers to build loops
out of goto's, then the optimizer will have to fix loops on its own. I
can think of a couple of approaches.


          1) If the loop header block has a successor block outside
the loop, then clone the loop header block.


          2) Peel an entire iteration of the loop.


Let's reconsider our example, rewritten slightly


a
goto L1


L1: if (p) goto L2 else goto L3


L2: b
goto L1


L3: c


The loop header is L1 and the other block in the loop is L2.
Cloning the header gives


a
goto L1


L1: if (p) goto L2 else goto L3


L2: b
goto L1'


L1': if (p) goto L2 else goto L3


L3: c


Note that we leave the original loop header block in place and make a copy
of it (called L1'). All back edges (edges from within the loop to the
loop header) are repointed to the clone.


When we straighten the mess out a little, we get


a
if (p) goto L2 else goto L3
L2: b
if (p) goto L2 else goto L3
L3: c


which is just what's desired.


The second approach, peeling an iteration of the loop, is rather more
violent. On the other hand, if we peel and then perform global common
subexpression elimination (using value numbering, for example), then we
effectively move all loop invariant in front of the loop.


Peeling our example gives


a
goto L1


L1: if (p) goto L2 else goto L3


L2: b
goto L1'


L1': if (p) goto L2' else goto L3


L2': b
goto L1'


L3: c


Cleaning it up a little would give


a
if (p) goto L2 else goto L3
L2: b
L1': if (p) goto L2' else goto L3
L2': b
goto L1'
L3: c


which is obviously not the same result as achieved by cloning. However,
the higher-level goal is achieved; that is, we have a place to put
loop-invarient code -- in fact, we have already made a copy of all the
loop-invariant code (and everything else). The downside of this approach
is that we can consume lots of space (if not in the final result, at least
in out intermediate representation).


A relevant paper is


    title="Code Motion of Control Structures in High-Level Languages",
    author="Ron Cytron and Andy Lowry and F. Kenneth Zadeck",
    booktitle=popl13,
    year=1986,
    month=jan,
    pages="70--85"


Preston Briggs
--

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