GCC におけるスイッチ文の最適化（Lowering）戦略

2024 年 1 月 14 日

導入

コンパイラはスイッチ文を決定木として実装するが、それだけでは機能しない。GCC ではさらに高度な最適化手法が採用されている。 以下の議論は GCC を中心に行うが、ビットセット（bitset）の Lowering に限定しない限り、これらの最適化は Clang でも同等に適用可能である。

• 本稿では

  -O3

  最適化フラグを前提とする。
• 解説の簡略化のため、GCC のコードには若干の改変と特定の検証アサーションの削除を行った。

ジャンプテーブル（Jump Table）への最適化

コンパイラはスイッチ文をジャンプテーブルに変換するアプローチを採用するが、すべてのケースで有効なわけではない。

例 1：連続した値

2 つの整数

x

val

x

int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);

int compact(int x, int val) {
    switch (x) {
        case 0: return f0(val);
        case 1: return f1(val);
        case 2: return f2(val);
        case 3: return f3(val);
        case 4: return f4(val);
        default: return 0;
    }
}

アセンブリ出力: コンパイラはスイッチ文をジャンプテーブルに変換し、値が定数オフセットされている場合（例：97〜101）も同様に認識する。

compact:
	lea	eax, [rdi-97]  ; 定数オフセット計算
	cmp	eax, 4
	ja	.L2
	jmp	[QWORD PTR .L4[0+rax*8]]
.L4:
	.quad	.L8
	.quad	.L7
	; ... (ジャンプアドレスの配列)

例 2：疎な分布（閾値の確認）

直感では疎な分布はメリットが少ないはずだが、**GCC が考慮する閾値は「ケースラベルあたりのジャンプテーブルエントリが約 8 つ」**である。

以下の関数は、スパースであっても変換される。

int compact_7(int x, int val) {
    switch (x) {
        case 0: return f0(val);
        case 7: return f1(val);
        case 14: return f2(val);
        case 21: return f3(val);
        case 34: return f4(val);
        default: return 0;
    }
}

アセンブリ出力: 値の範囲内（0〜34）のエントリのみを有効にし、他は NOP または分岐として扱うジャンプテーブルが生成される。

例 3：比較の木（Tree of Comparisons）への展開

一方で、より疎な分布の場合は比較の木として展開される。

int sparse_8(int x, int val) {
    switch (x) {
        case 0: return f0(val);
        case 8: return f1(val);
        case 16: return f2(val);
        case 24: return f3(val);
        case 40: return f4(val);
        default: return 0;
    }
}

アセンブリ出力: この場合、比較命令の連鎖（Tree of Comparisons）が生成される。

sparse_8:
	mov	eax, edi
	cmp	eax, 16
	je	.L2
	jle	.L10
	cmp	eax, 24
	je	.L7
	; ... (木構造の比較命令)

いくつかの観察結果

• 間隔のみ確認: 未だに等間隔の値しか試していないが、コンパイラは高密度サブセットを識別できるのか。
• 重複したケース: 同じ結果を持つ複数のケースがある場合の処理は異なるか。
• 簡略化の欠如:

  sparse_8

  はジャンプ前に

  x

  を除算で簡略化する可能性があるが、GCC は見落としている。

特殊ケースによる振る舞いの変化

アウトライア（外れ値）

最初の例に外れ値を含めることで、コンパイラが高密度サブセットを認識できる。

int outlier(int x, int val) {
    switch (x) {
        case 1: return f0(val); // 密集
        case 2: return f1(val);
        case 3: return f2(val);
        case 4: return f3(val);
        case 5: return f4(val);
        case 100: return f5(val); // アウトライア
        default: return 0;
    }
}

振る舞い:

• ケース 1〜5: ジャンプテーブルを出力（高密度サブセットとして認識）。
• ケース 100: 単なる分岐（branch）を出力（孤立したケースとして処理）。

連続性（Contiguous）

複数のケースラベルが同じ関数を呼び出す場合、コンパイラは比較回数を最適化する。

int blocks_2(int x, int val) {
    switch (x) {
        case 0: case 1: case 2: case 3: return f1(val); // 4 つ連続
        case 21: ... case 24: return f2(val);            // 4 つ連続
        // ...
    }
}

