Почему нижний тестовый цикл предпочтительнее?

Question

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

while (condition) {
    ...
}

изменяется на:

if (condition) {
     do {
         ...
     } while (condition);
}

в отношении машинно-независимой оптимизации, почему последняя предпочтительнее?

Answer 1

Без оптимизации компилятора первый цикл переходит к ассемблерному коду:

  @@:
cmp ... ; or test ...
jz @f

...
jmp @b

В то время как второй цикл идет примерно так:

jmp bottom

  @@:
...

  bottom:
cmp ... ; or test ...
jz @b

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

Однако самое важное, что для первого цикла есть две ветви, доступные для каждой итерации цикла (2N), тогда как во второй, каждая итерация цикла имеет только одну ветвь с фиксированными издержками первого безусловного прыжок (N+1).

Для получения дополнительной информации об оптимизации цикла см. Стр. 88 этого руководства по оптимизации сборки .

Answer 2

В представлении сборки цикл - это просто инструкция перехода, которая переходит назад к коду.Поэтому компилятору необходимо вставить переход в конце цикла.

Многие наборы команд, такие как x86, ARM, MIPS, предоставляют инструкции условного перехода / перехода.Будет ли переход выполнен в зависимости от условия, указанного в инструкции.

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

Answer 3

Вы частично ошиблись.Типичная оптимизация такова:

    jmp $test;
$loop:
    ; loop statements
$test:
    test <condition>;
    branch-true $loop;

, а не эта:

$loop:
    test <condition>;
    branch-false $end;
    ; loop statements
    branch loop;
$end:

, которая имеет две ветви на каждой итерации цикла.Другое преимущество состоит в том, что часть после начального перехода идентична коду, сгенерированному для do/while.