14-10-2023
В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными[en], то есть переменными, значения которых в дальнейшем в программе не используются[1][2].
В связи с существующим разночтением термина мёртвый код[3][4], важно отметить, что оптимизация удаления мёртвого кода не занимается удалением недостижимого кода. Локализацией и удалением недостижимого кода занимается оптимизация удаления недостижимого кода[2].
Удаление бесполезного кода способно ускорить работу программы за счёт уменьшения количества исполняемых в ней операций и уменьшить размер программы или промежуточного представления[en].
Содержание |
Рассмотрим следующий код на языке Си:
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») отмечает (маркирует) все заведомо живые операции (операции выхода из процедуры, ввода/вывода, изменяющие глобальные переменные); второй обход SSA-формы («Sweep») начинается с живых операций и идёт вверх по определениям аргументов, помечая все операции на своём пути живыми, заканчивая теми операциями, которые не имеют предшественников[5]. Максимальная вычислительная сложность такого алгоритма зависит от размера программы как O(n2)[6].
DCE может не проводить никакого самостоятельного анализа, а просто воспользоваться результатами анализа активных переменных[en][7], но вычислительная сложность такого анализа составляет O(n3) в худшем случае[6]. Существуют специфические алгоритмы, занимающиеся удалением пустых узлов в CFG-графе, объединением нескольких базовых блоков в один и т.п., для такого анализа нужен построенный граф потока управления[8].
Алгоритм «Dead» был впервые опубликован в статье «Static Single Assignment Form and the Program Dependence Graph» в журнале ACM TOPLAS в 1991 году[9]. Алгоритм «Clean», работающий с CFG-графом был разработан и реализован Робом Шиллером в 1992 году[10].
Удаление мёртвого кода может применяться несколько раз в процессе компиляции, так как мёртвый код находится в программе не только из-за того, что он содержится в исходном коде — некоторые другие преобразования способны делать код мёртвым. К примеру, оптимизации распространение копий[en] и распространение констант часто превращают инструкции в бесполезный код[11][1]. Так же приходится удалять мёртвый код, созданный другими преобразованиями в компиляторе[11]. Например, классический алгоритм оптимизации понижения силы операции замещает трудоёмкие операции менее трудоёмкими, после чего удаление мёртвого кода устраняет старые операции и завершает преобразование (без усложнения алгоритма снижения силы)[12].
Удаление мёртвого кода.