Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goコンパイラ（cmd/5g、ARMアーキテクチャ向け）におけるスライス境界チェックの最適化に関するものです。具体的には、スライスアクセス時の境界チェックにおいて、一時レジスタへの値の移動を省略することで、生成されるアセンブリコードの効率を向上させています。これにより、命令数が削減され、実行速度のわずかな改善とコードサイズの縮小が期待されます。また、gcmp関数の制約が緩和され、第2オペランドがレジスタである必要がなくなりました。

コミット

commit 01ddc8bd9ae903aea203dfe927bb072fe6bce24a
Author: Dave Cheney <dave@cheney.net>
Date:   Sun Oct 7 11:37:14 2012 +1100

    cmd/5g: avoid temporary in slice bounds check
    
    before
    
    func addr(s[]int) *int {
            return &s[2]
       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3a02002        mov     r2, #2
       10c28:       e1510002        cmp     r1, r2
       10c2c:       8a000000        bhi     10c34 <main.addr+0x34>
       10c30:       eb0035e6        bl      1e3d0 <runtime.panicindex>
       10c34:       e5900000        ldr     r0, [r0]
       10c38:       e2800008        add     r0, r0, #8
       10c3c:       e58d0014        str     r0, [sp, #20]
       10c40:       e49df004        pop     {pc}            ; (ldr pc, [sp], #4)
    
    after
    
    func addr(s[]int) *int {
            return &s[2]
       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3510002        cmp     r1, #2
       10c28:       8a000000        bhi     10c30 <main.addr+0x30>
       10c2c:       eb0035e6        bl      1e3cc <runtime.panicindex>
       10c30:       e5900000        ldr     r0, [r0]
       10c34:       e2800008        add     r0, r0, #8
       10c38:       e58d0014        str     r0, [sp, #20]
       10c3c:       e49df004        pop     {pc}            ; (ldr pc, [sp], #4)
    
    Also, relax gcmp restriction that 2nd operand must be a register. A followup
    CL will address the remaining TODO items.
    
    R=rsc, remyoudompheng, minux.ma
    CC=golang-dev
    https://golang.org/cl/6620064

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

https://github.com/golang/go/commit/01ddc8bd9ae903aea203dfe927bb072fe6bce24a

元コミット内容

commit 01ddc8bd9ae903aea203dfe927bb072fe6bce24a
Author: Dave Cheney <dave@cheney.net>
Date:   Sun Oct 7 11:37:14 2012 +1100

    cmd/5g: avoid temporary in slice bounds check
    
    before
    
    func addr(s[]int) *int {
            return &s[2]
       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3a02002        mov     r2, #2
       10c28:       e1510002        cmp     r1, r2
       10c2c:       8a000000        bhi     10c34 <main.addr+0x34>
       10c30:       eb0035e6        bl      1e3d0 <runtime.panicindex>
       10c34:       e5900000        ldr     r0, [r0]
       10c38:       e2800008        add     r0, r0, #8
       10c3c:       e58d0014        str     r0, [sp, #20]
       10c40:       e49df004        pop     {pc}            ; (ldr pc, [sp], #4)
    
    after
    
    func addr(s[]int) *int {
            return &s[2]
       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3510002        cmp     r1, #2
       10c28:       8a000000        bhi     10c30 <main.addr+0x30>
       10c2c:       eb0035e6        bl      1e3cc <runtime.panicindex>
       10c30:       e5900000        ldr     r0, [r0]
       10c34:       e2800008        add     r0, r0, #8
       10c38:       e58d0014        str     r0, [sp, #20]
       10c3c:       e49df004        pop     {pc}            ; (ldr pc, [sp], #4)
    
    Also, relax gcmp restriction that 2nd operand must be a register. A followup
    CL will address the remaining TODO items.
    
    R=rsc, remyoudompheng, minux.ma
    CC=golang-dev
    https://golang.org/cl/6620064

変更の背景

この変更の主な背景は、Goプログラムの実行効率の向上と、生成されるバイナリサイズの削減です。Go言語は、メモリ安全性を確保するために、スライスへのアクセス時に自動的に境界チェックを行います。これは非常に重要な機能ですが、その実装方法によってはオーバーヘッドが生じる可能性があります。

このコミット以前のGoコンパイラ（cmd/5g）は、スライスの境界チェックを行う際に、比較対象となる定数（この場合はインデックス2）を一時的なレジスタにロードしてから比較を行っていました。これは、ARMアーキテクチャの特定の命令セットの制約や、コンパイラのコード生成ロジックに起因する可能性があります。

しかし、多くのARM命令セットでは、レジスタと即値（定数）を直接比較する命令が存在します。このコミットは、この直接比較命令を活用することで、不要な一時レジスタへのロード命令（mov命令）を削除し、より効率的なアセンブリコードを生成することを目指しています。

具体的には、以下の点が改善の動機となっています。

  1. 性能向上: 不要な命令の削除により、CPUサイクルが削減され、プログラムの実行速度がわずかに向上します。特に、ループ内で頻繁にスライスアクセスが行われる場合、この最適化は累積的な効果をもたらします。
  2. コードサイズ削減: 命令数が減ることで、生成されるバイナリのサイズが小さくなります。これは、組み込みシステムやリソースが限られた環境でのデプロイにおいて特に重要です。
  3. コンパイラの洗練: コンパイラがより効率的なコードを生成できるようになることで、Go言語全体のパフォーマンス特性が向上します。

また、gcmp関数の制約緩和は、コンパイラ内部のコード生成ロジックの柔軟性を高め、将来的な最適化や異なる命令セットへの対応を容易にするための布石と考えられます。

前提知識の解説

1. Go言語のスライスと境界チェック

Go言語のスライスは、配列を抽象化したもので、長さと容量を持つ動的なデータ構造です。スライスにインデックスでアクセスする際（例: s[i]）、Goランタイムは自動的にiがスライスの有効な範囲内にあるか（0 <= i < len(s)）をチェックします。このチェックを境界チェック (bounds check) と呼びます。

  • 目的: 境界チェックは、C/C++のような言語で発生しがちなバッファオーバーフローや、未定義のメモリ領域へのアクセスといったセキュリティ脆弱性や実行時エラーを防ぐために不可欠です。
  • オーバーヘッド: 境界チェックは実行時に行われるため、わずかながらパフォーマンスのオーバーヘッドを伴います。Goコンパイラは、可能な限り境界チェックを省略する（境界チェック除去 (bounds check elimination)）最適化を行いますが、このコミットのように、除去できない場合のコード生成効率も重要です。

2. ARMアセンブリ言語の基礎

このコミットで示されているアセンブリコードは、ARMアーキテクチャのものです。ARMは、モバイルデバイスや組み込みシステムで広く使用されているRISC（Reduced Instruction Set Computer）アーキテクチャです。

  • レジスタ: ARMプロセッサは、データを一時的に保持するための汎用レジスタ（r0, r1, r2など）を持っています。spはスタックポインタ、pcはプログラムカウンタです。
  • 命令の例:
    • add Rd, Rn, #imm: Rnレジスタの値に即値immを加算し、結果をRdレジスタに格納します。
    • ldr Rd, [Rn, #imm]: Rnレジスタの値に即値immを加算したアドレスからメモリの値をロードし、Rdレジスタに格納します。
    • mov Rd, #imm: 即値immをRdレジスタに移動します。
    • cmp Rn, Rm / cmp Rn, #imm: Rnレジスタの値とRmレジスタの値、またはRnレジスタの値と即値immを比較し、ステータスレジスタのフラグを設定します。
    • bhi label: 比較結果が「より大きい (Higher)」であれば、labelに分岐します。
    • bl function: functionを呼び出し、戻りアドレスをリンクレジスタ（lr）に保存します。
    • pop {reg_list}: スタックからレジスタリストに値をポップします。pop {pc}は、スタックからpcに値をロードし、関数から戻る際に使用されます。
  • 即値 (Immediate Value): 命令に直接埋め込まれる定数です。ARMでは、特定の範囲の即値しか直接命令に含めることができません。

3. コンパイラのコード生成と最適化

コンパイラは、高水準言語（Go）のソースコードを、プロセッサが直接実行できる機械語（アセンブリコード）に変換します。この変換プロセスには、様々な最適化が含まれます。

  • 中間表現 (IR): 多くのコンパイラは、ソースコードを直接機械語に変換するのではなく、まず中間表現に変換します。これにより、最適化が容易になり、異なるアーキテクチャへの対応も柔軟になります。
  • レジスタ割り当て (Register Allocation): 変数や一時的な値をCPUのレジスタに割り当てるプロセスです。レジスタはメモリよりも高速なため、効率的なレジスタ割り当てはパフォーマンスに大きく影響します。
  • 命令選択 (Instruction Selection): 中間表現の操作を、ターゲットアーキテクチャの特定のアセンブリ命令にマッピングするプロセスです。このコミットは、より適切な命令選択を行うことで最適化を実現しています。
  • コード生成 (Code Generation): 最適化された中間表現から最終的なアセンブリコードを生成する段階です。

4. cmd/5g

cmd/5gは、Go言語のツールチェーンの一部であり、ARMアーキテクチャ（具体的にはARMv5/ARMv6）向けのGoコンパイラです。Goのコンパイラは、ターゲットアーキテクチャごとに異なるバイナリ（例: 5g for ARM, 6g for amd64, 8g for 386）が存在していました。現在では、go buildコマンドが自動的に適切なコンパイラを選択するため、ユーザーが直接これらの名前を意識することは少なくなっています。

技術的詳細

このコミットの核心は、Goコンパイラcmd/5gがスライス境界チェックのために生成するARMアセンブリコードの改善にあります。

変更前のアセンブリコード (before)

       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3a02002        mov     r2, #2  ; 定数2をr2レジスタに移動
       10c28:       e1510002        cmp     r1, r2  ; r1（スライス長）とr2（定数2）を比較
       10c2c:       8a000000        bhi     10c34 <main.addr+0x34>
       10c30:       eb0035e6        bl      1e3d0 <runtime.panicindex>

このコードでは、スライスのインデックス2が有効範囲内にあるかを確認するために、スライスの長さ（r1にロードされている）と定数2を比較しています。注目すべきは、定数2を比較に使う前に、mov r2, #2という命令で一時的にr2レジスタにロードしている点です。その後、cmp r1, r2でレジスタ間の比較を行っています。

変更後のアセンブリコード (after)

       10c1c:       e28d0008        add     r0, sp, #8
       10c20:       e5901004        ldr     r1, [r0, #4]
       10c24:       e3510002        cmp     r1, #2  ; r1（スライス長）と即値2を直接比較
       10c28:       8a000000        bhi     10c30 <main.addr+0x30>
       10c2c:       eb0035e6        bl      1e3cc <runtime.panicindex>

変更後では、e3a02002 mov r2, #2という命令が削除され、代わりにe3510002 cmp r1, #2という命令が使用されています。これは、r1レジスタの値と即値2を直接比較する命令です。

最適化の効果

  • 命令数の削減: mov命令が1つ削除されたことで、境界チェックに必要な命令が1つ減りました。これにより、コードサイズが小さくなり、実行時の命令フェッチやデコードのオーバーヘッドが減少します。
  • レジスタ使用の最適化: 一時レジスタr2が不要になったことで、レジスタの競合が減り、コンパイラが他の用途にレジスタを割り当てやすくなる可能性があります。
  • パフォーマンス向上: 命令数の削減は、わずかながら実行速度の向上に寄与します。特に、このような基本的な操作が頻繁に行われる場合、その効果は無視できません。

gcmp関数の制約緩和

コミットメッセージには、「gcmp restriction that 2nd operand must be a register」が緩和されたとあります。gcmpはGoコンパイラ内部の関数で、比較命令（cmp）を生成する役割を担っています。

変更前は、gcmpの第2オペランド（比較対象）が必ずレジスタであるという制約がありました。そのため、定数と比較する場合でも、一度定数をレジスタにロードする必要がありました。

このコミットでは、src/cmd/5g/gsubr.cのgcmp関数内のチェックが変更され、第2オペランドがレジスタでなくても比較命令を生成できるようになりました。これにより、コンパイラは即値比較命令（cmp Rn, #imm）を直接生成できるようになり、上記の最適化が可能になりました。

この変更は、コンパイラのコード生成バックエンドにおける柔軟性を高め、より効率的なアセンブリコード生成を可能にする重要な改善です。

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

このコミットによるコードの変更は、主にGoコンパイラのARMバックエンド（cmd/5g）の以下の2つのファイルに集中しています。

  1. src/cmd/5g/cgen.c:

    • agen関数内で、スライス境界チェックに関連するコード生成ロジックが変更されています。
    • 変更前は、比較対象の定数（v）を一時的なNode n5に割り当て、gmoveでレジスタに移動し、その後gcmpを呼び出していました。
    • 変更後では、Node n5の宣言と関連するregalloc、gmove、regfreeの呼び出しが削除されています。
    • gcmpの呼び出しが、&n4（スライス長が格納されたレジスタ）と&n2（定数）を直接引数として取るように変更されています。
    --- a/src/cmd/5g/cgen.c
+++ b/src/cmd/5g/cgen.c
@@ -573,7 +573,7 @@ void
 agen(Node *n, Node *res)
 {
 	Node *nl, *nr;
-	Node n1, n2, n3, n4, n5, tmp;
+	Node n1, n2, n3, n4, tmp;
 	Prog *p1, *p2;
 	uint32 w;
 	uint64 v;
@@ -715,11 +715,8 @@ agen(Node *n, Node *res)
 					regalloc(&n4, n1.type, N);
 					cgen(&n1, &n4);
 					nodconst(&n2, types[TUINT32], v);
-					regalloc(&n5, n2.type, N);
-					gmove(&n2, &n5);
-					gcmp(optoas(OCMP, types[TUINT32]), &n4, &n5);
+					gcmp(optoas(OCMP, types[TUINT32]), &n4, &n2);
 					regfree(&n4);
-					regfree(&n5);
 					p1 = gbranch(optoas(OGT, types[TUINT32]), T, +1);
 					ginscall(panicindex, 0);
 					patch(p1, pc);

  2. src/cmd/5g/gsubr.c:

    • gcmp関数の引数チェックが緩和されています。
    • 変更前は、lhsとrhsの両方がレジスタである必要があるという厳格なチェックがありました。
    • 変更後では、rhsがレジスタである必要がなくなり、lhsがレジスタであれば比較命令を生成できるようになりました。これにより、gcmpはレジスタと即値の比較も直接扱えるようになります。
    --- a/src/cmd/5g/gsubr.c
+++ b/src/cmd/5g/gsubr.c
@@ -1103,7 +1103,7 @@ gcmp(int as, Node *lhs, Node *rhs)
 {
 	Prog *p;
 
-	if(lhs->op != OREGISTER || rhs->op != OREGISTER)
+	if(lhs->op != OREGISTER)
 		fatal("bad operands to gcmp: %O %O", lhs->op, rhs->op);
 
 	p = gins(as, rhs, N);

コアとなるコードの解説

src/cmd/5g/cgen.c の変更

cgen.cは、Goコンパイラのコード生成フェーズの一部であり、抽象構文木（AST）のノードをターゲットアーキテクチャのアセンブリ命令に変換する役割を担っています。

agen関数は、アドレス生成（address generation）に関連するコードを生成します。スライス要素へのアクセス（例: s[2]）は、そのアドレスを計算し、その際に境界チェックを行う必要があります。

変更前のコードでは、スライスインデックス（この例では定数2）を比較対象として使用する際に、まずnodconst(&n2, types[TUINT32], v)で定数ノードn2を作成し、次にregalloc(&n5, n2.type, N)で一時レジスタn5を割り当て、gmove(&n2, &n5)で定数2をn5に移動していました。そして、gcmp(optoas(OCMP, types[TUINT32]), &n4, &n5)で、スライス長が格納されたレジスタn4と、定数2が格納された一時レジスタn5を比較していました。

この変更により、n5に関連する一連の操作（レジスタ割り当て、移動、解放）が削除されました。代わりに、gcmp関数が&n4と&n2を直接引数として受け取るようになりました。これは、gcmp関数自体が、レジスタと即値の比較を直接処理できるようになったためです。これにより、中間的なレジスタへの移動が不要になり、生成されるアセンブリコードからmov r2, #2のような命令が削除されます。

src/cmd/5g/gsubr.c の変更

gsubr.cは、GoコンパイラのARMバックエンドにおける汎用的なサブルーチン（general subroutines）を含んでいます。gcmp関数は、比較命令（CMP）を生成するためのヘルパー関数です。

変更前は、gcmp関数の冒頭に以下のチェックがありました。

if(lhs->op != OREGISTER || rhs->op != OREGISTER)
    fatal("bad operands to gcmp: %O %O", lhs->op, rhs->op);

これは、比較の左辺（lhs）と右辺（rhs）の両方がレジスタである場合にのみ、gcmpが比較命令を生成できることを意味していました。もしrhsがレジスタでない場合（例えば、即値ノードの場合）、コンパイラはエラーを発生させるか、あるいはcgen.cのように、明示的に即値をレジスタに移動するコードを生成する必要がありました。

このコミットでは、このチェックが以下のように変更されました。

if(lhs->op != OREGISTER)
    fatal("bad operands to gcmp: %O %O", lhs->op, rhs->op);

これにより、rhsがレジスタであるという制約が取り除かれました。つまり、gcmpは、lhsがレジスタであれば、rhsが即値であっても比較命令を生成できるようになりました。この変更が、cgen.cでの最適化（即値の直接比較）を可能にする基盤となっています。gcmp内部で、rhsが即値である場合は、CMP命令の即値形式（cmp Rn, #imm）が選択されるようになります。

これらの変更は、GoコンパイラがARMアーキテクチャにおいて、より効率的なコードを生成するための重要なステップであり、コンパイラの最適化能力の向上を示しています。

関連リンク

参考にした情報源リンク

  • Go言語の公式ドキュメント (スライス、コンパイラ)
  • ARMアーキテクチャのリファレンスマニュアル (ARM命令セット)
  • Goコンパイラのソースコード (特にsrc/cmd/5gディレクトリ)
  • Go言語の境界チェックに関するブログ記事や論文
  • コンパイラ最適化に関する一般的な情報