Использование флага переноса после смены

Question

Для части div / mod следующего кода:

int pow(int x, unsigned int n)
{
    int y = 1;
    while (n > 1)
    {
        auto m = n%2;
        n = n/2;
        if (m)
            y *= x;
        x = x*x;
    }
    return x*y;
}

Я ожидаю, что сборка будет выглядеть как

shr n
cmovc y, yx

Но gcc / clang и даже icc не используютФлаг переноса здесь (с использованием 2 регистров и / / взамен): https://godbolt.org/z/L6VUZ1

Поэтому мне интересно, каким будет наилучший способ, если вы закодируете его вручную и почему (ILP, зависимости, ...).

Answer 1

test/je может слиться в один макрос на основных процессорах Intel и AMD, поэтому в коде с ветвлением вы экономите только размер кода и стоите 1 цикл задержки обнаружения ветвления, используя выход CFсдвига вместо более раннего test/je.

(К сожалению, здесь gcc действительно тупой и использует test edx,edx в результате and edx,1, вместо того, чтобы просто использовать test dl,1 или лучше test sil,1 длясохраните также mov. test esi,1 будет использовать кодировку imm32, потому что для test нет кодировки test r/m32, imm8, поэтому компиляторы знают, что нужно читать узкие регистры для test.)

Но вреализация без ответвлений, которую использует clang, да, вы бы сохранили моп, используя выход CF для cmovc вместо того, чтобы отдельно вычислять вход для cmove с test.Вы по-прежнему не сокращаете критический путь, потому что test и shr могут работать параллельно, а основные процессоры, такие как Haswell или Ryzen, имеют достаточно широкие конвейеры, чтобы полностью использовать весь ILP, и просто узкое место в imul переносимом цикломцепочка зависимостей.(https://agner.org/optimize/).

На самом деле это узкое место cmov -> imul -> для следующей итерации для y. В Haswell и более ранних версиях cmov имеет задержку в 2 цикла (2 мопа)), поэтому общая цепочка депозита составляет 2 + 3 = 5 циклов. (Конвейерные множители означают, что выполнение дополнительного умножения y*=1 не замедляет часть x*=x или наоборот; они оба могут быть в полете сразу, простоне запускаться в одном и том же цикле.)

Если вы неоднократно используете один и тот же n для разных баз, версия с ветвлением должна хорошо прогнозироваться и быть очень хорошей, потому что прогнозирование ветвлений + спекулятивное выполнение разъединяет зависимость от данныхцепочки.

В противном случае, вероятно, лучше съесть более длительную задержку версии без ветвей, чем страдать от промахов веток.