使用ymm寄存器作为“类内存”存储位置

Question

考虑以下在x86中的循环：

; on entry, rdi has the number of iterations
.top:
; some magic happens here to calculate a result in rax
mov [array + rdi * 8], rax ; store result in output array
dec rdi
jnz .top

很简单：某些东西在 rax 中计算出结果（未显示），然后我们将结果按相反的顺序存储到数组中，通过 rdi 进行索引。

我想改变上面的循环，使其不对内存进行任何写入（我们可以假设未显示的计算不会写入内存）。

只要 rdi 中的循环计数受限，我就可以使用 ymm 寄存器提供的充足空间（512字节）来保存这些值，但实际上这似乎很困难，因为您不能“索引”任意寄存器。

一种方法是始终将 ymm 寄存器的整个“数组”向左移动一个元素，然后将元素插入新释放的位置。

类似于这样：

vpermq  ymm3, ymm3, 10_01_00_11b ; left rotate ymm by qword
vpermq  ymm2, ymm2, 10_01_00_11b ; left rotate ymm by qword
vpermq  ymm1, ymm1, 10_01_00_11b ; left rotate ymm by qword
vpermq  ymm0, ymm0, 10_01_00_11b ; left rotate ymm by qword

vblenddd ymm3, ymm3, ymm2, 3     ; promote one qword of ymm2 to ymm3
vblenddd ymm2, ymm2, ymm1, 3     ; promote one qword of ymm1 to ymm2
vblenddd ymm1, ymm1, ymm0, 3     ; promote one qword of ymm0 to ymm1

