|
Удаление мёртвого кодаВ теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все результаты вычисления такого кода являются мёртвыми переменными[англ.], то есть переменными, значения которых в дальнейшем в программе не используются[1][2]. Существует разночтение термина мёртвый код[3][4]. При этом, оптимизация удаления мёртвого кода не занимается удалением недостижимого кода. Локализацией и удалением недостижимого кода могут заниматься сборщик мусора[5] или другие оптимизации, например, удаления недостижимого кода[2]. Удаление бесполезного кода способно ускорить работу программы за счёт уменьшения количества исполняемых в ней операций и уменьшить размер программы или промежуточного представления. ПримерыРассмотрим следующий код на языке Си: int foo(void)
{
int a = 24;
int b;
b = a + 3; /* Бесполезный код */
return a << 2;
}
В данном примере операция сложения int foo(void)
{
int a = 24;
int b; /* Мёртвая переменная */
return a << 2;
}
После удаления операции сложения, переменная int foo(void)
{
int a = 24;
return a << 2;
}
Несмотря на то что вычисление происходит внутри функции, его результат записывается в переменную, находящуюся в области видимости только этой функции; и если учесть что функция безусловно возвращает число 96, она может быть упрощена оптимизацией распространение констант так, чтобы её тело состояло только из операции АлгоритмыКлассический алгоритм DCE («Dead») работает на SSA-представлении и состоит из двух обходов: первый обход («Mark») отмечает (маркирует) все заведомо живые операции (операции выхода из процедуры, ввода-вывода, изменяющие глобальные переменные); второй обход («Sweep») начинается с живых операций и идёт вверх по определениям аргументов, помечая все операции на своём пути живыми, заканчивая теми операциями, которые не имеют предшественников в SSA-форме[6]. Максимальная вычислительная сложность такого алгоритма зависит от размера программы как O(n2)[7]. DCE может не проводить никакого самостоятельного анализа, а просто воспользоваться результатами анализа активных переменных[англ.][8], но вычислительная сложность такого анализа составляет O(n3) в худшем случае[7]. Существуют специфические алгоритмы, занимающиеся удалением пустых узлов в CFG-графе, объединением нескольких базовых блоков в один и т.п., для такого анализа нужен построенный граф потока управления[9]. Алгоритм «Dead» был впервые опубликован в статье «Static Single Assignment Form and the Program Dependence Graph» в журнале ACM TOPLAS в 1991 году[10]. Алгоритм «Clean», работающий с CFG-графом был разработан и реализован Робом Шиллером в 1992 году[11]. ПрименениеУдаление мёртвого кода может применяться несколько раз в процессе компиляции, так как мёртвый код находится в программе не только из-за того, что он содержится в исходном коде — некоторые другие преобразования способны делать код мёртвым. К примеру, оптимизации распространение копий[англ.] и распространение констант часто превращают инструкции в бесполезный код[1][12]. Также приходится удалять мёртвый код, созданный другими преобразованиями в компиляторе[12]. Например, классический алгоритм оптимизации понижения силы операции замещает трудоёмкие операции менее трудоёмкими, после чего удаление мёртвого кода устраняет старые операции и завершает преобразование (без усложнения алгоритма снижения силы)[13]. Интересные факты
См. такжеПримечания
Литература
Ссылки |