46023 (665330), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

│ │ │

│ │ │

│ │ /

├────────┤ \

│ y │ Динами- │

├────────┤ │

│ x │ ческая │

/───> ├────────┤ │

│ │ / │Элемен- │ часть > Рамка 1

│ │ / │ты чисел│ │

├─────┤ / ┌─> ├────────┤ - - - - │

│ │/ │ │ p │ Стати- │

│ │ │ ├────────┤ │

│ │ │ │ Стат. │ │

│ │ └───│ часть │ ческая │

│ │ │ чисел │ │

├─────┤ ├────────┤ │

│ │──\ │ n │ часть │

└─────┘ \────> └────────┘ /

Дисплей Стек

Рис. 20.5 Схема связи Дисплея и стека во время выполнения с

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

частей

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

Динамическая рабочая память должна распределяться во время

прогона, статическая же может распределяться во время компиляции.

Объем статической рабочей памяти, который должен выделяться каж-

дой рамке, определяться не рабочей памятью, требуемой в конце

каждого блока (обычно она является нулем), а МАКСИМАЛЬНОЙ рабо-

чей памятью, требуемой в любой точке внутри блока. Для статичес-

кой рабочей памяти эту величину можно установить в процессе ком-

пиляции, если в фазе распределения памяти мы ассоциируем с рабо-

чей стековой областью текущей рамки два указателя, причем один из

них указывает на текущую границу статической рабочей памяти, а

другой - на максимальный размер, до которого она выросла при ра-

боте с текущим блоком. Именно значение этого второго указателя

при выходе из блока и дает объем статического рабочего стека,

включаемого в соответствующую рамку.

2. ПРЕДСТАВЛЕНИЕ МАССИВОВ

2.1 Прямоугольные массивы

Простейшие массивы (одномерные) естественно представляются

векторами, т.к. они хорошо согласуются в том смысле, что для по-

лучения относительного адреса элемента массива в векторе надо вы-

честь нижнюю границу по измерению из индекса элемента.

Из многомерных массивов рассмотрим сначала прямоугольные. Их

также возможно представлять векторами. Для реализации выборки или

засылки в массив надо получить относительный адрес нужного эле-

мента в векторе по значениям индексов этого элемента.

Предполагая линейное расположение всех точек n-мерного прос-

транства (n - размерность), соответствующего массиву, мы можем

считать первые измерения старшими и тогда рядом располагаются

элементы, соседние по последнему измерению - так называемый

ПРЯМОЙ порядок, либо наоборот - ОБРАТНЫЙ порядок. Например, в

языке Алгамс поддерживается прямой порядок, в Фортране - обрат-

ный, а в АЛГОЛе-60 представление многомерных массивов никак не

фиксируется.

Когда в программе выбирается конкретный элемент массива, его

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

прогона. Рассмотрим массив:

[1:10,-5:5] int Table

Будем считать, что элементы записаны в лексикографическом

порядке индексов, т.е. элементы хранятся в следующем порядке:

Table[1,-5], Table[1,-4] ......... Table[1,5],

Table[2,-5], Table[2,-4] ......... Table[2,5],

.

.

.

Table[10,-5], ...................... Table[10,5]

Адрес конкретного элемента вычисляется как смещение по отно-

шению к базовому адресу (адресу первого элемента) массива:

ADDR(Table[I,J])=ADDR(Table[l1,l2])+(u2-l2+1)*(I-l1)+(J-l2)

Здесь l1 и u1 - нижняя и верхняя границы первой размерности

и т.д. и считается, что каждый элемент массива занимает единицу

объема памяти.

Для трехмерного массива соответствующая формула имеет вид:

ADDR(Table[I,J,K])=ADDR(Table[l1,l2,l3])+

(u2-l2+1)*(u3-l3+1)(I-l1)+

(u3-l3+1)*(J-l2)+K-l3

Выражение (ui-li+1) задает число различных значений, кото-

