По следам C++ Siberia: дракон в мешке
Конференции бывают разные. Некоторые собирают огромные толпы зрителей, другие могут быть интересны лишь полутора специалистам.
Забавно другое: часто бывает, что зал собирает большое количество слушателей, которым любопытна тема, они задают вопросы и впоследствии с энтузиазмом рассказывают о пережитом коллегам. В то же время, запись оного мероприятия собирает несоизмеримо меньше просмотров, чем котики на ютубе. Предполагаю, что видео банально теряются на просторах видеохостингов и не могут найти зрителей. Сей досадный факт обязательно надо исправлять!
На самом деле, пост не о том.
Так уж вышло, что мне довелось выступать на означенной конференции, где я на пальцах и с приплясываниями рассказывал, что такое LLVM, чем интересна нотация SSA, что такое IR код и, наконец, как так получается, что детерменированные на первый взгляд C++ программы, оказывается, провоцируют неопределенное поведение.
Кстати, этот доклад можно поставить пятым номером в серии статей про виртуальную машину Smalltalk. Многие просили подробнее рассказать о LLVM. В общем, убиваем всех зайцев сразу. Заинтересовавшимся, предлагаю «откинуться на спинку кресла», опционально налить чего-нибудь интересного и послушать. Обещаю, что больше часа времени я не отниму.
Ах да, под катом можно найти пояснения тех моментов, которым не было уделено должное внимание на конференции. Я постарался ответить на часто задаваемые вопросы и детально разобрать листинги LLVM IR. В принципе, текстовую часть статьи можно читать как самостоятельное произведение, тем не мене я рассчитывал на то, что читатель обратится к нему уже после просмотра видео.
Проблема с нарушением strict aliasing
В докладе я упомянул ситуацию с преобразованием указателей на разные типы, которое может нарушить правило strict aliasing. К сожалению, проблему я назвал, а вот решение нет.
Итак, код:
float invert(float f) {
uint32_t* raw = reinterpret_cast<uint32_t*>(&f);
*raw ^= (1 << 31); // инвертируем знак
return * reinterpret_cast<float*>(raw);
}
Как было сказано, проблема заключается в небезопасном преобразовании указателя на float в указатель на uint32_t. Если при компиляции была указана опция -no-strict-aliasing то код будет работать именно так как задумано, а вот если нет… Как же решить задачу без стрельбы по конечностям?
Решений этой проблемы три — два корректных и одно условно-безопасное.
Корректное решение номер один — копирование
Копирование регионов памяти — гарантированно безопасная операция. В этом случае компилятор не будет пытаться делать предположений относительно природы указателей и возможности их пересечения в памяти:
float invert(float f) {
uint32_t raw = 0;
memcpy(&raw, &f, sizeof(float));
raw ^= (1 << 31); // инвертируем знак
memcpy(&f, &raw, sizeof(float));
return f;
}
Что интересно: компилятор обязательно заметит, что копируемые регионы всегда заданы однозначно и с фиксированным размером, а потому сможет заменить вызов к системной функции memcpy() на регистровые операции, если оба значения будут у него «на руках» (а так, скорее всего и будет). Таким образом, никакого оверхеда на использование вызова функции здесь нет.
Корректное решение номер два — использование char*
Тип char и указатели на него трактуются компилятором особенным образом. Во-первых, стандарт требует, чтобы тип char всегда занимал ровно 1 байт памяти. В отличие от числовых типов, размер char задается строго.
Во-вторых, компилятор позволяет указателю char* хранить адреса произвольных участков памяти, то есть указывать на объекты разных типов. По стандарту, char* считается совместимым («aliases everything») со всеми другими указателями в терминах strict aliasing.
Работа с памятью через char* безопасна при условии соблюдения endianness и выравнивания. Так что с большими оговорками можно написать так:
float invert(float f) {
char* const raw = reinterpret_cast<char*>(&f) + sizeof(float);
*raw ^= 0x80; // инвертируем знак
return * reinterpret_cast<float*>(raw);
}
Разумеется, реальный код должен учитывать порядок байт на платформе и выбирать нужный байт для операции.
Условно-безопасное решение — использование union
Мы подходим к самой противоречивой части, которая всегда вызывала много споров.
Для начала приведу код:
float invert(float f) {
union {
uint32_t as_int;
float as_float;
};
as_float = f; // загружаем значение
as_int ^= (1 << 31); // инвертируем знак
return as_float; // возвращаем значение
}
Так вот, стандарт говорит, что так делать нельзя. По стандарту, union можно использовать только для экономии и переиспользования памяти под разные типы данных. Стандарт считает, что читаться всегда должно только то значение, которое было записано ранее. Запись одного типа с последующим чтением другого — undefined behavior.
В природе существует огромное количество кода, который нарушает это правило. Если бы компиляторы следовали букве закона, то все было бы совсем плохо. К счастью, а может быть к сожалению, все известные мне компиляторы закрывают глаза на такую шалость. Соответственно, код будет работать. Но решение это плохое, потому что основано на слепой вере в то, что все будет хорошо и «у меня точно работает».
Такие вот пироги с котятами…
Разбор полетов с IR кодом
Во второй части статьи я приведу подробный разбор IR кода для рассмотренного в докладе алгоритма подсчета суммы массива.
Для начала сам листинг в том виде, в котором он был представлен на слайде 21:
1 ; Function Attrs: nounwind readonly
2 define i32 @sum_array(int*, int)(i32* nocapture readonly %input, i32 %length) #0 {
3 %1 = icmp sgt i32 %length, 0 ; а есть вообще что суммировать?
4 br i1 %1, label %.lr.ph, label %._crit_edge
5 ._crit_edge:
6 %sum.0.lcssa = phi i32 [ 0, %0 ], [ %4, %.lr.ph ]
7 ret i32 %sum.0.lcssa ; возврат результата
8 .lr.ph:
9 %i.02 = phi i32 [ %5, %.lr.ph ], [ 0, %0 ]
10 %sum.01 = phi i32 [ %4, %.lr.ph ], [ 0, %0 ]
11 ; вычисление адреса текущего элемента в массиве и его загрузка в регистр
12 %2 = getelementptr inbounds i32, i32* %input, i32 %i.02
13 %3 = load i32, i32* %2, align 4
14 ; аккумулирование суммы и инкремент индекса
15 %4 = add nsw i32 %3, %sum.01 ; новое значение sum
16 %5 = add nuw nsw i32 %i.02, 1 ; новое значение i
17 ; условие выхода
18 %exitcond = icmp eq i32 %5, %length
19 ; проверка условия выхода и переход
20 br i1 %exitcond, label %._crit_edge, label %.lr.ph
21 }
Итак, листинг начинается с объявления функции с именем "sum_array(int*, int)", которая принимает два параметра с типами i32* и i32 и возвращает i32. Да, все что записано в кавычках и есть имя. LLVM не накладывает ограничений на именование идентификаторов. Единственное требование — уникальность строки. Поэтому clang для простоты восприятия помещает в имя весь прототип функции.
Как и в C-подобных языках в объявлении функции сначала идет тип возвращаемого значения, потом собственно имя, а потом параметры. Вторая пара круглых скобок — это раздел описания параметров функции. Про типы мы уже сказали, осталось разобраться с ключевыми словами.
Ключевое слово nocapture говорит LLVM, что функция не сохраняет переданный указатель и не записывает его во внешнюю память. Эта информация может быть использована анализатором для определения того факта, что указатель не «утекает». Характерным применением является escape analysis и оптимизация, которая превращает аллокацию в куче в аллокацию на стеке, если оптимизатор может доказать, что указатель не покидает контекста исполнения. Результат — минус одно выделение памяти на каждое обращение.
Ключевое слово readonly имеет ту же семантику, что и спецификатор const при объявлении указателя на константу в C++. Таким образом гарантируется, что функция не изменяет содержимое памяти по такому указателю.
Строки 3 и 4 это быстрая отсечка, если в параметр %length был передан 0, строки 6 и 7 — точка выхода из функции.
3 %1 = icmp sgt i32 %length, 0 ; сравни значение %length с нулем
4 br i1 %1, label %.lr.ph, label %._crit_edge ; если результат истина, перейди к метке %.lr.ph, иначе к %._crit_edge
5 ._crit_edge:
; значение суммы будет 0, если мы пришли из базового блока %0 или %4, если пришли из %.lr.ph (см. ниже)
6 %sum.0.lcssa = phi i32 [ 0, %0 ], [ %4, %.lr.ph ]
; возврат %sum.0.lcssa в качестве результата функции
7 ret i32 %sum.0.lcssa
Далее следует основное тело функции — собственно алгоритм подсчета суммы элементов массива:
8 .lr.ph:
9 %i.02 = phi i32 [ %5, %.lr.ph ], [ 0, %0 ] ; значение индекса — или 0, или значение инкремента с предыдущей итерации (%5)
10 %sum.01 = phi i32 [ %4, %.lr.ph ], [ 0, %0 ] ; значение суммы — или 0, или сумма с прошлой итерации (%4)
11 ; вычисление адреса элемента в массиве %input по индексу %i.02
12 %2 = getelementptr inbounds i32, i32* %input, i32 %i.02
13 %3 = load i32, i32* %2, align 4
14 ; аккумулирование суммы и инкремент индекса
15 %4 = add nsw i32 %3, %sum.01 ; новое значение суммы — прибавить значение элемента массива (%3) к сумме (%sum.01)
16 %5 = add nuw nsw i32 %i.02, 1 ; новое значение индекса — прибавить 1 к текущему значению индекса %i.02
17 ; условие выхода — если значение индекса после инкремента сравнялось с %length
18 %exitcond = icmp eq i32 %5, %length
19 ; если условие выхода истинно — переходим к метке %._crit_edge, иначе крутим дальше %.lr.ph
20 br i1 %exitcond, label %._crit_edge, label %.lr.ph
Думаю, тут все должно быть понятно из комментариев в самом листинге. Тем не менее, сто́ит отметить пару моментов.
Во-первых, начинающих LLVM программистов часто смущает «магическая» инструкция getelementpointer (GEP). На самом деле, все что она делает, это рассчитывает смещение поля в типе данных с учетом базового адреса объекта и серии индексов — путей к элементам. В случае массива у нас есть только одно измерение — линейная последовательность элементов. Соответственно, смещение элемента по индексу вычисляется тривиально. В случае сложной структуры со вложенными элементами, необходимо задать индекс поля на каждом уровне вложенности.
За подробностями предлагаю обратиться к руководству LLVM по этой инструкции и специальной статье, призванной разрешить недопонимание.
Во-вторых, стоит обратить внимание на спецификаторы nsw и nuw у инструкций add на 15 и 16 строке.
Буквально, они говорят LLVM о том, что результат выполнения не предполагает знакового (no signed wrap) и беззнакового (no unsigned wrap) переполнений. Они позволяют ускорить код ценой неопределенного поведения, если предположение окажется ложным.
С этими понятиями и с UB тесно связано понятие value poisoning, про которое тоже обязательно надо почитать.
Заключение
Напоследок, хочу от всей души поблагодарить Сергея Платонова — sermp. Без него это событие не состоялось бы. Особенно если учесть, чего ему это стоило. Спасибо, Серега!
С моей точки зрения, C++ Siberia — это одна из лучших конференций по C++ в Сибири. Уровень докладов очень высокий, практически все интересно послушать.
Мне особенно понравились доклады:
- Разумеется, доклад Эрика Ниблера, который позволяет по новому взглянуть на C++
- Отличное введение в грядущие концепты дал Александр Фокин
- Александр Гранин в очередной раз взорвал всем мозг функциональщиной! Линзы в C++, каково вам, а?
- Интересное решение проблемы ODR предложил Алексей Кутумов (кстати, тоже пересекается с clang/LLVM!)
- Наконец, Евгений Рыжков из всем здесь известной команды PVS Studio рассказал о применении статического анализа на примере Unreal Engine. Рассказ должен быть интересен в первую очередь руководителям проектов, поскольку затрагивает в основном вопросы менеджмента. Но и программистам его послушать очень и очень рекомендую.
…Вот собственно и все. Надеюсь, что вам понравилось выступление и вы узнали что-то новое для себя. Если нет, всегда полезно повторить и проверить себя. До встречи!
P.S.: Было бы здорово, если бы авторы вышеозначенных докладов написали свои статьи с дополнениями. Оно того определенно стоит.
P.P.S.: Ребята из Новосибирского государственного университета (НГУ) попросили рассказать про LLVM в более доступной для студентов форме. Сама лекция будет на следующей неделе. Если кто желает поприсутствовать — милости просим. Событие также будет стримиться в онлайн.
