Path: utzoo!attcan!uunet!husc6!mailrus!cornell!uw-beaver!uw-june!uw-entropy!dataio!bright
From: bright@Data-IO.COM (Walter Bright)
Newsgroups: comp.lang.c
Subject: Re: Duff's device
Message-ID: <1683@dataio.Data-IO.COM>
Date: 7 Sep 88 18:32:38 GMT
References: <32941@cca.CCA.COM>
Reply-To: bright@dataio.Data-IO.COM (Walter Bright)
Organization: Data I/O Corporation; Redmond, WA
Lines: 29

In article <32941@cca.CCA.COM> g-rh@CCA.CCA.COM (Richard Harter) writes:
<Duff's device is another variant on the the loop and a half problem
<where you need to execute a loop body a whole number of times and part
<of the loop body once.
<  goto A;
<  do {
<    code_section_1
<A:       /* Entry point for partial loop construction */
<    code_section_2
<    }
<    while (sometest);

This type of code is called an 'irreducible flow graph' in optimizer texts.
Basically, it's a loop with more than one entry point. It's the bane of
optimizers, as most loop optimization algorithms depend on there being
only one entry point. Typical approaches to deal with this are:
	1. Abandon optimization on that loop.
	2. Abandon optimization on the function that contains that loop.
	3. Rewrite the flow graph to eliminate the problem (the algorithm
	   is called 'node splitting', it's basically putting a copy
	   of code_section_2 before the loop).
Irreducible flow graphs occur so rarely in production code (even in code
that is a snarl of goto's) that implementing (3) is not worthwhile, and
approach (1) or (2) is used.

Some optimizers do not do flow analysis to detect loops. They rely on
recognizing loop constructs such as for(), while() and do..while(). Since
they cannot recognize an irreducible flow graph, they silently abandon
optimization on *any* function with a goto in it.