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

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

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

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

Остальная работа алгоритма приведена на рис. 9.44. о 9.6.3 Ребра в глубинном оетовном дереве При построении Рг 8Т для графа потока ребра графа потока можно разделить на три категории. 793 9.6. Циклы в графах потоков Вызов хеагсЬ (1) Узел 1 имеет два преемника. Предположим, что сначала рассматривается я = 3; добавляем ребро 1 — 3 в Т. Добавляем ребро 3 — 4 в Т. Узел 4 имеет два преемника. Предположим, что сначала рассматривается а = 6; добавляем ребро 4 — 6 в Т. Добавляем ребро 6 — 7 в Т.

Узел 7 имеет два преемника, 4 и 8. Но узел 4 уже мар- кирован как "посещен" вызовом юеагсЬ (4), так что для в = 4 никаких действий не выполняется. Для в = 8 до- бавляем ребро 7 — 8 в Т. Узел 8 имеет два преемника, 9 и 10. Предположим, что сначала рассматривается е = 10; добавляем ребро 8 — 10 вТ. 10 имеет преемника — узел 7, но 7 уже помечен как "посещен".

Таким образом, юеагсЬ (10) завершает работу установками г(гл [10] = 10 и с =- 9. Устанавливаем я = 9 и добавляем ребро 8 — 9 в Т. Единственным преемником 9 является уже посещенный узел 1, так что устанавливаем фл [9] = 9 и с = 8. Последним преемником 8 является посешенный узел 3, так что для е = 3 не выполняем никаких действий. В этот момент все преемники 8 рассмотрены, так что устанав- ливаем грй [8] = 8 и с = 7. Все преемники 7 рассмотрены, так что устанавливаем оп[7] =7ис=б. Аналогично все преемники б рассмотрены, так что уста- навливаем г(Тл [6] = 6 и с = 5.

Преемник 3 узла 4 был посещен, но 5 — еше нет, так что добавляем в дерево ребро 4 — 5. Преемник 7 узла 5 был посещен, так что устанавливаем оп[5] =5ис=4. Все преемники 4 рассмотрены; устанавливаем атп [4] = 4 и с = 3. Устанавливаем сЦл [3] = 3 и с = 2.

Узел 2 еще не был посещен, так что добавляем ребро 1- 2вТ. Устанавливаем а7Ь [2] = 2 и с = 1. Устанавливаем фл [1] = 1 и с = О. Вызов юеагсЬ (3) Вызов юеагсЬ (4) Вызов хеагсЬ (6) Вызов юеагсЬ (7) Вызов хеагсЬ (8) Вызов юеагсЬ (10) Возврат в хеагсЬ (8) Вызов юеагсЬ (9) Возврат в хеагсЬ (8) Возврат в юеагсЬ (7) Возврат в хеагсЬ (6) Возврат в юеагсЬ (4) Вызов яеагсЬ (5) Возврат в хеагсЬ (4) Возврат в юеагсЬ (3) Возврат в юеагсЬ (1) Вызов хеагсЬ (2) Возврат в юеагсЬ (1) Рис. 9.44. Выполнение алгоритма 9.37 для графа потока на рис. 9.42 794 Глава 9.

Машинно-независимые оптимизации 1. Ребра, именуемые наступающими (адчапс)пб), идут от узла т к истинным преемникам т в дереве. Все ребра в РЕ8Т являются наступающими. Других наступающих ребер на рис. 9.42 нет, но, например, если бы имелось ребро 4 — 8, то оно также попадало бы в эту категорию. 2. Ребра, идущие от узла т к предку пт в дереве (возможно, к самому т). Эти ребра называются отступающими (ге1геабпб). Например, на рис. 9.42 отступаюшими ребрами являются 4- 3, 7- 4, 10- 7, 8- 3 и 9- 1. 3.

Ребра т — кн такие, что ни т, ни и не являются предками друг друга. На рис. 9.42 такими ребрами являются только ребра 2 — 3 и 5 — 7. Такие ребра называются поперечными (сгока). Важным свойством поперечных ребер является то, что если изобразить РЕ8Т так, чтобы дочерние узлы некоторого узла располагались слева направо в порядке, в котором они добавлялись в дерево, то все поперечные ребра будут идти справа налево. Следует заметить, что т — п является отступающим ребром тогда и только тогда, когда оп [т] > оп [и]. Чтобы понять, почему это так, заметим, что если т является потомком п в РЕ8Т, то зеагсЬ (т) завершается раньше .геагсл (и), так что 4л [т] > 4п [и].

И наоборот, если г~~л [т] > г1Гл (и], то зеагсЬ (гп) завершается до кеагсй (и), или т = п. Но вызов зеагся (и) должен начинаться до зеагс)» (гп), если существует ребро т — п, иначе тот факт, что и является преемником т, должен сделать п потомком т в РЕ8Т. Таким образом, время активности зеагсЬ(т) представляет собой подынтервал времени активности зеагсЬ (п), откуда следует, что п является предком т в РгЯТ. 9.б.4 Обратные ребра и приводимость Обратным ребром (Ьас)г едце) называется ребро а — » 6, у котороп» б доминирует над а.

