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

このコミットは、Goコンパイラのガベージコレクタにおけるエスケープ解析の改善に関するものです。特に、関数の入力パラメータから出力パラメータへのデータの流れをより正確に追跡できるようにすることで、エスケープ解析の精度を向上させることを目的としています。これにより、不要なヒープ割り当てを減らし、プログラムのパフォーマンスを最適化します。

コミット

commit 507fcf37d2a5565fbe5d13b24f7082464b17dc3a
Author: Luuk van Dijk <lvd@golang.org>
Date:   Mon Oct 29 13:38:21 2012 +0100

    cmd/gc: escape analysis to track flow of in to out parameters.
    
    includes step 0: synthesize outparams, from 6600044
    includes step 1,2: give outparams loopdepth 0 and verify unchanged results
             generate esc:$mask tags, but still tie to sink if a param has mask != 0
    from 6610054
    
    adds final steps:
    - have esccall generate n->escretval, a list of nodes the function results flow to
    - use these in esccall and ORETURN/OAS2FUNC/and f(g())
    - only tie parameters to sink if tag is absent, otherwise according to mask, tie them to escretval
    
    R=rsc, bradfitz
    CC=dave, gobot, golang-dev, iant, rsc
    https://golang.org/cl/6741044

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

https://github.com/golang/go/commit/507fcf37d2a5565fbe5d13b24f7082464b17dc3a

元コミット内容

このコミットは、Goコンパイラのcmd/gc（Goコンパイラのフロントエンドとバックエンドの一部）におけるエスケープ解析のロジックを拡張し、関数の入力パラメータから出力パラメータへのデータの流れを追跡できるようにします。

これまでの変更（コミット6600044と6610054）に加えて、以下の最終ステップが追加されています。

• esccall関数がn->escretval（関数の結果が流れるノードのリスト）を生成するように変更。
• esccall、ORETURN（関数の戻り値）、OAS2FUNC（多値戻り値の代入）、およびf(g())のような関数呼び出しのコンテキストでn->escretvalを使用。
• パラメータにエスケープタグ（esc:$mask）が存在しない場合にのみシンク（ヒープ）に紐付け、タグが存在する場合はマスクに従ってescretvalに紐付ける。

変更の背景

Go言語では、ガベージコレクションの効率を最大化するために、コンパイラが「エスケープ解析」と呼ばれる最適化を行います。エスケープ解析は、変数がヒープに割り当てられるべきか、それともスタックに割り当てられるべきかを決定します。スタック割り当てはヒープ割り当てよりもはるかに高速であり、ガベージコレクタの負荷を軽減します。

このコミット以前のエスケープ解析は、関数の入力パラメータが出力パラメータにどのように影響するかを完全に追跡できていませんでした。例えば、関数がポインタを受け取り、そのポインタを戻り値として返す場合、そのポインタがヒープにエスケープするかどうかを正確に判断することが困難でした。

この変更の背景には、以下のような課題がありました。

1. 不正確なエスケープ解析: 入力から出力へのフローが考慮されていないため、実際にはスタックに割り当てられるべき変数が誤ってヒープに割り当てられることがありました。これは、不要なメモリ割り当てとガベージコレクションのオーバーヘッドを引き起こし、プログラムのパフォーマンスを低下させます。
2. 最適化の機会の損失: コンパイラが変数の寿命を正確に判断できないため、より積極的な最適化（例えば、スタック割り当て）を適用する機会を逃していました。
3. 複雑な関数呼び出しのハンドリング: 多値戻り値やネストされた関数呼び出し（例: f(g())）のような複雑なシナリオにおいて、エスケープ解析が不十分でした。

このコミットは、これらの課題に対処し、エスケープ解析の精度を向上させることで、Goプログラムの実行時パフォーマンスを改善することを目的としています。特に、関数の入出力パラメータ間のデータフローを明示的に追跡することで、より多くの変数をスタックに割り当てられるようにし、ガベージコレクションのプレッシャーを軽減します。

