Построение абстрактной модели

Модель строится на основе абстрактного описания алгоритма оптимизации.

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

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

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

Пример: 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.

Зависимость между двумя обращениями к массиву существует тогда и только тогда, когда обращение к общему элементу попадает в границы цикла.
Это случается только тогда, когда значение

является целым и L ≤ i0 ≤ U, где L и U соответственно нижняя и верхняя граница цикла. Этот алгоритм использует следующие термины: SIV subscript, определяемый тремя коэффициентами a, c1 и c2; цикл, определяемый своей нижней границей L и верхней границей U. Алгоритм осуществляет поиск следующего шаблона:

Таким образом, модель состоит из следующих видов строительных блоков:

SIV subscript, содержащий три атрибута, которые соответствуют значениям a, c1 и c2;
Цикл, содержащий два атрибута, которые соответствуют значениям L и U, а также множество SIV subscript.

Для частного случая оптимизаций, работающих с таким абстрактным представлением, которое близко синтаксической структуре программы, можно использовать способ построения модели, основанный на идее редукции грамматик (см. []). Пример: Control Flow Graph optimizer. Рассмотрим оптимизатор, который осуществляет трансформации для упрощения графа потока управления процедуры. Термин линейный участок (basic block) обозначает последовательность инструкций, которая начинается с метки, может заканчиваться условным или безусловным переходом, и может содержать последовательность не-переходных инструкций. Линейный участок называется пустым, если в нем не содержится не-переходных инструкций. Оптимизатор осуществляет следующие трансформации:

если некоторый переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2, то J1 трансформируется в прямую ссылку на метку L2;
если обе ветви условного перехода J ведут на одну и ту же метку L, то J трансформируется в безусловный переход на метку L;
если метка L некоторого линейного участка B не используется ни в каком переходе, то B удалается.

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

переход J1 ведет на метку L1 некоторого пустого линейного участка, который завершается безусловным переходом J2 на метку L2;
обе ветви условного перехода J ведут на одну и ту же метку L;
метка L не используется ни в каком переходе;

Этот алгоритм использует граф потока управления в качестве абстрактного представления обрабатываемой программы.

Такое представление тесно связано с синтаксической структурой программы. Редукция грамматики языка позволяет получить модель, которая состоит из следующих видов строительных блоков:

Процедура, содержащая последовательность линейных участков;
Линейный участок, содержащий метку, переход, а также атрибут ``пустой'';
Метка, содержащая атрибут ``не используется'';
Безусловный переход, содержащий ссылку на метку;
Условный переход, содержащий ссылки на метки.

Будем называть модельной структурой граф, вершины которого - строительные блоки, а ребра - связи между строительными блоками. Проекция предложений исходного языка в модельные структуры индуцирует разбиение множества предложений исходного языка на классы эквивалентности. Один класс эквивалентности состоит из предложений, которые имеют одинаковое модельное представление, т.е. которые неразличимы для алгоритма оптимизации. Это свойство позволяет нам выдвинуть гипотезу, согласно которой на эквивалентных предложениях оптимизатор работает одинаково. Следовательно, в желаемом тестовом наборе достаточно иметь не более одного представителя из каждого класса эквивалентности. Поскольку множество модельных структур, т.е. множество классов эквивалентности, в общем случае бесконечно, то для создания тестового набора мы должны выбрать некоторое его конечное подмножество. Основанием для этого выбора должны служить те шаблоны, которые были выделены при анализе алгоритма оптимизации. Таким образом, критерий тестового покрытия формулируется в терминах абстрактной модели. Пример: Критерий тестового покрытия для анализатора Weak-Zero SIV Subscripts. Напомним, что анализатор Weak-Zero SIV Subscripts осуществляет поиск следующего шаблона: L ≤ i0 ≤ U и i0 целое, где i0 определяется из соотношения

(1)

Сформулируем соответствующий критерий тестового покрытия в терминах модели, т.е. в терминах L, U, a, c1 и c2. Фиксируем L, U и c1 - целые числа. Пусть a принимает значения 1 и 2. Мы хотим, чтобы i0 принимало целые значения из некоторого множества, а также какие-нибудь нецелые значения.Пусть в упомянутое множество входят целые числа, удовлетворяющие одному из следующих требований:

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.

Для нахождения значения c2 достаточно решить уравнение (1) относительно значений a и i0.

Содержание раздела