karl@sugar.uu.net (Karl Lehenbauer) (11/25/88)
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
With a shift:
main()
{
register int x = 17441;
x >>= 1;
}
generates (for the shift)...
asr.l #1,d4
--
-- "We've been following your progress with considerable interest, not to say
-- contempt." -- Zaphod Beeblebrox IV
-- uunet!sugar!karl, Unix BBS (713) 438-5018rodd@dasys1.UUCP (Rod Dorman) (11/26/88)
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 > asr.l #1,d4 As many compiler writers have found in the past and I'm sure many will rediscover in the future, this only works for positive values. Try shifting -1 and you'll get -1 as a result, *not* zero as one would expect. -- Rod -- Rod Dorman {sun!hoptoad,cmcl2!phri}!dasys1!rodd Big Electric Cat Public Unix "The ships hung in the sky in much the same way that bricks don't"
tim@crackle.amd.com (Tim Olson) (11/27/88)
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)
peter@sugar.uu.net (Peter da Silva) (11/27/88)
In article <7949@dasys1.UUCP>, rodd@dasys1.UUCP (Rod Dorman) writes: > 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 > > asr.l #1,d4 > As many compiler writers have found in the past and I'm sure many will > rediscover in the future, this only works for positive values. Try > shifting -1 and you'll get -1 as a result, *not* zero as one would expect. First consider (unsigned)/2. Then... As many compiler users in the past have discovered, having -1/2 == -1 is often much more useful... particularly with graphics applications. This depends on how you interpret integer arithmetic... should division be truncated towards zero (trunc), to the numerically lower value (floor), or the numerically higher value (cieling). Mathemeticians like trunc, but this leads to a singularity at 0. Say that, for some reason, you're drawing a line at arctan(1/2) using a straightforward algorithm, and it goes through the origin. With trunc With floor ** ** ** ** *** ** ** ** ** ** See comp.lang.c for assorted flames. -- Peter da Silva `-_-' peter@sugar.uu.net Have you hugged U your wolf today? Disclaimer: My typos are my own damn busines#!rne