А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 159
Текст из файла (страница 159)
В примере 9.29 демонстрируется важность этого шага. Пример 9.29. В графе потока иа рис. 9.36 выражение Ь + с иа пути В1 — Вз— — Ве — Вт вычисляется дважды. Выражение Ь + с является ожидаемым даже в начале блока Вп Если мы вычислим это выражение, как толью оио станет ожидаемым, то мы должны вычислять его в базовом блоке Вп Затем этот результат должен храниться до его использования в блоке Вт, т.е. в процессе вычислений, включающих цикл из блоков Вз и Вз. Однако можно отложить вычисления выражеиия Ь+ с до начала блока Вз и до того момента, югда поток управления будет переходить от блока В4 к блоку Вт.
и Пример 9.30. Вновь обратимся к выражению Ь + с иа рис. 9.33. Двумя наиболее ранними точками для этого выражения являются базовые блоки Вз и Вз. Обратите внимание иа то, что иа рис. 9.33, а оии оба выделены как серым, так и черным цветом, что указывает иа то, что в этих блоках выражение Ь+ с является одновременно ожидаемым и недоступным. Нельзя отложить Ь+ с из блока Вз в блок Ве, посюльку Ь+ с используется в Вз.
Однако можно отложить это выражение из блока Вз в блок Вя. Отложить Ь + с из блока В4 в блок Вт нельзя. Причина этого в том, что, хотя Ь+ с и ие используется в В4, размещение вычисления в Вт может привести 782 Глава 9. Машинно-независимые оптимизации В в, Рис. 9.36. Граф потока к примеру 9.29, иллюстрирующий необходимость откладывания выражения к избыточному вычислению б+ с на пути Вз — Ве — Вт.
Как вы увидите, В4— одно из наиболее поздних мест, где можно вычислять 6+ с. о Уравнения потока данных для задачи откладываемых выражений показаны на рис. 9.34, в. Анализ проводится в прямом направлении. "Отложить" выражение до входа в программу невозможно, так что Опт'рзход] = И. Выражение откладываемо до выхода из блока В, если оно не используется в блоке, и либо оно откладываемо до входа в В, либо принадлежит множеству еаг11езг]В].
Выражение не откладываемо до входа в блок, если только все его предшественники не включают данное выражение в свои множества рояфопаЫе на выходе из этих блоков. Таким образом, оператор сбора — пересечение множеств, а внутренние точки должны быть инициализированы верхним элементом полурешетки — универсальным множеством. Грубо говоря, выражение помещается на границе, где оно переходит из откладываемого в не откладываемое. Говоря более конкретно, выражение е может быть помещено в начале блока В, только если выражение на входе в В принадлежит его множеству еаг1~езг или розгропаЫе. Кроме того, В находится на откладываемой границе е, если выполняется одно из следующих условий. 1. е ф розгропаЫе [В] .оиг, Другими словами, е е е ивен.
783 9.5. Устранение частичной избыточности 2. е не может быть отложено до одного из преемников В. Другими словами, существует преемник В, такой, что е не входит в множество еагйезг или роз~ролаЫе на входе в этот преемник. Выражение е может быть помещено в начале блока В в любом из приведенных выше случаев благодаря введению новых блоков на этапе предварительных шагов алгоритма. Пример 9.31. На рис. 9.33, б показан результат анализа.
Серые прямоугольники представляют блоки, множества еагйезг которых включают выражение Ь + с. Черные тени указывают блоки, которые включают Ь+ с в множествах роыропаЫе. Таким образом, последние размещения выражений — на входах в блоки В4 и Вз, поскольку 1. Ь+ с входит в множество розгролаЫе блока В4, но не блока Вт и 2, множество еагйезг блока Вз включает Ь + с, а сам блок его использует. Выражение сохраняется во временной переменной г в блоках В4 и Вь и во всех остальных местах, как показано на рисунке, вместо выражения Ь + с используется значение, сохраненное в 1. о Используемые выражения Наконец, обратный проход используется для выяснения, используются ли за пределами блока созданные в нем временные переменные.
Мы говорим, что выражение ислользуевся (нзеб) в точке р, если существует путь, ведущий из р, который использует выражение до того, как его значение будет вычислено заново. Это, по сути, анализ живых переменных, но выполненный не для переменных, а для выражений. Уравнения потока данных для используемых выражений представлены на рис. 9.34, г. Анализ выполняется в обратном направлении. Используемое выражение на выходе из блока В является используемым на входе в этот блок, только если оно не входит в множество 1агезг.
В качестве новых использований блок генерирует множество е изел. На выходе из программы никакие выражения не используются. Поскольку нас интересует поиск выражений, которые могут быть использованы любым из путей, оператором сбора является объединение. Соответственно, внутренние точки должны быть инициализированы верхним элементом полурешеткн — пустым множеством. Алгоритм отложенного перемещения кода Все описанные шаги алгоритма подытожены в формальном описании алгоритма 9.32.
Глава 9. Машинно-независимые оптимизации Алгоритм 9.32. Отложенное перемещение кода Вход: граф потока, для каждого базового блока В которого вычислены множества е изел и е lа11л. Выход: модифицированный граф потока, удовлетворяющий четырем условиям отложенного перемещения кода из раздела 9.5.3. Метод: выполняем следующие действия.
1. Вставляем пустые блоки во все ребра, входящие в блоки с более чем одним предшественником. 2. Для всех блоков В находим апйс1рагеЫ [В] лп, как определено на рис. 9.34, а. 3. Для всех блоков В находим анадаЫе [В] лп, как определено на рис. 9.34, б. 4. Вычисляем наиболее раннее размещение для всех блоков В: еаг11езг [В] = апйс1рагег1 [В] лп — ага11аЫе [В] лп 5. Для всех блоков В находим розгропаЫе[В] лп, как определено на рис. 9 34, е. 6. Для всех блоков В вычисляем самые поздние размещения: 1агеег [В] = (еаг!1еел [В] О разгропаЫе [В] лп) О и[ ~ [П ( йми~ир р и ~8~.ы]] Лезисс(В) Здесь — означает дополнение по отношению к множеству всех выражений, вычисляемых программой. 7.
Для всех блоков В находим изеЫ [В] .ош, как определено иа рис. 9.34, г. 8. Для каждого выражения, скажем, х+ у, вычисляемого программой, выполняем следующее. а) Создаем для х + у новую переменную, скажем, 1. б) Для всех блоков В, таких, что х+ у е 1агеел [В] О изей [В] .аш, в начало блока В добавляем ~ = х+у. в) Для всех блоков В, таких, что х+ у Ее изеп О( — 1агезг[В]Оигег1ога[В]), заменяем каждый оригинал х + у на 1. и 785 9.5.
Устранение частичной избыточности Резюме При устранении частичной избыточности при помощи единого алгоритма находится множество типов избыточных операций. Этот алгоритм иллюстрирует, как много задач потоков данных могут использоваться при поиске оптимального размещения выражений. 1. Ограничения на размещения накладываются анализом ожидаемости выражений, который представляет собой обратный анализ потока данных с пересечением в качестве оператора сбора и определяет, используется ли выражение впоследствии каждой точкой программы по всем путям. 2.
Наиболее ранее размещение выражения определяется точкой программы, в которой выражение ожидаемо, но не доступно. Поиск доступных выражений выполняется при помощи прямого анализа потока данных с оператором сбора, представляющим собой пересечение множеств. Этот анализ выясняет, является ли выражение ожидаемым перед каждой точкой программы вдоль всех путей. 3. Наиболее позднее размещение выражения определяется точкой программы, в которой выражение более не может быть откладываемым. Выражения в некоторой точке программы являются откладываемыми, если вдоль всех путей, достигающих данной точки программы, не встречается использование этого выражения. Поиск откладываемых выражений выполняется при помощи прямого анализа потока данных с оператором сбора, представляющим собой пересечение множеств.
4. Присваивание временным переменным устраняется, если только они не используются впоследствии вдоль некоторого пути. Поиск используемых выражений выполняется при помощи обратного анализа потока данных с оператором сбора, представляющим собой объединение множеств. 9.5.6 Упражнения к разделу 9.5 Упражнение 9.5.1. Для графа потока на рис. 9.37 выполните следующее. а) Вычислите множество апг!с!ригеи для начала и конца каждого блока. б) Вычислите множество ага!!аб!е для начала и конца каждого блока. в) Вычислите множество еагбелг для каждого блока. г) Вычислите множество ров!ропаЫе для начала и конца каждого блока.
д) Вычислите множество плед для начала и конца каждого блока. 786 Глава 9. Машинно-независимые оптимизации е) Вычислите множество 1агезг для каждого блока. ж) Введите временную переменную 1; покажите, где она вычисляется и где используется. в, Рис. 9.37. Граф потока к упражнению 9.5.1 Упражнение 9.5.2. Повторите упражнение 9.5.1 для графа потока на рис.
9.10 (см. упражнения к разделу 9.1). В своем анализе вы можете ограничиться выражениями а+ б, с — а и б*д. И Упражнение 9.5.3. Рассмотренные в данном разделе концепции применимы также для устранения частично бесполезного кода. Переменная является частично бесполезной (рагйа1!у г!еаб), если она активна только на некоторых путях, но не на всех. Можно оптимизировать выполнение программы путем вычисления определения только на тех путях, на которых переменная является активной. В отличие от устранения частичной избыточности, когда выражения размещаются до исходного их положения, новые определения переменных размещаются после исходных. Разработайте алгоритм для перемещения частично бесполезного кода, чтобы выражения вычислялись только тогда, когда они в конце концов будут использованы.
787 9.6. Циклы в графах потоков 9.6 Циклы в графах потоков Выше мы никак не выделяли циклы — они рассматривались так же, как и любые другие виды потоков управления. Однако важность циклов не подлежит сомнению, по крайней мере потому, что программы затрачивают основное время выполнения именно на работу циклов, так что оптимизация, повышающая производительность циклов, может оказать существенное влияние на производительность программы в целом.
Таким образом, желательно четко идентифицировать циклы и рассматривать их отдельно от других видов потоков управления. Циклы также влияют на время работы анализа программы. Если в программе нет ни одного цикла, то ответ на задачи потоков данных можно получить путем одного прохода по программе. Например, задача потока данных в прямом направлении может быть решена путем однократного посещения всех узлов в топологическом порядке. В этом разделе мы рассмотрим новые концепции — доминаторы, упорядочение вглубь, обратные ребра, глубина графа, приводимость. Все они понадобятся для последующего материала, посвященного поиску циклов и скорости сходимости итеративных анализов потоков данных.
9.6.1 Доминаторы Мы говорим, что узел й графа потока доминирует (бош1па1ев) над узлом п (записывается как д аое п), если любой путь от входного узла графа потока к и проходит через д. Заметим, что при таком определении каждый узел доминирует над самим собой. Пример 9.33. Рассмотрим граф потока (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
