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

コミット

commit 6bee4e556fddec07cbdeb348dd91d3e55f7e2960
Author: Luuk van Dijk <lvd@golang.org>
Date:   Thu Dec 1 14:46:32 2011 +0100

    gc: avoid re-genning ninit in branches involving float comparison.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/5451050

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

https://github.com/golang/go/commit/6bee4e556fddec07cbdeb348dd91d3e55f7e2960

元コミット内容

gc: avoid re-genning ninit in branches involving float comparison.

このコミットは、Goコンパイラ（gc）において、浮動小数点数比較を含む分岐処理でninit（ノードの初期化リスト）が再生成されるのを避けるための変更です。

変更の背景

Goコンパイラは、ソースコードを機械語に変換する過程で、中間表現（IR）を生成し、それを最適化し、最終的にターゲットアーキテクチャのコードを生成します。この過程で、各ノード（ASTノードなど）には、そのノードが評価される前に実行されるべき初期化処理のリスト（ninit）が関連付けられることがあります。

浮動小数点数（float）の比較は、特にIEEE 754標準に準拠するシステムにおいて、通常の整数比較とは異なる振る舞いをすることがあります。例えば、NaN（Not a Number）との比較は常に偽となる、あるいは非正規化数（denormalized numbers）の扱いなど、特殊なケースが存在します。

このコミットの背景には、Goコンパイラが浮動小数点数比較を含む条件分岐（例: if a < b where a and b are floats）を処理する際に、ninitが不必要に再生成される問題があったと考えられます。ninitの再生成は、コンパイル時間の増加や、場合によってはコード生成の非効率性につながる可能性があります。特に、分岐の各パスで同じ初期化処理が繰り返し生成されるような状況は避けるべきです。

この問題は、コンパイラのコード生成フェーズ、特にcgen.cファイル内のbgen関数（分岐コード生成を担当）で発生していたようです。bgen関数は、条件式に基づいてコードの分岐を生成しますが、浮動小数点数比較の場合に、条件式の評価とは直接関係のないninitが再度処理されてしまうことが問題でした。

前提知識の解説

Goコンパイラ (gc)

Go言語の公式コンパイラはgcと呼ばれます。これは、Go言語で書かれたプログラムを機械語に変換する役割を担います。gcは、フロントエンド（構文解析、型チェック）、中間コード生成、最適化、バックエンド（コード生成）といった複数のフェーズで構成されています。

AST (Abstract Syntax Tree)

Goコンパイラは、ソースコードを解析して抽象構文木（AST）を構築します。ASTは、プログラムの構造を木構造で表現したもので、各ノードは変数宣言、関数呼び出し、演算子などの言語要素に対応します。

Node構造体とninitフィールド

Goコンパイラの内部では、ASTの各要素はNode構造体で表現されます。このNode構造体には、ninitというフィールドが存在します。ninitはNodeList型であり、そのノードが評価される前に実行されるべき初期化処理（例えば、一時変数の宣言や初期化など）のリストを保持します。これは、複雑な式や条件分岐において、必要な前処理を適切に行うために使用されます。

cgen.cとbgen関数

src/cmd/{5g,6g,8g}/cgen.cは、それぞれARM (5g), AMD64 (6g), x86 (8g) アーキテクチャ向けのコード生成（cgenはCode Generationの略）を担当するファイルです。これらのファイルには、Goコンパイラのバックエンドの一部として、中間表現からターゲットアーキテクチャの機械語への変換ロジックが含まれています。

bgen関数（Branch Generationの略）は、条件分岐（if文、forループの条件など）のコードを生成する役割を担っています。この関数は、与えられた条件式（Node *n）が真または偽の場合にジャンプするターゲット（Prog *to）を指定して、適切な分岐命令を生成します。

浮動小数点数比較

浮動小数点数の比較は、整数とは異なり、NaN（Not a Number）の存在や、精度に関する問題があります。IEEE 754標準では、NaNとの比較は常に偽となります。また、浮動小数点数の比較は、CPUの浮動小数点演算ユニット（FPU）の特定の命令セットを使用することが多く、その挙動はアーキテクチャによって微妙に異なる場合があります。

Prog構造体とpatch関数

Prog構造体は、Goコンパイラの内部で機械語命令（またはその中間表現）を表すために使用されます。patch関数は、生成された命令のジャンプ先アドレスを修正するために使用されます。これは、分岐命令のターゲットがまだ不明な場合（例えば、前方参照の場合）に、後から正しいアドレスで埋めるために必要です。

技術的詳細

このコミットは、Goコンパイラのコード生成フェーズにおける特定の最適化に関するものです。具体的には、src/cmd/{5g,6g,8g}/cgen.cファイル内のbgen関数が修正されています。

bgen関数は、条件式を評価し、その結果に基づいてコードの実行フローを分岐させるための機械語命令を生成します。浮動小数点数比較を含む条件式の場合、bgen関数は通常、比較結果に応じて異なるコードパスにジャンプする命令を生成します。

問題は、この分岐処理の際に、条件式nに関連付けられたninit（初期化リスト）が、分岐の各パスで不必要に再生成される可能性があったことです。ninitは、ノードが評価される前に一度だけ実行されるべき初期化処理を含むため、分岐のたびに再生成されるのは非効率的であり、場合によっては誤ったコードを生成する原因にもなりかねません。

このコミットでは、この問題を解決するために、bgen関数内で浮動小数点数比較を処理する部分に以下の変更が加えられました。

