Produrre bene aggiungere con codice di trasporto da clang

Question

Sto provando a produrre codice (attualmente usando clang ++ - 3.8) che aggiunge due numeri composti da più parole macchina. Per semplificare le cose per il momento sto solo aggiungendo numeri a 128 bit, ma mi piacerebbe essere in grado di generalizzare questo.

Prima alcune typedefs:

typedef unsigned long long unsigned_word; 
typedef __uint128_t unsigned_128; 

E un tipo "risultato":

struct Result 
{ 
    unsigned_word lo; 
    unsigned_word hi; 
}; 

La prima funzione, f prende due coppie di parole senza segno e restituisce un risultato, da come intermedio passo mettendo entrambe queste parole a 64 bit in una parola a 128 bit prima di aggiungerle, in questo modo:

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; 
} 

Questo in realtà viene inline piuttosto esattamente in questo modo:

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

Ora, invece ho scritto una funzione più semplice utilizzando il clangore primitive multi-precisione, come di seguito:

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; 
} 

Questo produce il seguente assemblea:

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

In questo caso, c'è un extra. Invece di fare un ordinario add sulle lo-words, quindi un adc sulle hi-words, è solo add s le parole-chiave, quindi add s le lo-words, quindi fa un adc sull'hi-word di nuovo con un argomento di zero.

Questo può non sembrare troppo male, ma quando si tenta questo con parole più grandi (diciamo 192bit, 256bit) a presto ottiene un pasticcio di or s e altre istruzioni riguardanti la porta a monte della catena, invece di una semplice catena di add, adc, adc, ... adc.

I primitivi multi-precisione sembrano fare un lavoro terribile esattamente a quello che sono destinati a fare.

Quindi quello che sto cercando è un codice che potrei generalizzare a qualsiasi lunghezza (non c'è bisogno di farlo, quanto basta per capire come farlo), che clang produce addizioni in un modo con è efficiente come ciò che fa è costruito a 128 bit (che sfortunatamente non riesco facilmente a generalizzare). Presumo che questo dovrebbe solo una catena di adc s, ma sono benvenuto in argomenti e codice che dovrebbe essere qualcos'altro.

Answer 1

C'è un intrinseco per fare questo: _addcarry_u64. Tuttavia, solo Visual Studio e ICC (almeno VS 2013 e 2015 e ICC 13 e ICC 15) lo fanno in modo efficiente. Clang 3.7 e GCC 5.2 continuano a non produrre codice efficiente con questo intrinseco.

Clang ha inoltre un built-in che si potrebbe pensare, __builtin_addcll, ma non produce codice efficiente.

Il motivo per Visual Studio fa questo è che non permette il montaggio in linea in modalità a 64 bit in modo che il compilatore dovrebbe fornire un modo per fare questo con un intrinseco (anche se Microsoft ha preso il loro tempo l'attuazione del presente).

Pertanto, con Visual Studio utilizzare _addcarry_u64. Con ICC utilizzare _addcarry_u64 o assemblaggio in linea. Con Clang e GCC usa l'assemblaggio in linea.

Si noti che dalla microarchitettura di Broadwell ci sono due nuove istruzioni: adcx e adox a cui è possibile accedere con lo _addcarryx_u64 intrinseco. La documentazione di Intel per questi elementi intrinseci era different then the assembly produced by the compiler ma sembra che la loro documentazione sia corretta ora. Tuttavia, Visual Studio sembra ancora produrre solo adcx con _addcarryx_u64 mentre ICC produce sia adcx sia adox con questo intrinseco. Ma anche se ICC produce entrambe le istruzioni, non produce il codice più ottimale (ICC 15) e quindi l'assemblaggio in linea è ancora necessario.

Personalmente, penso che il fatto che una caratteristica non standard di C/C++, come l'inline assembly o l'intrinseco, sia richiesto per fare ciò è una debolezza di C/C++, ma altri potrebbero non essere d'accordo. L'istruzione adc è nel set di istruzioni x86 dal 1979. Non terrei il respiro sui compilatori C/C++ in grado di capire in modo ottimale quando si desidera adc. Certo, possono avere tipi predefiniti come __int128 ma nel momento in cui si desidera un tipo più grande che non è incorporato, è necessario utilizzare alcune funzionalità C/C++ non standard come l'assembly inline o le intrinseche.

---

In termini di codice assembly inline per fare questo ho già postato una soluzione per aggiunta di 256 bit per otto interi a 64 bit nel registro a multi-word addition using the carry flag.

Ecco il codice ripubblicato.

#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)) 

Se si desidera caricare in modo esplicito i valori dalla memoria si può fare qualcosa di simile

//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" 
    ); 

che produce assemblaggio nearlly identico dal seguente funzione nel 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); 
} 

I Ho un'esperienza limitata con l'assemblaggio in linea di GCC (o assemblaggio in linea in generale - di solito uso un assemblatore come NASM), quindi forse ci sono soluzioni di assemblaggio in linea migliori.

---

Quindi quello che sto cercando è il codice che ho potuto generalizzare a tutta la lunghezza

Per rispondere a questa domanda qui è un'altra soluzione utilizzando il modello meta-programmazione. I used this same trick for loop unrolling. Questo produce un codice ottimale con ICC. Se Clang o GCC implementano mai _addcarry_u64 in modo efficiente questa sarebbe una buona soluzione generale.

#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); 
} 

Assemblea da 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 

programmazione Meta è una caratteristica fondamentale degli assemblatori quindi è troppo cattivo C e C++ (se non per mezzo di modelli hack di programmazione meta) non hanno alcuna soluzione per questo sia (la lingua D lo fa).

---

L'assembly inline che ho utilizzato sopra la memoria di riferimento causava alcuni problemi in una funzione. Ecco una nuova versione che sembra funzionare meglio

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" 
    ); 
}