指令数量不是一个好的性能指标。无论是以字节为单位的代码大小(x86机器指令长度可变),还是针对现有主流CPU执行它们的方式:前端操作(解码后)的数量和/或延迟/吞吐量是相关的优化目标,具体取决于周围代码的重要性。对于这么小的东西,其中一个最重要的目标是什么。(如何预测现代超标量处理器上操作的延迟,并如何手动计算它们?)
rcr
/ rcl
非常缓慢,特别是count != 1的情况。
四个单操作码指令更快,包括使用BMI2 rorx
将您想要插入的位复制并旋转到tmp寄存器中的正确位置,然后使用and
来隔离它。如果您不需要保留输入,则使用普通的移位/和。那比我想到的任何通过CF弹跳的方法都更有效。
这比使用
xor
-zero/
bt
/
setc
/
shl
更有效率。它还避免了
局部寄存器假依赖或停顿:
setc ebx
不存在,只有
setc bl
(或
setc bh
)。这也意味着,如果你可以破坏你的输入寄存器而不是使用临时寄存器,你就不需要像
setc bl
/
movzx ebx, bl
这样效率低下的指令,因为这会让零扩展成为延迟的关键路径,并且破坏mov-elimination。
我将EDX作为临时寄存器,因为在普通的调用约定中,它被调用方破坏。
; input in EAX, merge-target in ECX (read/write)
; no pre-conditions necessary
; unlike the original which doesn't count the cost of zeroing EDX
rorx edx, eax, 23-3 ; shift bit 23 to bit 3. Use SHR if you don't need the EAX value later
and edx, 1<<3 ; and isolate
and ecx, 0xFFFFFFF7 ; clear it in the destination
or ecx, edx ; and merge
; total size: 14 bytes of machine code for imm8 masks, 20 for imm32 masks
; 4 uops.
or
可以替换为
add
或
lea
,因为我们知道没有重叠的1位。如果您想要将结果保存在不同的寄存器中,则
lea
非常有用,因为它可以复制和合并。但是,如果您需要这样做,您只需将
or
操作放入临时寄存器中,而不是ECX寄存器,您可以选择任何临时寄存器,包括EAX寄存器(在这种情况下,您可以将
rorx
优化为
shr
)。
add
在某些情况下与Sandybridge系列上的一些形式的
jcc
宏融合,因此非常有用,例如当您需要根据FLAGS进行分支时。
xor
也可以使用,但没有任何优点,并且对于人类读者来说不是习惯用法。
lea
可以用于允许仅使用shr
而不是更长的rorx
,如果您不介意破坏输入。2寄存器LEA比add
或or
多1个字节,但是当没有移位计数(AMD)和无常量位移时,在大多数CPU上速度很快。(在Ice Lake之前,它不能在Intel上运行太多端口,因此如果所有其他条件相等,则使用add
或or
,即当您无法使用lea
保存任何指令或延迟或其他东西时。)clang在使用-O3
(只需tune=generic,没有-march
)时对其进行了很好的利用:https://godbolt.org/z/Kbbh6zs4W;它还使用-march = haswell
生成相同的SHR / AND / AND / LEA。(我猜测即使编译需要稍后使用它的代码,它也不会考虑使用rorx来保留该输入。)
这些指令都是Intel和AMD上的单操作码指令,并且你的目标位位置很低,所以两个AND掩码都可以适合一个符号扩展的imm8,因此AND指令每个为3个字节。(而不是6个字节的and r/m32, imm32)。rorx是6个字节,带有VEX前缀和imm8。总大小为14个字节,如果目标位超出了低7位,则为20个字节。 (或者低8位,如果您使用像and dl, 0x80 / ... / or cl, dl这样的字节操作数大小,会在P6系列上引起部分寄存器问题,但在其他地方没有问题.)
(问题中使用的指令也是单操作码,包括bt。在AMD CPU上,bts等指令是2个操作码,但bt只有1个操作码。)
使用更高的目标位数,您可以使用btr ecx, 30
(4个字节,在英特尔上仍然是1个uop)而不是and ecx,~(1<<30)
(6个字节或5个字节进入EAX)来节省空间。但这会在AMD上增加一个额外的uop。
当然,如果您关心代码大小,您可以使用mov edx,eax
/ ror edx,23-3
(总共5个字节)而不是使用rorx
(6个字节)。因此,具有高目标位位置的总共为17个字节。或者如果我们可以破坏EAX,则为15个字节。
如果位位置是运行时变量,则效率会降低,需要进行可变计数移位。(并进行一些减法或其他操作以生成移位计数。)在那种情况下,可能会有更好的不同策略。
另一种在寄存器之间交换位的方法是使用掩码异或,但在这里我们不想交换,只是单向移动。我们可以使用反转的掩码作为立即数。(或如果在寄存器中,则使用BMI1 andn。)
主要问题是x86缺少一个位域插入指令。使用移位/与提取很容易,尽管这仍然需要2个指令,除非您拥有AMD TBM的立即形式的bextr
,使用XOP编码。(仅适用于Bulldozer系列) 或者如果您已经在寄存器中有一个常量,则使用pext
。如果存在bt
的反向操作可以将CF放置在指定位置,那就太好了,但不幸的是没有这样的指令。
如果有一个位域插入指令,无论是来自CF还是另一个寄存器的低位,您都不需要进行掩码。
避免使用rcr
/rcl
而不需要临时寄存器-稍微慢一些,但仍然是4个uops。
@rcgldr展示了一个有趣的技巧,使用rcr
/rcl
可以减小代码大小,但在现代CPU上速度较慢,例如Zen3上rcl
和rcr r32, imm
需要7个uops,吞吐量为3c,而Sandybridge系列(包括Alder Lake)需要8个uops,吞吐量为6c。(https://uops.info/ / https://agner.org/optimize/)
这是10字节的机器码,不需要临时寄存器。我们可以用只有12字节的机器码来复制功能,但仍然只有4个单uop指令,假设x86足够现代化。上面的版本在Intel Haswell及更早版本上速度更快。
这个操作从ECX到结果的关键路径延迟更长(3个周期),但是对于EAX到结果(3个周期)来说相同,假设单个uop adc和旋转。此外,更多的uops竞争移位单元,因此不能在后端端口的选择上运行得那么广泛。这是否重要取决于周围的代码。
即使目标位位置> 8,在64位模式下,它的代码大小也相同,并且避免了需要任何8字节掩码的情况。
如果您没有可以破坏(包括输入)的备用寄存器,则非常值得这样做。或者仅仅是为了代码大小,如果这不是您代码中真正热门的部分。
ror ecx, 3+1
bt eax, 23
adc ecx, ecx
rol ecx, 3
初始的向右旋转可以是 rcr
或 ror
;我们不关心要替换的位是否暂时被移动到了最高位,或者只是移动到了 CF。 ror
更快。
我们基本上通过 rcl ecx, 1
然后 rol ecx, 3
来模拟 rcl ecx, 3+1
。我认为它们在 FLAGS 输出上有所不同,但 ECX 结果匹配并且从 FLAGS 中读取的方式相同。
然后用等效但更快的 adc same,same
替换 rcl r32, 1
;它们只在 FLAGS 输出上有所不同。 adc
在 Intel 上没有任何奇怪的部分 FLAGS 写入(大多数 SPAZO 不受影响),这使得旋转在 Intel 上更加昂贵。在 Broadwell 之前,adc
在 Intel 上需要 2 个微操作,但在 AMD 上已经是 1 个微操作很长时间了。
这个使用bt
来遍历FLAGS,因此可以轻松支持运行时可变的源位位置。对于目标位位置的可变性,您需要计算移位次数,而ror reg, cl
则速度较慢(在Intel上需要3个uop)。不幸的是,没有可变计数的rorx
,只有shlx
/ shrx
。