c++ - Producir buen complemento con código de acarreo de clang

clang download

Question

Estoy tratando de producir código (actualmente usando clang ++ - 3.8) que agrega dos números que consisten en varias palabras de máquina. Para simplificar las cosas por el momento, solo estoy agregando números de 128 bits, pero me gustaría poder generalizar esto.

Primero algunos typedefs:

typedef unsigned long long unsigned_word;
typedef __uint128_t unsigned_128;

Y un tipo de "resultado":

struct Result
{
  unsigned_word lo;
  unsigned_word hi;
};

La primera función, f , toma dos pares de palabras sin firmar y devuelve un resultado, por medio de un paso intermedio, colocando ambas palabras de 64 bits en una palabra de 128 bits antes de agregarlas, así:

Result f (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
  Result x;
  unsigned_128 n1 = lo1 + (static_cast<unsigned_128>(hi1) << 64);
  unsigned_128 n2 = lo2 + (static_cast<unsigned_128>(hi2) << 64);
  unsigned_128 r1 = n1 + n2;
  x.lo = r1 & ((static_cast<unsigned_128>(1) << 64) - 1);
  x.hi = r1 >> 64;
  return x;
}

De hecho, esto se alinea bastante bien así:

movq    8(%rsp), %rsi
movq    (%rsp), %rbx
addq    24(%rsp), %rsi
adcq    16(%rsp), %rbx

Ahora, en cambio, he escrito una función más simple usando los primativos de multi precisión de clang, como se muestra a continuación:

static Result g (unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
  Result x;
  unsigned_word carryout;
  x.lo = __builtin_addcll(lo1, lo2, 0, &carryout);
  x.hi = __builtin_addcll(hi1, hi2, carryout, &x.carry);
  return x;
}

Esto produce el siguiente ensamblaje:

movq    24(%rsp), %rsi
movq    (%rsp), %rbx
addq    16(%rsp), %rbx
addq    8(%rsp), %rsi
adcq    $0, %rbx

En este caso, hay un complemento adicional. En lugar de hacer un add ordinario de las palabras-lo, luego un adc en las hi-palabras, simplemente add s las hi-palabras, luego add s las palabras-lo, luego hace un adc en la palabra-alta de nuevo con un argumento de cero.

Puede que esto no se vea tan mal, pero cuando pruebas esto con palabras más grandes (digamos 192bit, 256bit) pronto obtienes un desorden de or s y otras instrucciones relacionadas con el carry up de la cadena, en lugar de una simple cadena de add , adc , adc , ... adc .

Las primitivas de precisión múltiple parecen estar haciendo un trabajo terrible en exactamente lo que están destinados a hacer.

Entonces, lo que estoy buscando es un código que pueda generalizar a cualquier longitud (no es necesario hacerlo, lo suficiente para que pueda averiguar cómo hacerlo), con qué clang produce adiciones es tan eficiente como lo que hace con Está construido en el tipo de 128 bits (que desafortunadamente no puedo generalizar fácilmente). Supongo que esto debería ser solo una cadena de adc , pero me complacen los argumentos y el código de que debería ser algo más.

Answer 1

Comenzando con clang 5.0 es posible obtener buenos resultados usando __uint128_t -adición y obtener el bit de acarreo por desplazamiento:

inline uint64_t add_with_carry(uint64_t &a, const uint64_t &b, const uint64_t &c)
{
    __uint128_t s = __uint128_t(a) + b + c;
    a = s;
    return s >> 64;
}

En muchas situaciones, el clang aún realiza operaciones extrañas (supongo que debido a un posible aliasing), pero generalmente la copia de una variable en un temporal ayuda.

Ejemplos de uso con

template<int size> struct LongInt
{
    uint64_t data[size];
};

Uso manual:

void test(LongInt<3> &a, const LongInt<3> &b_)
{
    const LongInt<3> b = b_; // need to copy b_ into local temporary
    uint64_t c0 = add_with_carry(a.data[0], b.data[0], 0);
    uint64_t c1 = add_with_carry(a.data[1], b.data[1], c0);
    uint64_t c2 = add_with_carry(a.data[2], b.data[2], c1);
}

Solución genérica

