CODEWITHSUNDEEP
assemblygccx86llvm
JohnTortugo
JohnTortugo

Reputation: 6625

Why bottom test loop is preferable?

I heard someone once say that compilers frequently move the loop conditions to the bottom of the loop. That is, loops like these:

while (condition) {
    ...
}

is changed to :

if (condition) {
     do {
         ...
     } while (condition);
}

regarding machine independent optimization, why is latter preferable?

Upvotes: 7

Views: 1019

Answers (3)

Ling Kun
Ling Kun

Reputation: 11

For the assembly view, a loop is just a jump instruction that jump backward of the code. So compiler need to insert a jump at the end of the loop.

Many instruction set, like x86, ARM, MIPS all provide conditional jump/branch instructions. Whether the jump will take place dependent on the condition specified in the instruction.

So compilers prefer this kind of instructions, and move the condition to the end of the loop to make use of the instruction.

Upvotes: 0

user207421
user207421

Reputation: 311023

You are partially mistaken. The typical optimization is this:

    jmp $test;
$loop:
    ; loop statements
$test:
    test <condition>;
    branch-true $loop;

rather than this:

$loop:
    test <condition>;
    branch-false $end;
    ; loop statements
    branch loop;
$end:

which has two branches in every iteration of the loop. Another advantage is that the part after the initial jump is identical to the code generated for do/while.

Upvotes: 1

Mike Kwan
Mike Kwan

Reputation: 24477

Without compiler optimisation, the first loop goes to assembly code like this:

  @@:
cmp ... ; or test ...
jz @f

...
jmp @b

Whereas the second loop goes to something like this:

jmp bottom

  @@:
...

  bottom:
cmp ... ; or test ...
jz @b

Conditional jumps are usually predicted to be taken so the first method could potentially lead to more pipeline/instruction cache flushes.

However, the most important thing is that for the first loop, there are two branches available per loop iteration (2N), whereas in the second, each loop iteration only has one branch with a fixed overhead of the first unconditional jump (N+1).

For more information on loop optimisation, see page 88 of this assembly optimisation guide.

Upvotes: 8

Related Questions