dean@ndmath.UUCP (02/02/87)
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)ballou@brahms.Berkeley.EDU.UUCP (02/03/87)
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; Well, not quite. If this is what the newsletter indicates, then the newsletter is in error. The idea is to avoid doing a multiplication by 7, and the correct idea is this: Replace for (i = 0; i < 10; ++ i) j += i * 7; with i = 10; for ($foo = 0; $foo < 70; $foo += 7) j += $foo; WHERE $foo is a compiler generated temporary whose lifetime is the for loop. (Aside: Please, no flames, I am quite well aware that '$' cannot appear in a C identifier!) This works as long as the compiler can prove that the value of i will not be altered by side effects in the loop. >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? (Your "following code" appears to have turned into line eater fodder.) Yes, you are right, the code you indicated does not work. However, the suggested replacement does have the same effect. -------- Kenneth R. Ballou ARPA: ballou@brahms.berkeley.edu Department of Mathematics UUCP: ...!ucbvax!brahms!ballou University of California Berkeley, California 94720
braner@batcomputer.UUCP (02/03/87)
[] The full-page ad by Microsoft in BYTE tells us about all kinds of nifty optimizations that a C compiler MIGHT do if it was smart enough. It would be a lot more interesting to hear about ACTUAL optimizations done by REAL compilers. I would be especially interested in hearing about pitfalls, e.g. correct but obtuse code that confuses a given optimizing compiler into generating wrong code... - Moshe Braner
m5d@bobkat.UUCP (02/03/87)
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
gwyn@brl-smoke.UUCP (02/08/87)
In article <182@ndmath.UUCP> dean@ndmath.UUCP (Dean Alvis) writes: > for(i=0;i<10;++i) j += i*7; > evaluates to: > for(i=0;i<70;i += 7) j += i; >... following code which depends on the value of i may not work correctly. I suspect the article in question was merely using C to illustrate the concept, not claiming formal equivalence under all circumstances. Such optimization is usually done at a point inside the compiler where the original C code no longer exists but has been turned into parse trees. Certainly, correct optimization would require fixing up the final value of variable `i', if it were used after the loop. Note that experienced C programmers often have already performed such program transformations in their heads and written the "optimized" code sequence; this is partly due to the fact that the original C compilers didn't do much optimization. So long as an optimization is guaranteed never to alter program semantics, it really should be done by the compiler rather than by the programmer, who generally has more important things to worry about.
guy@gorodish.UUCP (02/09/87)
>So long as an optimization is guaranteed never to alter program semantics, >it really should be done by the compiler rather than by the programmer, who >generally has more important things to worry about. And who is, more often than not these days, writing C code rather than writing code that happens to be in C for some particular machine (even when writing kernel code!), so that they *can't* know what code is better or worse.
bright@dataio.UUCP (02/09/87)
In article <5603@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >In article <182@ndmath.UUCP> dean@ndmath.UUCP (Dean Alvis) writes: >> for(i=0;i<10;++i) j += i*7; >> evaluates to: >> for(i=0;i<70;i += 7) j += i; >>... following code which depends on the value of i may not work correctly. >I suspect the article in question was merely using C to illustrate >the concept, not claiming formal equivalence under all circumstances. >Certainly, correct optimization would require fixing up the >final value of variable `i', if it were used after the loop. There are a lot of subtle things about loop induction variable replacement, the point of Microsoft's article was merely to advertise that their next version of the compiler could do it. For a good treatment of the subject (though not complete, as I discovered), see Aho and Ullman's excellent book on compilers (usually known as the Dragon Book). >Note that experienced C programmers often have already performed such >program transformations in their heads and written the "optimized" >code sequence; this is partly due to the fact that the original C >compilers didn't do much optimization. So long as an optimization is >guaranteed never to alter program semantics, it really should be done >by the compiler rather than by the programmer, who generally has more >important things to worry about. You are quite right. In fact, nearly all the transformations done by an optimizing compiler can be done by the programmer in the original source code. The reasons this is undesirable is: 1. The goals of maximum performance vs portability, readability and maintainability are often at right angles to each other. 2. 'Tuning' code to wring the last bit of performance out of your code may work against you when using a different compiler or compiling for a different CPU. Having a global optimizer enables the programmer to concentrate on the algorithm rather than performance, letting the compiler do the grunt work. By the way, Datalight is the first C compiler vendor for the PC that is shipping a global optimizer, see the Feb. 87 Computer Language ad. Datalight can be reached at (206) 367-1803. P.S. I have no connection with Datalight other than the fact that I wrote the compiler, and make money off of sales of it!
mccaugh@uiucdcsm.UUCP (02/11/87)
Yes, the two fragments of code are semantically equivalent in that they
should yield as final value j(final) = j(initial) + 315. Of course, if
j(initial) = undefined, they will still be equivalent!
A loop-invariant for the first fragment is:
(i=#) & (j(#) = j(initial) + 7*(1 + ... + #-1))
where '#' = number of cycles (of the FOR-loop); a loop-invariant for the
second fragment is similar: (i=7*#) & (j(#) = j(initial) + 7*(1 + ... + #-1)).
Both fragments will cycle 10 times, so that:
j(final) = j(10) = j(initial) + 7*(9*10)/2
= j(initial) + 315.
(But the final values of i of course differ: i(final) = 10 in the first
fragment, and 70 in the second -- I here assumed that 'i' was a loop-
counter and that 'j' was the variable of interest.)
The efficiency gained in the second fragment is to replace a multiplication
by an addition, considered "efficient" since the simplification is repeated
ten times.
I apologize for this verbose response, which I only entered after reading the
first 5 and being disappointed to find no demonstration of the equivalence
claimed for the 2 fragments. (I sincerely hope this fills that gap.)
-- Scott McCaughrin (mccaugh@uiucmsl)