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

このコミットは、Go言語のARMアーキテクチャ向けコンパイラであるcmd/5gのpeephole最適化器（peep.c）において、以前無効化されていたいくつかの最適化を再有効化するものです。具体的には、EOR -1,x,y命令をより効率的なMVN x,y命令に変換する最適化と、冗長なMOVB命令のシーケンスを削除する最適化が対象となっています。これにより、生成されるARMアセンブリコードの効率が向上し、実行速度の改善やコードサイズの削減が期待されます。

コミット

commit 542dd8b9fba40e03ccdf1fac0a805b5b23ea3b8c
Author: Dave Cheney <dave@cheney.net>
Date:   Fri Oct 26 18:19:10 2012 +1100

    cmd/5g: peep.c: reactivate some optimisations
    
    Thanks to Minux and Remy for their advice.
    
    The EOR optimisation is applied to a few places in the stdlib.
    
    // hash/crc32/crc32.go
    func update(crc uint32, tab *Table, p []byte) uint32 {
            crc = ^crc
            for _, v := range p {
                    crc = tab[byte(crc)^v] ^ (crc >> 8)
            }
            return ^crc
    }\n    
    before:
    
    --- prog list "update" ---
    0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
    0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
    0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
    0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) EOR         $-1,R0,R5
    0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
    0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)
    
    after:
    
    --- prog list "update" ---
    0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
    0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
    0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
    0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MVN         R0,R5
    0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
    0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)
    
    After 5l has done its work,
    
            crc = ^crc
       3d710:       e59d0014        ldr     r0, [sp, #20]\n       3d714:       e3e0b000        mvn     fp, #0\n       3d718:       e020500b        eor     r5, r0, fp
    
    becomes
    
            crc = ^crc
       3d710:       e59d0014        ldr     r0, [sp, #20]\n       3d714:       e1e05000        mvn     r5, r0
    
    The MOVB optimisation has a small impact on the stdlib, in strconv
    and gzip.
    
    // GZIP (RFC 1952) is little-endian, unlike ZLIB (RFC 1950).\n    func put2(p []byte, v uint16) {
            p[0] = uint8(v >> 0)
            p[1] = uint8(v >> 8)
    }\n    
    before:
    
    --- prog list "put2" ---
    1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
    1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
    1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
    1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R0,R0
    1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
    1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
    1375 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1
    
    after:
    
    --- prog list "put2" ---
    1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
    1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
    1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
    1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
    1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
    1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1
    
    R=remyoudompheng, rsc, minux.ma
    CC=golang-dev
    https://golang.org/cl/6674048

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

https://github.com/golang/go/commit/542dd8b9fba40e03ccdf1fac0a805b5b23ea3b8c

元コミット内容

cmd/5g: peep.c: reactivate some optimisations

Thanks to Minux and Remy for their advice.

The EOR optimisation is applied to a few places in the stdlib.

// hash/crc32/crc32.go
func update(crc uint32, tab *Table, p []byte) uint32 {
        crc = ^crc
        for _, v := range p {
                crc = tab[byte(crc)^v] ^ (crc >> 8)
        }
        return ^crc
}

before:

--- prog list "update" ---
0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) EOR         $-1,R0,R5
0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)

after:

--- prog list "update" ---
0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MVN         R0,R5
0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)

