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

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

本コミットは、Go言語の初期のコンパイラである6gにおける、符号なし整数の除算処理に関する修正です。具体的には、src/cmd/6g/gen.cファイル内のdodiv関数において、符号なし除算の際にdxレジスタ(除算の被除数の上位ビットを保持するレジスタ)の初期化が適切に行われるように変更されています。

コミット

commit 250ec1665a8d142a4b4f7e634991aeac50bb14f8
Author: Ken Thompson <ken@golang.org>
Date:   Mon Nov 3 13:27:16 2008 -0800

    unsigned divide by fn()
    
    R=r
    OCL=18351
    CL=18351

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

https://github.com/golang/go/commit/250ec1665a8d142a4b4f7e634991aeac50bb14f8

元コミット内容

    unsigned divide by fn()

このコミットメッセージは非常に簡潔ですが、「関数による符号なし除算」という問題に対処していることを示唆しています。これは、除算の被除数が符号なし整数であり、かつ除数が関数呼び出しの結果である場合に、特定のコンパイラ最適化やコード生成のロジックが正しく機能しない可能性があったことを示しています。

変更の背景

Go言語のコンパイラは、ソースコードを機械語に変換する過程で、様々な最適化やレジスタ割り当てを行います。特に除算のような演算は、CPUのアーキテクチャに依存する特性が強く、符号付き/符号なしの区別が重要になります。

x86アーキテクチャでは、DIV命令(符号なし除算)やIDIV命令(符号付き除算)が提供されています。これらの命令は、被除数をAX(またはEAX/RAX)とDX(またはEDX/RDX)レジスタの組み合わせで表現します。具体的には、DX:AX(またはEDX:EAX/RDX:RAX)が被除数となり、AX(またはEAX/RAX)が被除数の下位ビット、DX(またはEDX/RDX)が上位ビットを保持します。

符号なし除算の場合、被除数が32ビット(または64ビット)であれば、DXレジスタは通常0に初期化されている必要があります。これは、被除数が単一のレジスタに収まる場合でも、DIV命令がDX:AXを被除数として扱うためです。もしDXが適切に0クリアされていないと、意図しない大きな値が被除数として扱われ、誤った除算結果やオーバーフローを引き起こす可能性があります。

このコミットは、dodiv関数(Goコンパイラが除算操作を処理する部分)において、符号なし除算の際にdxレジスタの初期化が不足していた、あるいは誤ったタイミングで行われていた問題を修正することを目的としています。特に、除数が関数呼び出しの結果である場合など、コンパイラが被除数の値を事前に完全に把握できない状況で、dxの初期化が漏れるケースがあったと考えられます。

前提知識の解説

Go言語のコンパイラ 6g

6gは、Go言語の初期のコンパイラの一つで、主にx86-64アーキテクチャ(AMD64)をターゲットとしていました。Go言語のコンパイラは、フロントエンド(構文解析、型チェックなど)とバックエンド(コード生成、最適化など)に分かれています。src/cmd/6g/gen.cは、このバックエンドの一部であり、Goの抽象構文木(AST)をターゲットアーキテクチャの機械語命令に変換するコード生成ロジックを含んでいます。

Node構造体

Goコンパイラ内部では、プログラムの各要素(変数、定数、演算子、関数呼び出しなど)がNode構造体として表現されます。Nodeは、その要素の型、値、レジスタ割り当て情報、Ullman数(式の複雑度を示す指標)など、コンパイルに必要な様々な情報を含んでいます。

レジスタ割り当てとコード生成

コンパイラは、効率的なコードを生成するために、CPUのレジスタを最大限に活用します。regallocはレジスタを割り当てる関数、regfreeはレジスタを解放する関数です。gmoveは、あるNodeから別のNodeへ値を移動させる(多くの場合、レジスタ間またはレジスタとメモリ間の移動に対応する機械語命令を生成する)関数です。ginsは、指定されたオペレーション(optoasで変換されたアセンブリ命令)に対応する機械語命令を生成する関数です。

符号付き整数と符号なし整数

