А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 108

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

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

Таким образом, хотя объем памяти, необходимой для временных переменных в конечном счете оказывается известен компилятору, он может не быть известен в момент генерации промежуточного кода. 537 7.2. Выделение памяти в стеке 4. Следует ответственно подходить к вопросу помещения указателя на вершину стека. Распространенный подход состоит в том, чтобы он указывал на конец полей фиксированного размера в записи активации. Тогда обращение к данным фиксированной длины может осуществляться с использованием фиксированных смешений относительно указателя на вершину стека, известных генератору промежуточного кода.

Следствием такого метода является размещение полей переменной длины записи активации "выше" вершины стека. Их смещения вычисляются во время выполнения программы, ио обращение к ним выполняется также посредством указателя на вершину стека — просто значения смещений оказываются положительными. Запись активации вызывающей процедуры Ответственность вызывающей процедуры Записьактивации вызываемой процедуры Ответственность вызываемой процедуры тор и Рис. 7.7.

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

Последовательность вызова и ее разделение между вызывающей и вызываемой процедурами имеет следующий вид. 538 Глава 7. Среды времени выполнения 1. Вызывающая процедура вычисляет фактические параметры. 2. Вызывающая процедура сохраняет адрес возврата и старое значение гор зр в записи активации вызываемой процедуры. Затем вызывающая процедура увеличивает ~ор зр до позиции, показанной на рис.

7.7, т.е. (ор зр перемещается за локальные данные и временные переменные вызывающей процедуры и за поля параметров и состояния машины вызываемой процедуры. 3. Вызываемая процедура сохраняет значения регистров и другую информацию о состоянии машины. 4. Вызываемая процедура инициализирует свои локальные данные и начинает выполнение. Соответствующая последовательность возврата выглядит следующим образом. 1.

Вызываемая процедура помещает возвращаемое значение после параметров, как показано на рис. 7.5. 2. Используя информацию в поле состояния машины, вызывающая процедура восстанавливает ~ор зр и другие регистры и переходит к адресу возврата, который помещен вызывающей процедурой в поле состояния. 3. Хотя значение ~ор зр было уменьшено, вызывающая процедура знает, где находится возвращаемое значение по отношению к текущему значению ~ор зр; таким образом, вызывающая процедура может получить доступ к возвращаемому значению и использовать его. Приведенные выше последовательности вызова и возврата позволяют количеству аргументов вызываемой процедуры изменяться от вызова к вызову (как в функции ргзпс й языка программирования С).

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

7.7, информация, описывающая параметры, должна располагаться после поля состояния машины, чтобы вызываемая процедура легко могла ее найти. Например, в случае функции ргзпт.й языка программирования С первый аргумент описывает остальные, так что после того, как функция находит первый аргумент, она знает, где располагаются все остальные аргументы. 539 7.2. Выделение памяти в стеке 7.2.4 Данные переменной длины в стеке Система управления памятью времени выполнения зачастую должна выделять память для объектов, размеры которых во время компиляции неизвестны, но которые являются локальными объектами процедуры и, таким образом, могут размещаться в стеке. В современных языках память для объектов неизвестного во время компиляции размера выделяется из кучи, которая будет рассматриваться в разделе 7.4.

Однако выделение памяти в стеке для объектов, массивов и других структур неизвестного размера возможно, и мы рассмотрим здесь, как это делается. Причина, по которой размещение объектов в стеке предпочтительнее размещения в куче, в том, что в этом случае мы избегаем затрат на сборку мусора. Заметим, что стек может использоваться только для объектов, локальных по отношению к данной процедуре и становящихся недоступными после возврата из нее. Распространенная стратегия выделения памяти для массивов переменной длины (т.е. массивов, размеры которых зависят от значений одного или нескольких параметров вызываемой процедуры) показана на рис. 7.8.

Та же схема работает для объектов любого типа, если они локальны для вызываемой процедуры и имеют размер, зависящий от параметров вызова. Запись аятивациидвяр Массивыр Записьактивации дпя процедуры в званной процедуройр тор тр Массивы д тор Рис. 7.8. Доступ к динамически распределенным массивам Глава 7. Среды времени выполнения На рис.

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

Таким образом при выполнении р эти указатели находятся в позициях с известными смещениями относительно указателя на вершину стека, так что целевой код может получить доступ к элементам массива посредством этих указателей. На рис. 7.8 также показана запись активации для процедуры д, вызванной процедурой р. Запись активации для д начинается после массивов р, и все массивы переменной длины процедуры д располагаются за ней. Доступ к данным в стеке осуществляется при помоши двух указателей — гор и гор зр. Здесь гор отмечает фактическую вершину стека; он указывает на позицию, в которой начнется очередная запись активации. Второй указатель, гор зр, используется для поиска локальных полей фиксированной длины в записи активации на вершине стека.

Для согласованности с рис. 7.7 мы считаем, что указатель гор зр указывает на конец поля состояния машины. На рис. 7.8 гор зр указывает на конец этого поля в записи активации для д. Там можно найти поле связи управления для д, которое приведет к тому месту в записи активации для р, на которое указывал гор зр, когда запись активации для р находилась на вершине стека. Код для перестановки гор и гор зр может быть сгенерирован во время компиляции с использованием размеров, которые станут известны только во время выполнения. Когда осуществляется возврат из д, гор зр может быть восстановлен по сохраненной связи управления в записи активации для д.

Новое значение гор представляет собой (старое невосстановленное) значение ~ор зр минус длина полей состояния машины, связей управления и доступа, возвращаемого значения и параметров гсм. рис. 7.5) в записи активации д. Эта длина известна вызывающей процедуре во время компиляции и может зависеть от вызывающей процедуры в случае, когда количества параметров могут изменяться от вызова к вызову д. 7.2.5 Упражнения к разделу 7.2 Упражнение 7.2.1. Предположим, что программа на рис. 7.2 использует функцию рагШюл, которая всегда выбирает в качестве разделителя с элемент массива а [гп1 Считаем также, что при переупорядочении массива а)т~,..., а ~п~ его порядок по возможности сохраняется, т.е. сначала идут все элементы, меньшие п, в их исходном относительном порядке, затем — элемент е, а затем — все элементы, ббльшие п, также в исходном относительном порядке. а) Изобразите дерево активаций для сортировки чисел 9„8, 7, 6, 5, 4, 3, 2, К б) Чему равно максимальное количество записей активации, одновременно находящихся в стеке? 7.2.

Выделение памяти в стеке Упражнение 7.2.2. Повторите упражнение 7.2.1 для набора чисел 1, 3, 5, 7, 9, 2, 4, 6, 8. Упражнение 7.2.3. На рис. 7.9 приведен код на языке программирования С, рекурсивно вычисляющий числа Фибоначчи.

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

Список файлов книги