delphi - 如何将DivMod优化为10的常数除数

Question

在Delphi math.pas 单元中，有一个过程 DivMod ，我想将其转换为内联并对其进行优化以使除数始终为10。但是我不知道五角大楼ASM的细节。什么是波纹管程序的转换

 procedure DivMod(Dividend: Integer; Divisor: Word;
  var Result, Remainder: Word);
asm
        PUSH    EBX
        MOV     EBX,EDX
        MOV     EDX,EAX
        SHR     EDX,16
        DIV     BX
        MOV     EBX,Remainder
        MOV     [ECX],AX
        MOV     [EBX],DX
        POP     EBX
end;

Answer 1

到目前为止，您可以做的最重要的优化是使用定点乘法逆来除以编译时常量Why does GCC use multiplication by a strange number in implementing integer division?。

任何体面的C编译器都会为您做到这一点，但是显然Delphi不会这样做，因此使用asm这样做是有充分理由的。

您可以在EAX中返回一个值，而不是将商和余数都存储到内存中吗？传递2个指针args似乎很浪费，并迫使调用者从内存中检索值。 (更新，是的，我认为您可以通过使其成为函数而不是过程来实现；不过，我只是从其他答案中盲目地修改了Delphi代码。)

无论如何，幸运的是，我们可以让C编译器为我们找出乘法逆和移位计数的艰苦工作。我们甚至可以使它使用与Delphi用于内联asm相同的“调用约定”。 GCC's regparm=3 32-bit calling convention在EAX，EDX和ECX中按此顺序传递args。

对于只需要商的情况，您可能需要制作一个单独的版本，因为(与慢速div指令不同)，如果使用快速乘法逆运算，则必须将其余部分作为x - (x/y)*y分别计算。但是，是的，这仍然是现代x86的两倍至4倍。

或者，您可以将其余的计算留在纯Delphi中完成，除非编译器通常对优化不满意。

#ifdef _MSC_VER
#define CONVENTION  _fastcall   // not the same, but 2 register args are better than none.
#else
#define CONVENTION __attribute__((regparm(3)))
#endif

// use gcc -Os to get it to emit code with actual div.

divmod10(unsigned x, unsigned *quot, unsigned *rem) {
    unsigned tmp = x/10;
    // *quot = tmp;
    *rem = x%10;
    return tmp;
}

From the Godbolt compiler explorer:

# gcc8.2  -O3 -Wall -m32
div10:    # simplified version without the remainder, returns in EAX
        mov     edx, -858993459     # 0xCCCCCCCD
        mul     edx                 # EDX:EAX = dividend * 0xCCCCCCCD
        mov     eax, edx
        shr     eax, 3
        ret
      # quotient in EAX

# returns quotient in EAX, stores remainder to [ECX]
# quotient pointer in EDX is unused (and destroyed).
divmod10:
        mov     edx, -858993459
        push    ebx
        mov     ebx, eax
        mul     edx                      # EDX:EAX = dividend * 0xCCCCCCCD
        mov     eax, edx
        shr     eax, 3
        # quotient in EAX = high_half(product) >> 3 = product >> (32+3)
        lea     edx, [eax+eax*4]         # EDX = quotient*5
        add     edx, edx                 # EDX = quot * 10
        sub     ebx, edx                 # remainder = dividend - quot*10
        mov     DWORD PTR [ecx], ebx     # store remainder
        pop     ebx
        ret
        # quotient in EAX

这是C编译器的输出。根据需要适应Delphi内联汇编；输入是在Delphi的正确寄存器中，我认为。

如果Delphi inline-asm不允许您破坏EDX，则可以保存/恢复它。或者，您想删除未使用的 quotient指针输入，则可以调整asm或在Godbolt上调整C并查看新的编译器输出。

这比 div的指令更多，但 div的速度非常慢(10 oups，即使在Skylake上也有26个周期的延迟)。

如果在Delphi中具有64位整数类型，则可以在Delphi源代码中执行此操作，并避免使用内联asm。或如MBo所示，对于仅使用32位整数类型的0..2 ^ 16-1范围内的输入，可以将$CCCD用作乘法逆。

对于其余部分，存储/重载往返(4到5个周期)的延迟与最近采用移动消除功能的Intel CPU的实际计算相似(3 +1为商，+ 3 lea/add/sub = 7)，因此必须为此使用内联asm。但是在延迟和吞吐量方面，它仍然比 div指令更好。请参阅 https://agner.org/optimize/和其他性能链接 in the x86 tag wiki。

您可以复制/粘贴的Delphi版本

( 如果我做对了，我不了解Delphi，只是根据我对调用约定/语法的推断，在SO和 this site上复制并修改了示例)

