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

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

このコミットは、Goコンパイラ（gc）における評価順序の修正に関するものです。特に、関数呼び出しの評価順序が不正に並べ替えられる問題を解決し、インライン化との相互作用における問題を改善することを目的としています。この変更により、order.cという新しいファイルが導入され、式から副作用を持つ操作を分離し、ステートメントシーケンスに移動させることで、walkパスによる不正な並べ替えを防ぐための独立した順序付けパスが追加されました。

コミット

commit ee9bfb023a0cda29ee97eeec592d34c504e9705c
Author: Russ Cox <rsc@golang.org>
Date:   Wed Jan 25 17:53:50 2012 -0500

    gc: fix order of evaluation
    
    Pulling function calls out to happen before the
    expression being evaluated was causing illegal
    reorderings even without inlining; with inlining
    it got worse.  This CL adds a separate ordering pass
    to move things with a fixed order out of expressions
    and into the statement sequence, where they will
    not be reordered by walk.
    
    Replaces lvd's CL 5534079.
    
    Fixes #2740.
    
    R=lvd
    CC=golang-dev
    https://golang.org/cl/5569062

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

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

元コミット内容

gc: fix order of evaluation
    
Pulling function calls out to happen before the
expression being evaluated was causing illegal
reorderings even without inlining; with inlining
it got worse.  This CL adds a separate ordering pass
to move things with a fixed order out of expressions
and into the statement sequence, where they will
not be reordered by walk.
    
Replaces lvd's CL 5534079.
    
Fixes #2740.
    
R=lvd
CC=golang-dev
https://golang.org/cl/5569062

変更の背景

Goコンパイラ（gc）において、関数呼び出しが評価される式よりも前に実行されるように引き出される際、不正な評価順序の並べ替えが発生していました。この問題は、インライン化が行われない場合でも発生していましたが、インライン化が適用されるとさらに悪化しました。

コンパイラは、コードの最適化や変換を行う過程で、式の評価順序を調整することがあります。しかし、Go言語の仕様では、特定の操作（特に副作用を伴う関数呼び出しなど）には厳密な評価順序が定められています。このコミット以前のコンパイラは、これらの厳密な順序を維持できず、結果としてプログラムの動作が予測不能になったり、バグが発生したりする可能性がありました。

この問題に対処するため、副作用を持つ式（特に関数呼び出し）を、それらが評価されるべきステートメントシーケンスに明示的に移動させる新しい「順序付けパス」を導入する必要がありました。これにより、後続のwalkパス（コンパイラのASTトラバーサルと変換を行う主要なパス）が、これらの操作を誤って並べ替えることを防ぎます。

前提知識の解説

このコミットを理解するためには、以下の概念が重要です。

  • Goコンパイラ (gc): Go言語の公式コンパイラであり、ソースコードを機械語に変換します。gcは、複数のパス（フェーズ）を経てコンパイルを行います。
  • 抽象構文木 (AST): ソースコードの構文構造を木構造で表現したものです。コンパイラはASTを操作して、コードの解析、最適化、コード生成を行います。
  • 評価順序 (Order of Evaluation): プログラミング言語において、式やステートメントの各部分がどの順番で評価されるかを定めた規則です。Go言語では、特定の操作（例: 関数呼び出しの引数評価）には厳密な順序が保証されています。
  • 副作用 (Side Effect): 関数や式が、その戻り値以外に、プログラムの状態（変数、メモリ、I/Oなど）を変更する操作のことです。例えば、println関数は画面に何かを出力するという副作用を持ちます。
  • インライン化 (Inlining): コンパイラ最適化の一種で、関数呼び出しを、その関数の本体のコードで直接置き換えることです。これにより、関数呼び出しのオーバーヘッドが削減され、パフォーマンスが向上する可能性があります。しかし、インライン化はコードの構造を大きく変更するため、評価順序に関する問題を引き起こすことがあります。
  • walkパス: gcコンパイラの主要なパスの一つで、ASTを走査し、型チェック後のASTをさらに変換・最適化します。このパスは、式の簡略化やコード生成のための準備を行います。
  • Node構造体: gcコンパイラ内部でASTのノードを表す構造体です。n->ninitのようなフィールドは、そのノードに関連付けられた初期化ステートメントのリストを保持します。これは、副作用を持つ式を評価する前に実行する必要がある操作を格納するために使用されます。

技術的詳細

このコミットの核心は、Goコンパイラに新しい「順序付けパス」を導入することです。このパスは、order.cという新しいファイルで実装されており、pgen.cのcompile関数内でwalkパスの前に実行されます。

従来のコンパイラでは、式の中に副作用を持つ操作（特に関数呼び出し）が含まれている場合、walkパスがこれらの操作を、Go言語の仕様で定められた評価順序に反して並べ替えてしまう可能性がありました。これは、walkパスが式の構造を最適化する際に、副作用の順序を適切に考慮していなかったためです。