After 5l has done its work,

        crc = ^crc
   3d710:       e59d0014        ldr     r0, [sp, #20]
   3d714:       e3e0b000        mvn     fp, #0
   3d718:       e020500b        eor     r5, r0, fp

becomes

        crc = ^crc
   3d710:       e59d0014        ldr     r0, [sp, #20]
   3d714:       e1e05000        mvn     r5, r0

The MOVB optimisation has a small impact on the stdlib, in strconv
and gzip.

// GZIP (RFC 1952) is little-endian, unlike ZLIB (RFC 1950).
func put2(p []byte, v uint16) {
        p[0] = uint8(v >> 0)
        p[1] = uint8(v >> 8)
}

before:

--- prog list "put2" ---
1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R0,R0
1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
1375 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1

after:

--- prog list "put2" ---
1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1

R=remyoudompheng, rsc, minux.ma
CC=golang-dev
https://golang.org/cl/6674048

変更の背景

このコミットの主な背景は、Go言語のARMアーキテクチャ向けコンパイラ（cmd/5g）が生成するアセンブリコードの効率を向上させることにあります。コンパイラが生成するコードは、人間が手書きするアセンブリコードほど最適化されていない場合があり、特に特定の命令シーケンスはより短く、より高速な代替命令に置き換えることが可能です。

過去に何らかの理由で無効化されていた（おそらく安定性やデバッグの容易さを優先したため）これらのpeephole最適化を再有効化することで、以下のメリットが期待されます。

パフォーマンスの向上: より効率的な命令シーケンスを使用することで、CPUサイクルを削減し、プログラムの実行速度を向上させます。
コードサイズの削減: 不要な命令や冗長な命令を削除することで、最終的なバイナリのサイズを小さくします。これは特に組み込みシステムやリソースが限られた環境で重要です。
コンパイラの成熟: コンパイラがより高度な最適化を実行できるようになることで、全体的な品質と信頼性が向上します。

コミットメッセージでMinuxとRemyへの感謝が述べられていることから、これらの最適化の再有効化にあたり、彼らからの助言やレビューがあったことが伺えます。これは、コンパイラの最適化が複雑であり、専門家の知見が不可欠であることを示唆しています。

前提知識の解説

1. Goコンパイラの構造（特に`cmd/5g`とバックエンド）

Go言語のコンパイラは、複数のステージを経てソースコードを実行可能なバイナリに変換します。大まかには以下のようになります。

フロントエンド: ソースコードの字句解析、構文解析、意味解析を行い、抽象構文木（AST）を生成します。
ミドルエンド（共通バックエンド）: ASTを中間表現（IR）に変換し、アーキテクチャに依存しない最適化（インライン化、デッドコード削除など）を行います。
バックエンド（コード生成器）: 中間表現を特定のターゲットアーキテクチャ（x86, ARMなど）のアセンブリコードに変換します。この段階で、レジスタ割り当てや命令スケジューリングなどのアーキテクチャ固有の最適化が行われます。

このコミットで言及されているcmd/5gは、Goの初期のコンパイラ群の一部で、ARMアーキテクチャ（具体的にはARMv5/v6/v7）をターゲットとしていました。Go 1.5以降、コンパイラはGo言語自体で書かれ、go tool compileコマンドに統合されましたが、このコミットが作成された2012年当時は、各アーキテクチャごとに5g（ARM）、6g（x86-64）、8g（x86）といった独立したコンパイラが存在していました。

peep.cは、この5gコンパイラのバックエンドの一部であり、生成されたアセンブリコードに対してpeephole最適化を適用する役割を担っています。

2. Peephole最適化とは

Peephole最適化は、コンパイラのコード生成フェーズの後に適用される、比較的小規模な最適化手法です。その名前が示す通り、コンパイラが生成したアセンブリコードの「小さな窓（peephole）」、つまり数命令のシーケンスを検査し、より効率的な代替シーケンスに置き換えることで機能します。

特徴としては：

局所性: ごく少数の命令（通常2〜5命令）のみを考慮します。
パターンマッチング: 特定の非効率な命令パターンを認識し、既知のより効率的なパターンに置き換えます。
シンプルさ: 実装が比較的容易であり、コンパイラの他の部分に大きな影響を与えずに適用できます。
効果: 小規模ながらも、頻繁に現れるパターンに対して適用されるため、全体的なコード品質とパフォーマンスに有意な影響を与えることがあります。

一般的なpeephole最適化の例としては、冗長なロード/ストアの削除、定数伝播、強度の削減（例: x * 2をx << 1に変換）、そして本コミットで扱われるような命令の置き換えなどがあります。

3. ARMアーキテクチャの基本的なアセンブリ命令

ARM（Advanced RISC Machine）は、モバイルデバイスや組み込みシステムで広く使用されているRISC（Reduced Instruction Set Computer）アーキテクチャです。このコミットで登場する主要なARMアセンブリ命令について解説します。

EOR (Exclusive OR): 論理XOR演算を実行します。EOR Rd, Rn, Operand2 の形式で、RnとOperand2のビットごとのXOR結果をRdに格納します。
MVN (Move Not): オペランドのビットごとのNOT（1の補数）を計算し、結果をデスティネーションレジスタに移動します。MVN Rd, Operand2 の形式で、Operand2のNOT結果をRdに格納します。これは、EOR命令で-1（すべてのビットが1）とXORするのと等価です。
MOV (Move): レジスタまたは即値の値を別のレジスタに移動します。
MOVW (Move Word): 32ビットのワード（4バイト）を移動します。
MOVB (Move Byte): 8ビットのバイトを移動します。
MOVH (Move Halfword): 16ビットのハーフワード（2バイト）を移動します。
MOVHU (Move Halfword Unsigned): 符号なし16ビットのハーフワードを移動します。

4. ビット演算と補数（`^`演算子、-1の表現）

Go言語の^演算子は、整数型に対してビットごとのNOT（1の補数）を計算します。例えば、^crcはcrcのすべてのビットを反転させます。

2進数において、すべてのビットが1である値は、符号なし整数では最大値を表し、符号付き整数では-1を表すことがあります（2の補数表現の場合）。ARMアセンブリでは、即値-1はすべてのビットが1の32ビット値（0xFFFFFFFF）として扱われます。

したがって、EOR $-1, R0, R5という命令は、レジスタR0の内容と即値-1（0xFFFFFFFF）のビットごとのXORを取り、その結果をレジスタR5に格納することを意味します。任意のビット列Xとすべてのビットが1のビット列FとのXOR演算は、Xの各ビットを反転させることになります（X XOR F = NOT X）。これはまさにMVN命令が実行する操作と同じです。

技術的詳細

このコミットで再有効化された最適化は、主に以下の2つです。

1. `EOR -1,x,y => MVN x,y` 最適化

目的: EOR命令と即値-1の組み合わせを、より効率的な単一のMVN命令に置き換えることです。
詳細:
- Go言語のコードでcrc = ^crcのようにビットごとのNOT演算が行われると、コンパイラはこれをARMアセンブリのEOR $-1, Rsrc, Rdestという形式に変換することがあります。
- EOR命令は通常、2つのオペランドに対してXOR演算を実行します。しかし、第2オペランドが-1（すべてのビットが1）である場合、これは実質的に第1オペランドのビットを反転させる操作になります。
- ARMアーキテクチャには、この「ビット反転」操作を直接実行するMVN（Move Not）命令が存在します。MVN Rdest, Rsrcは、Rsrcのビットを反転させてRdestに格納します。
- MVN命令は、EOR命令よりもシンプルであり、多くの場合、より少ないサイクルで実行できるか、あるいは命令デコードの観点からより効率的です。また、命令のエンコーディングも異なるため、コードサイズにも影響を与える可能性があります。
- この最適化は、peep.c内でAEOR（ARM EOR命令）を検出し、そのソースオペランドが定数-1である場合に、命令の種類をAMVN（ARM MVN命令）に変更し、オペランドの形式を調整することで実現されます。
コミットメッセージの例: hash/crc32/crc32.goのupdate関数におけるcrc = ^crcのGoコードが、最適化前はEOR $-1,R0,R5というアセンブリ命令に変換されていましたが、最適化後はMVN R0,R5というより効率的な命令に置き換えられています。さらに、5l（Goリンカ）が最終的なARM機械語を生成する段階でも、この最適化が適用され、よりコンパクトなコードが生成されることが示されています。

2. 冗長な`MOVB`命令の最適化

目的: MOVB x,R; MOVB R,Rのような冗長なムーブ命令のシーケンスを削除することです。
詳細:
- コンパイラがコードを生成する過程で、一時的なレジスタへのムーブや、すでにレジスタにある値を再度同じレジスタにムーブするような、意味のない命令シーケンスが生成されることがあります。
- 例えば、MOVB R0, R1（R0の内容をR1に移動）の直後にMOVB R1, R1（R1の内容をR1に移動）のような命令が続く場合、後者の命令は完全に冗長であり、削除してもプログラムの動作に影響はありません。
- この最適化は、peep.c内でAMOVB, AMOVBU, AMOVH, AMOVHU（バイトまたはハーフワードのムーブ命令）を検出し、その直後に続く命令が同じレジスタへの冗長なムーブである場合に、その冗長な命令を削除（excise）することで実現されます。
- これにより、命令数が削減され、コードサイズが小さくなり、命令フェッチやデコードのオーバーヘッドが減少するため、実行効率が向上します。
コミットメッセージの例: compress/gzip/gzip.goのput2関数が例として挙げられていますが、コミットメッセージに示されているbeforeとafterのアセンブリコードは同一です。これは、この最適化が常に目に見える形でアセンブリコードを劇的に変更するわけではないこと、あるいは例示が簡略化されていることを示唆しています。しかし、コミットメッセージには「The MOVB optimisation has a small impact on the stdlib, in strconv and gzip.」と明記されており、実際に標準ライブラリのstrconvやgzipパッケージで効果があることが示されています。

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

変更はsrc/cmd/5g/peep.cファイルに集中しています。

--- a/src/cmd/5g/peep.c
+++ b/src/cmd/5g/peep.c
@@ -133,26 +133,24 @@ loop1:
 	if(t)
 		goto loop1;
 
-return;
-
-#ifdef	NOTDEF
 	for(r=firstr; r!=R; r=r->link) {
 		p = r->prog;
 		switch(p->as) {
-//		case AEOR:
-//			/*
-//			 * EOR -1,x,y => MVN x,y
-//			 *///
-//			if(isdconst(&p->from) && p->from.offset == -1) {
-//				p->as = AMVN;
-//				p->from.type = D_REG;
-//				if(p->reg != NREG)
-//					p->from.reg = p->reg;
-//				else
-//					p->from.reg = p->to.reg;
-//				p->reg = NREG;
-//			}
-//			break;
+		case AEOR:
+			/*
+			 * EOR -1,x,y => MVN x,y
+			 */
+			if(isdconst(&p->from) && p->from.offset == -1) {
+				p->as = AMVN;
+				p->from.type = D_REG;
+				if(p->reg != NREG)
+					p->from.reg = p->reg;
+				else
+					p->from.reg = p->to.reg;
+				p->reg = NREG;
+			}
+			break;
 
 		case AMOVH:
 		case AMOVHU:
@@ -161,6 +159,7 @@ return;
 			/*
 			 * look for MOVB x,R; MOVB R,R
 			 */
+			r1 = r->link;
 			if(p->to.type != D_REG)
 				break;
 			if(r1 == R)
@@ -175,8 +174,8 @@ return;
 			excise(r1);
 			break;
 		}
-\t\tr1 = r->link;
 	}\n+#ifdef	NOTDEF
 
 //	for(r=firstr; r!=R; r=r->link) {
 //		p = r->prog;

コアとなるコードの解説

peep.cは、GoコンパイラのARMバックエンドにおけるpeephole最適化のロジックを実装しています。上記のdiffは、主に2つの最適化ブロックのコメントアウトを解除し、一部のコードを調整しています。

AEOR (EOR命令) の最適化ブロック:
- 以前は//と#ifdef NOTDEFでコメントアウトされていたcase AEOR:ブロックが再有効化されています。
- このブロックは、現在の命令pがAEOR（ARMのEOR命令）である場合に処理を行います。
- if(isdconst(&p->from) && p->from.offset == -1): これは、EOR命令のソースオペランド（p->from）が定数であり、その値が-1であるかどうかをチェックしています。
- もし条件が真であれば、以下の変換が行われます。
  - p->as = AMVN;: 命令の種類をAMVN（MVN命令）に変更します。
  - p->from.type = D_REG;: ソースオペランドのタイプをレジスタ（D_REG）に設定します。これは、MVN命令が通常、レジスタをオペランドとして取るためです。
  - if(p->reg != NREG) p->from.reg = p->reg; else p->from.reg = p->to.reg;: MVN命令のソースレジスタを決定します。元のEOR命令の第2オペランド（p->reg）が存在すればそれを使用し、そうでなければデスティネーションレジスタ（p->to.reg）を使用します。これは、EOR -1, Rsrc, RdestがMVN Rsrc, Rdestに変換されることを意味します。
  - p->reg = NREG;: EOR命令の第2オペランドレジスタ（p->reg）を無効化します。MVNは単一のソースオペランドしか持たないためです。
- このロジックにより、EOR $-1, Rsrc, Rdestという2オペランド命令が、より効率的なMVN Rsrc, Rdestという1オペランド命令に変換されます。
AMOVH, AMOVHU, AMOVB, AMOVBU (ムーブ命令) の最適化ブロック:
- このブロックも以前はコメントアウトされていた部分が再有効化されています。
- case AMOVH:などから始まるこのブロックは、ハーフワードまたはバイトのムーブ命令を処理します。
- r1 = r->link;: 現在の命令rの次の命令をr1に取得します。この行は、以前はループの最後にありましたが、この最適化ブロックの先頭に移動されています。これは、この最適化が現在の命令とその次の命令のペアを検査するため、r1が常に有効な次の命令を指すようにするためです。
- if(p->to.type != D_REG) break;: 現在のムーブ命令のデスティネーションがレジスタでない場合は、この最適化を適用しません。
- if(r1 == R) break;: 次の命令が存在しない場合は処理を中断します。
- if(r1->as != p->as) break;: 次の命令の種類が現在の命令と同じでない場合は中断します。
- if(r1->from.type != D_REG || r1->from.reg != p->to.reg) break;: 次の命令のソースオペランドがレジスタであり、かつそのレジスタが現在の命令のデスティネーションレジスタと同じであるかをチェックします。
- if(r1->to.type != D_REG || r1->to.reg != p->to.reg) break;: 次の命令のデスティネーションオペランドがレジスタであり、かつそのレジスタが現在の命令のデスティネーションレジスタと同じであるかをチェックします。
- これらの条件がすべて満たされる場合、MOVB x,R; MOVB R,Rのような冗長なパターンが検出されたことになります。
- excise(r1);: 冗長な次の命令r1を命令リストから削除します。

これらの変更により、peep.cはより積極的なpeephole最適化を実行し、Goコンパイラが生成するARMアセンブリコードの品質を向上させます。

参考にした情報源リンク

コミットメッセージに記載されているGoのChange List: https://golang.org/cl/6674048
Go言語のコンパイラに関する一般的な知識
ARMアセンブリ命令に関する一般的な知識
Peephole最適化に関する一般的な知識
Go言語の^演算子に関する知識
cmd/5gが古いARMコンパイラであるという歴史的背景に関する知識
isdconstなどのコンパイラ内部関数に関する一般的な推測（具体的なドキュメントは公開されていないため）
excise関数が命令を削除する役割を持つという一般的なコンパイラ最適化の知識

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

コミット

commit 542dd8b9fba40e03ccdf1fac0a805b5b23ea3b8c
Author: Dave Cheney <dave@cheney.net>
Date:   Fri Oct 26 18:19:10 2012 +1100

    cmd/5g: peep.c: reactivate some optimisations
    
    Thanks to Minux and Remy for their advice.
    
    The EOR optimisation is applied to a few places in the stdlib.
    
    // hash/crc32/crc32.go
    func update(crc uint32, tab *Table, p []byte) uint32 {
            crc = ^crc
            for _, v := range p {
                    crc = tab[byte(crc)^v] ^ (crc >> 8)
            }
            return ^crc
    }
    
    before:
    
    --- prog list "update" ---
    0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
    0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
    0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
    0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) EOR         $-1,R0,R5
    0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
    0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)
    
    after:
    
    --- prog list "update" ---
    0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
    0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
    0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
    0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MVN         R0,R5
    0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
    0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)
    
    After 5l has done its work,
    
            crc = ^crc
       3d710:       e59d0014        ldr     r0, [sp, #20]
       3d714:       e3e0b000        mvn     fp, #0
       3d718:       e020500b        eor     r5, r0, fp
    
    becomes
    
            crc = ^crc
       3d710:       e59d0014        ldr     r0, [sp, #20]
       3d714:       e1e05000        mvn     r5, r0
    
    The MOVB optimisation has a small impact on the stdlib, in strconv
    and gzip.
    
    // GZIP (RFC 1952) is little-endian, unlike ZLIB (RFC 1950).
    func put2(p []byte, v uint16) {
            p[0] = uint8(v >> 0)
            p[1] = uint8(v >> 8)
    }
    
    before:
    
    --- prog list "put2" ---
    1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
    1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
    1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
    1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R0,R0
    1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
    1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
    1375 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1
    
    after:
    
    --- prog list "put2" ---
    1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
    1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
    1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
    1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
    1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
    1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1
    
    R=remyoudompheng, rsc, minux.ma
    CC=golang-dev
    https://golang.org/cl/6674048

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

https://github.com/golang/go/commit/542dd8b9fba40e03ccdf1fac0a805b5b23ea3b8c

元コミット内容

cmd/5g: peep.c: reactivate some optimisations

Thanks to Minux and Remy for their advice.

The EOR optimisation is applied to a few places in the stdlib.

// hash/crc32/crc32.go
func update(crc uint32, tab *Table, p []byte) uint32 {
        crc = ^crc
        for _, v := range p {
                crc = tab[byte(crc)^v] ^ (crc >> 8)
        }
        return ^crc
}

before:

--- prog list "update" ---
0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) EOR         $-1,R0,R5
0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)

