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

このコミットは、Goコンパイラのcmd/gcにおいて、論理AND (&&) および論理OR (||) 演算子のランタイム競合検出器（Race Detector）による計測（instrumentation）を改善するものです。特に、これらの演算子の右オペランドが条件付きでしか実行されないという特性を考慮し、計測が不必要に高コストにならないようにするための変更が含まれています。

コミット

commit c0b3c17184735e1f4352aea6a9ecf5779f098cd5
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon Mar 25 22:12:47 2013 +0100

    cmd/gc: instrument logical && and ||.
    
    The right operand of a && and || is only executed conditionnally,
    so the instrumentation must be more careful. In particular
    it should not turn nodes assumed to be cheap after walk into
    expensive ones.
    
    Update #4228
    
    R=dvyukov, golang-dev
    CC=golang-dev
    https://golang.org/cl/7986043

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

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

元コミット内容

cmd/gc: instrument logical && and ||.

論理AND (&&) および論理OR (||) 演算子を計測対象とする。これらの演算子の右オペランドは条件付きでしか実行されないため、計測はより慎重に行う必要がある。特に、ウォーク後に安価であると想定されるノードを高価なものに変えるべきではない。 Issue #4228 を更新。

変更の背景

Go言語の競合検出器（Race Detector）は、並行プログラムにおけるデータ競合（data race）を検出するための強力なツールです。データ競合は、複数のゴルーチンが同時に同じメモリ位置にアクセスし、少なくとも1つのアクセスが書き込みであり、かつそれらのアクセスが同期メカニズムによって保護されていない場合に発生します。このような競合は、プログラムの予測不能な動作やバグの原因となります。

競合検出器は、コンパイル時にコードに計測（instrumentation）コードを挿入することで機能します。この計測コードは、メモリへのアクセス（読み書き）を監視し、競合の可能性をランタイムでチェックします。

しかし、論理AND (&&) と論理OR (||) 演算子には特殊な性質があります。これらは「短絡評価（short-circuit evaluation）」を行います。

A && B: A が false であれば B は評価されません。
A || B: A が true であれば B は評価されません。

従来の競合検出器の計測では、この短絡評価の特性が考慮されていませんでした。つまり、右オペランドが実行されない場合でも、その部分に挿入された計測コードが実行されてしまう可能性がありました。これは、不必要なオーバーヘッドを発生させるだけでなく、場合によっては誤った競合検出を引き起こす可能性もありました。

このコミットは、Issue #4228 (Go issue tracker: "cmd/gc: race detector doesn't instrument logical && and ||") に対応するものです。このIssueでは、論理演算子の右オペランドが競合検出器によって適切に計測されていない、あるいは不適切に計測されているという問題が提起されていました。特に、右オペランドが実行されない場合に、その部分の計測コードが実行されることによるパフォーマンスへの影響や、誤検出の可能性が懸念されていました。

この変更の目的は、論理AND/OR演算子の短絡評価のセマンティクスを尊重しつつ、右オペランドが実際に実行される場合にのみ競合検出器の計測が適用されるようにすることです。これにより、競合検出の正確性を高め、不必要なランタイムオーバーヘッドを削減することが目指されました。

前提知識の解説

1. Goコンパイラ (`cmd/gc`)

cmd/gc はGo言語の公式コンパイラです。Goのソースコードを機械語に変換する役割を担っています。コンパイルプロセスには、字句解析、構文解析、型チェック、中間表現（IR）の生成、最適化、コード生成など、様々なフェーズがあります。競合検出器の計測は、通常、中間表現の段階で行われます。

2. Goの競合検出器 (Race Detector)

Goの競合検出器は、Go 1.1で導入された強力なツールです。go run -race や go build -race のように -race フラグを付けてビルド・実行することで有効になります。その仕組みは以下の通りです。