前提知識の解説

このコミットを理解するためには、以下のGoコンパイラとエスケープ解析に関する概念を理解しておく必要があります。

1. エスケープ解析 (Escape Analysis): Goコンパイラが行う最適化の一つで、変数がプログラムの実行中にどこにメモリを割り当てられるべきかを決定します。

   • スタック割り当て: 関数内で宣言され、その関数の実行が終了すると不要になる変数は、通常スタックに割り当てられます。スタックは高速で、ガベージコレクションの対象外です。
   • ヒープ割り当て: 変数が関数のスコープを超えて参照される可能性がある場合（例: グローバル変数に代入される、関数の戻り値として返される、チャネルを通じて送信されるなど）、その変数はヒープに割り当てられます。ヒープはガベージコレクションの対象であり、割り当てと解放にオーバーヘッドが伴います。 エスケープ解析の目的は、可能な限り多くの変数をスタックに割り当てることで、ヒープ割り当ての数を減らし、ガベージコレクションの頻度と時間を削減することです。

2. cmd/gc: Goコンパイラの主要部分です。gcは「Go Compiler」の略で、Goソースコードを機械語に変換する役割を担います。エスケープ解析は、このgcの最適化フェーズの一部として実行されます。

3. NodeとNodeList: Goコンパイラ内部では、プログラムの抽象構文木（AST）がNode構造体で表現されます。NodeListはNodeのリンクリストです。コンパイラはこれらのNodeを走査し、プログラムの構造と意味を解析します。

4. in-parametersとout-parameters:

   • in-parameters (入力パラメータ): 関数に渡される引数です。
   • out-parameters (出力パラメータ): 関数の戻り値です。 エスケープ解析では、これらのパラメータがどのようにメモリを共有し、どこにデータが流れるかを追跡することが重要です。

5. loopdepth: エスケープ解析において、変数が宣言されたスコープの深さを示す概念です。ループやラベルによってスコープが深くなることがあります。loopdepthが小さいほど、変数の寿命が短い可能性があり、スタック割り当ての候補になりやすいです。このコミットでは、出力パラメータにloopdepth 0を与えることで、それらが関数の戻り値として特別に扱われるようにしています。

6. sink (シンク): エスケープ解析における「シンク」は、変数がヒープにエスケープする場所を抽象的に表す概念です。変数がシンクに「紐付けられる」とは、その変数がヒープに割り当てられる必要があると判断されることを意味します。

7. esc:$maskタグ: エスケープ解析の結果をエンコードするために使用されるメタデータです。関数の型情報に付与され、どの入力パラメータがどの出力パラメータにエスケープするか、あるいはヒープにエスケープするかを示すビットマスクとして機能します。これにより、コンパイラは関数呼び出しサイトで、引数がどこにエスケープするかを効率的に判断できます。

8. esccall関数: Goコンパイラのエスケープ解析フェーズで、関数呼び出しを処理する主要な関数です。この関数は、呼び出しの引数と戻り値のエスケープ特性を分析します。

9. n->escretval: このコミットで導入されたNode構造体の新しいフィールドです。関数呼び出しのNodeにおいて、その関数の戻り値が流れる先のノードのリストを保持します。これにより、関数の戻り値のエスケープ特性をより正確に追跡できるようになります。

10. ORETURN, OAS2FUNC, OCALLMETH, OCALLFUNC, OCALLINTER: これらはGoコンパイラ内部のASTノードのオペレーションコードです。

    • ORETURN: return文を表します。
    • OAS2FUNC: 多値戻り値の関数呼び出しの結果を複数の変数に代入する操作（例: x, y = f()）を表します。
    • OCALLMETH: メソッド呼び出しを表します。
    • OCALLFUNC: 通常の関数呼び出しを表します。
    • OCALLINTER: インターフェースメソッド呼び出しを表します。 これらの操作において、データのフローとエスケープ特性を正確に追跡することが、このコミットの主要な目的です。

