Конференции ИВТ СО РАН

Тезисы докладов

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

В литературе описаны два подхода к удалению избыточности - перемещение операторов (code motion) [1], использующий потоковый анализ, и нумерация значений (value numbering) [2], разделяющий операторы программы на классы эквивалентности. Сильные и слабые стороны обоих подходов взаимно противоположны. В настоящее время развиваются комбинированные методы, позволяющие объединить сильные стороны обоих подходов.

В работе предлагается новый алгоритм для удаления частично избыточных выражений, являющийся развитием известного алгоритма SSAPRE [3] для перемещения операторов. Благодаря использованию принципов сопоставления операторов, характерных для методов нумерации значений, предложенный алгоритм соединяет преимущества обоих подходов:

• Поиск избыточности между лексически неодинаковыми операторами, то есть обработка семантики операторов присваивания.
• Удаление частично избыточных операторов, т.е. операторов, результат которых уже вычислялся на некотором (но не на любом) пути исполнения.

Кроме того, алгоритм является разреженным (sparse) в том смысле, что его временная сложность не превосходит O(N ln N) для достаточно широкого класса входных данных.

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

[1] J. Knoop, O. Ruething, and B. Steffen. Lazy code motion. In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, volume 27.
[2] Preston Briggs, Keith D. Cooper and L. Taylor Simpson. Value numbering. Software Practice and Experience, 27(6):701--724, 1997.
[3] Kennedy R., Chan S. Liu S., et. al. Partial Redundancy Elimination in SSA form. ACM Transactons on Programming Languages and Systems 1999 v. 21(3):627-676

Дополнительные материалы:

ZIP (217 kb)

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск