Adding two pointers

[Chris Torek]

In article <922 at garcon.cso.uiuc.edu> mcdaniel at uicsrd.csrd.uiuc.edu
(Tim McDaniel) writes:
>One question has not yet been answered, and it makes this whole fiasco
>moot.

Indeed, it is the heart of the matter.  (But beware the word `moot',
for it means both `not worthy of discussion' and `worthy of discussion'.
A `moot' is a meeting, where a group discusses some topic of interest.
The discussion is often interminable and leads to no resolution; hence
the double meaning.)

>What additional power does pointer addition give?  What can be
>done with it that can't be done about as easily as with pointer
>subtraction?

Presumably the reason someone might want to write

	some_type base[N], *low, *high, *mid;
	...
	mid = (low + high) / 2;

is to avoid the scaling that occurs with

	mid = ((low - base) + (high - base)) / 2 + base;

which, if compiled in the most straightforward (and stupid) manner,
yeilds machine code much like this:

	// pretend everything is an int
	// mid <- ( (low-base)/size + (high-base)/size ) * size + base
	sub	base,low,r0
*1	div	r0,size,r0	# `size' being a constant
	sub	base,high,r1
*2	div	r1,size,r1
	add	r0,r1,r0
	div	r0,$2,r0	# divide by 2 is really shift right 1
*3	mul	r0,size,r0
	add	r0,base,mid

The three lines marked with `*' are unnecessary.  They cannot be
deleted if the code is expressed as in the second comment above,
because it is not clear that the division by `size' (*1 and *2) does
not discard low bits---for instance, if size is 2, that it does not
force the result of the subtractions to be even.  We, however, know
that both `low' and `high' point into the same array, and that the
result of the two `sub's just before the starred `div's are in fact
a multiple of `size', that no bits are discarded, and that the marked
`div' and `mul' instructions can in fact be factored out.

But subtraction of pointers is a common occurrence in C, and any
optimising compiler worth its name should note this.  Subtraction of
two pointers is only defined if both point to elements of the same
array; and when they do, it is guaranteed that the difference is a
whole number of elements, or in other words a proper multiple of `size'.
So the compiler should reduce this to

	sub	base,low,r0
	sub	base,high,r1
	add	r0,r1,r0
	div	r0,$2,r0
	add	r0,base,mid

which is what we need anyway (to avoid overflow).

(Sad to say, gcc does not win this one....  It does, however, avoid
divides by using sub+bge+add+label+shift.  The bge+add+label sequence
is unnecessary.  Is rms listening?)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris