Книга: Системное программное обеспечение. Лабораторный практикум

Генератор ассемблерного кода

Порождение ассемблерного кода для триад не представляет проблем. Соответствующие алгоритмы реализованы в модуле 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).

Для унарных линейных операций последовательность действий при генерации ассемблерного кода такова:

1. Запоминается имя операнда. Для переменных именем операнда является имя переменной, для константы – значение константы, а для ссылки на другую триаду, кроме предыдущей, – имя регистра или временной переменной, в которой хранится результат вычисления триады (для предыдущей триады имя операнда пустое).

2. Если имя операнда не пустое, то операнд надо загрузить в регистр eax. Для этого порождается команда mov, но если операнд – результат вычисления предыдущей триады (имя операнда пустое), то загружать в eax его не нужно, так как он уже находится там после вычисления триады, и никакая команда на этом шаге не порождается.

3. Порождается команда, соответствующая унарной операции над регистром eax (в данном результирующем языке: not – для логического отрицания; neg – для унарного арифметического минуса).

4. Если одной команды недостаточно, порождается еще одна команда (в данном случае для логического отрицания требуется еще команда and).

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

Для бинарных линейных операций последовательность действий при генерации ассемблерного кода такова:

1. Запоминаются имена обоих операндов. Для переменных именем операнда является имя переменной, для константы – значение константы, а для ссылки на другую триаду, кроме предыдущей – имя регистра или временной переменной, в которой хранится результат вычисления триады (для предыдущей триады имя операнда пустое).

2. Если имя одного из операндов пустое (операнд получен при вычислении предыдущей триады), то нет необходимости загружать его в регистр eax, иначе порождается команда mov, которая загружает первый операнд в регистр eax.

3. Порождается команда, соответствующая бинарной операции над регистром eax. Если имя второго операнда пустое, то первый операнд триады становится вторым операндом команды, иначе – второй операнд триады становится вторым операндом команды.

4. Если одной команды недостаточно, порождается еще одна (в данном результирующем языке это необходимо только для команды вычитания sub в том случае, если операнды менялись местами – чтобы получить верный результат, требуется еще команда neg).

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

Определение имени операнда выполняется вспомогательной функцией GetOpName. Порождение ассемблерного кода выполняется функцией MakeOper1 – для унарных операций, и функцией MakeOper2 – для бинарных операций. Можно обратить внимание, что функция GetOpName проверяет имя переменной на совпадение его с предопределенным именем CompileTest, и если имена совпадают, заменяет имя переменной на предопределенное имя Result. Эта проверка и подстановка – простейший пример модификации компилятором результирующего кода в зависимости от семантических соглашений (предопределенное имя Result всегда обозначает результат функции в выходном языке). В промышленных компиляторах такие модификации, как правило, связаны с неявными преобразованиями типов данных, принятыми во входном языке.

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

Для триад присваивания значений и для триад безусловного перехода (JMP) порождение команд элементарно просто и не требует пояснений.

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

1: < (a, b)

можно построить по

mov eax, a
cmp eax, b
jl @M1_1
xor eax, eax
jmp @M1_2
@M1_1: xor eax, eax
inc eax
@M1_2:

которая будет обеспечивать запись в регистр аккумулятора (eax) логического результата операции сравнения (0 – «ложь», 1 – «истина»).

Однако, как уже было сказано, большое количество операций передачи управления не способствует эффективности выполнения программы. К тому же рассмотренный выше подход порождает много лишних команд. Как правило, в процессорах есть команды, позволяющие организовать либо прямой обмен между регистром флагов и регистром аккумулятора, либо обмен данными через стек. В процессорах типа Intel 80x86 это команды группы set<*>, где <*> зависит от необходимого флага [41, 44]. Тогда для того же самого примера порядок команд будет иным:

mov eax, a
cmp eax, b
setl al
and eax, 1

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

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

test eax, eax

однако эффективность результирующего кода можно увеличить, если учесть, что триаде IF всегда предшествует либо триада сравнения, либо триада логической операции, а следовательно, при выполнении кода, порожденного для этих триад, флаги уже будут установлены соответствующим образом. Тогда нет необходимости порождать дополнительную команду для установки флагов и для триады IF достаточно построить только команду условного перехода по флагу «ноль» (в процессорах типа Intel 80x86 это команда jz).

Но система команд процессоров типа Intel 80x86 имеет одну особенность: команды условного перехода могут передавать управление не далее, чем на 128 байт вперед или назад от места команды. В момент генерации кода для триады IF, как правило, не известно, будет ли передача управления происходить в пределах 128 байт кода или выйдет за рамки данного ограничения. Чтобы обойти это ограничение, передачу управления можно организовать с помощью двух команд: сначала команда условного перехода по обратному условию «не ноль» передает управление на локальную метку, а потом команда безусловного перехода передает управление на требуемую «дальнюю» метку:

jnz @Fx
jmp @Mx
Fx:…

Здесь @Fx – локальная («обходная») метка, а @Mx – та метка, на которую необходимо передать управление. Именно такой подход реализован в разработанном генераторе ассемблерного кода.[11]

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

a:= 1;
if (a<0) b:=0 else b:=1;

первая часть условного оператора (b:=0) никогда не будет выполнена и в результате выполнения оптимизации это станет очевидным (первый операнд триады IF будет равен 0). Генератор ассемблерного кода порождает соответствующий код: если первый операнд равен 0 – команду безусловного перехода; если первый операнд не равен 0, никаких команд для триады IF вообще не порождается.

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

Оглавление книги