27

バックグラウンド

長い間、gcc は多くの組み込みのビット操作関数、特に末尾と先頭の 0 ビットの数を提供してきました (接尾辞andを持つlong unsignedandについても同様です)。long long unsignedlll

— 組み込み関数:int __builtin_clz (unsigned int x)

x最上位ビット位置から始まる、先頭の 0 ビットの数を返します。が 0 の場合x、結果は未定義です。

— 組み込み関数:int __builtin_ctz (unsigned int x)

x最下位ビット位置から開始して、の末尾の 0 ビットの数を返します。が 0 の場合x、結果は未定義です。

ただし、テストしたすべてのオンライン (免責事項: 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これらすべての関数を緩和した C++14にしました。これにより、 、、およびの 3 /組み込みconstexprのラッパー関数テンプレートの SFINAE 式で使用する候補になります。ctzclzunsignedunsigned longunsigned 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(これは、マイクロ最適化のように見えるかもしれませんが、組み込みのビット操作関数のレベルまで既に下がっている場合は、大きな違い）

質問

組み込み関数clz(0)とのファミリはどの程度未定義ctz(0)ですか?

  • std::invalid_argument彼らは例外をスローできますか？
  • x64 の場合、現在の gcc ディストリビューションの場合、基になる型のサイズが返されますか?
  • ARM/x86 プラットフォームは違いますか (それらをテストするためにアクセスできません)。
  • 上記の SFINAE トリックは、そのようなプラットフォームを分離する明確な方法ですか?
4

2 に答える 2

18

値が定義されていない理由は、結果が定義されていないプロセッサー命令をコンパイラーが使用できるようにするためです。

ただし、結果が定義されていないだけではないことを理解することが重要です。それらは非決定論的です。たとえば、インテルの命令リファレンスを考えると、命令が現在の時刻の下位 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) に対して #bits を返すことを決定したプロセッサ/コンパイラでうまく機能します。しかし、疑似乱数値を返すことを決定したプロセッサー/コンパイラーでは、コンパイラーは「ctnznz(0) に必要なものを返すことが許可されており、#bits を返すとコードが小さくなるため、そうします」と判断する場合があります。 . その後、コードは間違った応答を生成するにもかかわらず、常に ctznz を呼び出すことになります。

別の言い方をすれば、コンパイラの未定義の結果は、実行中のプログラムの未定義の結果と同じように未定義であるとは限りません。

これを回避する方法は本当にありません。ソースオペランドがゼロの可能性がある __builtin_clz を使用する必要がある場合は、常にチェックを追加する必要があります。

于 2014-11-07T20:01:17.843 に答える
15

残念ながら、x86-64 の実装でさえ異なる場合があります。Intel の命令セットリファレンスとは異なります。そのため、マイクロアーキテクチャ間、または AMD と Intel の間で動作が一貫していない可能性があります。(AMD は宛先を変更せずに残していると思います。)BSFBSR(0)ZF

新しいものLZCNTとTZCNT指示はどこにでもあるわけではありません。どちらも Haswell アーキテクチャ (Intel 用) の時点でのみ存在します。

于 2013-10-22T21:43:56.237 に答える