技術的詳細

このコミットは、Goコンパイラのエスケープ解析のロジックを大幅に強化し、特に「入力パラメータから出力パラメータへのフロー追跡」に焦点を当てています。以下にその技術的詳細を掘り下げます。

1. escretvalの導入と利用

• Node構造体への追加: src/cmd/gc/go.hにおいて、Node構造体にNodeList* escretval;フィールドが追加されました。これは、関数呼び出しのASTノード（OCALLMETH, OCALLFUNC, OCALLINTER）において、その関数の戻り値が流れる先のノードのリストを保持するために使用されます。これにより、コンパイラは関数の戻り値がどこに「エスケープ」するかを、より粒度高く追跡できるようになります。
• esccallでの生成: src/cmd/gc/esc.cのesccall関数内で、呼び出される関数の戻り値の型に基づいて、ダミーのONAMEノード（PAUTOクラス）が生成され、n->escretvalリストに追加されます。これらのダミーノードは、呼び出し元関数内の戻り値の「プレースホルダー」として機能し、エスケープ解析が戻り値のフローを追跡できるようにします。
• ORETURNでの利用: ORETURNノードの処理において、関数の戻り値が単一の関数呼び出しの結果である場合（例: return f()）、その呼び出しのescretvalが現在の関数の出力パラメータ（PPARAMOUT）に紐付けられます。これにより、f()の戻り値のエスケープ特性が、呼び出し元の関数の戻り値に適切に伝播されます。
• OAS2FUNCでの利用: x,y = f()のような多値戻り値の代入において、f()の呼び出しノードのescretvalリストが、代入先の変数リスト（n->list）に紐付けられます。これにより、各戻り値が対応する変数にどのようにエスケープするかが正確に追跡されます。
• f(g())のようなネストされた呼び出し: esccall関数内で、f(g())のような形式の呼び出しが検出された場合、g()の呼び出しノードのescretvalがf()の引数リストとして扱われます。これにより、g()の戻り値のエスケープ特性がf()の引数に適切に伝播されます。

2. escassignfromtag関数の導入

• 目的: この新しいヘルパー関数は、関数の型に付与されたエスケープタグ（esc:$mask）に基づいて、ソースノード（src）からデスティネーションノードリスト（dsts）へのエスケープフローを制御します。
• 動作:
  • タグがEscUnknownの場合、ソースはシンク（ヒープ）に紐付けられます。
  • タグのビットマスク（em）を解析し、各ビットが対応するデスティネーションノード（dstsリストの要素）へのエスケープを示す場合、escassignを呼び出してフローを確立します。
  • これにより、コンパイラは、事前に計算されたエスケープタグを利用して、関数呼び出しの引数やレシーバのエスケープ特性を効率的に判断し、適切なエスケープ先（シンクまたはescretval）に紐付けることができます。

3. loopdepthのセマンティクス変更

• src/cmd/gc/go.hにおいて、escloopdepthのコメントが更新され、-1: global, 0: return variables, 1:function top levelと明記されました。これは、出力パラメータ（戻り値）がloopdepth 0として扱われることを示唆しており、エスケープ解析がこれらの変数を特別に扱うためのヒントとなります。

4. 相互再帰関数のエスケープ解析の改善

• escfunc関数内で、e->recursiveフラグが設定されている（相互再帰関数グループ内である）場合、関数の出力パラメータ（PPARAMOUT）が明示的にシンクに紐付けられます。これは、相互再帰関数グループでは戻り値のフローを完全に追跡することが困難な場合があるため、安全策としてヒープエスケープと見なすことで、誤った最適化を防ぎます。

5. テストケースの追加と修正

