Новый подход к построению методов межпроцедурного анализа программ
(Работа поддержана грантом РФФИ №96-01-01433)
А.С. Антонов, Вл.В. Воеводин
Введение
Необходимость выполнения межпроцедурного анализа очень часто возникает на практике, в частности, при анализе параллельных свойств программ. Можно привести множество примеров задач, решаемых с использованием техники межпроцедурного анализа: определение независимости вхождений в тело подпрограммы параметров и глобальных переменных, распараллеливание циклов, содержащих вызовы подпрограмм, определение необходимых пересылок данных для вызова распределяемой подпрограммы при использовании компьютеров с распределенной памятью, поддержка корректности данных в кэш-памяти многопроцессорных систем и многие другие. Без межпроцедурного анализа придется предположить, что все фактические параметры и внешние переменные как используются, так и переопределяются в вызываемой подпрограмме, поэтому многие полезные свойства программы не будут использованы.
В данной работе рассматривается новый подход, основанный на анализе свойств графа алгоритма [1,2,3] впервые описанный в [4].
Обзор существующих методов межпроцедурного анализа
Одним из первых методов разрешения проблемы межпроцедурного анализа была предложена подстановка тела подпрограммы на место вызова (inline expansion [14]), но она сильно затруднена, если в графе вызовов есть контуры, что приводит к значительному увеличению размера кода и времени анализа. В известных обзорах [5,15] большое внимание уделялось методам межпроцедурного анализа без учета индексных переменных. Но такой анализ является весьма грубым и недостаточным для реальных программ, поскольку в большинстве случаев необходима информация о существовании зависимости между ссылками на отдельные элементы массивов.
|
|
Последующее развитие методов межпроцедурного анализа шло по двум направлениям: с одной стороны, уточнение методов нахождения входных и выходных данных подпрограмм, а с другой - описание найденных данных в терминах фактических параметров (обратная подстановка).
В большинстве работ, посвященных межпроцедурному анализу, входные и выходные данные аппроксимируются вырезками массивов, используемыми или изменяемыми в анализируемой подпрограмме. Следуя [9], будем называть такие области READ и WRITE областями. Все методы описания READ и WRITE областей можно разделить на два класса: неточные и точные методы. Неточные методы проще, но, в отличие от точных, описывают только некоторую аппроксимацию необходимой области. Точные же методы могут потребовать много памяти и времени для анализа программ. В некоторых случаях используются комбинированные методы, например, приближенное описание объединения точно описанных областей.
Среди неточных методов получения READ и WRITE областей можно отметить ограниченные регулярные секции (restricted regular sections [8]), описания с помощью триплетов (bounded regular sections [11]), простые секции (simple sections [6]), описание в виде минимальной выпуклой оболочки (convex hull) [9,17]. Из точных методов можно указать подход Бурке-Сайтрона [7] и построение совокупного образа (merged image) [16].
Однако знания READ и WRITE областей недостаточно для полноценного анализа, так как READ области могут содержать данные, вычисленные ранее в исследуемой подпрограмме, а, следовательно, они не будут представлять входных данных анализируемой процедуры. WRITE области могут содержать данные, которые не потребуются нигде в дальнейшем тексте программы, что также не соответствует выходным данным подпрограммы. Для более точного анализа вводятся IN и OUT области, которые представляют именно входные и выходные данные подпрограммы, то есть данные, необходимые для выполнения подпрограммы, и данные, вычисляемые в исследуемой подпрограмме и используемые где-либо далее. Метод получения IN и OUT областей из READ и WRITE областей подробно описан в [9,10].
|
|
Методы описания входных и выходных данных подпрограммы в терминах фактических параметров описаны в работах [9,16].
2Получение входных и выходных данных подпрограмм с помощью графа алгоритма
Использование графа алгоритма, введенного в [1,2,3], позволяет получить точное описание входных и выходных данных фрагмента программы.
Основная идея этого метода заключается в том, чтобы получить описание нужного множества в пространстве элементов массива средствами анализа пространства итераций программы. Если из всей области срабатывания оператора WJ [3] вычесть все области Dk из описания графа алгоритма фрагмента по входу Ai (напомним, что точки областей Dk являются конечными точками дуг графа алгоритма данного фрагмента), то полученная область Winp будет описывать множество точек пространства итераций, в которых Ai потребляет входные для исследуемого фрагмента данные.
Теперь нужно получить описание области пространства итераций Winp в пространстве элементов массива A. Рассмотрим задачу для входа Ai(P(J)) массива A, где P(J) - это векторная функция, определяющая индексные выражения данного входа. Будем предполагать, что для входа Ai найдена подобласть пространства итераций Wiinp, в каждой точке которой аргументом для входа Ai являются начальные данные. По определению данной области, для любой точки JÎWiinp элемент массива Ai(P(J)) нигде в данном фрагменте не вычисляется, а берется из входных данных, т.е. является элементом искомого множества.
|
|
Cконструируем вспомогательный фрагмент, содержащий вход A0 по переменной A:
DO I1 = l1, u1
...
DO Id = ld, ud
... =... A0(I1, I2,..., Id)...
END DO
...
END DO,
где d - это размерность переменной A, а lk, uk - нижняя и верхняя границы k-го измерения массива A соответственно, k=1,d. Будем считать, что данный фрагмент достижим из каждой точки программы и всегда срабатывает последним - этого всегда можно добиться эквивалентным преобразованием фрагмента.
Возьмем любую точку J области Wiinp. Ясно, что элемент массива Ai(P(J))=Ai(p1(J),...,pd(J)) принадлежит искомому множеству и надо найти описание всех подобных точек P(J) в пространстве элементов массива A.
Предположим, что в каждой точке J области Wiinp происходит не использование, а определение элемента Ai(P(J)), т.е. вход Ai будет играть роль выхода. Будем считать областью срабатывания оператора, содержащего Ai, не область WJ, а область Wiinp. Область срабатывания входа A0 определяется только границами циклов вспомогательного фрагмента, так как он безусловно достижим из каждой точки программы.
В таких предположениях решим стандартную задачу построения элементарного графа алгоритма Ai®A0 и найдем область 
, на которой определены дуги графа алгоритма. Особенность множества заключается в том, что, являясь многогранником в пространстве итераций, он одновременно является и описанием множества входных данных в пространстве элементов массива A для входа Ai.
Аналогичным образом данная задача решается для всех входов, а искомое подмножество входных элементов массива A является объединением областей, полученных при решении данной задачи для каждого отдельного входа.
Использование такого метода позволяет получить точное описание IN и OUT областей подпрограммы. Существование эффективных алгоритмов построения графа алгоритма обеспечивает возможность использования этого метода при анализе реальных программ.