Небольшие ветки в современных процессорах

Question

Как современные процессоры, такие как Kaby Lake, справляются с небольшими ветвями? (в приведенном ниже коде это переход к метке LBB1_67). Из того, что я знаю, ветвь не будет вредной, потому что переход уступает 16-байтовому размеру блока, который является размером окна декодирования.

Или возможно, что из-за макрооперации ветвь будет полностью удалена?

        sbb     rdx, qword ptr [rbx - 8]
        setb    r8b
        setl    r9b
        mov     rdi, qword ptr [rbx]
        mov     rsi, qword ptr [rbx + 8]
        vmovdqu xmm0, xmmword ptr [rbx + 16]
        cmp     cl, 18
        je      .LBB1_67
        mov     r9d, r8d
.LBB1_67:                               #   in Loop: Header=BB1_63 Depth=1
        vpcmpeqb        xmm0, xmm0, xmmword ptr [rbx - 16]
        vpmovmskb       ecx, xmm0
        cmp     ecx, 65535
        sete    cl
        cmp     rdi, qword ptr [rbx - 32]
        sbb     rsi, qword ptr [rbx - 24]
        setb    dl
        and     dl, cl
        or      dl, r9b

Answer 1

Не существует особых случаев для коротких расстояний между ветвями в любых процессорах x86. Даже безусловный jmp следующей инструкции (архитектурно nop) требуется правильное предсказание ветвления для эффективной обработки; если вы кладете достаточно их в ряд, у вас заканчиваются записи BTB, и производительность падает с обрыва. Медленная jmp-инструкция

Выборка / декодирование - только незначительная проблема; да, очень короткая ветвь в одной и той же строке кэша все еще будет попадать в L1i и, вероятно, в кэш uop. Но маловероятно, что декодеры будут в особом случае делать прогнозируемый принятый скачок вперед и использовать предварительное декодирование нахождения границ команд из одного блока, который включает в себя как ветвь, так и цель.

Когда инструкция декодируется в uops и подается во внешний интерфейс, значения регистров недоступны; они доступны только в бэк-энде выполнения вне очереди.

Основная проблема заключается в том, что когда инструкции после .LBB1_67: Выполните, архитектурное состояние отличается в зависимости от того, была ли ветвь взята или нет. Как и состояние микроархитектуры (RAT = Таблица распределения регистров).

Или:

• r9 зависит от sbb / setl результат (mov r9d, r8d не бегал)
• r9 зависит от sbb / setb результат (mov r9d, r8d побежал)

Условные ветви называются "управляющими зависимостями" в терминологии компьютерной архитектуры. Предсказание ветвлений + спекулятивное выполнение позволяет избежать превращения управляющих зависимостей в зависимости от данных. Если je was predicted not taken, the Setl result (the old value of г9 ) is overwritten by mov` и больше нигде не доступен.

Там нет никакого способа оправиться от этого после обнаружения неверного прогноза в je (на самом деле должен был быть взят), особенно в общем случае. Текущие процессоры x86 не пытаются искать альтернативный путь, воссоединяющийся с выбранным путем, или не выясняют, что он делает.

Если cl не был готов в течение долгого времени, поэтому неверный прогноз не был обнаружен в течение длительного времени, многие инструкции после or dl, r9b мог быть выполнен с использованием неправильных входных данных. В общем случае единственный способ надежного и эффективного восстановления - это отказаться от всей работы, выполненной по инструкциям, с "неправильного" пути. Обнаружение этого vpcmpeqb xmm0, [rbx - 16] Например, все еще работает в любом случае трудно, и не искал. (Современный Intel, так как Nehalem, я думаю, имеет буфер порядка ветвлений (BOB), который снимает RAT на ветвях, обеспечивая эффективный откат до пропадания ветвления, как только обнаружение выполнения обнаруживает, в то же время позволяя выполнение не по порядку выполнения по более ранним инструкциям. продолжить во время отката. До этого промах филиала должен был откатиться до состояния выхода на пенсию.)

---

Некоторые процессоры для некоторых не x86 ISA (например, PowerPC, я думаю) экспериментировали с поворотными ветвями, которые пропускают ровно 1 инструкцию в предикацию (зависимость от данных), а не спекулируют мимо них. напр., динамическое прогнозирование гамака для неориентированных архитектур наборов инструкций обсуждает эту идею и даже решает, следует ли прогнозировать или нет для каждой ветви. Если ваша история предсказания ветвлений говорит, что эта ветвь предсказывает плохо, предсказание этого может быть хорошим. (Ветвь гамака - это та, которая переходит вперед на одну или пару инструкций. Обнаружение точно 1 случая команды тривиально на ISA со словами инструкций фиксированной ширины, как RISC, но сложно на x86.)

В этом случае x86 имеет cmovcc инструкция, операция выбора ALU, которая производит один из двух входов в зависимости от состояния флага. cmove r9d, r8d вместо cmp / je сделает это невосприимчивым к ошибочным прогнозам ветвей, но ценой введения зависимости данных от cl а также r8d для инструкций, которые используют r9d , Процессор Intel не пытается сделать это для вас.

(В Broadwell и более поздних версиях Intel, cmov составляет всего 1 моп, вместо 2. cmp/jcc - 1 моп, а mov само по себе тоже 1 моп, так что в не взятом случае cmov также меньше мопов для фронтэнда. И в взятом случае, взятая ветвь может привести к появлению пузырьков в конвейере, даже если прогноз правильно, в зависимости от того, насколько высок код пропускной способности кода: могут ли его поглотить очереди между этапами.)

Смотрите флаг оптимизации gcc -O3 делает код медленнее, чем -O2 для случая, когда CMOV медленнее, чем ветвь, потому что введение зависимости от данных плохо.