after:

--- prog list "update" ---
0164 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) TEXT        update+0(SB),$12-24
0165 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:101) MOVW        tab+4(FP),R8
0166 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MOVW        crc+0(FP),R0
0167 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:102) MVN         R0,R5
0168 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        p+8(FP),R0
0169 (/home/dfc/go/src/pkg/hash/crc32/crc32.go:103) MOVW        R0,autotmp_0019+-12(SP)

After 5l has done its work,

        crc = ^crc
   3d710:       e59d0014        ldr     r0, [sp, #20]
   3d714:       e3e0b000        mvn     fp, #0
   3d718:       e020500b        eor     r5, r0, fp

becomes

        crc = ^crc
   3d710:       e59d0014        ldr     r0, [sp, #20]
   3d714:       e1e05000        mvn     r5, r0

The MOVB optimisation has a small impact on the stdlib, in strconv
and gzip.

// GZIP (RFC 1952) is little-endian, unlike ZLIB (RFC 1950).
func put2(p []byte, v uint16) {
        p[0] = uint8(v >> 0)
        p[1] = uint8(v >> 8)
}

before:

--- prog list "put2" ---
1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R0,R0
1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
1375 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1

after:

--- prog list "put2" ---
1369 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) TEXT       put2+0(SB),$0-16
1370 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:76) MOVHU      v+12(FP),R4
1371 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVHU      R4,R0
1372 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R0,R1
1373 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVBU      R1,R3
1374 (/home/dfc/go/src/pkg/compress/gzip/gzip.go:77) MOVW       $p+0(FP),R1