рые может принимать i-индекс.

Значение произведения (u2-l2+1)*(u3-l3+1) представляет со-

бой число различных пар значений, которые могут принимать второй

и третий индексы, а также расстояние между элементами массива,

отличающимися только на одну единицу в первом индексе.

Расстояние между элементами, отличающимися на 1 в i-индексе,

известно как i-й шаг. Так, в приведенном выше примере первый шаг

s1 состовляет (u2-l2+1)*(u3-l3+1). Второй шаг s2 равен (u3-l3+1).

Третий шаг s3 составляет 1.

Ясно, что вычисление адресов элементов массива в процессе

прогона может занимать много времени. Поэтому рекомендуется при

программировании по возможности избегать выборки из массивов,

особенно из многомерных. Тем не менее, шаги могут вычисляться

только один раз и храниться в статической части массива наряду с

границами. Такая статическая информация часто называется описате-

лем массива. В этой же части массива наряду с нижней и верхней

границами и шагом для каждой размерности может храниться указа-

тель на элементы массива. Нижняя и верхняя границы требуются для

проверки правильности нахождения индексов в пределах границ, а

шаги и нижние границы - при обращении к конкретным элементам мас-

сива.

2.2 Обращение к элементам массива с помощью векторов Айлифа

Айлиф разработал свой способ обращения к элементам массивов.

Этот способ требует для хранения массива больше памяти, но зато

обращение к элементу выполняется быстрее. Вместе с каждым масси-

вом хранится набор указателей. Так, например, массив, определен-

ный как

B[4:6,-2:1,0:1]

хранился бы в виде структуры, представленной ниже на рис.

20.6.

┌──────┐ ─ ─ ─ ─ i

С │ ──┼───────────────────────────> │ │ (0)

└──────┘ D ─ ─ ─ ─

│ │ (1)

─ ─ ─ ─

│ │ (2)

─ ─ ─ ─

│ │ (3)

┌───────┐

┌─────────────────────────────┼── │ 4

│ ├───────┤

│ ┌────────┼── │ 5

│ │ ├───────┤

│ │ │ │ 6

│ │ └────┼──┘

│ │ │

│ │ │ j

│ │ │

│ │ │

│ │ └──────┐

E │ F │ G │

┌─────┐ │ ┌─────┐ │ ┌─────┐ │

┌─────────┼─ │ │ ┌─────────┼─ │ │ ┌─────────┼─ │ │-2

│ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │

│ ┌─────┼─ │ │ │ ┌─────┼─ │ │ │ ┌─────┼─ │ │-1

│ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤ │

│ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ 0

│ │ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ 1

│ │ │ └───┼─┘ │ │ │ └───┼─┘ │ │ │ └───┼─┘

│ │ │ │ │ │ │ │ │ │ │ │

H┌─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬────┬───┐

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

k└─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴────┴───┘

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Рис. 20.6 Схема обращения к элементам массива с помощью век-

торов Айлифа

Пусть запись вида (B+5) означает содержимое по адресу B+5.

Тогда к элементу B[i,j,k] можно обратиться следующим образом:

(((C)+i)+j)+k

При этом выбирается содержимое ячейки C и к нему прибавляет-

ся значение индекса i, затем по полученному в результате этого

адресу выбирается содержимое, которое дает указатель на следую-

щий более низкий уровень, и т.д.

Важно отметить, что при данном способе обращения к элементу

массива не требуется выполнения операций умножения. Вместе с тем

в рассмотренном примере, кроме вектора для хранения массива, тре-

буется еще один вектор длины 3 и три вектора длины 4, и таким об-

разом, вместо 24 элементов требуется 39. Этот метод оказывается

наиболее экономичным, когда диапазоны изменения индексов увеличи-

ваются от первого к последнему. Наименее всего этот метод эффек-

тивен, когда первый индекс имеет наибольший диапазон изменения.

В приведенном примере не производилось проверки корректнос-

