Главная » Просмотр файлов » MIT 25 Reaching defnitions_ webs_ SSA

MIT 25 Reaching defnitions_ webs_ SSA (798430), страница 2

Файл №798430 MIT 25 Reaching defnitions_ webs_ SSA (MIT 25 Reaching defnitions_ webs_ SSA) 2 страницаMIT 25 Reaching defnitions_ webs_ SSA (798430) страница 22019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Along thesetwo paths, a is defined only at x and y.This rule implies that z must be a node with multiple predecessors, because otherwise two paths wouldhave to share the single predecessor and therefore would not be disjoint. It similarly implies that z can alsoappear in the middle of one of the paths from x and y to z, but cannot be in the middle of both.Although path convergence gives us a clear criterion for when to insert a φ-function, it is expensive toevaluate directly. SSA conversion is therefore usually done using control flow analysis, which we will talkabout shortly.4 Conditional constant propagationConstant propagation and constant folding together form an important optimization that moves computations to compile time rather than run time, that allows deletion of code that is never executed, and thatsimplifies the programs enabling further optimizations.

Conditional constant propagation is a version ofconstant propagation that takes advantage of different information along different exit edges from conditional nodes. Sparse conditional constant propagation, introduced by Wegman and Zadeck, takes advantageof SSA to keep track of less information about each node.

Although constant propagation, copy propagation, constant folding, and unreachable code elimination can achieve similar effects when used together,conditional constant propagation enables strictly more optimization.The goal of conditional constant propagation is to simplify code like the following:x = 1if (x<2) {y = 5+x} else {y = f(x)}z = y*yinto code that uses constants:x=1y=6z=364⊤...

-2-1012...⊥Figure 2: Conditional constant propagation latticeThe assignments to x and y may also be dead code at this point. Notice that we have removed theconditional entirely because its guard expression is constant, and this facilitates the optimization of theassignment to z.The analysis is a forward analysis. For each variable in the program, we keep track of its possible valuesusing the lattice in Figure 2, due to Killdall. The value > represents an undefined variable, or one that wehave not yet seen a definition for. The value ⊥ represents an “overdefined” variable, one that has more thanone possible value and that therefore cannot be predicted at compile time.

Therefore, for a given constantc, merging a path where no definition has been seen yet with one on which a constant value c has been seenyields c u > = c since it’s safe to replace an undefined value with c. Two different constant values combineto yield ⊥ (that is, c1 u c2 = ⊥), and once a variable is non-constant, it remains so: ⊥ u c = ⊥.We can keep track of the possible values of a whole set of k variables x1 , . . . , xk in a tuple of elementsof this lattice, which we will write (v1 , . . .

, vk ). The tuple of elements is of course itself a lattice with topelement (>, . . . , >).In the non-SSA representation, we need to keep track of this tuple of elements at every point in the code.In the SSA representation, there is only one definition of each variable, so a variable is either constant ornot; we can keep track of a single tuple (v1 , . . . , vk ) for the entire analysis.In either representation, we want to keep track of one more piece of information for each node: whetherthe node is unreachable. We will let u represent unreachability of a node, with u = > meaning the nodeis unreachable, and u = ⊥ meaning it may be reachable.

Treating > as “true” and ⊥ as “false”, the meetoperation is conjunction: u1 u u2 = u1 ∧ u2 . For the non-SSA representation, the dataflow values will betuples (u, (v1 , . . . , vk )), with the usual componentwise lattice ordering lifted from the orderings on u and vi .The transfer functions Fn (u, (~v )) are defined as follows:~ because we need not consider definitions made by unreachable code.• F (>, (~v )) = (>, (>))• F (⊥, (v1 , .

. . , vk ))) = (v10 , . . . , vk0 ) where for all i, vi0 = vi unless n defines xi . In this case the assignmentxi = e is interpreted abstractly using the current values for the variables occurring in e. For example,2 + 2 = 4, but 2 + ⊥ = ⊥, and 2 + > = >, and f (x) = ⊥.• One exception to the previous case is conditionals. For a conditional node containing if e, the analysis interprets e abstractly as in the previous case. If the result is ⊥, the same information is propagatedon both exiting edges.

But if the result is true or false, the information propagated on the edge not~ because that code is unreachable from this if.taken is (>, (>)),For example, applying this (non-sparse) analysis to the example from earlier, we obtain the result shownin Figure 3.Notice that the assignment y = f (x) is marked as unreachable, so it can be removed along with theconditional. Once the analysis completes, all definitions xi = e for which vi = c on the outgoing edge canbe replaced with x = c. Dead code removal can then be used to remove unnecessary assignments.When the analysis is done in SSA form, we keep track of just one tuple of values (v1 , . . . , vk ), and onlyunreachability is propagated through the CFG.

Dead code removal can then be performed easily in themanner outlined earlier, assuming that use sets are updated as we rewrite definitions to use constants.5x=1(⊥,(1,⊤,⊤))if x<2(⊥,(1,⊤,⊤))(⊤,(⊤,⊤,⊤))y=5+xy=f(x)(⊥,(1,6,⊤))(⊤,(⊤,⊤,⊤))z=y*y(⊥,(1,6,36))Figure 3: Example of conditional constant propagationx=2y=1x=1y=2(2,1,⊤)x=2y=1(2,1,⊤)(1,2,⊤)⊓(⊥,⊥,⊤)x=1y=2z = x + y(1,2,⊤)z = x + y(2,1,3)(1,2,3)⊓z = x + y(⊥,⊥,⊥)(⊥,⊥,3)Figure 4: Conditional constant propagation does not give the meet-over-paths solution4.1Solution qualityIn contrast to the analyses we’ve seen earlier, conditional constant propagation does not achieve a MOPsolution.

The reason is that the transfer functions are not distributive. To see this, consider Figure 4, inwhich the meet is taken both before a join point in control flow (corresponding to the way that dataflowanalysis works) and after (corresponding to the meet-over-paths criterion). Nevertheless, it’s an importantand effective optimizaton.6.

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

Тип файла
PDF-файл
Размер
237,28 Kb
Тип материала
Высшее учебное заведение

Список файлов статьи

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