Лекция 05. Глобальная нумерация значений (Лекции (2015)), страница 2

Однако, при переходе от одногосуперблока к другому он пропускает некоторые избыточности.В рассматриваемом примере:B3 и B7 составляют отдельные суперблоки, поэтомувычисления a0 + b0 и c0 + d0 в блоках B7 и B3не рассматриваются алгоритмом вместе с вычислениямив других блоках и не распознаются как избыточные,хотя на самом деле они избыточны.Выражение e + f является доступным в блоке B7:e + f вычисляется на любом пути, достигающем блока B7,и ни e, ни f не переопределяются до вычисления в B7.Потому оно избыточно и будет исключено, хотя этоневерно.Причина: расширенный алгоритм не может установить,20что e имеет разные номера значений в блоках D и E.5.2.

Нумерация значений в суперблоках5.2.5 Оценка расширенного алгоритма локальной нумерации значенийНесмотря на перечисленные недостатки, расширенный алгоритмзаслуживает применения:он позволяет найти намного больше избыточностей, чемлокальный алгоритм, за минимальные дополнительныенакладные расходы.Использование механизма контекстно-ориентированных ТЗпозволяет существенно сократить накладные расходы наработу с суперблоками.215.3 Глобальная нумерация значений5.3.1 Необходимость обработки точек сбора Расширенный алгоритм локальнойнумерации значений пропускаетнекоторые избыточности, так как онудаляет всю таблицу значений, когдадостигает блока, имеющего в ГПУболее одного предшественникаB1B2B4B5(в нашем примере это блоки B7 и B3).B7 Нужен алгоритм, который можетраспространять информацию черезточки сбора графа потока(в нашем примере это переходыB6B3от B5 и B6 к B7, и от B2 и B7 к B3).225.3 Глобальная нумерация значений5.3.2 Проблема точек сбора Для нумерации значений в блоке B7,расширенный алгоритм не можетB1использовать ТЗ для пути {B1, B4, B5},так как при этом не учитываетсяпуть от B6 к B7 .B2B4Алгоритм не может использовать ТЗдля пути {B1, B4, B6}, так как при этомB5не учитывается путь от B5 к B7.B6B7Алгоритм не может слить ТЗ дляB5 и B6, так как операция слиянияунифицирует номера значений,полученные вдоль непересекающихсяпутей.

При унификации неучитывается, что, например, вычисленияe + f в B5 и B6 могут иметь разныеномера значений.B3235.3 Глобальная нумерация значенийB15.3.3 Обработка точек сбора ТЗ, которую алгоритм можетиспользовать для блока B7, существует:оба пути, достигающие B7 ({B1, B4, B5}B2B4B5и {B1, B4, B6}), имеют общее началоB6B7{B1, B4}.Следовательно, алгоритм можетиспользовать ТЗ для B4 (она содержитB3в себе таблицу для B1) в качественачального состояния ТЗ для B7.Легко видеть, что B4 = Idom (B7).Следовательно для глобальнойнумерации значений можноиспользовать дерево доминаторов,визуализирующее отношение Idom.245.3 Глобальная нумерация значенийB15.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Дерево доминаторов255.4 Алгоритм глобальной нумерации значений5.4.1 Вводные замечанияАлгоритм DBGVN (Dominator Based Global Value Numbering)выполняет нумерацию значений процедуры с помощьюрекурсивного обхода ее дерева доминаторов.ТЗ каждого базового блока инициализируется информацией,полученной при нумерации значений его родителя по деревудоминаторов.Для упрощения реализации алгоритма, SSA-имя первого вхождениявыражения (на данном пути по дереву доминаторов) становится егономером значения.

Это позволяет обойтись без массива имен, таккак каждый номер значения – это аналог SSA-имени.Когда обнаруживается избыточное вычисление выражения,компилятор удаляет операцию, и заменяет все использованияуказанного SSA-имени на номер значения этого выражения.265.4 Алгоритм глобальной нумерации значений5.4.1 Вводные замечания Замена SSA-имени на номер значения вычисляющего его выражениядопустима в следующих двух ситуациях:Номер значения может заместить избыточное вычислениевыражения в любом блоке, доминатором которого является блок,в котором в первый раз вычисляется это выражение.Номер значения может заместить избыточное вычисление,результат которого является параметром -узла, входящего всостав границы доминирования блока, в котором в первый развычисляется это выражение.Обработка -функций.