ти индекса. Это может быть достигнуто путем хранения вместе с

каждым элементом вектора Айлифа граничной пары для соответствую-

щего индекса. Правда, в случае прямоугольного массива это могло

бы оказаться неэкономичным. У каждого из элементов векторов E,F и

G в рассматриваемом примере были бы одинаковые граничные пары.

Однако следует обратить внимание на то, что с каждым из этих эле-

ментов могли бы быть связаны и различные граничные пары, что да-

ло бы возможность, используя векторы Айлифа, обращаться к масси-

вам со значительно более сложной структурой.

Так, например, на рис. 20.7 показан набор векторов Айлифа,

позволяющих обращаться к трехмерному массиву, элементы которого

хранятся в следующем порядке:

B[4,-1,-1] B[5,1,2] B[6,0,0]

B[4,-1, 0] B[5,2,2] B[6,0,1]

B[4,-1, 1] B[5,2,3] B[6,0,2]

B[4,-1, 2] B[5,3,2] B[6,0,3]

B[4, 0, 0] B[5,3,3] B[6,0,4]

B[4, 0, 1] B[5,3,4] B[6,0,5]

B[4, 0, 2] B[5,3,5]

B[4, 0, 3]

B[4, 0, 4]

B[4, 0, 5]

B[4, 0, 6]

┌─────┬─┬─┐

│ │4│6│

└──┼──┴─┴─┘ ─ ─ ─ ─ ─

└────────────────────────────> │ │

─ ─ ─ ─ ─

│ │

─ ─ ─ ─ ─

│ │

─ ─ ─ ─ ─

│ │

┌────┬──┬──┐

┌──────────────────────────────┼── │-1│ 0│

│ ├────┼──┼──┤

│ ┌────────┼── │ 1│ 3│

│ │ ├────┼──┼──┤

│ │ │ │ 0│ 0│

│ │ └─┼──┴──┴──┘

│ │ │

│ │ │

│ ─ ─ ─ ─ ─ ─ │ ┌─────┘

│ │ │<──┘ │

│ ┌─────┬──┬──┐ │

│ ┌───┼─ │ 2│ 2│ │

┌─────┬──┬──┐ │ │ ├─────┼──┼──┤ ┌─────┬───┬──┐

┌─┼─ │-1│ 2│ │ │┌──┼─ │ 2│ 3│ ┌┼─ │ 0│ 5│

│ ├─────┼──┼──┤ │ ││ ├─────┼──┼──┤ │└─────┴───┴──┘

│ │ │ 0│ 6│<┘ ││ │ │ 2│ 5│ │

│ └───┼─┴──┴──┘ ││ └─┼───┴──┴──┘ │

│ │ ┌─┘│ │ │

│ │ │ ┌┘ ┌─┘ ┌────┘

│ │ │ │ │ │

│ │ │ │ │ │

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

Рис. 20.7 Пример векторов Айлифа для трехмерного массива

сложной структуры

2.3 Замечания по поводу "разреженных" массивов

В некоторых случаях, при хранении массивов по схеме векто-

ров Айлифа или подобной ей схеме с использованием дескрипторов

можно избежать хранения пустых, тривиальных или незаданных значе-

ний элементов. В этих случаях можно рассматривать пару "информа-

ционный элемент" - "значения индексов" как элемент информационно-

го множества, а задание значения (нетривиального) элементу масси-

ва - как пополнение множества, а задание неопределенного (или

тривиального) значения - как удаление элемента из множества.

Представление таких "неполных" (или "разреженных") массивов

реализуется как представление множеств.

3. ОРГАНИЗАЦИЯ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ

3.1 Проблемы распределения памяти

Распределение памяти для определенных программистом перемен-

ных в языках высокого уровня обычно бывает простым. Часто ло-

кальные переменные размещаются в памяти непосредственно после

соответствующей программной единицы. Однако для современных ЭВМ и

