А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 166
Текст из файла (страница 166)
9.51. Вычисление передаточных функций для графа потока на рнс. 9.48, а с исполь- зованием анализа, основанного на областях выполнение тела цикла 0 или более Раз, — ~к' и,в .. множество Яеп пРедставлЯет собой (д4, с[5, с[6), а множество Ы[ — пустое. Из области Вт имеется два выхода— базовые блоки Вз и В4. Таким образом, для получения соответствуюсцих передаточных функций Вт следует вычислить композиции упомянутой передаточной функции с каждой из передаточных функций В6.
Обратите внимание, например, что с[6 находитсЯ в множестве 8еп фУнкции Уйт сит(вз] из-за наличиЯ пУтей наподобие Вз -" В4 — Вз — Вз или даже Вз — Вз — В4 Вз — Вз. Наконец, рассмотрим Ва, граф потока, целиком. Его подобластями являются В1, Вт и В5, которые мы будем рассматривать в топологическом порядке.
Как и ранее, передаточная функция Дй,з (1?,] представляет собой просто тождественную функцию, а передаточная функция 1йб сит(в,[ представляет собой просто 1Й, сит(в,[, котоРаЯ, в свою очеРедь, ЯвлЯетсЯ гв,. Заголовок Вт, представляющий собой В2, имеет единственного предшественника, В1, так что передаточная функция к его входу представляет собой просто передаточную функцию на выходе из В1 в области Вз. Для получения соответствУюн?их пеРедаточных фУнкций в Вз мы вычислЯем композиции [й сит(вз] 816 с передаточными функциями к выходам Вз и В4 в Л7. Последней рассмотрим область Лб. Ее заголовок Вб имеет два предшественника в Лб, а именно — Вз и В4.
СлеДовательно, ДлЯ полУчениЯ 1'л, вв1п,1 наДо вычислить ~ив 6671п,) Л )и, с„т1Щ). Поскольку передаточная функция базового блока Вб представляет собой тождественнУю фУнкцию, Гп, ост)п,) = ~л,з )п,р На шаге 3 вычисляются действительные достигающие определения на основе передаточных функций. На шаге 3, а пч [Лб] = Я, поскольку в начале программы достигающие определения отсутствуют. На рис. 9.52 показано, как на шаге 3, б вычисляются оставшиеся значения потока данных. Этот шаг начинается с подобласти Лб. Поскольку передаточные функции от начала Лб к началу каждой подобласти уже вычислены, значение потока данных в начале каждой подобласти получается путем однократного применения передаточной функции.
Мы повторяем эти шаги до тех пор, пока не получим значения потока данных для каждой области-листа, которые представляют собой отдельные базовые блоки. Заметим, что значения потока данных, показанные на рис. 9.52, в точности те же, которые мы получили бы при применении итеративного анализа потока данных к тому же графу потока, как, естественно, н должно быть. о айвза)лт) (пч [Л81) 7 Е1438)лт) (и" [Лб]) Л~в,!м[лв) (П1 [Л8]) УЛ7381пв) [ПЧ [Л7]) Упвза~п,) (ПЧ [Лб]) Ув.з.)л,) (пч [Лб]) Уп,, )л,) [пч[Л6]) (в111Вв2|ввз) (Вв2) 1~3~ 1~41115~ Ввб) ( 1~1 ~ 112 ~ 6131 вв4 ~ вв5 в ввб) (вв2: В"3~ Гв4~ 415 Ввб) (112~ ввз~ <14~ <"5 116) (вв1 ~ вв2~ ввз: 414~ г15~ об) Рис.
9.52, Последние шаги анализа потока на основании областей 9.7.6 Обработка неприводимых графов потоков Если ожидается, что в программе, обрабатываемой компилятором илн другим специализированным инструментарием, неприводимые графы потоков будут распространенным явлением, то мы рекомендуем использовать итеративный подход вместо анализа, основанного на иерархии. Однако если требуется быть готовым только к редким неприводимым графам, то в этом случае вполне адекватен метод "расщепления узлов". Если граф потока неприводим, мы обнаружим, что получающийся в результате граф областей содержит циклы, но не имеет обратных ребер, так что дальнейший пч [Лб] = пч [Л1] = йч [Л7! = пч [Л5] = 1"1[Л6] = пя [Л4] = пч[Лз! = пч [Л2] = Глава 9.
Машинно-независимые оптимизации 817 9.7. Анализ на основе областей разбор этого графа невозможен. Типичная ситуация показана на рис. 9.53, и, где граф имеет ту же структуру, что и граф на рис. 9.45, хотя узлы на рис. 9.53 в действительности являются сложными областями (что видно из наличия внутри них узлов меньшего размера). ' © б) а) Рнс. 9.53. Дублирование области делает непрнводнмый граф приводимым Мы выбираем некоторую область Л, у которой более одного предшественника и которая не является заголовком всего графа потока. Если у Л имеется й предшественников, создаем Й копий всего графа Л и соединяем каждого предшественника заголовка Л со своей копией графа Л.
Вспомните, что иметь предшественника вне области может только заголовок области. Оказывается, хотя мы и не будем доказывать этот факт, что такое расщепление узлов приводит после идентификации новых обратных ребер и построения их областей к снижению количества областей как минимум на единицу. Получающийся граф может остаться неприводимым, но чередование фаз расщепления с фазами обнаружения и свертывания в области естественных циклов в конечном итоге дает одну область, т.е, граф потока оказывается приведенным.
Пример 9.5!. Расщепление, показанное на рис. 9.53, б, превращает ребро Лзь -" Лз в обратное ребро, поскольку Лз теперь доминирует над Лзь Эти две области можно скомбинировать в одну область тела. Таким образом, мы приводим весыраф к одной области. В общем случае могут потребоваться дополнительные расщепления, а в наихудшем случае общее количество базовых блоков может экспоненциально зависеть от количества блоков в исходном графе потока. о 818 Глава 9.
Машинно-независимые оптимизации Следует также подумать и о том, как результат анализа потока данных в расщепленном графе потока соотносится с интересующим нас ответом для исходного графа потока. Существует два подхода. 1. Расщепление областей может благотворно сказаться на процессе оптимизации, и мы можем просто изменить граф потока так, чтобы он имел копии некоторых блоков.
Поскольку в каждый дублированный блок можно попасть только по некоторому подмножеству путей, достигающих оригинала, значения потока данных в этих дублированных блоках будут, вообще говоря, содержать более специализированную информацию по сравнению с доступной в оригинале. Например, каждого дублированного блока может достигать меньшее количество определений, чем количество определений, достигающих исходного блока. 2.
Если мы хотим сохранить исходный граф потока, без расщепления, то после анализа расщепленного графа потока мы рассматриваем каждый расщепленный блок В и соответствующее ему множество блоков Вы Вз,..., Вь. Можно вычислить нч[В] = пч[Вг] л пч[Вз] л л пч[Вь]; значения опт вычисляются аналогично. 9.7.7 Упражнения к разделу 9.7 Упражнение 9.7.1. Для графа потока на рис. 9.10 1см. упражнения к разделу 9.1) выполните следующее. а) Найдите все возможные области. Области, состоящие из единственного узла и без ребер, можно не учитывать.
б) Найдите множество вложенных областей, построенное алгоритмом 9.52. в) Выполните приведение графа потока при помощи преобразований Т1 и Тз, описанных во врезке "Происхождение термина «приводимость»" в разделе 9.7.2. Упражнение 9.7.2. Повторите упражнение 9.7.! для следующих графов потоков. а) Граф на рис. 9.3. б) Граф на рис. 8.9. в) Созданный вами граф из упражнения 8.4.1. г) Созданный вами граф нз упражнения 8.4.2. Упражнение 9.7.3. Докажите, что каждый естественный цикл является областью. 819 9.8.
Символический анализ !! Упражнение 9.7.4. Покажите, что граф потока приводим тогда и только тогда, когда он может быть преобразован в единственный узел с использованием а) операций Т1 и Тз, описанных во врезке "Происхождение термина «приводимость»" в разделе 9.7.2; б) определения области, введенного в разделе 9.7.2. ! Упражнение 9.7.5. Покажите, что выполнение расщепления узлов к неприводимому графу потока с последующим применением приведения Т! — Тз к получившемуся расщепленному графу дает строго меньшее количество узлов, чем было до выполнения указанных действий. ! Упражнение 9.7.6.
Что произойдет, если для приведения полного ориентированного графа поочередно применять расщепление узлов и приведение Т, — Тз? 9.8 Символический анализ В этом разделе мы используем символический анализ для иллюстрации использования анализа на основе областей.
В этом анализе мы символически отсле- живаем значения переменных программы как выражения от входных переменных и других переменных, которые мы назовем ссылочными переменными (геГегепсе чапаЫез). Выражение переменных через одно и то же множество ссылочных переменных выявляет их взаимоотношения. Символический анализ может использоваться для разных целей, таких как оптимизация, распараллеливание и анализ для понимания программы. Пример 9.52.
Рассмотрим простой пример программы на рис. 9.54. Здесь х используется как единственная ссылочная переменная. Символический анализ обнаруживает, что у имеет значение х — 1, а з — значение х — 2 после соответствующих присваиваний в строках 2 и 3. Эта информация полезна, например, при выяснении, выполняют ли инструкции в строках 4 и 5 запись в разные ячейки памяти !и, таким образом, могут ли они выполняться параллельно). Кроме того, можно утверждать, что условие г ) х никогда не будет истинным, что позволяет оптимизатору удалить условную инструкцию из строк 6 и 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