計測 (Instrumentation): コンパイル時に、メモリへのアクセス（読み込み、書き込み）が行われる箇所に特別なコード（計測コード）が挿入されます。
ランタイム監視: 実行時に、この計測コードがメモリアクセスイベントを記録し、それらのイベントがデータ競合のルール（異なるゴルーチンからの同時アクセス、少なくとも一方が書き込み、同期なし）に違反していないかをチェックします。
レポート: データ競合が検出された場合、競合が発生した場所（ファイル名、行番号）や関連するゴルーチンのスタックトレースなどの詳細な情報がレポートされます。

競合検出器は、プログラムの実行パスを監視するため、テストスイートを実行する際に有効にすると、並行処理のバグを見つけるのに非常に役立ちます。

3. 短絡評価 (Short-circuit Evaluation)

論理AND (&&) と論理OR (||) 演算子に見られる評価戦略です。

expr1 && expr2: expr1 が false と評価された場合、式全体の結果は false と確定するため、expr2 は評価されません。
expr1 || expr2: expr1 が true と評価された場合、式全体の結果は true と確定するため、expr2 は評価されません。

この特性は、例えば if obj != nil && obj.Method() のように、ヌルポインタ参照を防ぐために利用されることがあります。競合検出器がこの特性を考慮しないと、obj.Method() が実際に実行されない場合でも、その内部のメモリアクセスが計測されてしまい、誤った競合が報告されたり、不必要なオーバーヘッドが発生したりする可能性があります。

4. コンパイラのAST (Abstract Syntax Tree) とノード (Node)

コンパイラは、ソースコードを解析する際に、プログラムの構造を抽象構文木（AST）として表現します。ASTは、プログラムの各要素（変数、演算子、関数呼び出しなど）をノードとして表現し、それらの関係を木構造で表します。このコミットで言及されている Node は、このASTの各要素を指します。OANDAND は論理AND演算子、OOROR は論理OR演算子を表すノードの種類です。

5. `ninit` と `nbody`

GoコンパイラのASTノードには、関連する初期化文や本体の文を保持するためのフィールドがあります。

ninit: ノードの評価前に実行されるべき初期化文のリスト。
nbody: ノードの本体（例えば、if 文のthenブロックや for ループの本体）。

競合検出器の計測コードは、これらの ninit や nbody に追加されることがよくあります。

6. `racewalk.c` と `subr.c`

racewalk.c: Goコンパイラのソースコードの一部で、競合検出器の計測ロジックが含まれています。ASTをウォーク（走査）し、メモリアクセスが行われるノードに計測コードを挿入する処理が記述されています。
subr.c: コンパイラのサブルーチンやユーティリティ関数が含まれるファイルです。ullmancalc のようなノードの複雑度を計算する関数などが含まれることがあります。

技術的詳細

このコミットの主要な技術的課題は、短絡評価される論理演算子 (&&, ||) の右オペランドに対する競合検出器の計測を、そのオペランドが実際に実行される場合にのみ適用することです。

racewalknode 関数は、ASTノードを再帰的に走査し、競合検出のための計測コードを挿入するGoコンパイラの重要な部分です。従来の racewalknode では、OANDAND (論理AND) と OOROR (論理OR) のケースにおいて、右オペランド (n->right) の計測がコメントアウトされていました。これは、「より複雑なツリー変換が必要であり、それが実行されるかどうかわからないため」という理由からでした。つまり、短絡評価の性質上、右オペランドが常に実行されるとは限らないため、単純に計測コードを挿入すると問題が生じる可能性があったのです。

このコミットでは、この問題を解決するために以下の変更が導入されました。

racewalknode における OANDAND および OOROR の処理変更:
- 左オペランド (n->left) は常に評価されるため、通常通り racewalknode(&n->left, init, wr, 0); で計測されます。
- 右オペランド (n->right) については、新しいアプローチが取られます。
  - n->right が実行されるかどうかは条件に依存するため、その計測コードはメインの init リストではなく、n->right 自体の ninit リストに追加されるように変更されました。
  - 具体的には、racewalknode(&n->right, &l, wr, 0); のように、一時的な NodeList *l を使用して右オペランドの計測コードを収集します。
  - その後、appendinit(&n->right, l); という新しいヘルパー関数を呼び出し、収集した計測コードを n->right ノードの ninit リストに「追加」します。これにより、n->right が実際に評価されるときにのみ、その計測コードが実行されるようになります。
