Re: strength reduction (Preston Briggs)
Wed, 25 Sep 1991 14:19:18 GMT

          From comp.compilers

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

Newsgroups: comp.compilers
From: (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 91-09-045 91-09-064
Date: Wed, 25 Sep 1991 14:19:18 GMT

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

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

Post a followup to this message

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