ОС, требующих разделения неизменяемой и изменяемой частей прог-

раммы, возникает необходимость помещать локальные переменные в

отдельные области памяти.

Основные проблемы возникают тогда, когда нужно распределить

память для временных переменных, т.е. промежуточных результатов,

потребность в которых появляется при компиляции. Эти переменные

определяются не в программе на входном языке, а компилятором. Ре-

шение о том, сколько для них требуется памяти и как ее распреде-

лить, полностью зависит от компилятора. Поэтому нужен алгоритм

как можно более эффективного размещения в памяти этих переменных.

Здесь под эффективностью обычно понимается стремление минимизиро-

вать объем используемой памяти.

Распределение памяти становится нетривиальной задачей в том

случае, когда у ЭВМ существует более чем один уровень памяти.

У многих машин имеются ограниченные наборы быстрых регис-

тров, которые отличаются от основной памяти либо более быстрым

доступом, либо иными, более удобными свойствами. Эффективное ис-

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

алгоритмы оптимального размещения переменных в быстрых регистрах.

3.2 Распределение памяти для временных переменных

Алгоритмы генерации команд не касаются распределения памяти

для временных переменных. Можно считать, что эти алгоритмы берут

новое имя переменной из бесконечного множества неиспользованных

имен каждый раз, когда, согласно алгоритму, требуется новая вре-

менная переменная. Алгоритм распределения памяти должен размес-

тить эти переменные в памяти так, чтобы потребовалось мини-

мальное число ячеек памяти.

ИНТЕРВАЛОМ для переменной называется отрезок времени между

начальным определением этой переменной и ее последним использова-

нием. Очевидно, переменные, интервалы для которых совсем не свя-

заны, могут быть совмещены в памяти.

Рассмотрим набор переменных V1, V2, V3, ..., Vn. Для каждой

переменной Vi определена команда ST Vi, которая присваивает этой

переменной начальное значение и означает начало интервала для Vi.

Определяется также команда U Vi, которая означает очередное

использование этой переменной. Последняя команда этого вида, ис-

пользующая Vi, означает конец интервала для Vi. Команда U будет

применяться для обозначения таких команд, как ADD, SUB и т.д.

Для вычисления значения выражения (a+b*c)/(f*g-(d+e)/(h+k))

генератор команд по дереву разбора сформировал следующую последо-

вательность машинных команд:

L h

ADD k

ST V1

L d

ADD e

DIV V1

ST V2

L f

MPY g

SUB V2

ST V3

L b

MPY c

ADD a

DIV V3

Имена V1, V2 и V3 были взяты из множества неиспользованных

имен. Алгоритм распределения памяти, который мы хотим определить,

должен показать, что фактически эти три переменные могут быть по-

мещены в одну и ту же ячейку памяти T1.

Поскольку этот алгоритм распределения памяти касается опре-

деленных частей последовательности, можно написать

ST V1

U V1

ST V2

U V2

ST V3

U V3

Так как последнее использование каждой переменной встречает-

ся до определения следующей переменной, то легко видеть, что дос-

таточно одной ячейки памяти.

Предположим, что имеется стек неиспользованных ячеек памяти

[T1, T2, T3, ...]. Предположим далее, что каждый раз, когда нуж-

на ячейка, она берется из вершины стека и что сразу после послед-

него использования какой-либо переменной отведенная для нее ячей-

ка возвращается в стек. Тогда алгоритм распределения памяти для

временных переменных проще всего описать следующим образом.

Последовательность команд просматривается НАЧИНАЯ С КОНЦА, В

ОБРАТНОМ ПОРЯДКЕ. Если встречается команда вида U Vi и при этом

для переменной Vi еще не отведена ячейка памяти, то из вершины

стека берется свободная ячейка, ставится в соответствие перемен-

ной Vi и производится замена символа Vi в данной команде на ад-

рес соответствующей ячейки памяти. Такая же замена производится и

