РАСПРЕДЕЛЕНИЕ ПАМЯТИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск по сайту: