В первой части цикла мы рассмотрели неопределённое поведение в С и показали некоторые случаи, которые позволяют сделать С более быстрым, чем «безопасные» языки. В части 2 мы рассмотрели некоторые неожиданные баги, которые могут противоречить представлениям многих программистов об языке С. В этой части, мы рассмотрим проблемы, которые компилятор Clang решает, чтобы достичь высокого быстродействия, и устранить некоторые сюрпризы.
Почему не выдаётся предупреждение, что оптимизация выполнена на основе UB?
Люди часто спрашивают, почему компилятор не генерирует предупреждений когда он производит оптимизацию на основе неопределённого поведения, ведь каждый такой случай может быть вызван багом в пользовательском коде. Сложности в таком подходе следующие: 1) будет генерироваться слишком много предупреждений, чтобы они были полезными — потому что эти оптимизации происходят всё время, и при отсутствии багов, 2) реально сложно сгенерировать такие предупреждения только когда люди их хотят, 3) несколько последовательных оптимизаций объединяются вместе. Рассмотрим каждый пункт более подробно:
Очень трудно сделать предупреждения действительно полезными
Рассмотрим пример: несмотря на то, что баги, связанные с неверным преобразованием типов часто проявляются при TBBA (type based alias analysis), не будет полезным генерировать сообщения типа «оптимизатор предполагает, что P и P[i] не являются алиасами» при оптимизации примера «zero_array» (из части 1 цикла).
float *P;
void zero_array() {
int i;
for (i = 0; i < 10000; ++i)
P[i] = 0.0f;
}Кроме проблемы «ложных положительных срабатываний», есть логистическая проблема, которая состоит в том, что оптимизатор не имеет достаточно информации для генерации осмысленных предупреждений.
Во-первых, он работает на основе абстрактного представления кода (LLVM IR), который совершенно отличается от С, и во-вторых, компилятор имеет много слоёв, и в точке, где оптимизатор пытается вынести чтение из P за пределы цикла, он не знает о анализе TBAA. Это действительно трудная проблема.
Сложно сгенерировать такие предупреждения только потому, что люди этого хотят.
Clang реализует разные предупреждения для простых и очевидных случаев неопределённого поведения, таких, как выход за пределы для операции сдвига типа «x << 421». Вы можете подумать, что это простая и очевидная вещь, но она оказывается сложной, потому что люди не хотят получать предупреждения об UB в «мёртвом коде».
Мёртвый код имеет несколько форм, это могут быть, например, макросы, которые развернулись таким странным образом, когда им передали константу. Может возникнуть ситуация, когда в конструкции switch какие-то варианты (доказуемо) не выполняются, и пользователь будет недоволен, если мы будем выдавать предупреждения о коде, находящемся в этих местах. К тому же выражения switch в С-программах не обязательно хорошо структурированы.
Решение в том, что Clang собирает предупреждения о «рантаймовом поведении», а затем удаляет те из них, которые относятся к блокам, которые не будут исполняться. Сложность здесь заключается в том, что есть идиомы, которых мы не ожидаем, и делать такие вещи в фронтенде означает, что мы не отловим каждый случай, который пользователи хотят, чтобы мы отлавливали.
Последовательности оптимизаций открывают возможности для новых оптимизаций
Если во фронтенде так сложно генерировать предупреждения, возможно, мы можем генерировать их из оптимизатора! Самая большая проблема с тем, чтобы генерировать полезные сообщения заключается в отслеживании данных. Оптимизатор компилятора включает в себя дюжины проходов оптимизации, каждый из которых изменяет код, делая его (как мы надеемся) быстрее. Если инлайнер решил инлайнить функцию, это может открыть новые возможности для того, чтобы удалить, например, выражения типа «X*2/2».
Хотя мы касаемся простых и ограниченных примеров для демонстрации таких оптимизаций, большая часть реальных случаев происходит в коде, который образовался при разворачивании макросов, инлайна функций и других действий по удалению высокоуровневых абстракций, которые предпринимает компилятор. Реальность такова, что люди обычно не пишут совсем глупых вещей напрямую. Для предупреждений это означает, что для того, чтобы сослаться на пользовательский код, нужно в точности реконструировать, как компилятор получил промежуточный код. Нам понадобилась бы возможность сказать что-то такое:
предупреждение: после трёх уровней инлайна функций (возможно, находящихся в разных файлах при Link Time Optimization), удалении общих подвыражений, после выноса их из цикла и доказательства того, что эти 13 указателей не являются алиасами, мы обнаружили место, где вы делаете нечто неопределённое. Это может быть из-за бага в вашем коде, или из-за макроса, ли из-за инлайна, и неверный код фактически недоступен, но мы не можем доказать, что он мётрв.
К сожалению, у нас нет инфраструктуры для отслеживания этого, и даже если бы была, у компилятора нет интерфейса пользователя, достаточно хорошего, чтобы сообщить всё это программисту.
В целом, UB ценно для оптимизатора тем, что оно говорит: «операция неверна — можно предположить, что она никогда не произойдёт». В случае с "*P" это даёт оптимизатору повод полагать, что P не раен NULL. В случае "*NULL" (например, после подстановки констант и инлайна), это позволяет оптимизатору считать, что такой код недостижим. Важное допущение состоит в том, что, так как нельзя решить проблему останова, компилятор не может знать, что код на самом деле мёртв (как должно быть по стандарту С) или это баг, появившийся в результате (возможно, длинной) серии оптимизаций. Так как нет в общем виде хорошего способа различить эти две вещи, почти все эти предупреждения будут ложно-положительным шумом.
Подход Clang-а к UB
Принимая во внимание столь печальное положение дел с UB, вы можете спросить, что Clang и LLVM делают для исправления ситуации. Я уже упоминал пару вещей: Clang Static Analyzer, Klee и флаг -fcatch-undefined-behavior являются полезными инструментами для отслеживания некоторых классов таких багов. Проблема в том, что они не так широко используются, как компилятор, и всё, что мы можем сделать прямо в компиляторе, будет гораздо большим благом, чем то, что делается отдельными инструментами. Помните, что компилятор ограничен и не имеет динамической информации, и также ограничен тем, что не может тратить слишком много времени при компиляции.
Первый шаг Clang-а для улучшения кода — это включение большего количества предупреждений по умолчанию по сравнению с другими компиляторами. Хотя некоторые разработчики дисциплинированы и компилируют с "-Wall -Wextra" (например), многие не знают про эти флаги или не затрудняют себя включить их. Включив больше предупреждений по умолчанию, мы отловим большее количество багов.
Второй шаг состоит в том, что Clang генерирует предупреждения для многих классов неопределённого поведения (включая разыменование нуля, сдвиги на слишком большую величину, и т.п.), что позволяет отлавливать распространённые ошибки в коде. Выше приведены разные
Третий шаг состоит в том, что оптимизатор LLVM имеет гораздо меньше свободы в отношении UB, чем мог бы. Хотя стандарт говорит, что любой экземпляр неопределённого поведения может иметь неограниченный эффект, не было бы дружественным поведением в отношении к разработчику извлекать из этого выгоду. Вместо этого, оптимизатор LLVM обрабатывает их несколькими различными способами (ссылки даны на правила LLVM IR, не С, к сожалению):
1. Некоторые случаи неопределённого поведения просто преобразуются в операции, вызывающие исключение. Например, Clang для этой функции С++:
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!Разница в том, что мы решаем потратить несколько циклов на предотвращение потенциально серьёзного бага переполнения целого числа, что может привести к переполнению буфера и уязвимости (оператор new сам по себе дорогостоящий, поэтому лишние команды практически незаметны). Разработчики GCC знают об этой уязвимости по меньшей мере с 2005 года, но не починили её к моменту написания этой статьи. (уязвимость устранена в GCC 4.8.1 и выше. прим. перев.)
Арифметические операциями над неопределёнными значениями могут порождать неопределённые значения вмести неопределённого поведения. Разница в том, что неопределённое значение не может отформатировать ваш жесткий диск, или привести к другим нежелательным эффектам. Положительный эффект происходит в тех случаях, когда арифметическое выражение приводит к одному и тому же результату при любом возможном варианте неопределённого значения. Например, оптимизатор полагает, что результат «undef & 1» имеет нули в старших битах, оставляя только младший бит неопределённым. Это означает, что ((undef & 1) >> 1) будет равно 0 в LLVM, и не будет неопределённым значением.
Арифметические выражения, которые динамически выполняют неопределённые операции (такие, как переполнение знакового целого) генерируют «логическую ловушку» (logical trap value), «отравляющую» любые вычисления, в которых она используется, но не разрушающую всю остальную программу. Это означает, что нисходящие логические операции от неопределённой операции могут быть затронуты, но не вся остальная программа. Это является причиной, по которой оптимизатор не удаляет код, который производит операции с неинициализированными переменными. Запись в null и вызов функции по указателю null превращаются в вызов __builtin_trap() (который, в свою очередь, превращается в вызов инструкции «ud2» на x86). Это происходит всё время в оптимизированном коде (как результат других преобразований, таких, как инлайн функций и распространение констант). и мы удаляем блоки, содержащие такие команды, потому что они, очевидно, недостижимы.
Если (с точки зрения педантичного исполнения стандартов) они действительно недостижимы, в реальности мы понимаем, что люди иногда разыменовывают null-указатели, что заставляет выполнение кода падать в последующих функциях и делает очень сложным понимание проблемы. С точки зрения быстродействия, самый важный аспект здесь, это сжатие последующего кода. Поэтому clang превращает неопределённые операции в рантаймовый останов (runtime trap): если одна из них будет динамически достигнута, программа немедленно остановится и может быть отлажена. Недостатком здесь является небольшое раздувание кода за счёт этих операций и условий, управляющих их предикатами.
Оптимизатор предпринимает некоторые усилия, чтобы «сделать это правильно» в тех случаях, когда очевидно, что имел в виду программист (например, в коде "*(int*)P", где P указывает на float). Это помогает во многих случаях, но на самом деле вы не должны на это полагаться, и есть множество примеров, о которых вы можете думать, что они «очевидные», но они не являются такими после длинной серии преобразований, применённых к вашему коду.
Оптимизации, которые не попадают ни под одну из этих категорий, такие, как в примерах zero_array и set/call из части 1, оптимизируются так, как описано, «тихо», без сообщений пользователю. Мы делаем так, потому что нет ничего полезного, что можно сообщить, и очень необычно для (забагованного) кода реального приложения, если эти оптимизации его сломают.
Одна из главных областей улучшений, которые мы можеи делать, происходит за счёт таких «ловушек». Я думаю, было бы интересно добавить (выключенный по умолчанию) флаг предупреждения, который заставит оптимизатор делать предупреждения, когда он вставляет ловушки. Это даст очень много «шума» для некоторых исходников, но будет полезно для других. Первый ограничивающий фактор здесь состоит в том, что работа инфраструктуры заставит оптимизатор выдавать предупреждения: они не будут иметь полезных локаций в исходном коде, если отладочная информация отключена (но это можно исправить).
Другой, более значимый ограничивающий фактор состоит в том, что эти предупреждения не будут иметь никакой информации для отслеживания, которая помогла бы объяснить, что данная операция появилась в результате разворачивания цикла три раза и инлайна четырёх уровней вызова функции. Лучшее, что мы сможем сделать, это указать файл/строку/столбец, что будет полезно в большинстве тривиальных случаев, но будет очень сильно запутывать в других случаях. В любом случае, реализация этого для нас не является приоритетной потому что: а) это вряд ли даст хороший опыт б) мы не будем делать эту функцию включенной по умолчанию и в) для её реализации потребуется много работы.
Использование безопасного диалекта C (и других опций)
Последняя опция, которая у вас есть, если вам не нужно максимальное быстродействие, это использование различных флагов компилятора для того, чтобы использовать диалект C, который устраняет неопределённое поведение. Например, использование флага -fwrapv устраняет неопределённое поведение, возникающее из-за переполнения знаковых чисел (однако, отметим, что это не устраняет возможные уязвимости и дыры в безопасности, связанные с переполнением знаковых чисел). Флаг -fno-strict-aliasing отключает Type Based Alias Analysis, и вы можете игнорировать эти правила для типов. Если потребуется, мы можем добавить флаг к Clang, который по умолчанию будет обнулять все локальные переменные, флаг, вставляющий операцию «and» перед каждым сдвигом с переменной величиной сдвига и т.п. К сожалению, не существует способа полностью избавиться от неопределённого поведения в С, не сломав ABI и полностью убив быстродействие. Другая проблема состоит в том, что вы больше не будете писать на С, вы будете писать на похожем, но не совместимом с С диалекте.
Если написание кода на непереносимом диалекте С — не ваше, то флаги -ftrapv и -fcatch-undefined-behavior (наряду с другими вещами, которые упоминались ранее) может быть полезным оружием в вашем арсенале для отслеживания такого рода багов. Включение их в дебажной сборке может быть хорошим способом для раннего обнаружения багов. Эти флаги также могут быть полезны в продакшене, если вы собираете приложение, критическое в плане безопасности. Хотя нет гарантий, что вы найдёте все баги, они находят полезное подмножество багов.
В основном, реальная проблема в том, что С не является безопасным языком и (несмотря на его успешность и популярность) многие люди не понимают, как язык на самом деле работает. Десятилетия развития предшествовали его стандартизации в 1989 году, и С превратился из «низкоуровневого системного языка программирования, представляющего собой тонкий слой над ассемблером PDP» в «низкоуровневый системный язык программирования, пытающийся достичь высокого быстродействия, ломая ожидания людей». С одной стороны, все «трюки» С почти всегда работают, и код в целом более производительный из-за этого (и в некоторых случаях, гораздо более). С другой стороны, места читерских трюков часто очень удивляют людей и обычно проявляются в самый неподходящий момент.
С — это гораздо больше, чем переносимый ассемблер, иногда он способен очень сильно удивлять. Я надеюсь, что это обсуждение пояснило некоторые вопросы, касающиеся неопределённого поведения с С, по меньшей мере с точки зрения компилятора.
Автор: 32bit_me
