使用constant - imul或shl-add-combination进行乘法运算

Question

这个问题是关于我们如何将整数与常数相乘.那么让我们看一个简单的函数:

int f(int x) {
    return 10*x;
}

如何最佳地优化该功能,尤其是在内联到呼叫者时？

方法1(由大多数优化编译器生成(例如,在Godbolt上))

    lea    (%rdi,%rdi,4), %eax
    add    %eax, %eax

方法2(使用clang3.6和更早版本,使用-O3生成)

    imul   $10, %edi, %eax

方法3(使用g ++ 6.2生成,无需优化,删除存储/重新加载)

    mov    %edi, %eax
    sal    $2, %eax
    add    %edi, %eax
    add    %eax, %eax

哪个版本最快,为什么？主要对英特尔Haswell感兴趣.

Answer 1

根据Agner Fog的测试(以及像AIDA64这样的其他东西),自Core2以来,Intel CPU的imul r32,r32, imm延迟为3c,吞吐量为每1c一个.自Nehalem以来,64位乘法也快.(Agner表示Nehalem的imul r64,r64,imm速度较慢(2c吞吐量)imul r64,r64,但这与其他结果 不符.Instlatx64表示1c.)

Ryzen之前的AMD CPU速度较慢,例如,对于32位乘法,Steamroller的lat = 4c tput =每2c一个.对于64位乘法,lat = 6c tput =每4c一个.AMD Ryzen具有与英特尔相同的出色乘法性能.

在寻址模式下有2个组件的LEA(基本+索引,但没有恒定位移)在所有CPU上以1c延迟运行,除了可能用于LEA在管道的不同阶段运行的Atom(在实际的AGU中,而不是ALU)并且需要比"正常"ALU指令早4c输入.相反,我认为它的输入已经准备好,所以ADD可以使用相同周期的结果.(我没有对此进行测试,也没有任何Atom HW.)

在Intel SnB系列上,simple-LEA可以在端口1或5上运行,因此它的吞吐量是IMUL的两倍.

ADD可以在任何CPU上的任何ALU端口上运行.HSW引入了第4个ALU端口(与IvyBridge相比),因此每个时钟可以维持4个ALU uop(理论上).

因此LEA + ADD版本在大多数x86 CPU上具有2c延迟,而Haswell可以在每个时钟运行两次乘法.

但是,如果乘法只是较大周围环路的一小部分,这会影响总uop吞吐量,而不是乘法延迟或吞吐量,IMUL版本更好.

如果你的乘法常数对于两个LEA或SHL + LEA而言太大,那么你可能会更好地使用IMUL,特别是在主要用于具有极高性能整数乘法器的Intel CPU时.

SHL + LEA或SHL + SUB可能是由63乘有用例如(来自Godbolt: gcc6.2 -O3 -march=haswell)

    movl    %edi, %eax
    sall    $6, %eax
    subl    %edi, %eax

在Haswell,其中MOV是零延迟,这只有2c延迟.但它是3个融合域uops,而1为imull $63, %edi, %eax.因此,管道中的uops更多,减少了CPU可以"看到"执行无序执行的程度.它还会增加uop缓存和L1 I-cache的压力,使编译器始终选择此策略,因为它的指令字节更多.

在IvyBridge之前的CPU上,这比IMUL严格更糟,除非其他东西竞争port1,因为它是3c延迟(MOV在关键路径依赖链上,并且具有1c延迟).

像往常一样,没有一个asm片段可以说对所有情况都是最佳的.这取决于周围代码中的瓶颈:延迟,吞吐量或微量.

对于不同微体系结构中的相同周围代码,答案也会有所不同.