Для любого графа потока каждое обратное ребро является отступающим, но не всякое отступающее ребро является обратным. Граф потока называется приводимым (гебпс)Ые), если все его отступающие ребра в любом РЕ8Т являются обратными.

Другими словами, если граф приводим, то все его РЕ8Т имеют одно и то же множество отступающих ребер, в точности совпадающее с множеством обратных ребер. Если граф неприводим (лолгедис1Ые), то все обратные ребра в любом РЕБТ являются отступающими, но каждое РЕ8Т имеет дополнительные отступающие ребра, не являющиеся обратными. Эти отступающие ребра могут различаться у разных РЕ8Т. Таким образом, если удалить все обратные ребра графа потока и оставшийся граф при этом будет цикличен, то такой граф неприводим, и наоборот. Графы потоков, встречающиеся на практике, почти всегда приводимы, Прг использовании только структурированных инструкций потока управления, таки» 795 9.6.

Циклы в графах потоков Почему обратные ребра являются отступающими Предположим, что а — Ь вЂ” обратное ребро„т.е. его заголовок доминирует над хвостом. Последовательность вызовов функции зеагсл на рис. 9.43, приводящая к узлу а, должна быть путем в графе потока. Этот путь, конечно, должен включать все доминаторы а.

Отсюда следует, что вызов зеагсл (6) должен быть открыт, когда вызывается зеа«сл (а). Следовательно, Ь уже находится в дереве, когда в него добавляется а, и а добавляется как потомок Ь. Следовательно, а — 6 должно быть отступающим ребром. как 1тмЬеп-е!яе, иЬ11е-до, соп!шие и Ьгеа1с, получаются программы, графы потоков которых всегда приводимы. Даже программы, написанные с использованием инструкции йо1о, зачастую можно сделать приводимыми, если программист логически мыслит в терминах циклов и ветвлений. Пример 9.39. Граф потока на рис.

9.38 приводим. Все отступающие ребра в графе являются обратными, т.е. их заголовки доминируют над их хвостами. и Пример 9.40. Рассмотрим граф потока на рис. 9.45, начальный узел которого— 1. Узел 1 доминирует над узлами 2 и 3, но ни 2 не доминирует над 3, ни 3 над 2. Таким образом, этот граф потока не имеет обратных ребер, поскольку ни у одного ребра заголовок не доминирует над хвостом. Для данного графа потока существует два возможных глубинных остовных дерева, в зависимости от того, будет первой из хеагсл (1) вызвана процедура зеагсл (2) или зеагсл (3). В первом случае ребро 3 — 2 является отступающим, но не обратным; во втором таковым является ребро 2- 3. Интуитивно причина неприводимости данного графа потока в том, что в цикл 2-3 можно войти в двух разных местах — через узлы 2 и 3.

а Рис. 9.45. Канонический неприводимый граф потока 9.6.5 Глубина графа потока Для данного глубинного остовного дерева вглубь дерева графа глубина (дер1Ь) представляет собой наибольшее количество отступающих ребер на любом ацикличном пути. Можно доказать, что глубина никогда не превышает того, что можно 79б Глава 9.

Машинно-независимые оптимизации интуитивно назвать глубиной вложенности циклов графа потока. Если граф потока приводим, мы можем заменить в определении глубины "отступающие*' на "обратные", поскольку отступающие ребра любого !ЭРОТ являются обратными. Понятие глубины при этом становится независимым от реально выбранного РЕЯТ, и можно говорить о "глубине графа потока", а не о глубине графа потока в связи с одним из его глубинных остовных деревьев. Пример 9.41.

На рис. 9.42 глубина равна 3, поскольку существует путь 10 — 7 — 4- 3 с тремя отступающими ребрами, но нет ацикличного пути с четырьмя или более отступающими ребрами. То, что "глубочайший*' путь содержит только отступающие ребра, — не более чем случайное совпадение; в общем случае на наиболее глубоком пути у нас может быть смесь отступающих, наступающих и поперечных ребер. и 9.6.6 Естественные циклы Циклы в исходной программе могут определяться различными способами: они могут быть созданы как циклы Гог, вЫ!е или гереаг; они могут даже быть определены с использованием меток и инструкций кого.

С точки зрения анализа программ не имеет значения, как именно выглядят циклы в исходном тексте программы. Имеет значение только то, обладают ли они свойствами, допускающими простую их оптимизацию. В частности, нас интересует, имеется ли у цикла одна точка входа. Если это так, то компилятор в ходе анализа может предполагать выполнение некоторых начальных условий в начале каждой итерации цикла. Эта возможность служит причиной определения "естественного цикла". Такие пиклы обладают двумя важными свойствами. !.

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

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

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