appendinit ヘルパー関数の導入:
- この新しい関数は、subr.c にある既存の addinit 関数に似ていますが、init リストを「前置」するのではなく「追加」します。
- ONAME や OLITERAL のような単純なノードの場合、複数の参照が存在する可能性があるため、OCONVNOP (変換なしの操作) ノードを導入し、その ninit に計測コードを保持するようにします。これにより、元のノードのセマンティクスを壊さずに計測コードを挿入できます。
- n->ninit = concat(n->ninit, init); を使用して、既存の ninit リストに新しい計測コードを追加します。
- n->ullman = UINF; を設定することで、このノードのUllman数を無限大（非常に高コスト）に設定します。これは、競合検出器の計測が挿入されたノードは、コンパイラが「安価」と見なすべきではないことを示唆しています。
subr.c の ullmancalc の変更:
- OANDAND および OOROR のケースで、flag_race (競合検出器が有効な場合) に ul = UINF; を設定するロジックが追加されました。
- これは、競合検出器が有効な場合、これらの論理演算子の評価コストが、計測コードの挿入によって高くなる可能性があることをコンパイラに伝えるためです。これにより、コンパイラはこれらのノードを含む式に対して、より慎重な最適化戦略を取るようになります。
テストケースの更新 (mop_test.go):
- TestRaceFailingAnd2 と TestRaceFailingOr2 の名前がそれぞれ TestRaceAnd2 と TestRaceOr2 に変更されました。これは、以前はこれらのケースがコンパイラによって適切に計測されていなかった（"failing"）が、今回の変更によって適切に計測されるようになったことを示唆しています。
- テストコード自体は、&& や || の右オペランドにデータ競合を引き起こす可能性のある操作（例: 共有変数 x へのアクセス）を含み、競合検出器がそれを正しく検出できることを検証します。

これらの変更により、Goの競合検出器は論理AND/OR演算子の短絡評価のセマンティクスを正しく理解し、右オペランドが実際に実行される場合にのみ、その部分のメモリアクセスを計測するようになりました。これにより、競合検出の精度と効率が向上します。

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

`src/cmd/gc/racewalk.c`

// racewalknode関数のOANDANDとOORORのケース
 	case OANDAND:
 	case OOROR:
 	\tracewalknode(&n->left, init, wr, 0);
-\t\t// It requires more complex tree transformation,
-\t\t// because we don\'t know whether it will be executed or not.
-\t\t//racewalknode(&n->right, init, wr, 0);
+\t\t// walk has ensured the node has moved to a location where
+\t\t// side effects are safe.
+\t\t// n->right may not be executed,
+\t\t// so instrumentation goes to n->right->ninit, not init.
+\t\tl = nil;
+\t\tracewalknode(&n->right, &l, wr, 0);
+\t\tappendinit(&n->right, l);
 	\tgoto ret;

// 新しいヘルパー関数appendinitの追加
+static void
+appendinit(Node **np, NodeList *init)
+{
+\tNode *n;
+\n+\tif(init == nil)
+\t\treturn;
+\n+\tn = *np;
+\tswitch(n->op) {
+\tcase ONAME:
+\tcase OLITERAL:
+\t\t// There may be multiple refs to this node;
+\t\t// introduce OCONVNOP to hold init list.
+\t\tn = nod(OCONVNOP, n, N);\
+\t\tn->type = n->left->type;\
+\t\tn->typecheck = 1;\
+\t\t*np = n;\
+\t\tbreak;\
+\t}
+\tn->ninit = concat(n->ninit, init);\
+\tn->ullman = UINF;\
+}

`src/cmd/gc/subr.c`

