Устранение частичного резервирования
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Май 2015 г. ) |
В теории компиляторов частичное устранение избыточности (PRE) — это оптимизация компилятора , которая устраняет выражения , избыточные на некоторых, но не обязательно на всех путях выполнения программы. PRE — это форма исключения общих подвыражений .
Выражение называется частично избыточным, если значение, вычисленное с помощью выражения, уже доступно на некоторых, но не на всех путях программы к этому выражению. Выражение является полностью избыточным, если значение, вычисленное с помощью выражения, доступно на всех путях программы к этому выражению. PRE может исключить частично избыточные выражения, вставляя частично избыточное выражение в пути, которые его еще не вычисляют, тем самым делая частично избыточное выражение полностью избыточным.
Например, в следующем коде:
if (some_condition) {
// some code that does not alter x
y = x + 4;
}
else {
// other code that does not alter x
}
z = x + 4;
выражение x+4 назначен на z частично избыточно, поскольку оно вычисляется дважды, если some_condition это правда. PRE выполнит перемещение кода по выражению, чтобы получить следующий оптимизированный код:
if (some_condition) {
// some code that does not alter x
t = x + 4;
y = t;
}
else {
// other code that does not alter x
t = x + 4;
}
z = t;
выполняет (своего рода) устранение общих подвыражений и перемещение кода, инвариантного к циклу . Интересным свойством PRE является то, что он одновременно [1] [2] Кроме того, PRE может быть расширен для устранения поврежденных частичных дублирований, тем самым эффективно выполняя снижение численности . Это делает PRE одной из наиболее важных оптимизаций компиляторов. Традиционно PRE применяется к лексически эквивалентным выражениям, но недавно были опубликованы формулировки PRE, основанные на статической форме одиночного присваивания , которые применяют алгоритм PRE к значениям вместо выражений, объединяя PRE и глобальную нумерацию значений .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Глобальная оптимизация путем подавления частичной избыточности , Морель и Ренвуаз, 1979 г.
- ^ Эффективное частичное устранение избыточности , Бриггс и Купер, 1994 г.
Дальнейшее чтение
[ редактировать ]- Мучник, Стивен С. Расширенное проектирование и реализация компилятора . Морган Кауфманн. 1997.
- Кнуп Дж., Рутинг О. и Штеффен Б. Движение ленивого кода . Уведомления ACM SIGPLAN Vol. 27, Числ. 7 июля 1992 г., '92 Конференция по PLDI.
- Палери В.К., Шрикант Ю.Н. и Шанкар П. Простой алгоритм частичного устранения избыточности . Уведомления SIGPLAN, Vol. 33(12). страницы 35–43 (1998).
- Кеннеди Р., Чан С., Лю С.М., Ло Р., Пэн Т. и Чоу Ф. Частичное устранение избыточности в форме SSA . Транзакции ACM на языках программирования Vol. 21, Числ. 3, стр. 627–676, 1999.
- ВанДрунен Т. и Хоскинг А.Л. Устранение частичной избыточности на основе значений , Конспекты лекций по информатике, том. 2985/2004, стр. 167–184, 2004 г.
- Цай, К. и Сюэ, Дж. Оптимальное и эффективное устранение частичной избыточности на основе предположений». Международный симпозиум по генерации и оптимизации кода (CGO'03), 91-104, 2003.
- Сюэ Дж. и Кнооп Дж. Свежий взгляд на PRE как на задачу максимального потока . Международная конференция по созданию компиляторов (CC'06), страницы 139–154, Вена, Австрия, 2006 г.
- Сюэ, Дж. и Цай К. Оптимальный на всю жизнь алгоритм для спекулятивного PRE . Транзакции ACM по оптимизации архитектуры и кода Vol. 3, Числ. 3, стр. 115–155, 2006.