А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 148
Текст из файла (страница 148)
Предположим, что имеются функции !~ (х) = дел, 0 (х — Ы!1 ) и 1з (х) = адепт О (х — Ы1з). Тогда ~з ( !1 (х)) = 8епз 0 (8еп, О (х — 1пП1 ) — бойз) = = (йелз 0 (Пел, — Ы!з)) 0 (х — (1г1П1 0 1г1Пз)) Это правило распространяется на базовый блок, состоящий из произвольного количества инструкций.
Предположим, что блок В имеет п инструкций, передаточные функции которых 1; = 8еп, 0 (х — lаП;) для 1 = 1, 2,, и. Тогда передаточная функция для базового блока В может быть записана как 1н (х) = 8епн О (* — И1н), где Ы1В = ~Ж ~.~ Ы12 ~-! ' ' ' О Ы1а дели — — дел„0 (дел„1 — Ы1„) 0 (Пел„з — Ы1„~ — 1пП„) ц 0 ' ' ' 0 (8ел1 1г1П2 1пдз — ' ' ' — 1г!П~) Таким образом, базовый блок, как и инструкция, с одной стороны, генерирует множество определений, с другой — уничтожает множество определений. Множество яеп содержит все определения внутри блока, которые "видимы" непосредственно после блока; будем называть их нижнелредставлеиными (доюпюапЬ 729 9.2.
Введение в анализ потоков данных скрозь). Определение нижнепредставлено в базовом блоке только в том случае, если оно не уничтожено последующим определением той же переменной в этом же базовом блоке. Множество /пП базового блока представляет собой простое объединение всех определений, уничтоженных отдельными инструкциями. Обратите внимание, что определение может присутствовать как в множестве яел базового блока, так и в его множестве НП. Если это так, то больший приоритет имеет множество яел, поскольку в форме реп-ЙП множество lаП применяется до множества дел.
Пример 9.10. Множество яел для базового блока Пз: а = 3 сиз. а= 4 представляет собой таз), поскольку Пз не является нижнепредставленным определением. Множество /аП содержит как ~, так и дз, поскольку Пз уничтожает с~э и наоборот. Тем не менее, поскольку вычитание множества /аП предшествует операции объединения с множеством яел, конечная передаточная функция для этого блока будет включать определение Пз.
и Уравнения потока управления Теперь рассмотрим множество ограничений, порождаемых потоком управления между базовыми блоками. Поскольку определение достигает точки программы, если существует по крайней мере один путь, вдоль которого зта точка может быть достигнута, опт [Р] С пч [В] везде, где имеется ребро потока управления от Р к В. Однако, поскольку определение не может достичь точки, если нет пути для ее достижения, пч [В] должно быть не больше, чем объединение достигающих определений всех предшествующих базовых блоков.
Иными словами, можно безопасно считать, что пч [В) = =0 оит [Р] Р— нредшесзвенник В Будем называть объединение оператором сбора (шеес орегасог) для достигающих определений. Этот оператор используется для суммирования вкладов различных путей при их слиянии в любой схеме потока данных. Итеративный алгоритм для достигающих определений Мы считаем, что любой граф потока содержит два пустых блока — входной блок, являющийся стартовой точкой графа, и выходной блок, через который проходят все выходы из графа. Поскольку начала графа не достигают никакие определения, передаточная функция для входного блока представляет собой простую константную функцию, возвращающую О, т.е.
опт [Вход] = ~. Глава 9. Машинно-независимые оптимизации Задача достигающих определений формулируется при помощи следующих уравнений: Оит [Вход) = !2! и для всех базовых блоков В, отличных от входного, Опт[В) = вели О [пч(В] — Ы!1и) Данные уравнения могут быть решены при помощи приведенного ниже алгоритма. В результате работы этого алгоритма получается наименьшая фиксированная точки (1еаз! Йхес1рош!) уравнений, т.е. решение, значения множеств Пя и О!!т которого содержатся в соответствуюгцих значениях любого другого решения этих уравнений.
Этот результат приемлем, поскольку любое определение в одном из множеств пч и Оит, конечно же, должно достигать указанной точки. Это решение корректно, поскольку оно не включает никакие определения, о которых мы точно знаем, что они не являются достигающими. Алгоритм 9.11. Достигающие определения Вход: граф потока, в котором для каждого блока В вычислены множества 1г!1!и и депп. Выход: пч [В] и Оит [В], множества достигающих определений для входа и выхода каждого блока В графа потока. МптОд: мы используем итеративный подход с начальной оценкой Опт[В) = ьэ для всех В, сходящийся к требуемым значениям пч и Опт.
Поскольку итерации должны продолжаться до тех пор, пока не сойдутся множества пч (а следовательно, и О!!т), мы можем использовать логическую переменную сйаще в качестве индикатора, были ли внесены при данном проходе изменения в какое-либо из множеств Ог!т. Однако как в этом, так и в аналогичных алгоритмах, которые будут рассмотрены ниже, мы полагаем, что механизм отслеживания изменений очевиден, и не рассматриваем его. Набросок алгоритма приведен на рис.
9.!4. Первые две строки инициализируют некоторые значения потока данных4. В строке 3 начинается цикл, итерации которого выполняются до схождения, а внутренний цикл в строках 4 — 6 применяет уравнения потока данных к каждому блоку, отличному от входного. и Интуитивно алгоритм 9.11 распространяет определения до тех пор, пока это возможно без их уничтожения, моделируя все возможные пути выполнения программы. В конечном счете этот алгоритм завершит свою работу, поскольку для 4 Внимательный читатель заметит, что можно объединить строки ! и 2. Однако в аналогичных алгоритмах потоков данных может оказаться необходимым инициализировать входной и выходной узлы не так, как все остальные. Поэтому мы следуем общему щаблоиу итеративных алгоритмов, в которых "граничные условия" наподобие строки ! отделены от инициализации (строка 2). 731 9.2. Введение в анализ потоков данных опт[Вход] = а; 1ог 1каждый базовый блок В, отличный от входного) опт [В] = И; майе 1внесены изменения в ог1т) 1ог (каждый базовый блок В, отличный от входного) ] опт [В] = аепн 0 (1ы [В] — Ы11п); 1) 2) 3) 4) 5) 6) Рис.
9.14. Итеративный алгоритм для вычисления достигающих определений Пример 9.12. Представим семь определений 4,йз,...,с)т в графе потока на рис. 9.13 битовыми векторами, в которых 1-й бит слева представляет определение д,. Объединение множеств вычисляется как логическая операция ИЛИ над соответствующими битовыми векторами. Разность двух множеств Я вЂ” Т вычисляется как побитовая логическая операция И над вектором Я и дополнением к битовому вектору Т. любого В множество огзт [В] никогда не уменьшается в размере; если определение попало в это множество, оно останется в нем навсегда (см. упражнение 9.2.6). Поскольку множество всех определений конечно, рано или поздно должен произойти проход цикла, при котором ни в одно из множеств опт не будет добавлено ни одно определение, и алгоритм завершит свою работу.
Поскольку, если множество опт в данном проходе неизменно, множество пч будет неизменно при следующем проходе, работу алгоритма можно безопасно завершить по условию неизменности множества опт. Если не изменяется ни одно множество пч, то не может измениться и ни одно множество Опт, так что все последующие итерации цикла оставят все множества пч и Оит неизменными. Верхняя граница количества итераций в цикле равна количеству узлов в графе потока. Причина этого в том, что если определение достигает некоторой точки, то оно может сделать это по пути без циклов, а количество узлов в графе потока и есть верхняя граница количества узлов в пути без циклов. При каждой итерации цикла зкЬ11е каждое определение перемещается как минимум на один узел вдоль рассматриваемого пути, а зачастую и более чем на один узел — в зависимости от порядка, в котором посещаются узлы.
В действительности при правильном упорядочении блоков в цикле в строке 4, как показывают эмпирические данные, среднее количество итераций для реальных программ не превышает 5 (см, раздел 9.6.7). Поскольку множества определений могут быть представлены битовыми векторами, а операции над этими множествами могут быть реализованы при помощи логических операций над битовыми векторами, на практике алгоритм 9.11 на удивление эффективен.
732 Глава 9. Машинно-независимые оптимизации На рис. 9.15 показаны значения, принимаемые множествами пч и опт в алгоритме 9.11. Начальные значения, указанные при помощи верхнего индекса О, как, например, пч [В), присваиваются в цикле в строке 2 на рис. 9.14. Все мно- о жества пустые, что представлено векторами 0000000. Значения на последующих итерациях алгоритма указываются с использованием верхних индексов: пч [В) 1 и опт [В) ~ — на первой итерации, пч [В] и опт [В] — на второй. Рис. 9.15. Вычисление щ и опт Предположим, что цикл Гог в строках 4-6 выполняется с блоком В, принимающим значения В„Вз, Вз, В4, Выход в указанном порядке. Когда В = Вм поскольку оит[Вход] = И, пч [Вз) представляет собой пустое множество, а опт [Вз] равен яепн,. Это значение отличается от предыдущего значения оит[Вз)~, так что мы знаем, что на первой итерации внесены изменения (а потому будет выполнена и вторая итерация).
Затем рассмотрим В = Вз и вычислим пч [Вз] — опт [Вз) и опт [В4] = 1110000 + 0000000 = 1110000 оот[Вз] = яеин, 0 (пч[Вз]~ — Ы!н,) = = 0001100 + (1110000 — 1100001) = 0011100 Результаты вычислений показаны на рис. 9.15. Например, в конце первого пРохода Оот[Вз)' = 0011100, что отРажает тот факт, что Й4 и с~в генеРиРУютсЯ в Вз, в то время как йз достигает начала базового блока Вз н не уничтожается в нем. Заметим, что после второй итерации оит[Вз] изменяется; это отражает тот факт, что да также достигает начала базового блока Вз и не уничтожается в нем. Мы не увидели этого на первой итерации, поскольку путь от да к концу Вз, Вз — В4 — Вз, в данном порядке за одну итерацию не проходится.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
