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

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

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

7.4. Функции на рисунке представлены первыми буквами их имен. Не забывайте, что данное дерево — только одно из множества возможных, поскольку аргументы по- 532 Глава 7. Среды времени выполнения следовательных вызовов, а также количество вызовов вдоль любой ветви зависит от значений, возвращаемых функцией рагууууол. а Г р(2,3) 9(2,)) у(3,3) р(7,9) 9(7,7) д(9,9) Рнс.

7.4. Дерево активации, представляющее вызовы в процессе выполнения быстрой сортировки Возможность использования стека времени выполнения обеспечивается некоторыми взаимосвязями между деревом активации и поведением программы. !. Последовательность вызовов процедур соответствует обходу дерева акти- вации в прямом порядке. 2.

Последовательность возвратов из процедур соответствует обходу дерева активации в обратном порядке. 3. Предположим, что управление находится в некоторой активации какой-то процедуры, соответствующей узлу (37 дерева активации. Тогда открытыми в настоящий момент активациями (аклуивньиии — йче) являются активации, соответствующие узлу 737 и его предкам. Порядок вызова этих активаций определяется порядком их появления на пути от корня дерева активации до узла М, а возврат из них будет осуществляться в порядке, обратном порядку их активаций.

7.2.2 Записи активации Вызовы процедур и возвраты из них обычно управляются стеком времени выполнения, именуемым стеком управления (соп(го! з(ас((). Каждая активная активация имеет зались активации (асбчабоп гесог((), иногда именуемую кадром ((гаупе), в стеке управления. На дне стека находится запись активации корня дерева активации, а последовательность записей активации в стеке соответствует пути в дереве активации от корня до текущей активации, в которой в настоящий момент находится управление.

Запись последней по времени активации находится на вершине стека. 533 7.2. Выделение памяти в стеке Пример 7.3. Если управление в настоящий момент находится в активации о (2, 3) дерева на рис. 7.4, то запись активации для о (2, 3) находится на вершине стека управления. Непосредственно под ней находится запись активации для д (1, 3)— родителя д (2, 3) в дереве активации. Еше ниже в стеке находится запись активации для д (1, 9), а в самом низу стека размещена запись активации для т — активации функции ва1п, представленной корнем дерева активации. и Будет удобнее изображать стеки управления так, чтобы низ стека находился выше его вершины, так что элементы записи активации, находящиеся ниже на странице книги, на самом деле были ближе к вершине стека. Содержимое записи активации варьируется в зависимости от реализуемого языка программирования.

Вот список данных, которые могут находиться в записи активации (элементы данных и их возможный порядок в стеке показаны на рис. 7.5). Рис. 7.5. Общий вид записи активации !. Временные значения, появляющиеся, например, в процессе вычисления выражений, когда эти значения не могут храниться в регистрах. 2. Локальные данные процедуры, к которой относится данная запись актива- ции.

3. Информация о состоянии машины непосредственно перед вызовом процедуры. Эта информация обычно включает адрес возврата (значение счетчика программы, которое должно быть восстановлено по выходу из процедуры) и содержимое регистров, которые использовались вызывающей процедурой и должны быть восстановлены при возврате из вызываемой процедуры. 534 Глава 7. Среды времени выполнения 4. Связь доступа может потребоваться для обращения вызванной процедуры к данным, хранящимся в другом месте, например в другой записи активации. Связи доступа рассматриваются в разделе 7.3.5. 5.

Связь управления указывает на запись активации вызывающей процедуры. 6. Память для возвращаемого значения вызываемой функции„если таковое имеется. Не все вызываемые процедуры возвращают значения, а кроме того, для большей эффективности возвращаемое значение может находиться не в стеке, а в регистре. 7. Фактические параметры, используемые вызываемой процедурой.

Зачастую эти значения также располагаются не в стеке, а по возможности для большей эффективности передаются в регистрах. Однако в общем случае место для них отводится в стеке. Пример 7.4. На рис. 7.6 показаны снимки стека времени выполнения при прохождении управления по дереву активации на рис. 7.4. Пунктирные линии в частях дерева указывают завершенные активации.

Поскольку массив и — глобальный, память для него выделяется до начала активации функции та~и, как показано на рис. 7.6, а. Когда управление достигает первого вызова в теле функции та1л, активируется процедура г и ее запись активации вносится в стек (см. рис. 7.6, 6). Запись активации для г содержит пространство для локальной переменной 1 (вспомните, что вершина стека находится внизу). Когда управление возвращается из этой активации, ее запись снимается со стека, оставляя там только одну запись активации функции та1п. Затем управление достигает вызова д с фактическими параметрами 1 и 9 и на вершину стека помещается запись активации для этого вызова, как показано на рис. 7.6, в. Запись активации для 9 содержит пространство для параметров т и п и локальной переменной з, следуя общей схеме на рис.

7.5. Обратите внимание, что сейчас повторно используется пространство стека, которое ранее было отведено для записи активации г. Никакие локальные данные функции г не доступны для вызова о (1,9). Когда происходит возврат из вызова функции д (1, 9), стек вновь содержит только одну запись активации функции гла1л. Между двумя последними снимками на рис. 7.6 произошло несколько активаций. Был выполнен рекурсивный вызов д (1,3). За время жизни этой активации начались и закончились активации р (1, 3) и 911, 0), оставляя запись активации для 9 (1,3) на вершине стека (см.

рис. 7.6, г). Заметим, что в случае рекурсивной процедуры одновременное наличие нескольких ее записей активации в стеке— обычное явление. и 535 7.2. Выделение памяти в стеке елгеяег а[! Ц гаа(л еа(л о)гактивирована а) Кадр для функции та!л там там г 9(1,9) р(1,9) 9(1,3) г 9(1,9) р(1,3) 9(1 д) л) г снята со стека, 9(1,9) внесена л стек г) Управление возвращается к 9(1,3) Рис. 7.6, Растущий вниз стек записей активации 7.2.3 Последовательности вызовов Вызовы процедур реализованы с помощью последовал)ельвостей вызовов (са11- 1пк зе()пепсез), состоящих из кода, который выделяет память в стеке для записи активации и вносит информацию в ее поля. Последовательность возврата представляет собой аналогичный код, который восстанавливает состояние машины, так что вызывающая процедура может продолжать работу. Последовательности вызовов и схема записей активации могут существенно отличаться даже в разных реализациях одного и того же языка.

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

Однако часть последовательности вызова в вызываемой процедуре генерируется лишь единожды. Следовательно, желательно разместить как можно ббльшую часть последовательности вызова в коде вызываемой проце- 536 Глава 7. Среды времени выполнения дуры — с учетом того, что известно вызываемой процедуре при ее вызове. Как мы увидим, вызываемая процедура не имеет доступа ко всей информации. При разработке последовательностей вызовов и схемы записей активации помогают следующие принципы.

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

Более того, это позволяет реализовать процедуры, которые принимают при каждом вызове различное количество аргументов, как, например, функция ркзпс й в языке программирования С. Вызываемая функция знает, где в ее записи активации следует разместить возвращаемое значение; ее же аргументы располагаются в стеке последовательно ниже этого места. Элементы фиксированного размера обычно располагаются посредине. Как видно из рис. 7.5, эти элементы обычно включают связь управления, связь доступа и состояние машины. При каждом вызове сохраняются одни и те же компоненты состояния машины, так что сохранение и восстановление состояния для каждого вызова осуществляется одним и тем же кодом.

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

Однако некоторые локальные переменные имеют размер, который не может быть выяснен до выполнения программы; наиболее распространенным примером является массив с динамическим размером, который определяется одним из параметров вызываемой процедуры. Кроме того, количество памяти„необходимой для временных переменных, обычно зависит от того, насколько успешно они распределяются по регистрам на стадии генерации кода.

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

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