Взаимное влияние оптимизаций
Ввиду большой вычислительной сложности задачи компиляции, компилятор, как правило, разбивается на ряд различных фаз. Этот очевидный сам по себе подход подразумевает, что фазы выполняются в определённом порядке. Существует нетривиальная проблема определения наиболее оптимального порядка следования фаз. Многие фазы могут влиять на потенциальную эффективность выполнения последующих фаз. Машинно-независимая оптимизация «подстановка констант», к примеру, обычно повышает эффективность «вычислению константных выражений», что может привести к появлению последующих констант для подстановки. Таким образом, ясно, что эти две оптимизации должны производиться итеративно.
Что касается back-end’а, то задача определения порядка фаз здесь усложняется, поскольку некоторые фазы сокращают применимость последующих фаз. Более того, зависимость между фазами обычно циклична. Мы проиллюстрируем эту проблему следующими примерами:
Выбор инструкций и распределение регистров: алгоритм выбора инструкций преобразует элементы внутреннего представления в машинные команды. Обычно эта фаза также определяет, какие значения будут оставаться на виртуальных регистрах. Более того, при наличии более одного регистрового файла алгоритм выбора инструкций также должен определять типы регистров для каждой операции, поскольку, как правило, имеется оптимальный вариант с точки зрения стоимости инструкции. Тем не менее, только при распределении регистров можно понять был ли тот или иной выбор удачным, если принять во внимание стоимость сохранения временного значения в памяти.
Распределение регистров и планирование команд: распределение регистров сопоставляет виртуальным регистрам физические. Обычно при этом один физический регистр используется для нескольких виртуальных, что приводит к дополнительным антизависимостям, мешающим планировщику. С другой стороны, последовательное планирование команд явно влияет на области жизни виртуальных регистров, тем самым непосредственно влияя на результаты распределения регистров.
Планирование команд и оптимизации адресного кода: оптимизации адресного кода зависят от конкретной последовательности доступов к памяти, получаемой после планировщика. Положение переменных в памяти и количество операций автоувеличения зависят от последовательности доступа, и, возможно, что альтернативная последовательность команд будет более эффективна сточки зрения стоимости адресных вычислений. Поскольку оптимизации адресного кода приводят к новым инструкциям, они могут повлиять в дальнейшем на эффективность сжатия.
Результат приведённых здесь зависимостей таков, что практически любая последовательность фаз может приводить к неэффективному коду для определённых входных программ. Проблема порядка следования фаз ещё острее для процессоров с нерегулярной архитектурой, таких как большинство ЦПОС. Для преодоления этих проблем обычно прибегают к сопряжению фаз (phase coupling), что приводит к тесному обмену информацией между сопряжёнными фазами.
Простейший способ сопряжения фаз – итеративное выполнения нескольких фаз с возможностью изменения потенциально неправильных решений, основанных на пометках сделанных последующими фазами. Другие подходы пытаются оценить влияние каждой фазы на последующие фазы на ранней стадии. Наибольшая степень сопряжения фаз достигается, когда фазы фактически соединяются в одну, хотя такие алгоритмы тяжелы для разработки и, как правило, очень трудоёмки.
Существует целый ряд подходов к композиции фаз. Например, в [22] покрытие деревьев совмещается с распределением регистров и планированием для Texas Instruments DSP. Ещё один подход, основанный на алгоритме simulated annealing, по сути похожем на генетические алгоритмы, описан в [23].
Здесь мы остановимся на общем подходе, основанном на CLP (constraint logic programming) – системе решения определённого класса задач. К этому классу задач можно свести и задачи генерации кода для нерегулярных архитектур, в частности для ЦПОС [24], т.е. для случаев, когда имеется большое количество различных ограничений, которые нельзя выразить в общем виде.
Рассмотрим пример такого описания. Пусть имеется инструкция вида:
X1:=X2+X3
где X1, X2 и X3 представляют различные наборы регистров, причём не все комбинации регистров, представляющих каждый из операндов возможны, а имеются дополнительные ограничения. К примеру, пусть
X1={a1,a2}, X2={b2, b2} и X3={c1,c2}. При этом обычно присутствуют ограничения вида: «если X2=b1 и X3=с1, то X1 может быть только a2», или же «X1=a1 только при X3=c2», и т.п. Эта ситуация может быть ещё более усложнена, если допустимые комбинации регистров зависят и от выполняемой параллельно инструкции. Искомые величины (X2) будем в дальнейшем называть переменными, а множество их возможных значений ({b1, b2}) – доменами. Решением задачи CSP называется набор значений для переменных X1..X3, удовлетворяющих всем ограничениям.
Например, в [25] система команд процессора описывается следующим списком:
(Op, R, [O1,…,On], ERI, Cons)
где Op – обозначает имеющуюся в процессоре операцию, R – множество ресурсов для хранения результата (регистров или ячеек памяти), Oi – множество ресурсов для размещения входных данных, ERI – набор дополнительных ресурсов, используемых данной машинной операцией (допустим шины или функциональные узлы), Cons – набор ограничений на значения Op,
R, Oi и ERI.
Для решения задачи CLP в [28] использовался язык ECLiPSe [26], являющийся расширением языка PROLOG. При этом поиск решения задачи сводится к поиску некоторой маркировки, т.е. выбора для каждой исходной переменной одного из значений из связанного с ней домена. Например, переменная X1 из приведённого выше примера может быть промаркирована значением a1 из её домена {a1, a2}. ECLiPSe содержит библиотеку алгоритмов для поиска маркировки для случая конечных доменов значений. Более того, в ECLiPSe входит набор обобщённых оптимизирующих процедур, получающих на вход стратегию маркировки l(V) на наборе переменных V вместе с целевой функцией cost(V), и вычисляющие оптимальную маркировку: minimize(l(V), const(V)).
Данный подход позволяет достигать впечатляющих результатов (разница по сравнению с ручным ассемблерным кодом всего порядка 20%). Из недостатков следует отметить заметные затраты ресурсов и времени (порядка минут) на компиляцию тестовых программ из набора DSPStone [27].
