А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 132

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 132)

8.4.5 Циклы Конструкции языков программирования наподобие циклов якп11е, до-ткп11е и Гог, естественным образом приводят к циклам в программах. Поскольку почти каждая программа затрачивает основную часть времени работы на выполнение циклов, особенно важным становится вопрос генерации эффективного высококачественного кода для циклов. Многие преобразования кода зависят от идентификации "циклов" в графах потоков.

Мы говорим, что множество узлов Ь в графе потока является циклом, если выполняются следующие условия. 1. В Ь существует узел, именуемый входом в цикл, обладающий тем свойством, что никакие другие узлы не имеют предшественников вне Ь, т.е. любой путь из входа всего графа потока в любой узел в В проходит через вход в цикл, не совпадаюгций со входом в весь граф потока. 2. Кахслый узел в Л имеет непустой полностью содержащийся в Л путь ко входу в В.

Пример 8.9. Граф потока на рис. 8.9 имеет три цикла: 1. состоящий из единственного блока Вз, 2. состоящий из единственного блока Вв, 3. 1Вз, Вз, Ва ). 647 8.4. Базовые блоки и графы потоков Первые два цикла представляют собой отдельные узлы с петлями, т.е. ребрами, выходящими из узла и входящими в тот же узел. Например, Вз образует цикл с Вз в качестве входа в цикл. Вспомним, что второе требование заключается в наличии непустого пути из Вз в себя же. Таким образом, отдельный узел, например, Вз, у которого нет петли Вз -- Вз, циклом не является, поскольку не существует непустого пути из Вз в Вз, полностью лежащего в [Вз).

Третий цикл В = (Вз, Вз, В4) имеет вход в цикл Вз. Обратите внимание, что среди указанных трех узлов только у узла Вз есть предшественник Вм не входящий в множество В. Далее, каждый из этих трех узлов имеет непустой путь к Вз, полностью лежащий в Т. Например, Вз имеет путь Вз Вз Вл Вз с заданным свойством. с 8.4.6 Упражнения к разделу 8.4 Упражнение 8.4.1. На рис. 8.10 приведена простая программа умножения мат- риц. аког (з=0; з<пз з++) гог (3=0з 7<п; З++) с[э.][7] = 0.0; аког (з=Оз з<пз з++) аког (з=Оз 7<из з++) аког ()с=Оз )с<пз )с++) с[з][з] = с[з][з] + а[з.][)с]*Ь[)с][з]; Рис, 8.!О. Алгоритм умножения матриц а) Транслируйте эту программу в трехадресные инструкции, подобные рассмотренным в этом разделе.

Считается, что элементы матрицы являются 8-байтными числами и что матрица хранится построчно. б) Постройте граф потока для вашего кода из части а упражнения. в) Укажите циклы в графе потока из части б упражнения. Упражнение 8.4.2. На рис. 8.11 приведен код для подсчета количества простых чисел от 2 до и с использованием алгоритма решета Эратосфена для достаточно большого массива а,. Иначе говоря, в конечном счете а [г] равно ТЕ0Е тогда и только тогда, когда не существует простых чисел, не превышающих з/г', являющихся делителем г'.

Массив а инициализируется значениями ТК0Е, после чего элемент массива а [)1 устанавливается равным е АЬЯЕ, если мы находим делитель ). а) Транслируйте эту программу в трехадресные инструкции, подобные рассмотренным в этом разделе. Считается, что размер целого числа — 4 байт. 648 Глава 8. Генерация кода Йог (а=21 а<=пг з++) а(Х) = ТЕПЕ; СОПП~ = О! а = аЧгс(п); йог (8=2; 8<=в; з++) Н (а[а)) ( СОЦП~++! йог (З =2*8; з<=п! а ( З ) = еА|.ЯЕ; /* Х --- простое число */ 3 = з+х) /* Простое число не может */ /* быть кратно Х */ Рнс. 8.11. Код решета Эратосфена б) Постройте граф потока для вашего кода из части а упражнения. в) Укажите циклы в графе потока из части б упражнения.

8.5 Оптимизация базовых блоков 8.5.1 Представление базовых блоков с использованием ориентированных ациклических графов Многие важные методы локальной оптимизации начинаются с преобразования базового блока в ориентированный ациклический граф. В разделе 6.1.1 ориентированные ациклические графы использовались для прсдставлсния отдсльных выражений. Естественным образом эта идея распространяется и на набор выражений, образующих базовый блок. Ориентированный ациклический граф для базовых блоков строится следующим образом.

