[instcombine] ptrdiff_t not optimized as well as it could be

[lattner]

Bugzilla Link	537
Resolution	FIXED
Resolved on	Feb 22, 2010 12:46
Version	1.0
OS	All
CC	@markus-oberhumer

Extended Description

Markus Oberhumer writes:

In the example below llvm is only able to optimize away the subtraction in test1, but not in test2/3.

include

int test1(int a, int b) { int d = b - a; a = b - d; // no-op return a; }

char test2(char a, char* b) { ptrdiff_t d = b - a; a = b - d; // no-op on all llvm-supported machines return a; }

int test3(char a, char b, char* c) { ptrdiff_t d = b - a; return (d == 8) || ((a = b - d) < c); // a = ... is a no-op }

[markus-oberhumer]

Point taken (and confirmed for i386 backend as well). Initially I had hoped we could perform this type of optimization at LLVM level, but it looks that this is not trivial.

Thanks, Markus

[lattner]

Again, this is resolved at the codegen level, not at the LLVM level.

$ llvm-as < test2.ll | llc .machine ppc970 .text .align 4 .globl _test2 _test2: blr

-Chris

[markus-oberhumer]

This is what I currently get for the original test1/test2 functions, so I don't feel this issue is resolved yet. Especially that it might enable more subsequent optimizations.

~Markus

int %test1(int %a, int %b) { entry: ret int %a }

sbyte %test2(sbyte %a, sbyte %b) { entry: %tmp.1 = cast sbyte %b to uint ; [#uses=1] %tmp.3 = cast sbyte %a to uint ; [#uses=1] %tmp.4 = sub uint %tmp.3, %tmp.1 ; [#uses=1] %tmp.10 = getelementptr sbyte %b, uint %tmp.4 ; <sbyte> [#uses=1] ret sbyte %tmp.10 }

[lattner]

Try LLC with one of the native backends, e.g. PPC or X86. For the C backend, we would expect the C compiler to catch this.

-Chris

[markus-oberhumer]

I've just built a fresh toolchain from CVS (20051023), but I cannot see the optimization neither in the bytecode nor in the CWriter. At which level is this supposed to happen - at code generation time? IMHO this should be handled in a more generic way.

FYI, 20051023 toolchain produces

sbyte %ptr_renorm_1_v1_ptrdiff_t(sbyte %ptr, sbyte %base) { entry: %tmp.5 = cast sbyte %ptr to uint ; [#uses=1] %tmp.6 = cast sbyte %base to uint ; [#uses=1] %tmp.7 = sub uint %tmp.5, %tmp.6 ; [#uses=1] %tmp.9 = getelementptr sbyte %base, uint %tmp.7 ; <sbyte> [#uses=1] ret sbyte %tmp.9 }

[lattner]

All 8 testcases in comment 5 compile to 'blr' now, thus they are optimized.

-Chris

[lattner]

Ok

[markus-oberhumer]

Chris,

this is indeed some real-world code which is needed on segmented-memory architectures (e.g. IBM OS/400 iSeries) for pointer renormalization after some dirty bit operations. On flat-memory archs it's is just a no-op.

Furthermore the current CVS (build 20050630) does not seem to optimize any of the functions as listed below, so this bug should not get closed yet.

~Markus

/ return ptr; / char ptr_renorm_1_v1_ptrdiff_t(char ptr, char base) { return base - (ptrdiff_t) (base - ptr); } char ptr_renorm_1_v1_size_t(char ptr, char base) { return base - (size_t) (base - ptr); } char ptr_renorm_1_v2_ptrdiff_t(char ptr, char base) { return base - (ptrdiff_t) ((uintptr_t)base - (uintptr_t)ptr); } char ptr_renorm_1_v2_size_t(char ptr, char base) { return base - (size_t) ((uintptr_t)base - (uintptr_t)ptr); }

/ return ptr; / char ptr_renorm_2_v1_ptrdiff_t(char ptr, char base) { return base + (ptrdiff_t) (ptr - base); } char ptr_renorm_2_v1_size_t(char ptr, char base) { return base + (size_t) (ptr - base); } char ptr_renorm_2_v2_ptrdiff_t(char ptr, char base) { return base + (ptrdiff_t) ((uintptr_t)ptr - (uintptr_t)base); } char ptr_renorm_2_v2_size_t(char ptr, char base) { return base + (size_t) ((uintptr_t)ptr - (uintptr_t)base); }

[lattner]

Reid: I'm not sure I understand what your point is about those.

Nate: you point sounds good to me. If Markus is ok with closing it, go for it.

-Chris

[llvmbot]

Looking at the siod code, I note that siod has the possibility of firing multiple times on test case 3. Grepping for "return.*=[^=]" on slib.c yields:

737: return(CAR(cell) = value);} 741: return(CDR(cell) = value);} 1755: if NULLP(tmp) return(VCELL(var) = val); 1756: return(CAR(tmp)=val);} 1777: if NNULLP(tmp) return(CAR(tmp) = val); 1778: if NULLP(env) return(VCELL(var) = val);

[llvmbot]

Test 2 is fixed by:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20050613/026709.html

We should probably close this as fixed and cover test 3 with the cross-MBB SelectionDAG ISel. For what its worth, while this is very rare, it does fire once on Multisource/Applications/siod.

[lattner]

Out of curiousity Markus, how did you notice this? Did this come from real code?

-Chris

[lattner]

assigned to @lattner