Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!rutgers!tut.cis.ohio-state.edu!DG-RTP.DG.COM!meissner
From: meissner@DG-RTP.DG.COM (Michael Meissner)
Newsgroups: gnu.gcc.bug
Subject: Strength reduction vs Motorola 88k [was more patches to loop.c]
Message-ID: <8904052322.AA00710@tiktok.dg.com>
Date: 5 Apr 89 23:22:18 GMT
References: <8904010147.AA01751@bayes.arc.nasa.gov>
Sender: daemon@tut.cis.ohio-state.edu
Distribution: gnu
Organization: GNUs Not Usenet
Lines: 44

Now that strength reduction doesn't cause an error, can somebody point
me to some code that actually speeds up with strength reduction?  For
the 88k compiler, I have not found anything that speeds up, and
dhrystone in fact slows down by 1%.  This is more curiousity at this
stage...

I hypothesize that strength reduction is being too general in the way
it optimizes things.  As I understand strength reduction in general,
though not yet the specifics of what GNU does, it trys to replace high
cost instructions such as multiplies with lower cost instructions such
as adds.  Thus for a loop of the form:

	for (i = 0; i < n; i++)
		a[i] = 3*b[i];

with a loop of the form:

	for ((p1 = &a, p2 = &b, i = 0);
	     i < n;
	     (p1 += sizeof(a[0]), p2 += sizeof(b[0]), i++))
		*p1 = 3*(*p2);

which eliminates the multiplies inheirent in the array indexing.
However, not all multiplies are high cost.  In particular, some
multiplies can be folded directly into memory indexing and such, and
others that are powers of two can be done simply by the appropriate
shifts.

Could this be the reason on the 88k that I see slowdown, is that in
attempting to optimize things, it replaces a 1 cycle add + indexed
multiply into two or three adds spread over multiple registers, which
is then adds up to multiple cycles.  Or could the 88k multiply
instruction be sufficiently fast (4 clocks compared to 1 for add),
that strength reduction just doesn't produce the gains that you see on
more conventional processors.  At present, I haven't had time to go
further on this issue.

--
Michael Meissner, Data General.
Uucp:		...!mcnc!rti!xyzzy!meissner		If compiles were much
Internet:	meissner@dg-rtp.DG.COM			faster, when would we
Old Internet:	meissner%dg-rtp.DG.COM@relay.cs.net	have time for netnews?