コンピュータにおける整数は、その表現方法によって「符号付き(signed)」と「符号なし(unsigned)」に分けられます。

  • 符号付き整数: 最上位ビットを符号ビットとして使用し、正の値と負の値を表現します(例: int, long)。
  • 符号なし整数: 全てのビットを値の表現に使用し、非負の値のみを表現します(例: uint, ulong)。

除算演算において、符号付きと符号なしでは結果の解釈や、CPUが使用する命令が異なります。特に、符号なし除算では、被除数が負になることはないため、DXレジスタは通常0に初期化される必要があります。

dodiv関数

dodiv関数は、Goコンパイラが除算(ODIV)および剰余(OMOD)演算を処理するための内部関数です。この関数は、被除数(nl)、除数(nr)、結果を格納するres、そしてaxdxレジスタに対応するNodeを受け取ります。この関数内で、実際の除算命令が生成されます。

技術的詳細

このコミットの核心は、dodiv関数における符号なし除算のdxレジスタの初期化ロジックの変更です。

変更前のコードでは、if(!issigned[t->etype]) { nodconst(&n3, t, 0); gmove(&n3, dx); }というブロックが、regallocの呼び出しよりも前に存在していました。これは、被除数の型が符号なしの場合に、dxレジスタを0で初期化しようとするものです。しかし、この位置では、nl(被除数)やnr(除数)のコード生成がまだ行われていないため、dxレジスタが他の目的で使用されたり、その値が上書きされたりする可能性がありました。

変更後のコードでは、dxレジスタの0初期化ロジックが、cgen(nl, ax)(被除数のコード生成)の直後、かつgins(optoas(OFOR, t), N, N)(符号拡張命令の生成)の直前に移動されています。

具体的には、以下の2つのパスでdxの初期化が行われるようになりました。

  1. nl->ullman >= nr->ullman の場合(被除数の複雑度が除数以上の場合):

    • cgen(nl, ax); で被除数をaxレジスタにロードします。
    • if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); } で、被除数が符号なしの場合にdxを0クリアします。
    • その後、符号付きの場合にOFOR命令(符号拡張)を生成し、除数のコード生成と除算命令の生成が続きます。
  2. nl->ullman < nr->ullman の場合(除数の複雑度が被除数より高い場合):

    • cgen(nr, &n3); で除数をn3にロードします。
    • cgen(nl, ax); で被除数をaxレジスタにロードします。
    • if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); } で、被除数が符号なしの場合にdxを0クリアします。
    • その後、符号付きの場合にOFOR命令(符号拡張)を生成し、除算命令の生成が続きます。

この変更により、dxレジスタの0初期化が、被除数がaxレジスタにロードされた直後に行われるようになり、その後の除算命令が正しいDX:AXのペアで実行されることが保証されます。特に、除数が関数呼び出しの結果である場合など、コンパイラが被除数の値を事前に完全に把握できない状況でも、dxの初期化が適切なタイミングで行われるようになります。

また、Node n3;Node n3, n4; に変更され、n4という新しいNodeが導入されています。これは、dxレジスタを0で初期化するために使用される一時的なNodeとしてn4が使われるようになったためです。

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

src/cmd/6g/gen.c ファイルの dodiv 関数内。

--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -907,7 +907,7 @@ void
 dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)
 {
  int a;
- Node n3;
+ Node n3, n4;
  Type *t;
 
  t = nl->type;
@@ -919,25 +919,25 @@ dodiv(int op, Node *nl, Node *nr, Node *res, Node *ax, Node *dx)
  }
  a = optoas(op, t);
 
- if(!issigned[t->etype]) {
-  nodconst(&n3, t, 0);
-  gmove(&n3, dx);
- }
-
  regalloc(&n3, nr->type, N);
  if(nl->ullman >= nr->ullman) {
   cgen(nl, ax);
-  if(issigned[t->etype])
+  if(!issigned[t->etype]) {
+   nodconst(&n4, t, 0);
+   gmove(&n4, dx);
+  } else
    gins(optoas(OFOR, t), N, N);
   cgen(nr, &n3);
-  gins(a, &n3, N);
  } else {
   cgen(nr, &n3);
   cgen(nl, ax);
-  if(issigned[t->etype])
+  if(!issigned[t->etype]) {
+   nodconst(&n4, t, 0);
+   gmove(&n4, dx);
+  } else
    gins(optoas(OFOR, t), N, N);
-  gins(a, &n3, N);
  }