1. NodeList *ll; の追加: llという一時的なNodeListポインタが導入されました。
2. n->ninit の保存とクリア: bgen関数が再帰的に呼び出される前に、現在のノードnのninitをllに一時的に保存し、n->ninitをnil（またはNULL）に設定します。

   ll = n->ninit;
   n->ninit = nil;
   

   これにより、再帰的なbgen呼び出しの際に、ninitが再度処理されるのを防ぎます。
3. bgen(n, 1, p2); の呼び出し: 条件式nを評価し、真の場合にp2にジャンプするコードを生成します。
4. n->ninit の復元: 再帰的なbgen呼び出しが完了した後、保存しておいたninitを元のノードnに戻します。

   n->ninit = ll;
   

この変更により、浮動小数点数比較を含む分岐処理において、ninitが一度だけ処理され、不必要な再生成が回避されるようになります。これは、コンパイラの効率性を向上させ、生成されるコードの品質を維持するために重要な修正です。

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

変更は、src/cmd/5g/cgen.c, src/cmd/6g/cgen.c, src/cmd/8g/cgen.c の3つのファイルに共通して行われています。これらのファイルは、それぞれ異なるアーキテクチャ（ARM, AMD64, x86）向けのコード生成を担当しています。

各ファイルのbgen関数内の、浮動小数点数比較を処理する部分（case OLT: case OLE: case OGT: case OGE: case OEQ: case ONE: のような比較演算子を扱うブロック内）に以下の変更が加えられています。

--- a/src/cmd/5g/cgen.c
+++ b/src/cmd/5g/cgen.c
@@ -850,6 +850,7 @@ bgen(Node *n, int true, Prog *to)
  	int et, a;
  	Node *nl, *nr, *r;
  	Node n1, n2, n3, n4, tmp;
+	NodeList *ll; // <-- 追加
  	Prog *p1, *p2;
 
  	USED(n4);			// in unreachable code below
@@ -950,7 +951,10 @@ bgen(Node *n, int true, Prog *to)
  			p1 = gbranch(AB, T);
  			p2 = gbranch(AB, T);
  			patch(p1, pc);
+			ll = n->ninit; // <-- 追加
+			n->ninit = nil; // <-- 追加
  			bgen(n, 1, p2);
+			n->ninit = ll; // <-- 追加
  			patch(gbranch(AB, T), to);
  			patch(p2, pc);
  			goto ret;

同様の変更がsrc/cmd/6g/cgen.cとsrc/cmd/8g/cgen.cにも適用されています。

コアとなるコードの解説

変更の核心は、bgen関数内で浮動小数点数比較を処理するロジックにあります。

1. NodeList *ll;: これは、現在のノードnの初期化リストninitを一時的に保持するためのポインタ変数です。
2. ll = n->ninit;: bgen関数が再帰的に呼び出される前に、現在のノードnに紐付けられているninit（初期化処理のリスト）をllに保存します。これにより、元のninitへの参照が失われるのを防ぎます。
3. n->ninit = nil;: n->ninitをnilに設定します。これは非常に重要なステップです。この設定により、その後のbgen(n, 1, p2);の再帰呼び出しにおいて、nのninitが既に処理されたものとして扱われ、不必要な再生成が回避されます。もしn->ninitがnilに設定されないまま再帰呼び出しが行われると、同じ初期化処理が再度生成されてしまう可能性があります。
4. bgen(n, 1, p2);: これは、条件式nを評価し、その結果に基づいてコードを生成するための再帰呼び出しです。1は真のケースを、p2は真の場合にジャンプするターゲットを示します。
5. n->ninit = ll;: 再帰呼び出しが完了した後、一時的に保存しておいたninit（llに格納されていたもの）を元のノードnのninitフィールドに復元します。これにより、ninitが他の場所で必要とされる場合に備えて、その情報が保持されます。

この一連の操作により、浮動小数点数比較を含む分岐処理において、ninitが一度だけ適切に処理され、コンパイラの効率性と正確性が向上します。これは、コンパイラの内部動作を理解し、特定のコーナーケースでの非効率性を解消するための典型的な最適化手法と言えます。

関連リンク

• Go言語の公式ドキュメント: https://golang.org/doc/
• Goコンパイラのソースコード: https://github.com/golang/go
• Goコンパイラの内部構造に関する資料 (Goのバージョンによって内容は異なる可能性があります):
  • "The Go Programming Language Compiler" by Russ Cox: https://talks.golang.org/2015/go-compiler.slide
  • "Go Compiler Internals" by David Crawshaw: https://dave.cheney.net/2014/11/25/go-compiler-internals

参考にした情報源リンク

• Go言語のコミット履歴: https://github.com/golang/go/commits/master
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージにあるhttps://golang.org/cl/5451050は、このGerritの変更リストへのリンクです。)
• IEEE 754 浮動小数点数標準に関する情報:
  • Wikipedia: https://ja.wikipedia.org/wiki/IEEE_754
• Goコンパイラのgcに関する一般的な情報源 (Stack Overflow, 技術ブログなど)
• Go言語のNode構造体やNodeListに関する情報 (Goコンパイラのソースコードを直接参照)
• Go言語のProg構造体やpatch関数に関する情報 (Goコンパイラのソースコードを直接参照)
• Go言語のbgen関数に関する情報 (Goコンパイラのソースコードを直接参照)
• Go言語のcgen.cファイルに関する情報 (Goコンパイラのソースコードを直接参照)
• Go言語のコンパイラ最適化に関する一般的な情報