Разреженное условное постоянное распространение

В информатике компиляторах разреженное условное распространение констант (SCCP) — это оптимизация, часто применяемая в после преобразования в статическую форму однократного присваивания (SSA). Он распространяет константы , которые представляют собой вычисление статических значений, которые можно вычислить во время компиляции. Более того, он может найти больше постоянных значений и, следовательно, больше возможностей для улучшения, чем отдельно применяя устранение мертвого кода и распространение констант в любом порядке или с любым количеством повторений. ^[1]^[2]

Алгоритм работает , выполняя абстрактную интерпретацию кода в форме SSA. Во время абстрактной интерпретации обычно используется плоская решетка констант для значений и глобальная среда, сопоставляющая переменные SSA со значениями в этой решетке. Суть алгоритма заключается в том, как он обрабатывает инструкции перехода . При обнаружении условия для ветки оцениваются как можно лучше, учитывая точность абстрактных значений, привязанных к переменным в условии. Может случиться так, что значения совершенно точны (ни сверху, ни снизу), и, следовательно, абстрактное выполнение может решить, в каком направлении разветвляться. Если значения не являются постоянными или переменная в условии не определена, то необходимо выбрать оба направления ветвления, чтобы оставаться консервативными.

По завершении абстрактной интерпретации инструкции, которые так и не были достигнуты, помечаются как мертвый код. Переменные SSA, имеющие постоянные значения, затем могут быть встроены (распространены) в точку их использования. ^{[ нужен пример ]}

Примечания

^ Вегман, Марк Н. и Задек, Ф. Кеннет. « Постоянное распространение с условными ветвями ». Транзакции ACM по языкам и системам программирования , 13 (2), апрель 1991 г., страницы 181–210.
^ Клик, Клиффорд и Купер, Кейт. « Объединение анализа, объединение оптимизаций », Транзакции ACM в языках и системах программирования , 17 (2), март 1995 г., страницы 181–196.

Ссылки

Купер, Кейт Д. и Торчон, Линда. Разработка компилятора . Морган Кауфманн. 2005.

[1] Вегман, Марк Н. и Задек, Ф. Кеннет. « Постоянное распространение с условными ветвями ». Транзакции ACM по языкам и системам программирования , 13 (2), апрель 1991 г., страницы 181–210.

[2] Клик, Клиффорд и Купер, Кейт. « Объединение анализа, объединение оптимизаций », Транзакции ACM в языках и системах программирования , 17 (2), март 1995 г., страницы 181–196.

[1]

[2]

v т и Оптимизация компилятора
Базовый блок	Оптимизация глазка Нумерация локальных значений
Петля	Автоматическое распараллеливание Автоматическая векторизация Индукционная переменная Петля слияния Движение кода, инвариантное к циклу Инверсия цикла Перестановка петель Оптимизация гнезда циклов Разделение цикла Развертывание цикла Выключение петли Конвейерная обработка программного обеспечения Снижение прочности
Поток данных анализ	Доступное выражение Удаление общего подвыражения Постоянное складывание мертвого магазина Устранение Распознавание и устранение индукционных переменных Анализ переменных в реальном времени Использовать-определить цепочку
SSA на основе	Глобальная нумерация значений Разреженное условное постоянное распространение
Генерация кода	Планирование инструкций Выбор инструкции Распределение регистров Рематериализация
Функциональный	Вырубка лесов Устранение хвостового вызова
Глобальный	Межпроцедурная оптимизация
Другой	Устранение проверки границ Выполнение функции во время компиляции Устранение мертвого кода Шаблоны выражений Встроенное расширение Перейти к потоку Частичная оценка Оптимизация на основе профиля
Статический анализ	Анализ псевдонимов Анализ доступа к массиву Анализ потока управления Анализ потока данных Анализ зависимостей Анализ побега Анализ указателя Анализ формы Анализ диапазона значений