А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 167
Текст из файла (страница 167)
и 9.8.1 Аффинные выражения ееылочных переменных Поскольку невозможно создать краткие аналитические символические выражения для всех вычисляемых значений, мы выбираем абстрактную область определения и используем приближения вычислений наиболее близкими выражениями из этой области. Мы уже встречались ранее с примером подобной стратегии при рассмотрении распространения констант. В этом случае наша абстрактная 820 г=х; Рнс.
9.54. Пример программы, поясняющий символический анализ область определения состояла из констант, и специальный символ ФАС использовался в случае, ко~да обнаруживалось, что переменная не является константой. Представленный здесь символический анализ по возможности выражает значения как иффинные выражения ссылочных переменных. Выражение является аффинным по отис~нению к переменным щ, ез,..., е„, если оно может быть выражено как со + г~ ш + .
+ с„е„, где со, сы,,,, с„— константы. Такие выражения неформально известны как линейные. Строго говоря, аффинное выражение является линейным, ~олько если со равно О. Аффинные выражения интересуют нас потому, что они часто используются для индексирования массивов в циклах— такая информация весьма полезна при оптимизации и распараллеливании. Существенно больше информации по этой теме имеется в главе 11. Переменные индукции Вместо программных переменных в качестве ссылочных аффинные выражения могут использовать количество итераций в цикле.
Переменные, значения которых могут быть выражены как с~(+ со, где ( — количесгво итераций ближайшего охватывающего цикла, известны как переменные индукции (шанс([оп чапаЫез), или индуктивные переменные. Пример 9.53. Рассмотрим следующий фрагмент кода: аког (щ = 10; т < 20; т++ ) ( х = ш * 3; А[х) = Ор Предположим, что мы ввели в цикл переменную, скажем, 1, подсчитывающую количество выполненных итераций. На первой итерации цикла значение( равно О, на второй — 1 и т.л.
Переменную гп можно записать как аффинное выражение от 1, а именно как кп = ( + 10. Переменная х, значение которой — Зт, в процессе последовательных итераций цикла принимает значения 30, 33, ..., 57. Таким образом, аффннное выражение для х имеет вид г = ЗО + 3(. Мы заключаем, что и гл, н г являются переменными индукции этого цикла. о Запись переменных в виде аффинных выражений индексов циклов дает возможность выполнять некоторые преобразования, в частности вычислять ряд зна- 1) 2) 3) 4) 5) 6) 7) Глава 9.
Машинно-независимые оптимизации х = 1прис() у=х — 1; г = у — 1; А[х) = 10; А[у) = 11; Н (г > х) 821 9.8. Символический анализ чений переменной индукции при помощи сложения, а не умножения. Такое преобразование известно как снижение стоимости и рассматривалось в разделах 8.7 и 9.1. Например, можно удалить умножение х = в*3 из цикла в примере 9.53, переписав код следующим образом: х = 27; аког (аз= 10; т< 20; в++ ) (х=х+3;А(х)=0;) Заметим, кроме того, что адреса ячеек, в которые записывается нулевое значение, а именно йА+30, йА+ЗЗ,.... йА+57, также представляют собой аффиннос выражение от индекса цикла. Фактически этот ряд целых чисел — единственное, что должно быть вычислено, так что можно полностью удалить из кода одну из переменных.
Так, рассматриваемый код можно переписать просто как аког (х = йА+30; х <= ьА+57; х += 3 ) *х = 0 Помимо ускорения вычислений, символический анализ полезен и для распараллеливания. Когда индексы массива в цикле представляют собой аффинные выражения от индексов цикла, можно сделать определенные выводы о взаимоотношениях данных, к которым выполняется обращение в разных итерациях. Например, можно выяснить, что в каждой итерации запись ведется в новые ячейки памяти, а следовательно, все итерации цикла могут выполняться параллельно на разных процессорах. Такая информация используется в главах 10 и 11 для выделения параллельности в последовательных программах.
Другие ссылочные переменные Если переменная не является линейной функцией уже выбранных ссылочных переменных, то ее значение можно рассматривать как ссылочное для будущих операций. Например, рассмотрим следующий фрагмент кода: а = Г(); Ь = а + 10; с = а + 11; Значение, хранящееся в а, после вызова функции не может быть выражено как линейная функция каких-либо ссылочных переменных. но может использоваться в качестве таковой для последующих инструкций. Например, используя а в качестве ссылочной переменной, можно выяснить, что с на единицу больше 6 в конце приведенного фрагмента.
Пример 9.54. В этом разделе рабочим примером служит код на рис. 9.55. Внутренний и внешний циклы легко различимы и понятны, поскольку переменные 7' 822 и д не изменяются нигде, кроме самой конструкции 1ог. Таким образом, можно заменить 1 и д ссылочными переменными 1 и з, которые подсчитывают количество итераций внешнего и внутреннего циклов соответственно. Иначе говоря, мы можем положить 7" = 1+ 99 и д = 7' + 9 и подставить эти выражения вместо 7' и д. При трансляции в промежуточный код можно воспользоваться тем фактом, что каждый цикл выполняется как минимум однократно, и отложить проверки 1 < 100 и 7' < 10 до концов циклов. Рис. 9.55.
Исходный код к примеру 9.54 На рис. 9.56 показан граф потока для кода на рис. 9.55 после введения переменных 1 и ) и рассмотрения циклов Гог в качестве циклов гереаг Как выясняется, переменные а, 6, с и г( являются переменными индукции. Последовательность значений, присваиваемых этим переменным в каждой строке кода, показана на рис.
9.57. Как вы увидите, для этих переменных можно найти аффинные выражения от ссылочных переменных ( и 7', т.е. в строке 4 а =7', в строке 7 г( = 102 + 7' — 1, а в строке 8 с = ~. с 9.8.2 Формулировка задачи потока данных Данный анализ находит аффинные выражения от ссылочных переменных, введенных 1) для подсчета количества выполненных в каждом цикле итераций и 2) для хранения значений на входе в области там, где это необходимо. Этот анализ также находит переменные индукции, инварианты циклов и константы — как вырожденные аффинные выражения. Заметим, что данному анализу не под силу найти все константы, поскольку он отслеживает только аффинные выражения от ссылочных переменных. Значения потоков данных: символические отображения Областью определения значений потоков данных в данном анализе являются символические отображения (зутЬо11с тара), представляющие собой функции, 1) 2) 3) 4) 5) б) 7) 8) Глава 9.
Машинно-независимые оптимизации а=О; аког (й = 100; й < 200; г++) ( а=а+1; Ь = 10 * а; с=О; аког (д = 10р д < 20; д++) ( с(=Ь+ сг с = с+ 1; 823 9.8. Символический анализ в, в, в, в, Рис. 9.56. Граф потока и его иерархия областей к примеру 9.54 Рис. 9.57. Последовательность значений переменных в точках программы в примере 9.54 отображающие каждую переменную в программе на значение. Это значение является либо аффинной функцией ссылочных переменных, либо специальным символом мАА, представляющим неаффинное выражение. если имеется только одна переменная, то нижнее значение полурешетки представляет собой отображение переменной на мАА. Полурешетка для п переменных представляет собой просто произведение отдельных полурешеток.
Для указания нижнего элемента полуре- 824 Глава 9. Машинно-независимые оптимизации щетки, который отображает все переменные на балл, используется обозначение тч„„. Можно определить символическое отображение всех переменных на неизвестное значение, которое будет верхним элементом полурешетки, как мы делали для распространения констант. Однако в анализе на основе областей верхние значения нам не требуются. Пример 9.55. Символические отображения, связанные с каждым блоком кода из примера 9.54, показаны на рис. 9.58. Позже вы узнаете, как находятся эти отображения, — они являются результатом анализа потока данных на основе областей графа потока на рис.
9.56. Рис. 9.58. Символические отображения программы нз примера 9.54 Символическое отображение, связанное с входом программы, — т,„,. На выходе из Вз значение а устанавливается равным О. На входе в блок Вз на первой итерации а имеет значение О и увеличивается на 1 в каждой последующей итерации внешнего цикла.
Таким образом, а равно г — 1 на входе в з-ю итерацию и ~' в ее конце. Символическое отображение на входе в базовый блок Вз отображает переменные Ь, с, ~1 на нАА, поскольку при входе во внешний цикл значения этих переменных неизвестны (их значения зависят от количества итераций внешнего цикла). Символическое отображение на выходе из Вз отражает инструкции присваивания переменным а, Ь и с в этом блоке. После того как установлена корректность отображений на рис.
9.58, каждое из присваиваний а, Ь, с и 4 на рис. 9.55 можно заменить соответствующим аффинным выражением, т.е. код на рис. 9.55 можно заменить кодом, приведенным на рис. 9.59. о Передаточная функция инструкции Передаточная функция в этой задаче потока данных отображает символическое отображение на символическое отображение. Для вычисления передаточной функции инструкции присваивания мы интерпретируем семантику присваивания и определяем, может ли присваиваемая переменная быть выражена в виде аффин- 825 9.8. Символический анализ а=О; азот (1 = 1; з. <= 100р 1++) 1) 2) 3) 4) 5) 6) 7) 8) а = Ь = Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