R=remyoudompheng, rsc, minux.ma
CC=golang-dev
https://golang.org/cl/6674048

変更の背景

パフォーマンスの向上: より効率的な命令シーケンスを使用することで、CPUサイクルを削減し、プログラムの実行速度を向上させます。
コードサイズの削減: 不要な命令や冗長な命令を削除することで、最終的なバイナリのサイズを小さくします。これは特に組み込みシステムやリソースが限られた環境で重要です。
コンパイラの成熟: コンパイラがより高度な最適化を実行できるようになることで、全体的な品質と信頼性が向上します。

前提知識の解説

1. Goコンパイラの構造（特に`cmd/5g`とバックエンド）

Go言語のコンパイラは、複数のステージを経てソースコードを実行可能なバイナリに変換します。大まかには以下のようになります。

フロントエンド: ソースコードの字句解析、構文解析、意味解析を行い、抽象構文木（AST）を生成します。
ミドルエンド（共通バックエンド）: ASTを中間表現（IR）に変換し、アーキテクチャに依存しない最適化（インライン化、デッドコード削除など）を行います。
バックエンド（コード生成器）: 中間表現を特定のターゲットアーキテクチャ（x86, ARMなど）のアセンブリコードに変換します。この段階で、レジスタ割り当てや命令スケジューリングなどのアーキテクチャ固有の最適化が行われます。

