Оптимизация для pentium процессора - переходы и ветви

12. ПЕРЕХОДЫ И ВЕТВИ
====================
 Pentium пытается предсказать - произойдет ли условный переход, или нет. Для
этого у него есть "буффер предсказания переходов" (BTB) в котором храниться
история 256 последних переходов.

Pentium без MMX, делает предсказания на основе двух последних событий.
Предполагается, что условный переход произойдет, если он произошел в прошлый
или в позопрошлый раз. Соответственно, если условный преход не произошел в
последние два раза, то предполагается, что он не произойдет и сейчас. Если
условный переход,не встречался ранее (или отсутствует в BTB), то считается что
он не произойдет.

Pentium MMX (или Pentium Pro) делают свой анализ на основе последних четырех
событий, т.е. может предсказать простой повторяющийся участок. Условный
переход, который не встречался ранее (или отсутствует в BTB), будет
считаться происходящим, если он направлен назад (т.н. цикл) и не происходящем,
если он направлен вперед.

Если условный переход предсказан правильно,(т.е.если догадка была правильная),
то он будет исполнен за 1 такт. Непредсказанный переход исполниться за 4
такта, если инструкция в U-трубе и за 5 тактов, если в V-трубе.

Задержка из-за непредсказанного перехода будет намного большей, если сразу
за переходом будет инструкция другого перехода или вызова подпрограммы.
Pentium ведет себя очень странно в данной ситуации. Механизм предсказания
переходов полностью дезориентируется: второй переход может не предсказаться,
даже если он должен предсказаться и наоборот. И это проблема остается, в
следующий раз переход снова не будет предсказан. Более того, любой
безусловный переход или вызов подпрограммы потребуют дополнительных тактов,
если будут стоять первой инструкцией после перехода. Для того что бы избегать
этого вы должны избегать использовать инструкции переходов или вызовов
подпрограмм сразу в начале новой ветви. Пример:

        DEC     EAX
        JNZ     L1
        CMP     EBX,ECX
        NOP
        JB      L2
        ...
L1:     NOP
        NOP
        CALL    P
        ...
L2:     NOP
        RET

Pentium MMX так же может потребоваться дополнительные такты, но только в том
случае если две инструкции ветвления находятся в одном, выровненном, блоке
DWORD. Эту проблему можно решить использовав переход near вместо short во
второй инструкции ветвления, что бы сделать ее длиннее, но этот метод не
поможет вам на Pentium без MMX, так что вам придется использовать инструкции
типа NOP, что бы решить эту проблему на обоих процессорах.

Алгоритм предсказания переходов наиболее оптимален для цикла, где проверка
расположена в конце, как в этом примере:

        MOV ECX, [N]
L:      MOV [EDI],EAX
        ADD EDI,4
        DEC ECX
        JNZ L

Поскольку алгоритм предсказания переходов на Pentium без MMX несимметричный,
то могут встретиться участки, где можно добиться ускорения путем
преобразования кода. Рассмотрим следующую конструкцию:

        TEST EAX,EAX
        JNZ  SHORT A1
        CALL F0
        JMP  SHORT E
A1:     CALL F1
E:

Если F0 вызывается более часто, чем F1, а F1 редко вызывается дважды, то вы
можете улучшить предсказание переходов поменяв местами обе ветви. Тем не менее
это будет немножко неоптимально для Pentium MMX и Pentium Pro, которые могут
не предсказывать переход, если его не в буффере предсказания переходов. Другой
причиной целесообразности обмена может служить то, что кеш кода используется
не эффективно, когда реже используемый переход исполняется раньше. Вы можете
вставить два NOP перед каждым CALL, что бы предотвратить замедление в случае
неправильного предсказания перехода.

Многократные переходы (структуры case) лучше всего реализуются на Pentium без
MMX списком адресов переходов. при этом адреса переходов или вызовов
подпрограмм хранятся в сегменте данных, а не кода. На Pentium MMX и Pentium
PRO косвенные переходы должны быть предсказуемы, для максимальной
эффективности, таким образом на этих процессорах лучше использовать
множественные двунаправленные ветвления.

Все вызовы подпрограмм должны быть снабжены инструкциями возврата, т.к. эти
инструкции правильно предсказываются на Pentium MMX и Pentium Pro.

Избеганее ветвления
-------------------
Иногда можно получить тот же эффект, не используя ветвления, всего лишь
удачной манипуляцией битов и флагов. Например мы можем вычислить абсолютное
значение числа со знаком, не используя ветвления:
MOV EDX,EAX
SAR EDX,31
XOR EAX,EDX
SUB EAX,EDX

Флаг переноса очень полезен, для такого рода трюков.
Устанавливается если величина ноль:  CMP [значение], 1
Устанавливается, если величина не ноль:  XOR EAX, EAX / CMP EAX, [значение]
Увеличение счетчика, если перенос:  ADC EAX, 0
Установка бита каждый раз, когда перенос:  RCL  EAX, 1
Создает битовую маску, если перенос:  SBB, EAX, EAX

Этот пример находит минимум из двух без значных чисел: если (b<a), то a=b;
SUB EBX,EAX
SBB ECX,ECX
AND ECX,EBX
ADD EAX,ECX

Этот пример выбирает между двумя числами: если (a не 0), то a=b иначе a = c;
CMP EAX,1
SBB EAX,EAX
AND ECX,EAX
XOR EAX,-1
AND EAX,EBX
OR  EAX,ECX

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

На Pentium Pro вы можете использовать инструкции условного перемещения для
того, что бы избавиться от лишнего ветвления.