背景(执行此操作可能有更好的方法):
我正在开发一个Julia库,在其中我可以手动管理内存。我mmap
一个大块,然后将其像栈一样对待:函数将指针作为参数接收,如果它们分配了一个对象,则它们将向被调用者返回一个递增的指针。
如果被调用方本身完全返回了指针,则该被调用方本身可能不会增加该指针,而只是返回它收到的原始指针。
每当函数返回时,就我的库而言,超出指针当前位置的任何内容都是垃圾。我希望LLVM意识到这一点,以便它可以优化所有不必要的存储。
这是一个演示该问题的测试用例:取两个长度为16的向量的点积。首先,进行一些初步加载(这些是我的库,位于GitHub上:SIMDPirates,PaddedMatrices):
using SIMDPirates, PaddedMatrices
using SIMDPirates: lifetime_start, lifetime_end
b = @Mutable rand(16);
c = @Mutable rand(16);
a = FixedSizeVector{16,Float64}(undef);
b' * c # dot product
# 3.9704768664758925
当然,如果我们手工编写一个点产品,我们将永远不会包括商店,但是当您尝试为任意模型生成代码时,要做到这一点要困难得多。因此,我们将编写一个存储在指针中的坏点积:
@inline function storedot!(ptr, b, c)
ptrb = pointer(b)
ptrc = pointer(c)
ptra = ptr
for _ ∈ 1:4
vb = vload(Vec{4,Float64}, ptrb)
vc = vload(Vec{4,Float64}, ptrc)
vstore!(ptra, vmul(vb, vc))
ptra += 32
ptrb += 32
ptrc += 32
end
ptra = ptr
out = vload(Vec{4,Float64}, ptra)
for _ ∈ 1:3
ptra += 32
out = vadd(out, vload(Vec{4,Float64}, ptra))
end
vsum(out)
end
与循环一次并使用
fma
指令累积点积不同,我们循环两次,首先计算和存储乘积,然后求和。我想要的是让编译器找出正确的东西。
这是下面两个版本。第一种使用llvm lifetime内部函数尝试将指针内容声明为垃圾内容:
function test_lifetime!(a, b, c)
ptra = pointer(a)
lifetime_start(Val(128), ptra)
d = storedot!(ptra, b, c)
lifetime_end(Val(128), ptra)
d
end
第二个而不是使用预分配的指针,而是使用alloca创建一个指针
function test_alloca(b, c)
ptra = SIMDPirates.alloca(Val(16), Float64)
storedot!(ptra, b, c)
end
两者当然都能得到正确的答案
test_lifetime!(a, b, c)
# 3.9704768664758925
test_alloca(b, c)
# 3.9704768664758925
但是只有alloca版本是正确优化的。
alloca的程序集(AT&T语法):
# julia> @code_native debuginfo=:none test_alloca(b, c)
.text
vmovupd (%rsi), %ymm0
vmovupd 32(%rsi), %ymm1
vmovupd 64(%rsi), %ymm2
vmovupd 96(%rsi), %ymm3
vmulpd (%rdi), %ymm0, %ymm0
vfmadd231pd 32(%rdi), %ymm1, %ymm0 # ymm0 = (ymm1 * mem) + ymm0
vfmadd231pd 64(%rdi), %ymm2, %ymm0 # ymm0 = (ymm2 * mem) + ymm0
vfmadd231pd 96(%rdi), %ymm3, %ymm0 # ymm0 = (ymm3 * mem) + ymm0
vextractf128 $1, %ymm0, %xmm1
vaddpd %xmm1, %xmm0, %xmm0
vpermilpd $1, %xmm0, %xmm1 # xmm1 = xmm0[1,0]
vaddsd %xmm1, %xmm0, %xmm0
vzeroupper
retq
nopw %cs:(%rax,%rax)
nopl (%rax,%rax)
如您所见,内存没有移动,我们有一个
vmul
和三个vfmadd
来计算点积(在进行向量归约之前)。不幸的是,这不是我们从尝试使用生命周期的版本中得到的:
# julia> @code_native debuginfo=:none test_lifetime!(a, b, c)
.text
vmovupd (%rdx), %ymm0
vmulpd (%rsi), %ymm0, %ymm0
vmovupd %ymm0, (%rdi)
vmovupd 32(%rdx), %ymm1
vmulpd 32(%rsi), %ymm1, %ymm1
vmovupd %ymm1, 32(%rdi)
vmovupd 64(%rdx), %ymm2
vmulpd 64(%rsi), %ymm2, %ymm2
vmovupd %ymm2, 64(%rdi)
vmovupd 96(%rdx), %ymm3
vaddpd %ymm0, %ymm1, %ymm0
vaddpd %ymm0, %ymm2, %ymm0
vfmadd231pd 96(%rsi), %ymm3, %ymm0 # ymm0 = (ymm3 * mem) + ymm0
vextractf128 $1, %ymm0, %xmm1
vaddpd %xmm1, %xmm0, %xmm0
vpermilpd $1, %xmm0, %xmm1 # xmm1 = xmm0[1,0]
vaddsd %xmm1, %xmm0, %xmm0
vzeroupper
retq
nopw %cs:(%rax,%rax)
nop
在这里,我们只得到了如下所示的循环:
vmul
,存储到内存中,然后是vadd
。但是,这4个之一已被替换为fmadd
。另外,它不会从任何商店读取数据,因此我认为无效商店消除通行证应该没有问题。
关联的llvm:
;; julia> @code_llvm debuginfo=:none test_alloca(b, c)
define double @julia_test_alloca_17840(%jl_value_t addrspace(10)* nonnull align 8 dereferenceable(128), %jl_value_t addrspace(10)* nonnull align 8 dereferenceable(128)) {
top:
%2 = addrspacecast %jl_value_t addrspace(10)* %0 to %jl_value_t addrspace(11)*
%3 = addrspacecast %jl_value_t addrspace(11)* %2 to %jl_value_t*
%4 = addrspacecast %jl_value_t addrspace(10)* %1 to %jl_value_t addrspace(11)*
%5 = addrspacecast %jl_value_t addrspace(11)* %4 to %jl_value_t*
%ptr.i20 = bitcast %jl_value_t* %3 to <4 x double>*
%res.i21 = load <4 x double>, <4 x double>* %ptr.i20, align 8
%ptr.i18 = bitcast %jl_value_t* %5 to <4 x double>*
%res.i19 = load <4 x double>, <4 x double>* %ptr.i18, align 8
%res.i17 = fmul fast <4 x double> %res.i19, %res.i21
%6 = bitcast %jl_value_t* %3 to i8*
%7 = getelementptr i8, i8* %6, i64 32
%8 = bitcast %jl_value_t* %5 to i8*
%9 = getelementptr i8, i8* %8, i64 32
%ptr.i20.1 = bitcast i8* %7 to <4 x double>*
%res.i21.1 = load <4 x double>, <4 x double>* %ptr.i20.1, align 8
%ptr.i18.1 = bitcast i8* %9 to <4 x double>*
%res.i19.1 = load <4 x double>, <4 x double>* %ptr.i18.1, align 8
%res.i17.1 = fmul fast <4 x double> %res.i19.1, %res.i21.1
%10 = getelementptr i8, i8* %6, i64 64
%11 = getelementptr i8, i8* %8, i64 64
%ptr.i20.2 = bitcast i8* %10 to <4 x double>*
%res.i21.2 = load <4 x double>, <4 x double>* %ptr.i20.2, align 8
%ptr.i18.2 = bitcast i8* %11 to <4 x double>*
%res.i19.2 = load <4 x double>, <4 x double>* %ptr.i18.2, align 8
%res.i17.2 = fmul fast <4 x double> %res.i19.2, %res.i21.2
%12 = getelementptr i8, i8* %6, i64 96
%13 = getelementptr i8, i8* %8, i64 96
%ptr.i20.3 = bitcast i8* %12 to <4 x double>*
%res.i21.3 = load <4 x double>, <4 x double>* %ptr.i20.3, align 8
%ptr.i18.3 = bitcast i8* %13 to <4 x double>*
%res.i19.3 = load <4 x double>, <4 x double>* %ptr.i18.3, align 8
%res.i17.3 = fmul fast <4 x double> %res.i19.3, %res.i21.3
%res.i12 = fadd fast <4 x double> %res.i17.1, %res.i17
%res.i12.1 = fadd fast <4 x double> %res.i17.2, %res.i12
%res.i12.2 = fadd fast <4 x double> %res.i17.3, %res.i12.1
%vec_2_1.i = shufflevector <4 x double> %res.i12.2, <4 x double> undef, <2 x i32> <i32 0, i32 1>
%vec_2_2.i = shufflevector <4 x double> %res.i12.2, <4 x double> undef, <2 x i32> <i32 2, i32 3>
%vec_2.i = fadd <2 x double> %vec_2_1.i, %vec_2_2.i
%vec_1_1.i = shufflevector <2 x double> %vec_2.i, <2 x double> undef, <1 x i32> zeroinitializer
%vec_1_2.i = shufflevector <2 x double> %vec_2.i, <2 x double> undef, <1 x i32> <i32 1>
%vec_1.i = fadd <1 x double> %vec_1_1.i, %vec_1_2.i
%res.i = extractelement <1 x double> %vec_1.i, i32 0
ret double %res.i
}
它消除了
alloca
和store
。但是,尝试使用生命周期:
;; julia> @code_llvm debuginfo=:none test_lifetime!(a, b, c)
define double @"julia_test_lifetime!_17839"(%jl_value_t addrspace(10)* nonnull align 8 dereferenceable(128), %jl_value_t addrspace(10)* nonnull align 8 dereferenceable(128), %jl_value_t addrspace(10)* nonnull align 8 dereferenceable(128)) {
980 top:
%3 = addrspacecast %jl_value_t addrspace(10)* %0 to %jl_value_t addrspace(11)*
%4 = addrspacecast %jl_value_t addrspace(11)* %3 to %jl_value_t*
%.ptr = bitcast %jl_value_t* %4 to i8*
call void @llvm.lifetime.start.p0i8(i64 256, i8* %.ptr)
%5 = addrspacecast %jl_value_t addrspace(10)* %1 to %jl_value_t addrspace(11)*
%6 = addrspacecast %jl_value_t addrspace(11)* %5 to %jl_value_t*
%7 = addrspacecast %jl_value_t addrspace(10)* %2 to %jl_value_t addrspace(11)*
%8 = addrspacecast %jl_value_t addrspace(11)* %7 to %jl_value_t*
%ptr.i22 = bitcast %jl_value_t* %6 to <4 x double>*
%res.i23 = load <4 x double>, <4 x double>* %ptr.i22, align 8
%ptr.i20 = bitcast %jl_value_t* %8 to <4 x double>*
%res.i21 = load <4 x double>, <4 x double>* %ptr.i20, align 8
%res.i19 = fmul fast <4 x double> %res.i21, %res.i23
%ptr.i18 = bitcast %jl_value_t* %4 to <4 x double>*
store <4 x double> %res.i19, <4 x double>* %ptr.i18, align 8
%9 = getelementptr i8, i8* %.ptr, i64 32
%10 = bitcast %jl_value_t* %6 to i8*
%11 = getelementptr i8, i8* %10, i64 32
%12 = bitcast %jl_value_t* %8 to i8*
%13 = getelementptr i8, i8* %12, i64 32
%ptr.i22.1 = bitcast i8* %11 to <4 x double>*
%res.i23.1 = load <4 x double>, <4 x double>* %ptr.i22.1, align 8
%ptr.i20.1 = bitcast i8* %13 to <4 x double>*
%res.i21.1 = load <4 x double>, <4 x double>* %ptr.i20.1, align 8
%res.i19.1 = fmul fast <4 x double> %res.i21.1, %res.i23.1
%ptr.i18.1 = bitcast i8* %9 to <4 x double>*
store <4 x double> %res.i19.1, <4 x double>* %ptr.i18.1, align 8
%14 = getelementptr i8, i8* %.ptr, i64 64
%15 = getelementptr i8, i8* %10, i64 64
%16 = getelementptr i8, i8* %12, i64 64
%ptr.i22.2 = bitcast i8* %15 to <4 x double>*
%res.i23.2 = load <4 x double>, <4 x double>* %ptr.i22.2, align 8
%ptr.i20.2 = bitcast i8* %16 to <4 x double>*
%res.i21.2 = load <4 x double>, <4 x double>* %ptr.i20.2, align 8
%res.i19.2 = fmul fast <4 x double> %res.i21.2, %res.i23.2
%ptr.i18.2 = bitcast i8* %14 to <4 x double>*
store <4 x double> %res.i19.2, <4 x double>* %ptr.i18.2, align 8
%17 = getelementptr i8, i8* %10, i64 96
%18 = getelementptr i8, i8* %12, i64 96
%ptr.i22.3 = bitcast i8* %17 to <4 x double>*
%res.i23.3 = load <4 x double>, <4 x double>* %ptr.i22.3, align 8
%ptr.i20.3 = bitcast i8* %18 to <4 x double>*
%res.i21.3 = load <4 x double>, <4 x double>* %ptr.i20.3, align 8
%res.i19.3 = fmul fast <4 x double> %res.i21.3, %res.i23.3
%res.i13 = fadd fast <4 x double> %res.i19.1, %res.i19
%res.i13.1 = fadd fast <4 x double> %res.i19.2, %res.i13
%res.i13.2 = fadd fast <4 x double> %res.i19.3, %res.i13.1
%vec_2_1.i = shufflevector <4 x double> %res.i13.2, <4 x double> undef, <2 x i32> <i32 0, i32 1>
%vec_2_2.i = shufflevector <4 x double> %res.i13.2, <4 x double> undef, <2 x i32> <i32 2, i32 3>
%vec_2.i = fadd <2 x double> %vec_2_1.i, %vec_2_2.i
%vec_1_1.i = shufflevector <2 x double> %vec_2.i, <2 x double> undef, <1 x i32> zeroinitializer
%vec_1_2.i = shufflevector <2 x double> %vec_2.i, <2 x double> undef, <1 x i32> <i32 1>
%vec_1.i = fadd <1 x double> %vec_1_1.i, %vec_1_2.i
%res.i = extractelement <1 x double> %vec_1.i, i32 0
call void @llvm.lifetime.end.p0i8(i64 256, i8* %.ptr)
ret double %res.i
}
终生开始和终生存在,但四个存储中的三个也是如此。
我可以确认第四家商店不见了:
julia> fill!(a, 0.0)'
1×16 LinearAlgebra.Adjoint{Float64,FixedSizeArray{Tuple{16},Float64,1,Tuple{1},16}}:
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
julia> test_lifetime!(a, b, c)
3.9704768664758925
julia> a'
1×16 LinearAlgebra.Adjoint{Float64,FixedSizeArray{Tuple{16},Float64,1,Tuple{1},16}}:
0.157677 0.152386 0.507693 0.00696963 0.0651712 0.241523 0.129705 0.175321 0.236032 0.0314141 0.199595 0.404153 0.0 0.0 0.0 0.0
虽然没有指定生存期,但所有四个当然都必须发生:
julia> function teststore!(a, b, c)
storedot!(pointer(a), b, c)
end
test_store! (generic function with 1 method)
julia> fill!(a, 0.0); test_store!(a, b, c)
3.9704768664758925
julia> a'
1×16 LinearAlgebra.Adjoint{Float64,FixedSizeArray{Tuple{16},Float64,1,Tuple{1},16}}:
0.157677 0.152386 0.507693 0.00696963 0.0651712 0.241523 0.129705 0.175321 0.236032 0.0314141 0.199595 0.404153 0.256597 0.0376403 0.889331 0.479269
但是,与
alloca
不同,它无法消除所有4家商店。作为引用,我使用LLVM 8.0.1构建了Julia。
由于两个原因,我没有使用
alloca
代替堆栈指针:a)使用
alloca
创建的指针调用非内联函数时出现错误。用其他指针替换这些指针会使错误消失,以及内联函数也是如此。如果有办法解决这个问题,我至少可以在更多地方使用alloca
。b)我无法找到如何让Julia在分配给alloca的每个线程中拥有超过4MB的堆栈。我认为4MB对于我的许多用例来说已经足够了,但不是全部。如果我打算编写相当通用的软件,那么这样的限制就不是很大。
我的问题:
alloca
相比,由于某些原因,优化器受到的限制更大? 最佳答案
最初发布问题后,我在以下项目符号中进行了编辑:
原来正是这个问题。如果
ptra
别名为b
或c
,则排除存储将是无效的。改为:
a = @Mutable rand(48);
a[Static(1:16)]' * a[Static(17:32)]
# 2.5295415040590425
function test_lifetime!(a)
ptra = pointer(a)
b = PtrVector{16,Float64,16}(ptra)
c = PtrVector{16,Float64,16}(ptra + 128)
ptra += 256
lifetime_start(Val(128), ptra)
d = storedot!(ptra, b, c)
lifetime_end(Val(128), ptra)
d
end
test_lifetime!(a)
# 2.5295415040590425
实际上会淘汰所有商店吗:
# julia> @code_native debuginfo=:none test_lifetime!(a)
.text
vmovupd 128(%rdi), %ymm0
vmovupd 160(%rdi), %ymm1
vmovupd 192(%rdi), %ymm2
vmovupd 224(%rdi), %ymm3
vmulpd (%rdi), %ymm0, %ymm0
vfmadd231pd 32(%rdi), %ymm1, %ymm0 # ymm0 = (ymm1 * mem) + ymm0
vfmadd231pd 64(%rdi), %ymm2, %ymm0 # ymm0 = (ymm2 * mem) + ymm0
vfmadd231pd 96(%rdi), %ymm3, %ymm0 # ymm0 = (ymm3 * mem) + ymm0
vextractf128 $1, %ymm0, %xmm1
vaddpd %xmm1, %xmm0, %xmm0
vpermilpd $1, %xmm0, %xmm1 # xmm1 = xmm0[1,0]
vaddsd %xmm1, %xmm0, %xmm0
vzeroupper
retq
nop
因此,答案是:LLVM知道alloca指针不能为输入之一做别名,因此可以安全地不进行存储。
我在问题中想要的行为(不进行别名检查)将是不安全的/可能会得到不正确的结果:
ptra
的存储区之一可能会更改b
或c
的内容。因此,实际上必须执行除最后一家商店以外的所有商店。在上一个测试中,我定义了
a
,b
和c
距同一指针的偏移量不同,从而确保将存储在a
中的内容更改为b
或c
,从而使LLVM实际上消除了存储。完美的!
关于optimization - 如何告诉LLVM可以优化远距仓储?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58841260/