Re: strength reduction

In article 91-09-064 albaugh@dms.UUCP (Mike Albaugh) writes:
> 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:
>
> ptrB = loc(B)
> for ptrA = loc(A), loc(a)+(4*(n-1)), 4
> *ptrA = 0
> *ptrB =1
> ptrB = ptrB + 4;
> end


This isn't quit the best possible.
Instead, share one index for both array accesses.


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


This keeps us down to 1 addition (and no multiplies) per iteration.
(We're assuming Reg+Offset or Reg+Reg addressing modes, as provided
by many (but not all) modern architectures).
Generally, all array accesses with the same stride can share the same
index. Albaugh is correct in that the strength-reducer must be
"aware" or the available addressing modes. And of course, scaling
may be used to multiply. For a nice discussion, see


The Compilation of Loop Induction Expressions
Richard L. Sites
TOPLAS Volume 1(1), July 1979


Preston Briggs
--

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