Unnecessary copy when constructing arrays from returned arrays?

[bwesterb]

I want to construct a big array by concatenating smaller arrays returned by other functions. As a simple example:

pub fn g(f: &Fn() -> [u64;40]) -> [u64;80] {
    let a = f();
    let b = f();
    let mut ret = [0u64;80];
    ret[0..40].copy_from_slice(&a[..]);
    ret[40..80].copy_from_slice(&b[..]);
    ret
}

Rust nightly generates a call to memcpy.

Is there a way to prevent this memcpy? Am I missing obvious other way to write this function?

Of course one could rewrite the called function f to take a &mut [u64] instead of returning the array, but that removes compile-time checks on the length and introduces bounds checks. Using &mut [u64;40] as an "out" argument solves that problem, but then I don't see a safe way to get two &mut [u64;40] into [u64;80] without using transmute.

(Background: I'm implementing the XMSSMT hash-based signature in Rust, which involves concatenating lots of hashes. The usual Rust hash library returns an array (actually a GenericArray) instead of using a &mut [u64;...] parameter which led me to believe that the copy could be optimised away.)

[ecstatic-morse]

What you're looking for is commonly known as "named return value optimization". It's currently not implemented in rust but progress is being tracked in #32966.

In the meantime, if you are willing to take an out-param (&mut [u64; 80]), it's not too hard to convert to an array reference with an arbitrary size and offset. I've used arrayref for this purpose in the (distant) past. You would also want to change your function parameter to use an out-param (f: impl Fn(&mut [u64; 40])).

[nikic]

LLVM isn't very good at optimizing away memcpy's. I think it would be possible to eliminate one of the memcpy's by extending call slot optimization to work with a destination that is a GEP of alloca.

[nikic]

Together with a few other changes, https://reviews.llvm.org/D89623 will remove the last memcpy in g1 and g4. It also removes one of the memcpys in g3.

g2 would require mutable noalias to be reenabled.

[nikic]

On beta we generate 1, 2, 2, 1 memcpys. On nightly we generate 1, 2, 1, 0 memcpys. With -Z mutable-noalias we generate 1, 0, 1, 0 memcpys.

Not sure why the one memcpy in the first function is still there. It gets dropped when I run -memcpyopt on the final IR, so presumably a phase ordering issue.

[nikic]

For g the IR after -memcpyopt is:

; Function Attrs: nounwind nonlazybind
define void @_ZN6test111g17h45fb2453d8cc5713E([80 x i64]* noalias nocapture sret([80 x i64]) dereferenceable(640) %0, {}* nonnull align 1 %1, [3 x i64]* noalias nocapture readonly align 8 dereferenceable(24) %2) unnamed_addr #0 {
  %4 = alloca [40 x i64], align 8
  %5 = alloca [40 x i64], align 8
  %6 = bitcast [40 x i64]* %5 to i8*
  call void @llvm.lifetime.start.p0i8(i64 320, i8* nonnull %6)
  %7 = getelementptr inbounds [3 x i64], [3 x i64]* %2, i64 0, i64 3
  %8 = bitcast i64* %7 to void ([40 x i64]*, {}*)**
  %9 = load void ([40 x i64]*, {}*)*, void ([40 x i64]*, {}*)** %8, align 8, !invariant.load !2, !nonnull !2
  %10 = bitcast [80 x i64]* %0 to [40 x i64]*
  call void %9([40 x i64]* noalias nocapture nonnull sret([40 x i64]) dereferenceable(320) %10, {}* nonnull align 1 %1) #5
  %11 = bitcast [40 x i64]* %4 to i8*
  call void @llvm.lifetime.start.p0i8(i64 320, i8* nonnull %11)
  call void %9([40 x i64]* noalias nocapture nonnull sret([40 x i64]) dereferenceable(320) %4, {}* nonnull align 1 %1) #5
  %12 = bitcast [80 x i64]* %0 to i8*
  %13 = getelementptr i8, i8* %12, i64 320
  call void @llvm.memset.p0i8.i64(i8* align 8 %13, i8 0, i64 320, i1 false)
  %14 = getelementptr inbounds [80 x i64], [80 x i64]* %0, i64 0, i64 40
  %15 = bitcast i64* %14 to i8*
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 dereferenceable(320) %15, i8* nonnull align 8 dereferenceable(320) %11, i64 320, i1 false) #5
  call void @llvm.lifetime.end.p0i8(i64 320, i8* nonnull %11)
  call void @llvm.lifetime.end.p0i8(i64 320, i8* nonnull %6)
  ret void
}

The problem is that we have a clobbering memset which is dead, but will only be eliminated by the following DSE pass.

[nikic]

The memcpy in the first example should be eliminated by llvm/llvm-project@9080444 and llvm/llvm-project@2902bde (possibly the first one isn't needed) by side-stepping the phase ordering issue. MemCpyOpt happened to implement partial DSE for this particular case already.