peep.cは、この5gコンパイラのバックエンドの一部であり、生成されたアセンブリコードに対してpeephole最適化を適用する役割を担っています。

2. Peephole最適化とは

特徴としては：

局所性: ごく少数の命令（通常2〜5命令）のみを考慮します。
パターンマッチング: 特定の非効率な命令パターンを認識し、既知のより効率的なパターンに置き換えます。
シンプルさ: 実装が比較的容易であり、コンパイラの他の部分に大きな影響を与えずに適用できます。
効果: 小規模ながらも、頻繁に現れるパターンに対して適用されるため、全体的なコード品質とパフォーマンスに有意な影響を与えることがあります。

3. ARMアーキテクチャの基本的なアセンブリ命令

EOR (Exclusive OR): 論理XOR演算を実行します。EOR Rd, Rn, Operand2 の形式で、RnとOperand2のビットごとのXOR結果をRdに格納します。
MVN (Move Not): オペランドのビットごとのNOT（1の補数）を計算し、結果をデスティネーションレジスタに移動します。MVN Rd, Operand2 の形式で、Operand2のNOT結果をRdに格納します。これは、EOR命令で-1（すべてのビットが1）とXORするのと等価です。
MOV (Move): レジスタまたは即値の値を別のレジスタに移動します。
MOVW (Move Word): 32ビットのワード（4バイト）を移動します。
MOVB (Move Byte): 8ビットのバイトを移動します。
MOVH (Move Halfword): 16ビットのハーフワード（2バイト）を移動します。
MOVHU (Move Halfword Unsigned): 符号なし16ビットのハーフワードを移動します。

