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

Существует разночтение термина мёртвый код . При этом, оптимизация удаления мёртвого кода не занимается удалением недостижимого кода . Локализацией и удалением недостижимого кода могут заниматься сборщик мусора или другие оптимизации, например, удаления недостижимого кода .

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

Примеры

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

 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-форме . Максимальная вычислительная сложность такого алгоритма зависит от размера программы как O(n ² ) .

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

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

Применение

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

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

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

См. также

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

Примечания

Литература

• Cooper and Torczon. Engineering a Compiler. — Morgan Kaufmann, 2011. — С. 544-550, 593. — ISBN 978-0-12-088478-0 .

• Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. . — Вильямс, 2003. — С. , 714, 733, 734. — ISBN 5-8459-0189-8 .

• Muchnick, Steven S. . — Morgan Kaufmann Publishers , 1997. — С. -597. — ISBN 1-55860-320-4 .

Ссылки