template<int size>
void addTo(LongInt<size> &a, const LongInt<size> b)
{
    __uint128_t c = __uint128_t(a.data[0]) + b.data[0];
    for(int i=1; i<size; ++i)
    {
        c = __uint128_t(a.data[i]) + b.data[i] + (c >> 64);
        a.data[i] = c;
    }
}

Godbolt Link : todos los ejemplos anteriores están compilados solo para mov , add y adc instructions (comenzando con clang 5.0, y al menos -O2).

Los ejemplos no producen un buen código con gcc (hasta 8.1, que en este momento es la versión más alta en godbolt). Y aún no logré obtener nada utilizable con __builtin_addcll ...

Answer 2

En Clang 6, ambos __builtin_addcl y __builtin_add_overflow producen el mismo desarmado óptimo .

Result g(unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
  Result x;
  unsigned_word carryout;
  x.lo = __builtin_addcll(lo1, lo2, 0, &carryout);
  x.hi = __builtin_addcll(hi1, hi2, carryout, &carryout);
  return x;
}

Result h(unsigned_word lo1, unsigned_word hi1, unsigned_word lo2, unsigned_word hi2)
{
  Result x;
  unsigned_word carryout;
  carryout = __builtin_add_overflow(lo1, lo2, &x.lo);
  carryout = __builtin_add_overflow(hi1, carryout, &hi1);
  __builtin_add_overflow(hi1, hi2, &x.hi);
  return x;
}

Asamblea para ambos:

add rdi, rdx
adc rsi, rcx
mov rax, rdi
mov rdx, rsi
ret

Answer 3

Hay un intrínseco para hacer esto: _addcarry_u64 . Sin embargo, solo Visual Studio e ICC (al menos VS 2013 y 2015 e ICC 13 e ICC 15) lo hacen de manera eficiente. Clang 3.7 y GCC 5.2 todavía no producen código eficiente con este intrínseco.

Clang además tiene un built-in que uno pensaría que hace esto, __builtin_addcll , pero tampoco produce un código eficiente.

La razón por la que Visual Studio hace esto es porque no permite el ensamblado en línea en el modo de 64 bits, por lo que el compilador debe proporcionar una forma de hacerlo con un intrínseco (aunque Microsoft se tomó su tiempo para implementar esto).

Por lo tanto, con Visual Studio, use _addcarry_u64 . Con ICC use _addcarry_u64 o ensamblado en línea. Con Clang y GCC, use el ensamblaje en línea.

Tenga en cuenta que desde la microarquitectura de Broadwell hay dos nuevas instrucciones: adcx y adox que puede acceder con el _addcarryx_u64 intrínseco. La documentación de Intel para estos intrínsecos solía ser diferente al ensamblado producido por el compilador, pero parece que su documentación es correcta ahora. Sin embargo, Visual Studio todavía parece producir adcx con _addcarryx_u64 mientras que ICC produce tanto adcx como adox con este intrínseco. Pero a pesar de que ICC produce ambas instrucciones, no produce el código más óptimo (ICC 15) y, por lo tanto, el ensamblaje en línea sigue siendo necesario.

Personalmente, creo que el hecho de que se requiera una característica no estándar de C / C ++, como el ensamblaje en línea o intrínsecos, es una debilidad de C / C ++, pero otros pueden estar en desacuerdo. La instrucción adc ha estado en el conjunto de instrucciones x86 desde 1979. No me quedaría sin aliento con los compiladores C / C ++ que son capaces de determinar de manera óptima cuándo quieres adc . Claro que pueden tener tipos __int128 como __int128 pero en el momento que desee un tipo más grande que no esté incorporado, deberá usar alguna característica no estándar de C / C ++, como el ensamblaje en línea o intrínsecos.

En términos de código ensamblador en línea para hacer esto, ya he publicado una solución para la adición de 256 bits para ocho enteros de 64 bits en el registro en la adición de varias palabras usando la bandera de acarreo .

Aquí está ese código publicado.

#define ADD256(X1, X2, X3, X4, Y1, Y2, Y3, Y4) /
 __asm__ __volatile__ ( /
 "addq %[v1], %[u1] /n" /
 "adcq %[v2], %[u2] /n" /
 "adcq %[v3], %[u3] /n" /
 "adcq %[v4], %[u4] /n" /
 : [u1] "+&r" (X1), [u2] "+&r" (X2), [u3] "+&r" (X3), [u4] "+&r" (X4) /
 : [v1]  "r" (Y1), [v2]  "r" (Y2), [v3]  "r" (Y3), [v4]  "r" (Y4)) 

