Новый подход к построению методов межпроцедурного анализа программ

(Работа поддержана грантом РФФИ №96-01-01433)

А.С. Антонов, Вл.В. Воеводин

Введение

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

В данной работе рассматривается новый подход, основанный на анализе свойств графа алгоритма [1,2,3] впервые описанный в [4].

1 Обзор существующих методов межпроцедурного анализа

Одним из первых методов разрешения проблемы межпроцедурного анализа была предложена подстановка тела подпрограммы на место вызова (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 области могут содержать данные, вычисленные ранее в исследуемой подпрограмме, а, следовательно, они не будут представлять входных данных анализируемой процедуры. ............