// ullmancalc関数のOANDANDとOORORのケース
 	case OANDAND:
 	case OOROR:
 	\t// hard with race detector
 	\tif(flag_race) {
 	\t\tul = UINF;
 	\t\tgoto out;
 	\t}

`src/pkg/runtime/race/testdata/mop_test.go`

// テスト関数名の変更
-func TestRaceFailingAnd2(t *testing.T) {
+func TestRaceAnd2(t *testing.T) {

-func TestRaceFailingOr2(t *testing.T) {
+func TestRaceOr2(t *testing.T) {

コアとなるコードの解説

`racewalk.c` の変更

OANDAND / OOROR の計測ロジック:
- 以前は右オペランドの計測がコメントアウトされていましたが、今回の変更で有効化されました。
- racewalknode(&n->right, &l, wr, 0); は、右オペランド n->right を再帰的にウォークし、その過程で生成された計測コードを一時的な NodeList l に収集します。
- appendinit(&n->right, l); は、収集した計測コード l を n->right ノード自身の初期化リスト n->ninit に追加します。これにより、n->right が実際に評価される（短絡評価されずに実行される）場合にのみ、その計測コードが実行されるようになります。
appendinit 関数:
- この新しいヘルパー関数は、指定されたノード *np の ninit リストに、与えられた init リストのノードを追加します。
- ONAME や OLITERAL のようなノードは、コンパイラ内で複数回参照される可能性があるため、直接 ninit を変更すると問題が生じる可能性があります。そのため、OCONVNOP (変換なしの操作) ノードを新しく作成し、その ninit に計測コードを格納することで、元のノードの参照を壊さずに計測コードを挿入します。
- n->ullman = UINF; は、このノードのUllman数を無限大に設定します。Ullman数は、コンパイラが式の評価コストを推定するために使用する値です。UINF に設定することで、このノード（およびそれに付随する計測コード）が「安価ではない」ことをコンパイラに伝え、不適切な最適化を防ぎます。

`subr.c` の変更

ullmancalc の OANDAND / OOROR ケース:
- flag_race が有効な場合（競合検出器がオンの場合）、論理AND/OR演算子のUllman数を UINF に設定します。
- これは、racewalk.c での計測コード挿入により、これらの演算子の実際の実行コストが増加することをコンパイラに明示的に伝えるためのものです。これにより、コンパイラはこれらの演算子を含むコードに対して、より保守的な最適化戦略を採用するようになります。

`mop_test.go` の変更

テスト関数名の変更:
- TestRaceFailingAnd2 と TestRaceFailingOr2 が TestRaceAnd2 と TestRaceOr2 に変更されたことは、このコミットによって、以前は適切に計測されていなかった（または競合が検出されなかった）ケースが、正しく計測され、競合が検出されるようになったことを示しています。
- これらのテストは、論理AND/OR演算子の右オペランドが実行されるパスで意図的にデータ競合を発生させ、競合検出器がそれを正しく報告するかどうかを検証します。

これらの変更により、Goの競合検出器は、論理AND/OR演算子の短絡評価のセマンティクスを尊重しつつ、その右オペランドが実際に実行される場合にのみ、適切な計測を行うようになりました。これにより、競合検出の正確性が向上し、不必要なオーバーヘッドが削減されます。

参考にした情報源リンク

Go Race Detector Documentation: https://go.dev/doc/articles/race_detector
Go Compiler Internals (general concepts): https://go.dev/blog/go1.1 (Go 1.1のリリースノートにはRace Detectorの導入について記載があります)
Short-circuit evaluation: https://en.wikipedia.org/wiki/Short-circuit_evaluation
Ullman number (compiler optimization context): https://en.wikipedia.org/wiki/Ullman_number (一般的なコンパイラの概念として)
Go source code (for context on cmd/gc, racewalk.c, subr.c): https://github.com/golang/go
Go AST and compiler passes: (Specific documentation is scarce, but general compiler design principles apply. Reading the source code is often the best way to understand.)