Tworzenie dobrego dodatku z kodem carry z clang

Question

Próbuję utworzyć kod (obecnie używający clang ++ - 3.8), który dodaje dwie liczby składające się z wielu słów maszynowych. Aby uprościć rzeczy na chwilę, dodaje tylko 128-bitowe liczby, ale chciałbym móc to uogólnić.

Pierwsze kilka typedefs:

typedef unsigned long long unsigned_word; 
typedef __uint128_t unsigned_128; 

A "Wynik" Typ:

struct Result 
{ 
    unsigned_word lo; 
    unsigned_word hi; 
}; 

Pierwsza funkcja f, przyjmuje dwie pary bez znaku słowa i zwraca rezultacie, jako półproduktu krok, wstawiając oba te 64-bitowe słowa do 128-bitowego słowa przed ich dodaniem, tak jak:

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

To faktycznie dostaje inlined całkiem ładnie tak:

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

Teraz, zamiast Pisałem prostszą funkcję za pomocą szczęk wielu precyzyjnych primatives, jak poniżej:

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

To daje następujące montaż:

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

W tym przypadku jest dodatkowy dodatek. Zamiast zwykłego add na lo-słowach, a następnie adc na hi-words, to tylko add s słowa lo, następnie robi adc na hi-word ponownie z argument zero.

To może nie wyglądać źle, ale kiedy spróbujesz tego z większymi słowami (powiedzmy 192bit, 256bit), szybko dostaniesz bałagan or s i inne instrukcje dotyczące prowadzenia łańcucha, zamiast prostego łańcucha add, adc, adc, ... adc.

Prymitywy o wielu precyzjach wydają się robić straszną robotę dokładnie w tym, co zamierzają zrobić.

Czego szukam to kod, który mógłbym uogólnić na dowolną długość (nie trzeba tego robić, wystarczy, żebym mógł się dowiedzieć, jak to zrobić), który klang produkuje dodatki w taki sposób, że jest równie skuteczny jak co robi z wbudowanym 128-bitowym typem (którego niestety nie da się łatwo uogólnić). Zakładam, że powinien to być łańcuch o numerach adc s, ale jestem zadowolony z argumentów i kodu, że powinno to być coś innego.

Answer 1

Jest to nieodłączne: _addcarry_u64. Jednak tylko Visual Studio i ICC (co najmniej VS 2013 i 2015 oraz ICC 13 i ICC 15) robią to skutecznie. Klang 3.7 i GCC 5.2 wciąż nie tworzą wydajnego kodu z tym nieodłącznym.

Clang dodatkowo ma wbudowane narzędzie, które mogłoby się wydawać, że to robi, __builtin_addcll, ale nie zapewnia również wydajnego kodu.

Powodem, dla którego robi to program Visual Studio, jest to, że nie umożliwia on wbudowanego zestawu w trybie 64-bitowym, więc kompilator powinien zapewnić sposób na to samo z wewnętrznym (chociaż Microsoft nie spieszył się z jego implementacją).

Dlatego w Visual Studio należy użyć _addcarry_u64. Z ICC użyj _addcarry_u64 lub wbudowanego zestawu. Z Clang i GCC użyj wbudowanego zestawu.

Należy pamiętać, że od mikroarchitektury Broadwell istnieją dwa nowe instrukcje: adcx i adox których można uzyskać dostęp z _addcarryx_u64 wewnętrznej. Dokumentacja Intela dla tych właściwości była kiedyś different then the assembly produced by the compiler, ale wydaje się, że ich dokumentacja jest teraz poprawna. Jednak Visual Studio nadal wydaje się produkować tylko adcx z _addcarryx_u64, podczas gdy ICC generuje zarówno adcx, jak i adox z tym wewnętrznym. Mimo że ICC generuje obie instrukcje, nie generuje on najbardziej optymalnego kodu (ICC 15), a zatem montaż liniowy jest nadal konieczny.

Osobiście uważam, że fakt, że niestandardowa funkcja C/C++, taka jak wbudowany zestaw lub wewnętrzne elementy, jest wymagana do tego, jest słabością C/C++, ale inni mogą się z tym nie zgodzić. Instrukcja adc znajduje się w zestawie instrukcji x86 od 1979 roku. Nie będę wstrzymywał kompilatorów C/C++, aby móc optymalnie określić, kiedy chcesz adc. Oczywiście mogą one mieć wbudowane typy, takie jak __int128, ale w momencie, gdy potrzebujesz większego typu, który nie jest wbudowany, musisz użyć niestandardowej funkcji C/C++, takiej jak wbudowany zestaw lub wewnętrzne elementy.

---

Pod względem inline kodu montażowej do tego mogę już napisali rozwiązanie dla 256-bitowego Dodatkowo do ośmiu 64-bitowych liczb całkowitych w rejestrze na multi-word addition using the carry flag.

Oto kod przesłany.

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

Jeśli chcesz jawnie załadować wartości z pamięci można zrobić coś takiego

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

która produkuje nearlly identyczny zestaw jak z poniższej funkcji w MTK

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 Mam ograniczone doświadczenie z wbudowanym montażem GCC (lub ogólnie montażem liniowym - zwykle używam asemblera takiego jak NASM), więc może są lepsze wbudowane rozwiązania montażowe.

---

Więc czego szukam jest kod, który mogę uogólnić na dowolną długość

Aby odpowiedzieć na to pytanie tutaj jest inne rozwiązanie przy użyciu szablonu programowanie meta. I used this same trick for loop unrolling. Zapewnia to optymalny kod za pomocą ICC. Jeśli Clang lub GCC kiedykolwiek wdroży efektywnie _addcarry_u64, byłoby to dobre ogólne rozwiązanie.

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

Zgromadzenie z MTK

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 

Meta programowanie jest podstawową cechą monterów więc szkoda C i C++ (z wyjątkiem poprzez szablonu meta hacki programowania) nie ma rozwiązania tego albo (w języku D robi).

---

Wykorzystany przeze mnie wbudowany zespół, który powodował problemy z pamięcią w funkcji. Oto nowa wersja, która wydaje się działać lepiej

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