pinsrq   xmm0, rax, 0  ; playing with mixed-VEX mode fire (see Peter's answer)

这只展示了处理16个寄存器中的四个，所以显然要处理全部16个寄存器需要很多代码（32条指令）。

有更好的方法吗？

虽然不可预测的分支是不可取的，但我们仍然可以考虑使用它们的解决方案。

- BeeOnRope

---

只是好奇这样做的动机是什么？我无法想象洗牌AVX寄存器会比L1击中更便宜。 - Mysticial

不，从性能角度来看，这绝对没有意义。动机是生成rax中的值的代码实际上是使用rdpmc读取性能计数器的小型微基准测试，对于处理内存读写的基准测试，没有任何与保存结果相关的“多余”内存活动非常好。我正在uarch-bench中使用这个“一次性”模式。@Mysticial - BeeOnRope

哦，我明白了。很不错。 - Mysticial

自修改代码在不写入内存的情况下是不可能实现的，而且你无法索引寄存器。你能否使用分支预测模式可学习的模式进行可预测的分支？否则，我认为没有比没有AVX512掩码vpbroadcastq和旋转掩码寄存器的巨大无分支暴力堆栈更好的选择了。 - Peter Cordes

coreboot有一个C编译器来完成这种事情。 - fuz

Answer 1

你不能将 vpinsrq 插入到 YMM 寄存器中。只有 XMM 目标可用，因此它不可避免地将完整的 YMM 寄存器的上半部分清零。它是AVX1作为128位指令的VEX版本引入的。 AVX2和AVX512没有将其升级为YMM / ZMM目的地。我猜想他们不想提供插入到高位的功能，而且提供一个仅查看imm8最低位的YMM版本会很奇怪。

你需要一个暂存寄存器，然后使用 vpblendd 将其混合到 YMM 中。或者（在 Skylake 或 AMD 上）使用旧版SSE版本以保持上半字节不变！ 在 Skylake 上，使用旧版SSE指令写入 XMM 寄存器会对整个寄存器产生错误依赖。你希望出现这种错误依赖。(我还没有测试过;它可能会触发某种合并uop) 但是在Haswell上则不需要，因为它会保存所有YMM寄存器的上半部分，进入“状态C”。

明显的解决方案是留下一个scratch reg来用于vmovq+vpblendd(而不是vpinsrq y,r,0)。这仍然需要2个uops，但vpblendd在英特尔CPU上不需要5号端口，如果有影响的话。movq使用端口5。如果你真的很缺空间，mm0..7 MMX寄存器可用。

---

降低成本

通过嵌套循环，我们可以分割工作。稍微展开内部循环，我们就可以大部分消除这部分成本。

例如，如果我们的内部循环产生4个结果，我们可以在内部循环中使用您的暴力堆栈方法在2或4个寄存器上，没有实际的展开（“魔术”负载只出现一次），从而带来适度的开销。3或4个微操作，可选地没有循环传递的依赖链。

; on entry, rdi has the number of iterations
.outer:
    mov       r15d, 3
.inner:
; some magic happens here to calculate a result in rax

%if  AVOID_SHUFFLES
    vmovdqa   xmm3, xmm2
    vmovdqa   xmm2, xmm1
    vmovdqa   xmm1, xmm0
    vmovq     xmm0, rax
%else
    vpunpcklqdq  xmm2, xmm1, xmm2        ; { high=xmm2[0], low=xmm1[0] }
    vmovdqa   xmm1, xmm0
    vmovq     xmm0, rax
%endif

    dec   r15d
    jnz   .inner

    ;; Big block only runs once per 4 iters of the inner loop, and is only ~12 insns.
    vmovdqa  ymm15, ymm14
    vmovdqa  ymm13, ymm12
    ...
    
    ;; shuffle the new 4 elements into the lowest reg we read here (ymm3 or ymm4)

%if  AVOID_SHUFFLES       ; inputs are in low element of xmm0..3
    vpunpcklqdq  xmm1, xmm1, xmm0     ; don't write xmm0..2: longer false dep chain next iter.  Or break it.
    vpunpcklqdq  xmm4, xmm3, xmm2
    vinserti128  ymm4, ymm1, xmm4, 1  ; older values go in the top half
    vpxor        xmm1, xmm1, xmm1     ; shorten false-dep chains

%else                     ; inputs are in xmm2[1,0], xmm1[0], and xmm0[0]
    vpunpcklqdq  xmm3, xmm0, xmm1     ; [ 2nd-newest,  newest ]
    vinserti128  ymm3, ymm2, xmm3, 1
    vpxor        xmm2, xmm2,xmm2   ; break loop-carried dep chain for the next iter
    vpxor        xmm1, xmm1,xmm1   ; and this, which feeds into the loop-carried chain
%endif

    sub   rdi, 4
    ja   .outer

奖励：这只需要AVX1（在AMD上更便宜，将256位向量保持在内部循环之外）。我们仍然获得12 x 4个qword的存储空间，而不是16 x 4个。那只是一个任意的数字。

有限展开

我们可以像这样展开内部循环：

.top:
    vmovdqa     ymm15, ymm14
    ...
    vmovdqa     ymm3, ymm2           ; 12x movdqa
    vinserti128 ymm2, ymm0, xmm1, 1

    magic
    vmovq       xmm0, rax
    magic
    vpinsrq     xmm0, rax, 1
    magic
    vmovq       xmm1, rax
    magic
    vpinsrq     xmm1, rax, 1

    sub         rdi, 4
    ja          .top

当我们退出循环时，ymm15..2和xmm1和0中充满了有价值的数据。如果它们在底部，它们将运行相同的次数，但ymm2将是xmm0和1的副本。跳转到循环入口而不执行第一次迭代上的vmovdqa操作是一个选择。

根据4x magic，这会消耗我们6个端口5的uops（movq + pinsrq），12个vmovdqa（没有执行单元）和1个vinserti128（再次是端口5）。因此，每4个magic需要19个uops，即4.75个uops。

您可以将vmovdqa + vinsert与第一个magic交错，或者在第一个magic之前/之后拆分它。您不能破坏xmm0，直到vinserti128之后，但如果您有一个空闲的整数寄存器，可以延迟vmovq。

更多嵌套

另一个循环嵌套层次或展开循环会大大减少vmovdqa指令的数量。 然而，将数据混洗到YMM寄存器中至少具有最小代价。 从GP regs加载xmm。

AVX512可以为我们提供更便宜的int-> xmm。 （它还允许写入YMM的所有4个元素）。 但我认为它不能避免需要展开或嵌套循环以避免每次都触及所有寄存器的需要。

---

PS：

对于洗牌累加器，我的第一个想法是将元素向左移动一位。但后来我意识到这样会有5个状态元素，而不是4个，因为我们有两个寄存器中的高低位以及新写入的xmm0。（并且可以使用vpalignr。）

这里留下一个例子，展示了使用vshufpd可以做什么：在一个寄存器中将低位移动到高位，并合并另一个寄存器中的高位作为新的低位。

    vshufpd   xmm2, xmm1,xmm2, 01b     ; xmm2[1]=xmm2[0], xmm2[0]=xmm1[1].  i.e. [ low(xmm2), high(xmm1) ]
    vshufpd   xmm1, xmm0,xmm1, 01b
    vmovq     xmm0, rax

---

AVX512：将向量作为内存索引

对于一般情况下将向量寄存器写入内存，我们可以使用vpbroadcastq zmm0{k1}, rax，并对其他zmm寄存器重复此操作，但需要不同的k1掩码。使用合并掩码（掩码只有一个位被设置）的广播操作可以让我们将数据索引存储到向量寄存器中，但我们需要为每个可能的目标寄存器编写一条指令。

创建掩码：

xor      edx, edx
bts      rdx, rcx          #  rdx = 1<<(rcx&63)
kmovq     k1, rdx
kshiftrq  k2, k1, 8
kshiftrq  k3, k1, 16
...

从 ZMM 寄存器中读取：

vpcompressq zmm0{k1}{z}, zmm1    ; zero-masking: zeros whole reg if no bits set
vpcompressq zmm0{k2},    zmm2    ; merge-masking
... repeat as many times as you have possible source regs

vmovq       rax, zmm0

（参见vpcompressq的文档：使用零屏蔽将所有元素清零，包括它所写入的元素以上的所有元素。）

为了隐藏vpcompressq的延迟，您可以将多个依赖链传递到多个临时向量中，然后在最后执行vpor xmm0, xmm0, xmm1。（其中一个向量将全为零，另一个将具有所选元素。）

根据此instatx64报告，SKX的延迟为3c，吞吐量为2c。

- Peter Cordes

Answer 2

以下是您可以考虑的几个选项：

展开循环

如果您展开循环（由于ymm寄存器中可用的存储空间仅限于64个qword，因此必须有限制迭代次数），则可以使用硬编码逻辑将来自rax的结果直接插入正确的位置，例如使用pinrsq或movq有时与洗牌组合以让您访问高位。每次迭代只需要1.25条指令，比32好得多！

垂直通道

您当前的洗牌解决方案可以描述为通过寄存器进行水平旋转，从ymm N的高qword向低qword进行传递。也就是说，在您的方案中，一个寄存器内的相邻元素在逻辑上是相邻的。相反，您可以进行垂直旋转，其中给定qword通道中的元素在寄存器ymm N-1和ymm N+1中的相同通道中的元素在逻辑上是相邻的。这避免了任何水平洗牌的需要，并且大部分移位只需要单个寄存器之间的mov操作。您只需要特殊处理第一个和最后一个寄存器，将您的元素包装到下一个通道中去。

类似于这样：

; shift all lanes "up"
vmovdqa ymm15, ymm3
vmovdqa  ymm3, ymm2
vmovdqa  ymm2, ymm1
vmovdqa  ymm1, ymm0

; wrap from the top register back to ymm0, shifting to the left by 1
vpermq   ymm0, ymm15, 10_01_00_11b
; store new element
vpinsrq  ymm0, rax, 0

这是一种通用的“移动每个元素”的策略，最简单的实现方式就是使用一个vmovdqa指令操作每个已使用的ymm寄存器，并添加两个附加指令以完成环绕和新元素插入。就向量操作而言，寄存器-寄存器之间的移动比其他任何类型的操作都要快，因为它们可以被消除（0延迟），并且每个周期可以执行4次。

该方法确实需要一个临时寄存器（在上面的示例中为ymm15），我想不出消除它的简单方法，因此您最多只能使用15个寄存器作为“队列”的一部分。

间接跳转

您可以根据迭代计数进行计算的间接跳转，跳转到一个短的（2-4条指令）序列，将元素放入正确的位置。基本上是一个vpinsrq指令，有时还需要一些额外的洗牌来访问高位。

这种类型的表格可以是完全通用的，即允许以任意顺序写入任意索引，但如果您知道您正在像上面那样按顺序索引，则可以使用该假设简化表格（即，您可以通过先写入低元素，然后使用vinserti128或类似方法将它们同时移动到正确的高级别来处理高级别。）

这个表格很可能在第一次预测时出错。之后，这取决于模式和间接分支预测器的强度，有可能会出错，也有可能不会。

- BeeOnRope