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

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

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

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

Ее верхним элементом является съгзег, а нижним — млс, т.е. наибольшим значением в частичном порядке является 1дЧПЕР, а наименьшим — МЛС. Значения констант неупорядочены, но все они меныпе глчпеР и больше млс. Как говорилось в разделе 9,3.1, сбор двух значений представляет собой их наибольшую нижнюю границу. Таким образом, для всех значений с ГЛ4ПЕЕ Л с — с И ХЛС Л В вЂ” ХАС Для любой константы с сЛс=с Для двух различных констант сз и сз с~ Л сг = НАС Значение потока данных в этой структуре представляет собой отображение каждой переменной программы на одно из значений в полурешетке констант. Значение переменной с в отображении ги обозначается как т (с). 762 Глава 9.

Машинно-независимые оптимизации Рис. 9.25. Полурешетка, представляющая возможные "значения" одной целочисленной переменной 9.4.2 Сбор в структуре распространения констант Полурешетка значений потока данных представляет собой произведение полурешеток наподобие показанной на рис. 9.25, по одной для каждой переменной.

Таким образом, гп < ш' тогда и только тогда, когда для всех переменных и т(е) < гп'(о). Или т Л т' = т", если для всех переменных о выполняется соотношение тн (е) = т(е) Л гпт (и). 9.4.3 Передаточные функции для структуры распространения констант Далее мы полагаем, что базовый блок содержит только одну инструкцию. Передаточные функции для базовых блоков, состоящих из нескольких инструкций, могут быть построены путем композиции функций, соответствующих отдельным инструкциям. Множество Г состоит из некоторых передаточных функций, которые принимают отображения переменных на значения в решетке констант и возвращают другие отображения данного вида.

г содержит тождественную функцию, которая получает в качестве аргумента и возвращает одно и то же отображение. Кроме того, Г содержит константную передаточную функцию для входного узла. Эта передаточная функция возвращает, независимо от полУченного аРгУмента, отобРажение то, где пзо 1н) = глчппг дла всех переменных ц. Такое граничное условие не лишено смысла, поскольку перед началом выполнения программы нет определения ни одной переменной. В общем случае пусть Г", — передаточная функция для инструкции а и пусть т и т' представляют значения потока данных, такие, что т' = ); (гп).

Мы опишем Гя в терминах отношений между гп и т'. 1. Если а не является инструкцией присваивания, то ~, представляет собой тождественную функцию. 763 9.4. Распространение констант 2. Если л — присваивание переменной х, то для всех переменных в ф х выполняется соотношение т'(и) = т(п), где т'(х) определяется следующим образом. а) Если в правой части инструкции л находится константа с, то т'(х) = = с. б) Если в правой части инструкции л находится выражение типа у+ л'~, то т (у) + т (л), если т (у) и т (л) — константные значения, т'(х) = млс, если либо т (х), либо т, (р) является млс, оМОЕГ в противном случае.

в) Если в правой части инструкции л находится любое иное выражение (например, вызов функции или присваивание посредством указателя), то т'(х) = млс. 9.4.4 Монотонность структуры распространения констант Покажем, что структура распространения констант монотонна. Во-первых, можно рассмотреть влияние функции ~, на единственную переменную. Во всех случаях, кроме 2, б, ~, либо не изменяет значение т(х), либо изменяет отображение на возвращающее константу или млс. Понятно, что в этих случаях ~, является монотонной.

В случае 2, б влияние ~, протабулировано на рис. 9.26. В первом и втором столбцах представлены возможные входные значения у и л; в последнем столбце показаны выходные значения х. Значения в каждом столбце или подстолбце упорядочены от наибольшего к наименьшему. Чтобы показать, что функция монотонна, убедимся, что для каждого из возможных значений у значение х не возрастает с уменьшением значения л. Например, если у представляет собой константное ЗНаЧЕНИЕ См а ЗНаЧЕНИЕ Л ИЗМЕНЯЕТСЯ От иМПЕР ЧЕРЕЗ Сз К МЛС, тО ЗНаЧЕНИЕ Х соответственно изменяется от смпЕЕ через с1 + сз к млс. Эту проверку можно выполнить для всех значений у.

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

764 Глава 9. Машинно-независимые оптимизации Рис. 9.2О, 11ерсдаго шая функция распространения коистаиг для х = у+я 9.4.5 Недистрибутивность структуры распространения констант Сгруктура распространения констант монотонна, но не днстрибутивна, г.е. итеративное мг1'-решение безопасно, но может быть меньше моР-решения. Приведенный далее пример доказывает недистрибутивность рассматриваемой структуры. Пример 9.22. В программе на рис.

