А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 146
Текст из файла (страница 146)
Анализ потоков данных позволяет найти ответы на перечисленные и многие другие вопросы. 720 Глава 9. Машинно-независимые оптимизации 9.2.1 Абстракция потока данных Как было сказано в разделе 1.6.2, выполнение программы может рассматриваться как ряд преобразований состояния программы, которое состоит из значений всех переменных программы, включая переменные в кадрах стека, находящихся ниже текущей вершины стека времени выполнения.
Каждое выполнение инструкции промежуточного кода преобразует входное состояние программы в новое выходное состояние. Входное состояние связано с точкой программы перед инструкцией, а выходное — с точкой програлоиы после инструкции. При анализе поведения программы мы должны рассматривать все возможные последовательности точек программы (" пути" ) в графе потока, через которые может проходить программа.
Затем из возможных состояний программы в каждой точке извлекается информация, необходимая для решения поставленных нами задач анализа потока данных. При более сложном анализе следует учитывать пути с переходами при вызовах и возвратах из процедур. Однако для начала мы ограничимся путями в одном графе потока для единственной процедуры. Итак, что же нам может рассказать граф потока о возможных путях выполнения? ° В пределах одного базового блока точка программы после инструкции совпадает с точкой программы перед следующей инструкцией.
° Если имеется дуга от базового блока В1 к базовому блоку Вз, то за точкой программы после последней инструкции В1 может непосредственно следовать точка программы перед первой инструкцией Вз. Таким образом, мы можем определить путь выполнения (ехеси11оп рагп), или просто путь, от точки р~ к точке р„как последовательность точек ры рз,...,р„, таких, что для каждого 1 = 1, 2,..., п — 1 либо 1. р, является точкой, непосредственно предшествующей инструкции, а р,ч 1— точкой, непосредственно следующей за этой инструкцией в том же блоке, либо 2. р; представляет собой конец некоторого блока, а р;„1 — начало следующего блока. В общем случае существует бесконечное число возможных путей выполнения программы и не существует верхней границы длины пути выполнения.
Анализ программы подводит итог всем возможным состояниям, которые могут существовать в точке программы, на основании конечного множества фактов. Различные анализы могут выбирать разную информацию, и в общем случае ни один анализ не требует идеального представления состояния программы.
721 9.2. Введение в анализ потоков данных Пример 9.8. Даже простая программа на рис. 9.12 описывает неограниченное количество путей выполнения. Кратчайший путь не входит в цикл и состоит из точек программы (1, 2, 3, 4, 9). Следующий по длине путь проходит одну итерацию цикла и состоит из точек (1,2,3,4,5,6, 7,8,3,4,9). Мы знаем, что, например, при первом прохождении точки (5) значение а равно 1 в соответствии с определением 4. Мы говорим, что д1 достигает точки (5) при первой итерации. В последующих итерациях точки (5) достигает дз, и значение а становится равным 243.
в, в, в, Рис. 9.12. Пример программы, иллюстрирующей абстракцию потока данных В общем случае отследить все состояния программы для всех возможных путей невозможно. В анализе потока данных мы не выделяем пути, достигающие данной точки. Более того, мы не отслеживаем состояния полностью; вместо этого мы абстрагируемся от определенных деталей, отслеживая только данные, необходимые для проведения нашего анализа. Два примера иллюстрируют, как одни и те же состояния программы могут привести к разной информации, абстрагированной в точке программы. 1.
Чтобы помочь пользователям в отладке их программ, мы можем решить отслеживать все возможные значения переменной в некоторой точке программы и в каких именно местах программы эти значения могут быть определены. Например, мы можем подвести итоги всех состояний программы в точке (5), сказав, что возможные значения переменной а в этой точке — 11, 243) и что она может быть определена в 1аы дз). Определения, которые могуг достичь точки программы по некоторому пути, известны как достигающие определения. 722 Глава 9. Машинно-независимые оптимизации 2.
Предположим, что теперь нас интересует реализация дублирования констант. Если использование переменной х достигается только одним определением и это определение присваивает х константу, то можно просто заменить х этой константой. Если же одной точки программы могут достичь несколько определений, то мы не можем прибегнуть к дублированию констант. Таким образом, при дублировании констант нас интересуют те определения, для которых данной точки программы достигает только одно-единственное определение, независимо от того, какой путь выполнения рассматривается. Для точки (5) на рис. 9.12 не существует определения, которое должно быть определением а в этой точке, так что для а в точке (5) это множество определений пустое.
Даже если переменная имеет единственное определение в интересующей нас точке, это определение должно присваивать переменной константу. Таким образом, можно просто описать некоторые переменные как "не константы" вместо сбора информации об их возможных значениях или всех возможных определениях. Как видите, одна и та же информация может быть подытожена различными способами в зависимости от цели анализа. о 9.2.2 Схема анализа потока данных В каждом приложении анализа потока данных мы связываем с каждой точкой программы значение потока данных (да1а-()очч ча1ие), которое представляет абстракцию множества всех возможных состояний программы, которые могут наблюдаться в данной точке.
Множество возможных значений потока данных является областью определения (бота(п) этого приложения. Например, областью определения для достигающих определений является множество всех подмножеств определений в программе. Конкретное значение потока данных представляет собой множество определений, и мы хотим связать с каждой точкой программы точное множество определений, которые могут достигать данной точки.
Как говорилось выше, выбор абстракции зависит от цели анализа; для эффективности мы отслеживаем только ту информацию, которая имеет отношение к решаемой нами задаче. Обозначим значения потока данных до и после каждой инструкции в как 1н [з[ и опт [в[ соответственно. Задача потока данных (дага-бов ргоЫеш) состоит в поиске решения для множества ограничений, накладываемых на нч [з[ и о0т [з[ для всех инструкций в. Существует два вида ограничений; основанные на семантике инструкций (передаточные функции) и основанные на потоке управления.
Передаточные функции Значения потока данных перед инструкцией и после нее ограничены семантикой этой инструкции. Предположим, например, что наш анализ потока данных Т2З 9.2. Введение в анализ потоков данных включает определение константного значения переменных в точках. Если переменная а имеет значение с перед выполнением инструкции Ь = а, то и а, и 6 после присваивания имеют значение с. Такое соотношение между значениями потока данных до и после инструкции присваивания известно как передаточная функция 11тапз1ег Йлсцоп). Передаточные функции работают в двух направлениях: информация может распространяться как в прямом направлении вдоль пути выполнения, так и в обратном.
В задаче прямого потока передаточная функция инструкции е, которая обычно обозначается как 2„ получает значение потока данных перед инструкцией и выдает новое значение потока данных после инструкции, т.е. оот[е] = );(пч[а]) И наоборот, в задаче обратного потока передаточная функция г", для инструкции а преобразует значение потока данных после инструкции в новое значение потока данных до инструкции, т.е. пч [е] =,); (опт [а]) Ограничения потока управления Второе множество ограничений значений потоков данных порождается потоком управления. В базовом блоке поток управления очень простой. Если базовый блок В состоит из инструкций зы ез,..., е„в указанном порядке, то значение потока управления на выходе из а, то же, что и значение потока управления на входе в а,+и т.е. БЧ [аг-ь1] = оот[а;] для всех г = 1,2,,п — 1 Однако ребра потока управления между базовыми блоками приводят к более сложным ограничениям между последней инструкцией одного базового блока и первой инструкцией следуюшего.
Например, если нас интересует сбор всех определений, которые могут достигать точки программы, то множество определений, достигающих лидера базового блока, представляет собой объединение определений после последних инструкций каждого из предшественников данного блока. В следующем разделе потоки данных между блоками рассматриваются более детально. 9.2.3 Схемы потоков данных в базовых блоках При рассмотрении потоков данных в базовых блоках можно сэкономить время и память, поскольку поток управления проходит по базовому блоку без прерываний и ветвлений. Таким образом, можно переформулировать схему в терминах 724 Глава 9. Машинно-независимые оптимизации значений потока данных при входе в блок и выходе из него.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
