Устранение мертвого кода
В теории компилятора устранение мертвого кода ( DCE , удаление мертвого кода , удаление мертвого кода или удаление мертвого кода ) — это оптимизация компилятора для удаления мертвого кода (кода, который не влияет на результаты программы). Удаление такого кода имеет несколько преимуществ: оно уменьшает размер программы , что является важным фактором в некоторых контекстах, снижает использование ресурсов, таких как количество передаваемых байтов. [ 1 ] и это позволяет работающей программе избегать выполнения ненужных операций , что сокращает время ее работы . Это также может обеспечить дальнейшую оптимизацию за счет упрощения структуры программы. Мертвый код включает код, который никогда не может быть выполнен ( недоступный код ), и код, который влияет только на мертвые переменные (записаны, но никогда не читаются снова), то есть не имеет отношения к программе.
Примеры
[ редактировать ]Рассмотрим следующий пример, написанный 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 никогда не сможет быть выполнен, а устранение мертвого кода полностью удалит его из оптимизированной программы. Этот метод часто используется при отладке и позволяет дополнительно активировать блоки кода; использование оптимизатора с устранением мертвого кода устраняет необходимость использования препроцессора для выполнения той же задачи.
На практике большая часть мертвого кода, который находит оптимизатор, создается в результате других преобразований оптимизатора. Например, классические методы снижения нагрузки на операторов включают в код новые вычисления и уничтожают старые и более дорогостоящие вычисления. [ 2 ] Последующее устранение мертвого кода удаляет эти вычисления и завершает эффект (не усложняя алгоритм уменьшения силы).
Исторически устранение мертвого кода выполнялось с использованием информации, полученной в результате анализа потока данных . [ 3 ] Алгоритм, основанный на статической форме с одним присвоением (SSA), представлен в оригинальной журнальной статье SSA . Рона Цитрона и др. о форме [ 4 ] Роберт Шиллингсбург (он же Шилнер) усовершенствовал алгоритм и разработал сопутствующий алгоритм для удаления бесполезных операций потока управления. [ 5 ]
Динамическое устранение мертвого кода
[ редактировать ]Мертвый код обычно считается мертвым безоговорочно . Поэтому разумно попытаться удалить мертвый код путем устранения мертвого кода во время компиляции .
Однако на практике разделы кода также часто представляют мертвый или недостижимый код только при определенных условиях , которые могут быть неизвестны во время компиляции или сборки. Такие условия могут налагаться разными средами выполнения (например, разными версиями операционной системы или разными наборами и комбинациями драйверов или служб, загруженных в конкретную целевую среду), что может требовать разных наборов особых случаев в коде, но при этом в то же время стал условно мертвым кодом для остальных случаев. [ 6 ] [ 7 ] Кроме того, программное обеспечение (например, драйвер или резидентная служба) может быть настроено для включения или исключения определенных функций в зависимости от предпочтений пользователя, что делает неиспользуемые части кода бесполезными в конкретном сценарии. [ 6 ] [ 7 ] Хотя модульное программное обеспечение может быть разработано для динамической загрузки библиотек только по требованию, в большинстве случаев невозможно загрузить только соответствующие процедуры из конкретной библиотеки, и даже если это будет поддерживаться, процедура все равно может включать разделы кода, которые могут можно считать мертвым кодом в данном сценарии, но его нельзя исключать уже во время компиляции.
Методы, используемые для динамического обнаружения спроса, идентификации и разрешения зависимостей, удаления такого условно мертвого кода и повторного объединения оставшегося кода при загрузке или во время выполнения, называются динамическим устранением мертвого кода. [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ] [ 17 ] [ 18 ] или динамическое устранение неработающих инструкций . [ 19 ]
Большинство языков программирования, компиляторов и операционных систем не предоставляют никакой или незначительной поддержки, кроме динамической загрузки библиотек и позднего связывания , поэтому программное обеспечение, использующее динамическое устранение мертвого кода, очень редко встречается в сочетании с языками, скомпилированными заранее или написанными на языке ассемблера . [ 8 ] [ 12 ] [ 9 ] Однако реализации языка, выполняющие своевременную компиляцию, могут динамически оптимизироваться для устранения мертвого кода. [ 18 ] [ 20 ] [ 21 ]
Подобные подходы иногда используются и для динамического обновления программного обеспечения и горячего исправления , хотя и с несколько иной направленностью .
См. также
[ редактировать ]- Дублирующий код
- Упрощение (символическое вычисление)
- Устранение частичного резервирования
- Устранение союза
- Динамическое обновление программного обеспечения
- Динамическая связь (вычисления)
- Самостоятельный переезд
- Программные костыли
- Дерево трясется
- Оптимизация после прохода
- Оптимизация на основе профиля
- Супероптимизатор
- Функция многоверсионности
Ссылки
[ редактировать ]- ^ Малавольта, Ивано и др. «Идентификация, устранение и эмпирическая оценка мертвого кода JavaScript». Транзакции IEEE по разработке программного обеспечения 49.7 (2023 г.): 3692–3714. Веб.
- ^ Аллен, Фрэнсис; Кок, Джон ; Кеннеди, Кен (июнь 1981 г.). «Сокращение численности операторов». В Джонсе, Нил Д .; Мучник, Стивен Стэнли (ред.). Анализ потока программы: теория и применение . Прентис-Холл . ISBN 0-13729681-9 .
- ^ Кеннеди, Кен (июнь 1981 г.). «Обзор методов анализа потоков данных». В Джонсе, Нил Д .; Мучник, Стивен Стэнли (ред.). Анализ потока программы: теория и применение . Прентис-Холл . ISBN 0-13729681-9 .
- ^ Сайтрон, Рон К.; Ферранте, Жанна ; Розен, Барри К.; Задек, Ф. Кеннет (1991). Эффективное вычисление статической формы одиночного задания и графа зависимости программы . АСМ ТОПЛАС 13(4).
- ^ Купер, Кейт Д .; Торчон, Линда (2003) [2002-01-01]. Разработка компилятора . Морган Кауфманн . стр. 498 и далее. ISBN 978-1-55860698-2 .
- ^ Jump up to: а б с Пол, Матиас Р. (3 апреля 2002 г.) [18 июня 2001 г.]. «[fd-dev] Ctrl+Alt+Del» . freedos-dev . Архивировано из оригинала 9 сентября 2017 г. Проверено 9 сентября 2017 г.
[…] любая из […] опций может быть «навсегда» исключена во время установки (также будет сохранена память для соответствующих фрагментов кода благодаря нашему динамическому устранению мертвого кода ), или ее можно отключить или включить в любое позднее время. через функции API на случай, если кто-то захочет запретить пользователю перезагрузить компьютер. […] мы рассматриваем возможность добавления большего количества синхронных вызовов очистки кэша […] Благодаря нашему методу динамического устранения мертвого кода это не приведет к какому-либо раздуванию, когда это не требуется в конкретной целевой конфигурации, поскольку конкретный вызов очистки кэша будет включен в Образ времени выполнения FreeKEYB только в том случае, если соответствующий дисковый кэш также загружен или ключи командной строки дали FreeKEYB указание загрузить соответствующую поддержку.
- ^ Jump up to: а б с Пол, Матиас Р. (6 апреля 2002 г.). «[fd-dev] Ctrl+Alt+Del» . freedos-dev . Архивировано из оригинала 27 апреля 2019 г. Проверено 27 апреля 2019 г.
[…] FreeKEYB создает образ времени выполнения драйвера во время инициализации в зависимости от типа компьютера, на котором он загружается, типа клавиатуры, раскладки, страны и используемой кодовой страницы, типа установленной мыши и видеоадаптеров, другие драйверы, загруженные в эту систему, операционную систему и используемые методы загрузки и перемещения, включенные отдельные функции и параметры конфигурации, указанные в командной строке. Из-за большого количества поддерживаемых переключателей и опций командной строки […] (около пятидесяти переключателей […] с несколькими возможными настройками) существует большое количество комбинаций функций с бесчисленными зависимостями […], что приводит к […] бесконечному количеству [ …] разные целевые изображения. Технология динамического устранения мертвого кода FreeKEYB позволяет разрешить […] эти […] зависимости и […] удалить мертвый код и данные […] не ограничивается […] включением или исключением несколько ограниченного количества модулей или целых подпрограмм. и исправить некоторые таблицы диспетчеризации, как в классическом программировании TSR, но […] работает […] на [...] уровне байтов […] способно удалять […] отдельные инструкции в середине более крупных процедур […] распределенных по всему код для обработки конкретного случая или поддержки определенной функции […] специальные инструменты используются для анализа кода […] и создания […] таблиц исправлений […] автоматически […] с использованием условных определений […] для объявления различных случаев […] не только необязательно во время сборки, но и во время инициализации […] без […] накладных расходов, связанных с наличием хотя бы некоторого количества мертвого кода в рабочем образе […] для отслеживания всех зависимостей между […] эти условные выражения, динамически создавать и перемещать образ времени выполнения, исправлять все ссылки между этими небольшими, изменяющимися и движущимися двоичными частями […] по-прежнему позволяя использовать крошечный стиль .COM/.SYS […] модель […] готова во время инициализации […] API для импорта и экспорта структур объектов между FreeKEYB и вызывающим приложением […] для прозрачного изменения размера и перемещения их внутри […] во время выполнения […]
- ^ Jump up to: а б Пол, Матиас Р.; Фринке, Аксель К. (13 октября 1997 г.) [впервые опубликовано в 1991 г.], FreeKEYB - Расширенный драйвер клавиатуры и консоли для DOS (Руководство пользователя) (изд. v6.5) [1] (Примечание. FreeKEYB - это Unicode динамически основанный на драйвер настраиваемый преемник K3PLUS, поддерживающий большинство раскладок клавиатуры , кодовых страниц и кодов стран . Использование готового ассемблера макросов , а также системы инструментов автоматического анализа предварительной и постобработки для генерации зависимостей и морфинга кода метаданных . встроенный в исполняемый файл вместе с двоичным кодом и самоудаляющимся, расслабляющим и перемещающим загрузчиком , драйвер реализует мертвого кода детального динамического устранения и перемещения методы на уровне байтов во время загрузки , а также самомодифицирующийся код и возможность реконфигурации при запуске. - время свести к минимуму объем памяти, чтобы закрыть каноническую форму, в зависимости от базового оборудования, операционной системы и конфигурации драйверов, а также выбранного набора функций и языкового стандарта (около шестидесяти переключателей конфигурации с сотнями опций для почти неограниченного числа возможных комбинаций). ). Эта сложность и динамика скрыты от пользователей, которые имеют дело с одним исполняемым файлом так же, как с обычным драйвером. K3PLUS — расширенный драйвер клавиатуры для DOS в свое время широко распространялась в Германии, и была доступна адаптация к нескольким другим европейским языкам. Он уже поддерживал подмножество функций, но не реализовал динамическое устранение мертвого кода.)
- ^ Jump up to: а б Пол, Матиас Р. (10 апреля 2001 г.). «[ANN] Выпущена бета-версия 6 FreeDOS» (на немецком языке). Группа новостей : de.comp.os.msdos . Архивировано из оригинала 9 сентября 2017 г. Проверено 2 июля 2017 г.
[...] совершенно новая функция, динамическое устранение мертвого кода , которая собирает и перемещает необходимые компоненты драйвера только во время установки, так что неиспользуемый код или области данных не остаются резидентными (например, если у кого-то есть определенная функция FreeKEYB не требуется). […]
(Примечание. Это первая известная реализация детального динамического устранения мертвого кода на уровне байтов для программного обеспечения, собранного или скомпилированного заранее .) - ^ Пол, Матиас Р. (21 августа 2001 г.). «[fd-dev] Изменение кодовых страниц во FreeDOS» . freedos-dev . Архивировано из оригинала 19 апреля 2019 г. Проверено 20 апреля 2019 г.
[…] […] уникальная функция […] мы называем динамическое устранение мертвого кода , поэтому вы можете во время установки […] указать, какие компоненты драйвера вам нужны, а какие нет. Это касается динамической загружаемой модульности и позднего связывания, которых я до сих пор не видел в DOS. Если вам не нравится заставка, макросы, калькулятор или поддержка мыши или <почти что-нибудь еще>, вы можете указать это в командной строке, и FreeKEYB, принимая во внимание все зависимости между подпрограммами, полностью удалите все фрагменты кода, которые связаны с этой функцией и не являются необходимыми для обеспечения запрошенной функциональности, прежде чем драйвер переместит образ в целевое местоположение и станет резидентным. Удаление некоторых более мелких функций сэкономит всего пару байт, но исключение более сложных компонентов может сэкономить полКб и более. Вы также можете указать размер областей данных […]
- ^ Пол, Матиас Р. (30 декабря 2001 г.). «Внутренняя структура KEYBOARD.SYS» . Группа новостей : comp.os.msdos.programmer . Архивировано из оригинала 9 сентября 2017 г. Проверено 3 июля 2017 г.
[…] загрузчик будет динамически оптимизировать резидентные области данных и разделы кода на уровне байтов, чтобы удалить любую избыточность из драйвера в зависимости от данной конфигурации оборудования/программного обеспечения/драйвера и языкового стандарта. […]
- ^ Jump up to: а б Пол, Матиас Р.; Фринке, Аксель К. (16 января 2006 г.), FreeKEYB - Расширенный международный драйвер клавиатуры и консоли для DOS (Руководство пользователя) (предварительная версия v7)
- ^ Пол, Матиас Р. (2 февраля 2002 г.). «Treiber dynamisch nachladen (Intra-Segment-Offset-Relokation zum Laden von TSRs in die HMA)» [Динамическая загрузка драйверов (перемещение внутрисегментного смещения для загрузки TSR в HMA)] (на немецком языке). Группа новостей : de.comp.os.msdos . Архивировано из оригинала 9 сентября 2017 г. Проверено 2 июля 2017 г.
- ^ Пол, Матиас Р. (24 февраля 2002 г.). «Информация GEOS/NDO для RBIL62?» . Группа новостей : comp.os.geos.programmer . Архивировано из оригинала 20 апреля 2019 г. Проверено 20 апреля 2019 г.
[…] Поскольку FreeKEYB использует наше динамическое устранение мертвого кода для оптимизации образа памяти для целевой среды во время загрузки, я бы определенно хотел добавить в FreeKEYB для GEOS специальную поддержку , которой можно было бы управлять с помощью параметра командной строки, поэтому дополнительный код загружается только при использовании GEOS. […]
- ^ Пол, Матиас Р. (15 марта 2002 г.). «Слой клавиатуры AltGr под GEOS?» . Группа новостей : comp.os.geos.misc . Архивировано из оригинала 20 апреля 2019 г. Проверено 20 апреля 2019 г.
[…] Я бы хотел добавить специальные крючки в FreeKEYB, наш продвинутый драйвер клавиатуры для DOS, чтобы это улучшило удобство использования в GEOS […] Благодаря нашей сложной новой технологии динамического устранения мертвого кода , которая удаляет на уровне байтов любой код фрагменты, не используемые в конкретном драйвере, пользователе или конфигурации системы и аппаратной среде, когда установщик драйвера создает и перемещает сам загрузочный образ, это вообще не влияет на память для пользователей, не использующих GEOS, поэтому не о чем беспокоиться (объем памяти и т. д.), как в традиционно запрограммированных драйверах DOS. […]
- ^ Тамманур, Сатьянараян (31 января 2001 г.). Структура распределения регистров «точно в срок» и оптимизации кода для встраиваемых систем (дипломная работа MS). Университет Цинциннати , Инженерное дело: Компьютерная инженерия. ucin982089462. [2] Архивировано 28 июля 2019 г. в Wayback Machine. [3] Архивировано 28 июля 2019 г. в Wayback Machine.
- ^ Глю, Энди (2 марта 2011 г.). «Динамическое устранение мертвого кода и будущее оборудования» . [ постоянная мертвая ссылка ] [4] [5]
- ^ Jump up to: а б Конвей, Эндрю (4 декабря 1995 г.). «Циклические структуры данных» . Группа новостей : comp.lang.functional . Архивировано из оригинала 9 сентября 2017 г. Проверено 3 июля 2017 г.
[…] Ленивая оценка — это, по сути, динамическое устранение мертвого кода . […]
(Примечание. Возможно, это первое публичное использование термина динамическое устранение мертвого кода , хотя только концептуально и с акцентом на ленивые вычисления в функциональных языках .) - ^ Баттс, Дж. Адам; Сохи, Гури (октябрь 2002 г.). «Динамическое обнаружение и устранение недействительных инструкций» (PDF) . Сан-Хосе, Калифорния, США: Факультет компьютерных наук, Университет Висконсин-Мэдисон . АСПЛОС Х АСМ 1-58113-574-2/02/0010. Архивировано (PDF) из оригинала 20 апреля 2019 г. Проверено 23 июня 2017 г.
- ^ Джонг, Йесонг; Даниэльссон, Пер; Энсиё, Пер; Херманссон, Матс; Йоланки, Мика; Мур, Скотт; Страндер, Ларс; Веттергрен, Ларс (8 ноября 2002 г.). «Глава 5. Обзор Java и реализация iSeries — 5.1.1. Различные компоненты». Intentia Movex Java на сервере IBM iSeries — Руководство по внедрению — Обзор Movex Java на сервере iSeries — Установка и настройка Movex Java на iSeries — Советы и приемы по эксплуатации (PDF) . Красные книги. IBM Corp. с. 41. ИСБН 0-73842461-7 . SG24-6545-00. Архивировано (PDF) из оригинала 8 октября 2013 г. Проверено 20 апреля 2019 г. [6]
- ^ Полито, Гильермо (2015). «Поддержка виртуализации для специализации и расширения среды выполнения приложений — языки программирования» (PDF) . Университет наук и технологий Лилля . стр. 111–124. Идентификатор HAL: тел-01251173. Архивировано (PDF) из оригинала 23 июня 2017 г. Проверено 23 июня 2017 г.
Дальнейшее чтение
[ редактировать ]- Бодик, Растислав; Гупта, Раджив (июнь 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]