新しいorderパスの目的は、この問題を解決することです。具体的には、以下の処理を行います。

  1. 副作用の分離: 式の中から副作用を持つ部分（例: 関数呼び出し、make、new、recvなど）を特定します。
  2. 一時変数の導入: これらの副作用を持つ操作の結果を保持するための一時変数を導入します。
  3. ステートメントへの昇格: 副作用を持つ操作を、その結果を一時変数に代入するステートメントとして、現在の式の初期化リスト（n->ninit）または親のステートメントシーケンスに移動させます。
  4. 式の置き換え: 元の式の中の副作用を持つ操作を、新しく導入された一時変数への参照に置き換えます。

これにより、walkパスが処理するASTは、副作用が明示的なステートメントとして分離された状態になります。walkパスはステートメントの順序を変更しないため、副作用の評価順序が保証されるようになります。

特に、OCALLFUNC、OCALLMETH、OCALLINTER（関数呼び出し）、ORECV（チャネルからの受信）などの操作がこの順序付けパスの対象となります。これらの操作は、評価順序が厳密に定められているため、不正な並べ替えは深刻なバグにつながります。

order.c内の主要な関数は以下の通りです。

  • order(Node *fn): 指定された関数fnのボディ（fn->nbody）に対して順序付けパスを開始します。
  • orderstmt(Node *n, NodeList **out): 単一のステートメントnを順序付けし、生成されたステートメントをoutリストに追加します。
  • orderexpr(Node **np, NodeList **out): 単一の式*npを順序付けし、生成されたステートメントをoutリストに追加します。必要に応じて、式を一時変数への代入に変換します。
  • ordercallargs(NodeList **l, NodeList **out): 関数呼び出しの引数リストlを順序付けします。多値返却関数の場合は、copyretを使用して一時変数に結果をコピーします。
  • copyexpr(Node *n, Type *t, NodeList **init): 式nの値を一時変数にコピーし、その代入ステートメントをinitリストに追加します。

この変更は、コンパイラの内部構造に深く関わるものであり、Go言語のセマンティクス（意味論）を正しく実装するために不可欠な修正です。

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

このコミットでは、主に以下のファイルが変更されています。

  • src/cmd/gc/Makefile:
    • order.oがコンパイル対象に追加され、新しいorder.cファイルがビルドプロセスに含まれるようになります。
  • src/cmd/gc/go.h:
    • order関数のプロトタイプが追加されます。
    • addinit関数とcopyexpr関数のプロトタイプが追加されます。これらは、初期化リストへの追加や式のコピーに関連するヘルパー関数です。
  • src/cmd/gc/inl.c:
    • インライン化に関連するコードが修正され、inlconv2expr関数がNode **npを受け取るように変更されます。これにより、インライン化された式がorderパスによって適切に処理されるようになります。
    • addinit関数が使用されるようになります。
  • src/cmd/gc/order.c (新規ファイル):
    • 評価順序を修正するための新しいパスが実装されています。このファイルには、order、orderstmt、orderexprなどの主要な関数が含まれています。
  • src/cmd/gc/pgen.c:
    • compile関数内で、walkパスの前にorder(curfn)が呼び出されるようになります。これにより、orderパスがwalkパスの前に実行され、ASTの評価順序が修正されます。
  • src/cmd/gc/sinit.c:
    • init2関数内で、ONAMEノードがninitを持つ場合にfatalエラーを発生させるチェックが追加されます。これは、orderパスがninitを適切に処理していることを保証するためです。
  • src/cmd/gc/subr.c:
    • copyexpr関数が静的関数からグローバル関数に変更され、order.cから呼び出せるようになります。
    • addinit関数が追加されます。この関数は、ノードの初期化リストに新しいステートメントを追加するユーティリティです。
  • src/cmd/gc/typecheck.c:
    • OMAKEMAP, OMAKECHAN, OMAKESLICEのtypecheck処理において、n->listがnilに設定されるようになります。これは、orderパスがこれらのノードの構造を再構築するためです。
  • src/cmd/gc/walk.c:
    • walkstmtおよびwalkexpr関数内で、addinit関数が使用されるようになります。これにより、walkパスがノードの初期化リストを適切に処理し、orderパスによって導入されたステートメントを尊重するようになります。
    • ONAMEノードがwalkstmtの最後に残っている場合にfatalエラーを発生させるチェックが追加されます。これは、orderパスがONAMEノードを適切に変換していることを保証するためです。
  • test/fixedbugs/bug401.go、test/func8.go、test/reorder2.go:
    • 評価順序の問題をテストするための新しいテストケースが追加または修正されています。特にtest/reorder2.goは、様々な複雑な式における評価順序の挙動を検証しています。

コアとなるコードの解説

このコミットの最も重要な部分は、新しく追加されたsrc/cmd/gc/order.cファイルです。

src/cmd/gc/order.c

このファイルは、ASTを走査し、副作用を持つ式をステートメントに変換することで、評価順序を強制する役割を担います。

  • order(Node *fn):

    void
order(Node *fn)
{
    NodeList *out;
    out = nil;
    orderstmtlist(fn->nbody, &out);
    fn->nbody = out;
}

    この関数は、指定された関数fnのボディ（fn->nbody）を順序付けします。orderstmtlistを呼び出して、関数ボディ内のすべてのステートメントを処理し、結果として得られる順序付けされたステートメントのリストをfn->nbodyに再割り当てします。

  • orderstmtlist(NodeList *l, NodeList **out):

    static void
