Заставить GCC использовать логику переноса для арифметики произвольной точности без встроенного ассемблера?

При работе с арифметикой произвольной точности (например, 512-битными целыми числами) есть ли способ заставить GCC использовать ADC и аналогичные инструкции без использования встроенного ассемблера?

Первый взгляд на исходный код GMP показывает, что у них просто есть реализации сборки для каждой поддерживаемой платформы.

Вот написанный мной тестовый код, который добавляет два 128-битных числа из командной строки и выводит результат. (Вдохновленный add_n mini-gmp):

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int main (int argc, char **argv)
{
    uint32_t a[4];
    uint32_t b[4];
    uint32_t c[4];
    uint32_t carry = 0;

    for (int i = 0; i < 4; ++i)
    {
        a[i] = strtoul (argv[i+1], NULL, 16);
        b[i] = strtoul (argv[i+5], NULL, 16);
    }

    for (int i = 0; i < 4; ++i)
    {
        uint32_t aa = a[i];
        uint32_t bb = b[i];
        uint32_t r = aa + carry;
        carry = (r < carry);
        r += bb;
        carry += (r < bb);
        c[i] = r;
    }

    printf ("%08X%08X%08X%08X + %08X%08X%08X%08X =\n", a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0]);
    printf ("%08X%08X%08X%08X\n", c[3], c[2], c[1], c[0]);

    return 0;
}

GCC -O3 -std=c99 Не производит никаких adc инструкций, проверенных objdump. Моя версия gcc — i686-pc-mingw32-gcc (GCC) 4.5.2.


person morrog    schedule 29.03.2013    source источник
comment
Неа. Это не произойдет так просто (если это вообще возможно). Это одна из причин, почему GMP использует встроенную сборку.   -  person Mysticial    schedule 29.03.2013
comment
@Mysticial: я согласен, но я хотел задать вопрос на всякий случай. Во время поиска в Google я увидел мало осмысленных дискуссий по этой теме.   -  person morrog    schedule 29.03.2013
comment
Да, я точно знаю, о чем вы говорите, поскольку я пытался сделать то же самое раньше и с треском провалился. Этого не может сделать не только GCC, но и MSVC, и ICC. Короче говоря, для обнаружения намерения требуется очень специализированный проход оптимизации компилятора, который настолько нишев, что ни один автор компилятора не стал бы тратить время на такую ​​вещь.   -  person Mysticial    schedule 29.03.2013
comment
@Mysticial, я заставил ICC сделать это эффективно, используя встроенный заголовок _addcarry_u64 ="добавление нескольких слов с использованием флага переноса"> stackoverflow.com/questions/29029572/   -  person Z boson    schedule 23.03.2015
comment
@Zboson ICC и MSVC не имели такой встроенной функции до недавнего времени. (~ 1 год назад)   -  person Mysticial    schedule 23.03.2015
comment
@ Mysticial, вау, я не знал, что у MSVC есть _addcarry_u64. Я только что попробовал, и действительно, он выдает 1x add и 3x adc! Что там с GCC и Clang?   -  person Z boson    schedule 23.03.2015


Ответы (1)


GCC будет использовать флаг переноса, если он увидит, что ему нужно:
Например, при добавлении двух значений uint64_t на 32-разрядной машине это должно привести к в один 32-битный ADD плюс один 32-битный ADC. Но кроме тех случаев, когда компилятор вынужден использовать перенос, его, вероятно, нельзя убедить сделать это без ассемблера. Следовательно, может быть полезно использовать самый большой доступный целочисленный тип, чтобы позволить GCC оптимизировать операции, эффективно сообщая ему, что отдельные «компоненты» значения принадлежат друг другу.

Для простого сложения другим способом вычисления переноса может быть просмотр соответствующих битов в операндах, например:

uint32_t aa,bb,rr;
bool msbA, msbB, msbR, carry;
// ...

rr = aa+bb;

msbA = aa >= (1<<31); // equivalent: (aa & (1<<31)) != 0;
msbB = bb >= (1<<31);
msbR = rr >= (1<<31);


carry = (msbA && msbB) || ( !msbR && ( msbA || msbB) );
person JimmyB    schedule 29.03.2013
comment
Использование большего целочисленного типа только поднимает проблему на более высокий уровень. Если в GCC нет 512-битных целочисленных типов, вам все равно придется возиться с логикой переноса. - person Mysticial; 29.03.2013
comment
Конечно, рано или поздно вам обязательно придется вычислять свой собственный керри. Но при использовании uint64_t вместо uint32_t, например, вы сэкономите себе 50% 'ручных' вычислений флага переноса и времени их обработки. - person JimmyB; 29.03.2013
comment
Если вы стремитесь к скорости (как и большинство людей в пакетах с множественной точностью), вы можете вычислить перенос, используя aa, bb и rr и затем сдвиг вправо на 31 бит, сэкономив 2 сдвига. Вы также, вероятно, хотите, чтобы операторы без ветвления & | ~ потому что эти биты, по-видимому, очень трудно предсказать, и поэтому предсказатель ветвления, скорее всего, ошибется при выполнении выражения. - person Ira Baxter; 19.03.2015
comment
Еще один дешевый прием — использовать только 31 бит 32-битного слова (а еще лучше — 63 из 64 бит). Вы отказываетесь от 3% или меньше емкости вашего хранилища, но бит переноса вычисляется для вас в старшем разряде суммы. - person Ira Baxter; 19.03.2015
comment
Кстати, для беззнаковых типов carry == ((a+b) < a). - person JimmyB; 19.03.2015
comment
Если вам время от времени требуется арифметика с высокой точностью, то неуклюжее выполнение вычислений переноса в C не окажет реального влияния на производительность приложения в целом. Получение переноса, управляемого компилятором, будет иметь значение только в том случае, если ваши вычисления очень сильно используют арифметику с множественной точностью. Тогда вы, вероятно, обнаружите, что реальной ценой является деление-множественная точность. - person Ira Baxter; 20.03.2015
comment
@HannoBinder: ((a+b)‹a) работает на языках (таких как C), которые не допускают переполнения. Я работаю с языком, в котором результаты после переполнения явно определяются как неопределенное поведение. (Жизнь иногда непроста, когда ты зеленый). - person Ira Baxter; 20.03.2015
comment
Возможно, стоит взглянуть на встроенные функции целочисленного переполнения GCC: gcc.gnu .org/onlinedocs/gcc/Integer-Overflow-Builtins.html - person Till Kolditz; 07.09.2016