А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 147
Текст из файла (страница 147)
Обозначим значения потока данных непосредственно перед и непосредственно после каждого базового блока В как пч [В] и оит[В] соответственно. Ограничения для пч [В] и оит[В] можно вывести из ограничений на пч [в] и оит [а] для различных инструкций з в базовом блоке В следующим образом. Предположим, что блок В состоит из инструкций аи...,в„в указанном порядке. Если в1 — первая инструкция базового блока В, то пч[В] = пч[з1]. Аналогично если а„ вЂ” последняя инструкция базового блока В, то оит[В] = = оит[а„,]. Передаточная функция базового блока В, которую мы обозначим как 5у, может быть получена как композиция передаточных функций инструкций базового блока.
Пусть у,, — передаточная функция для инструкции аь Тогда Ун = = — г",„о . о гвв с ~„. Соотношение между началом блока и его концом имеет вид оит[В] = ~н (пч [В]) Ограничения, накладываемые потоком управления между базовыми блоками, можно легко переписать, заменяя пч [В] и оит [В] на пч [з1] и оит [а„] соответственно. Например, если значения потока данных представляют собой информацию о множествах констант, которые могут быть присвоены переменным, то мы получаем задачу прямого потока, в которой пч[В] =[ ] оит [Р] ~г Р— пввдшественвик В При обратном потоке — например, как мы вскоре увидим, в случае анализа живых переменных — уравнения аналогичны, но пч и оит меняются местами, т.е.
пч [В] = ун (оит[В]) оит[В] = О пч[В] В отличие от линейных арифметических уравнений, уравнения потоков данных обычно не имеют единственного решения. Наша цель заключается в том, чтобы найти наиболее "точное" решение, которое удовлетворяет двум множествам ограничений: ограничениям потока управления и ограничениям передачи. Иначе говоря, нам нужно решение, которое приводит к корректному улучшению кода и не допускает небезопасных преобразований, которые могут изменить результат вычислений компьютера. Этот вопрос вкратце рассматривается во врезке "Консерватизм анализа потоков данных" и более подробно — в разделе 9.3.4.
В следующих подразделах мы рассмотрим некоторые из наиболее важных примеров задач, которые могут быть решены с помощью анализа потоков данных. 725 9.2. Введение в анализ потоков данных Выявление возможных использований до определения Вот как мы используем решение задачи достигающих определений для обнаружения использований переменных до их определения. Фокус заключается во введении фиктивного определения для каждой переменной х на входе в граф потока.
Если фиктивное определение х достигает точки р, где х может быть использовано, то возможно использование этой переменной до ее определения. Заметим, что никогда нельзя быть абсолютно уверенным, что в программе имеется ошибка, поскольку могут быть причины (возможно, со сложным логическим доказательством), по которым путь р, на котором нет реального определения х, никогда не будет пройден. 9.2.4 Достигающие определения Достигающие определения (геас!т!пя г)ебп!йопя) — одна из наиболее распространенных и полезных схем потока данных. Зная, где именно в программе может быть определена каждая переменная х при достижении потоком управления каждой точки р.
можно получить много информации об этой переменной. В частности„компилятор может выяснить, является ли х константой в точке р, а отладчик может сообщить о возможном использовании в точке р не инициализированной переменной х. Мы говорим, что определение е! досглигаепг точки р, если существует путь от точки, непосредственно следующей за г1, к точке р, такой, что д не уничтожается вдоль этого пути. Мы уничтожаем (Ы1!) определение переменной х, если существует иное определение х где-то вдоль путиз. Интуитивно понятно, что, если определение д некоторой переменной х достигает точки р, то г! может быть местом, где последний раз определяется значение х, используемое в р. Определением переменной х является инструкция, которая присваивает или может присваивать значение переменной х.
Параметры процедур, обращения к массивам и косвенные обращения могут использовать псевдонимы, так что не так легко сказать, обращается ли некоторая инструкция к конкретной переменной х. Анализ программы должен быть консервативным: если мы не знаем, присваивает ли инструкция а значение переменной х, то мы должны считать, что она может сделать это, т.е. что переменная х после инструкции я может иметь либо исходное значение, бывшее у нее до инструкции в, либо новое значение, созданное гь Для простоты в оставшейся части главы предполагается, что мы работаем только с переменными, не имеющими псевдонимов. Этот класс пере- 'Заметим, что путь может иметь циклы, так что можно прийти к другому определению Н вдоль пути, который не уничтожает г!.
726 Глава 9. Машинно-независимые оптимизации менных включает все локальные скалярные переменные в большинстве языков программирования; в случае С и С++ исключаются локальные переменные, адре- са которых были вычислены в некоторой точке программы. Пример 9.9. На рис. 9.13 показан граф потока с семью определениями. Нас интересуют определения, достигающие блока Вз. Все определения в блоке В| достигают начала блока Вз.
Определение йз . з = ) — 1 в блоке Вз также достигает начала блока Вз, поскольку других определений з в цикле, приводящем к началу блока Вз, нет. Однако это определение уничтожает определение в(з . )' = п, не позволяя ему достичь блоков Вз или В4. Инструкция г(4: г = в+1 в Вз недостигает начала Вз, поскольку переменная г всегда переопределяется в 1т . ( = иЗ.
Наконец, определение да . а = и2 также достигает начала блока Вз. и авив =(«г иг и, ) В, ( в' г в, вепа = ( ви в' ылв, авив = ( в' вглв =(и, ) явив, =( в, ) Гияв ( ~, '~„) в, Рнс. 9.13. Граф потока для иллюстрации достигающих определений (а == Ь) ииструкцил1г е1ае 1й (а == Ь) ииструкция2; При используемом нами определении достигающих определений иногда допускаются неточности. Однако все они — в безопасном направлении.
Например, вспомним о нашем предположении, что могут быть обойдены все ребра графа потока. На практике это предположение может оказаться неверным. Например, ни для каких значений а и 6 поток управления не сможет достичь инструкции 2 в приведенном далее фрагменте: 9.2. Введение в анализ потоков данных Консерватизм анализа потоков данных Поскольку все схемы потоков данных вычисляют всего лишь приближения (определяемые всеми возможными путями выполнения программы), следует гарантировать, что любые ошибки будут допущены только в "безопасном направлении".
Стратегия принятия решений безопасна (или консервативна), если она не позволяет нам изменить результаты вычисления программы. Такая безопасная стратегия может, к сожалению, не допустить некоторых улучшений кода программы, которые оставили бы неизменным ее смысл, но в конечном счете безопасной стратегии, которая разрешала бы все допустимые оптимизации кода, не запрещая ни одной из них, не существует. Применение небезопасных стратегий, ускоряющих работу программы ценой ее ошибочности, совершенно неприемлемо. Таким образом, при разработке схемы потока данных следует продумывать, как именно будет использована полученная информация, и гарантировать, что все приближения будут делаться в "консервативном", или "безопасном", направлении.
Каждая схема и ее применение должны рассматриваться отдельно. Например, при использовании достигающих определений для дублирования констант безопасно считать, что определение является достигающим, в то время как оно не является таковым (мы можем считать, что х не является константой, в то время как на самом деле можно выполнить дублирование константы), но считать, что определение не является достигающим, в то время как на самом деле это не так, — опасно (мы можем таким образом заменить х константой, в то время как на самом деле значение х при выполнении программы может принимать значения, отличные от этой константы). В общем виде задача определения возможности прохода для каждого пути графа потока неразрешима. Таким образом, мы просто предполагаем, что каждый путь графа потока при каком-то из выполнений программы может быть пройден. В применении к определению досгижимости консервативное решение состоит в предположении, что определение может достичь некоторой точки, даже если оно ее не достигает.
Таким образом, мы допускаем наличие путей, которые не могут быть пройдены при выполнении программы, и разрешаем определениям проходить через неоднозначные определения той же переменной. 728 Глава 9. Машинно-независимые оптимизации Уравнения передачи для достигающих определений Теперь займемся ограничениями для задачи достигающих определений. Начнем с детального изучения единственной инструкции. Рассмотрим определение и =ч+и Здесь, как и в большинстве случаев далее, + обозначает обобщенный бинарный оператор.
Эта инструкция "генерирует" определение П переменной и и "уничтожает" все другие определения этой переменной в программе. Передаточная функция определения д может быть записана как ~а (х) = 8епа О (х — Ы1а) (9.!) Здесь Пепл — — (Н) — множество определений, генерируемых инструкцией, а Ы!а— множество всех прочих определений и в программе. Как говорилось в разделе 9.2.2, передаточная функция базового блока может быть получена путем композиции передаточных функций содержащихся в нем инструкций. Композиция функций вида !9.1), о котором мы будем говорить как о "виде !или форме) дел-lоП", имеет тот же вид, что легко увидеть.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