orderstmtlist(NodeList *l, NodeList **out)
{
    for(; l; l=l->next)
        orderstmt(l->n, out);
}

    ステートメントのリストを反復処理し、各ステートメントに対してorderstmtを呼び出します。

  • orderstmt(Node *n, NodeList **out):

    static void
orderstmt(Node *n, NodeList **out)
{
    // ... (various switch cases for different statement types)
    switch(n->op) {
    // ...
    case OAS2FUNC: // 多値返却関数からの代入
        orderinit(n, out);
        orderexprlist(n->list, out); // 左辺の式を順序付け
        ordercall(n->rlist->n, out); // 右辺の関数呼び出しを順序付け
        *out = list(*out, n);
        break;
    // ...
    case OCALLFUNC: // 関数呼び出しステートメント
    case OCALLINTER:
    case OCALLMETH:
        orderinit(n, out);
        ordercall(n, out); // 関数呼び出し自体を順序付け
        *out = list(*out, n);
        break;
    // ...
    case OFOR: // forループ
        orderinit(n, out);
        orderexprinplace(&n->ntest); // テスト式をインプレースで順序付け
        orderstmtinplace(&n->nincr); // インクリメントステートメントをインプレースで順序付け
        orderblock(&n->nbody); // ボディブロックを順序付け
        *out = list(*out, n);
        break;
    // ...
    }
}

    この関数は、様々な種類のステートメントを処理します。重要なのは、副作用を持つ可能性のある式（例: 代入の右辺、関数呼び出しの引数、forループの条件やインクリメント）に対してorderexprやorderexprinplaceを呼び出し、それらの副作用をoutリストに移動させることです。

  • orderexpr(Node **np, NodeList **out):

    static void
orderexpr(Node **np, NodeList **out)
{
    Node *n;
    n = *np;
    // ...
    orderinit(n, out); // ノードの初期化リストをoutに移動

    switch(n->op) {
    // ...
    case OCALLFUNC: // 関数呼び出し式
    case OCALLMETH:
    case OCALLINTER:
        ordercall(n, out); // 関数呼び出しを順序付け
        n = copyexpr(n, n->type, out); // 結果を一時変数にコピー
        break;

    case ORECV: // チャネルからの受信式
        n = copyexpr(n, n->type, out); // 結果を一時変数にコピー
        break;
    }
    *np = n; // 変換されたノードで元のポインタを更新
}

    この関数は、式を処理します。OCALLFUNCやORECVのような副作用を持つ式の場合、ordercallを呼び出して副作用を処理し、copyexprを使用して式の評価結果を一時変数にコピーします。これにより、元の式は一時変数への参照に置き換えられ、副作用はステートメントとしてoutリストに分離されます。

  • copyret(Node *n, NodeList **out):

    static NodeList*
copyret(Node *n, NodeList **out)
{
    // ...
    // 多値返却関数の結果を一時変数に代入するOAS2ノードを作成
    as = nod(OAS2, N, N);
    as->list = l1; // 左辺（一時変数リスト）
    as->rlist = list1(n); // 右辺（関数呼び出し）
    typecheck(&as, Etop);
    orderstmt(as, out); // 代入ステートメントを順序付け

    return l2; // 一時変数への参照リストを返す
}

    多値返却関数呼び出しの場合に、その結果を複数の新しい一時変数に代入するOAS2ステートメントを生成し、それをoutリストに追加します。これにより、多値返却関数の結果が明確に一時変数に格納され、その後の処理で安全に参照できるようになります。

src/cmd/gc/subr.c

  • addinit(Node **np, NodeList *init): 
    void
addinit(Node **np, NodeList *init)
{
    Node *n;
    if(init == nil)
        return;

    n = *np;
    switch(n->op) {
    case ONAME:
    case OLITERAL:
        // このノードへの複数の参照がある可能性があるため、
        // 初期化リストを保持するためにOCONVNOPを導入する。
        n = nod(OCONVNOP, n, N);
        n->type = n->left->type;
        n->typecheck = 1;
        *np = n;
        break;
    }
    n->ninit = concat(init, n->ninit);
}
    このヘルパー関数は、指定されたノード*npの初期化リスト（n->ninit）に、新しい初期化ステートメントのリストinitを追加します。ONAMEやOLITERALのようなノードの場合、それら自体が初期化リストを持つことは想定されていないため、OCONVNOP（変換操作なし）ノードを導入して、そのninitフィールドに初期化リストを格納します。これにより、副作用を持つ操作がノードに適切に関連付けられます。

これらの変更により、Goコンパイラは、Go言語の仕様に厳密に従って式の評価順序を保証できるようになり、特にインライン化されたコードや複雑な式における潜在的なバグが解消されます。

関連リンク

参考にした情報源リンク

  • コミットメッセージ自体
  • Go言語コンパイラの一般的な知識 (AST、評価順序、インライン化など)
  • Go言語のソースコード (特にsrc/cmd/gcディレクトリ内のファイル)