А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 156
Текст из файла (страница 156)
Чтобы избежать перечисления бесконечного количества выражений, можно представить Ъ' при помощи перечисления только минимальных пар эквивалентных выражений. Например, если мы выполняем инструкции а=Ь с=а+с1 то минимальное множество эквивалентностей представляет собой (а = Ь, с=а+И). Отсюда следуют прочие эквивалентности, такие как с = Ь+ И и а+ е= — Ь+ е, но их не надо перечислять явно. а) Каким должен быть оператор сбора для такой структуры? б) Разработайте структуру данных для представления значений области определения и алгоритм реализации оператора сбора. в) Какие функции связаны с инструкциями? Какое влияние должна оказывать инструкция наподобие а = Ь+с на разбиение выражений (т.е.
на значение в Ъ)? г) Является ли данная структура монотонной, дистрибутивной? 768 Глава 9. Машинно-независимые оптимизации 9.5 Устранение частичной избыточности В этом разделе мы подробно рассмотрим минимизацию количества вычислений выражений, т.е. рассмотрим все возможные последовательности выполнения в графе потока и узнаем, сколько раз вычисляется выражение, подобное к э р. Выполняя перемещения кода и при необходимости сохраняя результат во временной переменной, зачастую можно снизить количество вычислений такого выражения вдоль многих путей выполнения, при этом ни по одному из возможных путей количество вычислений не увеличится. Заметим, что количество различных мест, где выполняется вычисление х+ у, может и увеличиться, но это относительно неважно, поскольку снизится количество вычислений выражения х + Гд Применение разработанного в этом разделе преобразования кода повышает производительность получающегося кода, поскольку, как вы увидите, операция никогда не применяется, если только она не абсолютно необходима.
Каждый оптимизирующий компилятор реализует нечто наподобие рассматриваемого здесь преобразования, даже если прн этом использует "менее агрессивный' алгоритм по сравнению с рассматривающимся здесь. Однако имеется и иная причина рассмотреть эту задачу. Поиск места или мест в ~рафе потока для вычисления каждого выражения требует четырех различных видов анализа потока данных. Таким образом, изучение "устранения частичной избыточности", как называется минимизация количества вычислений выражений, существенно способствует пониманию той роли, которую анализ потоков данных играет в компиляторе. Избыточность в программе существует в различных формах.
Как говорилось в разделе 9.!.4, она может быть в виде общих подвыражений, когда несколько вычислений выражения дают одно и то же значение. Она может быть и в виде выра>кения, инвариантного относительно цикла, которое вычисляет одно и то же значение на каждой итерации цикла. Избыточность может быть частичной, если она обнаруживается вдоль некоторых, но не всех, путей. Общие подвыражения и выражения. инвариантные относительно цикла, можно рассматривать как частные случаи частичной избыточности; таким образом, для устранения различных видов избьпочности можно разработать единый алгоритм устранения частичной избыточности. Далее мы рассмотрим различные типы избыточности, а затем поставим обобщенную задачу устранения частичной избыточности и представим алгоритм ее решения. Этот алгоритм представляет особый интерес, поскольку включает решение нескольких задач потоков данных как в прямом.
так и в обратном направлениях. 769 9.5. Устранение частичной избыточности 9.5.1 Источники избыточности На рис. 9.30 проиллюстрированы три вида избыточности: общие подвыражения, выражения, инвариантные по отношению к циклу, и частично избыточные выражения. На рисунке показан код как до, так и после выполнения каждого вида оптимизации. в, в, а) Рис. 9.30. Примеры а) глобального общего подвыражения; б) перемещения кода, инвариантного по отношению к циклу; в) устранения частичной избыточности Глобальные общие подвыражения На рис. 9.30, а выражение 6+ с, вычисляемое в блоке В4, избыточно: оно уже вычислено при достижении блока В4, независимо от того, каким именно путем поток управления достигает блока В4. Как видно из приведенного примера, значение выражения может отличаться на разных путях.
Можно оптимизировать приведенный код, сохраняя результат вычисления 6+ с в блоках Вз и Вз в одной и той же временной переменной, скажем, 1, и вместо повторного вычисления выражения 6+ с присваивая значение 6 переменной е в блоке В4. При наличии 770 Глава 9. Машинно-независимые оптимизации Поиск "глубоких" общих подвыражений Анализ доступных выражений для определения избыточных выражений работает только с текстуально идентичными выражениями.
Например, применение устранения общих подвыражений распознает, что с1 в фрагменте кода с1 = Ь + с; а = с1 + с1; имеет то же значение, что и С2 в с2 = Ь + с; е = с2 + с1; при условии, что переменные 6 и с не изменялись между этими фрагментами. Однако данный анализ не в состоянии определить идентичность а и е. Найти такие "глубокие" общие выражения можно путем повторного применения устранения общих подвыражений до тех пор, пока на очередной итерации не будет найдено ни одного нового общего подвыражения.
Можно также воспользоваться структурой из упражнения 9.4.2 для поиска "глубоких'* подвыражений. присваивания переменным 6 или с после последнего вычисления 6+ с, но до блока В4 выражение в блоке В4 избыточным не является. Формально мы говорим, что выражение 6+ с является (полностью) избыточным в точке р, если в этой точке имеется доступное в смысле раздела 9.2.б выражение.
Иначе говоря, выражение 6+ с вычисляется вдоль всех путей, достигающих р, и переменные 6 и с не переопределяются после того, как вычислено последнее из выражений. Условие неизменности 6 и с является необходимым, потому что, хотя выражение 6+ с выполняется перед достижением точки р текстуально, значение 6+ с, вычисленное в точке р, может оказаться иным из-за возможного изменения операндов. Выражения, инвариантные относительно циклов На рис.
9.30, б показан пример выражения, инвариантного относительно цикла. Выражение Ь+ с является инвариантом в предположении, что в цикле не изменяются ни переменная Ь, ни переменная с. Эту программу можно оптимизировать путем замены таких повторных вычислений единственным вычислением за пределами цикла. Результаты вычисления присваиваются временной переменной, скажем, г, а затем выражение в цикле заменяется переменной 1. Здесь есть один момент, на который следует обратить особое внимание при таком "перемещении кода". Мы не должны выполнять ни одну команду, которая не выполняется без оп- тн 9.5. Устранение частичной избыточности тимизации. Например, если можно выйти из цикла без выполнения инструкции, являющейся инвариантом относительно цикла, то такая инструкция не должна выноситься за пределы цикла.
Тому есть две причины. 1. Если инструкция генерирует исключение, то в результате мы получим генерацию исключения там, где его могло бы и не быть. 2. При выходе из цикла без вычисления "оптимизированная" программа оказывается менее эффективной, чем исходная. Чтобы гарантировать возможность оптимизации выражений, являющихся инвариантами относительно циклов и')н1е, компилятор обычно представляет инструкцию мМ1ес 1 Я; ) так же, как и инструкцию Н с 1 гереас Я; ипс11 пос с; При этом выражение, являющееся инвариантом относительно цикла, может быть вынесено и располагаться непосредственно перед конструкцией гереа)-ипй1. В отличие от устранения общих подвыражений, когда вычисление избыточного выражения просто опускается, устранение выражений, инвариантных относительно циклов, выполняет их перенос изнутри цикла наружу.
Поэтому такая оптимизация известна как перемещение кода, инвариантного относительно цикла (!оор-)пчайапг соде пюйоп). Эту оптимизацию может потребоваться применить повторно, поскольку когда выясняется, что переменная содержит значение, инвариантное относительно цикла, то таковыми же могут оказаться и выражения, использующие эту переменную. Частично избыточные выражения Пример частично избыточного выражения приведен на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
