В теорії компіляторів ви́даленням ме́ртвого ко́ду () називають оптимізацію, за якої видаляється мертвий код. Ме́ртвим ко́дом (або ма́рним ко́дом) називають код, виконання якого не впливає на вивід програми, всі результати обчислення такого коду є , тобто змінними, значення яких надалі в програмі не використовуютьсяКомпиляторы — принципы, технологии, инструменты — С. 713, 714.Engineering a Compiler — С. 544..
Через існування різночитань терміна мертвий код (смешивание понятий мёртвого и недостижимого кодов)Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код)., важливо відзначити, що оптимізація видалення мертвого коду не займається видаленням недосяжного коду. Локалізацією і видаленням недосяжного коду можуть займатися прибиральникА. Ю. Дроздов, А. М. Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, № 3 (текст ) або інші оптимізації, наприклад, видалення недосяжного коду.
Видалення непотрібного коду здатне прискорити роботу програми завдяки зменшенню кількості виконуваних у ній операцій і зменшити обсяг програми або проміжного подання.
Приклади Розглянемо такий код мовою Сі: 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-поданніEngineering a Compiler — С. 544—546.. Максимальна обчислювальна складність такого алгоритму залежить від розміру програми як O(n2)Jan Olaf Blech, Lars Gesellensetter, Sabine Glesner. Formal Verification of Dead Code Elimination in Isabelle/HOL. IEEE Computer Society Press, сентябрь 2005 (текст)..
DCE може не проводити ніякого самостійного аналізу, а просто скористатися результатами Advanced Compiler Design and Implementation — С. 443., але обчислювальна складність такого аналізу становить у гіршому випадку O(n3). Існують специфічні алгоритми, які видаляють порожні вузли в графі потоку керування, об'єднують декілька базових блоків в один тощо, але для такого аналізу потрібен побудований граф потоку керуванняEngineering a Compiler — С. 547—550..
Алгоритм «Dead» вперше опубліковано в статті «Static Single Assignment Form and the Program Dependence Graph» в журналі 1991 рокуRon Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. 13(4), 1991 (текст).. Алгоритм «Clean», що працює з графом потоку керування розробив і реалізував Роб Шиллер 1992 рокуEngineering a Compiler — С. 593..
Застосування Видалення мертвого коду може в процесі компіляції застосовуватися кілька разів, оскільки мертвий код може не тільки існувати в програмі від початку, але й з'являтися після деяких перетворень коду програми. Наприклад, оптимізації і поширення констант часто перетворюють інструкції в марний кодAdvanced compiler design and implementation — С. 13, 327, 603.. Також доводиться видаляти мертвий код, створений іншими перетвореннями в компіляторі. Наприклад, класичний алгоритм оптимізації зниження вартості операцій заміщає трудомісткі операції менш трудомісткими, після чого видалення мертвого коду усуває старі операції і завершує перетворення (без ускладнення алгоритму зниження вартості)Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. В Program Flow Analysis: Theory & Application, Muchnick and Jones, Prentice-Hall, 1981..
Цікаві факти У листопаді 2010 року Microsoft випустила нову версію Internet Explorer 9 Platform Preview 7, яка за швидкістю інтерпретації JavaScript на бенчмарку SunSpider перевершила всі інші браузери. В офіційному блозі Internet Explorer лідер проєкту, , заявив, що одним із нововведень релізу є використання оптимізації видалення мертвого коду, завдяки чому й досягнуто такого результату. Однак незабаром з'ясувалося, що незначні зміни у сирцевому коді бенчмарка викликали істотне падіння продуктивності Internet Explorer 9, чого не відбувалося при тестуванні Google Chrome або Opera. Через це на адресу розробників Internet Explorer посипалися звинувачення в «підгонці» продукту під конкретний бенчмарк.
Див. також Мертвий код Недосяжний код Видалення недосяжного коду
Примітки
Література
Посилання How to trick C/C++ compilers into generating terrible code?