Недостижимый код

В программировании и теории компиляторов, недостижимым кодом называют часть кода программы, которая ни при каких условиях не может быть исполнена, поскольку является недостижимой в графе потока управления^[1][2].

Недостижимый код часто относят к одному из типов мёртвого кода, такая терминология обычно применяется при рассмотрении исходного кода программ^[3][4]. Однако в теории компиляторов, эти понятия ни как не связаны, мёртвым кодом там называют только достижимый, но не влияющий на вывод программы код^[1][5][2].

Основные недостатки наличия в программе недостижимого кода:

• Занимает излишнюю память;
• Является причиной излишнего кэширования инструкций в кэш инструкций CPU — которое так же снижает локальность данных;
• Затрудняет поддержку приложений — время и силы могут быть потрачены на поддержку и документирование части кода, которая является недостижимой, а значит никогда не исполняется.

Причины

Существование недостижимого кода может быть обусловлено разными факторами, например:

• Программные ошибки в сложных условных переходах;
• Вследствие внутренних преобразований, выполняемых оптимизирующим компилятором;
• Неполное тестирование новой или модифицированной программы, которому не удалось обнаружить недостижимый код;
• При исправлении одной ошибки, программист создал другую ошибку, которая обходит недостижимый код и не была обнаружена во время тестирования;
• Устаревший код, который не был полностью удалён программистом, так как он был смешан с действующим кодом;
• Устаревший код, который программист забыл удалить;
• Ранее полезный код, который никогда не будет исполнен, так как, в дальнейшем, ввод данных никогда не приведёт к исполнению этого кода;
• Устаревший код, который был намеренно сохранён, но сделан недостижимым, для того чтобы его можно было при необходимости снова включить в программу;
• Отладочные конструкции и остаточные части кода, которые еще должны быть удалены из программы.

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

Примеры

Рассмотрим следующий пример на языке Си:

 int foo(int x, int y)
 {
   return x + y;
   int z = x*y;  /* Недостижимый код */
 }

Операция int z = x*y является недостижимым кодом, так как перед ней выполняется выход из процедуры (операции, стоящие после возврата из процедуры могут и не являться недостижимым кодом, например, если на метку, стоящую после возврата ссылается оператор goto).

Анализ

Поиск недостижимого кода в исходном коде может быть выполнен с помощью статического анализа кода^[3][4]. В оптимизирующем компиляторе, выявить и удалить недостижимый код способна оптимизация удаления недостижимого кода, которая находит в графе потока управления недостижимые узлы и удаляет их^[6]. Простой анализ CFG-графа на недостижимые узлы часто бывает реализован в компиляторе в виде отдельной функции, т.н. сборщика мусора, которая вызывается сразу после преобразований, способных изменять граф потока управления^[7].

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

На практике, сложность реализуемого анализа существенно влияет на количество выявляемого недостижимого кода. Например, после свёртки констант и простого анализа потока управления можно обнаружить, что код внутри оператора if в следующем примере является недостижимым:

 int foo(void)
   int n = 2 + 1;
   if (n > 4)
   {
     printf("%d", n);  /* Недостижимый код */
   }
 }

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

 int foo(void)
   double x = sqrt(2);
   if (x > 4)
   {
     printf("%lf", x);  /* Недостижимый код */
   }
 }

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

См. также

• Мёртвый код
• Удаление мёртвого кода
• Удаление недостижимого кода

Примечания

1. ↑ ^{1 2} Engineering a Compiler — С. 544.
2. ↑ ^{1 2} Debray, S. K., Evans, W., Muth, R., and De Sutter, B. 2000. Compiler techniques for code compaction. ACM Trans. Program. Lang. Syst. 22, 2 (Mar. 2000), 378-415. (summary Архивировано)
3. ↑ ^{1 2} Dead code detection and removal. Aivosto. Архивировано из первоисточника 6 августа 2012.
4. ↑ ^{1 2} Compares some free alternatives to DCD (Dead Code Detector). Java.net. Архивировано из первоисточника 23 сентября 2012.
5. ↑ Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код).
6. ↑ Engineering a Compiler — С. 550.
7. ↑ А.Ю.Дроздов, А.М.Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, №3 (текст Архивировано)

Литература

• Cooper and Torczon Engineering a Compiler. — Morgan Kaufmann, 2011. — С. 544-550, 593. — ISBN 978-0-12-088478-0
• Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. Компиляторы — принципы, технологии, инструменты. — Вильямс, 2003. — С. 669, 670, 568-609. — ISBN 5-8459-0189-8
• Muchnick, Steven S. Advanced Compiler Design and Implementation. — Morgan Kaufmann Publishers, 1997. — С. 580-582. — ISBN 1-55860-320-4