目的: EOR命令と即値-1の組み合わせを、より効率的な単一のMVN命令に置き換えることです。
詳細:
- Go言語のコードでcrc = ^crcのようにビットごとのNOT演算が行われると、コンパイラはこれをARMアセンブリのEOR $-1, Rsrc, Rdestという形式に変換することがあります。
- EOR命令は通常、2つのオペランドに対してXOR演算を実行します。しかし、第2オペランドが-1（すべてのビットが1）である場合、これは実質的に第1オペランドのビットを反転させる操作になります。
- ARMアーキテクチャには、この「ビット反転」操作を直接実行するMVN（Move Not）命令が存在します。MVN Rdest, Rsrcは、Rsrcのビットを反転させてRdestに格納します。
- MVN命令は、EOR命令よりもシンプルであり、多くの場合、より少ないサイクルで実行できるか、あるいは命令デコードの観点からより効率的です。また、命令のエンコーディングも異なるため、コードサイズにも影響を与える可能性があります。
- この最適化は、peep.c内でAEOR（ARM EOR命令）を検出し、そのソースオペランドが定数-1である場合に、命令の種類をAMVN（ARM MVN命令）に変更し、オペランドの形式を調整することで実現されます。
コミットメッセージの例: hash/crc32/crc32.goのupdate関数におけるcrc = ^crcのGoコードが、最適化前はEOR $-1,R0,R5というアセンブリ命令に変換されていましたが、最適化後はMVN R0,R5というより効率的な命令に置き換えられています。さらに、5l（Goリンカ）が最終的なARM機械語を生成する段階でも、この最適化が適用され、よりコンパクトなコードが生成されることが示されています。