Прежде, чем компилятор сможетанализировать -функцию в блоке, он должен присвоить номеразначений всем ее входам. Это возможно не всегда.В частности, любой вход -функции, значение которого приходит пообратному ребру (относительно дерева доминаторов) не может27иметь номера значения.5.4 Алгоритм глобальной нумерации значений5.4.2 Обработка -функцийСледующие два условия гарантируют, что при попадании алгоритма вблок всем параметрам -функций этого блока уже присвоены номеразначений:1. Рекурсивная процедура DBGVN обходит дерево доминаторов поширине.

Это гарантирует, что все предшественники блока будутобработаны до самого блока.2. Блок не имеет обратных входных ребер.Если -функция бессмысленна или избыточна, она должна бытьудалена:-функция бессмысленна если все ее входы имеют одинаковыйномер значения. При удалении бессмысленной -функцииссылки на ее результат заменяются номером значения ее входов.-функция избыточна, если она вычисляет то же самоезначение, что и другая -функция в том же блоке285.4 Алгоритм глобальной нумерации значений5.4.3 Рекурсивный алгоритм глобальной нумерации значенийВход:(1) граф потока управления N, E, дерево доминаторов DT(2) множество Val значений переменных, констант ивыраженийВыход: отображение VN: Val  N  {0} (N – множество натуральныхчисел), ставящее в соответствие каждому значению его номер:натуральное число или 0.Метод: Применить к корню DT рекурсивную процедуру DBGVN(Dominator Based Global Value Numbering)295.4 Алгоритм глобальной нумерации значений5.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(1) Обработка -функцийprocedure DBGVN(Block B)Отметить начало новой области имен||Обработка -функцийfor each p  B, где p – -функция вида “n  (…)”if p бессмысленна или избыточнапоместить номер значения p в VN[n]удалить pelseVN[n]  n;добавить p в ТЗ305.4 Алгоритм глобальной нумерации значений5.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(2) Обработка остальных инструкцийprocedure DBGVN(Block B)for each aB где a – присваивание вида “x  op, y, z”заменить y на VN[y] и z на VN[z]expr  op, y, z|| expr – вход в ТЗif expr может быть упрощено до exprЗаменить a на “x  expr ”expr  exprif expr имеется в ТЗ с номером vVN[x]  vУдалить aelse Добавить expr в ТЗ с номером x VN[x]  x315.4 Алгоритм глобальной нумерации значений5.4.4 Рекурсивная процедура DBGVN (на псевдокоде)(3) Окончание обработки блока B и переход к обработке его дочернихблоков (по дереву доминаторов)procedure DBGVN(Block B)for each s  Succ(B)скорректировать входы -функций в sfor each дочернего блока c узла B по дереву доминаторовDBGVN (c)|| рекурсивный вызовОчистить ТЗ при выходе из области (стэк)325.4 Алгоритм глобальной нумерации значений5.4.5 Пример применения алгоритмаB1 Применим алгоритм к фрагменту кода нарисунке.

Порядок обработки определяетсядеревом доминаторовv #valB1(v)B2B3B4 Обработка блока B1.Переменным u0, v0, и w0в качестве номеров значенийбудут присвоены их SSA-именаu0, v0, и w0u0 u0v0 v0w0 w0x0y0u1x1y1u2x2y2z0u3B2B3B4B1B2u0  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После обработки B1335.4 Алгоритм глобальной нумерации значений5.4.5 Пример применения алгоритмаB1 Обработка блока B2.B2Выражение c0 + d0 определенов блоке B1, доминаторе B2.Поэтому в B2 можно удалитьоба присваивания, присвоивx0 и y0 номер значения v0.Необходимо такжеподготовится к обработке блокаB4, заменив параметры функций u0, x0, и y0 номерамиих значений u0, v0, и v0.vu0v0w0x0y0u1x1y1u2x2y2z0u3#val(v)u0v0w0v0v0B3B4B1B2u0  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После обработки B2345.4 Алгоритм глобальной нумерации значений5.4.5 Пример применения алгоритмаB1 Обработка блока B3.Все три выражения в правыхчастях уже вычислены в B1,B2vдоминаторе B3Поэтому переменным u1, x1 и y1присваиваются номеразначений u0, w0 и w0соответственнои удалить присваивания.В заключение обработки B3,необходимо заполнить вторыепараметры -функцийиз B4 номерами значенийu0, w0 и w0.u0v0w0x0y0u1x1y1u2x2y2z0u3#val(v)u0v0w0v0v0u0w0w0B3B4B1B2u0  a0 + b0v0  c0 + d0w0  e0 + f0B3B4u2  (u0, u0)x2  (v0, w0)y2  (v0, w0)z0  u2 + y2u3  a0 + b0После обработки B3355.4 Алгоритм глобальной нумерации значений5.4.5 Пример применения алгоритмаB1 Обработка блока B4. Сначала исследуются-функции.