spaghetti code (Preston Briggs)
Sat, 22 Feb 1992 01:49:43 GMT

          From comp.compilers

Related articles
spaghetti code (1992-02-22)
Re: spaghetti code/reducible loops (1992-02-25)
spaghetti code (1992-02-28)
Re: spaghetti code (1992-03-02)
| List of all articles for this month |

Newsgroups: comp.arch,comp.compilers
From: (Preston Briggs)
Keywords: optimize, design
Organization: Rice University, Houston
References: <9202220021.AA28153@ucbvax.Berkeley.EDU>
Date: Sat, 22 Feb 1992 01:49:43 GMT

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

if (...) then
<statements A>
goto 20
<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

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>
<statements B>
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

Post a followup to this message

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