Это не официальный сайт wikipedia.org 01.01.2023

Удаление мёртвого кода — Википедия
Википедия

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

В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными[en], то есть переменными, значения которых в дальнейшем в программе не используются[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 может не проводить никакого самостоятельного анализа, а просто воспользоваться результатами анализа активных переменных[en][8], но вычислительная сложность такого анализа составляет O(n3) в худшем случае[7]. Существуют специфические алгоритмы, занимающиеся удалением пустых узлов в CFG-графе, объединением нескольких базовых блоков в один и т.п., для такого анализа нужен построенный граф потока управления[9].

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

ПрименениеПравить

Удаление мёртвого кода может применяться несколько раз в процессе компиляции, так как мёртвый код находится в программе не только из-за того, что он содержится в исходном коде — некоторые другие преобразования способны делать код мёртвым. К примеру, оптимизации распространение копий[en] и распространение констант часто превращают инструкции в бесполезный код[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. ↑ 1 2 Компиляторы — принципы, технологии, инструменты — С. 713, 714.
  2. ↑ 1 2 Engineering a Compiler — С. 544.
  3. ↑ Dead code detection and removal  (неопр.). Aivosto. Дата обращения: 14 июля 2012. Архивировано 5 августа 2012 года. (смешивание понятий мёртвого и недостижимого кодов)
  4. ↑ Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код).
  5. ↑ А.Ю.Дроздов, А.М.Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, №3 (текст Архивная копия от 4 марта 2016 на Wayback Machine)
  6. ↑ Engineering a Compiler — С. 544-546.
  7. ↑ 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).
  8. ↑ Advanced Compiler Design and Implementation — С. 443.
  9. ↑ Engineering a Compiler — С. 547-550.
  10. ↑ 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).
  11. ↑ Engineering a Compiler — С. 593.
  12. ↑ 1 2 Advanced compiler design and implementation — С. 13, 327, 603.
  13. ↑ Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. В Program Flow Analysis: Theory & Application, Muchnick and Jones, Prentice-Hall, 1981.
  14. ↑ Browser debate: Did Microsoft cheat?  (неопр.) The H. Дата обращения: 12 июня 2012. Архивировано 25 июня 2012 года.
  15. ↑ Lies, damned lies, and benchmarks: is IE9 cheating at SunSpider?  (неопр.) Ars Technica. Дата обращения: 3 декабря 2017. Архивировано 25 июня 2012 года.

ЛитератураПравить

СсылкиПравить

Источник — https://ru.wikipedia.org/w/index.php?title=Удаление_мёртвого_кода&oldid=128607345