Тема 06(2016)Глобальная нумерация значений (Лекции), страница 2
Описание файла
Файл "Тема 06(2016)Глобальная нумерация значений" внутри архива находится в папке "Лекции". PDF-файл из архива "Лекции", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Так как этонеобходимо учесть в алгоритме нумерации значений, алгоритмусложнится.Описанного затруднения легко избежать, если выполнятьнумерацию значений для суперблоков в SSA-форме:тогда каждое имя будет определяться только один раз, иописанные конфликты невозможны.176.2. Нумерация значений в суперблоках6.2.4 Контекстные таблицы значений и SSA-формаB1 m0 +, a0, b0 B2 p0 +, c0, d0B3 r2 (r0, r1)n0 +, a0, b0r0 +, c0, d0y0 +, a0, b0z0 +, c0, d0B4q0 +, a0, b0r1 +, c0, d0B7e2 (e0, e1)u2 (u0, u1)v0 +, a0, b0w0 +, c0, d0x0 +, e2, f0B5e0 +, b0, 18s0 +, a0, b0u0 +, e0, f0B6e1 +, b0, 17t0 +, c0, d0u1 +, e1, f0B1B2 SSA-форма обладает двумя важнымисвойствами:(1) каждое имя определяется только водной инструкции(2) каждое использование значенияссылается только на одно определение.B4B5B6B7B3186.2.
Нумерация значений в суперблоках6.2.4 Контекстные таблицы значений и SSA-формаB1m0 +, a0, b0n0 +, a0, b0B2p0 +, c0, d0r0 +, c0, d0B3r2 (r0, r1)y0 +, a0, b0z0 +, c0, d0B4q0 +, a0, b0r1 +, c0, d0B5e0 +, b0, 18s0 +, a0, b0 u0 +, e0, f0B6e1 +, b0, 17t0 +, c0, d0 u1 +, e1, f0B7e2 (e0, e1)u2 (u0, u1)v0 +, a0, b0w0 +, c0, d0x0 +, e2, f0B1B2 Инструкции, удаляемые алгоритмом анализасуперблоков, выделены подчеркиванием ицветом Инструкции, помеченные , не удаляютсяалгоритмом локальной нумерации значений.B4B5B6B7B3196.2.
Нумерация значений в суперблоках6.2.5 Оценка расширенного алгоритма локальной нумерации значенийРасширенный алгоритм локальной нумерации значений отличноработает внутри суперблока. Однако, при переходе от одногосуперблока к другому он пропускает некоторые избыточности.В рассматриваемом примере:B3 и B7 составляют отдельные суперблоки, поэтомувычисления a0 + b0 и c0 + d0 в блоках B7 и B3не рассматриваются алгоритмом вместе с вычислениямив других блоках и не распознаются как избыточные,хотя на самом деле они избыточны.Выражение e + f является доступным в блоке B7:e + f вычисляется на любом пути, достигающем блока B7,и ни e, ни f не переопределяются до вычисления в B7.Потому оно избыточно и будет исключено, хотя этоневерно.Причина: расширенный алгоритм не может установить,20что e имеет разные номера значений в блоках D и E.6.2.
Нумерация значений в суперблоках6.2.5 Оценка расширенного алгоритма локальной нумерации значенийНесмотря на перечисленные недостатки, расширенный алгоритмзаслуживает применения:он позволяет найти намного больше избыточностей, чемлокальный алгоритм, за минимальные дополнительныенакладные расходы.Использование механизма контекстно-ориентированных ТЗпозволяет существенно сократить накладные расходы наработу с суперблоками.216.3 Глобальная нумерация значений6.3.1 Необходимость обработки точек сбора Расширенный алгоритм локальнойнумерации значений пропускаетнекоторые избыточности, так как онудаляет всю таблицу значений, когдадостигает блока, имеющего в ГПУболее одного предшественникаB1B2B4B5(в нашем примере это блоки B7 и B3).B7 Нужен алгоритм, который можетраспространять информацию черезточки сбора графа потока(в нашем примере это переходыB6B3от B5 и B6 к B7, и от B2 и B7 к B3).226.3 Глобальная нумерация значений6.3.2 Проблема точек сбора Для нумерации значений в блоке B7,расширенный алгоритм не можетB1использовать ТЗ для пути {B1, B4, B5},так как при этом не учитываетсяпуть от B6 к B7 .B2B4Алгоритм не может использовать ТЗдля пути {B1, B4, B6}, так как при этомB5не учитывается путь от B5 к B7.B6B7Алгоритм не может слить ТЗ дляB5 и B6, так как операция слиянияунифицирует номера значений,полученные вдоль непересекающихсяпутей.
При унификации неучитывается, что, например, вычисленияe + f в B5 и B6 могут иметь разныеномера значений.B3236.3 Глобальная нумерация значенийB16.3.3 Обработка точек сбора ТЗ, которую алгоритм можетиспользовать для блока B7, существует:оба пути, достигающие B7 ({B1, B4, B5}B2B4B5и {B1, B4, B6}), имеют общее началоB6B7{B1, B4}.Следовательно, алгоритм можетиспользовать ТЗ для B4 (она содержитB3в себе таблицу для B1) в качественачального состояния ТЗ для B7.Легко видеть, что B4 = Idom (B7).Следовательно для глобальнойнумерации значений можноиспользовать дерево доминаторов,визуализирующее отношение Idom.246.3 Глобальная нумерация значенийB16.3.3 Обработка точек сбора ТЗ, которую алгоритм можетB2B4использовать для блока B7, существует:B5оба пути, достигающие B7 ({B1, B4, B5}и {B1, B4, B6}), имеют общее началоB6B7{B1, B4}.Следовательно, алгоритм можетB3использовать ТЗ для B4 (она содержитв себе таблицу для B1) в качествеB1начального состояния ТЗ для B7.Легко видеть, что B4 = Idom (B7).Следовательно для глобальнойнумерации значений можноиспользовать дерево доминаторов,визуализирующее отношение Idom.B3B4B3B5B7B6Дерево доминаторов256.4 Алгоритм глобальной нумерации значений6.4.1 Вводные замечанияАлгоритм DBGVN (Dominator Based Global Value Numbering)выполняет нумерацию значений процедуры с помощьюрекурсивного обхода ее дерева доминаторов.ТЗ каждого базового блока инициализируется информацией,полученной при нумерации значений его родителя по деревудоминаторов.Для упрощения реализации алгоритма, SSA-имя первого вхождениявыражения (на данном пути по дереву доминаторов) становится егономером значения.
Это позволяет обойтись без массива имен, таккак каждый номер значения – это аналог SSA-имени.Когда обнаруживается избыточное вычисление выражения,компилятор удаляет операцию, и заменяет все использованияуказанного SSA-имени на номер значения этого выражения.266.4 Алгоритм глобальной нумерации значений6.4.1 Вводные замечания Замена SSA-имени на номер значения вычисляющего его выражениядопустима в следующих двух ситуациях:Номер значения может заместить избыточное вычислениевыражения в любом блоке, доминатором которого является блок,в котором в первый раз вычисляется это выражение.Номер значения может заместить избыточное вычисление,результат которого является параметром -узла, входящего всостав границы доминирования блока, в котором в первый развычисляется это выражение.Обработка -функций.
Прежде, чем компилятор сможетанализировать -функцию в блоке, он должен присвоить номеразначений всем ее входам. Это возможно не всегда.В частности, любой вход -функции, значение которого приходит пообратному ребру (относительно дерева доминаторов) не может27иметь номера значения.6.4 Алгоритм глобальной нумерации значений6.4.2 Обработка -функцийСледующие два условия гарантируют, что при попадании алгоритма вблок всем параметрам -функций этого блока уже присвоены номеразначений:1. Рекурсивная процедура DBGVN обходит дерево доминаторов поширине. Это гарантирует, что все предшественники блока будутобработаны до самого блока.2.
Блок не имеет обратных входных ребер.Если -функция бессмысленна или избыточна, она должна бытьудалена:-функция бессмысленна если все ее входы имеют одинаковыйномер значения. При удалении бессмысленной -функцииссылки на ее результат заменяются номером значения ее входов.-функция избыточна, если она вычисляет то же самоезначение, что и другая -функция в том же блоке286.4 Алгоритм глобальной нумерации значений6.4.3 Рекурсивный алгоритм глобальной нумерации значенийВход:(1) граф потока управления N, E, дерево доминаторов DT(2) множество Val значений переменных, констант ивыраженийВыход: отображение VN: Val N {0} (N – множество натуральныхчисел), ставящее в соответствие каждому значению его номер:натуральное число или 0.Метод: Применить к корню DT рекурсивную процедуру DBGVN(Dominator Based Global Value Numbering)296.4 Алгоритм глобальной нумерации значений6.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(1) Обработка -функцийprocedure DBGVN(Block B)Отметить начало новой области имен||Обработка -функцийfor each p B, где p – -функция вида “n (…)”if p бессмысленна или избыточнапоместить номер значения p в VN[n]удалить pelseVN[n] n;добавить p в ТЗ306.4 Алгоритм глобальной нумерации значений6.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(2) Обработка остальных инструкцийprocedure DBGVN(Block B)for each aB где a – присваивание вида “x op, y, z”заменить y на VN[y] и z на VN[z]expr op, y, z|| expr – вход в ТЗif expr может быть упрощено до exprЗаменить a на “x expr ”expr exprif expr имеется в ТЗ с номером vVN[x] vУдалить aelse Добавить expr в ТЗ с номером x VN[x] x316.4 Алгоритм глобальной нумерации значений6.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(3) Окончание обработки блока B и переход к обработке его дочернихблоков (по дереву доминаторов)procedure DBGVN(Block B)for each s Succ(B)скорректировать входы -функций в sfor each дочернего блока c узла B по дереву доминаторовDBGVN (c)|| рекурсивный вызовОчистить ТЗ при выходе из области (стэк)326.4 Алгоритм глобальной нумерации значений6.4.5 Пример применения алгоритмаB1 Применим алгоритм к фрагменту кода нарисунке.