Устранение мертвого кода - Dead code elimination

В теория компилятора, устранение мертвого кода (также известный как DCE, удаление мертвого кода, удаление мертвого кода, или же полоска мертвого кода) это оптимизация компилятора удалить код, не влияющий на результаты программы. Удаление такого кода имеет несколько преимуществ: оно уменьшает размер программы, что является важным фактором в некоторых контекстах, и позволяет запущенной программе избегать выполнения нерелевантных операций, что сокращает время ее выполнения. Он также может обеспечить дальнейшую оптимизацию за счет упрощения структуры программы.Мертвый код включает код, который никогда не может быть выполнен (недостижимый код ) и код, влияющий только на мертвые переменные (записано, но больше никогда не читается), то есть не имеет отношения к программе.

Примеры

Рассмотрим следующий пример, написанный на C.

 int фу(пустота) {   int а = 24;   int б = 25; / * Присваивание мертвой переменной * /   int c;   c = а * 4;   возвращаться c;   б = 24; /* Недостижимый код */   возвращаться 0; }

Простой анализ использования ценностей покажет, что ценность б после первого присваивания не используется внутри фу. Более того, б объявлен как локальная переменная внутри фу, поэтому его значение нельзя использовать вне фу. Таким образом, переменная б является мертвых а оптимизатор может освободить место для хранения и исключить его инициализацию.

Кроме того, поскольку первый оператор return выполняется безоговорочно, ни один из возможных путей выполнения не достигает второго назначения для б. Таким образом, задание недоступен и могут быть удалены.Если процедура была более сложной поток управления, например, метка после оператора возврата и идти к в другом месте процедуры, тогда возможный путь выполнения может существовать для присвоения б.

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

У большинства продвинутых компиляторов есть опции для активации удаления мертвого кода, иногда на разных уровнях. Более низкий уровень может удалять только те инструкции, которые не могут быть выполнены. Более высокий уровень также может не резервировать место для неиспользуемых переменных. Еще более высокий уровень может определять инструкции или функции, которые не служат цели, и устранять их.

Обычно удаление мертвого кода используется в качестве альтернативы дополнительному включению кода через препроцессор. Рассмотрим следующий код.

 int главный(пустота) {   int а = 5;   int б = 6;   int c;   c = а * (б / 2);   если (0) {   / * ОТЛАДКА * /     printf("% d п", c);   }   возвращаться c; }

Поскольку выражение 0 всегда будет оцениваться как ложный, код внутри оператора if никогда не может быть выполнен, а удаление мертвого кода полностью удалит его из оптимизированной программы. Этот метод распространен в отладка по желанию активировать блоки кода; использование оптимизатора с устранением мертвого кода устраняет необходимость использования препроцессор для выполнения той же задачи.

На практике большая часть мертвого кода, который находит оптимизатор, создается другими преобразованиями в оптимизаторе. Например, классические приемы для оператора снижение силы вставьте новые вычисления в код и сделайте старые, более дорогие вычисления мертвыми.^[1] Последующее удаление мертвого кода удаляет эти вычисления и завершает эффект (без усложнения алгоритма уменьшения силы).

Исторически устранение мертвого кода выполнялось с использованием информации, полученной из анализ потока данных.^[2] Алгоритм, основанный на статическая форма единого назначения (SSA) появляется в исходной статье журнала о SSA форма Рона Цитрона и др.^[3] Роберт Шиллингсбург (он же Шилльнер) улучшил алгоритм и разработал сопутствующий алгоритм для удаления бесполезных операций потока управления.^[4]

Динамическое устранение мертвого кода

Мертвый код обычно считается мертвым безусловно. Следовательно, разумно попытаться удалить мертвый код путем удаления мертвого кода на время компиляции.

Однако на практике разделы кода часто представляют только мертвый или недоступный код. при определенных условиях, который может быть неизвестен во время компиляции или сборки. Такие условия могут быть наложены разными среды выполнения (например, разные версии операционной системы или разные наборы и комбинации драйверов или служб, загруженных в конкретную целевую среду), которые могут потребовать разных наборов особых случаев в коде, но в то же время стать условно мертвым кодом для другие случаи.^[5][6] Кроме того, программное обеспечение (например, драйвер или резидентная служба) может быть сконфигурировано для включения или исключения определенных функций в зависимости от предпочтений пользователя, делая неиспользуемые части кода бесполезными в конкретном сценарии.^[5][6] Хотя модульное программное обеспечение может быть разработано для динамической загрузки библиотек только по запросу, в большинстве случаев невозможно загрузить только соответствующие подпрограммы из конкретной библиотеки, и даже если это будет поддерживаться, подпрограмма может по-прежнему включать разделы кода, которые могут считаться мертвым кодом в данном сценарии, но не может быть исключен уже во время компиляции.

Методы, используемые для динамического обнаружения спроса, выявления и разрешения зависимостей, удаления такого условно мертвого кода и рекомбинации оставшегося кода при нагрузка или же время выполнения называются динамическое устранение мертвого кода^{[5][6][7][8][9][10][11][12][13][14][15][16][17]} или же динамическое устранение мертвых инструкций.^[18]

Большинство языков программирования, компиляторов и операционных систем не предлагают или почти не поддерживают больше, чем динамическая загрузка библиотек и позднее связывание, поэтому программное обеспечение, использующее динамическое удаление мертвого кода, очень редко в сочетании с языками составлен заранее или написано в язык ассемблера.^[7][11][8] Однако языковые реализации, выполняющие своевременная компиляция может динамически оптимизироваться для устранения мертвого кода.^[17][19][20]

Хотя с довольно разной направленностью, похожие подходы иногда также используются для динамическое обновление программного обеспечения и горячее исправление.

Смотрите также

• Резервный код
• Упрощение (символьное вычисление)
• Устранение частичной избыточности
• Устранение конъюнкции
• Математическое исключение
• Динамическое обновление ПО
• Динамическая связь (вычисления)
• Программное обеспечение
• Дерево трясется
• Постпроходная оптимизация
• Профильная оптимизация
• Супероптимизатор
• Сжатие сборки мусора
• Самовоспроизведение

Рекомендации

дальнейшее чтение

• Бодик, Растислав; Гупта, Раджив (Июнь 1997 г.). «Частичное устранение мертвого кода с помощью нарезных преобразований». Труды конференции ACM SIGPLAN 1997 по проектированию и реализации языков программирования (PLDI '97): 682–694.
• Ахо, Альфред Вайно; Сетхи, Рави; Ульман, Джеффри Дэвид (1986). Компиляторы - принципы, методы и инструменты. Издательство Эддисон Уэсли. ISBN  0-201-10194-7.
• Мучник, Стивен Стэнли (1997). Расширенный дизайн и реализация компилятора. Издательство Morgan Kaufmann. ISBN  1-55860-320-4.
• Грун, Дик; Бал, Анри Эль; Jacobs, Ceriel J. H .; Лангендоэн, Коэн Г. (2000). Современный дизайн компилятора. John Wiley & Sons, Inc. ISBN  0-471-97697-0.
• Кеннеди, Кен; Аллен, Рэнди (2002). «Глава 4.4. Анализ потока данных - Глава 4.4.2. Устранение мертвого кода». Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях (2011 г., цифровая печать, 1-е изд.). Академическая пресса / Издательство Morgan Kaufmann / Эльзевир. стр.137, 145–147, 167. ISBN  978-1-55860-286-1. LCCN  2001092381.

внешняя ссылка

• Как заставить компиляторы C / C ++ генерировать ужасный код?