Управление порядком выполнения инструкций

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

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

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

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

Вторая реализация является более эффективной, поскольку к моменту декодирования и обращения за данными инструкции y = x; значение x уже наверняка будет правильным.

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

Ключевым моментом для эффективного переупорядочивания инструкция является возможность компилятора отслеживать зависимость по данным между различными инструкциями (зависимости могут быть трех основных типов: RAW, WAW, WAR) /___/. Приведенный выше пример наглядно демонстрирует необходимость использования анализа алиасов. Если компилятор считает, что p к моменту выполнения операции * p = z; может указывать на переменную x, то он не сможет выполнить переупорядочивание инструкций аналогичное приведенному выше, поскольку это приведет к нарушению логики работы программы.