x86_64最佳方法将64位寄存器减少到32位,同时保留零或非零状态。

38

我正在寻找将64位寄存器缩小为32位寄存器的最快/空间效率最高的方法,仅保留64位寄存器的零/非零状态。

我目前最好的想法是popcntq
(1c tput,在主流英特尔上延迟3c,代码大小为5字节):

// rax is either zero or non-zero
popcntq %rax, %rax
// eax will be zero if rax was zero, otherwise it will be non-zero

注意:直接使用32位的eax是行不通的:如果rax是2的61次方,那么eax的零/非零状态与rax的不同。

是否有更好的聪明方法?


1
如果更好的混淆有所帮助,crc32 rax, rax 可能是一个选项 :-) - Alex Guteniev
2
@prl:这是一个不错的开始 - 用neg rax替换cmp rax, 1可以得到正确的结果,而且代码也更短。请看我的回答。 - Nate Eldredge
5
或许对于一个超级优化器来说,这是一个有趣的测试。 - Nate Eldredge
1
@NateEldredge 看了一下GNU的,但没有找到构建“result = any zero / non-zero value”概念的方法。 - Noah
2
@MarkKahn - 我不确定我理解你的悬赏原因:“寻找来自可靠来源的答案”。我的回答已经引用了 Agner Fog 的指令表作为性能分析的支持来源。你是否还想要一个链接到 https://uops.info/ 或者 现代超标量处理器操作预测延迟的考虑因素是什么,如何手动计算它们? 来了解如何使用这些数字?可能还有一些技巧没有被想到,但我认为很多人都会认为我是一个“可靠的来源”。 - Peter Cordes
显示剩余2条评论
2个回答

31

最少 uops(前端带宽):
1个uop,延迟3个时钟周期(英特尔)或1个时钟周期(Zen)。
同时最小的代码大小为5个字节。

 popcnt  %rax, %rax         # 5 bytes, 1 uop for one port
 # if using a different dst, note the output dependency on Intel before ICL

