Построение абстрактной модели
Модель строится на основе абстрактного описания алгоритма оптимизации.
Алгоритм оптимизации формулируется с использованием терминов, обозначающих сущности некоторого подходящего абстрактного представления программы, такого как граф потока управления, граф потока данных, таблица символов и пр. Оптимизатор для осуществления своих трансформаций ищет сочетания сущностей абстрактного представления программы, которые удовлетворяют некоторым шаблонам (например, наличие в программе циклов, наличие в теле цикла конструкций с определенными свойствами, наличие в процедуре общих подвыражений, наличие между инструкциями зависимости данных некоторого вида и пр.). При этом могут учитываться сущности лишь части терминов. Для построения модели мы будем рассматривать только те термины, которые именуют сущности, задействованные хотя бы в одном шаблоне.
Итак, в результате анализа алгоритма выделяются термины и шаблоны, используемые в алгоритме. Далее на основании этой информации описывается множество модельных строительных блоков:
- каждому термину соответствует свой вид модельного строительного блока;
- строительные блоки могут связываться между собой чтобы иметь возможность образовывать структуры, соответствующие шаблонам.
Пример: Weak-Zero SIV Subscripts analyzer. Рассмотрим анализатор, собирающий информацию о некотором виде зависимости данных для последующего использования этой информации в различных оптимизаторах. А именно, рассмотрим Weak-Zero SIV Subscripts analyzer (см., например, []).
Термин subscript используется для обозначения пары выражений, использующихся в паре обращений в теле цикла к одному (возможно, многомерному) массиву и стоящих на одной и той же позиции в ндексах. Subscript называется SIV (single index variable), если на соответствующей индексируемой позиции используется ровно одна индексная переменная. SIV subscript, зависящий от индукционной переменной i, называется слабо-нулевым (weak-zero), если он имеет вид <ai+c1, c2>, где a, c1, c2 - константы и a≠0.
Зависимость между двумя обращениями к массиву существует тогда и только тогда, когда обращение к общему элементу попадает в границы цикла.
Это случается только тогда, когда значение
Этот алгоритм использует следующие термины: SIV subscript, определяемый тремя коэффициентами a, c1 и c2; цикл, определяемый своей нижней границей L и верхней границей U. Алгоритм осуществляет поиск следующего шаблона: Таким образом, модель состоит из следующих видов строительных блоков:
- SIV subscript, содержащий три атрибута, которые соответствуют значениям a, c1 и c2;
- Цикл, содержащий два атрибута, которые соответствуют значениям L и U, а также множество SIV subscript.
- если некоторый переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2, то J1 трансформируется в прямую ссылку на метку L2;
- если обе ветви условного перехода J ведут на одну и ту же метку L, то J трансформируется в безусловный переход на метку L;
- если метка L некоторого линейного участка B не используется ни в каком переходе, то B удалается.
- переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2;
- обе ветви условного перехода J ведут на одну и ту же метку L;
- метка L не используется ни в каком переходе;
Такое представление тесно связано с синтаксической структурой программы. Редукция грамматики языка позволяет получить модель, которая состоит из следующих видов строительных блоков:
- Процедура, содержащая последовательность линейных участков;
- Линейный участок, содержащий метку, переход, а также атрибут ``пустой'';
- Метка, содержащая атрибут ``не используется'';
- Безусловный переход, содержащий ссылку на метку;
- Условный переход, содержащий ссылки на метки.
(1) |
- i0<L, например, i0=L-1;
- i0=L;
- i0 расположено близко к L внутри интервала, задаваемого границами цикла, например, i0=L+1;
- i0 расположено в середине интервала, задаваемого границами цикла, например, i0=;
- i0 расположено близко к U внутри интервала, задаваемого границами цикла, например, i0=U-1;
- i0=U;
- i0>U, например, i0=U+1.