[インデックス 123] ファイルの概要

このコミットは、Goコンパイラのx86-64アーキテクチャ向けバックエンドである6gのコード生成部分、具体的にはsrc/cmd/6g/gen.cファイルに対する変更です。このファイルは、Go言語のソースコードをx86-64アセンブリコードに変換する際の、様々な命令の生成ロジックを含んでいます。特に、整数除算（div）と剰余（mod）演算のコード生成に関する改善が行われています。

コミット

more div/mod

SVN=121577

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/181ad4743cdf29a4ef71f97ad1ea0d2840696714

元コミット内容

commit 181ad4743cdf29a4ef71f97ad1ea0d2840696714
Author: Ken Thompson <ken@golang.org>
Date:   Fri Jun 6 21:21:54 2008 -0700

    more div/mod
    
    SVN=121577

変更の背景

このコミットは、Goコンパイラの初期段階における、x86-64アーキテクチャでの整数除算および剰余演算のコード生成ロジックの改善を目的としています。x86アーキテクチャでは、DIV命令やIDIV命令（符号付き除算）は、特定のレジスタ（RAXとRDX）を暗黙的に使用するという特殊な性質を持っています。具体的には、除算の被除数はRDX:RAXレジスタペアに格納され、除算後には商がRAXに、剰余がRDXに格納されます。

従来のコード生成では、これらのレジスタが既に他の目的で使用されている場合に、コンパイラが適切にレジスタを退避・復元する処理が不足していた可能性があります。その結果、レジスタの衝突が発生し、誤ったコードが生成されたり、コンパイラが異常終了したりする可能性がありました。

このコミットは、cgen_div関数（除算のコード生成を担当する関数）において、RAXとRDXレジスタが既に占有されている場合に、それらのレジスタの内容を一時的に退避し、除算命令の実行後に復元するロジックを追加することで、この問題を解決しようとしています。これにより、より堅牢で正しい除算・剰余のコード生成が可能になります。

前提知識の解説

x86-64アーキテクチャにおける整数除算とレジスタ

x86-64アーキテクチャでは、整数除算命令（DIVまたはIDIV）は、以下のように特定のレジスタを暗黙的に使用します。

• RAX (Accumulator Register): 64ビットの汎用レジスタ。除算命令では、被除数の下位64ビットを格納し、除算後には商が格納されます。
• RDX (Data Register): 64ビットの汎用レジスタ。除算命令では、被除数の上位64ビットを格納し、除算後には剰余が格納されます。

符号付き除算（IDIV）の場合、被除数が64ビットであっても、除算前にRAXの内容をRDXに符号拡張するCQO（Convert Quadword to Octaword）命令（32ビットの場合はCDQ）がよく使用されます。これにより、RDX:RAXレジスタペア全体で128ビットの被除数を表現します。

コンパイラのレジスタ割り当て

コンパイラは、プログラムの実行速度を最大化するために、頻繁に使用される値をCPUのレジスタに割り当てます。これをレジスタ割り当て（Register Allocation）と呼びます。しかし、レジスタの数は限られているため、コンパイラはどの値をどのレジスタに割り当てるかを慎重に決定する必要があります。

特定の命令（今回のDIV/IDIVのように）が特定のレジスタを暗黙的に使用する場合、コンパイラはそのレジスタが他の目的で使用されていないことを確認するか、もし使用されている場合はその内容を一時的にメモリに退避（spill）し、命令実行後にレジスタに復元（reload）する必要があります。このプロセスは「レジスタの退避と復元」と呼ばれます。

Ullman Number (ウルマン数)

Ullman Numberは、コンパイラの最適化、特にレジスタ割り当ての文脈で用いられる概念です。式木の各ノードに対して計算される値で、そのノードを評価するために必要なレジスタの最小数を示します。Ullman Numberが大きいほど、そのサブツリーの評価にはより多くのレジスタが必要となる可能性があり、コンパイラはレジスタの利用効率を考慮してコード生成の順序を決定します。

このコミットのコードでは、nl->ullman >= nr->ullmanという条件が見られます。これは、左オペランド（nl）と右オペランド（nr）のどちらを先に評価するかを決定する際に、Ullman Numberを考慮していることを示唆しています。一般的に、Ullman Numberが大きい方を先に評価することで、レジスタのスピルを減らすことができる場合があります。

