Устранение мертвого кода

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

Примеры

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

int foo(void) {
  int a = 24;
  int b = 25; /* Assignment to dead variable */
  int c;
  c = a * 4;
  return c;
  b = 24; /* Unreachable code */
  return 0;
}

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

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

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

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

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

int main(void) {
  int a = 5;
  int b = 6;
  int c;
  c = a * (b / 2);
  if (0) {   /* DEBUG */
    printf("%d\n", c);
  }
  return c;
}

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

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

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

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

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

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

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

Большинство языков программирования, компиляторов и операционных систем не предоставляют никакой или незначительной поддержки, кроме динамической загрузки библиотек и позднего связывания , поэтому программное обеспечение, использующее динамическое устранение мертвого кода, очень редко встречается в сочетании с языками, скомпилированными заранее или написанными на языке ассемблера . Однако реализации языка, выполняющие JIT-компиляцию, могут динамически оптимизироваться для устранения мертвого кода.

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

См. также

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

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

• Бодик, Растислав; Гупта, Раджив (июнь 1997 г.). «Частичное устранение неработающего кода с помощью преобразований срезов». Материалы конференции ACM SIGPLAN 1997 года по разработке и реализации языков программирования (PLDI '97) : 682–694.
• Ахо, Альфред Вайно ; Сетхи, Рави ; Уллман, Джеффри Дэвид (1986). Компиляторы — принципы, методы и инструменты . Издательская компания Аддисон Уэсли . ISBN  0-201-10194-7 .
• Мучник, Стивен Стэнли (1997). Расширенное проектирование и реализация компилятора . Издательство Морган Кауфманн . ISBN  1-55860-320-4 .
• Грюн, Дик ; Баль, Анри Эль ; Джейкобс, Сериэль Дж. Х.; Лангендоен, Коэн Г. (2000). Современный дизайн компилятора . Джон Уайли и сыновья, Inc. ISBN  0-471-97697-0 .
• Кеннеди, Кен ; Аллен, Рэнди (2002). «Глава 4.4. Анализ потока данных - Глава 4.4.2. Устранение мертвого кода». Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях (цифровая печать 2011 г., 1-е изд.). Academic Press / Morgan Kaufmann Publishers / Elsevier . стр. 137 , 145–147, 167. ISBN.  978-1-55860-286-1 . LCCN   2001092381 .
• Мут, Роберт; Дебрэ, Саумья К.; Уоттерсон, Скотт; Де Босшер, Коэн (январь 2001 г.) [1999-11-02]. «alto: оптимизатор времени соединения для Compaq Alpha». Программное обеспечение: практика и опыт . 31 (1): 67–101. CiteSeerX   10.1.1.33.4933 . doi : 10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A . S2CID   442062 . [7]

Внешние ссылки

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