Устранение частичной избыточности - 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 и глобальная нумерация значений.
Смотрите также
Рекомендации
- ^ Глобальная оптимизация за счет подавления частичного резервирования, Морель и Ренвуаз, 1979
- ^ Эффективное устранение частичной избыточности, Бриггс и Купер, 1994
дальнейшее чтение
- Мучник, Стивен С. Расширенный дизайн и реализация компилятора. Морган Кауфманн. 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.