Re: spaghetti code/reducible loops

In article 92-02-102, preston@dawn.cs.rice.edu (Preston Briggs) writes:
> The only particular form of "spaghetti code" that really frustrates me is
> the irreducible loop. An irreducible loop has multiple entry points.


> An alternative is called "node splitting". In the simple case above, the
> code can be restructured, giving
> [Example deleted]
>
> I've never built a node splitter. I'm not anyone has.


Our optimizer does node splitting. We initially just gave up on
irreducible loops, but we kept getting customer benchmarks that contained
them, and finally we got one in which the irreducible loop was where most
of the time was spent, and we *had* to optimize it to win the bid. :-)
What's that about necessity being the mother of invention? :-)


> 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).


Hmm, maybe I should publish ours! It wasn't really that hard, though it
is possible for it to duplicate a large amount of code if you have nested
irreducible loops. (Splitting an inner loop will duplicate less code than
splitting the containing loop, but it can still become large.) We give
the user the ability to control how much code gets duplicated to fix
irreducible loops; if you exceed this, we just give up on that loop (but
not on others).


> 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.


In our case, it wasn't so much that customers felt they couldn't
restructure their code, they were just unwilling to do so. "It ain't
broke, so don't fix it", was their attitude.


--
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
bill@ssd.csd.harris.com
--

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