Удаление мёртвого кода (R;glyuny b~jmfkik tk;g)
В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными, то есть переменными, значения которых в дальнейшем в программе не используются[1][2].
Существует разночтение термина мёртвый код[3][4]. При этом, оптимизация удаления мёртвого кода не занимается удалением недостижимого кода. Локализацией и удалением недостижимого кода могут заниматься сборщик мусора[5] или другие оптимизации, например, удаления недостижимого кода[2].
Удаление бесполезного кода способно ускорить работу программы за счёт уменьшения количества исполняемых в ней операций и уменьшить размер программы или промежуточного представления.
Примеры[править | править код]
Рассмотрим следующий код на языке Си:
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-форме[6]. Максимальная вычислительная сложность такого алгоритма зависит от размера программы как O(n2)[7].
DCE может не проводить никакого самостоятельного анализа, а просто воспользоваться результатами анализа активных переменных[8], но вычислительная сложность такого анализа составляет O(n3) в худшем случае[7]. Существуют специфические алгоритмы, занимающиеся удалением пустых узлов в CFG-графе, объединением нескольких базовых блоков в один и т.п., для такого анализа нужен построенный граф потока управления[9].
Алгоритм «Dead» был впервые опубликован в статье «Static Single Assignment Form and the Program Dependence Graph» в журнале ACM TOPLAS в 1991 году[10]. Алгоритм «Clean», работающий с CFG-графом был разработан и реализован Робом Шиллером в 1992 году[11].
Применение[править | править код]
Удаление мёртвого кода может применяться несколько раз в процессе компиляции, так как мёртвый код находится в программе не только из-за того, что он содержится в исходном коде — некоторые другие преобразования способны делать код мёртвым. К примеру, оптимизации распространение копий и распространение констант часто превращают инструкции в бесполезный код[1][12]. Также приходится удалять мёртвый код, созданный другими преобразованиями в компиляторе[12]. Например, классический алгоритм оптимизации понижения силы операции замещает трудоёмкие операции менее трудоёмкими, после чего удаление мёртвого кода устраняет старые операции и завершает преобразование (без усложнения алгоритма снижения силы)[13].
Интересные факты[править | править код]
- В ноябре 2010 года Microsoft выпустила новую версию Internet Explorer 9 Platform Preview 7, которая по скорости интерпретации JavaScript на бенчмарке SunSpider превзошла все остальные браузеры. В официальном блоге Internet Explorer лидер проекта, Dean J. Hachamovitch, заявил, что одним из новшеств релиза является использование оптимизации удаления мёртвого кода, благодаря чему и достигнут такой результат. Однако вскоре выяснилось, что незначительные изменения в исходном коде бенчмарка вызывали существенное падение производительности Internet Explorer 9, чего не происходило при тестировании Google Chrome или Opera. В связи с чем в адрес разработчиков Internet Explorer посыпались обвинения в «подгонке» продукта под конкретный бенчмарк[14][15].
См. также[править | править код]
Примечания[править | править код]
- ↑ 1 2 Компиляторы, 2003, с. 713, 714.
- ↑ 1 2 Cooper and Torczon, 2011, с. 544.
- ↑ Dead code detection and removal. Aivosto. Дата обращения: 14 июля 2012. Архивировано 5 августа 2012 года. (смешивание понятий мёртвого и недостижимого кодов)
- ↑ Компиляторы, 2003, с. 669 (недостижимый код), 713 (мёртвый код).
- ↑ А.Ю.Дроздов, А.М.Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, №3 (текст Архивная копия от 4 марта 2016 на Wayback Machine)
- ↑ Cooper and Torczon, 2011, с. 544-546.
- ↑ 1 2 Jan Olaf Blech, Lars Gesellensetter, Sabine Glesner. Formal Verification of Dead Code Elimination in Isabelle/HOL. IEEE Computer Society Press, сентябрь 2005 (текст Архивная копия от 7 марта 2016 на Wayback Machine).
- ↑ Muchnick, Steven S., 1997, с. 443.
- ↑ Cooper and Torczon, 2011, с. 547-550.
- ↑ 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 (текст Архивная копия от 24 сентября 2011 на Wayback Machine).
- ↑ Cooper and Torczon, 2011, с. 593.
- ↑ 1 2 Muchnick, Steven S., 1997, с. 13, 327, 603.
- ↑ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. В Program Flow Analysis: Theory & Application, Muchnick and Jones, Prentice-Hall, 1981.
- ↑ Browser debate: Did Microsoft cheat? The H. Дата обращения: 12 июня 2012. Архивировано 25 июня 2012 года.
- ↑ Lies, damned lies, and benchmarks: is IE9 cheating at SunSpider? Ars Technica. Дата обращения: 3 декабря 2017. Архивировано 25 июня 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.