8. Машинно-зависимые фазы компиляции

Все рассмотренные выше четыре фазы компиляции являются машинно-независимыми и определяются только языком программирования, для которого создается компилятор. Напротив, на остальные три фазы язык уже не оказывает влияния. Это машинно-зависимые фазы, определяемые архитектурой ЭВМ, на которой будет выполняться откомпилированная программа. Промежуточная форма программы, создаваемая на этапах лексического, синтаксического и семантического анализа позволяет логически отделить их от машинно-зависимых фаз распределения памяти, генерации кода и сборки. Рамки пособия не позволяют подробно рассмотреть машинно-зависимые фазы и ниже будут лишь обозначены основные задачи, решаемые на этих фазах.

8.1. Распределение памяти

Основные задачи этой фазы:

 Выделить память для всех переменных программы, в том числе и для временных переменных, хранящих промежуточные результаты.

 Выделить память для всех констант.

 Убедится, что память распределена и величинам по соответствующим адресам присвоено начальное значение (константам и самоопределенным переменным).

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

Алгоритмы этой фазы очень сильно зависят от организации памяти ЭВМ для которой создается компилятор и способах эффективного доступа к ней. Важно знать какие регистры имеются в наличии, допустима ли косвенная адресация, имеются ли базовые и индексные регистры и т.п. При наличии базовых (сегментных) и индексных регистров память для глобальных переменных и констант (статическую память) целесообразно представлять в виде последовательных блоков или сегментов, указывая с помощью регистров начало каждого блока. В этом случае при распределении памяти необходимо определять номера сегментов и вычислять смещения внутри сегментов. Фаза генерации кода будет использовать эти смещения для формирования адресов в командах, и генерировать код, загружающий указатель соответствующего блока памяти (адрес начала сегмента) в регистр во время выполнения программы.

При выделении памяти используется счетчик адреса с нулевым начальным значением, которое затем меняется по мере распределения памяти. Фаза распределения памяти просматривает таблицы идентификаторов и констант и если встречается глобальная (статическая) переменная или константа, то выполняются следующие четыре шага:

(1) При необходимости выравнивается значение счетчика адреса.

(2) В адресное поле таблицы для соответствующей переменной или константы заносится текущее значение счетчика адреса.

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

(4) К содержимому счетчика адреса прибавляется вычисленная длина переменной или константы.

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

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

Алгоритм использует стек C, который вначале содержит набор адресов памяти, предназначенных для временных переменных. При первой встретившейся записи в M_j, которая открывает зону M_j, из стека берется адрес и присваивается M_j (из стека этот адрес естественно выталкивается). При последнем чтении из M_j, которое закрывает ее зону, адрес, присвоенный M_j, записывается в стек C, так как содержимое этой ячейки уже больше не нужно. Формирование адресов для временных переменных вполне можно совместить с генерацией кода. Алгоритм предполагает, что мы знаем тетраду, осуществляющую последнее чтение из M_j. Информацию об этом можно хранить в отдельном поле таблицы идентификаторов для каждой временной переменной.

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

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