Re: strength reduction

albaugh@dms.UUCP (Mike Albaugh)
23 Sep 91 14:27:14 GMT

          From comp.compilers

Related articles
Strength Reduction napi@rangkom.MY (1991-09-17)
Re:strength reduction ssimmons@convex.com (1991-09-17)
Re: Strength Reduction preston@dawn.rice.edu (1991-09-17)
Re: strength reduction albaugh@dms.UUCP (1991-09-23)
Re: strength reduction preston@dawn.rice.edu (1991-09-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: albaugh@dms.UUCP (Mike Albaugh)
Keywords: optimize
Organization: Atari Games Inc., Milpitas, CA
References: 91-09-045
Date: 23 Sep 91 14:27:14 GMT

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


Post a followup to this message

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