Самый быстрый способ установить флаг переноса

Question

Я делаю цикл, чтобы суммировать два массива. Моя цель - сделать это, избегая проверок на перенос c = a + b; carry = (c<a). Я потерял CF, когда я проведу цикл, с инструкцией cmp.

В настоящее время я использую и JE и STC для проверки и сохранения ранее сохраненного состояния CF. Но прыжок занимает более 7 циклов, что много для того, чего я хочу.

//This one is working 
    asm(
     "cmp $0,%0;" 
     "je 0f;" 
     "stc;" 
    "0:" 
     "adcq %2, %1;" 
     "setc %0" 

    : "+r" (carry), "+r" (anum) 
    : "r" (bnum) 
    ); 

Я уже пробовал использовать SAHF (2 + 2 (мы) циклы), но это не сработало.

//Do not works 
    asm(
     "mov %0, %%ah;" 
     "sahf;" 
     "adcq %2, %1;" 
     "setc %0" 

     : "+r" (carry), "+r" (anum) 
     : "r" (bnum) 
    ); 

Любой знает способ установить CF быстрее? Как прямой ход или что-то подобное ..

Answer 1

Looping without clobbering CF will be faster. См. Эту ссылку для некоторых лучей asm.

Не пытайтесь писать только adc с встроенным asm внутри цикла C. Это невозможно для того, чтобы быть оптимальным, потому что вы не можете просить gcc не использовать флаги clobber. Попытка узнать asm с помощью встроенного asm GNU C сложнее, чем писать автономную функцию, особенно. в этом случае, когда вы пытаетесь сохранить флаг переноса.

Вы можете использовать setnc %[carry] для сохранения и subb $1, %[carry] для восстановления. (Или cmpb $1, %[carry] Я думаю.) Или, как указывает Стивен, negb %[carry].

0 - 1 производит перенос, но 1 - 1 нет.

Использовать uint8_t для переменной, чтобы удерживать перенос, поскольку вы никогда не добавите его непосредственно на %[anum]. Это позволяет избежать случайностей partial-register slowdowns. например

uint8_t carry = 0; 
int64_t numa, numb; 

for (...) { 
    asm ("negb %[carry]\n\t" 
      "adc %[bnum], %[anum]\n\t" 
      "setc %[carry]\n\t" 
      : [carry] "+&r" (carry), [anum] "+r" (anum) 
      : [bnum] "rme" (bnum) 
      : // no clobbers 
     ); 
} 

Вы также можете предоставить альтернативный шаблон ограничения для источника регистра, reg/mem dest. Я использовал an x86 "e" constraint вместо "i", потому что 64-битный режим по-прежнему позволяет только 32-битные расширенные символы. gcc должен будет получить большие константы времени компиляции в регистр самостоятельно. Carry ранний сбитый, поэтому даже если он и bnum были как 1, так и gcc не могли использовать один и тот же регистр для обоих входов.

Это все еще ужасно и увеличивает длину цепи зависимостей, связанной с циклом, от 2c до 4c (Intel pre-Broadwell) или от 1c до 3c (Intel BDW/Skylake и AMD).

Таким образом, ваша петля работает со скоростью 1/3, потому что вы используете kludge вместо того, чтобы писать весь цикл в asm.

---

Предыдущая версия этого ответа предложил добавить перенос непосредственно, вместо того чтобы восстановить его в CF. Этот подход имеет фатальный недостаток: он смешивает входящую перенос в эту итерацию с исходящим переносом, идущим на следующую итерацию.

---

Также sahf - это набор AH из флагов. lahf загружает AH во флаги (и он работает на всех низких 8 бит флагов.Сопоставьте эти инструкции; не используйте lahf на 0 или 1, которые вы получили от setc.

Прочтите инструкцию по установке insn для любых insns, которые, похоже, не делают то, что вы ожидаете. См https://stackoverflow.com/tags/x86/info

Answer 2

Если размер массива известен во время компиляции, вы могли бы сделать что-то вроде этого:

#include <inttypes.h> 
#include <malloc.h> 
#include <stdio.h> 
#include <memory.h> 

#define str(s) #s 
#define xstr(s) str(s) 

#define ARRAYSIZE 4 

asm(".macro AddArray2 p1, p2, from, to\n\t" 
    "movq (\\from*8)(\\p2), %rax\n\t" 
    "adcq %rax, (\\from*8)(\\p1)\n\t" 
    ".if \\to-\\from\n\t" 
    " AddArray2 \\p1, \\p2, \"(\\from+1)\", \\to\n\t" 
    ".endif\n\t" 
    ".endm\n"); 

asm(".macro AddArray p1, p2, p3\n\t" 
    "movq (\\p2), %rax\n\t" 
    "addq %rax, (\\p1)\n\t" 
    ".if \\p3-1\n\t" 
    " AddArray2 \\p1, \\p2, 1, (\\p3-1)\n\t" 
    ".endif\n\t" 
    ".endm"); 

int main() 
{ 
    unsigned char carry; 

    // assert(ARRAYSIZE > 0); 

    // Create the arrays 
    uint64_t *anum = (uint64_t *)malloc(ARRAYSIZE * sizeof(uint64_t)); 
    uint64_t *bnum = (uint64_t *)malloc(ARRAYSIZE * sizeof(uint64_t)); 

    // Put some data in 
    memset(anum, 0xff, ARRAYSIZE * sizeof(uint64_t)); 
    memset(bnum, 0, ARRAYSIZE * sizeof(uint64_t)); 
    bnum[0] = 1; 

    // Print the arrays before the add 
    printf("anum: "); 
    for (int x=0; x < ARRAYSIZE; x++) 
    { 
     printf("%I64x ", anum[x]); 
    } 
    printf("\nbnum: "); 
    for (int x=0; x < ARRAYSIZE; x++) 
    { 
     printf("%I64x ", bnum[x]); 
    } 
    printf("\n"); 

    // Add the arrays 
    asm ("AddArray %[anum], %[bnum], " xstr(ARRAYSIZE) "\n\t" 
     "setc %[carry]" // Get the flags from the final add 

     : [carry] "=q"(carry) 
     : [anum] "r" (anum), [bnum] "r" (bnum) 
     : "rax", "cc", "memory" 
    ); 

    // Print the result 
    printf("Result: "); 
    for (int x=0; x < ARRAYSIZE; x++) 
    { 
     printf("%I64x ", anum[x]); 
    } 
    printf(": %d\n", carry); 
} 

Это дает примерно такой код:

mov (%rsi),%rax 
add %rax,(%rbx) 
mov 0x8(%rsi),%rax 
adc %rax,0x8(%rbx) 
mov 0x10(%rsi),%rax 
adc %rax,0x10(%rbx) 
mov 0x18(%rsi),%rax 
adc %rax,0x18(%rbx) 
setb %bpl 

С добавлением 1 к воле всех F в полностью переполняют все, вывод из приведенного выше кода:

anum: ffffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffff 
bnum: 1 0 0 0 
Result: 0 0 0 0 : 1 

В качестве источника десять, ARRAYSIZE может составлять до 100 элементов (из-за ограничений на вложенность глубины gnu). Похоже, этого должно быть достаточно ...