Тема 06(2016)Глобальная нумерация значений (Лекции), страница 3
Описание файла
Файл "Тема 06(2016)Глобальная нумерация значений" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Порядок обработки определяетсядеревом доминаторовv #valB1(v)B2B3B4 Обработка блока B1.Переменным u0, v0, и w0в качестве номеров значенийбудут присвоены их SSA-именаu0, v0, и w0u0 u0v0 v0w0 w0x0y0u1x1y1u2x2y2z0u3B2B3B4B1B2u0 a0 + b0 x0 c0 + d0v0 c0 + d0 y0 c0 + d0w0 e0 + f0B3B4u1 a0 + b0 u2 (u0, u1)x1 e0 + f0 x2 (x0, x1)y1 e0 + f0 y2 (y0, y1)z0 u2 + y2u3 a0 + b0После обработки B1336.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Обработка блока B2.B2Выражение c0 + d0 определенов блоке B1, доминаторе B2.Поэтому в B2 можно удалитьоба присваивания, присвоивx0 и y0 номер значения v0.Необходимо такжеподготовится к обработке блокаB4, заменив параметры функций u0, x0, и y0 номерамиих значений u0, v0, и v0.vu0v0w0x0y0u1x1y1u2x2y2z0u3#val(v)u0v0w0v0v0B3B4B1B2u0 a0 + b0v0 c0 + d0w0 e0 + f0B3B4u1 a0 + b0 u2 (u0, u1)x1 e0 + f0 x2 (v0, x1)y1 e0 + f0 y2 (v0, y1)z0 u2 + y2u3 a0 + b0После обработки B2346.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Обработка блока B3.Все три выражения в правыхчастях уже вычислены в B1,B2vдоминаторе B3Поэтому переменным u1, x1 и y1присваиваются номеразначений u0, w0 и w0соответственнои удалить присваивания.В заключение обработки B3,необходимо заполнить вторыепараметры -функцийиз B4 номерами значенийu0, w0 и w0.u0v0w0x0y0u1x1y1u2x2y2z0u3#val(v)u0v0w0v0v0u0w0w0B3B4B1B2u0 a0 + b0v0 c0 + d0w0 e0 + f0B3B4u2 (u0, u0)x2 (v0, w0)y2 (v0, w0)z0 u2 + y2u3 a0 + b0После обработки B3356.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Обработка блока B4. Сначала исследуются-функции.
Это возможно, таккак выполнены условия :(1) все дети B1 по деревудоминаторов (B2, B3) ужеобработаны;(2) в B4 не входит обратных дуг.-функция, определяющая u2,бессмысленна: оба еепараметра равны u0.-функция исключается, а u2присваивается номер значенияu0.B2v#val(v)u0v0w0x0y0u1x1y1u2x2y2z0u3u0v0w0v0v0u0w0w0u0B3B4B1B2u0 a0 + b0v0 c0 + d0w0 e0 + f0B3B4x2 (v0, w0)y2 (v0, w0)z0 u2 + y2u3 a0 + b0После обработки первой -функции366.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Обработка блока B4.B2 Вторая -функция имеетпараметры v0 и w0.
Это первоевхождение -функции с такимиvu0v0w0присваивается ее SSA-имя.x0y0 -функция, определяющая y2u1избыточна, так как y2 равно x2.x1Поэтому эта -функцияy1исключается, а y2 присваивается u2x2номер значения x2.y2z0u3параметрами. Ее значению x2в качестве номера значения#val(v)u0v0w0v0v0u0w0w0u0u0x2B3B4B1B2u0 a0 + b0v0 c0 + d0w0 e0 + f0B3B4x2 (v0, w0)z0 u2 + y2u3 a0 + b0После обработки -функций376.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Обработка блока B4.B2 Обработка присваиваний. После подстановки вместокаждого операнда номера егозначения для правой частиприсваивания z0 получитсяномер значения # = u0 + x2. Присваивание u3 избыточно(номер значения его правойчасти такой же, как у правойчасти присваивания u0 в блокеB1.
Поэтому это присваиваниеисключается, а u3присваивается номер значенияu0.v#val(v)u0v0w0x0y0u1x1y1u2x2y2z0u3u0v0w0v0v0u0w0w0u0u0x2#u0B3B4B1B2u0 a0 + b0v0 c0 + d0w0 e0 + f0B3B4x2 (x0, x1)z0 u2 + y2После обработки B4386.4 Алгоритм глобальной нумерации значений6.4.5 Заключительные замечания Алгоритм глобальной нумерации значений была описана дляпрограмм, уже переведенных в SSA-форму. Однако, можно включитьнумерацию значений в процесс конструирования SSA. В результате включения нумерации значений в процессконструирования SSA повышается производительность оптимизатора,так как сокращается объем выполняемой работыуменьшается размер SSA-формы программы. Алгоритм глобальной нумерации значений объединяется с алгоритмомпереименования переменных при построении SSA-формы.
В данномкурсе этот объединенный алгоритм не рассматривается.39.