Jump to content

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

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

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

[ редактировать ]

Нумерация глобальных значений (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)

См. также

[ редактировать ]
  1. ^ Купер, Кейт Д.; Торчон, Линда. «Терминология, принципы и проблемы (с примерами нумерации локальных значений)» . ещевир . Проверено 15 мая 2017 г.
  2. ^ Купер, Кейт Д.; Торчон, Линда. «Локальная оптимизация: нумерация значений» (PDF) . Университет Райса . Проверено 15 мая 2017 г.

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f3443d2fb37f93a3aca8a045bf1aed73__1713788940
URL1:https://arc.ask3.ru/arc/aa/f3/73/f3443d2fb37f93a3aca8a045bf1aed73.html
Заголовок, (Title) документа по адресу, URL1:
Value numbering - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)