• test/escape2.goの既存のテストケースが修正され、新しいエスケープ解析のロジックが正しく動作することを確認しています。特に、foo75, foo75a, foo76a, foo76c, foo76e, foo77aなどの関数で、以前はヒープエスケープとされていたものがスタックエスケープ（does not escape）として正しく検出されるようになっています。
• test/escape5.goという新しいテストファイルが追加されました。このファイルには、入力パラメータから出力パラメータへのエスケープフローを詳細にテストする多数のシナリオが含まれています。
  • leaktoret, leaktoret2, leaktoret22などの関数は、入力ポインタが出力ポインタにエスケープするケースをテストします。
  • leaktosinkは、グローバル変数への代入によるヒープエスケープをテストします。
  • f1からf7までの関数は、様々な関数呼び出しパターンにおけるエスケープ解析の挙動を検証します。
  • leakrecursive1, leakrecursive2は、相互再帰関数におけるエスケープ解析の挙動をテストします。

これらの変更により、Goコンパイラのエスケープ解析は、関数の入出力パラメータ間の複雑なデータフローをより正確に理解し、より多くの変数をスタックに割り当てることが可能になります。結果として、生成されるバイナリの実行効率が向上し、ガベージコレクションのオーバーヘッドが削減されます。

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

このコミットで変更された主要なファイルと、それぞれの役割は以下の通りです。

• src/cmd/gc/esc.c:
  • Goコンパイラのエスケープ解析の主要なロジックが実装されているファイルです。
  • このコミットのほとんどの変更がここで行われています。esccall、escassign、escfuncなどの関数が修正・拡張され、新しいescassignfromtag関数が追加されています。
• src/cmd/gc/go.h:
  • Goコンパイラの内部で使用される共通のヘッダーファイルです。
  • Node構造体にescretvalフィールドが追加され、escloopdepthのコメントが更新されています。
• test/escape2.go:
  • 既存のエスケープ解析のテストケースが含まれるファイルです。
  • このコミットでは、新しいエスケープ解析のロジックに合わせて、既存のテストの期待される結果（コメント内のERRORメッセージ）が更新されています。
• test/escape5.go:
  • このコミットで新しく追加されたテストファイルです。
  • 特に、関数の入力パラメータから出力パラメータへのエスケープフローを詳細に検証するための、多数の新しいテストケースが含まれています。

コアとなるコードの解説

src/cmd/gc/esc.c の変更点

1. EscState構造体へのrecursiveフィールド追加:

   struct EscState {
       // ...
       int     recursive;      // recursive function or group of mutually recursive functions.
   };
   

   EscStateはエスケープ解析の状態を保持する構造体です。recursiveフィールドが追加され、現在解析中の関数が相互再帰グループの一部であるかどうかを示すために使用されます。

2. analyze関数でのrecursiveフラグの設定:

   analyze(NodeList *all, int recursive) {
       // ...
       e->recursive = recursive;
       // ...
   }
   

   analyze関数はエスケープ解析の開始点であり、ここでEscStateのrecursiveフィールドが初期化されます。

3. escfunc関数での相互再帰関数の戻り値の処理:

   escfunc(EscState *e, Node *func) {
       // ...
       // in a mutually recursive group we lose track of the return values
       if(e->recursive)
           for(ll=curfn->dcl; ll; ll=ll->next)
               if(ll->n->op == ONAME && ll->n->class == PPARAMOUT)
                   escflows(e, &e->theSink, ll->n);
       // ...
   }
   

   相互再帰関数グループ内では、戻り値の正確なフローを追跡するのが困難な場合があります。このコードは、そのような場合に、関数の出力パラメータ（PPARAMOUT）を安全策としてシンク（ヒープ）に紐付けることで、誤ったスタック割り当てを防ぎます。