в том случае, когда ячейка памяти для переменной Vi уже отведена

ранее. Если встречается команда ST Vi и для переменной Vi еще не

отведена ячейка памяти, то это означает либо ошибку, либо избы-

точность данной команды, так как подразумевается, что переменная

вычисляется без дальнейшего использования. Если для переменной Vi

ранее отведена ячейка памяти, то производится замена символа Vi в

данной команде на адрес соответствующей ячейки памяти и, пос-

кольку это первое обращение к переменной Vi, соответствующая

ячейка в данный момент может быть возвращена в стек свободной па-

мяти, так как для Vi она больше не понадобится.

Данциг и Рейнольдс показали, что этот алгоритм оптимален,

хотя он и не единственный возможный оптимальный алгоритм.

Например, рассмотрим последовательность

(1) ST V1

(2) ST V2

(3) U V2

(4) U V1

(5) ST V3

(6) U V1

(7) U V3

(8) ST V4

(9) U V3

(10) U V4

и предположим, что стек свободной памяти есть [T1, T2, T3].

Начинаем просмотр последовательности с конца; команда (10) поме-

щает переменную V4 в ячейку T1, команда (9) отводит для перемен-

ной V3 ячейку T2, после этого стек остается в виде [T3]. Команда

(8) освобождает ячейку T1, после этого стек принимает вид [T1,

T3]. Команда (6) помещает V1 в ячейку T1. Подобным же образом ко-

манда (5) освобождает ячейку T2; затем эта ячейка отводится ко-

мандой (3) переменной V2. В результате получается последова-

тельность

(1) ST T1

(2) ST T2

(3) U T2

(4) U T1

(5) ST T2

(6) U T1

(7) U T2

(8) ST T1

(9) U T2

(10) U T1

Этот алгоритм находит интервал для каждой переменной, ис-

пользуя первое появление этой переменной при обратном посмотре

для определения конца интервала, а соответствующую команду ST для

определения начала интервала. Больше от алгоритма ничего не тре-

буется.

Предложенный алгоритм может быть изменен так, чтобы выраба-

тывать ту же информацию путем прямого просмотра последовательнос-

ти команд. При прямом просмотре каждая команда ST определяет

по-прежнему начало интервала. Если для каждой переменной подсчи-

тано число ее использований, то можно найти и последнее использо-

вание любой переменной, так что конец соответствующего интервала

становится известным.

Другой вариант состоит в том, чтобы находить конец интерва-

ла способом, описанным для обратного просмотра, но фактически

осуществлять прямой просмотр. Это достигается образованием цепоч-

ки всех обращений к данной переменной в порядке их появления при

просмотре. С каждой переменной Vi связываются три ячейки, содер-

жащие Fi, Li и Ri. Значение Fi является номером команды ST для

переменной Vi в последовательности команд. Значение Li является

номером команды последнего обращения к переменной Vi. Поэтому ин-

тервал для Vi имеет вид (Fi,Li). Значение Ri является адресом

ячейки, отведенной для переменной Vi, и обычно первоначально ус-

танавливается равным нулю.

Если при просмотре последовательности команд встречается ко-

манда ST Vi, то это вызывает установку значений Fi и Li, равных

номеру этой команды в последовательности. Если встречается коман-

да U Vi, то Vi заменяется в ней на Li, а Li становится равным но-

меру этой команды. Для предыдущего примера переменные Fi и Li

принимают конечные значения:

F1=1 L1=6

F2=2 L2=3

F3=5 L3=9

F4=8 L4=10

а команды принимают вид

(1) ST 0

(2) ST 0

(3) U 2

(4) U 1

(5) ST 0

(6) U 4

(7) U 5

(8) ST 0

(9) U 7

(10) U 8

После завершения просмотра последовательности значение Li

указывает конец цепочки всех обращений к переменной Vi. Каждая

команда содержит в адресной части номер предыдущей команды из той

же цепочки. Если для переменной Vi отведена ячейка в памяти, то

