Методы межпроцедурного анализа. Идрисов, страница 3
Описание файла
PDF-файл из архива "Методы межпроцедурного анализа. Идрисов", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Такой анализ не производится, если не учитывается возможность вызовапроцедуры из различных контекстов и влияние контекста на тело процедуры вообще. Множество OUT отражает характеристики не самой подпрограммы, а последующего кода, и может быть использовано для межпроцедурных оптимизаций.
Например, может оказаться, что некоторые или всевнутрипроцедурные вычисления могут быть удалены как мёртвый код.Множества READ, WRITE и IN можно получить при помощи итеративного алгоритма в один проход:1. Изначально все множества принимаются пустыми.2. Для каждого узла:– если присутствует чтение из некоторой переменной, и она несодержится во множестве WRITE — её следует добавить вомножество READ;– если добавленная переменная не является локальной — она добавляется в IN;– если присутствует запись в некоторую переменную — её следует добавить во множество WRITE;– если переменная, добавленная во множество WRITE, не является локальной — она добавляется так же в OUT.48Методы и инструменты конструирования программ3.Для каждого вызова подпрограммы потребуется предварительноевычисление его множеств IN и OUT (хотя бы приблизительное),далее вызов рассматривается как обычный узел, использующий переменные IN и вычисляющий (записывающий) переменные OUT.Здесь под локальными переменными понимаются переменные, областьвидимости которых ограничивается данной процедурой.
В результате мыполучаем первые три множества и верхнюю оценку множества OUT, дляточного вычисления которого требуется проанализировать остаток кодапрограммы на предмет использования (чтения) переменных этого множества. Запись без чтения автоматически убирает переменную из множестваOUT, поскольку в этом случае результат вычисления не используется, соговоркой, что запись производится для любого из контекстов вызова процедуры (для любого пути исполнения в графе вызовов программы).Если при анализе переменных рассматривать каждый массив как одноцелое (запись в элемент массива считать записью массива, а чтение переменной массива считать чтением массива) — результат получается слишком грубым.
Для более точного анализа следует рассматривать компонентымассива отдельно, что и производится при анализе итераций циклов, использующих массивы, но для глобального анализа этот способ имеет слишком много накладных расходов. Компромиссом является рассмотрение отдельных областей массива в качестве атомарных единиц. Существует множество способов описания областей, и всегда можно выбрать тот, которыйнаиболее подходит для конкретной системы по точности/скорости работы итребуемым объёмам памяти. Рассмотрим основные способы описания областей массивов. Их можно разделить на две группы:1) точные — дают такой же результат, что и анализ каждой компоненты массива как отдельной переменной;2) неточные — дают приближённое описание областей массивов, которое требует меньше памяти и вычислительного времени, но даётогрублённый результат.2.3.1.
Неточные алгоритмы описания областей массивовКроме рассмотренных ниже алгоритмов анализа, разработчики Fida [8]включают в состав неточных алгоритмов “Пессимистический (Pessimistic)алгоритм”, который заключается в том, что все массивы предполагаютсяизменяемыми в процессе работы процедуры (межпроцедурный анализ неосуществляется), и “Классический (Classic)” — анализ массивов как скаляров.
Это делается для сравнения их на тестах другими алгоритмами.Идрисов Р. И. Методы межпроцедурного анализа492.3.1.1. Регулярные секции (Regular Sections)Этот алгоритм впервые предложили Каллаган и Кеннеди [9] (Callahan,Kennedy). Области массивов задаются через значения индексных переменных размерностей массива. Регулярные секции делятся на два вида: ограниченные регулярные секции (restricted regular sections) и описания с помощью триплетов (bounded regular sections). В методе ограниченных регулярных секций каждой из размерностей массива сопоставляется одно изследующих выражений:1) ┴ — если индексная переменная может принимать любое значение;2) α — если переменная принимает только одно, константное значение;3) α±jk — если индексная переменная связана с другой индексной переменной этого же массива константным смещением.Таким образом, этот алгоритм может описывать строки, диагонали иещё некоторые виды регионов в массиве, но несложно придумать такуюобласть, описание которой даст весь массив целиком, потому что не найдётся другого возможного описания.
При объединении и пересечении областей требуется процесс нормализации (приведения к зависимости от одной индексной переменной в случае, если есть записи типа 3). Сложностьалгоритма объединения областей — O(d2), где d — размерность массива.При описании с помощью триплетов (bounded regular sections) каждойразмерности массива сопоставляется тройка чисел (l:u:s), где l — нижняяграница значений индексной переменной, u — верхняя граница, а s — шагизменения значения индексной переменной. Также возможны значения(α.α.α) — если индексная переменная принимает константное значение,(┴.┴.┴) — если значение индексной переменной неизвестно.
Этот алгоритмне требует нормализации при объединении областей, его сложность —O(d).2.3.1.2. Дескрипторы доступа к данным (Data Access Descriptors)Впервые предложен Валасундарам и Кеннеди [10] (Balasundaram, Kennedy). В алгоритме области массива описываются простыми секциями (simple sections), которые имеют ортогональные и диагональные границы. Ортогональные границы накладывают условие на максимальное и минимальное значение индексной переменной размерности, диагонали накладываютограничение на пару индексных переменных различных размерностей.Границы хранятся в следующем виде:50Методы и инструменты конструирования программ1)2)α ≤ xi ≤ β , i ∈ [1, n]F — ортогональная граница,α ≤ xi − x j ≤ β , ∀i, j ∈ [1, n], i ≠ jF — диагональ,3)α ≤ xi + x j ≤ β , ∀i, j ∈ [1, n], i ≠ jF — обратная диагональ.Время построения минимальной оболочки для набора циклов не можетбыть выражено через их количество и размерность массива.
Скорость построения объединения O(d) согласно [11], где d — количество уравнений вописании области массива.2.3.1.3. Регионы (Regions)Алгоритм заключается в описании областей массива в виде минимальной выпуклой оболочки (convex hull) [12], которая ограничивается линейными неравенствами.
Неравенства делятся на набор индексных выражений(region) и контекст исполнения (execution context). Контекст исполненияотражает ограничения на управляющие параметры цикла. Здесь, в отличиеот предыдущего метода, линейные неравенства не ограничиваются толькодиагональными и ортогональными границами. Это позволяет описать болеесложные области, но увеличивает время построения оболочки.
Скоростьобъединения также O(d) согласно [11].2.3.2. Точные алгоритмы описания областей массивов2.3.2.1. Образы (Atom Images)Этот алгоритм впервые предложен Ли и Ю [3]. Идея — описать областидоступа к массиву с помощью неравенств на каждую из индексных переменных. Предлагаются две структуры для хранения этих данных:– Атом хранит информацию о ссылке на массив, получаемую из самойссылки. Это двумерный массив, в котором строки соответствуют индексным размерностям массива, а столбцы строки — коэффициентампри индексных переменных в выражении, используемом для доступа кмассиву. Нулевой столбец содержит константу — инвариант цикла.Также с каждым рядом ассоциируется флаг, который отвечает за линейность размерности.– Атомное изображение аналогично атому, но содержит также информацию о пределах изменения индексных переменных.
Эта информациядописывается в конец массива: после k рядов атома (где k — количество объемлющих циклов), идёт ряд k + 1, в котором находится линейноевыражение, отвечающее за верхнюю границу изменения переменной 1,Идрисов Р. И. Методы межпроцедурного анализа51аналогично для k + i. Все циклы предполагаются нормализованными,начинающимися с 1.Этим методом точно описываются области доступа к массиву, потомучто границы получаются напрямую из границ изменения индексных переменных объемлющих циклов. Главный недостаток такого алгоритма в том,что невозможно получить объединение двух областей.
В этом заключаетсяпринципиальное отличие от метода 2.3.1.1 Регулярных секций.2.3.2.2. Линеаризация (Linearization)Этот подход предложен Бурке и Сайтроном [13] (Burke, Cytron). В методе память рассматривается как одномерный массив, и все ссылки на массивы преобразуются в ссылки на память. При слиянии двух областей можно огрублять результат, предполагая, что результирующая область полностью занимает всё пространство между дальними границами областей массивов, но тогда метод становится неточным. Автоматически решаются некоторые проблемы анализа совмещений (Aliasing), но серьёзный недостаток этого метода в том, что требуется хранить большое количество неравенств для каждого из массивов, вследствие чего скорость проверки на зависимость понижается.
При построении объединения участки одной области просто дописываются к участкам другой, а при построении пересечениянужно проанализировать m1 * m2 комбинаций, где m — количество участков, используемое для описания области.2.3.2.3. Межпроцедурный Омега-тест (Interprocedural Omega-test)Рассмотрим следующий пример:For i=1 to 100 doa[i,i]=a[50,i];для того, чтобы показать, что области, используемые в качестве левого иправого значения присвоения пересекаются; достаточно найти целочисленное решение системы уравненийi=i50=iВ данном примере сразу же видно, что система имеет решение приi = 50, что лежит в диапазоне изменения индексной переменной.
Проблемазаключается в том, что целочисленное решение произвольной системыуравнений является np-полной задачей.Метод, предложенный Тангом (Tang) заключается в том, что все границы и шаги циклов записываются в виде системы уравнений и неравенств.Для построения пересечения областей используется целочисленный метод,52Методы и инструменты конструирования программявляющийся расширением метода исключения переменных Фурье—Моцкина [14]. Этот алгоритм имеет экспоненциальную сложность в худшем случае, но тесты показывают, что его можно использовать в реальныхкомпиляторах и для большинства задач время его работы полиноминально[15].2.3.3.