Re: while loop code generation

ast@halcyon.com (Andrew Tucker) writes:


> On page 227 of Fraser and Hanson's _A Retargetable C Compiler_,
> 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.
>
> Am I missing something or is their claim incorrect?


I assume they mean "performs conditional transfers of control", in
which case they are correct. Otherwise, in both cases, 2 gotos are
*generated*. Or, if you replace "generates goto's" with "performs
transfers of control", both templates perform n+1 gotos.


To clarify...given the following snippet of code:


    if expression == 0 goto L1
    goto L2


Two goto's are *generated* by the compiler/assembler.


At run time, for a given thread of execution, only one goto is
*performed*.


At run time, for a given thread of execution, either one or two
conditional transfers of control are *performed* -- one if "expression
== 0" is true, two otherwise. ("goto L1" is a conditional transfer of
control even if it is not *performed*; "goto L2" is an "unconditional
conditional transfer of control", that is, a conditional transfer of
control whose condition is "always true".)


(I think the main reason for counting *unperformed* conditional
transfers of control is that, generally, internal processor
architectures see them as more than just no-ops when it comes to
considering things like instruction scheduling, I-cache fetches, and
so on. I don't think *all* processor architectures see them this way,
but I do believe most high-performance ones do, so it's often
worthwhile avoiding unnecessarily executing untaken conditional
transfers of control.) --


"Practice random senselessness and act kind of beautiful."
James Craig Burley, Software Craftsperson burley@gnu.org
--

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