А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 169
Текст из файла (страница 169)
4. В случае, когда в правой части символического отображения в области В используется входное значение переменной ти]о) и на входе в область т(тг) = ылл, вводим новую ссылочную переменную т и присваивание с = ч в начале области Л и заменяем все обращения к т 10) обращениями к 1. Если в этом месте не ввести ссылочную переменную, то хранившееся в переменной 0 значение ылл проникнет во внутренние циклы. и У вЂ” 1 Уйз,з, ]Вз] = УВ, ег 1йзшост]Вз] / Вз ~..,.]„] = ~ гйв,лг]й,] = УВг г йе,ост]Ве] г о 1йз,10,ост]Вз] и 1Вг г — 1 г йт г 1и]йе] г йе,ест]В~] 1йти,ест]В4] г йе,сит]Ве] Уй,,в]В,] = 1 г йв,1и]йт] г Вг 1й„ест]В4] — Уйг,!00,оит[В4] г Вг Рис.
9.62. Отношения передаточных функций в восходящем проходе в примере 9.54 831 9.8. Символический анализ Пример 9.60. Покажем, как в примере 9.54 на восходящем проходе вычисляются передаточные функции программы, представленные на рис. 9.62. Область Лз представляет собой внутренний цикл с телом Вы Передаточная функция 1й представляет путь от входа в область Л; к началу зчй итерации, где 1' ) 1. Путь к концу 1-й итерации (~ > 1) представляет функция Д,. Область Л» состоит из блоков Вз и Вя с областью цикла Л; посредине.
Передаточные функции от входов в Вз и Лз можно вычислить так же, как и в исходном алгоритме. Передаточная функция ~л, о„т~щ представляет собой композицию блока В~ н всего выполнения внутреннего цикла, поскольку передаточная функция 1п, является тождественной функцией. Так как известно, что внутренний цикл выполняется !О раз, чтобы подытожить влияние внутреннего цикла, можно заменить | десяткой. Остальные передаточные функции можно вычислить аналогично. Вычисленные передаточные функции приведены на рис. 9.63. Рис.
9.63. Передаточные функции, вычисленные в процессе нисходящего прохода в примере 9.54 Символическое отображение на входе в программу — просто т„,А. Нисходящий проход используется для вычисления символического отображения на вход в последовательные вложенные области, пока не будут найдены все символические отображения для каждого базового блока. Начнем с вычисления значений потока данных для блока В~ в области Лв. пч[В~] = твдА опт [В~] = Лз, (пч [В~]) 832 Глава 9. Машинно-независимые оптимизации Опускаясь вниз к областям Йе и Нт, получаем пч, [Вз[ = ~л. ь.и(п,1 (опт [В1]) Опт, [Вз[ = ~Вг (!х~ [Вз[) И наконец в области Ва получаем пчго [Вз) =,~„„щ(п11 (Опт, [Вз[) ость, [Вз[ =,Гп., (пч;, [Вз[) Ничего удивительного, что мы получили результаты, которые уже были показаны на рис.
9.58. а Пример 9.54 демонстрирует простую программу, в которой каждая переменная, используемая в символическом отображении, имеет аффинное выражение. В примере 9.61 будет показано, зачем и как в алгоритме 9.59 вводятся ссылочные переменные. Пример 9.61. Рассмотрим простой пример, показанный на рис. 9.64, и. Пусть ,1, — передаточная функция, подытоживающая влияние выполнения 1 итераций внутреннего цикла. Несмотря на то что в процессе выполнения цикла переменная а изменяется, видно, что переменная 6 является переменной индукции, основанной на значении переменной а на входе в цикл, т.е.
Д (гп) (6) = т(а) — 1+ 1. Поскольку а присваивается входное значение, возвращаемое функцией хпрцс ( ), символическое отображение на входе во внутренний цикл отображает а на мАА. Мы вводим новую ссылочную переменную 1 для сохранения значения а на входе и выполняем подстановку, показанную на рис. 9.64, б. и 9.8.4 Упражнения к разделу 9.8 Упражнение 9.8.1. Для графа потока на рис. 9.10 (см, упражнения к разделу 9.1) укажите передаточные функции а) для блока Вз, б) для блока В», в) для блока Вз. Упражнение 9.8.2. Рассмотрим внутренний цикл на рис.
9.10, состоящий из блоков Вз и В4. Если 1 — количество выполнений цикла, а Г" — передаточная функция тела цикла (т.е. без ребра от Вя к Вз) от входа в цикл (начала блока Вз) до выхода из Вя, то что собой представляет Г"'? Помните, что г" получает в качестве аргумента отображение т, которое присваивает значение каждой из переменных а, 6, д и е.
Мы обозначаем зти значения как т (и), т (6) и так далее, хотя и не знаем их точные величины. 8ЗЗ 9.9. Резюме к главе 9 аког (1 = 1; 1 < и; 1++) 1) 2) 3) 4) 5) 6) а = 1прцс(); гог (3 = 1; 3 < 10; 3++) ( а=а — 1; Ъ = Э + аз а=а+1? а) Цикл с изменяющейся переменной а аког (1 = 1; з. < и; з.++) а = 1прцс() г= а; аког (3 = 1; 3 < 10; 3++) ( а=à — 1; Ь=Г-1+зз а = сз б) Ссылочная переменная ( делает (з переменной индукции Рис.
9.б4. Необходимость введения ссылочных переменных 9.9 Резюме к главе 9 + Глобальные общие подвыражения. Поиск вычислений одного и того же выражения в двух разных базовых блоках представляет собой важный метод оптимизации. Если одно из них предшествует другому, можно сохранить результат первого вычисления и использовать сохраненное значение вместо последующих вычислений.
! Упражнение 9.8.3. Рассмотрим теперь внешний цикл на рис. 9.10, состоящий из блоков Вз, Вз, В4 и Вз. Пусть у — передаточная функция тела цикла от входа в цикл в Вз н до выхода из Ва. Пусты — количество итераций внутреннего цикла из блоков Вз и В4 (которое нам неизвестно), а З вЂ” количество итераций внешнего цикла (также неизвестное нам). Что собой представляет уз? 834 Глава 9.
Машинно-независимые оптимизации + Распространение копирований. Инструкция копирования и = с присваивает значение одной переменной, с, другой переменной, и. В некоторых ситуациях можно заменить все использования и использованиями с, устраняя таким образом как присваивание, так и переменную и. + Перемещение кода. Еше одним важным методом оптимизации кода является перемещение вычислений из цикла, в котором они находятся. Это изменение кода корректно лишь в том случае, если при каждой итерации цикла вычисления дают одно и то же значение. + Переменные индукции. Многие циклы содержат переменные индукции, которые принимают значения нз линейной последовательности при каждой очередной итерации.
Некоторые из них используются только для подсчета итераций и часто могут быть устранены, тем самым снижая время выполнения итерации цикла. + Анализ потока данных. Схема анализа потока данных определяет значение в каждой точке программы. С инструкциями программы сопоставлены передаточные функции, которые связывают значение до инструкции и после нее. Значения у инструкций с более чем одним предшественником определяются путем комбинирования значений предшественников с использованием оператора сбора. + Анализ потоков данных в базовых блоках. Поскольку обычно распространение данных в базовых блоках достаточно простое, уравнения потока данных обычно имеют по две переменные для каждого блока, цс и оцт, которые представляют значения потоков данных соответственно в начале и конце блока.
Для получения передаточной функции базового блока вычисляется композиция передаточных функций инструкций блока. + Достигающие определения. Значения в структуре потока данных для достигаюших определений представляют собой множества инструкций программы, которые определяют значения одной или нескольких переменных. Передаточная функция блока уничтожает определения переменных, которые переопределяются в блоке, и добавляет (" генерирует" ) определения переменных, которые встречаются в этом блоке. Оператор сбора представляет собой объединение, поскольку определения достигают некоторой ~очки. если они достигают любого из ее предшественников.
+ Активные переменные. Еше одна важная структура потока данных вычисляет в каждой точке активные переменные (т.е. те переменные, которые используются до их переопределения). Эта структура похожа на достигаюшие определения, с тем отличием, что передаточная функция работает 835 9.9. Резюме к главе 9 в обратном направлении. Переменная активна в начале блока, если она либо используется до ее определения в блоке, либо активна в конце блока и не переопределяется в нем.
+ Достутаве выражения. Для поиска глобальных общих подвыражений в каждой точке программы определяются доступные выражения, которые уже вычислены к этому моменту, причем после последнего вычисления аргументы этих выражений не переопределялись. Структура потока данных в этом случае аналогична структуре достигающих определений, но оператор сбора в данном случае представляет собой пересечение множеств, + Абстракция задач потока данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
