Нумерация значений

Нумерация значений — это метод определения эквивалентности двух вычислений в программе и исключения одного из них с помощью оптимизации , сохраняющей семантику .

Глобальная нумерация значений

Нумерация глобальных значений (GVN) — это оптимизация компилятора, основанная на промежуточном представлении статической формы однократного назначения (SSA). Иногда это помогает устранить избыточный код , чего устранение общего подвыражения не помогает (CSE). В то же время, однако, CSE может исключить код, которого нет в GVN, поэтому оба часто встречаются в современных компиляторах. Нумерация глобальных значений отличается от нумерации локальных значений тем, что сопоставления чисел и значений сохраняются и за пределами границ базовых блоков, а для вычисления сопоставлений используются разные алгоритмы.

Нумерация глобальных значений работает путем присвоения номера значения переменным и выражениям. Один и тот же номер значения присваивается тем переменным и выражениям, которые, вероятно, эквивалентны. Например, в следующем коде:

w := 3
x := 3
y := x + 4
z := w + 4

хорошая процедура GVN присвоит один и тот же номер значения w и x, и то же число значений для y и z. Например, карта $\left\{{w}\mapsto 1,{x}\mapsto 1,{y}\mapsto 2,{z}\mapsto 2\right\}$ будет представлять собой оптимальное отображение числа значений для этого блока. Используя эту информацию, предыдущий фрагмент кода можно безопасно преобразовать в:

w := 3
x := w
y := w + 4
z := y

В зависимости от кода, следующего за этим фрагментом, распространение копирования может удалить присвоения x и чтобы z.

Причина, по которой GVN иногда более мощна, чем CSE, заключается в том, что CSE сопоставляет лексически идентичные выражения, тогда как GVN пытается определить основную эквивалентность. Например, в коде:

a := c × d
e := c
f := e × d

Без распространения копирования CSE не исключил бы перерасчет, назначенный f, но даже плохой алгоритм GVN должен обнаружить и устранить эту избыточность.

В IR и исходных языках, где возможна повторная привязка (присвоение одной и той же переменной более одного раза), форма SSA требуется для выполнения GVN, чтобы false $\left\{{\text{variable name}}\mapsto {\text{value number}}\right\}$ сопоставления не создаются.

Нумерация локальных значений

Нумерация локальных значений (LVN) — это оптимизация компилятора , цель которой — найти несколько экземпляров эквивалентных выражений (т. е. выражений, которые дают одинаковый результат) и заменить их первым вхождением. LVN — это локальная оптимизация, означающая, что в отличие от глобальной нумерации значений работает с одним базовым блоком она одновременно .

Нумерация локальных значений работает путем присвоения уникального номера каждой операции и запоминания этих ассоциаций. Затем просматриваются последующие инструкции и, если идентичная инструкция уже зарегистрирована, заменяются результатом предыдущей инструкции. Например:

a ← 4         a is tagged as #1
b ← 5         b is tagged as #2
c ← a + b     c (#1 + #2) is tagged as #3
d ← 5         d is tagged as #2, the same as b
e ← a + d     e, being '#1 + #2' is tagged as #3

Присвоив инструкциям номера, сравнение дубликатов превращается в простое целочисленное сравнение. В этом конкретном примере c и e присваиваются одинаковые номера (#3), тем самым сигнализируя компилятору, что любые ссылки на e можно просто заменить на те, которые c.

Трудности и расширения

Проблемы при неиспользовании SSA

Наивная реализация может попытаться выполнить оптимизацию, напрямую используя имена переменных вместо чисел. Однако этот подход не работает, когда значения переменных могут меняться. Рассмотрим псевдокод :

a ← 1         a is tagged as #1
b ← 2         b is tagged as #2
c ← a + b     c is tagged as #3
b ← 3
d ← a + b     d is incorrectly tagged as #3

В этом сценарии d неправильно присвоен номер 3, поскольку аргументы совпадают с аргументами c. Однако это неверно, поскольку b изменил значение с 2 на 3, в результате чего фактические результаты стали другими. Использование представления SSA устраняет это несоответствие.

Использование математических тождеств

Простая реализация также может оказаться неспособной уловить все эквивалентные выражения, даже если они отличаются только порядком своих операндов. В следующем примере a и b может быть присвоен тот же номер:

a ← 1 + 2
b ← 2 + 1

Эту проблему можно легко решить, присвоив обоим случаям один и тот же номер (т. е. a + b и b + a оба записаны под одним и тем же номером) или путем сортировки операндов перед проверкой эквивалентов.

Оптимизаторы нумерации локальных значений также могут знать о математических тождествах. Предполагая a является целым числом , всем следующим выражениям можно присвоить одно и то же значение:

b ← a + 0
c ← a * 1
d ← min(a, MAX_INT)
e ← max(a, a)
f ← a & 0xFF..FF       (assuming '&' denotes bitwise AND)

См. также

• Частичное устранение избыточности
• Оптимизирующий компилятор
• Удаление общего подвыражения

Дальнейшее чтение

• Килдалл, Гэри Арлен (1973). «Единый подход к глобальной оптимизации программ» . Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования — POPL '73 . Попл '73. стр. 194–206. дои : 10.1145/512927.512945 . hdl : 10945/42162 . ISBN  9781450373494 . S2CID   10219496 . Проверено 20 ноября 2006 г. [1]
• Альперн, Боуэн, Вегман, Марк Н. и Задек, Ф. Кеннет. «Обнаружение равенства переменных в программах», Протокол конференции пятнадцатого ежегодного симпозиума ACM по принципам языков программирования ( POPL ), ACM Press, Сан-Диего, Калифорния, США, январь 1988 г., страницы 1–11.
• Л. Тейлор Симпсон, «Устранение избыточности, основанной на ценности». Технический отчет 96-308, Факультет компьютерных наук, Университет Райса, 1996 г. (Авторская кандидатская диссертация)
• Мучник, Стивен Стэнли (1997). Расширенное проектирование и реализация компилятора . Издательство Морган Кауфманн . ISBN  978-1-55860-320-2 .
• Бриггс, П.; Купер, Кейт Д .; Симпсон, Л. Тейлор (1997). «Нумерация значений». Программное обеспечение-практика и опыт . 27 (6): 701–724.