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

コミット

コミットハッシュ: dc78c64f239ef5969ecbb9ca4c3b7a6928143e98
作成者: Ken Thompson ken@golang.org
コミット日時: 2008年11月7日 14:20:32 -0800
コミットメッセージ: "byte multiply"

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

https://github.com/golang/go/commit/dc78c64f239ef5969ecbb9ca4c3b7a6928143e98

元コミット内容

このコミットは、Go言語の初期開発期におけるバイト乗算（byte multiply）の最適化実装です。3つのファイルが変更されており、合計で34行の追加と1行の削除が行われています。

src/cmd/6g/cgen.c: 5行追加、1行削除
src/cmd/6g/gen.c: 29行追加
src/cmd/6g/gg.h: 1行追加

変更の核心は、cgen_bmulという新しい関数の追加と、既存の乗算処理ロジックの変更にあります。

変更の背景

2008年当時、Go言語はまだ開発初期段階にありました。Ken Thompson、Rob Pike、Robert Griesemer によって設計されたGoは、2007年9月にGoogleの20%プロジェクトとして開始され、2008年1月に初期コンパイラの開発が始まりました。

6gコンパイラは、AMD64（x86-64）アーキテクチャ向けのGoコンパイラでした。当時のGoコンパイラは、アーキテクチャ固有の実装を持っており、6g（AMD64）、8g（x86）、5g（ARM）という命名規則が使われていました。

バイト乗算の最適化が必要とされた背景には、以下の要因があります：

アーキテクチャ固有の最適化: AMD64アーキテクチャにおいて、バイト単位の乗算は特殊な処理が必要でした
効率的なコード生成: 小さなデータ型の演算を効率的に処理するため
レジスタ使用量の最適化: 限られたレジスタリソースを効率的に使用するため

前提知識の解説

Go言語の初期コンパイラアーキテクチャ

2008年当時のGoコンパイラは、C言語で書かれており、以下のような構造を持っていました：

構文解析: ソースコードを解析して抽象構文木（AST）を構築
型チェック: 型の整合性を検証
コード生成: ASTから機械語コードを生成

6gコンパイラの構造

6gコンパイラは、以下のような主要コンポーネントから構成されていました：

cgen.c: コード生成のメインロジック
gen.c: 各種命令の生成ロジック
gg.h: 共通のヘッダファイル

バイト乗算の特殊性

バイト乗算（8ビット乗算）は、以下の理由で特殊な処理が必要でした：

オーバーフロー: 8ビット × 8ビット = 最大16ビットの結果
符号拡張: 符号付きと符号なしの処理の違い
レジスタ使用: AMD64での効率的なレジスタ使用

技術的詳細

1. cgen.c の変更

// 変更前
case OMUL:
    a = optoas(n->op, nl->type);
    goto sbop;

// 変更後
case OMUL:
    a = optoas(n->op, nl->type);
    if(a != AIMULB)
        goto sbop;
    cgen_bmul(n->op, nl, nr, res);
    break;

この変更により、乗算命令がAIMULB（バイト乗算命令）の場合、専用のcgen_bmul関数が呼び出されるようになりました。

2. cgen_bmul関数の実装

新しく追加されたcgen_bmul関数は、以下の処理を行います：

型の決定: 符号付き/符号なしに応じて適切な型を選択
レジスタ割り当て: 効率的なレジスタ使用のための順序決定
コード生成: 最適化されたバイト乗算コードの生成

3. ullmanの利用

if(nl->ullman >= nr->ullman) {
    // 左オペランドを先に処理
} else {
    // 右オペランドを先に処理
}

ullmanは、式の複雑さを表すメトリクスで、レジスタ使用量を最適化するために使用されます。

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

src/cmd/6g/cgen.c:122-128

case OADD:
case OMUL:
    a = optoas(n->op, nl->type);
-   goto sbop;
+   if(a != AIMULB)
+       goto sbop;
+   cgen_bmul(n->op, nl, nr, res);
+   break;

src/cmd/6g/gen.c:1095-1124

+void
+cgen_bmul(int op, Node *nl, Node *nr, Node *res)
+{
+   Node n1, n2;
+   Type *t;
+   int a;
+
+   t = types[TUINT16];
+   if(issigned[nl->type->etype])
+       t = types[TINT16];
+
+   if(nl->ullman >= nr->ullman) {
+       regalloc(&n1, t, nl);
+       cgen(nl, &n1);
+       regalloc(&n2, t, nr);
+       cgen(nr, &n2);
+   } else {
+       regalloc(&n2, t, nr);
+       cgen(nr, &n2);
+       regalloc(&n1, t, nl);
+       cgen(nl, &n1);
+   }
+   a = optoas(op, t);
+   gins(a, &n2, &n1);
+   gmove(&n1, res);
+   regfree(&n1);
+   regfree(&n2);
+}

src/cmd/6g/gg.h:141

+void cgen_bmul(int, Node*, Node*, Node*);

t = types[TUINT16];
if(issigned[nl->type->etype])
    t = types[TINT16];

バイト乗算の結果は16ビットになる可能性があるため、結果を格納するために16ビット型に昇格させています。符号付きバイトの場合はTINT16、符号なしバイトの場合はTUINT16を使用します。

3. レジスタ割り当ての最適化

if(nl->ullman >= nr->ullman) {
    // 複雑な式を先に処理
} else {
    // 単純な式を先に処理
}

ullman値を比較して、より複雑な式を先に処理することで、レジスタ使用量を最適化しています。

4. 命令生成と結果の移動

a = optoas(op, t);
gins(a, &n2, &n1);
gmove(&n1, res);

最適化された命令を生成し、結果を適切な場所に移動しています。

5. リソースの解放

regfree(&n1);
regfree(&n2);

使用したレジスタを適切に解放し、メモリリークを防いでいます。

comemo