Устранение частичной избыточности - Partial redundancy elimination

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Май 2015 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Например, в следующем коде:

 если (some_condition) {   // какой-то код, который не меняет x   у = Икс + 4; } еще {   // другой код, который не меняет x } z = Икс + 4;

выражение х + 4 назначен z частично избыточен, потому что он вычисляется дважды, если some_condition правда. PRE будет выполнять код движения в выражении, чтобы получить следующий оптимизированный код:

 если (some_condition) {   // какой-то код, который не меняет x   т = Икс + 4;   у = т; } еще {   // другой код, который не меняет x   т = Икс + 4; } z = т;

Интересным свойством PRE является то, что он выполняет (форму) исключение общего подвыражения и движение кода с инвариантным циклом в то же время.^[1][2] Кроме того, PRE можно расширить, чтобы исключить пострадавший частичное дублирование, тем самым эффективно выполняя снижение силы. Это делает PRE одной из самых важных оптимизаций при оптимизации компиляторов. Традиционно PRE применяется к лексически эквивалентным выражениям, но в последнее время формулировки PRE основаны на статическая форма единого назначения были опубликованы, которые применяют алгоритм PRE к значениям вместо выражений, объединяя PRE и глобальная нумерация значений.

Смотрите также

• Нумерация значений
• Резервный код
• Устранение мертвого кода

Рекомендации

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

• Мучник, Стивен С. Расширенный дизайн и реализация компилятора. Морган Кауфманн. 1997 г.
• Knoop, J., Ruthing, O., и Штеффен, Б. Ленивое движение кода. Уведомления ACM SIGPLAN Vol. 27, Чис. 7 июля 1992 г. Конференция по PLDI.
• Палери В.К., Срикант Ю.Н., Шанкар П. Простой алгоритм устранения частичной избыточности. Уведомления SIGPLAN, Vol. 33 (12). страницы 35–43 (1998).
• Кеннеди, Р., Чан, С., Лю, С.М., Ло, Р., Пэн, Т., и Чоу, Ф. Частичное устранение избыточности в форме SSA. Транзакции ACM по языкам программирования Vol. 21, Чис. 3. С. 627–676, 1999.
• ВанДрунен Т., Хоскинг А.Л. Устранение частичной избыточности на основе стоимости, Конспект лекций по информатике Vol. 2985/2004, стр. 167 - 184, 2004.
• Цай, К. и Сюэ, Дж. Оптимальное и эффективное устранение частичной избыточности на основе предположений ». Международный симпозиум по генерации и оптимизации кода (CGO'03), 91-104, 2003.
• Сюэ Дж. И Кнуп Дж. Свежий взгляд на PRE как на проблему максимального потока. Международная конференция по созданию компиляторов (CC'06), страницы 139–154, Вена, Австрия, 2006 г.
• Сюэ Дж. И Цай К. Оптимальный для жизни алгоритм для спекулятивного PRE. Транзакции ACM по архитектуре и оптимизации кода Vol. 3, Чис. 3. С. 115–155, 2006.