spaghetti code

I wrote
>: "No spaghetti-coded algorithm (containing irreducible loops)
>: is going to be amenable to important loop-based optimizations."


and jbs@WATSON.IBM.COM asked
> What are irreducible loops and why do they give compilers
>problems? Can you give an example?


The only particular form of "spaghetti code" that really frustrates me is
the irreducible loop. An irreducible loop has multiple entry points. For
example:


...
if (...) then
<statements A>
goto 20
endif
<statements B>
10 continue
<statements C>
20 continue
<statements D>
30 if (...) goto 10


Obviously (to us) there is some kind of loop involving the statements from
10 to 30. Further, it seems intuitive that <A> and <B> are not part of
the loop. Unfortunately, I don't know of any algorithmic approach that
matches my intuition.


The common approach of finding "natural loops" fails because there is no
clear loop header. Typical interval reduction schemes fail for the same
reasons.


Some optimizers give up entirely when irreducible loops are detected. The
more sophisticated approaches will glob everything from the 1st IF through
the last IF into a single region, label it irreducible, and isolate it
from the rest of the procedure.


An alternative is called "node splitting". In the simple case above, the
code can be restructured, giving


if (...) then
<statements A>
<statements D>
else
<statements B>
endif
10 continue
<statements C>
<statements D>
30 if (...) goto 10


Note that we've merely duplicated <D>; no extra compuation is required.
Of course, this is a very simple example. It's possible to construct much
more complex cases.


I've never built a node splitter. I'm not anyone has. I _have_ seen a
detailed description of how it's done, but it's unpublished, and probably
unpublishable (kind of gross). There's rumors that you can require an
exponential amount of splitting (can't find it in print though).


Most people simply design languages that don't allow irreducible code.
Typically, don't allow branches into a loop. Of course, some people
object to such restrictions, thinking their algorithms can't be expressed
efficiently without such things. But the existance of the node splitting
algorithm shows that it _is_ possible to restructure their code so that
loops are exposed.


Preston Briggs
--

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