Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!im4u!ut-sally!ut-ngp!infotel!pollux!bobkat!m5d
From: m5d@bobkat.UUCP
Newsgroups: comp.lang.c
Subject: Re: induction variable optimization
Message-ID: <531@bobkat.UUCP>
Date: Tue, 3-Feb-87 09:25:54 EST
Article-I.D.: bobkat.531
Posted: Tue Feb  3 09:25:54 1987
Date-Received: Wed, 4-Feb-87 07:22:04 EST
References: <182@ndmath.UUCP>
Reply-To: m5d@bobkat.UUCP (Mike McNally (dlsh))
Organization: Digital Lynx, Inc; Dallas, TX
Lines: 53
Keywords: does this work?

In article <182@ndmath.UUCP> dean@ndmath.UUCP (Dean Alvis) writes:
>In a recent Newsletter from Microsoft in Byte, the following is given as an
>example of *induction variable optimization* :
>
>     for(i=0;i<10;++i)   j += i*7;
>
>     evaluates to:
>
>     for(i=0;i<70;i += 7)  j += i;
>
>Now, I may not understand what "evaluates to" means here, but it seems to me
>that these statements are not equivalent, and following code which depends on
>the value of i may not work correctly. Am I misunderstanding something?
>
>     Dean Alvis   ( ...!ndmath!dean)

The two statements are equivalent in terms of the effect on "j".  If
the optimizer determines that the variable "i" is not live after the
loop (i.e., there are no references to "i" and no pointers pointing to
it (hard to determine)) then the optimization is permissable...sort
of.  This is one of those things that would have to be a selectable
optimization.  If "i" were actually a hardware register in some
controller somewhere, then this might cause problems.

The compiler might also decide to generate the second loop, then insert
code afterwards to "fix" the value of "i".

Most induction variable oportunities arise from array subscripting:

    long a[100];

    for (i = 0; i < 100; i++)
        a[i] = <something>;

The compiler will have to generate code to multiply "i" by sizeof(long)
each time through the loop.  This could be improved by optimization,
although most C programmers would do it in the source code:

    long a[100], *b;

    for (i = 0, b = a; i < 100; i++, *b++ = <something>);

I once heard a story from a compiler deity in which some dude wrote a
FORTRAN source code optimizer.  It read FORTRAN source and produced
FORTRAN source which was "better".  It supposedly did better than the
IBM G (or H, whatever the heavily optimizing IBM FORTRAN compiler was
called) optimizer.  This could be fiction.

-- 
Mike McNally, mercifully employed at Digital Lynx ---
    Where Plano Road the Mighty Flood of Forest Lane doth meet,
    And Garland fair, whose perfumed air flows soft about my feet...
uucp: {texsun,killer,infotel}!pollux!bobkat!m5d (214) 238-7474