2. 冗長な`MOVB`命令の最適化

目的: MOVB x,R; MOVB R,Rのような冗長なムーブ命令のシーケンスを削除することです。
詳細:
- コンパイラがコードを生成する過程で、一時的なレジスタへのムーブや、すでにレジスタにある値を再度同じレジスタにムーブするような、意味のない命令シーケンスが生成されることがあります。
- 例えば、MOVB R0, R1（R0の内容をR1に移動）の直後にMOVB R1, R1（R1の内容をR1に移動）のような命令が続く場合、後者の命令は完全に冗長であり、削除してもプログラムの動作に影響はありません。
- この最適化は、peep.c内でAMOVB, AMOVBU, AMOVH, AMOVHU（バイトまたはハーフワードのムーブ命令）を検出し、その直後に続く命令が同じレジスタへの冗長なムーブである場合に、その冗長な命令を削除（excise）することで実現されます。
- これにより、命令数が削減され、コードサイズが小さくなり、命令フェッチやデコードのオーバーヘッドが減少するため、実行効率が向上します。
コミットメッセージの例: compress/gzip/gzip.goのput2関数が例として挙げられていますが、コミットメッセージに示されているbeforeとafterのアセンブリコードは同一です。これは、この最適化が常に目に見える形でアセンブリコードを劇的に変更するわけではないこと、あるいは例示が簡略化されていることを示唆しています。しかし、コミットメッセージには「The MOVB optimisation has a small impact on the stdlib, in strconv and gzip.」と明記されており、実際に標準ライブラリのstrconvやgzipパッケージで効果があることが示されています。

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

変更はsrc/cmd/5g/peep.cファイルに集中しています。

--- a/src/cmd/5g/peep.c
+++ b/src/cmd/5g/peep.c
@@ -133,26 +133,24 @@ loop1:
 	if(t)
 		goto loop1;
 
-return;
-
-#ifdef	NOTDEF
 	for(r=firstr; r!=R; r=r->link) {
 		p = r->prog;
 		switch(p->as) {
-//		case AEOR:
-//			/*
-//			 * EOR -1,x,y => MVN x,y
-//			 *///
-//			if(isdconst(&p->from) && p->from.offset == -1) {
-//				p->as = AMVN;
-//				p->from.type = D_REG;
-//				if(p->reg != NREG)
-//					p->from.reg = p->reg;
-//				else
-//					p->from.reg = p->to.reg;
-//				p->reg = NREG;
-//			}
-//			break;
+		case AEOR:
+			/*
+			 * EOR -1,x,y => MVN x,y
+			 */
+			if(isdconst(&p->from) && p->from.offset == -1) {
+				p->as = AMVN;
+				p->from.type = D_REG;
+				if(p->reg != NREG)
+					p->from.reg = p->reg;
+				else
+					p->from.reg = p->to.reg;
+				p->reg = NREG;
+			}
+			break;
 
 		case AMOVH:
 		case AMOVHU:
@@ -161,6 +159,7 @@ return;
 			/*
 			 * look for MOVB x,R; MOVB R,R
 			 */
+			r1 = r->link;
 			if(p->to.type != D_REG)
 				break;
 			if(r1 == R)
@@ -175,8 +174,8 @@ return;
 			excise(r1);
 			break;
 		}
-\t\tr1 = r->link;
 	}\n+#ifdef	NOTDEF
 
 //	for(r=firstr; r!=R; r=r->link) {
 //		p = r->prog;

コアとなるコードの解説

