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

В теорії компіляторів ви́даленням ме́ртвого ко́ду (англ. dead code elimination, DCE) називають оптимізацію, за якої видаляється мертвий код. Ме́ртвим ко́дом (або ма́рним ко́дом) називають код, виконання якого не впливає на програми, всі результати обчислення такого коду є ^[en], тобто змінними, значення яких надалі в програмі не використовуються.

Через існування різночитань терміна мертвий код, важливо відзначити, що оптимізація видалення мертвого коду не займається видаленням недосяжного коду. Локалізацією і видаленням недосяжного коду можуть займатися прибиральник або інші оптимізації, наприклад, видалення недосяжного коду.

Видалення непотрібного коду здатне прискорити роботу програми завдяки зменшенню кількості виконуваних у ній операцій і зменшити обсяг програми або ^[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») працює на і складається з двох обходів: перший обхід («Mark») позначає (маркує) всі напевне живі операції (операції виходу з процедури, введення-виведення, що змінюють глобальні змінні); другий обхід («Sweep») починається з живих операцій і йде вгору по визначеннях аргументів, позначаючи всі операції на своєму шляху живими, закінчуючи тими операціями, які не мають попередників у SSA-поданні. Максимальна обчислювальна складність такого алгоритму залежить від розміру програми як O(n²).

DCE може не проводити ніякого самостійного аналізу, а просто скористатися результатами ^[en], але обчислювальна складність такого аналізу становить у гіршому випадку O(n³). Існують специфічні алгоритми, які видаляють порожні вузли в графі потоку керування, об'єднують декілька базових блоків в один тощо, але для такого аналізу потрібен побудований граф потоку керування.

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

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

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

Цікаві факти

• У листопаді 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 посипалися звинувачення в «підгонці» продукту під конкретний бенчмарк.

Див. також

• Мертвий код
• Недосяжний код
• Видалення недосяжного коду

Примітки

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. , сентябрь 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. ^[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.

Література

• ^[en] and Torczon. Engineering a Compiler. — Morgan Kaufmann, 2011. — С. 544—550, 593. — .
• Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. Компиляторы — принципы, технологии, инструменты. — Вильямс, 2003. — С. 713, 714, 733, 734. — .
• ^[en]. Advanced Compiler Design and Implementation. — , 1997. — С. 592-597. — .

Посилання

• How to trick C/C++ compilers into generating terrible code?