Goコンパイラ（6g）の内部関数

• nodreg(Node *n, Type *t, int r): 指定されたレジスタrに対応するノードnを作成します。
• regalloc(Node *n, Type *t, Node *res): レジスタを割り当てます。nにレジスタを割り当て、その結果をresに格納します。
• regfree(Node *n): 割り当てられたレジスタを解放します。
• gmove(Node *f, Node *t): fからtへデータを移動するアセンブリ命令を生成します。
• gins(int as, Node *f, Node *t): 指定されたアセンブリ命令asとオペランドf, tを用いてアセンブリ命令を生成します。
  • AMOVQ: 64ビットデータを移動する命令（MOVQ）。
  • ACDQ: 32ビットのEAXレジスタの内容をEDX:EAXに符号拡張する命令（CDQ）。64ビットの場合はCQOに相当する処理が行われます。
• optoas(int op, Type *t): Goの演算子（op）を対応するアセンブリ命令（as）に変換します。ODIVは除算、OMODは剰余に対応します。

技術的詳細

このコミットの主要な変更は、cgen_div関数におけるRAX（D_AX）とRDX（D_DX）レジスタの取り扱いを改善した点です。

変更前は、cgen_divの冒頭でreg[D_AX] || reg[D_DX]が真の場合にfatal("registers occupide")としてコンパイラを異常終了させていました。これは、除算命令がこれらのレジスタを暗黙的に使用するため、既に占有されている場合は処理できないという単純な実装でした。

変更後は、sameregという新しいヘルパー関数が導入され、RAXまたはRDXが既に占有されている場合でも、そのレジスタが除算結果の格納先（res）と同じでない限り、レジスタの内容を一時的に退避・復元するロジックが追加されました。

samereg関数の追加

+int
+samereg(Node *a, Node *b)
+{
+\tif(a->op != OREGISTER)
+\t\treturn 0;
+\tif(b->op != OREGISTER)
+\t\treturn 0;
+\tif(a->val.vval != b->val.vval)
+\t\treturn 0;
+\treturn 1;
+}

この関数は、2つのNodeが同じレジスタを表しているかどうかをチェックします。OREGISTERオペランドであり、かつval.vval（レジスタ番号）が同じであれば、同じレジスタであると判断します。

cgen_div関数の変更点

1. レジスタ退避・復元ロジックの追加: RAX（D_AX）とRDX（D_DX）レジスタが既に占有されている場合、かつそのレジスタが除算結果の格納先（res）ではない場合に、以下の処理を行います。

   • 一時的なノードn3を割り当てます。
   • 占有されているレジスタ（n1またはn2）の内容をn3に移動（AMOVQ）して退避します。
   • 占有されているレジスタを解放（regfree）し、reg[D_AX]またはreg[D_DX]を0に設定して、レジスタが空いている状態にします。
   • 再帰的にcgen_divを呼び出し、除算のコードを生成させます。
   • 除算処理が完了した後、退避しておいたn3の内容を元のレジスタ（n1またはn2）に復元（AMOVQ）します。
   • 一時的なノードn3を解放します。

   この再帰的な呼び出しと退避・復元メカニズムにより、RAXやRDXが一時的に必要となる除算命令の実行中に、これらのレジスタが他の目的で占有されていても、その内容が失われることなく処理を進めることができるようになります。

2. Ullman Numberに基づく評価順序の改善: 変更前は、nl->ullman >= nr->ullmanの条件分岐内で、nr->addable（右オペランドが直接アセンブリ命令のオペランドとして使用可能か）によってコード生成のパスが分かれていました。 変更後は、このnr->addableによる分岐が削除され、常にcgen(nr, &n3); gins(a, &n3, N);という形式で右オペランドを評価し、その結果をレジスタn3に格納してから除算命令を実行するようになりました。これにより、コード生成のロジックが簡素化され、一貫性が保たれています。

3. レジスタ解放のタイミングの調整: 変更前は、n3レジスタの解放が条件分岐の内部で行われていましたが、変更後はcgen_div関数の最後に一度だけregfree(&n3);が呼び出されるようになりました。これにより、n3レジスタのライフタイムが適切に管理され、不要なレジスタの占有を防ぎます。

