А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 157
Текст из файла (страница 157)
9.30, в. Выражение Ь+ с в блоке В4 избыточно на пути В1 — Вз - В4, но не на пути В1 — Вз — В4. Можно устранить избыточность в первом пути, разместив вычисление Ь+с в блоке Вз. Все результаты вычисления Ь + с записываются во временную переменную 1, а вычисление в блоке В4 заменяется переменной 1. Таким образом, подобно перемещению кода, инвариантного относительно цикла, устранение частичной избыточности требует размещения новых вычислений выражения. 9.5.2 Все ли избыточные вычисления могут быть устранены? Можно ли устранить все избыточные вычисления вдоль каждого пути? Ответ на этот вопрос отрицателен, если только мы не допускаем изменения графа потока путем создания новых блоков. Глава 9.
Машинно-независимые оптимизации Пример 9.24. В примере, показанном на рис. 9.31, а, вычисление выражения 6+ с в блоке В4 избыточно, если программа следует по пути В! — Вз — В4. Однако мы не можем просто переместить вычисление 6+ с в блок Вз, поскольку это действие пРиведет к излишнемУ вычислению 6+ с на пУти В! — Вз — Вб. В В В, а) б) Рис. 9.3!.Ва — В» является критическим ребром Было бы хорошо, если бы можно было вставить вычисление 6+ столько вдоль ребра от блока Вз к блоку В».
Это можно сделать, поместив инструкцию в новый блок, скажем, Вб, и передавая управление от блока Вз блоку Вб при переходе к блоку В4. Это преобразование показано на рис. 9.31, б. и Определим критическое ребро графа потока как ребро, идущее от узла с более чем одним преемником к узлу с более чем одним предшественником. Введение новых блоков вдоль критических ребер позволяет нам всегда найти блок для размещения интересующего нас выражения. Например, ребро от Вз к В» на рис.
9.31, а является критическим, поскольку у блока Вз два преемника, а у блока В4 — два предшественника. Добавления блоков может оказаться недостаточным для того, чтобы устранить все избыточные выражения. Как показано в примере 9.25, может потребоваться дублирование кода для того, чтобы выделить путь, в котором обнаружена избыточность. Пример 9.25. В примере, показанном на рис. 9.32, а, выражение 6+ с избыточно вычисляется на пути В! — Вя — В» — Вб. Мы хотели бы устранить излишнее вычисление 6+ с в блоке Вб на этом пути и вычислять это выражение только на пути В! — Вз — В4 — Вб.
Однако не существует единственной точки (или ребра) в исходной программе, единственным образом соответствующей данному 773 9.5. Устранение частичной избыточности пути. Для создания такой точки программы мы можем дублировать пару блоков В4 и Ва так, что одна пара достижима по пути, проходящему через Вз, а вторая пара — по пути, проходящему через Вз, как показано на рис. 9.32, б.
Результат 6+ с сохраняется в переменной г в блоке Вз и перемещается в переменную й в блоке Ва, копии Ва, достигаемой из Вз. и б) а) Рис. 9.32, Дублирование кода Поскольку количество путей экспоненциально зависит от количества условных ветвлений в программе, устранение всех избыточных вычислений может существенно увеличить размер оптимизированного код. Поэтому ограничимся в нашем рассмотрении методов устранения избыточности теми, которые могут вносить дополнительные блоки, но не дублируют части графа потока управления.
9.5.3 Отложенное перемещение кода Желательно, чтобы оптимизированная при помощи алгоритма устранения частичной избыточности программа обладала следующими свойствами. !. Все избыточные вычисления выражений, которые можно удалить без дублирования кода, должны быть удалены. 2. Оптимизированная программа не выполняет никаких вычислений, которые не выполняются при выполнении исходной программы.
774 Глава 9. Машинно-независимые оптимизации 3. Все выражения вычисляются в последний возможный момент. Последнее свойство является важным в силу того, что значения выражений, являющихся избыточными, обычно хранятся до их использования в регистрах. Максимально позднее вычисление значения минимизирует его время жизни — промежуток времени между его определением и временем его последнего использования, что минимизирует использование им регистра. Будем говорить об оптимизации устранения частичной избыточности с максимально возможной задержкой вычислений как об отложенном перемещении кода ()агу соде пюбоп).
Дпя улучшения интуитивного понимания задачи рассмотрим сначала частичную избыточность одного выражения вдоль одного пути. Для удобства при рассмотрении будем считать, что каждая инструкция представляет собой базовый блок, состоящий из одной этой инструкции. Полная избыточность Выражение е в блоке В является избыточным, если е вычисляется вдоль всех путей, достигающих В, и впоследствии его операнды не переопределяются. Пусть Я вЂ” множество блоков, каждый из которых содержит выражение е и которые делают е в В избыточным. Множество ребер, покидающих блоки из Я, с необходимостью образует разрез (сшзе~), который, будучи удален, отсоединит блок В от входа в программу.
Более того, вдоль путей, ведущих из блоков из Я к В, не переопределяются никакие операнды е. Частичная избыточность Если выражение е в блоке В только частично избыточно, алгоритм отложенного перемещения кода пытается сделать е в В полностью избыточным, помещая дополнительные копии выражения в графе потока. Если попытка успешна, оптимизированный граф потока также имеет множество базовых блоков Я, каждый из которых содержит выражение е и выходящие ребра которых являются разрезом между входом и блоком В. Аналогично случаю полной избыточности никакие операнды е не переопределяются вдоль путей, которые идут из блоков из Я к В. 9.5.4 Ожидаемость выражений Существует дополнительное ограничение, накладываемое на вносимые выражения, заключающееся в том, что никакие дополнительные операции не должны выполняться.
Копии выражений должны помещаться в точках программы, в которых выражение является ожидаемым (апас(развед). Мы говорим, что выражение 6+ с является ожидаемым в точке р, если все пути, ведущие из р, в конечном счете вычисляют значение выражения б+ с на основе значений 6 и с, доступных в этой точке. 9.5. Устранение частичной избыточности Рассмотрим устранение частичной избыточности вдоль ациклического пути В~ — Вз — — В„. Предположим, что выражение е вычисляется только в блоках В1 и В„и что операнды е не переопределяются в блоках вдоль указанного пути. Существуют входящие ребра, которые присоединяются к этому пути, и выходящие ребра, покидающие этот путь.
Выражение е не является ожидаемым при входе в блок В, тогда и только тогда, когда существует выходящее ребро, покидающее блок В, г' < у < и, приводящее к пути выполнения, не использующему значение е. Таким образом, ожидаемость ограничивает местоположения, в которые может быть вставлено выражение. Можно создать разрез, который включает ребро В, 1 — В, и делает е избыточным в В„, если е либо доступно, либо ожидаемо на входе в В,. Если е ожидаемо, но не доступно на входе в Во необходимо разместить копию выражения е на входящем ребре.
У нас есть выбор места размещения копий выражения, поскольку обычно существует несколько разрезов в графе потока, удовлетворяющих всем требованиям. В изложенном выше материале вычисления добавляются в ребро, входящее в интересующий нас путь, н, таким образом, выражение вычисляется как можно ближе к использованию без внесения избыточности. Заметим, что эти добавленные операции сами по себе могут быть частично избыточными по отношению к другим экземплярам того же выражения в программе. Такая частичная избыточность может быть устранена путем дальнейшего перемещения вычислений.
Итак, ожидаемость выражений ограничивает местоположения, в которые может быть помещено выражение; выражение не может быть размещено ранее, чем оно становится ожидаемым. Чем раньше размещается выражение, тем ббльшая избыточность может быть устранена, а среди всех решений, устраняющих одни и те же избыточности, то, которое вычисляет выражение как можно позже, минимизирует время жизни регистров, хранящих значения этих выражений. 9.5.5 Алгоритм отложенного перемещения кода Приведенный материал приводит нас к четырехшаговому алгоритму. На первом шаге используется ожидаемость для определения местоположений, в которые могут быть помещены выражения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
