Видалення мертвого коду

В теорії компіляторів ви́даленням ме́ртвого ко́ду (англ. 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]. Існують специфічні алгоритми, які видаляють порожні вузли в графі потоку керування, об'єднують декілька базових блоків в один тощо, але для такого аналізу потрібен побудований граф потоку керування[9].

Алгоритм «Dead» вперше опубліковано в статті «Static Single Assignment Form and the Program Dependence Graph» в журналі ACM TOPLAS[en] 1991 року[10]. Алгоритм «Clean», що працює з графом потоку керування розробив і реалізував Роб Шиллер 1992 року[11].

Застосування

Видалення мертвого коду може в процесі компіляції застосовуватися кілька разів, оскільки мертвий код може не тільки існувати в програмі від початку, але й з'являтися після деяких перетворень коду програми. Наприклад, оптимізації поширення копій[en] і поширення констант часто перетворюють інструкції в марний код[1][12]. Також доводиться видаляти мертвий код, створений іншими перетвореннями в компіляторі[12]. Наприклад, класичний алгоритм оптимізації зниження вартості операцій заміщає трудомісткі операції менш трудомісткими, після чого видалення мертвого коду усуває старі операції і завершує перетворення (без ускладнення алгоритму зниження вартості)[13].

Цікаві факти

  • У листопаді 2010 року Microsoft випустила нову версію Internet Explorer 9 Platform Preview 7, яка за швидкістю інтерпретації JavaScript на бенчмарку SunSpider [Архівовано 20 січня 2022 у Wayback Machine.] перевершила всі інші браузери. В офіційному блозі Internet Explorer лідер проєкту, Дін Гачамович[en], заявив, що одним із нововведень релізу є використання оптимізації видалення мертвого коду, завдяки чому й досягнуто такого результату. Однак незабаром з'ясувалося, що незначні зміни у сирцевому коді бенчмарка викликали істотне падіння продуктивності Internet Explorer 9, чого не відбувалося при тестуванні Google Chrome або Opera. Через це на адресу розробників Internet Explorer посипалися звинувачення в «підгонці» продукту під конкретний бенчмарк[14][15].

Див. також

Примітки

  1. ↑ а б Компиляторы — принципы, технологии, инструменты — С. 713, 714.
  2. ↑ а б Engineering a Compiler — С. 544.
  3. ↑ Dead code detection and removal. Aivosto. Архів оригіналу за 5 серпня 2012. Процитовано 14 липня 2012. (смешивание понятий мёртвого и недостижимого кодов)
  4. ↑ Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код).
  5. ↑ А. Ю. Дроздов, А. М. Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, № 3 (текст [Архівовано 2016-03-04 у Wayback Machine.])
  6. ↑ Engineering a Compiler — С. 544—546.
  7. ↑ а б 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[en] 13(4), 1991 (текст).
  11. ↑ Engineering a Compiler — С. 593.
  12. ↑ а б 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. Архів оригіналу за 25 червня 2012. Процитовано 12 червня 2012.
  15. ↑ Lies, damned lies, and benchmarks: is IE9 cheating at SunSpider?. Ars Technica. Архів оригіналу за 25 червня 2012. Процитовано 3 грудня 2017.

Література

Посилання