не представляет труда подняться по соответствующей цепочке, заме-

няя адресные части команд на адрес ячейки, отведенной для Vi.

Итак, интервал для каждой переменной определяется парой чисел

(Fi,Li). Теперь можно просмотреть эти пары, чтобы распределить

память для всех переменных. Если Fi=Li, то соответствующая коман-

да ST является избыточной, как отмечалось раньше.

Интервалы просматриваются в порядке возрастания Fi. В нашем

примере переменные уже перенумерованы в этом порядке. Обычно ал-

горитм генерирования команд может быть согласован с алгоритмом

распределения памяти так, чтобы такая нумерация переменных всег-

да имела место. Для этого только требуется, чтобы порядок, в ко-

тором имена переменных впервые появляются в последовательности

команд, совпадал с порядком мест, отведенных в векторах для соот-

ветствующих ячеек Fi и Li. В нашем примере переменная V1 должна

быть определена до переменной V2 и т.д.

При просмотре интервалов в порядке возрастания значений Fi

первая переменная помещается в ячейку T1. Для каждого очередного

интервала (Fj,Lj) исследуются АКТИВНЫЕ интервалы, для которых па-

мять уже распределена, с тем чтобы выяснить, существует ли такой

интервал (Fi,Li), что Li

переменная Vj помещается в ту же ячейку памяти, что и переменная

Vi, а интервал (Fi,Li) отмечается как НЕАКТИВНЫЙ. Таким образом,

на каждом этапе активные интервалы определяют текущие переменные,

которые размещены в ячейках памяти, а также определяют моменты,

когда эти ячейки освобождаются. Если не существует активного ин-

тервала со значением Li

и отвести ее для Vj.

В нашем примере для V1 была бы отведена ячейка T1. Так как

L1>F2, то для V2 нужна новая ячейка, и поэтому для V2 была бы от-

ведена ячейка T2. С другой стороны, L2

тить V3 в ту же ячейку памяти, что и V2 (т.е. в ячейку T2).

Интервал для V2 теперь отмечается как неактивный. Так как L1

то переменная 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 теперь ис-

пользуется для V4. При t=7 вновь возникает такая же проблема.

Значение V4 не требуется до момента t=11, тогда как V3 ис-

пользуется при t=8 и V2 - при t=9. Поэтому регистр R1 отводится

для V5. При t=10 переменная V1 используется снова. Теперь приме-

няется сформулированное выше условие (2), так как значение V2

больше не потребуется. Поэтому регистр R2 отводится для V1. Ана-

логично при t=11 регистр К2 отводится для V4, так как больше не

потребуется значение V1.

Распределение регистров R1 и R3 для V5 и V3 сохраняется до

конца последовательности команд. Описанное распределение быстрых

регистров показано диаграммой на рис. 20.9.

V5 ├─────────────────┤

V4 ├────── ─ ─ ─ ─ ─ ──┤

V3 ├───────────────┼──────────────────┤

V2 ├─────┼─────┼────────┤

V1 ├──────────── ─ ─ ─ ─ ─ ─ ──┤

1 2 3 4 5 6 7 8 9 10 11 12 13

Рис. 20.9 Диаграмма использования переменных Vi в последова-

тельности команд, поясняющая работу алгоритма Биледи

4. ТАБЛИЦА СИМВОЛОВ

4.1 Описатели

Для каждого вхождения идентификатора в исх. программе осу-

ществляется поиск соотв. элемента в таблице символов (ТС), инфор-

мация, полученная при данном вхождении, сопоставляется с ранее

полученной информацией, выполняется необходимый контроль и регис-

трация новой информации. Таким образом, ТС является очень важной

частью компилятора и, в некотором смысле, узловой точкой всей

трансляции. Ее структура должна допускать эффективный поиск и

внесение информации. В то же время, каждый элемент должен зани-

мать как можно меньше места, для того, чтобы хватало места на

