not taking advantage of known pointer alignment

[llvmbot]

Bugzilla Link	9120
Resolution	FIXED
Resolved on	Feb 13, 2011 02:28
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@lattner,@nlewycky

Extended Description

This is gcc pr 47579:

#include
extern void b1(), b2();
void foo(const std::vector& v) { if (v.size() == 0) b1(); else b2(); }

which demonstrates a really neat missed optimization:

define void @​_Z3fooRKSt6vectorIiSaIiEE(%"class.std::vector"* nocapture %v) {
entry:
%tmp2.i = getelementptr inbounds %"class.std::vector"* %v, i64 0, i32 0, i64 8
%0 = bitcast i8* %tmp2.i to i32**
%tmp3.i = load i32** %0, align 8, !tbaa !​0
%tmp5.i = bitcast %"class.std::vector"* %v to i32**
%tmp6.i = load i32** %tmp5.i, align 8, !tbaa !​0
%sub.ptr.lhs.cast.i = ptrtoint i32* %tmp3.i to i64
%sub.ptr.rhs.cast.i = ptrtoint i32* %tmp6.i to i64
%sub.ptr.sub.i = sub i64 %sub.ptr.lhs.cast.i, %sub.ptr.rhs.cast.i
%cmp = icmp ult i64 %sub.ptr.sub.i, 4
br i1 %cmp, label %if.then, label %if.else
[...]

Is the difference between the pointers (%tmp3.i, %tmp6.i) less than 4? Well, the pointers are aligned so that's always true. However, LLVM doesn't know that.

We mark pointer alignment at the use (load/store) instead of the definition. In this case, I think we should add an alignment field to ptrtoint. Clang could set this based on user annotations or the minimum alignment of the type.

If we need a source annotation to make this work, we should make sure libc++ has it too.

[lattner]

This shouldn't need a source annotation. It is almost certainly a result of transforming "(sdiv exact a, b) == 0" to eliminate the compare. That instcombine xform should be updated to be more aggressive for exact sdivs.

[nlewycky]

Reduced testcase:

define i1 @​test(i32 %x, i32 %y) {
%A = sub i32 %x, %y
%B = sdiv exact i32 %A, 4
%C = icmp eq i32 %B, 0
ret i1 %C
}

which goes through instcombine in these steps:

1. replace %B with "%B = ashr i32 %A, 2".
2. add "%B.mask = and i32 %A, -4" and replace %C with "%C = icmp eq i32 %B.mask, 0". DCE %B.
3. replace %C with "%C = icmp ult i32 %A, 4". DCE %B.mask.

We can't just add the icmp + sdiv exact transform because instcombine visits %B first (replacing it with an ashr) and bug 8862 isn't fixed yet.

[llvmbot]

I didn't get want you want to do with the reduced testcase. Do you want to turn
this
%B = sdiv exact i32 %A, 4
%C = icmp eq i32 %B, 0
into
%C = icmp eq i32 %A, 0
?

[nlewycky]

Further:
%C = icmp eq i32 %x, %y
.

[llvmbot]

OK, but existing logic would take care of that last step :)

[lattner]

Comment #​2 is now simplified into:

define i1 @​test(i32 %x, i32 %y) {
%C = icmp eq i32 %x, %y
ret i1 %C
}

We now compile the original testcase down to this:

define void @​_Z3fooRKSt6vectorIiSaIiEE(%"class.std::vector"* nocapture %v) ssp {
entry:
%tmp2.i = getelementptr inbounds %"class.std::vector"* %v, i64 0, i32 0, i64 8
%0 = bitcast i8* %tmp2.i to i32**
%tmp3.i = load i32** %0, align 8, !tbaa !​0
%tmp5.i = bitcast %"class.std::vector"* %v to i32**
%tmp6.i = load i32** %tmp5.i, align 8, !tbaa !​0
%cmp = icmp eq i32* %tmp3.i, %tmp6.i
br i1 %cmp, label %if.then, label %if.else

so this looks fixed!

[lattner]

In assembly, this is:

__Z3fooRKSt6vectorIiSaIiEE: ## @​_Z3fooRKSt6vectorIiSaIiEE
pushq %rax
movq 8(%rdi), %rax
cmpq (%rdi), %rax
jne LBB0_2

which seems pretty nice. :) GCC 4.2 produces:

__Z3fooRKSt6vectorIiSaIiEE:
movq 8(%rdi), %rax
subq (%rdi), %rax
sarq $2, %rax
testq %rax, %rax
jne L2

Just like GCC llvm/llvm-bugzilla-archive#47579 indicates.