Si desea cargar explícitamente los valores de la memoria, puede hacer algo como esto

//uint64_t dst[4] = {1,1,1,1};
//uint64_t src[4] = {1,2,3,4};
asm (
     "movq (%[in]), %%rax/n"
     "addq %%rax, %[out]/n"
     "movq 8(%[in]), %%rax/n"
     "adcq %%rax, 8%[out]/n"
     "movq 16(%[in]), %%rax/n"
     "adcq %%rax, 16%[out]/n"
     "movq 24(%[in]), %%rax/n"
     "adcq %%rax, 24%[out]/n"
     : [out] "=m" (dst)
     : [in]"r" (src)
     : "%rax"
     );

Eso produce ensamblaje casi idéntico a partir de la siguiente función en ICC

void add256(uint256 *x, uint256 *y) {
    unsigned char c = 0;
    c = _addcarry_u64(c, x->x1, y->x1, &x->x1);
    c = _addcarry_u64(c, x->x2, y->x2, &x->x2);
    c = _addcarry_u64(c, x->x3, y->x3, &x->x3);
        _addcarry_u64(c, x->x4, y->x4, &x->x4);
}

Tengo una experiencia limitada con el ensamblado en línea de GCC (o el ensamblaje en línea en general, generalmente utilizo un ensamblador como NASM), por lo que quizás haya mejores soluciones de ensamblaje en línea.

Entonces, lo que busco es un código que pueda generalizar a cualquier longitud

Para responder a esta pregunta aquí hay otra solución que usa la meta programación de la plantilla. Usé este mismo truco para desenrollar el bucle . Esto produce un código óptimo con ICC. Si Clang o GCC implementan alguna vez _addcarry_u64 eficiente, esta sería una buena solución general.

#include <x86intrin.h>
#include <inttypes.h>

#define LEN 4  // N = N*64-bit add e.g. 4=256-bit add, 3=192-bit add, ...

static unsigned char c = 0;

template<int START, int N>
struct Repeat {
    static void add (uint64_t *x, uint64_t *y) {
        c = _addcarry_u64(c, x[START], y[START], &x[START]);
        Repeat<START+1, N>::add(x,y);
    }
};

template<int N>
    struct Repeat<LEN, N> {
    static void add (uint64_t *x, uint64_t *y) {}
};


void sum_unroll(uint64_t *x, uint64_t *y) {
    Repeat<0,LEN>::add(x,y);
}

Asamblea de ICC

xorl      %r10d, %r10d                                  #12.13
movzbl    c(%rip), %eax                                 #12.13
cmpl      %eax, %r10d                                   #12.13
movq      (%rsi), %rdx                                  #12.13
adcq      %rdx, (%rdi)                                  #12.13
movq      8(%rsi), %rcx                                 #12.13
adcq      %rcx, 8(%rdi)                                 #12.13
movq      16(%rsi), %r8                                 #12.13
adcq      %r8, 16(%rdi)                                 #12.13
movq      24(%rsi), %r9                                 #12.13
adcq      %r9, 24(%rdi)                                 #12.13
setb      %r10b

La metaprogramación es una característica básica de los ensambladores, así que es una lástima que C y C ++ (a excepción de los metalográficos de programación de plantillas) tampoco tengan una solución para esto (el lenguaje D sí lo hace).

El ensamblaje en línea que utilicé anteriormente que hacía referencia a la memoria estaba causando algunos problemas en una función. Aquí hay una nueva versión que parece funcionar mejor

void foo(uint64_t *dst, uint64_t *src)
{
    __asm (
        "movq (%[in]), %%rax/n"
        "addq %%rax, (%[out])/n"
        "movq 8(%[in]), %%rax/n"
        "adcq %%rax, 8(%[out])/n"
        "movq 16(%[in]), %%rax/n"
        "addq %%rax, 16(%[out])/n"
        "movq 24(%[in]), %%rax/n"
        "adcq %%rax, 24(%[out])/n"
        :
        : [in] "r" (src), [out] "r" (dst)
        : "%rax"
    );
}