большие программы с большим числом идентификаторов. Вообще гово-

ря, желательно, чтобы возможно меньшее число программ транслято-

ра непосредственно работало с ТС. Это позволит достаточно легко

вносить необходимые изменения. Особенно важно тщательно согласо-

вать формат описателя до того, как начнется программирование

транслятора.

ОПИСАТЕЛЕМ называется часть элемента ТС, в которой описы-

вается идентификатор. Существует другой термин для обозначения

этого же понятия, введенный Фельдманом - "семантическое слово" (У

Ахо и Ульмана это назывется "дескриптором").

Количество информации, которое нужно хранить в описателе,

зависит от того, чем является фактически идентификатор - простой

переменной, массивом, функцией и т.д. Поэтому в некоторых реали-

зацих описатели имеют переменную длину. Это допустимо не при лю-

бой организации ТС. Иногда в целях экономии памяти выбирают эле-

мент ТС малого размера, а для идентификаторов, требующих больше

места, отводят по несколько соседних элементов.

Другая возможность открывается, емли в нужных случаях отво-

дить часть описателя под указатель, ссылающийся на дополни-

тельную таблицу. Это несколько осложняет программирование, пос-

кольку тип описателя может менять свой смысл в зависимости от ти-

па элемента.

4.2 Возможные параметры описания переменных и процедур

в таблице символов

Для переменных и процедур в описателе может потребоваться

следующая информация:

ПЕРЕМЕННАЯ:

Тип (вещ., целый, строка, комплексный, метка и т.д.);

Точность, масштаб, длина;

Вид (простая переменная, массив, структура и т.д.);

Адрес во время выполнения программы;

Если массив, то - число измерений. Если есть граничные пары

(ограниченные множества в Паскале), то их значения;

Если структура или компонента структуры, то связь данной

компоненты с другими компонентами;

Формальный параметр или нет; если да, то тип соответствия

параметров;

Описана ли переменная как extern или как идентификатор объе-

динения (union) ?

Обрабатывалось ли уже ее описание ?

Существует ли инструкция, присваивающая ей значение ?

ПРОЦЕДУРА:

Является ли она внешней по отношению к программе ?

Является ли она функцией ?

Каков ее тип ?

Обрабатывалось ли уже ее описание ?

Является ли она рекурсивной ?

Каковы ее формальные параметры ? Их описатели должны быть

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

соответствие фактическим параметрам.

4.3 Таблица символов компилятора /360 WATFOR

/360 WATFOR - однопроходной компилятор с языка ФОРТРАН IV

для машин IBM/360.

ТС состоит из пяти разных списков:

- списка меток;

- списка арифметических констант;

- списка имен общих блоков, подпрограмм, переменных;

- списка блоков;

- списка подпрограмм.

(Таким образом, некоторые элементы оказываются в двух списках.)

Элементы всех списков помещаются в одной и той же таблице;

первые 2 байта каждого элемента используются для ссылки на сле-

дующий элемент в этом же списке. Следовательно, поиск отдельного

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

Элементы различных типов имеют разлмчную длину в пределах от

8 до 20 байтов.

Например, элемент для переменной имеют длину 16 байтов и со-

держит следующую информацию (первые 2 байта опущены):

3-4 5-10 11-12 13-14 15-16

┌────┬───────┬───────────┬──────┬───────────┐

│ B2 │идент-р│размерность│COMMON│EQUIVALENCE│

└────┴───────┴───────────┴──────┴───────────┘

В полях "COMMON" и "EQUIVALENCE" помещаются указатели на

элементы других переменных, связанных с данной при помощи ин-

струкций COMMON и EQUIVALENCE.

В поле "размерность" содержится 0, если переменная не яв-

ляется массивом; в противном случае оно указывает на отдельный

элемент, содержащий всю информацию о размерности: величины

d1,...,dn и длину d1*...*dn.

Два байта, обозначенные B2, содержат всю остальную информа-

