Dead code elimination

Dead code elimination (DCE, устранение мёртвого кода) — это оптимизация компилятора, заключающаяся в удалении фрагментов исходного или промежуточного кода программы, которые не влияют на её результат (недостижимый код) или результат выполнения которых нигде не используется (избыточный код). Является одной из стандартных и обязательных оптимизаций в большинстве современных компиляторов, интерпретаторов и инструментов статического анализа кода.

История

Первые упоминания об устранении мёртвого кода относятся к 1950-м годам, когда разработчики компиляторов для языков Fortran и ALGOL вручную вырезали неиспользуемые участки. Систематическое исследование DCE началось в 1970-х годах с развитием теории потока данных (data-flow analysis). В 1980-х годах алгоритмы DCE стали частью оптимизирующих компиляторов для C и C++ (например, в GCC и компиляторах от Intel). В 1990-х годах с появлением JIT-компиляторов в Java и .NET DCE начали применять на этапе выполнения. В 2010-х годах DCE вошла в стандартные инструменты сборки JavaScript (Webpack, Rollup, Terser) и языков системного программирования (Rust, Go).

Классификация мёртвого кода

Мёртвый код делится на два основных типа:

Недостижимый код (unreachable code)

Фрагменты, которые никогда не выполняются из-за логики управления. Примеры:

• Код после безусловного return, break, continue или throw.
• Условные ветки с константным условием (например, if (false) { ... }).
• Функции, которые нигде не вызываются.
• Циклы, тело которых не выполняется ни разу (например, while (false) { ... }).

Избыточный код (dead store / useless code)

Фрагменты, которые выполняются, но их результат не влияет на дальнейшие вычисления. Примеры:

• Присваивание значения переменной, которая больше не читается.
• Вызов функции, возвращаемое значение которой игнорируется, и функция не имеет побочных эффектов.
• Арифметические операции, результат которых нигде не используется.
• Объявления переменных, которые не используются.

Алгоритмы и методы

Анализ потока данных (data-flow analysis)

Основной метод DCE — построение графа потока управления (CFG) и анализ определений и использования переменных (def-use chain). Алгоритм помечает каждую инструкцию как «живую» (live), если её результат читается хотя бы одной другой инструкцией, или как «мёртвую» (dead), если результат не используется. Затем мёртвые инструкции удаляются.

Анализ достижимости (reachability analysis)

Для выявления недостижимого кода строится граф вызовов функций (call graph) и граф потока управления. Компилятор помечает все базовые блоки, которые могут быть достигнуты из точки входа программы. Непомеченные блоки удаляются.

Символическое выполнение (symbolic execution)

В продвинутых компиляторах (например, LLVM) используется символическое выполнение для определения константных условий и выявления веток, которые никогда не будут выполнены. Например, if (x == x) { ... } всегда истинно, а if (x < x) { ... } всегда ложно.

Анализ побочных эффектов (side-effect analysis)

При удалении вызовов функций компилятор проверяет, имеет ли функция побочные эффекты (изменение глобального состояния, ввод-вывод, вызов exit). Если функция не имеет побочных эффектов и её результат не используется, вызов удаляется.

Примеры

Пример 1: Недостижимый код

``c int foo() { return 1; int x = 2; // Недостижимый код — удаляется } ``

Пример 2: Избыточное присваивание

``c int bar() { int a = 5; // Избыточное присваивание — удаляется, если a не используется int b = a + 1; return b; } // После DCE: int bar() { return 6; } ``

Пример 3: Условная константа

``c int baz() { if (0) { return 1; // Недостижимый код — удаляется } return 2; } ``

Применение

Компиляторы и интерпретаторы

• GCC и Clang/LLVM — выполняют DCE на этапе оптимизации (флаги -O1, -O2, -O3). В LLVM DCE реализована в проходе DeadCodeEliminationPass.
• Java HotSpot JIT — удаляет мёртвый код во время выполнения, особенно при инлайнинге методов.
• V8 (JavaScript) — использует DCE в оптимизирующем компиляторе TurboFan.

Инструменты сборки

• Webpack и Rollup — выполняют tree-shaking, который является формой DCE для модулей JavaScript: удаляются неиспользуемые экспорты.
• Terser — минификатор JavaScript, удаляющий недостижимые ветки и неиспользуемые переменные.

Статический анализ

• PVS-Studio, Coverity, Clang Static Analyzer — предупреждают о наличии мёртвого кода, что помогает разработчикам улучшить качество кода.

Значение

Преимущества

• Уменьшение размера исполняемого файла — особенно критично для встраиваемых систем, мобильных приложений и веб-сборок (WASM).
• Повышение производительности — удаление лишних инструкций сокращает время выполнения и уменьшает нагрузку на кэш процессора.
• Ускорение компиляции — меньший объём кода сокращает время последующих проходов оптимизации.
• Улучшение читаемости — статические анализаторы помогают разработчикам выявлять и удалять мёртвый код, что упрощает поддержку.

Ограничения

• Ложные срабатывания — компилятор может ошибочно удалить код, который важен для отладки, логирования или метапрограммирования (например, рефлексия в Java или C#).
• Зависимость от контекста — DCE эффективна только при наличии полной информации о программе (whole-program analysis). В динамических языках (Python, Ruby) DCE ограничена из-за возможности изменения кода во время выполнения.
• Побочные эффекты — вызовы функций с побочными эффектами (например, запись в файл) не могут быть удалены, даже если их результат не используется.

Интересные факты

• В 2018 году в компиляторе LLVM была обнаружена ошибка, связанная с DCE: оптимизация удаляла код, необходимый для корректной работы с плавающей точкой в некоторых архитектурах.
• В языке Rust DCE выполняется на этапе линковки (LTO — Link-Time Optimization), что позволяет удалять мёртвый код даже из библиотек.
• В JavaScript tree-shaking (форма DCE) стал стандартом после выхода ECMAScript 2015 (ES6), который ввёл статические импорты и экспорты.
• В 2020 году команда V8 (Google) сообщила, что DCE в TurboFan сокращает размер сгенерированного машинного кода в среднем на 15-20%.

Источники

1. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley.
2. Muchnick, S. S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann.
3. Lattner, C., & Adve, V. (2004). LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. Proceedings of the International Symposium on Code Generation and Optimization.
4. Документация GCC: «Optimize Options» (раздел -fdce).
5. Документация LLVM: «Dead Code Elimination» (проход -dead-code-elimination).
6. Статья «Tree Shaking» в документации Webpack (webpack.js.org).