コアとなるコードの変更箇所

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -827,49 +827,85 @@ cgen_as(Node *nl, Node *nr, int op)\n  cgen(nr, nl);\n }\n \n+int\n+samereg(Node *a, Node *b)\n+{\n+\tif(a->op != OREGISTER)\n+\t\treturn 0;\n+\tif(b->op != OREGISTER)\n+\t\treturn 0;\n+\tif(a->val.vval != b->val.vval)\n+\t\treturn 0;\n+\treturn 1;\n+}\n+\n void\n cgen_div(int op, Node *nl, Node *nr, Node *res)\n {\n  Node n1, n2, n3;\n-\tint a;\n+\tint a, rax, rdx;\n \n-\tif(reg[D_AX] || reg[D_DX]) {\n-\t\tfatal(\"registers occupide\");\n-\t}\n+\tnodreg(&n1, types[TINT64], D_AX);\
+\tnodreg(&n2, types[TINT64], D_DX);\
 \n-\ta = optoas(op, nl->type);\
+\trax = reg[D_AX];\
+\trdx = reg[D_DX];\
+\n \t// hold down the DX:AX registers\n-\tnodreg(&n1, types[TINT64], D_AX);\
-\tnodreg(&n2, types[TINT64], D_DX);\
 \tregalloc(&n1, nr->type, &n1);\
+\tif(rax && !samereg(res, &n1)) {\
+\t\t// clean out the AX register\n+\t\tregalloc(&n3, types[TINT64], N);\
+\t\tgins(AMOVQ, &n1, &n3);\
+\t\tregfree(&n1);\
+\n+\t\treg[D_AX] = 0;\
+\t\tcgen_div(op, nl, nr, res);\
+\t\treg[D_AX] = rax;\
+\n+\t\tgins(AMOVQ, &n3, &n1);\
+\t\tregfree(&n3);\
+\t\treturn;\n+\t}\n+\n \tregalloc(&n2, nr->type, &n2);\
+\tif(rdx && !samereg(res, &n2)) {\
+\t\t// clean out the DX register\n+\t\tregalloc(&n3, types[TINT64], N);\
+\t\tgins(AMOVQ, &n2, &n3);\
+\t\tregfree(&n1);\
+\n+\t\treg[D_DX] = 0;\
+\t\tcgen_div(op, nl, nr, res);\
+\t\treg[D_DX] = rdx;\
+\n+\t\tgins(AMOVQ, &n3, &n2);\
+\t\tregfree(&n3);\
+\t\treturn;\n+\t}\n+\n+\ta = optoas(op, nl->type);\
 \n \tif(!issigned[nl->type->etype]) {\n \t\tnodconst(&n3, nl->type, 0);\
 \t\tgmove(&n3, &n2);\
 \t}\n \n+\tregalloc(&n3, nr->type, res);\
 \tif(nl->ullman >= nr->ullman) {\n \t\tcgen(nl, &n1);\
 \t\tif(issigned[nl->type->etype])\n \t\t\tgins(ACDQ, N, N);\
-\t\tif(!nr->addable) {\n-\t\t\tregalloc(&n3, nr->type, res);\
-\t\t\tcgen(nr, &n3);\
-\t\t\tgins(a, &n3, N);\
-\t\t\tregfree(&n3);\
-\t\t} else\n-\t\t\tgins(a, nr, N);\
+\t\tcgen(nr, &n3);\
+\t\tgins(a, &n3, N);\
 \t} else {\n-\t\tregalloc(&n3, nr->type, res);\
 \t\tcgen(nr, &n3);\
 \t\tcgen(nl, &n1);\
 \t\tif(issigned[nl->type->etype])\n \t\t\tgins(ACDQ, N, N);\
 \t\tgins(a, &n3, N);\
-\t\tregfree(&n3);\
 \t}\n+\tregfree(&n3);\
 \n \tif(op == ODIV)\n \t\tgmove(&n1, res);\

コアとなるコードの解説

samereg関数の追加 (行 831-838)

• この新しい関数は、2つのノードが同じレジスタを参照しているかどうかを効率的にチェックするために導入されました。
• a->op != OREGISTER や b->op != OREGISTER で、ノードがレジスタではない場合は即座に0（偽）を返します。
• a->val.vval != b->val.vval で、レジスタの識別子（レジスタ番号）が異なる場合も0を返します。
• 両方の条件を満たせば、同じレジスタであると判断し1（真）を返します。

cgen_div関数の変更 (行 841-885)

1. レジスタ退避・復元ロジックの導入 (行 846-869):

   • rax = reg[D_AX]; と rdx = reg[D_DX]; で、現在のRAXとRDXレジスタの占有状態を保存します。
   • nodreg(&n1, types[TINT64], D_AX); と nodreg(&n2, types[TINT64], D_DX); で、RAXとRDXに対応するノードを作成します。
   • regalloc(&n1, nr->type, &n1); と regalloc(&n2, nr->type, &n2); で、RAXとRDXを割り当てます。
   • if(rax && !samereg(res, &n1)) と if(rdx && !samereg(res, &n2)) のブロックが、レジスタ退避・復元の中核です。
     • raxまたはrdxが0でない（つまり、RAXまたはRDXが既に占有されている）ことを確認します。
     • !samereg(res, &n1) または !samereg(res, &n2) で、除算結果の格納先レジスタ（res）が、現在占有されているRAXまたはRDXとは異なることを確認します。
     • これらの条件が満たされた場合、以下の処理が行われます。
       • regalloc(&n3, types[TINT64], N); で一時レジスタn3を割り当てます。
       • gins(AMOVQ, &n1, &n3); または gins(AMOVQ, &n2, &n3); で、占有されているレジスタの内容をn3に退避します。
       • regfree(&n1); または regfree(&n2); で、占有されているレジスタを解放します。
       • reg[D_AX] = 0; または reg[D_DX] = 0; で、コンパイラのレジスタ管理状態を更新し、該当レジスタが空いているとマークします。
       • cgen_div(op, nl, nr, res); で、cgen_div関数を再帰的に呼び出します。これにより、RAX/RDXが空いている状態で除算のコードが生成されます。
       • reg[D_AX] = rax; または reg[D_DX] = rdx; で、元のレジスタ占有状態を復元します。
       • gins(AMOVQ, &n3, &n1); または gins(AMOVQ, &n3, &n2); で、退避しておいた内容を元のレジスタに戻します。
       • regfree(&n3); で一時レジスタn3を解放します。
       • return; で、現在のcgen_divの実行を終了します。再帰呼び出しによって既に処理が完了しているためです。

2. 被除数の符号拡張 (行 875, 881):

   • if(issigned[nl->type->etype]) gins(ACDQ, N, N); は、被除数（nl）が符号付き整数型の場合に、RAXの内容をRDX:RAXに符号拡張する命令（ACDQはCDQまたはCQOに相当）を生成します。これは、符号付き除算の前に必須のステップです。

3. 右オペランドの評価と除算命令の生成 (行 876-877, 882-883):

   • regalloc(&n3, nr->type, res); で、右オペランド（除数）を格納するための一時レジスタn3を割り当てます。
   • cgen(nr, &n3); で、右オペランドnrのコードを生成し、結果をn3に格納します。
   • gins(a, &n3, N); で、除算命令（aはIDIVまたはDIV）を生成します。この命令は、RDX:RAXをn3の内容で除算します。

4. レジスタ解放の統一 (行 885):

   • regfree(&n3); が関数の最後に移動され、n3レジスタの解放が統一的に行われるようになりました。これにより、レジスタのライフタイム管理が改善されています。

関連リンク

• Go言語のコンパイラに関する情報: https://go.dev/doc/compiler
• x86-64命令セットリファレンス（Intel Software Developer's Manualなど）
• コンパイラのレジスタ割り当てに関する一般的な情報

参考にした情報源リンク

• https://github.com/golang/go/commit/181ad4743cdf29a4ef71f97ad1ea0d2840696714
• x86 Assembly Guide: https://www.cs.virginia.edu/~evans/cs216/guides/x86.html
• Ullman's Algorithm for Register Allocation: https://en.wikipedia.org/wiki/Ullman%27s_algorithm (一般的な情報源として)
• Go Compiler Source Code (for context on 6g, Node, Type, reg etc.): https://github.com/golang/go