А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 149
Текст из файла (страница 149)
К тому моменту, когда на первой итерации мы выяснили, что да достигает конца В4, значения )м [Вз] и опт [Вз] были уже вычислены. 733 9.2. Введение в анализ потоков данных После второй итерации никаких изменений в опт не вносится, так что после третьего прохода алгоритм завершает свою работу, оставляя 1м и опт такими, какими они показаны в последних двух столбцах на рис.
9.15. а 9.2.5 Анализ активных переменных Некоторые улучшающие код преобразования зависят от информации, вычисляемой в направлении, противоположном потоку управления программы; один такой пример мы сейчас и рассмотрим. В анализе активных переменнык (11чезапайе апа!уз(з) для переменной х и точки р мы хотим выяснить, может ли значение х из точки р использоваться вдоль некоторого пути в графе потока, начинающемся в точке р. Если может, то мы говорим, что переменная х акгпивна (жива) в точке р, если нет — неакеивна (мертва). Важное применение анализа активных переменных — при распределении регистров для базовых блоков. Этот вопрос уже поднимался в разделах 8.6 и 8,8, После того как значение вычислено в регистр и будет использоваться в блоке, его не обязательно сохранять в памяти, если это значение будет мертвым на выходе из блока. Если все регистры заняты, а нам нужен свободный регистр, то, в первую очередь, используются регистры с мертвыми значениями, поскольку эти значения не надо сохранять.
Мы определим уравнения потока данных непосредственно в терминах пч[В] и опт[В[, которые представляют собой множества активных переменных в точках непосредственно перед блоком В и после него соответственно. Эти уравнения могут быть также выведены путем определения передаточных функций для отдельных инструкций с последующей их композицией для получения передаточной функции блока в целом. Определим 1, в(е~н — множество переменных, определенных (те. получающих значения) в блоке В до любых их использований в этом блоке; 2.
ивен — множество переменных, значения которых могут использоваться в блоке В до любых определений этих переменных. Пример 9.13. Например, блок Вз на рис. 9.13 использует(. Он также использует з до переопределения этой переменной, если только ( и з не являются псевдонимами друг друга. В предположении, что среди переменных на рис. 9.13 псевдонимов нет, ивен, = ((,Д. Кроме того, блок Вз определяет( и з. В том же предположении отсутствия псевдонимов Ые(н, —— (г, Я. о Как следствие этих определений любая переменная в ивен должна рассматриваться как активная на входе в блок В, в то время как переменные из Ые)н в начале блока В мертвы.
734 Глава 9. Машинно-независимые оптимизации Значит, уравнения, связывающие ЫеГ и изе с неизвестными ~м и опт, определяются следующим образом: пч [Вход] = а И для всех базовых блоков В, отличных от выходного, пч [В] = изен 0 (опт [В] — ЙеЯ оит[В] = Ц пч[Я] Первое уравнение определяет граничное условие, состоящее в том, что активных переменных при выходе из программы нет. Второе уравнение гласит, что переменная является активной при входе в блок, если она используется в блоке до переопределения или если она активна на выходе из блока и не переопределена в нем.
Третье уравнение говорит о том, что переменная активна при выходе из блока тогда и только тогда, когда она активна при входе по крайней мере в один из блоков-преемников. Сравнивая соотношения между уравнениями для активных переменных и для достигающих определений, можно заметить следующее. ° Оба множества используют объединение в качестве оператора сбора. Причина этого в том, что в каждой схеме потока данных мы распространяем информацию вдоль путей и нас интересует ситуация, когда существует хотя бы один путь с требуемым свойством, а не когда таким свойством обладают все пути.
° Однако поток информации в случае активных переменных идет "назад", обратно направлению потока управления, поскольку в этой задаче мы хотим убедиться, что использование переменной х в точке р передается всем точкам, предшествующим р вдоль путей выполнения, так что об использовании х становится известно в предшествующих точках, до ее использования. Для решения задачи в обратном направлении вместо опт [Вход] мы инициализируем ПЧ [ВЫХОд]. Множества ПЧ и Опт меняются ролями, а изе и ЫеГ заменяют соответственно яеп и /аП. Как и в случае достигающих определений решение уравнений для активных переменных не обязательно единственное, и мы хотим найти решение с наименьшим множеством активных переменных. Использующийся для этого алгоритм, по сути, представляет развернутую в обратном направлении версию алгоритма 9.11.
Алгоритм 9.14. Анализ активных переменных Вход: граф потока с множествами Ые1' и изе, вычисленными для каждого базового блока. 9.2. Введение в анализ потоков данных 735 Выход: множества переменных, активных на входе (бч [В)) и выходе (опт [В)) каждого блока В графа потока.
Метод: выполнить программу, приведенную на рис. 9.16. о !н [Выход[ = а; !ог (каждый базовый блок В, отличный от выходного) !н [В[ = о; зк!з!1е (Внесены изменения в пч) !ог !каждый базовый блок В, отличный от выходного) 1 оот[В) =[) „„„,„„,, !н[В1; !н [В) = изен О (опт [В) — йемен ); Рис. 9.16, Итеративный алгоритм лля вычисления активных переменных 9.2.6 Доступные выражения Выражение л + у доступно (ака1!аЫе) в точке р, если любой путь от входного узла к р вычисляет х + у и после последнего такого вычисления до достижения р иет последующих присваиваний переменным х и уз.
Когда речь идет о доступных выражениях, мы говорим, что блок уничтожает выражение ж+ у, если он присваивает !или может присваивать) х и у и после этого не вычисляет х + у заново. Блок генерируепз выражение х + у, если он вычисляет х + у и не выполняет последующих переопределений х и у. Заметим, что понятия "уничтожения" и "генерации" доступного выражения не те же, что в случае достигающих определений. Несмотря на это понятия "уничтожение" и "генерация" ведут себя, по сути, так же, как и уничтожение, и генерация для достигающих определений.
Основное применение информации о доступных выражениях — поиск глобальных общих подвыражений. Например, на рис. 9.17, а выражение 4 * з в блоке Вз будет общим подвыражением, если 4 * з доступно во входной точке блока Вз. Это выражение будет доступно, если з не будет присвоено новое значение в блоке Вз или если 4 * ! будет заново вычислено после такого присвоения в блоке Вз, как показано на рис. 9.17, б. Можно вычислить множество генерируемых выражений для каждой точки блока, проходя от начала до конца блока. В точке, предшествующей блоку, сгенерированных выражений нет. Если в точке р доступно множество выражений Я, а д представляет собой точку после р с инструкцией х = у+а между ними, то мы образуем множество доступных в д выражений следующим образом.
'Как обычно в этой главе, оператор ь означает обобпзепный оператор, пе обязательно оператор сложения. 736 Глава 9. Машинно-независимые оптимизации В, В, б) а) Рис. 9.17. Потенциальные общие подвыражения, пересекающие границы блоков 1. Добавляем к 5 выражение у + ж 2. Удаляем из Ь' все выражения, включающие переменную х. Заметим, что описанные действия должны выполняться в указанном порядке, так как к может совпадать с у или ж После того как мы достигнем конца блока, Я будет представлять собой множество сгенерированных выражений блока.
Множество уничтоженных выражений представляет собой множество всех выражений, скажем, у+ г, таких, что у или гопределяется в блоке, и при этом у+ г блоком не генерируется. Пример 9.15. Рассмотрим четыре инструкции, показанные на рис. 9.18. После первой инструкции доступно выражение 6+ с, после второй становится доступным выражение а — д, но 6+ с более недоступно, поскольку при этом переопределяется 6. Третья инструкция не делает 6+ с доступным, поскольку в ней переопределяется с.
После последней инструкции в связи с тем, что она изменяет д, становится недоступным и и — г1. Итак, здесь не генерируется ни одно доступное выражение и при этом уничтожаются все выражения, включающие а, 6, с или г1.а Мы можем найти доступные выражения методом, напоминающим метод вычисления достигающих определений. Предположим, что 11 — "универсальное" множество всех выражений, появляющихся в правой части одной или нескольких инструкций программы. Пусть для каждого блока В множество 1)ч [В~ содержит выражения из 11, доступные в точке непосредственно перед началом блока В, а 0))т )В] — такое же множество для точки, следующей за концом блока В. Определим е яелн как множество выражений, генерируемых В, а е Ййн — как множество выражений из 17, уничтожаемых в В. Заметим, что множества лч, 01)т, еяел и е lаЫ могут быть представлены в виде битовых векторов.
Неизвестные множе- 737 9.2. Введение в анализ потоков данных ИнстРУкциЯ ДОстУпныр ныРАжпниЯ а =Ь + с (6+ с! !а — г1,! !а — с!! Ь=а с=Ь Рис. 9.! 8. Вычисление доступных выражений ства !н и оцт связаны друг с другом и с известными е дел и е !р!!! следующими соотношениями: ОНТ !ВХОД1 — — З и для всех базовых блоков !3, отличных от входного, опт !!!~ == е яепн ! ! ПН~В1 — е й!!!и) пч )В! =- Опт !Р] .=-й, Р— ярелжсмвеяник П Приведенные выше уравнения выглядят почти идентичными уравнениям для достигающих определений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
