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

Кратко опишем содержание программных модулей, используемых для организации генератора списка триад.

Модуль TrdType содержит структуры данных, которые описывают допустимые типы триад.

Он содержит следующие важные типы данных и переменные:

• TTriadType – перечисление всех возможных типов триад;

• TriadStr – массив строковых обозначений для всех типов триад;

• TriaD1ineSet – множество тех триад, которые являются линейными операциями (оно важно для оптимизации и для порождения кода).

Модуль Triads содержит структуры данных, которые описывают триады и список триад. Эти структуры зависят от реализации компилятора, но не зависят от входного языка.

Он содержит следующие важные структуры данных:

• TOperand – описывает операнд триады;

• TTriad – описывает триаду и все связанные с нею данные;

• TTriaD1ist – описывает список триад.

Структура TOperand описывает операнд триады. Она содержит следующие данные:

• ОрТуре – тип операнда, который может принимать три значения:

– OPC0NST – константа;

– OPVAR – переменная (идентификатор);

– OPLINK – ссылка на другую триаду;

• и дополнительную информацию по операнду:

– ConstVal – значение (для константы);

– VarLink – ссылка на таблицу идентификаторов (для переменной);

– TriadNum – номер триады (для ссылки на триаду).

Один из вопросов, который необходимо было решить при реализации операндов триад, состоял в следующем: что использовать для описания ссылки на триаду – непосредственно ссылку на тип данных (указатель) или номер триады в списке?

Оба варианта имеют свои преимущества и недостатки:

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

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

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

Структура TTriad описывает триаду и все связанные с ней данные. Она содержит следующие поля данных:

• TriadType – тип триады (один из перечисленных в типе TTriadType в модуле TrdType);

• Operands – массив операндов триады (из двух операндов типа TOperand);

• Info – дополнительная информация о триаде для алгоритмов оптимизации;

• IsLinked – флаг, сигнализирующий о том, что на триаду имеется ссылка из другой триады, обеспечивающей передачу управления (типа IF или JMP).

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

Этот вопрос уже возникал при выборе метода хранения информации при организации таблиц идентификаторов в лабораторной работе № 1. Тогда было отдано предпочтение второму варианту, поскольку характер и размер хранимой информации для каждого идентификатора был неизвестен.

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

Флаг наличия ссылки важен для определения границ линейных участков программы при оптимизации: если на какую-то триаду есть ссылка из триад типа IF или JMP, значит, на нее может быть передано управление. Такая триада является возможной точкой входа участка программы, а потому – границей линейного участка.

Кроме перечисленных данных структура TTriad содержит следующие процедуры и функции:

• конструктор Create для создания триады;

• функцию проверки совпадения двух триад IsEqual;

• функцию MakeString, формирующую строковое представление триады для отображения триад на экране;

• функции, процедуры и свойства для доступа к данным триады.

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

Структура данных TTriaD1ist описывает список триад и методы работы с ним. Как и некоторые списки, рассмотренные ранее (в лабораторных работах № 2 и 3), она построена на основе динамического массива типа TList из библиотеки VCL системы программирования Delphi 5. В этой структуре нет никаких данных (используются только данные, унаследованные от класса TList), но с ней связаны методы, необходимые для работы со списком триад:

• функция очистки списка триад (Clear) и деструктор для освобождения памяти при удалении списка триад (Destroy);

• функция записи списка триад в текстовом представлении в список строк для отображения списка триад на экране (WriteToList);

• функция удаления триады из списка (DelTriad);

• функция GetTriad и свойство Triads для доступа к триадам в списке по их порядковому номеру.

Следует отметить, что функция записи списка триад в список строк (WriteToList) последовательно вызывает функцию MakeString для записи в список строк каждой триады из списка триад. Функция удаления триады из списка (DelTriad) освобождает память, занятую удаляемой триадой, а кроме того, следит за тем, чтобы при удалении триады флаг метки (IsLinked) от удаляемой триады был корректно переставлен на следующую по списку триаду.