gcc loop construct changes to assembly code

Question

Why does the gcc compiler translate while loops into do-while constructs when creating assembly code? I know any while loop can be rewritten as a do-while for instance in c

while (test) { ... }

can be rewritten as

if ( !test ) goto skip;
do {
. . .
} while ( test );
skip:

Because there are no `for` or `while` loops in assembly language. — Maxim Egorushkin, Oct 11 '11 at 19:02
If you want to talk about Assembly, post Assembly code generated by compiler. — Alex F, Oct 11 '11 at 19:02

zwol · Accepted Answer · 2019-11-18T20:23:32.507

Building on anatolyg's answer, you may wonder why the do-while construct is more efficient, especially considering that as shown, the test has been duplicated (so the generated code is bigger). The answer is that very often the test expression can be proven always to be true on loop entry, so

    if ( !test ) goto skip;
loop:
    . . . // loop body
    if ( test ) goto loop;
skip:
    . . . // continue the program

can be simplified to

loop:
    . . . // loop body
    if ( test ) goto loop;
    . . . // continue program

Now, why not do that at the same time as the original transformation, and avoid the original transformation if the compiler can't prove the loop will cycle at least once? Because the algorithm that proves the loop will cycle at least once is actually a generic if-condition optimizer. The usual sequence of optimizations is something like this:

Transform all loops into a "canonical" form (more or less as shown in the first code block above)
Do lots and lots of optimizations that expect loops in that canonical form, such as the if-statement elimination shown.
After you're done with everything that cares about loops as such, attempt to de-canonicalize where that would eliminate redundancy.

The other thing to know is that sometimes a duplicate test is deliberately left in because the compiler expects that to produce better run-time behavior. For instance, if the compiler has reason to believe that the loop usually cycles many times, but can't prove that it always cycles at least once, then the conditional branch instruction above the loop will almost always fall through, and the conditional branch below the loop will almost always jump. When that's the case, leaving them separate is likely to make the CPU's branch predictor more accurate. Branch prediction accuracy is second only to cache-friendliness as the limiting factor for speed on modern out-of-order CPUs.

There is also only 1 branch per time it loops (just the backwards one) instead of two. — harold, Oct 12 '11 at 20:33
True, but if the compiler did recombine the test expressions at the top of the loop, you'd have an *unconditional* branch at the bottom, which is almost free on modern CPUs -- it occupies a decode unit but never makes it into the main pipeline. — zwol, Oct 12 '11 at 20:41

score 3 · Answer 2 · answered Oct 11 '11 at 20:09

In general a do-while loop is more efficient than a while loop. Since the compiler wants to create a fast (rather than readable) program, it converts most while loops to do-while ones.

In fact, implementing a while loop using only if and goto (approximating the assembly language) can be done as follows:

start:
    if ( !test ) goto skip;
    . . . // loop body
    goto start;
skip:
    ; // continue the program

This is equivalent but probably less efficient than the do-while implementation (because the latter has 1 less line of code inside the loop):

    if ( !test ) goto skip;
loop:
    . . . // loop body
    if ( !test ) goto loop;
skip:
    ; // continue the program

gcc loop construct changes to assembly code

2 Answers2