Главная » Просмотр файлов » А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий

А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 154

Файл №1114947 А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий) 154 страницаА.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947) страница 1542019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 154)

Максимальная фиксированная точка и реп!ение сбором по путям Заметим, что в мог-решении в случае наличия циклов коли ьество рассматриваемых путей остается неограниченным. Таким образом, мог-определение само по себе не приводит к алгоритму. Итеративный алгоритм не должен начинаться с поиска всех путей, ведущих к базовому блоку, перед тем как применять оператор сбора. Вместо этого 1. итеративный алгоритм посещает базовые блоки нс обязательно в порядке их выполнения; 2. в каждой точке слияния алгоритм применяет оператор сбора к значениям потока данных„ полученным к этому моменту; нскоторые из этих значе- 758 Глава 9.

Машинно-независимые оптимизации ний бьши искусственно введены при инициализации, а не представляют результат выполнения программы от начала к рассматриваемой точке. Так как же соотносятся решение сбором по путям и решение, получаемое алгоритмом 9.21? Начнем рассмотрение с порядка обхода узлов. В пределах итерации мы можем посетить базовый блок до посещения его предшественников. Если таковым предшественником является входной узел, опт [Вход] инициализирован корректным константным значением.

Остальные узлы инициализированы значением Т, не меньшим, чем окончательный ответ. Монотонность обеспечивает при использовании Т в качестве входных данных получение результата, не меньшего, чем искомое решение. В этом смысле можно говорить о Т как о не представляющем никакой информации. Вг Рнс. 9.24. Граф потока, иллюстрирующий влияние раннего сбора по путям В чем выражается ранее применение оператора сбора? Рассмотрим простой пример, показанный на рис.

9.24, и предположим, что интересующее нас значение — п4 [В4]. В соответствии с определением мОР [В4] = ((~Вх,Ь ) ЦВ Л~г))(СВХОД) В итеративном алгоритме при посещении узлов в порядке Вы Вз, Вз, В4 Р1 [В4] = 1Вз (УВг (ггвход) Л ДВд (ггвход))) В то время как оператор сбора применяется в конце мор-определения, итеративный алгоритм применяет его раньше. Ответ при этом получается одинаковым, только если структура потока данных дистрибутивна. Если структура потока данных монотонна, но не дистрибутивна, то пч [В4] ( мор [В4].

Вспомним, что в общем случае решение пч [В] безопасно (консервативно), если для всех базовых блоков В пч[В] ( пзвм.(В]. 759 9.3. Основы анализа потока данных Представим набросок доказательства того, что в общем случае решение максимальной фиксированной точки, получаемое итеративным алгоритмом, всегда безопасно. Простая индукция по 1 показывает, что значения, полученные после ! итераций, не превосходят результата сбора по всем путям длиной ! и менее. Однако итеративный алгоритм завершается, только если он достигает того же ответа, что и при неограниченном количестве итераций, Таким образом, результат оказывается не большим, чем мог-решение. Поскольку мог < !пеА~., а мн' < мог, мы получаем мгг < !пиль, а следовательно, решение максимальной фиксированной точки, получаемое при использовании итеративного алгоритма, является безопасным.

9.3.5 Упражнения к разделу 9.3 Упражнение 9.3.1. Постройте диаграмму решетки для произведения трех решеток, каждая из которых основана на одном определении 4, 1 = 1, 2,3. Как ваша диаграмма соотносится с диаграммой на рис. 9.22? ! Упражнение 9.3.2. В разделе 9.3.3 мы доказали, что если структура имеет конечную высоту, то итеративный алгоритм сходится. Далее приведен пример, в котором структура не имеет конечной высоты и итеративный алгоритм не является сходящимся.

Множество значений $' представляет собой неотрицательные целые числа, а оператор сбора — минимум. Имеется три передаточные функции, а именно 1. тождественность ~г(х) = х; 2. "половина" 1п (х) = х,12; 3. "единица" 1о(х) = 1. Множество передаточных функций Г состоит из трех указанных функций н всевозможных их композиций. а) Опишите множество Е. б) Что собой представляет отношение < в данной схеме? в) Приведите пример графа потока с присоединенными передаточными функциями, для которого алгоритм 9.2! не сходится. г) Является ли данная структура монотонной, дистрибутивной? ! Упражнение 9.3.3. Мы доказали, что алгоритм 9.2! сходится, если структура монотонна и имеет конечную высоту.

Вот пример структуры, иллюстрирующей важность монотонности (конечности высоты оказывается недостаточно). Область 760 Глава 9. Машинно-независимые оптимизации определения 1' = (1, 2), оператор сбора — минимум, а множество функций Е состоит из тождественной функции ©) и функции "переключения" (,1з (х) = 3 — з), которая меняет 1 на 2 и наоборот.

а) Покажите, что эта структура имеет конечную высоту, но не монотонна. б) Приведите пример графа потока и назначения передаточных функций, такой, что алгоритм 9.21 не сходится. ! Упражнение 9.3.4. Пусть мог, [В] — сбор по всем путям длиной 1 или менее от входа до базового блока В. Докажите, что после 1 итераций алгоритма 9.21 пч [В] ( мог; [В].

Покажите также как следствие, что если алгоритм 9.21 сходится, то он сходится к результату, который не превышает (в смысле отношения () могрешение. ! Упражнение 9.3.5. Предположим, что множество функций Е структуры содержит только функции вида дел-)гй, т.е. область определения $' является показательным множеством некоторого множества, а Г" (х) = С О (х — К) для некоторых множеств С и К.

Докажите, что если оператор сбора представляет собой а) объединение или б) пересечение, то описанная структура дистрибутивна. 9.4 Распространение констант Все рассматривавшиеся в разделе 9.2 схемы в действительности представляют собой простые примеры дистрибутивных структур с конечной высотой. Таким образом, применение к ним итеративного алгоритма 9.21 как в прямом, так и в обратном направлениях, приводит в каждом случае к мог-решению. В этом разделе мы поближе познакомимся с полезной структурой потока данных, обладаюшей более интересными свойствами. Вспомним, что распространение констант (сопззап1 ргорадайоп), или "дублирование констант" (сопз1аШ то!йцд), заменяет выражения, которые при выполнении всякий раз вычисляют одну и ту же константу, самой этой константой.

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

9.4. Распространение констант 9.4.1 Значения потока данных для структуры распространения констант Множество значений потока данных представляет собой решетку произведения, в которой имеется по одному компоненту для каждой переменной программы. В решетку для единственной переменной входит следующее. !. Все константы подходяшего для данной переменной типа.

2. Значение мАС, означающее "не константу" (попа-сопвшпс). Переменная отображается на это значение, если выясняется, что она не имеет константного значения. Это может происходить потому, что переменной может быть присвоено входное значение либо она может быть вычислена из переменной, не являющейся константой, а также на разных путях, приводящих к одной и той же точке программы, ей могут присваиваться разные константы. 3.

Значение глчпег, которое означает "не определена" (илдебпед). Переменная получает это значение, если пока что о ней ничего нельзя утверждать наверняка; вероятно, пока что не найдено определение, достигающее рассматриваемой точки. Заметим, что мАс и 0хпее — это не одно и то же, это сушественно разные вещи. млс говорит о том, что имеется много путей определения переменной, так что мы знаем, что она не может быть константой; 1дЧПЕР же говорит о том, что мы знаем о переменной слишком мало, чтобы считать ее чем бы то ни было. Полурешетка для типичной целочисленной переменной показана на рис. 9.25.

Характеристики

Список файлов книги

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