Средства разработки приложений


Обзор методов оптимизации кода - часть 21


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

Согласно результатам этой работы, наилучшие результаты в среднем дают эвристики 1) и 3); авторы рекомендуют использовать эвристику частоты исполнения, а если данные профилирования отсутствуют, то сортировать команды по глубине в графе зависимостей.

3. На последней фазе рассматриваются (в порядке своих приоритетов) готовые к исполнению команды и выдаются в выходной поток. Если целевой процессор является VLIW-процессором, то выходной поток состоит из длинных командных слов, каждое из которых может содержать несколько команд входного потока. Различаются следующие способы формирования выходного потока [32]:

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

Иногда применяют дополнительную эвристику, выбирая из множества готовых к исполнению те команды, которые максимально расширят это множество на следующем шаге (см. [9]).

Интересный альтернативный алгоритм планирования, который предложен в работе [11], используется в системе построения компиляторов [5].


- Начало -  - Назад -  - Вперед -