По следам C++ Siberia: дракон в мешке
Конференции бывают разные. Некоторые собирают огромные толпы зрителей, другие могут быть интересны лишь полутора специалистам.
Забавно другое: часто бывает, что зал собирает большое количество слушателей, которым любопытна тема, они задают вопросы и впоследствии с энтузиазмом рассказывают о пережитом коллегам. В то же время, запись оного мероприятия собирает несоизмеримо меньше просмотров, чем котики на ютубе. Предполагаю, что видео банально теряются на просторах видеохостингов и не могут найти зрителей. Сей досадный факт обязательно надо исправлять!
На самом деле, пост не о том.
Так уж вышло, что мне довелось выступать на означенной конференции, где я на пальцах и с приплясываниями рассказывал, что такое LLVM, чем интересна нотация SSA, что такое IR код и, наконец, как так получается, что детерменированные на первый взгляд C++ программы, оказывается, провоцируют неопределенное поведение.
Кстати, этот доклад можно поставить пятым номером в серии статей про виртуальную машину Smalltalk. Многие просили подробнее рассказать о LLVM. В общем, убиваем всех зайцев сразу. Заинтересовавшимся, предлагаю «откинуться на спинку кресла», опционально налить чего-нибудь интересного и послушать. Обещаю, что больше часа времени я не отниму.
Ах да, под катом можно найти пояснения тех моментов, которым не было уделено должное внимание на конференции. Я постарался ответить на часто задаваемые вопросы и детально разобрать листинги LLVM IR. В принципе, текстовую часть статьи можно читать как самостоятельное произведение, тем не мене я рассчитывал на то, что читатель обратится к нему уже после просмотра видео.
Проблема с нарушением strict aliasingВ докладе я упомянул ситуацию с преобразованием указателей на разные типы, которое может нарушить правило strict aliasing. К сожалению, проблему я назвал, а вот решение нет.
Как было сказано, проблема заключается в небезопасном преобразовании указателя на float в указатель на uint32_t . Если при компиляции была указана опция -no-strict-aliasing то код будет работать именно так как задумано, а вот если нет… Как же решить задачу без стрельбы по конечностям?
Решений этой проблемы три — два корректных и одно условно-безопасное.
Корректное решение номер один — копированиеКопирование регионов памяти — гарантированно безопасная операция. В этом случае компилятор не будет пытаться делать предположений относительно природы указателей и возможности их пересечения в памяти:
Что интересно: компилятор обязательно заметит, что копируемые регионы всегда заданы однозначно и с фиксированным размером, а потому сможет заменить вызов к системной функции memcpy() на регистровые операции, если оба значения будут у него «на руках» (а так, скорее всего и будет). Таким образом, никакого оверхеда на использование вызова функции здесь нет.
Корректное решение номер два — использование char*Тип char и указатели на него трактуются компилятором особенным образом. Во-первых, стандарт требует, чтобы тип char всегда занимал ровно 1 байт памяти. В отличие от числовых типов, размер char задается строго.
Во-вторых, компилятор позволяет указателю char* хранить адреса произвольных участков памяти, то есть указывать на объекты разных типов. По стандарту, char* считается совместимым («aliases everything») со всеми другими указателями в терминах strict aliasing. Работа с памятью через char* безопасна при условии соблюдения endianness и выравнивания.
Так что с большими оговорками (на x86) можно написать так:
Разумеется, реальный код должен учитывать порядок байт на платформе и выбирать нужный байт для операции.
Условно-безопасное решение — использование unionМы подходим к самой противоречивой части, которая всегда вызывала много споров.
Для начала приведу код:
Так вот, стандарт говорит, что так делать нельзя. По стандарту, union можно использовать только для экономии и переиспользования памяти под разные типы данных. Стандарт считает, что читаться всегда должно только то значение, которое было записано ранее. Запись одного типа с последующим чтением другого — undefined behavior.
В природе существует огромное количество кода, который нарушает это правило. Если бы компиляторы следовали букве закона, то все было бы совсем плохо. К счастью, а может быть к сожалению, все известные мне компиляторы закрывают глаза на такую шалость. Соответственно, код будет работать. Но решение это плохое, потому что основано на слепой вере в то, что все будет хорошо и «у меня точно работает».
Такие вот пироги с котятами…
Разбор полетов с IR кодомВо второй части статьи я приведу подробный разбор IR кода для рассмотренного в докладе алгоритма подсчета суммы массива.
Для начала сам листинг в том виде, в котором он был представлен на слайде 21:
Итак, листинг начинается с объявления функции с именем " sum_array(int*, int) ", которая принимает два параметра с типами i32* и i32 и возвращает i32 . Да, все что записано в кавычках и есть имя. LLVM не накладывает ограничений на именование идентификаторов. Единственное требование — уникальность строки. Поэтому clang для простоты восприятия помещает в имя весь прототип функции.
Как и в C-подобных языках в объявлении функции сначала идет тип возвращаемого значения, потом собственно имя, а потом параметры. Вторая пара круглых скобок — это раздел описания параметров функции. Про типы мы уже сказали, осталось разобраться с ключевыми словами.
Ключевое слово nocapture говорит LLVM, что функция не сохраняет переданный указатель и не записывает его во внешнюю память. Эта информация может быть использована анализатором для определения того факта, что указатель не «утекает». Характерным применением является escape analysis и оптимизация, которая превращает аллокацию в куче в аллокацию на стеке, если оптимизатор может доказать, что указатель не покидает контекста исполнения. Результат — минус одно выделение памяти на каждое обращение.
Ключевое слово readonly имеет ту же семантику, что и спецификатор const при объявлении указателя на константу в C++. Таким образом гарантируется, что функция не изменяет содержимое памяти по такому указателю.
Строки 3 и 4 это быстрая отсечка, если в параметр %length был передан 0, строки 6 и 7 — точка выхода из функции.
Далее следует основное тело функции — собственно алгоритм подсчета суммы элементов массива:
Думаю, тут все должно быть понятно из комментариев в самом листинге. Тем не менее, сто́ит отметить пару моментов.
Во-первых, начинающих LLVM программистов часто смущает «магическая» инструкция getelementpointer (GEP). На самом деле, все что она делает, это рассчитывает смещение поля в типе данных с учетом базового адреса объекта и серии индексов — путей к элементам. В случае массива у нас есть только одно измерение — линейная последовательность элементов. Соответственно, смещение элемента по индексу вычисляется тривиально. В случае сложной структуры со вложенными элементами, необходимо задать индекс поля на каждом уровне вложенности.
За подробностями предлагаю обратиться к руководству LLVM по этой инструкции и специальной статье, призванной разрешить недопонимание.
Во-вторых, стоит обратить внимание на спецификаторы nsw и nuw у инструкций add на 15 и 16 строке.
Буквально, они говорят LLVM о том, что результат выполнения не предполагает знакового (no signed wrap) и беззнакового (no unsigned wrap) переполнений. Они позволяют ускорить код ценой неопределенного поведения, если предположение окажется ложным.
С этими понятиями и с UB тесно связано понятие value poisoning, про которое тоже обязательно надо почитать.
ЗаключениеНапоследок, хочу от всей души поблагодарить Сергея Платонова — sermp. Без него это событие не состоялось бы. Особенно если учесть, чего ему это стоило. Спасибо, Серега!
С моей точки зрения, C++ Siberia — это одна из лучших конференций по C++ в Сибири. Уровень докладов очень высокий, практически все интересно послушать.