Re: strength reduction

>From article 91-09-045, by ssimmons@convex.com (Steve Simmons):
> Loop induction variable optimization has its biggest win by
> transforming an index into the array to a direct pointer to the element.


A caveat: a _good_ compiler should only do this if it is a "win".
If a machine supports scaled indexing and there is more than one array
reference in the loop, it may be a "lose". Borrowing ssimmons's example:


          for i=1,n
              *(&A + (4*i)) = 0
              *(&B + (4*i)) = 1
          end


  Will (unfortunately) often be turned into:




> Converted to loop induction variable


        ptrB = loc(B)
        for ptrA = loc(A), loc(a)+(4*(n-1)), 4
            *ptrA = 0
            *ptrB =1
            ptrB = ptrB + 4;
        end


This is more a problem with "strength reduction" than loop induction,
in the sense that it trades an "imaginary" (effectively 0 time) multiply for
two real adds. It is also a fairly common "optimization" in well-respected
compilers :-)


I just wanted to provide an example where the "machine independant"
optimizations could benefit from a little "machine dependant" info. The
layers of a compiler are no where near so cleanly separated as texbooks would
have you believe.


> Notice, the address calculation has been completely optimized away.


A pity, if it was cheaper than two pointer adds :-)


Yes, I would prefer that the actual "base of array" be in pointers,
but common subexpession elimination should do that. The question I'm trying
to address is the blind conversion of indexed addresses to pointers so popular
in "new" compilers. I'm sure convex's compilers get this right :-)


Mike


| Mike Albaugh (albaugh@dms.UUCP || motcsd.mot.com!dms!albaugh)
| Atari Games Corp (Arcade Games, no relation to the makers of the ST)
| 675 Sycamore Dr. Milpitas, CA 95035 voice: (408)434-1709
--

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