CODEWITHSUNDEEP
cperformanceassemblywhile-loop
playforest
playforest

Reputation: 113

Compiler's alleged optimisation of while loop

In this segment of an embedded programming lecture, Dr. Samek explains how the compiler is able to realise efficiencies over the "original code" (presumably by this he means an implementation dictated by the logical order of the syntax):

I hope you have noticed that the disassembled code implements a different flow of control from what I've described for the while loop. The original code was supposed to test the condition first and then jump over the loop body if the condition wasn't true. The compiled code starts with an unconditional branch and reverses the order of the loop body and the testing of the condition. When you think about it, though, those two flows of control are equivalent, except the generated one is faster, because it has only one conditional branch at the bottom of the loop.

Throughout his explanation, he draws reference to the two flow charts shown. The chart depicting the compiled code illustrates how "it has only one conditional branch at the bottom of the loop." I can't seem to see how this works in practice:

0x2815 CMP -> 0x1c40 ADDS ->repeat until condition is false

0x2815 CMP -> 0xdbfc BLT.N -> 0x1c40 ADDS -> repeat until condition is false

I can understand how both flows of control are equivalent (at least from the diagrams alone), but certainly not how the generated one (on the right) is faster. First, the arrows at the very beginning of both diagrams lead to the very same branches. Second, although the branch does seem to occur later on in the schematic on the right, as you've seen from the screen-captures, the simulator seems to show that both methods commence with the machine instructions pertaining to the comparison (0x2815 CMP).

How can I reconcile the flow-charts to what I'm seeing in practice?

Upvotes: 1

Views: 322

Answers (2)

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

I concur with Kerren SB's answer. I'll discuss it in more detail:

The original logic has the following jump instructions that are executed during each iteration:

begin_loop:
    cmp counter, 21
    jge end_loop           ; jump when greater or equal
    ...
    jmp begin_loop
end_loop:
    ....

The revised logic executes one instruction less during each iteration:

    jmp test_loop          ; executed once; not part of loop
begin_loop:
    ...
test_loop:
    cmp counter, 21
    jlt begin_loop         ; jump when less than
    ...

So in the loop the unconditional jmp begin_loop is saved.

Upvotes: 6

Kerrek SB
Kerrek SB

Reputation: 477570

The only instructions that matter are the ones that are repeated in every loop round. And the point of the rearrangement of the logic is that there is only one jump per loop round. There may be several jumps before and after the entire loop, but we don't care about those. The only things that are expensive are the ones that are done over and over.

Upvotes: 5

Related Questions