Нумерация значений
Нумерация значений — это метод определения эквивалентности двух вычислений в программе и исключения одного из них с помощью оптимизации , сохраняющей семантику .
Глобальная нумерация значений
[ редактировать ]Нумерация глобальных значений (GVN) — это оптимизация компилятора, основанная на промежуточном представлении статической формы однократного назначения (SSA). Иногда это помогает устранить избыточный код , чего устранение общего подвыражения не помогает (CSE). В то же время, однако, CSE может исключить код, которого нет в GVN, поэтому оба часто встречаются в современных компиляторах. Нумерация глобальных значений отличается от нумерации локальных значений тем, что сопоставления чисел и значений сохраняются и за пределами границ базовых блоков, а для вычисления сопоставлений используются разные алгоритмы.
Нумерация глобальных значений работает путем присвоения номера значения переменным и выражениям. Один и тот же номер значения присваивается тем переменным и выражениям, которые, вероятно, эквивалентны. Например, в следующем коде:
w := 3 x := 3 y := x + 4 z := w + 4
хорошая процедура GVN присвоит один и тот же номер значения w
и x
, и то же число значений для y
и z
. Например, карта будет представлять собой оптимальное отображение числа значений для этого блока.
Используя эту информацию, предыдущий фрагмент кода можно безопасно преобразовать в:
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 сопоставления не создаются.
Нумерация локальных значений
[ редактировать ]Нумерация локальных значений (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
оба записаны под одним и тем же номером) или путем сортировки операндов перед проверкой эквивалентов. [1]
Оптимизаторы нумерации локальных значений также могут знать о математических тождествах. Предполагая a
является целым числом , всем следующим выражениям можно присвоить одно и то же значение: [2]
b ← a + 0 c ← a * 1 d ← min(a, MAX_INT) e ← max(a, a) f ← a & 0xFF..FF (assuming '&' denotes bitwise AND)
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Купер, Кейт Д.; Торчон, Линда. «Терминология, принципы и проблемы (с примерами нумерации локальных значений)» . ещевир . Проверено 15 мая 2017 г.
- ^ Купер, Кейт Д.; Торчон, Линда. «Локальная оптимизация: нумерация значений» (PDF) . Университет Райса . Проверено 15 мая 2017 г.
Дальнейшее чтение
[ редактировать ]- Килдалл, Гэри Арлен (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.