大多数CPU上,如果有的话,它的延迟是3个时钟周期,吞吐量为1个时钟周期(一个端口的1个微操作)。或者在Zen1/2/3上为1个时钟周期,吞吐量为0.25个时钟周期。在Excavator之前的Bulldozer系列中,popcnt r64的延迟为4个时钟周期,吞吐量为4个时钟周期(32位操作数大小的吞吐量为2个时钟周期,但仍然是4个时钟周期的延迟)。Bobcat的微码popcnt非常慢。 (https://agner.org/optimize/&https://uops.info/)

最低延迟(假设使用Haswell或更新版本,因此在写入AL并读取EAX时没有部分寄存器效应,或者具有不重命名部分寄存器的无P6祖先的微架构):
2个周期延迟,2个uop,6个字节。如果popcnt(5B)不可用,则也是最小的代码大小。

  test  %rax, %rax     # 3B, 1 uop any ALU port
  setnz %al            # 3B, 1 uop p06 (Haswell .. Ice Lake)
# only works in-place, with the rest of EAX already being known 0 for RAX==0

AL是EAX的低字节,所以对于任何非零的RAX,AL=1都会使EAX非零。

在Sandybridge/Ivy Bridge上读取EAX时,这将花费一个合并uop。Core2/Nehalem会停顿几个周期来插入该合并uop。早期的P6系列处理器(如Pentium-M)将完全停顿,直到稍后的指令读取EAX为止。(为什么GCC不使用部分寄存器?

Nate的neg/sbb在Broadwell及更高版本上与此相同,但长度缩短了1个字节。(并将上32位清零)。在Haswell上效果更好,因为sbb需要2个uops。在早期的主流Intel CPU上,它们都需要3个uops,其中当读取EAX时,这个需要一个合并uop,而sbb(除了在SnB/HSW上的sbb $0)总是需要2个uops。neg/sbb可以用于不同的寄存器中(仍然破坏输入),但在除AMD之外的CPU上存在虚假依赖。(K8/K10、Bulldozer-family和Zen-family都将sbb same,same识别为仅依赖于CF)。


如果您想将前32位清零,可以使用BMI2 RORX 进行复制和移位:
2个微操作,延迟2c,8字节
 rorx  $32, %rax, %rdx      # 6 bytes, 1 uop, 1c latency
 or    %edx, %eax           # 2 bytes, 1c latency
## can produce its result in a different register without a false dependency.

rorx $32 通常用于水平 SWAR 缩减,例如对于 dword 水平求和,您可以使用 movq 将一对 dwords 从 XMM 寄存器中移出,并在标量中使用 rorx/add 进行最后一个 shuffle+add,而不是使用 pshufd/paddd。

或者在没有 BMI2 的情况下仍然将上 32 位清零:
7 字节,4 uops,在 Intel 上的延迟为 3c(其中 bswap r64 是 2 uops,2c 延迟),否则在具有高效 bswap r64 的 CPU 上的延迟为 3 uops 2c,例如 Zen-family 和 Silvermont-family。

 mov    %eax, %edx       # 2 bytes, and not on the critical path
 bswap  %rax             # 3 bytes, vs. 4 for  shr $32, %rax 
 or     %edx, %eax       # 2 bytes
## can write a different destination

使用 shr $32, %rax 代替 bswap 的妥协方案是:
8字节,3个微操作,2个时钟周期的延迟,即使没有mov-elimination也是如此。
在原始寄存器上运行ALU指令而不是 mov 结果可以让未消除的MOV与之并行运行。
评估“最佳”性能的背景:

未成功的想法:

   bsf %rax, %rax    # 4 bytes.  Fails for RAX=1

当输入为0时,不更改目标。(AMD文档中有记录,Intel实现了但没有将其记录在未来的保护中。) 不幸的是,这将导致输入为1时RAX=0。
在Intel上与popcnt性能相同,在AMD上性能更差,但可以节省1个字节的代码大小。

(使用sub $1设置CF,然后??;Nate使用neg的方法可以使其工作得更加清晰。)

我还没有尝试使用superoptimizer强制检查其他可能的序列,但正如Nate所评论的那样,这是一个足够短小的问题,可以成为一种用例。


1
我起初没有理解setnz的解决方案。然后我意识到,我们只想要当rax已经为零时eax=零,所以即使setnz本身仅设定al,它也足够了。 - ecm

24

一个选择是

neg rax         ; 48 F7 D8
sbb eax, eax    ; 19 C0

记住,neg 像从零减一样设置标志位,所以仅当 rax 不为零时,它才会设置进位标志位。而将一个寄存器与其本身进行 sbb 运算将根据进位标志位的清除或设置而产生 0-1 的结果(感谢 @prl 在评论中提出此建议)。

虽然这仍然是 5 字节,需要 2 个微操作,而不是 1 个。 但如果我的计算正确,在 Skylake 上您将获得 2 个周期的延迟而不是 3 个,吞吐量为每个周期 2 个而不是 1 个。


不错。在Haswell及更早版本中,sbb eax,eax是2个uops,2c延迟。但在Broadwell及以后的版本中表现良好。EAX上的“false”依赖关系(除了Bulldozer之外的所有CPU)很好,因为SBB还取决于由最后一个写入RAX的相同指令产生的CF。与我的答案中的test rax,rax / setnz al想法相比,这可以节省一个字节(6个字节,2个uops,2c延迟)。 - Peter Cordes
根据https://www.agner.org/optimize/microarchitecture.pdf,修正、K8/K10、Bulldozer家族和Zen家族都将`sbb same,same`仅视为依赖于CF。如果您想在仍然破坏输入的情况下将其用于不同的目标寄存器,则可以使用此操作。 - Peter Cordes
1
这个(或Peter的test+setnz)很可能是优化编译器生成的代码,因此具有高度惯用性的优点,即使不是最快的代码。 (尽管正如Michael Abrash所说,“没有最快的代码”;总会有人来打败你认为是最快/最好的东西。)特别是MSVC喜欢使用巧妙的sbb序列。 GCC可能会坚持使用更明显的setCC,在P6时代曾经效率较低。 - Cody Gray
1
@CodyGray:你想到的是P4,其中setCC是3个uops,延迟为5个周期,在Prescott上可能更糟,如果Agner对于寄存器或内存目标的9c延迟是正确的。从一开始就有快速的setCC,即从PPro / PII / PIII开始的P6。https://www.agner.org/optimize/instruction_tables.pdf。(在P5上,它是单周期不可配对的,0F转义字节可能会有解码惩罚)。 - Peter Cordes
2
@CodyGray:确实,如果你指定了 -1 作为非零结果的返回值,这就是gcc和clang所做的:https://godbolt.org/z/oPMdYn7v1 - Nate Eldredge

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接