我不确定我是否可以通过inline-asm的arg传递权限。 This RADStudio documentation说:“除了ESP和EBP之外，asm语句在进入该语句时不能假设任何有关寄存器内容的信息。”但我假设args在EAX和EDX中。

将asm用于64位代码可能很愚蠢，因为在64位中，您可以有效地将纯Pascal用于64位乘法。 How do I implement an efficient 32 bit DivMod in 64 bit code。因此，在 {$IFDEF CPUX64}块中，最好的选择可能是使用 UInt64(3435973837)*num;的纯帕斯卡

function Div10(Num: Cardinal): Cardinal;
{$IFDEF PUREPASCAL}
begin
  Result := Num div 10;
end;
{$ELSE !PUREPASCAL}
{$IFDEF CPUX86}
asm
        MOV     EDX, $CCCCCCCD
        MUL     EDX                   // EDX:EAX = Num * fixed-point inverse
        MOV     EAX,EDX               // mov then overwrite is ideal for Intel mov-elimination
        SHR     EAX,3
end;
{$ENDIF CPUX86}
{$IFDEF CPUX64}
asm
         // TODO: use pure pascal for this; Uint64 is efficient on x86-64
        // Num in ECX, upper bits of RCX possibly contain garbage?
        mov     eax, ecx              // zero extend Num into RAX
        mov     ecx, $CCCCCCCD        // doesn't quite fit in a sign-extended 32-bit immediate for imul
        imul    rax, rcx              // RAX = Num * fixed-point inverse
        shr     rax, 35               // quotient = eax
end;
{$ENDIF CPUX64}
{$ENDIF}

 {Remainder is the function return value}
function DivMod10(Num: Cardinal; var Quotient: Cardinal): Cardinal;
{$IFDEF PUREPASCAL}
begin
  Quotient := Num div 10;
  Result := Num mod 10;
end;
{$ELSE !PUREPASCAL}
{$IFDEF CPUX86}
asm
    // Num in EAX,  @Quotient in EDX
    push    esi
    mov     ecx, edx           // save @quotient
    mov     edx, $CCCCCCCD
    mov     esi, eax           // save dividend for use in remainder calc
    mul     edx                // EDX:EAX = dividend * 0xCCCCCCCD
    shr     edx, 3             // EDX = quotient
    mov     [ecx], edx         // store quotient into @quotient

    lea     edx, [edx + 4*edx] // EDX = quot * 5
    add     edx, edx           // EDX = quot * 10
    mov     eax, esi                  // off the critical path
    sub     eax, edx           // Num - (Num/10)*10
    pop     esi
    // Remainder in EAX = return value
end;
{$ENDIF CPUX86}
{$IFDEF CPUX64}
asm
        // TODO: use pure pascal for this?  Uint64 is efficient on x86-64
    // Num in ECX,   @Quotient in RDX
    mov     r8d, ecx          // zero-extend Num into R8
    mov     eax, $CCCCCCCD
    imul    rax, r8
    shr     rax, 35           // quotient in eax

    lea     ecx, [rax + 4*rax]
    add     ecx, ecx          // ecx = 10*(Num/10)
    mov     [rdx], eax        // store quotient

    mov     eax, r8d          // copy Num again
    sub     eax, ecx          // remainder = Num - 10*(Num/10)
    // we could have saved 1 mov instruction by returning the quotient
    // and storing the remainder.  But this balances latency better.
end;
{$ENDIF CPUX64}
{$ENDIF}

存储商并返回余数意味着两者都可能在调用者中几乎同时准备就绪，因为从商计算余数的额外等待时间与存储转发重叠。 IDK如果这很好，或者如果执行顺序困惑而开始执行基于商的某些工作通常会更好。我猜想，如果您调用DivMod10，则可能只需要其余部分。

但在重复地除以10的小数位数拆分循环中，商是形成关键路径的原因，因此在该版本中返回商并存储余数将是一个更好的选择。

在这种情况下，您将以商作为EAX的返回值，并将函数arg重命名为余数。

该asm基于此C函数此版本( https://godbolt.org/z/qu2kvV)的clang输出，以Windows x64调用约定为目标。但是需要进行一些调整以提高效率，例如将 mov移出关键路径，并使用不同的寄存器来避免REX前缀。并用一个ADD代替一个LEA。

unsigned divmod10(unsigned x, unsigned *quot) {
    unsigned qtmp = x/10;
    unsigned rtmp = x%10;
     *quot = qtmp;
     //*rem = rtmp;
    return rtmp;
}

我使用clang的版本而不是gcc的版本，因为 imul r64,r64在Intel CPU和Ryzen上速度更快(3个周期延迟/1 uop)。 mul r32是3 oups，在Sandybridge系列上每2个时钟只有1个吞吐量。我认为乘法硬件自然会产生128位结果，并将其低64位拆分为edx:eax需要额外的uop或类似的东西。