1. В ориентированном ациклическом графе имеются узлы для всех начальных значений переменных, появляющихся в базовом блоке. 2. Для каждой инструкции в в базовом блоке имеется связанный с ней узел Х ориентированного ациклического графа. Дочерними узлами Х являются Зачастую можно существенно снизить время работы кода, просто выполнив локальную оптимизацию внутри каждого блока. Большее можно получить при помощи глобальной оптимизации, которая рассматривает потоки информации между' базовыми блоками программы.

Эта сложная оптимизация, включающая множество различных методов, будет рассматриваться начиная с главы 9. 649 8.5. Оптимизация базовых блоков узлы, соответствующие инструкциям, являющимся последними до в опре- делениями операндов, использующихся в в. 3. Узел Х помечается оператором из в; кроме того, к узлу присоединяется список переменных, последнее определение которых находится в блоке. 4. Ряд узлов помечается как выходные (оп1рп1 подеа).

Это узлы„переменные в которых живые при выходе из базового блока, т.е. их значения могут использоваться позже, в другом блоке графа потока. Вычисления этих "живых переменных'" являются предметом анализа глобального потока, рассматриваюшегося в разделе 9.2.5. Представление базового блока при помощи ориентированного ациклического графа позволяет нам выполнить ряд улучшающих преобразований кода, представленного блоком. а) Можно устранить локальные общие подвыражения (1оса! сопппоп зцЬех- ргеаз1оп), т.е. команды, которые вычисляют уже вычисленные значения. б) Можно устранить неиспользуемый, или мертвый, код (деад соде), т.е.

команды, вычисляющие никогда нс использующиеся значения. в) Можно переупорядочить инструкции, не зависящие друг от друга; такое псрсупорядочение может снизить время хранения временного значения в регистре. г) Можно применить алгебраические законы для переупорядочения операндов трехадресных команд, что иногда приводит к упрощению вычислений. 8.5.2 Поиск локальных общих подвыражений Общие подвыражения могут быть обнаружены путем выяснения при добавлении нового узла М, нет ли уже существующего узла Х с теми же дочерними узлами в том же порядке и с теми же операторами.

Если такой узел есть, то Х вычисляет то же самое значение, что и ЛХ, и может быть использован вместо него. Эта технология уже рассматривалась в разделе 6.1.1 в качестве метода "номера значения" для поиска общих подвыражений. Пример 8.10. Ориентированный ациклнческий граф для блока а=Ь+с Ь = а — с1 с=Ь+ с с1=а — д ббО Глава 8.

Генерация кода приведен на рис. 8.12. При построении узла для третьей инструкции с = Ь + с мы обнаруживаем, что использование Ь в Ъ+с обращается к узлу с меткой — на рис. 8.12, поскольку это последнее определение Ь. Таким образом, нас не должны волновать значения, вычисляемые в первой и третьей инструкциях. со Рис.

8.! 2. Ориентированный ациклнческий граф для базового блока из примера 8.10 Однако узел, соответствующий четвертой инструкции, с1 = а — с1, имеет оператор — и узлы а н Ио в качестве дочерних. Поскольку оператор и дочерние узлы те же, что и у узла, соответствующего второй инструкции, мы не создаем этот узел, а просто добавляем с1 к узлу с меткой —. с Может показаться, что, поскольку в ориентированном ациклическом графе на рис. 8.12 имеется только три узла, не являющихся листьями, базовый блок на рис. 8.10 можно заменить блоком только из трех инструкций. В действительности если Ь на выходе из блока не является живой, то нам не надо вычислять значение этой переменной и можно использовать с1 для получения значения, представленного узлом с меткой — на рис. 8.12.

В этом случае блок превращается в а=Ь+с с1 = а — с1 с=с1+с Однако если на выходе из базового блока живыми являются и Ь, и с1, то четвертой инструкцией должно быль копирование значения из одной переменной в другую'. Пример 8.11. При поиске общих подвыражений мы ищем выражения, которые гарантированно вычисляют одно и то же значение, независимо от того, как это В общем случае следует быть осторожным при выборе имен переменных во время реконструкции кода из ориентированного апиклического графа. Если переменная х определена дважды или если выполняется одно присваиванис и при этом используется и ее начальное значение хе, то следует убедиться, что значение х не изменяется до тех пор, пока не будут выполнены все использования узла, хранящего предыдущее значение х.

Характеристики

Список файлов книги