А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 161
Текст из файла (страница 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 Естественные циклы Циклы в исходной программе могут определяться различными способами: они могут быть созданы как циклы Гог, вЫ!е или гереаг; они могут даже быть определены с использованием меток и инструкций кого.
С точки зрения анализа программ не имеет значения, как именно выглядят циклы в исходном тексте программы. Имеет значение только то, обладают ли они свойствами, допускающими простую их оптимизацию. В частности, нас интересует, имеется ли у цикла одна точка входа. Если это так, то компилятор в ходе анализа может предполагать выполнение некоторых начальных условий в начале каждой итерации цикла. Эта возможность служит причиной определения "естественного цикла". Такие пиклы обладают двумя важными свойствами. !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
