Главная » Просмотр файлов » А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий

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

Файл №1114947 А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий) 156 страницаА.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947) страница 1562019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. В отличие от устранения общих подвыражений, когда вычисление избыточного выражения просто опускается, устранение выражений, инвариантных относительно циклов, выполняет их перенос изнутри цикла наружу.

Поэтому такая оптимизация известна как перемещение кода, инвариантного относительно цикла (!оор-)пчайапг соде пюйоп). Эту оптимизацию может потребоваться применить повторно, поскольку когда выясняется, что переменная содержит значение, инвариантное относительно цикла, то таковыми же могут оказаться и выражения, использующие эту переменную. Частично избыточные выражения Пример частично избыточного выражения приведен на рис.

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

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее