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

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

В связи с существующим разночтением термина мёртвый [3][4], важно отметить, что оптимизация удаления мёртвого а не занимается удалением недостижимого а. Локализацией и удалением недостижимого а могут заниматься сборщик мусора[5] или другие оптимизации, например, удаления недостижимого а[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-форме[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 (текст Архивировано)
  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 (текст Архивировано).
  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 (текст Архивировано).
  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 года.

Литература[ | ]

Ссылки[ | ]