Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

Текст полученного программного модуля TrdMake приведен в листинге П3.12, приложение 3.

Порождение ассемблерного кода для триад не представляет проблем. Соответствующие алгоритмы реализованы в модуле TrdAsm (листинг П3.13, приложение 3). Этот модуль зависит от внутреннего представления программы (от типов триад) и от целевой вычислительной системы (выходного языка). Главная задача заключается в том, чтобы распределить память и регистры процессора для хранения промежуточных результатов триад в тех случаях, когда эти результаты используются в качестве операнда в других триадах.

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

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

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

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

d:= a + b + c;

с:= d *(a + b);

a:= d *(a + b) + 1;

будет соответствовать последовательность триад:

1: + (a, b)

2: + (^1, c)

3::= (d, ^2)

4: * (d, ^1)

5::= (с, ^4)

6: + (^4, 1)

7::= (a, ^6)

Область действия для каждой триады в этой последовательности показана на рис. 5.3.

Если отбросить триады, область действия которых не распространяется дальше одной триады (как было сказано выше, для них не требуется хранение промежуточных результатов), то по рис. 5.3 видно, что для данной последовательности триад достаточно одной временной переменной, в которую сначала необходимо занести значение триады № 1, а затем – значение триады № 4. Если пользоваться рассмотренным ранее алгоритмом, то потребовалось бы как минимум две временных переменных.

Рис. 5.3. Области действия триад в списке триад.

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

Именно такой алгоритм распределения временных переменных и регистров реализован в функции MakeRegisters в модуле TrdAsm. Эта функция просматривает список триад с конца и распределяет регистры по порядку начиная от первого упоминания каждой триады. Номер закрепленного регистра записывается в информационное поле каждой триады (если это поле равно 0, считается, что нет необходимости хранить промежуточный результат вычисления триады). Минимальная граница области действия триады, в пределах которой регистр не может быть распределен повторно, запоминается в специальном списке регистров (в функции этот список представлен переменной listReg). Количество регистров, упомянутых в нем, и будет равно необходимому количеству регистров для вычисления списка триад.

Генератор ассемблерного кода ориентирован на процессоры типа Intel 80386 и более поздних модификаций в защищенном режиме работы. В этом режиме в процессоре доступно шесть регистров общего назначения по 32 бит каждый [41, 44]:

• еах;

• ebx;

• есх;

• edx;

• esi;

• edi.

Регистр esp используется как указатель стека, а регистр ebp – как базовый указатель стека (хранение временных переменных в стеке с использованием двух регистров описано в разделе, посвященном организации дисплеев памяти процедур и функций в [2, 3, 7]).

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

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

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

Для выполнения всех операций и хранения их результатов в пределах одной триады будем использовать регистр аккумулятора – eax. Кроме того, что это наглядно и удобно, в процессорах серии Intel 80x86 некоторые команды с этим регистром занимают меньше памяти и выполняются быстрее, чем команды с другими регистрами (а в ряде команд этот регистр является единственно возможным) [41, 44].

Порождение ассемблерного кода по списку триад выполняется функцией MakeAsmCode из модуля TrdAsm (листинг П3.13, приложение 3).