Удаление мёртвого кода

В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными^[en], то есть переменными, значения которых в дальнейшем в программе не используются^[1][2].

В связи с существующим разночтением термина мёртвый код^[3][4], важно отметить, что оптимизация удаления мёртвого кода не занимается удалением недостижимого кода. Локализацией и удалением недостижимого кода занимается оптимизация удаления недостижимого кода^[2].

Удаление бесполезного кода способно ускорить работу программы за счёт уменьшения количества исполняемых в ней операций и уменьшить размер программы или промежуточного представления^[en].

Примеры

Рассмотрим следующий код на языке Си:

 int foo(void)
 {
   int a = 24;
   int b;
   b = a + 3; /* Бесполезный код */
   return a << 2;
 }

В данном примере операция сложения b = a + 3 является мёртвым кодом, так как переменная b не используется в дальнейших вычислениях и является мёртвой, начиная с этой точки и заканчивая концом процедуры. После удаления этой инструкции получим:

 int foo(void)
 {
   int a = 24;
   int b; /* Мёртвая переменная */
   return a << 2;
 }

После удаления операции сложения, переменная b становится мёртвой во всей процедуре. Так как она объявлена локально, то может быть полностью удалена из программы:

 int foo(void)
 {
   int a = 24;
   return a << 2;
 }

Несмотря на то что вычисление происходит внутри функции, его результат записывается в переменную, находящуюся в области видимости только этой функции; и если учесть что функция безусловно возвращает число 96, она может быть упрощена оптимизацией распространение констант так, чтобы её тело состояло только из операции return 96. А затем компилятор может заменить все вызовы этой функции на возвращаемое значение.

Алгоритмы

Классический алгоритм DCE («Dead») работает на SSA-представлении и состоит из двух обходов: первый обход («Mark») отмечает (маркирует) все заведомо живые операции (операции выхода из процедуры, ввода/вывода, изменяющие глобальные переменные); второй обход («Sweep») начинается с живых операций и идёт вверх по определениям аргументов, помечая все операции на своём пути живыми, заканчивая теми операциями, которые не имеют предшественников в SSA-форме^[5]. Максимальная вычислительная сложность такого алгоритма зависит от размера программы как O(n²)^[6].

DCE может не проводить никакого самостоятельного анализа, а просто воспользоваться результатами анализа активных переменных^[en][7], но вычислительная сложность такого анализа составляет O(n³) в худшем случае^[6]. Существуют специфические алгоритмы, занимающиеся удалением пустых узлов в CFG-графе, объединением нескольких базовых блоков в один и т.п., для такого анализа нужен построенный граф потока управления^[8].

Алгоритм «Dead» был впервые опубликован в статье «Static Single Assignment Form and the Program Dependence Graph» в журнале ACM TOPLAS в 1991 году^[9]. Алгоритм «Clean», работающий с CFG-графом был разработан и реализован Робом Шиллером в 1992 году^[10].

Применение

Удаление мёртвого кода может применяться несколько раз в процессе компиляции, так как мёртвый код находится в программе не только из-за того, что он содержится в исходном коде — некоторые другие преобразования способны делать код мёртвым. К примеру, оптимизации распространение копий^[en] и распространение констант часто превращают инструкции в бесполезный код^[11][1]. Так же приходится удалять мёртвый код, созданный другими преобразованиями в компиляторе^[11]. Например, классический алгоритм оптимизации понижения силы операции замещает трудоёмкие операции менее трудоёмкими, после чего удаление мёртвого кода устраняет старые операции и завершает преобразование (без усложнения алгоритма снижения силы)^[12].

Интересные факты

• В ноябре 2010 года Microsoft выпустила новую версию Internet Explorer 9 Platform Preview 7, которая по скорости интерпретации JavaScript на бенчмарке SunSpider превзошла все остальные браузеры. В официальном блоге Internet Explorer лидер проекта, Dean J. Hachamovitch, заявил, что одним из новшеств релиза является использование оптимизации удаления мёртвого кода, благодаря чему и достигнут такой результат. Однако вскоре выяснилось, что незначительные изменения в исходном коде бенчмарка вызывали существенное падение производительности Internet Explorer 9, чего не происходило при тестировании Google Chrome или Opera. В связи с чем в адрес разработчиков Internet Explorer посыпались обвинения в «подгонке» продукта под конкретный бенчмарк^[13][14].

См. также

• Мёртвый код
• Недостижимый код
• Удаление недостижимого кода

Примечания

1. ↑ ^{1 2} Компиляторы — принципы, технологии, инструменты — С. 713, 714.
2. ↑ ^{1 2} Engineering a Compiler — С. 544.
3. ↑ Dead code detection and removal. Aivosto. Архивировано из первоисточника 6 августа 2012. (смешивание понятий мёртвого и недостижимого кодов)
4. ↑ Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код).
5. ↑ Engineering a Compiler — С. 544-546.
6. ↑ ^{1 2} Jan Olaf Blech, Lars Gesellensetter, Sabine Glesner. Formal Verification of Dead Code Elimination in Isabelle/HOL. IEEE Computer Society Press, сентябрь 2005 (текст Архивировано).
7. ↑ Advanced Compiler Design and Implementation — С. 443.
8. ↑ Engineering a Compiler — С. 547-550.
9. ↑ Ron Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. ACM TOPLAS 13(4), 1991 (текст Архивировано).
10. ↑ Engineering a Compiler — С. 593.
11. ↑ ^{1 2} Advanced compiler design and implementation — С. 13, 327, 603.
12. ↑ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. В Program Flow Analysis: Theory & Application, Muchnick and Jones, Prentice-Hall, 1981.
13. ↑ Browser debate: Did Microsoft cheat?. The H. Архивировано из первоисточника 26 июня 2012.
14. ↑ Lies, damned lies, and benchmarks: is IE9 cheating at SunSpider?. Ars Technica. Архивировано из первоисточника 26 июня 2012.

Литература

• Cooper and Torczon Engineering a Compiler. — Morgan Kaufmann, 2011. — С. 544-550, 593. — ISBN 978-0-12-088478-0
• Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. Компиляторы — принципы, технологии, инструменты. — Вильямс, 2003. — С. 713, 714, 733, 734. — ISBN 5-8459-0189-8
• Muchnick, Steven S. Advanced Compiler Design and Implementation. — Morgan Kaufmann Publishers, 1997. — С. 592-597. — ISBN 1-55860-320-4

Ссылки

• How to trick C/C++ compilers into generating terrible code?