那些遇到过的问题

如何告诉LLVM它可以优化离店？

Chr*_*rod 6 optimization llvm alloca julia llvm-ir

背景（可能有更好的方法可以做到这一点）：我正在开发一个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
Run Code Online (Sandbox Code Playgroud)

当然，如果我们手工编写一个点产品，我们将永远不会包括商店，但是当您尝试为任意模型生成代码时，要做起来就困难得多。因此，我们将编写一个存储在指针中的坏点积：

@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
Run Code Online (Sandbox Code Playgroud)

我们没有循环一次并用fma指令累积点积，而是循环了两次，首先计算和存储乘积，然后求和。我想要的是让编译器找出正确的东西。

这是下面两个版本。第一个使用llvm 生命周期内在函数尝试将指针内容声明为垃圾内容：

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
Run Code Online (Sandbox Code Playgroud)

第二个而不是使用预分配的指针，而是使用alloca创建一个指针

function test_alloca(b, c)
    ptra = SIMDPirates.alloca(Val(16), Float64)
    storedot!(ptra, b, c)
end
Run Code Online (Sandbox Code Playgroud)

当然都可以得到正确的答案

test_lifetime!(a, b, c)
# 3.9704768664758925
test_alloca(b, c)
# 3.9704768664758925
Run Code Online (Sandbox Code Playgroud)

但是只有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)
Run Code Online (Sandbox Code Playgroud)

如您所见，内存中没有移动，并且我们需要一秒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
Run Code Online (Sandbox Code Playgroud)

在这里，我们只获得写成的循环：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
}
Run Code Online (Sandbox Code Playgroud)

它消除了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
}
Run Code Online (Sandbox Code Playgroud)

终生开始和终生存在，但四个存储中的三个也是如此。我可以确认第四家商店不见了：

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
Run Code Online (Sandbox Code Playgroud)

虽然没有指定生命周期，但是这四个当然必须发生：

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
Run Code Online (Sandbox Code Playgroud)

但是，与相比alloca，它无法消除所有4家商店。

作为参考，我使用LLVM 8.0.1构建了Julia。

alloca由于两个原因，我没有使用堆栈指针代替：a）使用alloca-created指针调用非内联函数时出现错误。用其他指针替换这些指针会使错误消失，以及内联函数也是如此。如果有解决方法，我至少可以alloca在更多地方使用。b）我不知道如何使Julia能够为alloca提供每个线程超过4MB的堆栈。我认为4MB对于我的许多用例来说已经足够了，但不是全部。如果我打算编写相当通用的软件，那么这样的限制就不是很大。

我的问题：

  • 有什么方法可以使LLVM复制它在alloca中显示的行为？
  • 我做的事情是否正确，并且允许LLVM允许显示所需的行为，但是由于某种原因，与之相比，优化器受到的限制更大alloca？
  • 因此可以期望在将来的版本中有所改进。
  • 关于如何处理此问题，更好地启用优化器的建议，或者我总体上缺少的建议？
  • 假设只删除了最后一个，是否假设它们可能会混叠？

Chr*_*rod 5

I edited in the following bullet after originally posting the question:

  • Given that only the last is elided, is the problem that it assumes they may alias?

Turns out it was exactly this problem. If ptra did alias b or c, eliding the stores would have been invalid.

Writing instead:

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
Run Code Online (Sandbox Code Playgroud)

Does in fact elide all the stores:

# 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
Run Code Online (Sandbox Code Playgroud)

So the answer is: LLVM knows the alloca pointer cannot alias one of the inputs, therefore it is safe not to store. The behavior I wanted in my question (without an alias check) would have been unsafe / liable to get incorrect results: one of the stores into ptra could change the contents of b or c. Hence, all but the very last store actually do have to be performed.

In this last test, I defined each of a, b, and c at different offsets from the same pointer, so that stores into a are guaranteed not to change b or c, letting LLVM actually eliminate the stores. Perfect!

归档时间：

查看次数：

66 次

最近记录：

6 年，3 月 前
相关归档
朱莉娅的"=="和"==="比较运算符有什么区别？ 12
通过与BinarySearch的差异查找最接近的索引 9
Symfony 2 - 如何在每次加载页面时禁用查询用户？ 8
优化Haskell中的部分计算 8
使用javascript设置样式值时使用数字或字符串 6
由gcc生成的虚拟movup 4
将 Julia 数据框列标题更改为小写？ 4
我们可以在Obj C元素上保留没有getter和setter的属性吗？ 2
Julia中的exp函数求值为0 0
Fantasy Football的Python PuLP优化问题，如何添加某些条件约束？ 0
难疑归档
如何从JavaScript中删除数组中的特定元素？ 7655
如何在Java中调用另一个构造函数？ 2144
如何将Git存储库克隆到特定文件夹中？ 2083
动态创建元素的事件绑定？ 1677
如何删除GitHub上的提交？ 1619
如何知道对象在Python中是否具有属性 1491
尝试抓住加速我的代码？ 1463
如何使用OpenSSL创建自签名证书 1169
创建将T限制为枚举的通用方法 1122
如何在div中垂直对齐文本？ 1102