Redundant copy of arg into alloca can't be eliminated when there are reads through un-SROA-able pointers

[jckarter]

Bugzilla Link	31697
Version	trunk
OS	All
CC	@atrick,@comex

Extended Description

If you have a situation where memory pointed to by a readonly argument %x is copied to a local alloca %y and then %y is projected from, then LLVM normally eliminates the unnecessary copy. This IR:

declare void @​llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i32, i1)
declare void @​llvm.lifetime.start(i64, i8*)
declare void @​llvm.lifetime.end(i64, i8*)

define i32 @​copy_then_extract({ i32,i32,i32,i32 }* noalias nocapture readonly dereferenceable(16) %x, i32 %n) {
entry:
%y = alloca { i32, i32, i32, i32 }, align 16
%x0p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 0
%x0 = load i32, i32* %x0p
%x1p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 1
%x1 = load i32, i32* %x1p
%x2p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 2
%x2 = load i32, i32* %x2p
%x3p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 3
%x3 = load i32, i32* %x3p

%yi8 = bitcast { i32, i32, i32, i32 }* %y to i8*
call void @​llvm.lifetime.start(i64 16, i8* %yi8)

%y0p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 0
store i32 %x0, i32* %y0p
%y1p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 1
store i32 %x1, i32* %y1p
%y2p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 2
store i32 %x2, i32* %y2p
%y3p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 3
store i32 %x3, i32* %y3p

%ya = bitcast i8* %yi8 to i32*
%ya2p = getelementptr inbounds i32, i32* %ya, i64 2
%y2 = load i32, i32* %ya2p

%yi8_2 = bitcast { i32, i32, i32, i32 }* %y to i8*
call void @​llvm.lifetime.end(i64 16, i8* %yi8_2)
ret i32 %y2
}

reduces to:

define i32 @​copy_then_extract({ i32, i32, i32, i32 }* noalias nocapture readonly dereferenceable(16) %x, i32 %n) local_unnamed_addr #​0 {
entry:
%x2p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i64 0, i32 2
%x2 = load i32, i32* %x2p, align 4
ret i32 %x2
}

However, if %ya2p becomes a dynamic GEP by changing i64 2 to i64 %n, then the bitcast can no longer be reduced since that's not valid against a struct. This ends up completely blocking copy forwarding. This IR:

declare void @​llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i32, i1)
declare void @​llvm.lifetime.start(i64, i8*)
declare void @​llvm.lifetime.end(i64, i8*)

define i32 @​copy_then_extract({ i32,i32,i32,i32 }* noalias nocapture readonly dereferenceable(16) %x, i32 %n) {
entry:
%y = alloca { i32, i32, i32, i32 }, align 16
%x0p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 0
%x0 = load i32, i32* %x0p
%x1p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 1
%x1 = load i32, i32* %x1p
%x2p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 2
%x2 = load i32, i32* %x2p
%x3p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %x, i32 0, i32 3
%x3 = load i32, i32* %x3p

%yi8 = bitcast { i32, i32, i32, i32 }* %y to i8*
call void @​llvm.lifetime.start(i64 16, i8* %yi8)

%y0p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 0
store i32 %x0, i32* %y0p
%y1p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 1
store i32 %x1, i32* %y1p
%y2p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 2
store i32 %x2, i32* %y2p
%y3p = getelementptr inbounds { i32, i32, i32, i32 }, { i32, i32, i32, i32 }* %y, i32 0, i32 3
store i32 %x3, i32* %y3p

%ya = bitcast i8* %yi8 to i32*
%ya2p = getelementptr inbounds i32, i32* %ya, i32 %n
%y2 = load i32, i32* %ya2p

%yi8_2 = bitcast { i32, i32, i32, i32 }* %y to i8*
call void @​llvm.lifetime.end(i64 16, i8* %yi8_2)
ret i32 %y2
}

still keeps the unnecessary copy in the optimized IR:

define i32 @​copy_then_extract({ i32, i32, i32, i32 }* noalias nocapture readonly dereferenceable(16) %x, i32 %n) local_unnamed_addr #​1 {
entry:
%y = alloca <4 x i32>, align 16
%0 = bitcast { i32, i32, i32, i32 }* %x to <4 x i32>*
%1 = load <4 x i32>, <4 x i32>* %0, align 4
%yi8 = bitcast <4 x i32>* %y to i8*
call void @​llvm.lifetime.start(i64 16, i8* %yi8)
store <4 x i32> %1, <4 x i32>* %y, align 16
%2 = sext i32 %n to i64
%ya2p = getelementptr inbounds <4 x i32>, <4 x i32>* %y, i64 0, i64 %2
%y2 = load i32, i32* %ya2p, align 4
call void @​llvm.lifetime.end(i64 16, i8* %yi8)
ret i32 %y2
}

[llvmbot]

I am not sure why you say this is due to the bitcast.

The reason is the dynamic offset. This is what SROA says:

SROA function: copy_then_extract
SROA alloca: %y = alloca { i32, i32, i32, i32 }, align 16
Rewriting FCA loads and stores...
Can't analyze slices for alloca: %y = alloca { i32, i32, i32, i32 }, align 16
A pointer to this alloca escaped by:
%y2 = load i32, i32* %ya2p

In other words we can't create the slices for scalar promotion because we don't know the offset statically to split the structure.

With a constant offset it promotes the fields to scalars and correctly forwards the values.

If we want to optimize this we probably need to recognize the copy of the struct to an unmodified local and forward loads from the local to the argument values.

[atrick]

Just something to keep in mind... I'm not sure 'readonly' on the argument is relevant here since 'readonly' only prohibits writes through that pointer. I think that's more useful on the caller side when the function is 'argmemonly'. The optimization Joe wants is probably limited to functions that don't have any opaque code between the copy operation and the copy's use.

[jckarter]

You're right, Andy, noalias nocapture seems like the more important thing. It should be visible from the function implementation that it doesn't write through the argument, and noalias should assume that nobody else does either (AIUI). Adam, sorry if I'm misunderstanding what's going on; I had assumed that LLVM had a copy forwarding pass, but it could be that what I'm seeing in the "good" case just falls out from SROA.

[atrick]

"copy forward" is handled by GVN, but I think it only understands scalars.

[llvmbot]

Looks like we already do a similar forwarding for const global data in InstCombine to get around the copy that was alloca'd:

http://llvm.org/docs/doxygen/html/InstCombineLoadStoreAlloca_8cpp_source.html#l00279

Assuming we can cheaply recognize the copy (it should be trivial after vectorization) we may be able to piggyback on this.