Какая польза от этого блока asm с использованием x86 DIV в c ++? - PullRequest
Новая
       64

Какая польза от этого блока asm с использованием x86 DIV в c ++?

0 голосов
/ 03 октября 2018

Может кто-нибудь помочь мне понять преимущество использования asm-блока для умножения unsigned long long с точки зрения производительности.Это связано с конкурентной оптимизацией программирования.Я предполагаю, что это делает умножение быстрее, но я не могу понять код на самом деле. 

const int md = 998244353;
inline int mul(int a, int b)
{
#if !defined(_WIN32) || defined(_WIN64)
    return (int) ((long long) a * b % md);
#endif
    unsigned long long x = (long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm(
            "divl %4; \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (md)
    );
    return m;
}

1 Ответ

0 голосов
/ 04 октября 2018

Этот код на самом деле ускоряет 32-битные (где 64x64 => 128 умножение недоступно, поэтому компиляторы используют фактическое деление, но сильно проигрывает на 64-битных, где компиляторы используют мультипликативную инверсию, чтобы полностью избежать медленного аппаратного деления. Почему GCC использует умножение на странное число при реализации целочисленного деления?

Кроме того, он должен действительно использовать __builtin_constant_p, чтобы использовать встроенный asm только в том случае, если какой-либо ввод не является временем компиляцииконстанта после встраивания и постоянного распространения.

Но в любом случае, x86's div инструкция делает EDX:EAX / (src) => частное (EAX) и делитель (EDX). См. Когда и почему мы подписываем расширение и используем cdq с mul / div?

Ограничения "a" и "d" запрашивают младшие и старшие половины 64-битного продукта в EAX иEDX соответственно в качестве входных данных.

Из проводника компилятора Godbolt : 

const int md = 998244353;
int mul(int a, int b)
{
#ifdef __x86_64__ // FIXME: just use the asm if defined(i386) to exclude all others
    return (int) ((long long) a * b % md);
#else
    if(__builtin_constant_p(a) && __builtin_constant_p(b))
        return (int) ((long long) a * b % md);
      // clang's builtin_constant_p is evaled before inlining, derp

    unsigned long long x = (long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm(
            "divl %4; \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (md)
    );
    return m;
#endif
}

int main() {
    return mul(1,2);
}

компилируется следующим образом с gcc8.2 -O3 -m32: 

mul(int, int):
    mov     eax, DWORD PTR [esp+8]
    mov     ecx, 998244353
    imul    DWORD PTR [esp+4]     # one-operand imul does EDX:EAX = EAX * src
    divl ecx;                     # EDX:EAX / ecx => EAX and EDX

    mov     eax, edx              # return the remainder
    ret

main:
    mov     eax, 2     # builtin_constant_p used the pure C, allowing constant-propagation
    ret

Обратите внимание, что div является unsигнорируется деление, так что это не соответствует C. C выполняет знаковое умножение и знаковое деление. Это, вероятно, должно использовать idiv или приводить входные данные к беззнаковым.Или, может быть, им действительно нужны странные результаты с отрицательными данными по какой-то странной причине.

Так почему же компиляторы не могут генерировать это самостоятельно, без встроенного ассема?Потому что, если частное переполняет регистр назначения (al / ax / eax / rax), он ошибается с #DE (Divide Exception) вместо тихого усечения, как все другие целочисленные инструкции.

64-бит / 32-bit => 32-битное деление безопасно только в том случае, если вы знаете, что делитель достаточно велик для возможных дивидендов.(Но даже если это так, gcc все еще не знает, ищите эту оптимизацию. Например, a * 7ULL / 9 не может вызвать #DE, если сделано с одиночными mul и div, если a было 32-bit типа. Но gcc по-прежнему будет генерировать вызов вспомогательной функции libgcc.)

...