4. esc関数でのOCALLMETH, OCALLFUNC, OCALLINTER, OAS2FUNC, ORETURNの処理強化:

   • 関数呼び出し (OCALLMETH, OCALLFUNC, OCALLINTER): 以前はesccall(e, n);が呼び出されるだけでしたが、このコミットではesccallの内部ロジックが大幅に強化されています。
   • 多値戻り値の代入 (OAS2FUNC):

     case OAS2FUNC:  // x,y = f()
         // esccall already done on n->rlist->n. tie it's escretval to n->list
         lr=n->rlist->n->escretval;
         for(ll=n->list; lr && ll; lr=lr->next, ll=ll->next)
             escassign(e, ll->n, lr->n);
         if(lr || ll)
             fatal("esc oas2func");
         break;
     

     OAS2FUNCはx, y = f()のような多値戻り値の代入を処理します。n->rlist->nは関数呼び出しノード（f()）であり、そのescretval（関数の戻り値が流れるノードのリスト）を、代入先の変数リスト（n->list）に紐付けます。これにより、f()の各戻り値が対応する変数にどのようにエスケープするかが正確に追跡されます。
   • return文 (ORETURN):

     case ORETURN:
         ll=n->list;
         if(count(n->list) == 1 && curfn->type->outtuple > 1) {
             // OAS2FUNC in disguise
             // esccall already done on n->list->n
             // tie n->list->n->escretval to curfn->dcl PPARAMOUT's
             ll = n->list->n->escretval;
         }
     
         for(lr = curfn->dcl; lr && ll; lr=lr->next) {
             if (lr->n->op != ONAME || lr->n->class != PPARAMOUT)
                 continue;
             escassign(e, lr->n, ll->n);
             ll = ll->next;
         }
         // ...
     

     ORETURNは関数の戻り値を処理します。もし戻り値が単一の関数呼び出しの結果であり、かつ多値戻り値を持つ場合（f(g())のようなケース）、その呼び出しのescretvalを現在の関数の出力パラメータ（PPARAMOUT）に紐付けます。これにより、ネストされた呼び出しの戻り値のエスケープ特性が適切に伝播されます。

5. escassign関数でのOCALLMETH, OCALLFUNC, OCALLINTERの処理:

   case OCALLMETH:
   case OCALLFUNC:
   case OCALLINTER:
       if(count(src->escretval) != 1)
           fatal("escassign from call %+N", src);
       escflows(e, dst, src->escretval->n);
       break;
   

   関数呼び出しの結果が別の変数に代入される場合、呼び出しノードのescretval（この場合は単一の戻り値）が代入先のdstに紐付けられます。

6. escassignfromtag関数の追加:

   static void
   escassignfromtag(EscState *e, Strlit *note, NodeList *dsts, Node *src)
   {
       int em;
   
       em = parsetag(note);
   
       if(em == EscUnknown) {
           escassign(e, &e->theSink, src);
           return;
       }
           
       for(em >>= EscBits; em && dsts; em >>= 1, dsts=dsts->next)
           if(em & 1)
               escassign(e, dsts->n, src);
   
       if (em != 0 && dsts == nil)
           fatal("corrupt esc tag %Z or messed up escretval list\\n", note);
   }
   

   この新しい関数は、関数の型に付与されたエスケープタグ（note）を解析し、そのタグが示すビットマスクに基づいて、srcノードからdstsリスト内の対応するノードへのエスケープフローを確立します。タグが不明な場合は、srcをシンクに紐付けます。これは、コンパイラが事前に計算されたエスケープ情報を利用して、効率的にフローを決定するための重要なメカニズムです。

