Всего за 133 руб. Купить полную версию
Модуль, реализующий алгоритмы оптимизации
Модуль 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 реализуют алгоритмы оптимизации, которые были описаны в разделе "Краткие теоретические сведения", поэтому в дополнительных пояснениях не нуждаются.
Можно отметить только, что для хранения информации, связанной с переменными (значения переменных и числа зависимости переменных), эти процедуры используют непосредственно таблицу идентификаторов. И в этом случае проявляются преимущества того, что в триадах в качестве ссылки на переменную используется именно ссылка на таблицу идентификаторов, а не на имя переменной. Эффективность прямого обращения в таблицу за требуемым значением намного выше, чем поиск переменной по ее имени. Это справедливо для любых операций, выполняемых компилятором на этапах подготовки к генерации кода, генерации кода и оптимизации.
Текст программы генератора списка триад
Кроме перечисленных модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Этот модуль (FormLab4) реализует графическое окно TLab4Form на основе класса TForm библиотеки VCL и включает в себя две составляющие:
• файл программного кода (файл FormLab4.pas);
• файл описания ресурсов пользовательского интерфейса (файл FormLab4.dfm).
Модуль FormLab4 построен на основе модуля FormLab3, который использовался для реализации интерфейса с пользователем в лабораторной работе № 3. Он содержит все данные, управляющие и интерфейсные элементы, которые были использованы в лабораторных работах № 2 и 3. Такой подход оправдан, поскольку первым этапом лабораторной работы № 4 является лексический анализ, который выполняется модулями, созданными для лабораторной работы № 2, а вторым этапом – синтаксический анализ, который выполняется модулями, созданными для лабораторной работы № 3.
Кроме данных, используемых для выполнения лексического и синтаксического анализа так, как это было описано в лабораторных работах № 2 и 3, модуль содержит поле listTriad, которое представляет собой список триад. Этот список инициализируется при создании интерфейсной формы и уничтожается при ее закрытии. Он также очищается всякий раз, когда запускаются процедуры лексического и синтаксического анализа.
Кроме органов управления, использованных в лабораторной работе № 3, интерфейсная форма, описанная в модуле FormLab4, содержит органы управления для генератора списка триад лабораторной работы № 4:
• в многостраничной вкладке (PageControll) появилась новая закладка (Sheet-Triad) под названием "Триады";
• на закладке SheetTriad расположены интерфейсные элементы для вывода и просмотра списков триад (группа с заголовком и список строк для отображения каждого списка триад):
GroupTriadAll и ListTriadAll – для отображения полного списка триад, построенного до применения алгоритмов оптимизации;
GroupTriadConst и ListTriadConst – для отображения списка триад, построенного после оптимизации методом свертки объектного кода;
GroupTriadSame и ListTriadSame – для отображения списка триад, построенного после оптимизации методом исключения лишних операций.
• на той же закладке SheetTriad расположены два сплиттера для управления размерами списков триад;
• на первой закладке SheetFi 1 е ("Исходный файл") появились два дополнительных органа управления – флажки с двумя состояниями ("пусто" или "отмечено"):
CheckDelC – при установке этого флажка триады типа С удаляются из списка триад после выполнения оптимизации методом свертки объектного кода;
CheckDelSame – при установке этого флажка триады типа same удаляются из списка триад после выполнения оптимизации методом исключения лишних операций.
Внешний вид новой закладки интерфейсной формы TLab4Form приведен на рис. 4.3.