Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!cs.utexas.edu!sm.unisys.com!hplabs!amdcad!crackle!tim
From: tim@crackle.amd.com (Tim Olson)
Newsgroups: comp.sys.amiga.tech
Subject: Re: Aztec compiler ineffeciencies
Message-ID: <23627@amdcad.AMD.COM>
Date: 26 Nov 88 21:41:24 GMT
References: <3013@sugar.uu.net>
Sender: news@amdcad.AMD.COM
Reply-To: tim@crackle.amd.com (Tim Olson)
Organization: Advanced Micro Devices, Inc. Sunnyvale CA
Lines: 45
Summary:
Expires:
Sender:
Followup-To:

In article <3013@sugar.uu.net> karl@sugar.uu.net (Karl Lehenbauer) writes:
| I've been examining the output of Aztec 3.6a and have discovered that it does
| no optimization on divides, such as turning divides by constants into shifts
| and adds, even when the divisor is a power of 2!  This is probably Not News
| to a lot of you, but it was a shocker for me.
| 
| The code:
| 
| main()
| {
| 	register int x = 17441;
| 
| 	x /= 2;
| }
| 
| generates (for the divide):
| 
| 	move.l	#2,d1
| 	move.l	d4,d0
| 	jsr	.divs#		; <-- a subroutine call!
| 	move.l	d0,d4

A multiply by a constant can be strengh-reduced into a series of shifts
and adds, but not a divide.  Optimization *can* be done with power-of-two
divides, however, this is usually only performed with unsigned
dividends.  The reason is that negative dividends result in incorrect
quotients (at least under most implementations where quotients are
truncated towards zero instead of -infinity):

	-1 /  2 ->  0
	-1 >> 2 -> -1

Try declaring the variable 'x' as unsigned to see if the optimization is
now performed.

Strengh-reduction can be performed on signed divides by powers-of-two
with a little extra work.  The trick is to replicate the sign-bit of the
dividend to all the bits of a temporary, resulting in either 0 or -1. 
This is then subtracted from the dividend before the shift, resulting in
a correct quotient.


	-- Tim Olson
	Advanced Micro Devices
	(tim@crackle.amd.com)