9.27 т. и у устанавливаются равными 2 и 3 в базовом блоке Вы и 3 и 2 соответственно в базовом блоке Вз. Мы знаем, что независимо от выбранного пути значение г в конце блока 13з равно 5. Однако итеративный алгоритм не сможет обнаружить этот факт. Он применит оператор сбора на входе Вз и получит значения х и р, равные АгАС. Поскольку сложение двух нлс дает млс, алгоритм 9.21 на выходе из программы даст з =- нлс. Этот результат безопасен, но не точен. Алгоритм 9.2! не в состоянии отследить корреляцию, заключающуюся в том„что когда х равно 2, то у равно 3, и наоборот. Можно, но гораздо более высокой ценой, использовать более сложную структуру, которая отслеживает все возможные равенства, которые могут выполняться между парами выражений, включающими переменные программы. Такой подход рассматривается в упражнении 9.4.2.

Можно объяснить эту потерю точности недистрибутивностью структуры распространения констант теоретически. Пусть )ы 2з и гз — передаточные функции, представляющие блоки Вы Вз н Вз соответственно. Как показано на рис. 9.28, Ь (Л (~по) А Ь (тпо)) < Хз (Л (гпо)) А,)з (Б 1'гпо)) А это показывает недистрибутивность рассматриваемой структуры. 7бб 9.4. Распространение констант Рис.

9.27. Пример, демонстрирующий, что структура распространения констант недистрибутивна Рис. 9.28. Пример недистрибутивности передаточных функций 9.4.6 Интерпретация результатов Значение гл ювв используется в итеративном алгоритме с двумя целями: для инициализации входного узла и инициализации внутренних точек программы перед итерациями.

Смысл этих двух случаев немного различен. В первом случае утверждается, что в начале выполнения программы значения переменных не определены; во втором — что из-за недостатка информации в начале итеративного процесса мы аппроксимнруем решение верхним элементом глчпеи В конце итеративного процесса переменные на выходе из входного блока сохраняют значение гдчпер, поскольку оит ~Вход] никогда не изменяется. Значения глчпкр могут оказаться у переменной и в других точках программы. Если это происходит, значит, для данной переменной не нашлось определений на 766 Глава 9. Машинно-независимые оптимизации путях, ведущих к данной точке программы.

Заметим, что в силу определения оператора сбора при наличии хотя бы одного пути, на котором имеется определение переменной, достигающее рассматриваемой точки программы, эта переменная не будет иметь значение ~ЛЧ1ЗПР. Если все определения, достигающие точки программы, имеют одно и то же константное значение, то переменная рассматривается как константа, даже если она может оказаться не определена на некотором пути. Полагая, что программа корректна, алгоритм может найти большее количество констант, т.е.

для повышения эффективности программы алгоритм выбирает некоторые значения для переменных, которые могут быть не определенными. Такое изменение правомерно в большинстве языков программирования, поскольку не определенная переменная может принимать любое значение. Если семантика языка требует, чтобы все не определенные переменные принимали некоторое конкретное значение, то мы должны соответствующим образом изменить формулировку задачи.

Если же нас интересует поиск в программе переменных, которые могут быть не определены, то для получения такого результата можно переформулировать задачу анализа потока данных (см. упражнение 9.4.1). Пример 9.23. На рис. 9.29 значения х на выходе из базовых блоков Вз и Вз— соответственно 10 и глвпк. Поскольку имжк л 10 = 10, значение х на входе в блок Вя равно 10. Таким образом, в блоке Вы где используется х, его можно заменить на 1О.

Если выполнение пойдет по пути Вз — Вз — Вя — Вы то значение х, достигающее базового блока Вы будет не определенным. Таким образом, представляется некорректным замена использования х на 10. В, Рис. 9.29. Сбор глчпвг и константы 767 9.4. Распространение констант Однако если предикат Я не может быть ложен, если истинен предикат 17', то такой путь никогда не будет пройден. Программист может знать об этом, но такой вывод может оказаться за пределами возможностей анализа потоков данных.

Таким образом, если считать, что программа корректна и что все переменные определены до их использования, то вполне корректно и то, что значение х при входе в базовый блок Вз может принимать только значение 10. Если программа некорректна, то выбрать 10 в качестве значения х, — в любом случае не хуже, чем позволить этой переменной принимать некоторое случайное значение. и 9.4.7 Упражнения к разделу 9.4 Упражнение 9.4.1. Предположим, что мы хотим обнаружить все переменные, которые могут быть не инициализированными вдоль некоторого пути к рассматриваемой точке. Каким образом следует модифицировать структуру из этого раздела для поиска таких ситуаций? Упражнение 9.4.2. Интересная и мощная структура анализа потока данных получается, если представить, что область определения 1" включает все возможные разбиения выражений, так что два выражения принадлежат одному и тому же классу тогда и только тогда, когда они имеют одинаковые значения вдоль любого пути к рассматриваемой точке.

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

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

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