Часть 1 Часть 2 Часть 3 В первой части серии мы рассмотрели неопределенное поведение в C и показали некоторые случаи, когда C работает быстрее, чем «безопасные» языки.
Во второй части мы рассмотрели некоторые неожиданные ошибки, которые могут противоречить представлениям многих программистов о языке C. В этой части мы рассмотрим проблемы, которые решает компилятор Clang для достижения высокой производительности, и устраним некоторые сюрпризы.
Почему нет предупреждения, что оптимизация основана на UB?
Часто спрашивают, почему компилятор не выдает предупреждений при оптимизации на основе неопределенного поведения, ведь каждый такой случай может быть вызван ошибкой в пользовательском коде.Проблемы с этим подходом заключаются в следующем: 1) он будет генерировать слишком много предупреждений, чтобы быть полезным, поскольку такие оптимизации происходят постоянно и при отсутствии ошибок, 2) действительно сложно генерировать такие предупреждения только тогда, когда люди этого хотят, 3) несколько последовательных оптимизаций объединяются вместе.
Давайте рассмотрим каждый пункт более подробно:
Очень сложно сделать предупреждения действительно полезными
Давайте рассмотрим пример: хотя ошибки анализа псевдонимов на основе типов (TBBA) являются обычным явлением, при оптимизации примера было бы бесполезно генерировать сообщения типа «оптимизатор предполагает, что P и P[i] не являются псевдонимами».«zero_array» (из первой части серии).
Помимо проблемы «ложных срабатываний», существует логистическая проблема, заключающаяся в том, что оптимизатору не хватает информации для генерации содержательных предупреждений.float *P; void zero_array() { int i; for (i = 0; i < 10000; ++i) P[i] = 0.0f; }
Во-первых, он работает на основе абстрактного представления кода (LLVM IR), которое совершенно отличается от C, а во-вторых, компилятор имеет много слоев, и в тот момент, когда оптимизатор пытается переместить чтение из P за пределы цикла, он не знает об анализе ТБАА.
Это действительно сложная проблема.
Трудно генерировать эти предупреждения только потому, что люди этого хотят. Clang реализует различные предупреждения для простых и очевидных случаев неопределенного поведения, например, выхода за пределы операции сдвига, например «x << 421".
You might think this is a simple and obvious thing, but it turns out to be difficult because people don't want to be warned about UB in dead code. Мертвый код имеет несколько форм, например, макросы, которые таким странным образом разворачивались, когда им передавали константу.
Возможна ситуация, когда некоторые опции в операторе переключения (доказуемо) не выполняются, и пользователь будет недоволен, если мы выдадим предупреждения о коде, расположенном в этих местах.
Кроме того, операторы переключения в программах на языке C не обязательно хорошо структурированы.
Решение состоит в том, что Clang собирает предупреждения о «поведении во время выполнения», а затем удаляет те, которые относятся к блокам, которые не будут выполнены.
Проблема здесь в том, что существуют идиомы, которых мы не ожидаем, и выполнение этих действий во внешнем интерфейсе означает, что мы не сможем отловить каждый экземпляр, который пользователи хотят, чтобы мы перехватили.
Последовательности оптимизаций открывают возможности для новых оптимизаций.
Если так сложно генерировать предупреждения во фронтенде, возможно, мы сможем сгенерировать их с помощью оптимизатора! Самой большой проблемой при создании полезных сообщений является отслеживание данных.
Оптимизатор компилятора включает в себя десятки проходов оптимизации, каждый из которых меняет код, чтобы сделать его (надеюсь) быстрее.
Если инлайнер решит встроить функцию, это может открыть новые возможности для удаления, например, выражений типа «X*2/2».
Хотя мы коснемся простых и ограниченных примеров для демонстрации этих оптимизаций, большинство реальных случаев происходит в коде, который генерируется путем расширения макросов, встраивания функций и других действий по удалению абстракций высокого уровня, которые выполняет компилятор.
Реальность такова, что люди обычно не пишут глупости напрямую.
Для предупреждений это означает, что для ссылки на пользовательский код вам необходимо точно восстановить, как компилятор получил промежуточный код. Нам нужно было бы иметь возможность сказать что-то вроде: предупреждение: после трех уровней встраивания функций (возможно, расположенных в разных файлах во время оптимизации времени компоновки), удаления общих подвыражений, выведения их из цикла и доказательства того, что эти 13 указателей не являются псевдонимами, мы нашли место, где вы делаете что-то неопределенное.
Это может быть из-за ошибки в вашем коде, или из-за макроса, или из-за встроенного кода, а плохой код на самом деле недоступен, но мы не можем доказать, что он мертв.
К сожалению, у нас нет инфраструктуры, чтобы отслеживать это, а даже если бы и была, у компилятора нет достаточно хорошего пользовательского интерфейса, чтобы передать все это программисту.
Вообще UB ценен для оптимизатора тем, что говорит «операция некорректна — можно предположить, что она никогда не произойдет».
В случае «*P» это дает оптимизатору основание полагать, что P не равно NULL. В случае «*NULL» (например, после подстановки констант и встраивания) это позволяет оптимизатору предположить, что такой код недоступен.
Важным предположением является то, что, поскольку проблема остановки не может быть решена, у компилятора нет возможности узнать, действительно ли код мертв (как и должно быть по стандарту C) или это ошибка, возникшая в результате (возможно, длинной) серии ошибок.
оптимизации.
Поскольку в целом не существует хорошего способа отличить эти две вещи, почти все эти предупреждения будут ложноположительным шумом.
Подход Clang к UB
Учитывая столь печальное положение дел с UB, вы можете спросить, что делают Clang и LLVM, чтобы улучшить ситуацию.Я уже упоминал пару вещей: статический анализатор Clang, Klee и флаг -fcatch-undefine-behavior — полезные инструменты для отслеживания некоторых классов этих ошибок.
Проблема в том, что они не так широко используются, как компилятор, и все, что мы можем сделать непосредственно в компиляторе, будет гораздо большим благом, чем то, что делается отдельными инструментами.
Помните, что компилятор ограничен отсутствием динамической информации, а также ограничен тем, что не может тратить слишком много времени на компиляцию.
Первым шагом Clang к улучшению кода является включение по умолчанию большего количества предупреждений, чем в других компиляторах.
Хотя некоторые разработчики дисциплинированы и компилируют, например, с «-Wall -Wextra», многие не знают об этих флагах или не утруждают себя их включением.
Включив больше предупреждений по умолчанию, мы выявим больше ошибок.
Второй шаг заключается в том, что Clang генерирует предупреждения для многих классов неопределенного поведения (включая разыменование null, сдвиги на слишком большую величину и т. д.), что позволяет вам выявлять типичные ошибки в вашем коде.
Вышеперечисленное отличается Третий шаг заключается в том, что оптимизатор LLVM имеет гораздо меньше свободы в отношении UB, чем мог бы.
Хотя в стандарте говорится, что любой экземпляр неопределенного поведения может иметь неограниченный эффект, получение от него выгоды было бы неудобным для разработчиков.
Вместо этого оптимизатор LLVM обрабатывает их несколькими различными способами (к сожалению, ссылки ведут на правила LLVM IR, а не на C): 1. Некоторые случаи неопределенного поведения просто преобразуются в операции, вызывающие исключение.
Например, Clang для этой функции C++: int *foo(long x) {
return new int[x];
}
компилирует следующий код X86-64: __Z3fool:
movl $4, %ecx
movq %rdi, %rax
mulq %rcx
movq $-1, %rdi # Set the size to -1 on overflow
cmovnoq %rax, %rdi # Which causes 'new' to throw std::bad_alloc
jmp __Znam
вместо кода, который генерирует GCC: __Z3fool:
salq $2, %rdi
jmp __Znam # Security bug on overflow!
Разница в том, что мы решаем потратить несколько циклов на предотвращение потенциально серьёзной ошибки целочисленного переполнения, которая может привести к переполнению буфера и уязвимости (сам новый оператор стоит дорого, поэтому лишние команды практически незаметны).
Разработчики GCC знали об этой уязвимости как минимум с 2005 года, но на момент написания статьи не исправили ее.
( уязвимость была исправлена в GCC 4.8.1 и более поздних версиях.
ок.
перевод ) Арифметические операции над неопределенными значениями могут давать неопределенные значения вместо неопределенного поведения.
Разница в том, что неопределенное значение не может отформатировать ваш жесткий диск или вызвать другие нежелательные эффекты.
Положительный эффект возникает, когда арифметическое выражение приводит к одному и тому же результату для любого возможного варианта неопределенного значения.
Например, оптимизатор предполагает, что результат «undef & 1» имеет нули в старших битах, оставляя неопределенным только младший бит. Это означает, что ((undef & 1) > > 1) в LLVM будет 0, а не неопределенное значение.
Арифметические выражения, которые динамически выполняют неопределенные операции (например, переполнение целого числа со знаком), генерируют значение логической ловушки, которое отравляет любые вычисления, в которых оно используется, но не уничтожает остальную часть программы.
Это означает, что могут быть затронуты последующие логические операции неопределенной операции, но не остальная часть программы.
По этой причине оптимизатор не удаляет код, работающий с неинициализированными переменными.
Запись в значение null и вызов функции по нулевому указателю становится вызовом __builtin_trap() (который, в свою очередь, становится вызовом инструкции «ud2» на x86).
Это происходит постоянно в оптимизированном коде (в результате других преобразований, таких как встраивание функций и распространение констант).
и мы удаляем блоки, содержащие такие команды, потому что они заведомо недоступны.
Если (с точки зрения педантичных стандартов) они действительно недостижимы, то на самом деле мы понимаем, что люди иногда разыменовывают нулевые указатели, что приводит к сбою кода в последующих функциях и очень затрудняет понимание проблемы.
С точки зрения производительности наиболее важным аспектом здесь является сжатие последующего кода.
Таким образом, clang превращает неопределённые операции в ловушку времени выполнения: если одна из них достигается динамически, программа немедленно останавливается и её можно отлаживать.
Недостатком здесь является небольшое раздувание кода, связанное с этими операторами и условиями, управляющими их предикатами.
Оптимизатор прилагает некоторые усилия, чтобы «сделать все правильно» в тех случаях, когда очевидно, что задумал программист (например, в коде «*(int*)P», где P указывает на число с плавающей запятой).
Это помогает во многих случаях, но на это не следует особо полагаться, и существует множество примеров, которые могут показаться вам «очевидными», но это не так после того, как к вашему коду была применена длинная серия преобразований.
Оптимизации, которые не попадают ни в одну из этих категорий, такие как пример с нулевым массивом и набором/вызовом из части 1, оптимизируются, как описано, «тихо», без уведомления пользователя.
Мы делаем это, потому что нет ничего полезного, о чем можно было бы сообщить, и для (ошибочного) реального кода приложения очень необычно, чтобы такие оптимизации нарушали его.
Одна из основных областей улучшения, которую мы можем сделать, связана с этими ловушками.
Я думаю, было бы интересно добавить флаг предупреждения (отключен по умолчанию), который заставит оптимизатор выдавать предупреждения при вставке перехватчиков.
Для некоторых источников это будет очень шумно, но для других будет полезно.
Первым ограничивающим фактором здесь является то, что запуск платформы приведет к тому, что оптимизатор будет выдавать предупреждения: в исходном коде не будет полезных мест, если отладочная информация отключена (но это можно исправить).
Другим, более значимым ограничивающим фактором является то, что в этих предупреждениях не будет никакой информации отслеживания, которая помогла бы объяснить, что операция возникла в результате трехкратного развертывания цикла и встраивания четырех уровней вызовов функций.
Лучшее, что мы можем сделать, это файл/строка/столбец, что будет полезно в большинстве тривиальных случаев, но очень запутанно в других случаях.
В любом случае реализация этого не является для нас приоритетом, потому что: а) это вряд ли обеспечит хороший опыт, б) мы не будем включать эту функцию по умолчанию и в) для ее реализации потребуется много работы.
Использование безопасного диалекта C (и других параметров)
Последний вариант, который у вас есть, если вам не нужна максимальная производительность, — это использовать различные флаги компилятора для использования диалекта C, который устраняет неопределенное поведение.Например, использование флага -fwrapv устраняет неопределенное поведение, вызванное переполнением знаковых чисел (однако обратите внимание, что это не устраняет возможные уязвимости и дыры в безопасности, связанные с переполнением знаковых чисел).
Флаг -fno-strict-aliasing отключает анализ псевдонимов на основе типов, и вы можете игнорировать эти правила типов.
При необходимости мы можем добавить в Clang флаг, который по умолчанию обнуляет все локальные переменные, флаг, который вставляет операцию «и» перед каждым сдвигом с переменной величиной сдвига и т. д. К сожалению, полностью избавиться от этого невозможно.
неопределенного поведения в C без нарушения ABI и полного снижения производительности.
Другая проблема в том, что вы больше не будете писать на C, вы будете писать на диалекте, похожем, но несовместимом с C. Если написание кода на непереносимом диалекте C не для вас, то флаги -ftrapv и -fcatch-undefine-behavior (наряду с другими вещами, упомянутыми ранее) могут стать полезным оружием в вашем арсенале для отслеживания подобных ошибок.
Включение их в отладочную сборку может быть хорошим способом раннего обнаружения ошибок.
Эти флаги также могут быть полезны в рабочей среде, если вы создаете приложение, критически важное для безопасности.
Хотя нет никакой гарантии, что вы найдете все ошибки, они находят полезную подгруппу ошибок.
По сути, настоящая проблема заключается в том, что C не является безопасным языком и (несмотря на его успех и популярность) многие люди не понимают, как на самом деле работает этот язык.
Его стандартизации в 1989 году предшествовали десятилетия разработки, и C превратился из «языка системного программирования низкого уровня, который представляет собой тонкий слой поверх ассемблера PDP» в «язык системного программирования низкого уровня, который пытается достичь высокой производительности, ломая человеческие привычки».
ожидания».
С одной стороны, все приемы C почти всегда работают, и код в целом из-за этого более производительен (а в некоторых случаях и много более).
С другой стороны, чит-локации часто удивляют людей и появляются обычно в самый неподходящий момент. C — это нечто большее, чем просто портативный ассемблер, и иногда он может сильно удивить.
Я надеюсь, что это обсуждение прояснило некоторые вопросы, касающиеся неопределенного поведения в C, по крайней мере, с точки зрения компилятора.
Теги: #llvm #неопределённое поведение #C++ #программирование #компиляторы #C++
-
Беспроводные Центры Обработки Данных
19 Oct, 24 -
Обзор Рынка Моноколес 2018
19 Oct, 24 -
Колония. Эпилог
19 Oct, 24 -
Интернет. Финляндия И Военная Служба
19 Oct, 24
