Count Leading Zerosその他ビルトイン関数の実装

2025-09-01
#compiler

コンパイラの主要なトピックでは全然ないけど、余興として自作Cコンパイラにビルトイン関数としてclzとctzとpopcountを実装した顛末。

__builtin_clzなどの説明

__builtin_clzという、上位ビットから0が何個連続しているかを得るコンパイラのビルトイン関数が用意されている。 これを使うと最上位ビットの位置がわかり、例えば２のべき乗のシフト数を得ることができる。

他にも関係するビルトイン関数として、

  • __builtin_ctz: 下位ビットからの0の個数 (Count Trailing Zeros)
  • __builtin_popcount: ビットが1の個数 (Population Count)

などのビルトイン関数がある。 なぜ標準のライブラリ関数ではなくてビルトイン関数なのかというのは謎だが、プロセッサによっては専用の命令が用意されていて１命令で実行できるため関数呼び出しのコストを削るためなのかもしれない。

これらをどういう用途に使うのか、各プロセッサの専用命令として実装されるほど速度的に必須なのかは把握してないが、パリティを取ったりいろいろ用途があるんでしょう。

実装方法

自作のCコンパイラにビルトイン関数自体は以前から実装していて、allocaなどのコンパイル時の情報も利用する必要がある要素に使用していた。 構文としては普通の関数呼び出しと同じで、関数が規定の識別子の場合にはそれぞれに対応するコード生成を行うという仕組みとして実装していた。

ただ今まではコンパイル時に対応できるものだけで、__builtin_clzなどのように実行時に特別な命令が必要なビルトイン関数は作ったことがなかった。 コード生成では中間表現(Intermediate Representation, IR)を生成するが、IRは普通のC言語で使う範囲の一般的な命令セットしか用意してないので、プロセッサごとの専門の命令には対応してない。

なのでどう実装するか、IRの命令に特殊処理を追加するかとも考えたが、インラインアセンブラで対応することにした。

インラインアセンブラ

インラインアセンブラはC言語のソース中にアセンブリを埋め込める機能で、C言語では対応しきれない処理やプロセッサ依存のコードを書くことができる。 自作のCコンパイラで使用するライブラリでシステムコールを実装する必要があったため、簡易的なものは扱えるようにしていた。 これをclzなどを使えるようにするために、gccの書式に合わせて拡張する。

gccでのインラインアセンブラの書式は、 __asm("アセンブリコードテンプレート" : 出力変数指定 : 入力変数指定 : 破壊レジスタ指定) となっている。 細かくは、

  • 出力や入力に与えた変数はテンプレート中で%0などとして参照できて、C言語の変数とやりとりできる
  • 出力や入力はカンマ区切りで複数指定でき、出力"=r"(result)、入力"ri"(x)などといった形で指定

そうした上で、プロセッサごとの定義済みマクロに応じてインラインアセンブラのコードを切り替えてやる。

変数を必ずレジスタに配置するためのハック

テンプレートから%0などとC言語の値を参照する場合に、場合によっては問題になる。 変数を与えれば普通はプロセッサのレジスタが割り当てられるが、最適化の定数伝播で定数に置き換えられる可能性がある。 gccなどではその辺も対処しているのかもしれないが自作コンパイラでは単に置き換えるだけなので、レジスタの場合や即値の場合でアセンブリを変えないといけなかったりすると問題になる。

その変数には定数伝播を無効にするためにvolatileを使用することも考えたが、「volatileを指定した変数はsetjmp以降の変更が保持される」という仕様があるので、volatile変数はメモリ上に配置する必要があり、レジスタではなくなってしまうので無駄だし扱いが面倒になる。

まともに対処するのは難しいのでどうするか。 ハックとしてvolatile registerと指定した変数はレジスタに配置した上で、定数伝播は無効にする、という独自ルールにした。 そうすることで必ずレジスタとなり、意図するアセンブリに埋め込むことができるようになる。

CPUごとのclz, ctz実装方法

x86-64

  • clz: lzcnt命令
    • gccでコンパイルしたらbsr(Bit Scan Reverse)命令を使ったコードが生成されたがlzcntも使える模様、 bsrで得られる値は最上位ビットのビット位置なので、clz的にはビット幅-1から引く必要がある
  • ctz: tzcnt(Trailing Zero Count)命令
  • popcount: popcnt命令

aarch64

  • clz: clz命令
  • ctz: rbit命令でビット列を反転し、clzを使う
  • popcount: cnt.8b

cnt.8bはaarch64の汎用レジスタに対する命令ではなく、VFPというベクタ・浮動小数点演算命令のようで、汎用レジスタからコピーしたり戻したりする必要があるようだったので今回は未対応。

RISC-V64

  • clz, ctz, cpop命令

上記の命令はRISC-Vの通常の命令セットには含まれず、ビット操作拡張命令セット(ZBB)が必要になる。

zbb拡張の指定

自作コンパイラではなく既存のクロスコンパイラでのコンパイルを確認する際、これらの命令を使うようにするには-marchで指定する必要がある：

$ riscv64-unknown-elf-gcc -march=rv64gc_zbb clztest.c

指定しない場合にはclz命令を使わずに汎用的な処理で求めるライブラリ関数呼び出しにフォールバックされる。

zbbを指定した場合、出力されるELFオブジェクトファイルの.riscv.attributesセクションに拡張を表す指定（zbb1p0）が追加される。 この指定があることでobjdumpした時にビット拡張命令が逆アセンブルされる （自作アセンブラからの出力時にこの指定をつけない状態だと.insn xxxxとして、未対応命令のように逆アセンブルされる）。

RISC-Vのシミュレータspikeで実行する場合にも--isa=rv64gc_zbbと指定する必要がある （clzなどを使用したコードにISAを指定せず実行しようとするとイリーガル命令エラーが出る）。

WebAssembly

  • i32.clz, i32.ctz, i32.popcnt命令
  • i64もあり

リンク

関連記事

新着記事