Реферат: Проектирование трансляторов
горитм генерирования команд может быть согласован с алгоритмом
распределения памяти так, чтобы такая нумерация переменных всег-
да имела место. Для этого только требуется, чтобы порядок, в ко-
тором имена переменных впервые появляются в последовательности
команд, совпадал с порядком мест, отведенных в векторах для соот-
ветствующих ячеек Fi и Li. В нашем примере переменная V1 должна
быть определена до переменной V2 и т.д.
При просмотре интервалов в порядке возрастания значений Fi
первая переменная помещается в ячейку T1. Для каждого очередного
интервала (Fj,Lj) исследуются АКТИВНЫЕ интервалы, для которых па-
мять уже распределена, с тем чтобы выяснить, существует ли такой
интервал (Fi,Li), что Li<Fj. Если такой интервал существует, то
переменная Vj помещается в ту же ячейку памяти, что и переменная
Vi, а интервал (Fi,Li) отмечается как НЕАКТИВНЫЙ. Таким образом,
на каждом этапе активные интервалы определяют текущие переменные,
которые размещены в ячейках памяти, а также определяют моменты,
когда эти ячейки освобождаются. Если не существует активного ин-
тервала со значением Li<Fj, то нужно взять из стека новую ячейку
и отвести ее для Vj.
В нашем примере для V1 была бы отведена ячейка T1. Так как
L1>F2, то для V2 нужна новая ячейка, и поэтому для V2 была бы от-
ведена ячейка T2. С другой стороны, L2<F3, так что можно помес-
тить V3 в ту же ячейку памяти, что и V2 (т.е. в ячейку T2).
Интервал для V2 теперь отмечается как неактивный. Так как L1<F4,
то переменная V4 тоже помещается в ячейку T1.
3.3 Алгоритм Биледи
Многие ЭВМ имеют небольшой набор быстрых регистров, которые
сходны с ячейками основной памяти с той разницей, что выборка ин-
формации, запомненной в быстрых регистрах, требует во много раз
меньше времени, чем выборка из основной памяти. На самом деле,
быстрые регистры могут быть индекс-регистрами или добавочными
сумматорами. т.е. их сожержимое может использоваться специальным
образом в арифметических или логических операциях, но здесь мы не
учитываем эти свойства.
Эти быстрые регистры могут быть использованы для хранения
копий переменных, размещенных в основной памяти; что же касается
временной переменной, то она может находиться в быстром регистре
все время своего существования, не требуя места в основной памя-
ти. Если число доступных быстрых регистров превышает число нуж-
ных переменных, то проблемы не возникает и быстрые регистры мо-
гут быть распределены по алгоритму для временных переменных.
Однако если число доступных быстрых регистров не является
достаточным, то возникает ситуация, когда необходимо решать, ка-
кие из переменных должны оставаться в быстрых регистрах. Решение
будет зависеть от частоты использования различных переменных, и
алгоритм должен стремиться максимально использовать быстрые ре-
гистры.
Алгоритм Биледи приводит к оптимальному результату при неко-
торых ограничениях и часто дает хорошие результаты в более общих
случаях. Предполагается, что быстрые регистры должны применяться
для хранения копий переменных из ОП и что использовать эти пере-
менные можно только после занесения их в быстрые регистры.
В дальнейшем будем предполагать, что рассматриваемые пере-
менные не будут изменяться; поэтому, если нужно заменить ка-
кую-то переменную в быстром регистре, то нет необходимости запо-
минать текущее содержимое быстрого регистра, так как копия этого
содержимого уже есть в основной памяти.
Возникающая задача похожа на задачу замещения страниц в сис-
теме с двумя уровнями памяти.
Биледи (1966) сформулировал оптимальный алгоритм для случая,
когда известна полная картина будущих обращений, что использова-
лось в системе с двумя уровнями памяти для получения оценки эф-
фективности многих применяемых эвристических алгоритмов.
Задача распределения быстрых регистров отличается от задачи
с двумя уровнями памяти тем, что для нее нет необходимости выпол-
нять распределение до получения полной последовательности команд.
Поэтому алгоритм Биледи может быть применен непосредственно для
получения оптимальных результатов. Этот алгоритм прменялся в ком-
пиляторах в течение нескольких лет, и только с недавнего времени,
в связи с его использованием в системе с двумя уровнями памяти, с
ним стало связываться имя Биледи.
Интервалы, в которых используются основные переменные Vi,
могут быть изображены диаграммой, как показано на рис. 20.8.
V5 ├────────────────┤
V4 ├───────────────────┤
V3 ├──────────────┼──────────────────┤
V2 ├─────┼─────┼────────┤
V1 ├───────────────────────────┤
1 2 3 4 5 6 7 8 9 10 11 12 13
Рис. 20.8 Диаграмма использования переменных Vi в последова-
тельности команд
Каждая горизонтальная переменная изображает интервал для не-
которой переменной, причем точки указывают номера мест в последо-
вательности команд, где используется эта переменная. Будем пред-
полагать, что в каждой команде используется только одна перемен-
ная, так что на одной вертикали не может появится двух и более
точек. Число горизонтальных линий, пересекающихся с какой-либо
вертикалью, указывает, сколько ячеек памяти содержат в соответ-
ствующий момент нужные значения переменных. Если число пересече-
ний какой-то вертикали с различными горизонтальными линиями пре-
вышает число доступных быстрых регистров, то одна или более чем
одна из переменных не может быть помещена в быстрых регистрах.
Мы будем также полагать, что каждая выборка какой-либо пере-
менной из быстрого регистра требует ничтожной затраты времени.
Если нужной переменной нет в быстром регистре, то необходимо за-
менить содержимое одного из быстрых регистров на значение этой
переменной. Определим функцию S(i,t) следующим образом:
S(i,t)=0, если переменная Vi не находится в быстром регис-
тре в момент t;
S(i,t)=1, если Vi находится в быстром регистре в момент t.
Тогда сумма по всем номерам "t" не должна превышать N, где N
- число доступных быстрых регистров.
Если m(t) - номер переменной, используемой в команде "t", то
функцию U, характеризующую эффективность использования быстрых
регистров, можно определить следующим образом:
U=сумма S(m(t),t)).
t
Максимальное значение функции U (при заданных выше ограниче-
ниях) достигается, когда наибольшее число использований перемен-
ных будет происходить путем непосредственного обращения к быс-
трым регистрам. Единственное доп. ограничение состоит в том, что
S(m(t-1),t)=1
для всех значений t. Это означает, что каждая переменная при
использовании заносится в быстрый регистр.
Алгоритм Биледи состоит в следующем.
Последовательность команд исследуется, начиная с первой ко-
манды, определенной значением t=1. Для каждого значения t рас-
сматривается переменная Vi, где i=m(t), и выполняются действия по
одному из следующих вариантов:
(1) Для переменной Vi отведен быстрый регистр; тогда ис-
пользуется этот регистр.
(2) Для переменной Vi не отведено быстрого регистра, но
имеется неиспользованный быстрый регистр; в таком случае, этот
регистр отводится для Vi.
(3) Для переменной Vi не отведено быстрого регистра, и рас-
пределены все быстрые регистры. Тогда рассматриваются переменные,
для которых в текущий момент имеются копии в быстрых регистрах, и
если значение какой-то одной из них больше не потребуется, то
соответствующий быстрый регистр теперь отводится для Vi. Если со-
держимое всех быстрых регистров все еще необходимо, то для Vi от-
водится быстрый регистр, соответствующий той переменной, следую-
щее использование которой наиболее удалено от данной команды.
Пусть имеются 3 быстрых регистра R1, R2 и R3. Начиная с мо-
мента t=1 первые три команды отведут регистры R1, R2 и R3 для пе-
ременных V1, V2 и V3. В момент t=5 содержимое всех трех быстрых
регистров еще необходимо, а требуется регистр для V4. Переменная
V1 не будет использоваться до момента t=10, тогда как V2 ис-
пользуется при t=6 и V3 - при t=8. Поэтому регистр R1 теперь ис-
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