解説:

• ケース数 vs 比較回数: ヒューリスティクスは「ジャンプテーブル変換が収益的」な判定基準として、単なる「ケースラベル数」ではなく**「必要な比較回数の合計」**を用いる。
• 例：4 つ連続するケースでも、最適化により比較回数が減るため、総比較回数が閾値（8）を下回る場合、ジャンプテーブルへの変換は見送られる。

不連続性（Non-contiguous）とビットセット

不連続でかつ等間隔なケースには、**ビットセット（Bitset）**が使用される。

int bittest(int x, int val) {
    switch (x) {
        case '0': case '2': case '4': ... // 奇数/偶数のパターンや特定の間隔
        default: return 0;
    }
}

アセンブリ出力: 通常のアプローチ（ジャンプテーブルや比較の木）が用いられない。

bittest:
	lea	eax, [rdi-48]      ; ASCII コードから '0' (48) を除算した値
	cmp	eax, 21
	ja	.L1
	mov	edx, 2753205        ; ビットマスク（例：...01010...）
	bt	rdx, rax             ; ビットテスト命令 (Bit Test)
	jc	.L7                  ; カリーフラグがセットなら真
.L1:	ret
.L7:	jmp	f1

解説:

• 2753205

  はケースラベルの ASCII 値に対応するビットパターン（48 を除いた結果）。
• Intel 命令

  bt

  : 指定したバイトのビットを読み取り、CF フラグに格納する。
• GCC はこれを「ビットセット」として最適化している。

実装：GCC のソースコード内での Lowering パス

スイッチ文を Lowering するのは

pass_lower_switch

analyze_switch_statement

1. ビットセット（Bitsets）

bit_test_cluster::find_bit_tests

• 動的プログラミング: すべてのクラスターをビットセットにバンドルする最適な分割（最小ビットセット数）を見つける。
• ヒューリスティクス (

  is_beneficial

  ):
  • 単一の出力エッジ（uniq=1）かつケース数が 3 以上の場合。
  • 2 つのエッジかつケース数が 5 以上の場合。
  • 3 つのエッジかつケース数が 6 以上の場合。
  • これらを満たさなければ、元の

    simple_cluster

    を保持する。

2. ジャンプテーブル（Jump tables）

jump_table_cluster::find_jump_tables

• 動的プログラミング: ジャンプテーブルへの変換可能な「収益的」なクラスターを特定。
• 比較回数の計算: 連続したケースラベルの場合は比較回数が 2、それ以外は 1 と計算される。
• 主要なヒューリスティクス (

  max_ratio

  ):
  • 速度最適化 (

    -O[123|fast]

    ): ジャンプテーブルエントリ / 比較回数 の比率が 8 を超えると変換を見送る。
  • サイズ最適化 (

    -Os

    ): 比率が 2 を超える場合、コスト増を許容する可能性がある（ただし閾値チェックも行う）。
  • 閾値 (

    case_values_threshold

    ): デフォルトでは 5（アーキテクチャ依存）。エントリ数がこれより少ない場合はジャンプテーブル生成自体を見送る。

3. バイナリ木（Binary tree）

上記のいずれも適用できない場合、比較命令を用いたバイナリ決定木へフォールバックする。

• 確率考慮: プロファイルガイド最適化（

  __builtin_expect_with_probability

  など）の結果に基づき、各ノードの発生頻度を考慮して平衡化を行う（

  balance_case_nodes

  ）。

結論

GCC はスイッチ文を以下のような階層構造で Lowering する。

1. ビットセットへの変換:
   • エッジ数が少なくケース密度が高い場合。
   • 動的プログラミングで最小のビットセット数を見つける。
2. ジャンプテーブルへの変換:
   • 比較回数のコストとエントリサイズの比率（閾値）を考慮。
   • 速度優先時やサイズ優先時に異なる判断基準を使用。
3. バイナリ決定木への変換:
   • その他の場合、プロファイル情報を活用した平衡化された比較木を生成。

より深い理解のためには、GCC のソースコード（特に

pass_lower_switch