MIT 29 Partial Redundancy Elimination

PDF-файл MIT 29 Partial Redundancy Elimination Конструирование компиляторов (52974): Статья - 7 семестрMIT 29 Partial Redundancy Elimination: Конструирование компиляторов - PDF (52974) - СтудИзба2019-09-18СтудИзба

Описание файла

PDF-файл из архива "MIT 29 Partial Redundancy Elimination", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

CS 4120 Lecture 29Partial Redundancy Elimination4 November 2011Lecturer: Andrew Myers1Cascaded dataflow analysesSome analyses lead to optimizations that enable more optimization. For example, CSE plus copy propagation can lead to more CSE. To avoid rerunning analyses after optimizations, we can design analyses to takeinto account optimizations that will be performed. For example, we can change live variable analysis totake into account the removal of dead code.

Compared to CSE, local variable numbering is also a cascadedanalysis, at least within the scope of an extended basic block.2Partial redundancy eliminationCSE eliminates computation of fully redundant expressions: those computed on all paths leading to a node.Partially redundant expressions are those computed at least twice along some path, but not necessarilyall paths. Partial redundancy elimination (PRE) eliminates these partially redundant expressions. PREsubsumes CSE and loop-invariant code motion.t=b+cXa=b+cXa=tt=b+cd=b+cYd=tYFigure 1: Partial redundancy eliminationFigure 1 shows an example of PRE. The computation b+c is redundant along some paths but not others.To make it fully redundant, we place computation of b+c onto earlier edges so that it has always beencomputed at each point where it is needed.2.1Lazy code motionThe idea of lazy code motion is to eliminate all redundant computations while avoid creating any unnecessary computation: computations are moved earlier in the CFG.

Further, we want to make sure that althoughthe computations are moved earlier in the CFG, they are postponed as long as possible, to avoid creatingregister pressure.The approach is to first identify candidate locations where the partially redundant expression couldhave been moved in order to make it fully redundant, without creating extra computations. Then amongthese candidates we choose the one that comes latest along each path that needs it.12.2Anticipated expressionsThe anticipated expressions analysis (also known as very busy expressions) find expressions that are neededalong every path leaving a given node. If an expression is needed along every path leaving the node, thenthere can be no wasted computation if the expression is moved to that node.This is a backward analysis, in which the dataflow values are sets of expressions and the meet operatoris ∩.Once we know the anticipated expressions at each node, we tentatively place computations of theseexpressions and use an available expressions analysis to find expressions that are fully redundant under theassumption that the anticipated expressions are computed everywhere anticipated.

These fully redundantexpressions are the expressions to which we can apply the PRE optimization.2.3Postponable expressionsAt this point we know some set of nodes where the expression can be moved, and we know where it isused. We need to pick a set of edges that separate these two parts of the CFG, and put the computation ofthe expression on those edges. We want to postpone the computation as long as possible. The postponableexpressions analysis finds expressions e that are are anticipated at program point p but not yet used: everypath from the start to p contains an anticipation of e and no use before p. This is a forward analysis withmeet operator ∩.Once postponable expressions have been computed, certain edges form a frontier where the expressiontransitions from postponable to not postponable. It is on these edges that the new node computing theexpressions is placed.2.

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