Re: while loop code generation

ast@halcyon.com (Andrew Tucker) writes:
> they claim that the code
> goto L+1
> L: statement
> L+1: if expression != 0 goto L
> generates n+2 goto's for a loop executing statement n times while
> the code
> L:
> L+1: if expression == 0 goto L+2
> statement
> goto L
> L+2:
> generates 2n+1 goto's.
> Maybe my analysis (and my test code) are severely flawed, but
> I see both layouts as equivalent, with n+1 gotos executed when
> statement is executed n times.


Either the textbook or your reading of it is a tad off. The correct
statement (and the measure usually of importance) is the number of
conditional plus unconditional branch instructions.


The test-at-the-bottom form involves one successful conditional branch
per iteration, plus a failed conditional branch after the last
iteration, plus one unconditional branch to get started. Symbolically
1 UB + n CB(t) + 1 CB(f)
for n iterations.


The test-at-the-top form requires one conditional *and* one
unconditional branch per iteration, with the conditional branch failing,
plus a successful conditional branch after the last iteration.
Symbolically
n CB(f) + n UB + 1 CB(t)


Of course the exact costs will depend on your machine architecture,
but on nearly all machines test-at-the-bottom is preferable for a loop
that is to be executed many times. Two instructions are seldom
cheaper than one.


If you have reason to believe that the loop will usually be executed
zero (or at most one or two) times, then test-at- the-top might be
faster. But it'd be foolish to optimize for that case without strong
evidence, because the loops that actually matter for performance are
the ones that are executed many times.


regards, tom lane
--

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