C optimizer

[Mark Brader]

> >I would expect the following optimizations: ... 3) reducing things like
> >intval/2 == intval >> 1 when they are faster.
> 
> On most implementations these are not equivalent, unless the compiler can
> prove that intval >= 0.

Quite right, except that it also generally works if the compiler can prove
that intval is a multiple of the divisor.

However, I have met one compiler that always did the optimization anyway!
Accordingly, the expressions a/2 and a/b produced *different answers*
when a was negative and b was equal to 2!

(No, I don't remember which compiler it was.  It was a machine we were
porting product to, but I wasn't doing the port myself, I just came in to
try to identify why my code was producing wrong answers.)

It may be noted that the values produced by / and % on negative numbers,
where the dividend is not a multiple of the divisor, are not fully
defined by the language, neither in the K&R 1 nor the proposed ANSI versions.
This is because there are three identities that are desirable in different
situations, namely

	[1]	(-a)/b, a/(-b), -(a/b) are all equal
	[2]	a%b ranges from 0 to b-1 for positive b
	[3]	(a/b) * b  equals  a - a%b

But it isn't possible to satisfy all three.  The language does guarantee
[3].  Of the others, most implementations choose [1], to the annoyance
of mathematical users to whom [2] would be much more preferred; that's
because it's the way the underlying hardware typically behaves.

Now, it turns out that on a 2's complement machine that chooses to sign-
extend on >> (also implementation-defined) *and* which elects to support
identity [2], *then* the optimization described above *is* possible.

Oh -- I should also mention that in proposed ANSI C the library includes
two functions div() and ldiv(), which implement (for ints and longs
respectively) a form of / and % that is guaranteed to support identities
[1] and [3].  In ANSI C the compiler is allowed to optimize these so that
they do not become actual function calls.

Mark Brader, SoftQuad Inc., Toronto, utzoo!sq!msb, msb at sq.com
	A standard is established on sure bases, not capriciously but with
	the surety of something intentional and of a logic controlled by
	analysis and experiment. ... A standard is necessary for order
	in human effort.				-- Le Corbusier