Безветвевой счет с ведущими нулями на 32-битном RISC-V без расширения Zbb

Контекстом этого вопроса является создание устойчивой к побочным каналам реализации квадратного корня одинарной точности, совместимого с IEEE-754, для 32-битной платформы RISC-V без аппаратной поддержки арифметики с плавающей запятой и без расширения Zbb для расширенных возможностей. битовые манипуляции. Целочисленные умножения, в частности инструкции MUL и MULHU, поддерживаются аппаратным обеспечением и можно предположить, что они имеют фиксированную задержку. Подсчет начальных нулевых битов необходим для нормализации субнормальных операндов, а эмуляция CLZ должна быть неветвящейся из-за конструкции, устойчивой к побочным каналам.

Я начал с кода C99 для 32-битного счетчика начальных нулей, который я использовал двадцать лет назад на процессорах ARMv4t. Это полнодиапазонная реализация, т. е. она возвращает 32 при вводе нуля.

uint32_t cntlz (uint32_t a)
{ 
    uint32_t n = 0;
#if 0
    n = __builtin_clz (a);
#else
    n = !a + 1;
    if (a < 0x00010000u) { n |= 16;  a <<= 16; }
    if (a < 0x01000000u) { n |=  8;  a <<=  8; }
    if (a < 0x10000000u) { n |=  4;  a <<=  4; }
    if (a < 0x40000000u) { n +=  2;  a <<=  2; }
    n = n - (a >> 31);
#endif
    return n;
}

В качестве проверки работоспособности я скомпилировал приведенный выше исходный код с помощью clang 18.1 -marm -march=armv4t, в результате чего получился следующий код, который при 16 инструкциях без возврата функции использует на одну инструкцию больше, чем лучшая известная мне реализация ARMv4t (которая использует 15 инструкций без функции возвращаться):

cntlz:
        mov     r1, #1
        cmp     r0, #0
        moveq   r1, #2
        cmp     r0, #65536
        lsllo   r0, r0, #16
        orrlo   r1, r1, #16
        cmp     r0, #16777216
        lsllo   r0, r0, #8
        orrlo   r1, r1, #8
        cmp     r0, #268435456
        lsllo   r0, r0, #4
        orrlo   r1, r1, #4
        cmp     r0, #1073741824
        addlo   r1, r1, #2
        lsllo   r0, r0, #2
        add     r0, r1, r0, asr #31
        bx      lr

В настоящее время я работаю без доступа к платформе разработки RISC-V и использую Compiler Explorer для компиляции для 32-битной цели RISC-V. Я не мог понять, как правильно указать расширения, чтобы отключить поддержку чисел с плавающей запятой, поэтому я использовал clang 18.1 с -march=rv32gc, в результате чего был сгенерирован следующий ассемблерный код:

cntlz:                                  # @cntlz
        seqz    a1, a0
        srli    a2, a0, 16
        seqz    a2, a2
        slli    a2, a2, 4
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 24
        seqz    a2, a2
        slli    a2, a2, 3
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 28
        seqz    a2, a2
        slli    a2, a2, 2
        or      a1, a1, a2
        sll     a0, a0, a2
        srli    a2, a0, 30
        seqz    a2, a2
        slli    a2, a2, 1
        or      a1, a1, a2
        sll     a0, a0, a2
        srai    a0, a0, 31
        add     a0, a0, a1
        addi    a0, a0, 1             
        ret

Я не могу выделить каких-либо улучшений в коде, сгенерированном Clang, то есть он выглядит максимально сжатым. Я знаю, что реализации RISC-V могут реализовать слияние макроопераций. См.: Кристофер Челио и др., «Обновленный вариант использования компьютера с сокращенным набором команд: «Избежание раздувания ISA с помощью Macro-Op Fusion для RISC-V», технический отчет Калифорнийского университета в Беркли EECS-2016-130. Но ни одна из идиом слияния, обсуждаемых в отчете, похоже, не применима к этому коду, что заставляет меня предположить, что время выполнения равно 24 циклов для этой последовательности из 24 инструкций (без возврата функции). Мне было любопытно, что разрешает __builtin_clz(). Компиляция с включенным этим путем кода приводит к последовательности из 31 инструкции, которая преобразует ведущие нули в выровненную по левому краю маску из 1 бит и. затем применяет к маске вычисление количества населения:

        srli    a1, a0, 1
        or      a0, a0, a1
        srli    a1, a0, 2
        or      a0, a0, a1
        srli    a1, a0, 4
        or      a0, a0, a1
        srli    a1, a0, 8
        or      a0, a0, a1
        srli    a1, a0, 16
        or      a0, a0, a1
        not     a0, a0          // a0 now left-aligned mask of 1-bits
        srli    a1, a0, 1
        lui     a2, 349525
        addi    a2, a2, 1365
        and     a1, a1, a2
        sub     a0, a0, a1
        lui     a1, 209715
        addi    a1, a1, 819
        and     a2, a0, a1
        srli    a0, a0, 2
        and     a0, a0, a1
        add     a0, a0, a2
        srli    a1, a0, 4
        add     a0, a0, a1
        lui     a1, 61681
        addi    a1, a1, -241
        and     a0, a0, a1
        lui     a1, 4112
        addi    a1, a1, 257
        mul     a0, a0, a1
        srli    a0, a0, 24
        ret

