По следам 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 и выравнивания.

Так что с большими оговорками (на x86) можно написать так:

float invert(float f) { 
    char* const raw = reinterpret_cast<char*>(&f) + sizeof(float) - 1;
    *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 в более доступной для студентов форме. Сама лекция будет на следующей неделе. Если кто желает поприсутствовать — милости просим. Событие также будет стримиться в онлайн.