Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Методы межпроцедурного анализа. Идрисов

Методы межпроцедурного анализа. Идрисов, страница 3

PDF-файл Методы межпроцедурного анализа. Идрисов, страница 3 Конструирование компиляторов (52975): Статья - 7 семестрМетоды межпроцедурного анализа. Идрисов: Конструирование компиляторов - PDF, страница 3 (52975) - СтудИзба2019-09-18СтудИзба

Описание файла

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.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее