Что может сделать компилятор с информацией разветвления?

Ответ 1

Существует два возможных источника необходимой информации:

• Там Руководство разработчика программного обеспечения для архитектуры Intel 64 и IA-32 (3 тома). Это огромная работа, которая развивалась на протяжении десятилетий. Это лучшая ссылка, которую я знаю по многим предметам, в том числе с плавающей запятой. В этом случае вы хотите проверить том 2, ссылку на набор команд.
• Там Справочное руководство по оптимизации оптики Intel 64 и IA-32. Это расскажет вам в несколько кратких терминах, что ожидать от каждой микроархитектуры.

Теперь, я не знаю, что вы подразумеваете под "современным процессором Pentium", это 2013 год, правильно? Нет никаких Pentiums больше...

Набор инструкций поддерживает сообщение процессору, если ожидается, что ветвь будет взята или не принята префиксом для команд условной ветки (таких как JC, JZ и т.д.). См. Том 2А раздела (1), раздел 2.1.1 (версии, который у меня есть). Префиксы инструкций. Существуют префиксы 2E и 3E для не взятых и принятых соответственно.

Что касается того, действительно ли эти префиксы имеют какой-либо эффект, если мы сможем получить эту информацию, это будет в Справочном руководстве по оптимизации, разделе для микроархитектуры, которое вы хотите (и я уверен, что это не будет Pentium).

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

Нет смысла воспроизводить это здесь, так как вы можете бесплатно скачать руководство. Вкратце:

• Устранить ветки с помощью условных инструкций (CMOV, SETcc),
• Рассмотрим алгоритм статического предсказания (3.4.1.3),
• Встраивание
• Развертка Loop

Кроме того, некоторые компиляторы GCC, например, даже когда CMOV невозможно, часто выполняют побитную арифметику, чтобы выбрать одну из двух различных вычисляемых вещей, тем самым избегая ветвей. Он делает это особенно с инструкциями SSE при векторизации циклов.

В основном, статические условия:

• Предполагаются безусловные ветки (... вид ожидаемого...)
• Непрямые ветки не прогнозируются (из-за зависимости данных)
• Предполагается, что будут учтены предыдущие условные обозначения (полезно для циклов)
• Предполагаемые отклонения вперед не принимаются

Вероятно, вы хотите прочитать весь раздел 3.4.1.

Ответ 2

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

Компилятор может переставить вложенные тесты, так что тот, который чаще всего приводит к короткому замыканию, может использоваться, чтобы избежать выполнения теста на что-то с 50% -ной скоростью передачи.

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

Это лишь некоторые примеры. Я уверен, что есть другие, о которых я не думал.

Ответ 3

Сверху моей головы у вас есть две возможности.

Вариант №1: Сообщите компилятору подсказки и дайте компилятору упорядочить код соответствующим образом. Например, GCC поддерживает следующее...

__builtin_expect((long)!!(x), 1L)  /* GNU C to indicate that <x> will likely be TRUE */
__builtin_expect((long)!!(x), 0L)  /* GNU C to indicate that <x> will likely be FALSE */

Если вы поместите их в макроформа, например...

#if <some condition to indicate support>
    #define LIKELY(x)    __builtin_expect((long)!!(x), 1L)
    #define UNLIKELY(x)  __builtin_expect((long)!!(x), 0L)
#else
    #define LIKELY(x)   (x)
    #define UNLIKELY(x) (x)
#endif

... теперь вы можете использовать их как...

if (LIKELY (x != 0)) {
    /* DO SOMETHING */
} else {
    /* DO SOMETHING ELSE */
}

Это дает компилятору возможность организовать ветки в соответствии с алгоритмами предсказания статического ветвления и/или если процессор и компилятор поддерживают его, использовать инструкции, которые указывают, какая ветка более вероятна.

Вариант № 2: используйте математику, чтобы избежать ветвления.

if (a < b)
    y = C;
else
    y = D;

Это можно переписать как...

x = -(a < b);   /* x = -1 if a < b, x = 0 if a >= b */
x &= (C - D);   /* x = C - D if a < b, x = 0 if a >= b */
x += D;         /* x = C if a < b, x = D if a >= b */

Надеюсь, что это поможет.

Ответ 4

Это может сделать провал (т.е. случай, когда ветка не занята) наиболее используемый путь. Это имеет два больших эффекта:

• только одна ветвь может быть принята за такт или на некоторых процессорах даже за 2 такта, поэтому, если есть какие-либо другие ветки (как правило, большинство кода имеет значение в цикле), принятая ветка - плохая новость, не принятая ветвь меньше.
• Когда предиктор ветвления ошибочен, код, который он должен выполнить, с большей вероятностью будет находиться в кеше кода (или кэше μop, где это применимо). Если бы это было не так, это было бы двойной попыткой перезапуска трубопровода и ожидания промаха в кеше. Это меньше проблем в большинстве циклов, так как обе стороны ветки, скорее всего, находятся в кеше, но они вступают в игру в больших циклах и другом коде.

Он также может решить, следует ли делать if-conversion на основе лучших данных, чем эвристическое предположение. Если-преобразование может показаться "всегда хорошей идеей", но это не так, они только "часто являются хорошей идеей". Если ветвь в реализации ветвления очень хорошо предсказана, код if-convert может быть медленнее.