7. esccall関数の大幅な変更: esccall関数は、関数呼び出しのエスケープ解析の中心です。

   • f(g())の処理:

     if(a->type->etype == TSTRUCT && a->type->funarg) // f(g()).
         ll = a->escretval;
     

     f(g())のようなネストされた呼び出しの場合、内側の呼び出しg()の戻り値（a->escretval）が、外側の呼び出しf()の引数リストとして扱われます。
   • ローカル関数と相互再帰グループの処理:

     // function in same mutually recursive group.  Incorporate into flow graph.
     // ...
     // set up out list on this call node
     for(lr=fn->ntype->rlist; lr; lr=lr->next)
         n->escretval = list(n->escretval, lr->n->left);  // type.rlist ->  dclfield -> ONAME (PPARAMOUT)
     

     同じ相互再帰グループ内の関数呼び出しの場合、呼び出しノードnのescretvalが、呼び出される関数の戻り値の型情報（fn->ntype->rlist）に基づいて設定されます。
   • インポートされた関数や完全に解析された関数の処理:

     // Imported or completely analyzed function.  Use the escape tags.
     // ...
     // set up out list on this call node with dummy auto ONAMES in the current (calling) function.
     // ...
     // Receiver.
     if(n->op != OCALLFUNC)
         escassignfromtag(e, getthisx(fntype)->type->note, n->escretval, n->left->left);
     
     for(t=getinargx(fntype)->type; ll; ll=ll->next) {
         src = ll->n;
         // ...
         escassignfromtag(e, t->note, n->escretval, src);
         // ...
     }
     

     インポートされた関数や既に解析済みの関数については、その型情報に付与されたエスケープタグ（t->note）を利用して、引数やレシーバのエスケープ特性を判断します。escassignfromtag関数がここで使用され、タグに基づいて引数がシンクに紐付けられるか、またはn->escretvalに紐付けられるかが決定されます。

src/cmd/gc/go.h の変更点

1. Node構造体へのescretvalフィールド追加:

   struct  Node
   {
       // ...
       // Escape analysis.
       NodeList* escflowsrc;   // flow(this, src)
       NodeList* escretval;    // on OCALLxxx, list of dummy return values
       int     escloopdepth;   // -1: global, 0: return variables, 1:function top level, increased inside function for every loop or label to mark scopes
       // ...
   };
   

   escretvalは、関数呼び出しノード（OCALLMETH, OCALLFUNC, OCALLINTER）において、その関数の戻り値が流れる先のノードのリストを保持するために導入されました。これにより、戻り値のエスケープ特性をより正確に追跡できるようになります。 escloopdepthのコメントも更新され、0: return variablesが追加されています。これは、戻り値が特別なloopdepthを持つことを示し、エスケープ解析がこれらを特別に扱うためのヒントとなります。

test/escape2.go と test/escape5.go の変更点

これらのテストファイルは、上記のエスケープ解析の変更が正しく機能することを確認するために使用されます。特に、test/escape5.goは、入力から出力へのエスケープフローの様々なシナリオを網羅的にテストしており、このコミットの意図を明確に示しています。

例えば、leaktoret(p *int) *intのような関数では、入力パラメータpが戻り値としてエスケープすることが期待され、コンパイラはleaking param: p to resultというエラーメッセージを出力します。また、leaktoret22(p, q *int) (*int, *int)のような多値戻り値の関数では、どの入力パラメータがどの戻り値にエスケープするかが詳細にテストされています。

これらのコード変更は、Goコンパイラのエスケープ解析の精度を大幅に向上させ、結果としてGoプログラムのメモリ使用量とパフォーマンスを最適化することに貢献します。

関連リンク

• https://github.com/golang/go/commit/507fcf37d2a5565fbe5d13b24f7082464b17dc3a
• https://golang.org/cl/6741044 (Go Code Review - CL 6741044)

参考にした情報源リンク

• Go Escape Analysis: https://go.dev/doc/articles/go_mem (Go公式ドキュメントのメモリ管理に関する記事)
• Go Compiler Internals (一般的なGoコンパイラの構造理解のため): https://go.dev/blog/go-compiler-internals
• Go AST (抽象構文木) の理解のため: https://pkg.go.dev/go/ast
• Goコンパイラのソースコード (特にsrc/cmd/compile/internal/gcディレクトリ)
• Goのガベージコレクションに関する一般的な情報