why "guarded do" is better than "jump to middle" in asm

user_9623401 0
Viewed 914

I was reading a textbook which describes two way of translating a while loop into machine code:

//jump to middle
   goto test;
loop:
   body-statement
test:
   t = test-expr;
   if (t)
       goto loop;

and

//guarded do

t = test-expr;
if (!t)
   goto done;
loop:
   body-statement
   t = test-expr;
   if (t)
      goto loop;
done:

I don't know why using the secoond aproach, the compiler can optimize the initial test?

compiler-optimization x86-64 assembly c loops
1 Answers

I don't know why using the secoond aproach, the compiler can optimize the initial test?

This is what the asm / machine code might look like after the compiler is done, using C as pseudo-code for asm. (It's not useful to write C like this.) There's no further optimization / compilation happening after we get to this step.

In actual C you'd just write while(t) or for(int i=0 ; i<n ; i++) like a normal person (an idiomatic C loop), and let the compiler create an idiomatic asm loop (conditional branch at the bottom). That's what compilers are for.

Related: Why are loops always compiled into "do...while" style (tail jump)?

The main downside of jumping into the middle is that it puts an extra unconditional jump on all paths through the function. (Whether the loop runs zero iterations or not).

Peeling the before-first-iteration test to make if(run_at_all) do_loop avoids that jump by duplicating the test code, instead of jumping to a single copy of it.

Sometimes it can then be optimized away: many loops have a known trip-count, or at least known non-zero if the compiler can prove anything about t for the first iteration.

user_2241320
Related