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

Описание используемого метода оптимизации

Машинно-независимые методы оптимизации

Оба используемых машинно-независимых метода оптимизации – метод свертки объектного кода и метод исключения лишних операций – были описаны при выполнении лабораторной работы № 4, поэтому нет необходимости описывать их здесь повторно. Эти методы оптимизации не зависят ни от входного, ни от результирующего языка, а потому реализующие их алгоритмы, разработанные при выполнении лабораторной работы № 4, могут быть без модификаций использованы в курсовой работе.

Функции, осуществляющие оба метода машинно-независимой оптимизации, реализованы в модуле TrdOpt (листинг П3.11, приложение 3). Для алгоритма оптимизации методом свертки объектного кода необходимо вычислять значения триад, которые могут входить в состав линейных участков кода. Типы таких триад, а также функции вычисления их значений зависят от входного языка (поэтому при выполнении лабораторной работы № 4 они были выделены в отдельный модуль). Вычисления триад для алгоритма свертки объектного кода для курсовой работы реализованы в модуле TrdCalc (листинг П3.9, приложение 3).

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

• для логической операции OR нет необходимости порождать код, выполняющий эту операцию, если один из операндов равен 0;

• для операции AND нет необходимости порождать код, выполняющий эту операцию, если один из операндов равен 1;

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

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

Машинно-зависимые методы оптимизации

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

Реализованные методы машинно-зависимой оптимизации основаны на двух особенностях системы команд процессоров типа Intel 80x86 [41, 44]:

1. Особенность загрузки данных в регистр аккумулятора eax.

2. Особенность выполнения арифметических операций.

В первом случае учитывается, что команда загрузки нулевого значения в регистр аккумулятора eax

mov eax, 0

выполняется дольше и имеет большую длину, чем команда очистки регистра eax, которая может быть осуществлена с помощью операций xor (исключающее или) или sub (вычитание) над этим регистром процессора. Например:

xor eax, eax

Поэтому в тех случаях, когда в регистр аккумулятора eax требуется загрузить нулевое значение, генератор ассемблерного кода порождает именно команду очистки регистра. Аналогично, если необходимо загрузить значение, равное 1, то порождается пара команд

xor eax, eax

inc eax

а для значения -1 – пара команд

xor eax, eax

dec eax

Оптимизация загрузки регистра аккумулятора выполняется при порождении результирующего кода. Она реализована в функции MakeMove в модуле TrdAsm (листинг П3.13, приложение 3).

Надо отметить, что эта оптимизация существенно зависит и от целевой вычислительной системы (поскольку она использует особенности системы команд процессоров типа Intel 80x86), и от результирующего языка (например, если бы операндами были однобайтовые величины, эффективность такой оптимизации была бы сомнительна).

Во втором случае учитывается, что при выполнении операций сложения и вычитания в тех случаях, когда один из операндов равен 1 или -1, результирующий код будет более эффективным, если использовать ассемблерные команды увеличения и уменьшения значения регистра на 1 (команды inc и dec):

• для операции сложения порождается команда inc вместо команды add, если один из операндов равен 1;

• для операции сложения порождается команда dec вместо команды add, если один из операндов равен -1;

• для операции вычитания порождается команда inc вместо команды sub, если второй операнд равен -1;

• для операции вычитания порождается команда dec вместо команды sub, если второй операнд равен 1.

Оптимизация арифметических операций также происходит при генерации результирующего кода. Она реализована в функции MakeOpcode в модуле TrdAsm (листинг П3.13, приложение 3).