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

Модуль, реализующий алгоритмы оптимизации

Модуль TrdOpt реализует два алгоритма оптимизации списка триад:

• методом свертки объектного кода;

• методом исключения лишних операций.

Алгоритмы, реализованные в модуле TrdOpt, в общем случае не зависят от входного языка, однако они обрабатывают триады типа «присваивание» (в данной реализации – TRDASSIGN). Кроме того, границы линейных участков, на которых работают эти алгоритмы, зависят от триад условного и безусловного перехода (в данной реализации – TRDIF и TRDJMP). Сами алгоритмы требуют для себя триад специального типа, которые в данном случае реализованы как TRDC и TRDSAME.

В итоге реализация алгоритмов оптимизации зависит от следующих типов триад:

• триад присваивания;

• триад условного и безусловного перехода;

• триад специальных типов.

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

Функция вычисления значений триад при свертке объектного кода, которая имеет явную зависимость от входного языка, вынесена в отдельный модуль (модуль TrdCalc, функция CalcTriad).

Кроме функций, реализующих алгоритмы оптимизации, модуль TrdOpt содержит две структуры данных:

• TConstInfo – для хранения информации о значениях переменных;

• TDepInfo – для хранения информации о числах зависимости переменных.

Обе эти структуры построены на основе структуры TAddVarInfo, описанной в модуле TblElem (этот модуль был создан при выполнении лабораторной работы № 1), и предназначены для хранения информации, связанной с переменной в таблице идентификаторов.

Структура TConstInfo хранит информацию о значении переменной, если оно известно. Она используется в алгоритме оптимизации методом свертки объектного кода.

Структура TDepInfo хранит информацию о числе зависимости переменной. Она используется в алгоритме оптимизации методом исключения лишних операций.

Каждая из этих структур имеет одно поле, которое и предназначено для хранения информации. Для доступа к этому полю используются виртуальные функции и связанные с ними свойства, которые переопределяют функции и свойства типа данных TAddVarInfo.

Эти структуры данных создаются по мере выполнения соответствующих алгоритмов и уничтожаются после завершения их выполнения.

Теперь можно сравнить два подхода к хранению дополнительной информации:

1. Хранение информации внутри структур данных (реализовано для триад).

2. Хранение внутри структур данных только ссылок (указателей), а самой информации – во внешних структурах.

Первый подход имеет следующие преимущества:

• доступ к хранимой информации осуществлять проще и быстрее;

• нет необходимости работать с динамической памятью, выделять и освобождать ее по мере надобности.

В то же время первый подход имеет ряд недостатков:

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

• обеспечивается меньшая гибкость в обработке информации.

Второй подход имеет следующие преимущества:

• можно хранить разнородную информацию в зависимости от потребностей на каждой стадии компиляции;

• оперативная память расходуется только на хранение необходимой информации и только тогда, когда она действительно используется;

• обеспечивается более гибкая обработка информации (например, легко реализуется понятие «отсутствие данных» в алгоритме оптимизации методом свертки объектного кода через пустую ссылку nil).

Но и он имеет ряд недостатков:

• использование ссылок увеличивает время доступа к хранимой информации, что может быть важно при обработке компилятором больших объемов данных;

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

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

Алгоритмы оптимизации реализованы в модуле TrdOpt в виде двух процедур:

• OptimizeConst – для оптимизации методом свертки объектного кода;

• OptimizeSame – для оптимизации методом исключения лишних операций.

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

• С (TRDC) – при оптимизации методом свертки объектного кода;

• Same (TRDSAME) – при оптимизации методом исключения лишних операций.

Триады специального вида можно удалить из общего списка триад с помощью функции удаления триад заданного типа (DelTriadTypes), которая была описана в модуле Triads. В принципе, нет необходимости выполнять это, так как на порождаемый объектный код эта операция никак не влияет – триады специального вида не порождают никакого кода, но для иллюстрации работы алгоритмов оптимизации такая операция полезна.

Процедуры OptimizeConst иOptimizeSame реализуют алгоритмы оптимизации, которые были описаны в разделе «Краткие теоретические сведения», поэтому в дополнительных пояснениях не нуждаются.

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

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