GCCにおけるswitch文の低レベル化
Switch Lowering in GCC (xoranth.net)
要約
この記事では、GCCコンパイラがswitch文をどのように最適化するかを解説しています。コンパイラは、caseラベルの密度や性質に応じて、ジャンプテーブル、ビットテスト、または比較の二分木といった異なる低レベル化戦略を採用します。特に、密なケースや連続したケースはジャンプテーブルやビットセットに変換され、疎なケースは比較ツリーに展開されることが示されています。
全文翻訳
GCCにおけるswitch文の低レベル化
2024-01-14
はじめに
以前の記事で、switch文は見た目以上に複雑であることを確認しました。コンパイラは、それを（おそらくそうすべきではないかもしれませんが）決定木として実装することができます。それだけなのでしょうか？
この記事では、gccに焦点を当てます。ビットセット低レベル化を除くすべての最適化は、clangにも適用されます。特に断りがない限り、-O3最適化フラグを使用します。
また、gccのコードを若干編集し、簡潔にするために特定の断言を削除しました。
例
簡単な例から始めましょう。2つの整数xとvalを受け取る関数です。xの値に応じて、対応する関数（f0、f1など）をvalを引数として呼び出し、その結果を返します。これを手動で実装する場合、関数ポインタの配列を使用し、入力値を配列のインデックスとして使用するでしょう。
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;
}
return 0;
}
compact:
mov eax, edi
mov edi, esi
cmp eax, 4
ja .L2
jmp [QWORD PTR .L4[0+rax*8]]
.L4:
.quad .L8
.quad .L7
.quad .L6
.quad .L5
.quad .L3
.L5:
jmp f3
.L3:
jmp f4
.L8:
jmp f0
.L7:
jmp f1
.L6:
jmp f2
.L2:
xor eax, eax
ret
コンパイラはこのアプローチに同意し、switch文をジャンプテーブルに変換します。
さらに、値が定数でオフセットされている場合を識別できます。
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 97:
return f0(val);
case 98:
return f1(val);
case 99:
return f2(val);
case 100:
return f3(val);
case 101:
return f4(val);
default:
return 0;
}
return 0;
}
compact:
lea eax, [rdi-97]
cmp eax, 4
ja .L2
mov edi, esi
jmp [QWORD PTR .L4[0+rax*8]]
.L4:
.quad .L8
.quad .L7
.quad .L6
.quad .L5
.quad .L3
.L5:
jmp f3
.L3:
jmp f4
.L8:
jmp f0
.L7:
jmp f1
.L6:
jmp f2
.L2:
xor eax, eax
ret
値が疎になるほど、ジャンプテーブルへの変換の利点が少なくなることが直感的にわかります。
実験を通じて、gccはしきい値をcaseラベルあたり約8つのジャンプテーブルエントリと見なしていることがわかります。
つまり、次の関数はジャンプテーブルにコンパイルされます。
int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
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;
}
return 0;
}
compact_7:
mov eax, edi
mov edi, esi
cmp eax, 34
ja .L2
jmp [QWORD PTR .L4[0+rax*8]]
.L4:
.quad .L8
.quad .L2
;
.quad .L2
.quad .L7
.quad .L2
;
.quad .L2
.quad .L6
.quad .L2
;
.quad .L2
.quad .L5
.quad .L2
;
.quad .L2
.quad .L3
.L2:
xor eax, eax
ret
.L8:
jmp f0
.L7:
jmp f1
.L6:
jmp f2
.L5:
jmp f3
.L3:
jmp f4
しかし、次の関数は比較のツリーとして展開されます。
int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
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;
}
return 0;
}
sparse_8:
mov eax, edi
mov edi, esi
cmp eax, 16
je .L2
jle .L10
cmp eax, 24
je .L7
cmp eax, 40
jne .L1
jmp f4
.L10:
test eax, eax
je .L4
cmp eax, 8
jne .L1
jmp f1
.L1:
xor eax, eax
ret
.L4:
jmp f0
.L7:
jmp f3
.L2:
jmp f2
比較ツリーを明確にするために視覚化します。
G ret 0 ret 0 call f0 call f0 call f1 call f1 call f2 call f2 cmp eax, 24 cmp eax, 24 call f3 call f3 call f4 call f4 cmp eax, 16 cmp eax, 16 cmp eax, 16->call f2 je test eax, eax test eax, eax cmp eax, 16->test eax, eax jle cmp eax, 16->cmp eax, 24 test eax, eax->call f0 je cmp eax, 8 cmp eax, 8 test eax, eax->cmp eax, 8 cmp eax, 24->call f3 je cmp eax, 40 cmp eax, 40 cmp eax, 24->cmp eax, 40 cmp eax, 40->ret 0 jne cmp eax, 40->call f4 cmp eax, 8->ret 0 jne cmp eax, 8->call f1
いくつかの観察事項があります。
- これまでは等間隔の値のみを試しました。コンパイラは、すべてのケースのサブセットで収益性の高い変換を識別できますか？
- これまでは各
caseが異なる結果につながりました。異なるケースが同じ結果をもたらす場合はどうなりますか？ sparse_8のswitch文は、ジャンプ前にxを8で割ることで簡略化できます。興味深いことに、gccはこの簡略化を見つけません。
1と2について掘り下げてみましょう。
外れ値
最初の例に外れ値を含めることで変更を加えると、コンパイラが密なケースのサブセットを認識できることがわかります。
int f0(int val);
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
int f5(int val);
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;
}
return 0;
}
outlier:
mov eax, edi
mov edi, esi
cmp eax, 5
jg .L2
test eax, eax
jle .L1
cmp eax, 5
ja .L4
jmp [QWORD PTR .L6[0+rax*8]]
.L6:
.quad .L4
.quad .L4
.quad .L9
.quad .L8
.quad .L7
.quad .L5
.L2:
cmp eax, 100
jne .L1
jmp f5
.L7:
jmp f3
.L5:
jmp f4
.L9:
jmp f1
.L8:
jmp f2
.L4:
jmp f0
.L1:
xor eax, eax
ret
コンパイラはcase 100のために分岐を生成しますが、case 1から5のためにはジャンプテーブルを生成します。
連続
これまでの例では、各case文は異なるコードブロックにつながっていました。複数のcaseラベルが同じ関数を呼び出す場合、何が起こるかテストしてみましょう。
int f1(int val);
int f2(int val);
int f3(int val);
int f4(int val);
int f5(int val);
int blocks_2(int x, int val) {
switch (x) {
case 0: case 1: case 2: case 3:
return f1(val);
case 21: ... case 24:
return f2(val);
case 42: ... case 45:
return f3(val);
case 63: ... case 66:
return f4(val);
case 84: ... case 87:
return f5(val);
default:
return 0;
}
return 0;
}
blocks_2:
mov eax, edi
mov edi, esi
cmp eax, 45
jg .L2
cmp eax, 41
jg .L3
cmp eax, 3
jg .L4
test eax, eax
js .L1
jmp f1
.L2:
cmp eax, 66
jg .L8
cmp eax, 62
jle .L1
jmp f4
.L4:
sub eax, 21
cmp eax, 3
ja .L1
jmp f2
.L8:
sub eax, 84
cmp eax, 3
ja .L1
jmp f5
.L3:
jmp f3
.L1:
xor eax, eax
ret
私たちは20のcaseラベルを持ち、値は0から87の間です。コンパイラは、88エントリのジャンプテーブルにこのswitchを低レベル化できます。ジャンプテーブル変換が有利であるためのヒューリスティックの仮説は、そのサイズが8 * num_case_labelsよりも小さい場合です。88 < 20 * 8なので、このケースでは変換は有利であるはずですが、gccは比較のシーケンスにswitchを低レベル化することを選択しました。
その理由をよりよく理解するために、caseラベルの特定のブロックを調べましょう。
int blocks_2(int x, int val) {
switch (x) {
case 42: case 43: case 44:
case 45:
return f3(val);
}
return 0;
}
blocks_2:
mov eax, edi ; Move `val` to $eax
mov edi, esi
cmp eax, 45
; If val <= 45, do _not_ jump
jg .L2
cmp eax, 41
; If val >= 42, jump to L3
jg .L3
; ...
.L2:
; ...
.L3:
; We reach L3 only if 42 <= val <= 45
jmp f3 ; Call f3(val)
; ...
コンパイラは、ケースが連続していることを認識し、4つではなく2つの比較で実装できることを実現します。ジャンプテーブルヒューリスティックの入力がcaseラベルの数ではなく比較の数である場合、物事はうまくいきます。
合計で10回の比較があります。10 * 8 < 88なので、改訂されたヒューリスティックはジャンプテーブル変換が不利であることを示唆しています。
非連続
非連続なケースを試してみましょう。
int f1(int val);
int bittest(int x, int val) {
switch (x) {
case '0': case '2': case '4':
case '5': case '7': case '9':
case 'A': case 'C': case 'E':
return f1(x);
default:
return 0;
}
return 0;
}
bittest:
lea eax, [rdi-48]
cmp eax, 21
ja .L1
mov edx, 2753205 ; ???
bt rdx, rax
cjc .L7
.L1:
xor eax, eax
ret
.L7:
jmp f1
コンパイラは直感的でないマシンコードを生成します。なぜcmpもジャンプテーブルもないのですか？定数2753205はどこから来るのですか？
bt命令からのヒントが得られます。Intelドキュメントによると、btは：
ビット文字列内のビット（最初のオペランド、ビットベースと呼ばれる）を、ビットオフセット（2番目のオペランドで指定される）によって指定されたビット位置で選択し、ビットの値をCFフラグに格納します。
2753205のバイナリ表現を調べると、実際にはビットセットであることがわかります。1に設定されているビットは、caseラベルのASCII値に対応しており、各値は48から減算されています。
Simd ops chars 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G Cases ... edx 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 mov edx, 2753205 edx:p0--chars:p0 edx:p2--chars:p2 edx:p4--chars:p4 edx:p5--chars:p5 edx:p7--chars:p7 edx:p9--chars:p9 edx:p17--chars:p17 edx:p19--chars:p19 edx:p21--chars:p21
実装
GCCがswitch文を低レベル化する際に採用する、いくつかの異なる戦略に遭遇しました。より詳細な理解のために、コンパイラのソースコードを調べることができます。
switch文の低レベル化を担当するコンパイラパスは、（名前の通り）pass_lower_switchであり、これはanalyze_switch_statementを呼び出します。
GCCのソースコードは追跡が困難な場合があるため、以下にステップバイステップでコメント付きのバージョンを提供します。その後、各セクションを分解してその機能について説明します。
bool switch_decision_tree::analyze_switch_statement ()
{
unsigned l = gimple_switch_num_labels (m_switch);
auto_vec<cluster *> clusters;
...
compute_cases_per_edge ();
いくつかの前置きコードです。m_switchはgimpleオブジェクトを指します。GimpleはGCCが使用する内部表現です。これを通じて、ケースの全体数と各出力エッジのケースの個別の数を抽出します。
また、各caseラベルに選択された低レベル化戦略を記録するベクトルを割り当てます。
for (unsigned i = 1; i < l; i++)
{
tree elt = gimple_switch_label (m_switch, i);
// ...
tree low = CASE_LOW (elt);
tree high = CASE_HIGH (elt);
profile_probability p
= case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest, p));
// ...
}
さらにセットアップコードがあります。Gimpleには各ラベルに高値と低値の概念があることがわかります。つまり、連続したcaseラベルはこの段階ですでに結合されています。
各caseラベルに対して、simple_clusterを割り当てます。このクラスタはレコードとして機能し、ラベルに関連付けられた値の範囲、関連する出力エッジ、およびこのクラスタが選択される可能性をキャプチャします。この確率は、プロファイルガイド付き最適化から取得されます。デフォルトでは、caseラベル間で均一です。
// ...
vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters);
作成したクラスタのベクトルを変換します。bit_test_clusterという名前は、前述のビットセット低レベル化戦略を示唆しています。
/* Find jump table clusters. */
vec<cluster *> output2;
auto_vec<cluster *> tmp;
// ...
for (unsigned i = 0; i < output.length (); i++) {
cluster *c = output[i];
if (c->get_type () != SIMPLE_CASE) {
if (!tmp.is_empty ()) {
tmp.truncate (0);
}
output2.safe_push (c);
}
else
tmp.safe_push (c);
}
このセクションは、変換されたケースのベクトルと一時的なベクトルを割り当てます。ビットセット変換プロセス中に変更されなかったケースは、この一時的なベクトルに収集されます。これらのケースは、最適化されたクラスタが見つかるたびに処理され、クリアされます。
基本的に、このセクションではビットセットクラスタに変換できなかったcaseラベルのシーケンスを探しています。
vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
output2.safe_splice (n);
n.release ();
これらの連続するラベルをジャンプテーブルに変換しようとし、その結果を出力に追加します。
/* We still can have a temporary vector to test. */
if (!tmp.is_empty ()) {
vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
output2.safe_splice (n);
n.release ();
}
これは上記のループのコーダです。
// ...
bool expanded = try_switch_expansion (output2);
release_clusters(output2);
return expanded;
}
残ったものはすべて別のパスを通過し、switch文を決定木に変換します。ビットセットとジャンプテーブルは決定木のリーフです。
ビットセット
bit_test_cluster::find_bit_testsをさらに掘り下げてみましょう。コードのハイレベルな構造は次のとおりです。
最初に、すべてのクラスタをビットセットにバンドルする最適な方法を見つけることを目指します。この文脈での最適性とは、使用するビットセットの数を最小限に抑えることを意味します。動的計画法を使用してこれを行います。
次に、ビットセットを反復処理し、収益性ヒューリスティックを適用します。ビットセットがこのヒューリスティックを満たす場合、bit_test_clusterを発行します。そうでない場合は、元のsimple_clusterを保持します。
vec<cluster *> bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
{
...
unsigned l = clusters.length ();
auto_vec<min_cluster_item> min;
...
min.quick_push (min_cluster_item (0, 0, 0));
for (unsigned i = 1; i <= l; i++)
{
min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
for (unsigned j = 0; j < i; j++)
{
if (min[j].m_count + 1 < min[i].m_count
&& can_be_handled (clusters, j, i - 1))
min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
}
gcc_checking_assert (min[i].m_count != INT_MAX);
}
動的計画法のために、min_cluster_item構造体のベクトルを使用します。各min_cluster_itemには3つのコンポーネントがあります。
- 最初のコンポーネントは、最初のi個のcaseラベルを表すためにいくつのビットセットが必要かを記録します。ここで、
iはベクトルのインデックスです。 - 2番目のコンポーネントは、最後のビットセットの開始を記録します。
- 3番目のコンポーネントは未使用です。
動的計画法は次のとおりです。最初のi個のcaseラベルを表すために必要なビットセットの最小数を見つけたいと考えています。
ベースケースは単純で、単一のcaseラベルは単一のビットセットで表すことができます。
最初のj個のcaseラベルに対する最適なビットセット数をすでに求めたと仮定します。を最初のi要素に対する最適な分割数と定義します。これは、すでにを計算し、現在を求めていることを意味します。
caseラベルの範囲がビットセットクラスタとして表される場合、次のことが真である必要があります。
逆に、最初のiラベルに対する最適な割り当てがあると仮定します。最後のビットセットがラベルで始まる場合、この割り当てはに制限された割り当てとしても最適です。そうでない場合、も改善できます。
したがって、次のことが真である必要があります。
これらの条件は、コード内のifステートメントがチェックしているものと正確に一致します。
can_be_handled関数は、caseラベルの範囲がビットセットテストに変換できるかどうかを制御します。2つの基準をテストします。
- 結合されたすべてのcaseラベルの範囲は、レジスタの幅よりも小さくなければなりません。現代のシステムでは、結合された範囲は64未満である必要があります。
- caseラベルは、最大3つの一意の出力エッジを持たなければなりません。
エッジが1つより多い場合、ビットテストの連鎖を発行します。
vec<cluster *> output;
// ...
/* Find and build the clusters. */
for (unsigned end = l;;)
{
int start = min[end].m_start;
if (is_beneficial (clusters, start, end - 1))
{
bool entire = start == 0 && end == clusters.length ();
output.safe_push (new bit_test_cluster (clusters, start, end - 1, entire));
}
else
for (int i = end - 1; i >= start; i--)
output.safe_push (clusters[i]);
end = start;
if (start <= 0)
break;
}
output.reverse ();
return output;
}
ここで、is_beneficialテストを満たすビットセットのみを変換します。コードでは、countはクラスタによって処理されるcaseラベルの数、uniqは一意の出力エッジの数を表します。
bool bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
{
return (((uniq == 1 && count >= 3)
|| (uniq == 2 && count >= 5)
|| (uniq == 3 && count >= 6)));
}
ジャンプテーブル
ジャンプテーブル変換のロジックは、ビットテスト変換に使用されるものと似ています。動的計画法を活用して、ジャンプテーブルに収益性高く変換できる「クラスタ」を特定します。
コードを掘り下げてみましょう。
vec<cluster *> jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
{
if (!is_enabled ())
return clusters.copy ();
unsigned l = clusters.length ();
auto_vec<min_cluster_item> min;
min.reserve (l + 1);
最初に、min_cluster_itemのベクトルを事前に割り当てます。このベクトルを使用して、連続するcaseクラスタの最適なジャンプテーブル割り当てを追跡します。
min.quick_push (min_cluster_item (0, 0, 0));
動的計画法のベースケースもプッシュします。これは、switch全体に対して単一のジャンプテーブルを使用することに対応します。
ここでメインループに焦点を当てましょう。
unsigned HOST_WIDE_INT max_ratio = /* Used in the main heuristic. See next snippet. */;
for (unsigned i = 1; i <= l; i++)
{
// NOTE(xoranth): Base case
min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
/* Pre-calculate number of comparisons for the clusters. */
HOST_WIDE_INT comparison_count = 0;
for (unsigned k = 0; k <= i - 1; k++)
{
simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
NOTE(xoranth): get_comparison_count is 2 for contiguous case
labels, and 1 otherwise
comparison_count += sc->get_comparison_count ();
}
for (unsigned j = 0; j < i; j++)
{
unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
if (i - j < case_values_threshold ())
s += i - j;
Prefer clusters with smaller number of numbers covered.
if ()
{
min[i] = min_cluster_item (min[j].m_count + 1, j,
s );
}
simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
comparison_count -= sc->get_comparison_count ();
}
}
動的計画法ループはビットセットのものと似ています。最初のi個のcaseラベルを表すために必要なジャンプテーブルの最小数を見つけたいと考えています。
j < iの場合のj番目のcaseラベルでの分割を反復処理します。各反復中に、最良のスコアリング分割を追跡します。特別なケースj == 0は、switch文全体に対する単一のジャンプテーブルを表します。
この内部ループ内で、次のものも追跡します。
- switch文を低レベル化するために必要なジャンプテーブルの数。
- 分解の最後のジャンプテーブルの開始。
- ジャンプテーブルで処理できないケースの数。コードでは、これはアキュムレータ
sです。
ポイント1と2はビットセット低レベル化パスに類似していますが、3は新しく、ジャンプテーブルに固有です。
具体的には、ジャンプテーブルへのディスパッチには、間接ジャンプと境界チェックの必要性によるオーバーヘッドがあります。したがって、gccはジャンプテーブルを生成するために最小限のcaseラベルを必要とします。
分割によってジャンプテーブルが小さすぎる場合、ジャンプテーブルのサイズはアキュムレータsに追加され、異なる分割候補間のタイブレーカーとして使用されます。
スコアリングを計算するには、j番目とi番目のcaseラベル間の比較数が必要です。すべてのラベルの比較数の合計を計算し、内部ループが進むにつれてカウントを減らします。
処理されないcaseラベルの数も計算する必要があります。これは、ジャンプテーブルのサイズとcase_values_threshold関数の結果を比較することによって決定されます。この関数はアーキテクチャに依存し、switch-case固有の命令の存在を考慮しますが、最新のx64およびArm64マシンではデフォルトで5になります。
unsigned int default_case_values_threshold (void) {
return (targetm.have_casesi () ? 4 : 5);
}
ここで、max_ratioがどのように計算されるかから始めて、メインヒューリスティックに焦点を当てましょう。メインループを以下に再現します。メインヒューリスティックに関連しない行は省略しています。
GCCは、ジャンプテーブルエントリと比較の比率を低レベル化ヒューリスティックのメトリックとして使用していることがわかりました。下のコードは、速度（フラグ-O[123|fast]）またはサイズ（フラグ-Os）の最適化時に異なる比率が使用されることを示しています。具体的には、速度最適化時には比率8が、サイズ最適化時には比率2が使用されます。
unsigned HOST_WIDE_INT max_ratio
= (optimize_insn_for_size_p ()
? param_jump_table_max_growth_ratio_for_size // This is `2`
: param_jump_table_max_growth_ratio_for_speed); // This is `8`
for (unsigned i = 1; i <= l; i++)
{
/* Set minimal # of clusters with i-th item to infinite. */
min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
// NOTE(xoranth): Compute comparison count, see previous snippet
for (unsigned j = 0; j < i; j++)
{
NOTE(xoranth): Compute unhandled cases, see previous snippet
Prefer clusters with smaller number of numbers covered.
if ((min[j].m_count + 1 < min[i].m_count)
|| (min[j].m_count + 1 == min[i].m_count && s < min[i].m_non_jt_cases)
&& can_be_handled (clusters, j, i - 1, max_ratio, comparison_count))
{
min[i] = min_cluster_item (min[j].m_count + 1, j,
s );
}
// NOTE(xoranth): Update comparison count, see previous snippet
}
}
次にメインループに入ります。2つの分割が与えられた場合、ジャンプテーブルの発行数が少なくなる分割を優先します。または、同じ数のジャンプテーブルが発行される場合、最も多くのcaseラベルを処理する分割を優先します。また、収益性の低いジャンプテーブルを生成する分割は無視されます。収益性はcan_be_handled関数によってチェックされます。
can_be_handled条件は、オーバーフローをチェックし、caseラベル数とジャンプテーブルエントリ数の比率を比較します。
bool jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
unsigned start, unsigned end,
unsigned HOST_WIDE_INT max_ratio,
unsigned HOST_WIDE_INT comparison_count)
{
If the switch is relatively small such that the cost of one
indirect jump on the target are higher than the cost of a
decision tree, go with the decision tree.
[...]
For algorithm correctness, jump table for a single case must return
true. We bail out in is_beneficial if it's called just for
a single case.
if (start == end)
return true;
unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), clusters[end]->get_high ());
Check for overflow.
...
return lhs <= max_ratio * comparison_count;
}
関数のコーダもビットセットクラスタのものと似ています。すべてのジャンプテーブルを逆順に反復処理し、is_beneficialチェックに失敗したものを削除します。
vec<cluster *> output;
output.create (4);
/* Find and build the clusters. */
for (unsigned int end = l;;)
{
int start = min[end].m_start;
/* Do not allow clusters with small number of cases. */
if (is_beneficial (clusters, start, end - 1))
output.safe_push (new jump_table_cluster (clusters, start, end - 1));
else
for (int i = end - 1; i >= start; i--)
output.safe_push (clusters[i]);
end = start;
if (start <= 0) break;
}
output.reverse ();
return output;
}
ジャンプテーブルのis_beneficialチェックは、小さなジャンプテーブルを削除することを目的としています。caseラベルの数とcase_values_thresholdを比較します。
bool jump_table_cluster::is_beneficial (const vec<cluster *> &, unsigned start, unsigned end) {
if (start == end) return false;
return end - start + 1 >= case_values_threshold ();
}
二分木
GCCがビットセットクラスタまたはジャンプテーブルを発行できない場合、二分木の比較にフォールバックします。
ツリーを発行する際に、各caseラベルクラスタの確率を考慮に入れます。確率はプロファイルガイド付き最適化を介して取得されるか、__builtin_expect_with_probability組み込み関数を使用して取得できます。
コードは非常に単純です。
void switch_decision_tree::balance_case_nodes (case_tree_node **head, case_tree_node *parent)
{
case_tree_node *np = *head;
if (np) {
int i = 0;
case_tree_node **npp, *left;
profile_probability prob = profile_probability::never ();
すべてのcaseラベルの確率を合計します。
/* Count the number of entries on branch. Also count the ranges. */
while (np) {
i++;
prob += np->m_c->m_prob;
np = np->m_right;
}
caseラベルリストを、両方の半分が等しい確率を持つように分割します。
if (i > 2) {
npp = head;
left = *npp;
// NOTE(xoranth): this divides prob by 2.
profile_probability pivot_prob = prob.apply_scale (1, 2);
while (1) {
Skip nodes while their probability does not reach that amount.
prob -= (*npp)->m_c->m_prob;
if ((prob.initialized_p () && prob < pivot_prob) || ! (*npp)->m_right)
break;
npp = &(*npp)->m_right;
}
np = *npp;
*npp = 0;
*head = np;
np->m_parent = parent;
np->m_left = left == np ? NULL : left;
両方の半分で再帰的に二分木を構築します。
balance_case_nodes (&np->m_left, np);
balance_case_nodes (&np->m_right, np);
np->m_c->m_subtree_prob = np->m_c->m_prob;
if (np->m_left)
np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
if (np->m_right)
np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
} else {
// [...] Base case
}
}
}
結論
GCCがswitch文をコンパイルする際に採用するヒューリスティックと低レベル化戦略を見てきました。これには以下が含まれます。
- 複数の
caseラベルをビットセットに圧縮する。 switch文をジャンプテーブルに変換する。switch文を二分決定木に変換する。
さらに深く掘り下げたい方は、GCCのソースコードとこの論文を読むことをお勧めします。
最後に、この投稿を書くにあたってフィードバックをくれたB.X.V.、C.P.、およびV.P.に感謝します