AEOR (EOR命令) の最適化ブロック:
- 以前は//と#ifdef NOTDEFでコメントアウトされていたcase AEOR:ブロックが再有効化されています。
- このブロックは、現在の命令pがAEOR（ARMのEOR命令）である場合に処理を行います。
- if(isdconst(&p->from) && p->from.offset == -1): これは、EOR命令のソースオペランド（p->from）が定数であり、その値が-1であるかどうかをチェックしています。
- もし条件が真であれば、以下の変換が行われます。
  - p->as = AMVN;: 命令の種類をAMVN（MVN命令）に変更します。
  - p->from.type = D_REG;: ソースオペランドのタイプをレジスタ（D_REG）に設定します。これは、MVN命令が通常、レジスタをオペランドとして取るためです。
  - if(p->reg != NREG) p->from.reg = p->reg; else p->from.reg = p->to.reg;: MVN命令のソースレジスタを決定します。元のEOR命令の第2オペランド（p->reg）が存在すればそれを使用し、そうでなければデスティネーションレジスタ（p->to.reg）を使用します。これは、EOR -1, Rsrc, RdestがMVN Rsrc, Rdestに変換されることを意味します。
  - p->reg = NREG;: EOR命令の第2オペランドレジスタ（p->reg）を無効化します。MVNは単一のソースオペランドしか持たないためです。
- このロジックにより、EOR $-1, Rsrc, Rdestという2オペランド命令が、より効率的なMVN Rsrc, Rdestという1オペランド命令に変換されます。
AMOVH, AMOVHU, AMOVB, AMOVBU (ムーブ命令) の最適化ブロック:
- このブロックも以前はコメントアウトされていた部分が再有効化されています。
- case AMOVH:などから始まるこのブロックは、ハーフワードまたはバイトのムーブ命令を処理します。
- r1 = r->link;: 現在の命令rの次の命令をr1に取得します。この行は、以前はループの最後にありましたが、この最適化ブロックの先頭に移動されています。これは、この最適化が現在の命令とその次の命令のペアを検査するため、r1が常に有効な次の命令を指すようにするためです。
- if(p->to.type != D_REG) break;: 現在のムーブ命令のデスティネーションがレジスタでない場合は、この最適化を適用しません。
- if(r1 == R) break;: 次の命令が存在しない場合は処理を中断します。
- if(r1->as != p->as) break;: 次の命令の種類が現在の命令と同じでない場合は中断します。
- if(r1->from.type != D_REG || r1->from.reg != p->to.reg) break;: 次の命令のソースオペランドがレジスタであり、かつそのレジスタが現在の命令のデスティネーションレジスタと同じであるかをチェックします。
- if(r1->to.type != D_REG || r1->to.reg != p->to.reg) break;: 次の命令のデスティネーションオペランドがレジスタであり、かつそのレジスタが現在の命令のデスティネーションレジスタと同じであるかをチェックします。
- これらの条件がすべて満たされる場合、MOVB x,R; MOVB R,Rのような冗長なパターンが検出されたことになります。
- excise(r1);: 冗長な次の命令r1を命令リストから削除します。

これらの変更により、peep.cはより積極的なpeephole最適化を実行し、Goコンパイラが生成するARMアセンブリコードの品質を向上させます。

参考にした情報源リンク

コミットメッセージに記載されているGoのChange List: https://golang.org/cl/6674048
Go言語のコンパイラに関する一般的な知識
ARMアセンブリ命令に関する一般的な知識
Peephole最適化に関する一般的な知識
Go言語の^演算子に関する知識
cmd/5gが古いARMコンパイラであるという歴史的背景に関する知識
isdconstなどのコンパイラ内部関数に関する一般的な推測（具体的なドキュメントは公開されていないため）
excise関数が命令を削除する役割を持つという一般的なコンパイラ最適化の知識
Web検索結果: "Go compiler 5g peep.c"
Web検索結果: "ARM EOR MVN optimization"
Web検索結果: "peephole optimization compiler"

comemo

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. Goコンパイラの構造（特に`cmd/5g`とバックエンド）

2. Peephole最適化とは

3. ARMアーキテクチャの基本的なアセンブリ命令

4. ビット演算と補数（`^`演算子、-1の表現）

技術的詳細

1. `EOR -1,x,y => MVN x,y` 最適化

2. 冗長な`MOVB`命令の最適化

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

コアとなるコードの解説

関連リンク

参考にした情報源リンク

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

コミット

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

元コミット内容

変更の背景

前提知識の解説

1. Goコンパイラの構造（特に`cmd/5g`とバックエンド）

2. Peephole最適化とは

3. ARMアーキテクチャの基本的なアセンブリ命令

4. ビット演算と補数（`^`演算子、-1の表現）

技術的詳細

1. `EOR -1,x,y => MVN x,y` 最適化

2. 冗長な`MOVB`命令の最適化

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

コアとなるコードの解説

関連リンク

参考にした情報源リンク

Keyboard shortcuts

comemo