+ gins(a, &n3, N);
  regfree(&n3);
 
  if(op == ODIV)

コアとなるコードの解説

変更点1: Node n3; から Node n3, n4;

- Node n3;
+ Node n3, n4;

n4という新しいNode変数が追加されました。これは、dxレジスタを0で初期化するために使用される一時的なNodeとして導入されました。以前はn3がこの目的にも使われていましたが、n3は除数を保持するためにも使われるため、役割を分離することでコードの明確性と正確性を高めています。

変更点2: dxレジスタの0初期化ロジックの移動と修正

- if(!issigned[t->etype]) {
-  nodconst(&n3, t, 0);
-  gmove(&n3, dx);
- }

このブロックは削除されました。以前はdodiv関数の冒頭近くでdxを0クリアしていましたが、このタイミングでは被除数の値がaxにロードされる前であり、dxが他の目的で使われたり、その値が上書きされたりする可能性がありました。

  if(nl->ullman >= nr->ullman) {
   cgen(nl, ax);
-  if(issigned[t->etype])
+  if(!issigned[t->etype]) {
+   nodconst(&n4, t, 0);
+   gmove(&n4, dx);
+  } else
    gins(optoas(OFOR, t), N, N);
   cgen(nr, &n3);
-  gins(a, &n3, N);
  } else {
   cgen(nr, &n3);
   cgen(nl, ax);
-  if(issigned[t->etype])
+  if(!issigned[t->etype]) {
+   nodconst(&n4, t, 0);
+   gmove(&n4, dx);
+  } else
    gins(optoas(OFOR, t), N, N);
-  gins(a, &n3, N);
  }
+ gins(a, &n3, N);

dxレジスタの0初期化ロジックが、被除数(nl)がaxレジスタにロードされた直後に移動されました。

  • cgen(nl, ax);:被除数の値をaxレジスタに生成(ロード)します。
  • if(!issigned[t->etype]) { nodconst(&n4, t, 0); gmove(&n4, dx); }
    • !issigned[t->etype]:被除数の型が符号なしであるかをチェックします。
    • nodconst(&n4, t, 0);:型tの定数0を表すNoden4に作成します。
    • gmove(&n4, dx);n4(定数0)の値をdxレジスタに移動させます。これにより、符号なし除算の前にdxが確実に0クリアされます。
  • else gins(optoas(OFOR, t), N, N);:被除数が符号付きの場合、OFOR命令(符号拡張命令)を生成します。これは、符号付き除算の前にaxレジスタの符号をdxレジスタに拡張するために必要です。

この変更により、dxレジスタの初期化が、除算命令が実行される直前の適切なタイミングで行われるようになり、符号なし除算における正確性が保証されます。

変更点3: gins(a, &n3, N); の移動

-  gins(a, &n3, N);
...
-  gins(a, &n3, N);
...
+ gins(a, &n3, N);

除算命令を生成するgins(a, &n3, N);の呼び出しが、if/elseブロックの外に移動され、一度だけ呼び出されるようになりました。これにより、コードの重複が解消され、より簡潔になっています。除算命令は、被除数と除数のコード生成が完了し、dxレジスタの初期化(必要であれば)も済んだ後に行われるべきであるため、この位置が適切です。

関連リンク

参考にした情報源リンク

  • x86アセンブリ言語の除算命令(DIV, IDIV)に関する情報:
  • コンパイラのコード生成とレジスタ割り当てに関する一般的な情報:
    • コンパイラ設計に関する書籍やオンラインリソース(例: Dragon Book)
  • Go言語のコンパイラ内部構造に関する情報(より現代のコンパイラに関するものが多いですが、基本的な概念は共通しています):