Опять же, я не уверен, какие инструкции здесь могут быть подвергнуты слиянию макроопераций, но наиболее вероятным кандидатом кажется идиома LUI/ADDI, используемая для немедленной загрузки 32-битных данных, аналогично тому, как современные процессоры ARM объединяют MOVW/ MOVTпары. При таком предположении код все равно будет медленнее, чем тот, который у меня есть сейчас. Я попробовал полдюжины дополнительных целочисленных вариантов 32-битной эмуляции CLZ и не нашел ни одного, который приводил бы к меньшему числу 24 инструкций. Я также поискал в Интернете и не смог найти ничего лучше моего текущего кода.

Существуют ли какие-либо внеотраслевые полнофункциональные реализации счета ведущих нулей для 32-битных платформ RISC-V, требующие менее 24 тактов? Консервативно, я хочу предположить отсутствие слияния макроопераций, поскольку это кажется дорогостоящей функцией в микроконтроллере начального уровня, но ответы, основанные на слиянии макроопераций, присутствующем в существующих реализациях RISC-V, также приветствуются.

Примечание. Табличные методы в этом контексте не подходят, поскольку доступ к таблице может вызвать промахи в кэше, которые можно использовать для атак по побочным каналам.

Обновление от 09.06.2024: Проработав над этой проблемой еще 1,5 дня, я нашел вариант, который должен уменьшить количество требуемых инструкций с 24 до 22, однако не все компиляторы действительно могут доставить нужный код.

Основное наблюдение заключается в том, что RISC-V ISA не ортогональна по отношению к инструкциям типа SET, поскольку она поддерживает только разновидность «меньше чем». Другие сравнения могут потребовать инверсии сравнения с последующей инверсией результата, например, с помощью XOR 1 или применения SEQZ, добавляя по одной инструкции для каждого экземпляра. Моя идея теперь состоит в том, чтобы избежать этой инверсии для каждого экземпляра, транспонируя положительный операнд в отрицательный один раз, позволяя напрямую использовать сравнения «меньше чем». Выражено в переносимом коде C++11 и снабжено инструкциями RISC-V, которые, как я ожидаю, будут сгенерированы:

// https://stackoverflow.com/a/74563384/780717
// Only applies right shift to non-negative values to avoid implementation-defined behavior
int32_t sra (int32_t x, int32_t y)
{
     return (x < 0) ? (~(~x >> y)) : (x >> y);
}

uint32_t cntlz_rv32 (uint32_t a)
{
    uint32_t n, t;
    int32_t as;
    n = !a;                                           // 1: seqz
    t = ((a >> 16)!=0)*16; n = n - t; a = a >> t;     // 5: srli, snez, slli, sub, srl
    as = (int32_t)(~a);                               // 1: not
    t = (as < -256) * 8; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <  -16) * 4; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <   -4) * 2; n = n - t; as = sra (as, t); // 4: slti, slli, sub, sra
    t = (as <   -2) * 1; n = n - t;                   // 2: slti, sub
    n += 31;                                          // 1: addi
    return n;                                         // 22 instructions total w/o ret
}

В gcc 13.3 (не 14.1) генерируется следующая последовательность из 22 инструкций без ветвей (не считая ret):

cntlz_rv32(unsigned int):
        srli    a3,a0,16
        snez    a3,a3
        slli    a3,a3,4
        srl     a4,a0,a3
        not     a4,a4
        slti    a1,a4,-256
        slli    a1,a1,3
        sra     a4,a4,a1
        slti    a2,a4,-16
        slli    a2,a2,2
        seqz    a5,a0
        addi    a5,a5,31
        sra     a0,a4,a2
        slti    a4,a0,-4
        sub     a5,a5,a3
        slli    a4,a4,1
        sub     a5,a5,a1
        sub     a5,a5,a2
        sra     a0,a0,a4
        sub     a5,a5,a4
        slti    a0,a0,-2
        sub     a0,a5,a0
        ret

По непонятным мне причинам gcc 14.1 отказывается генерировать ожидаемый SLTI с помощью -256. Перемещая сравнение до применения дополнения до 1, необходимо добавить SEQZ, чтобы инвертировать результат сравнения. clang 18.1 генерирует неэффективную последовательность из 33 инструкций для приведенного выше исходного кода по непонятной мне причине.