Re: while loop code generation

Craig Burley <burley@cygnus.com>
15 Dec 1997 21:49:19 -0500

          From comp.compilers

Related articles
while loop code generation ast@halcyon.com (1997-12-14)
Re: while loop code generation gclind01@spd.louisville.edu (1997-12-15)
Re: while loop code generation burley@cygnus.com (Craig Burley) (1997-12-15)
Re: while loop code generation tgl@netcom.com (Tom Lane) (1997-12-15)
Re: while loop code generation n8tm@aol.com (1997-12-15)
Re: while loop code generation tim@franck.Princeton.EDU.composers (1997-12-29)
Re: while loop code generation preston@tera.tera.com (1998-01-03)
| List of all articles for this month |

From: Craig Burley <burley@cygnus.com>
Newsgroups: comp.compilers
Date: 15 Dec 1997 21:49:19 -0500
Organization: Cygnus Support
References: 97-12-112
Keywords: code, optimize

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
--


Post a followup to this message

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