[llvmgcc] Signed divide generated for pointer difference

[lattner]

Bugzilla Link	494
Resolution	FIXED
Resolved on	Feb 22, 2010 12:56
Version	1.0
OS	All

Extended Description

Consider this function:

int ptrdiff(int *X, int *Y) { return X-Y; }

llvmgcc currently compiles this to:

int %ptrdiff(int* %X, int* %Y) {
%tmp.1 = cast int* %X to int
%tmp.3 = cast int* %Y to int
%tmp.4 = sub int %tmp.1, %tmp.3
%tmp.5 = div int %tmp.4, 4
ret int %tmp.5
}

If llvmgcc compiled the divide to an unsigned divide, this could be optimized to
a right shift. Note that C and C++ guarantee that pointers used in pointer
arithmetic are into the same array. This means that an unsigned divide is fine,
and, further, that the remainder is guaranteed to be zero. Because of this
property, some cute code generation tricks can be used to generate slightly
better code.

In the future it might be worthwhile to consider adding a ptrdiff instruction to
LLVM. GCC includes the notion of an "exact divide" (a divide that is known to
have a remainder of zero) for this purpose. Maybe that would be a better way to go.

Note that the STL std::vector class (among others) use pointer differences
extensively, so it's worthwhile to generate decent code for this.

-Chris

[lattner]

assigned to @lattner

[lattner]

Fixed. Patch here:
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20041227/022878.html

Testcase here:
CFrontend/2005-01-02-PointerDifference.c.tr

The example in the bug is now compiled to:

int %Diff(int* %P, int* %Q) {
%tmp.1 = cast int* %P to int ; [#uses=1]
%tmp.3 = cast int* %Q to int ; [#uses=1]
%tmp.4 = sub int %tmp.1, %tmp.3 ; [#uses=1]
%tmp.5 = shr int %tmp.4, ubyte 2 ; [#uses=1]
ret int %tmp.5
}

This patch only implements it for the power of two case. To do more will
require the eventual extension of the LLVM IR to support "exact" integer
divisions.

-Chris