цию (см. рис. 20.10). Первоначально все поля содержат нули, и в

них заносится информация по мере обработки программы.

Единица в каждом однобитовом поле на рис. 20.10 говорит о

наличии соответствующего факта.

│ 0-1 │ 2-4 │ 5-6 │ 7 │ 8 │ 9 │

├───────────┼────────┼──────────┼────────┼───────┼─────────┤

│10 - прос- │число │ тип │ длина │ тип │исполь- │

│ тая │индексов│00 - лог. │задается│сформи-│зование │

│ перем.│в случае│01 - цел. │програм-│рован │сформиро-│

│11 - массив│массива │10 - вещ. │мистом │ │вано │

│ │ │11 - ком- │ │ │ │

│ │ │ плекс. │ │ │ │

│ 10 │ 11 │ 12 │ 13 │ 14 │ 15 │

├─────────┼────────┼─────────┼────────┼────────┼───────────┤

│формаль- │текущий │присваи- │имеет │встреча-│встреча- │

│ный пара-│параметр│вается │нач. │ется в │ется в │

│метр │цикла │значение │значение│COMMON │EQUIVALENCE│

│програм- │ │по ASSIGN│ │ │ │

│мы │ │ │ │ │ │

Рис. 20.10 Схема подполей поля B2

4.4 Представление структур в таблице символов

Мы можем представлять структуру, отводя по одному элементу

для каждой компоненты. Кроме обычных полей, каждый элемент имеет

три дополнительных поля: FATHER, SON и BROTHER.

Поле FATHER указывает на ОТЦА, SON - на первого СЫНА компо-

ненты, а поле BROTHER - на ее следующего БРАТА в последова-

тельности братьев группы.

Если данный элемент не имеет отца, сына или следующего бра-

та, то соответствующее поле будет содержать 0.

Ниже на рис. 20.11 приведены иерархические схемы строения

двух структур с указанием перед идентификатором каждой из

(под)компонент уровня ее вложенности.

1 A 1 L

2 B 2 M

3 C 4 C

3 D 4 D

2 E 2 B

2 F 5 C

5 D

Рис. 20.11 Схема построения двух структур

Элементы ТС для этих двух структур приведены ниже на Табли-

це 20.1. Этой информации может хватить с избытком (а может ока-

заться и недостаточно) для эффективной работы со структурами.

Поскольку могут существовать элементы, имена которых совпа-

дают, вводится еще один указатель SAME, связывающий такие элемен-

ты между собой. Первый из этих элементов содержит в этом поле 0.

Таблица 20.1 Схема заполнения элементов ТС для двух струк-

тур на рис. 20.11

┌────┬───┬─────┬──────┬────┬───────┐

│ │ID │ SAME│FATHER│ SON│BROTHER│

├────┼───┼─────┼──────┼────┼───────┤

│ A1 │ A │ 0 │ 0 │ B1 │ 0 │

│ B1 │ B │ 0 │ A1 │ C1 │ E1 │

│ C1 │ C │ 0 │ B1 │ 0 │ D1 │

│ D1 │ D │ 0 │ B1 │ 0 │ 0 │

│ E1 │ E │ 0 │ A1 │ 0 │ F1 │

│ F1 │ F │ 0 │ A1 │ 0 │ 0 │

│ L1 │ L │ 0 │ 0 │ M1 │ 0 │

│ M1 │ M │ 0 │ L1 │ C2 │ B2 │

│ C2 │ C │ C1 │ M1 │ 0 │ D2 │

│ D2 │ D │ D1 │ M1 │ 0 │ 0 │

│ B2 │ B │ B1 │ L1 │ C3 │ 0 │

│ C3 │ C │ C2 │ B2 │ 0 │ D3 │

│ D3 │ D │ D2 │ B2 │ 0 │ 0 │

└────┴───┴─────┴──────┴────┴───────┘

Характеристики

Список файлов реферата