Как undefined - __builtin_ctz (0) или __builtin_clz (0)?

Фон

В течение долгого времени gcc предоставлял ряд встроенных функций бит-скругления, в частности число конечных и ведущих 0-бит (также для long unsigned и long long unsigned, которые имеют суффиксы l и ll):

- Встроенная функция: int __builtin_clz (unsigned int x)

Возвращает число ведущих 0-бит в x, начиная с самого значащего бита должность. Если x равно 0, результат: undefined.

- Встроенная функция: int __builtin_ctz (unsigned int x)

Возвращает количество конечных 0-бит в x, начиная с младшего значащего бита должность. Если x равно 0, результат: undefined.

В каждом онлайн-компиляторе (отказ от ответственности: только x64) я тестировал, однако, результатом было то, что как clz(0), так и ctz(0) возвращают количество бит базового встроенного типа, например

#include <iostream>
#include <limits>

int main()
{
    // prints 32 32 32 on most systems
    std::cout << std::numeric_limits<unsigned>::digits << " " << __builtin_ctz(0) << " " << __builtin_clz(0);    
}

Живой пример.

Попытка обходного пути

Последний соединительный элемент Clang SVN в режиме std=c++1y сделал все эти функции расслабленными С++ 14 constexpr, что делает их кандидатами для использования в выражении SFINAE для шаблона функции обертки вокруг 3 ctz/clz встроенные значения для unsigned, unsigned long и unsigned long long

template<class T> // wrapper class specialized for u, ul, ull (not shown)
constexpr int ctznz(T x) { return wrapper_class_around_builtin_ctz<T>()(x); }

// overload for platforms where ctznz returns size of underlying type
template<class T>
constexpr auto ctz(T x) 
-> typename std::enable_if<ctznz(0) == std::numeric_limits<T>::digits, int>::type
{ return ctznz(x); }

// overload for platforms where ctznz does something else
template<class T>
constexpr auto ctz(T x) 
-> typename std::enable_if<ctznz(0) != std::numeric_limits<T>::digits, int>::type
{ return x ? ctznz(x) : std::numeric_limits<T>::digits; }

Выгода от этого взлома заключается в том, что платформы, которые дают требуемый результат для ctz(0), могут опустить дополнительное условие для тестирования для x==0 (что может показаться микро-оптимизацией, но когда вы уже достигли уровня встроенные функции бит-twiddling, это может иметь большое значение)

Вопросы

Как undefined - это семейство встроенных функций clz(0) и ctz(0)?

могут ли они исключить std::invalid_argument?
для x64, будут ли они для текущего gcc-дистрибутива возвращать размер типа underyling?
Существуют ли разные платформы ARM/x86 (у меня нет доступа к ним для тестирования)
- это вышеописанный SFINAE трюк, четко определенный способ разделения таких платформ?

Ответ 1

К сожалению, даже реализация x86-64 может отличаться - от Intel ссылка набора инструкций, BSF и BSR, с исходным операндом значение (0), оставляет пункт назначения undefined и устанавливает ZF (флаг нуля). Таким образом, поведение может быть несовместимым между микро-архитектурой или, скажем, AMD и Intel. (Я считаю, что AMD оставляет цель немодифицированной.)

Более новые инструкции LZCNT и TZCNT не являются вездесущими. Оба они присутствуют только в архитектуре Haswell (для Intel).

Ответ 2

Причина, по которой значение undefined заключается в том, что он позволяет компилятору использовать инструкции процессора, для которых результат undefined, когда эти инструкции являются самым быстрым способом получить ответ.

Но важно понимать, что не только результаты undefined; они недетерминированы. Это верно, учитывая справочную инструкцию Intel, для команды, например, вернуть низкие 7 бит текущего времени.

И здесь, где это становится интересным/опасным: автор компилятора может воспользоваться этой ситуацией, создать меньший код. Рассмотрите эту версию нестандартной спецификации вашего кода:

using std::numeric_limits;
template<class T>
constexpr auto ctz(T x) {
  return ctznz(0) == numeric_limits<T>::digits || x != 0
       ? ctznz(x) : numeric_limits<T>::digits;
}

Это хорошо работает на процессоре/компиляторе, который решил вернуть # бит для ctznz (0). Но не процессор/компилятор, который решает вернуть псевдослучайные значения, компилятор может решить: "Мне разрешено возвращать все, что я хочу, для ctznz (0), Затем код заканчивается вызовом ctznz все время, даже если он вызывает неправильный ответ.

Другими словами: результаты компилятора undefined не гарантируются как undefined таким же образом, как и результаты текущей программы undefined.

На самом деле это не так. Если вы должны использовать __builtin_clz, с исходным операндом, который может быть равен нулю, вы должны постоянно добавлять проверку.