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

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

このコミットは、Goコンパイラのcmd/gcにおけるエスケープ解析の動作を変更し、関数呼び出しグラフの依存関係順に解析を実行するように修正したものです。特に、相互再帰的な関数群を強連結成分（Strongly Connected Components: SCC）としてまとめて解析することで、より効率的かつ正確なエスケープ解析を可能にしています。

コミット

commit 9fe424737b59dd7c769ae5acfdaca8f511f40d25
Author: Russ Cox <rsc@golang.org>
Date:   Thu Jun 7 03:15:09 2012 -0400

    cmd/gc: run escape analysis in call graph dependency order
    
    If there are mutually recursive functions, there is a cycle in
    the dependency graph, so the order is actually dependency order
    among the strongly connected components: mutually recursive
    functions get put into the same batch and analyzed together.
    (Until now the entire package was put in one batch.)
    
    The non-recursive case (single function, maybe with some
    closures inside) will be able to be more precise about inputs
    that escape only back to outputs, but that is not implemented yet.
    
    R=ken2
    CC=golang-dev, lvd
    https://golang.org/cl/6304050

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

https://github.com/golang/go/commit/9fe424737b59dd7c769ae5acfdaca8f511f40d25

元コミット内容

Goコンパイラのcmd/gcにおけるエスケープ解析を、関数呼び出しグラフの依存関係順に実行するように変更します。相互再帰的な関数が存在する場合、依存関係グラフにはサイクル（循環）が生じます。この変更により、解析の順序は強連結成分（SCC）間の依存関係順となり、相互再帰的な関数は同じバッチとしてまとめて解析されるようになります。これまでの実装では、パッケージ全体が単一のバッチとして解析されていました。

非再帰的なケース（単一の関数、あるいは内部にいくつかのクロージャを持つ関数）では、入力が戻り値にのみエスケープする場合について、より精密な解析が可能になるはずですが、この機能はまだ実装されていません。

変更の背景

Goコンパイラのエスケープ解析は、変数がスタックに割り当てられるべきか、それともヒープに割り当てられるべきかを決定する重要な最適化ステップです。これまでの実装では、エスケープ解析はパッケージ内のすべての関数を一度に処理していました。このアプローチは、特に相互再帰的な関数群が存在する場合に問題がありました。

相互再帰関数は、互いに呼び出し合うため、関数呼び出しグラフ上でサイクルを形成します。このようなサイクルが存在すると、個々の関数を独立して解析することが困難になり、解析の精度が低下したり、不必要なヒープ割り当てが発生したりする可能性がありました。パッケージ全体を単一のバッチとして解析することは、解析の粒度が粗く、最適化の機会を逃す原因にもなり得ました。

このコミットの目的は、関数呼び出しグラフの構造をより正確に利用し、相互再帰関数を強連結成分として識別し、それらをまとめて解析することで、エスケープ解析の精度と効率を向上させることにありました。これにより、コンパイラは変数のライフタイムをより正確に判断し、可能な限りスタック割り当てを促進することで、ガベージコレクションの負荷を軽減し、プログラムの実行性能を向上させることが期待されます。

前提知識の解説

エスケープ解析 (Escape Analysis)

エスケープ解析は、コンパイラ最適化の一種で、プログラム内の変数がそのスコープを「エスケープ」するかどうかを決定します。ここでいう「エスケープ」とは、変数がその宣言された関数やブロックのライフタイムを超えて参照され続ける可能性があることを意味します。

  • スタック割り当て (Stack Allocation): 関数内で宣言されたローカル変数は、通常、関数の呼び出しスタックに割り当てられます。関数が終了すると、そのスタックフレームは破棄され、変数のメモリも解放されます。これは非常に高速な割り当て・解放メカニズムです。
  • ヒープ割り当て (Heap Allocation): 変数がそのスコープをエスケープする場合（例: ポインタが関数から返される、グローバル変数に代入されるなど）、その変数はヒープに割り当てられる必要があります。ヒープはプログラム全体で共有されるメモリ領域であり、ガベージコレクタによって管理されます。ヒープ割り当てはスタック割り当てよりもコストが高く、ガベージコレクションのオーバーヘッドも発生します。

エスケープ解析の目的は、変数がヒープに割り当てられる必要がないことを証明し、可能な限りスタックに割り当てることで、メモリ使用量を減らし、ガベージコレクションの頻度と時間を短縮し、プログラムのパフォーマンスを向上させることです。

呼び出しグラフ (Call Graph) と 依存関係グラフ (Dependency Graph)

  • 呼び出しグラフ: プログラム内の関数と、それらの関数が互いにどのように呼び出し合うかを示す有向グラフです。ノードは関数を表し、エッジは呼び出し関係を表します（例: 関数Aが関数Bを呼び出す場合、AからBへのエッジが存在します）。
  • 依存関係グラフ: 呼び出しグラフと密接に関連していますが、より広範な意味で、あるエンティティが別のエンティティに依存している関係を示すグラフです。エスケープ解析の文脈では、ある関数のエスケープ挙動が別の関数のエスケープ挙動に影響を与える場合に依存関係が生じます。

強連結成分 (Strongly Connected Components - SCC)

有向グラフにおいて、強連結成分（SCC）とは、グラフの頂点の部分集合であり、その部分集合内の任意の2つの頂点uとvについて、uからvへのパスとvからuへのパスの両方が存在するような最大の集合を指します。簡単に言えば、SCC内のすべての頂点は互いに到達可能です。

SCCは、グラフ内の「サイクル」（循環）を特定するのに役立ちます。相互再帰的な関数群は、関数呼び出しグラフにおいてSCCを形成します。例えば、関数AがBを呼び出し、BがAを呼び出す場合、AとBはSCCを形成します。

Sedgewick, Algorithms, Second Edition, p. 482

このコミットのコードコメントで参照されている「Sedgewick, Algorithms, Second Edition, p. 482」は、おそらくRobert Sedgewickの有名なアルゴリズムの教科書を指しています。このページには、有向グラフの強連結成分を見つけるためのアルゴリズムが記載されている可能性が高いです。一般的に、SCCを見つけるための主要なアルゴリズムには以下の2つがあります。

  • Tarjanのアルゴリズム: 深度優先探索（DFS）を1回実行するだけでSCCを特定できる効率的なアルゴリズムです。
  • Kosarajuのアルゴリズム: 2回のDFS実行を必要としますが、概念的には比較的理解しやすいアルゴリズムです。

Goコンパイラのエスケープ解析では、これらのアルゴリズムのいずれか、またはその派生形が、相互再帰関数群（SCC）を識別するために使用されています。

技術的詳細

このコミットの主要な技術的変更点は、エスケープ解析の実行順序を、関数呼び出しグラフの強連結成分（SCC）に基づいた依存関係順に変更したことです。

  1. SCCの検出:

    • Goコンパイラは、関数呼び出しグラフを構築し、そのグラフ上でSCCを検出します。これは、visitgen、visit、visitcode、visitcodelistといった新しい関数群によって実現されます。
    • visit関数は、深度優先探索（DFS）の原理に基づいてグラフを走査し、各ノードの訪問順序（walkgen）と、そのノードから到達可能な最小の訪問順序（min）を記録します。
    • SCCの検出には、Sedgewickのアルゴリズム（おそらくTarjanのアルゴリズムの変種）が用いられています。
    • 「2つの仮想ノード」の適応: コードコメントに記載されているように、各関数はグラフ内で2つの仮想ノード（nとn+1）として扱われます。関数自体のノード番号をnとし、n+1から探索を開始します。もし探索がn+1を最小値として返した場合、それは単一の関数とそれに含まれるクロージャからなる自明な成分（非再帰）であることを意味します。もし探索がnを最小値として返した場合、それはn+1からnへのパスが存在したことを意味し、関数群が相互再帰的であることを示します。この区別により、非再帰的な関数に対してはより精密な解析が可能になります。
    • クロージャの扱い: 隠れたクロージャ関数（n->curfn != N）は、それ自体が強連結成分のルートになることはできません。これにより、クロージャは常にそれが定義されている関数と同じ成分に強制的に含まれ、両者の変数間のエイリアシングをより正確にモデル化できます。

  2. バッチ処理:

    • SCCが検出されると、そのSCCに属するすべての関数が1つの「バッチ」としてまとめられます。
    • analyze関数がこのバッチを受け取り、そのバッチ内の関数に対してエスケープ解析を実行します。
    • analyze関数は、バッチが相互再帰的であるか（recursive引数）に応じて、解析の挙動を調整する可能性があります（ただし、コミットメッセージでは非再帰ケースでの精密化はまだ実装されていないと述べられています）。

  3. エスケープ解析の状態管理:

    • 以前はグローバル変数として管理されていたエスケープ解析の状態（theSink, dsts, loopdepthなど）が、EscStateという新しい構造体にカプセル化されました。
    • これにより、escfunc, esclist, esc, escassign, esccall, escflows, escflood, escwalk, esctagといった既存のエスケープ解析関連関数は、EscStateへのポインタを引数として受け取るように変更されました。
    • EscStateの導入は、複数のバッチ（SCC）を独立して、あるいは並行して解析するための基盤を提供します。各バッチは独自の解析状態を持つことができるため、解析のモジュール性と再利用性が向上します。

  4. 解析のフロー:

    • escapes関数が全体のオーケストレーションを行います。まず、すべての関数ノードを初期化し、visit関数を呼び出してSCCを検出します。
    • visit関数は、SCCを検出するたびに、そのSCCに属する関数群をanalyze関数に渡してエスケープ解析を実行させます。
    • analyze関数内で、従来のフロー解析（escfuncなど）とフラッドフィルアルゴリズム（escflood、escwalk）が実行され、変数のエスケープ挙動が決定されます。

この変更により、Goコンパイラは、相互再帰関数のような複雑な依存関係を持つコードに対しても、より正確で効率的なエスケープ解析を実行できるようになり、結果として生成されるバイナリのパフォーマンス向上に貢献します。

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

変更は主にsrc/cmd/gc/esc.cファイルに集中しています。

  1. 新しいSCC検出関連関数の追加:

    • static NodeList *stack;
    • static uint32 visitgen;
    • static uint32 visit(Node*);
    • static uint32 visitcode(Node*, uint32);
    • static uint32 visitcodelist(NodeList*, uint32);
    • static void analyze(NodeList*, int);
    • enum { EscFuncUnknown = 0, EscFuncPlanned, EscFuncStarted, EscFuncTagged, };

  2. escapes関数の変更:

    • 以前はescapes関数が直接すべての関数に対してescfuncを呼び出していましたが、このコミットではSCC検出ロジックが追加され、visit関数を介してanalyze関数が呼び出されるようになりました。
    • escapes関数は、まずすべての関数のwalkgenを初期化し、トップレベルの関数（クロージャではない関数）からvisitを呼び出してSCC検出を開始します。
    • その後、再度walkgenを初期化し、analyze関数を呼び出す部分が削除され、visit関数内でSCCが検出されるたびにanalyzeが呼び出される構造に変更されました。

  3. EscState構造体の導入と関連関数の変更:

    • typedef struct EscState EscState; と struct EscState { ... }; が追加され、エスケープ解析の状態をカプセル化します。
    • 以前グローバル変数だったtheSink, dsts, loopdepth, pdepth, dstcount, edgecount, noescがEscStateのメンバーになりました。
    • escfunc, esclist, esc, escloopdepthlist, escloopdepth, escassign, esccall, escflows, escflood, escwalk, esctagといったエスケープ解析の主要な関数が、第一引数としてEscState *eを受け取るように変更されました。これにより、これらの関数は特定の解析セッションの状態にアクセスできるようになります。

  4. analyze関数の追加:

    • static void analyze(NodeList *all, int recursive)が追加されました。この関数は、検出されたSCC（all）と、それが相互再帰的であるかどうかのフラグ（recursive）を受け取り、そのバッチに対して実際のエスケープ解析を実行します。
    • analyze関数内で、EscStateが初期化され、従来のescfunc、escflood、esctagの呼び出しが行われます。

  5. Node構造体へのescフィールドの追加:

    • Node構造体にescフィールドが追加され、関数のエスケープ解析の状態（EscFuncUnknown, EscFuncPlanned, EscFuncStarted, EscFuncTagged）を追跡するために使用されます。

コアとなるコードの解説

強連結成分 (SCC) 検出ロジック

  • visit(Node *n):

    • この関数は、SCC検出のための深度優先探索（DFS）の主要な部分です。
    • n->walkgenはノードnが訪問された順序を記録します。visitgenはグローバルな訪問カウンタです。
    • min変数は、現在のノードnから到達可能なノードの中で最も小さいwalkgen値を追跡します。
    • stackは、DFS中に訪問中のノードを保持するスタックです。
    • 関数が呼び出しグラフを再帰的に探索し、visitcodelistやvisitcodeを介して他の関数呼び出しをたどります。
    • if((min == n->walkgen || min == n->walkgen+1) && n->curfn == N)の条件がSCCのルートを特定します。
      • min == n->walkgenは、現在のノードnがSCCのルートであり、そのSCCが相互再帰的であることを示します（n+1からnへのパスが存在）。
      • min == n->walkgen+1は、現在のノードnがSCCのルートであり、そのSCCが単一の関数（非再帰）であることを示します。
      • n->curfn == Nは、トップレベルの関数（クロージャではない）のみがSCCのルートになり得るという制約です。
    • SCCのルートが特定されると、stackからそのSCCに属するノードが取り出され、analyze関数に渡されます。

  • visitcodelist(NodeList *l, uint32 min) と visitcode(Node *n, uint32 min):

    • これらは、AST（抽象構文木）を走査し、関数呼び出しやクロージャの定義を見つけてvisit関数を再帰的に呼び出すヘルパー関数です。
    • min値を伝播させ、呼び出し先から返される最小のwalkgen値を更新します。

エスケープ解析の状態管理とバッチ処理

  • EscState構造体:

    • エスケープ解析の実行に必要なすべての状態（シンクノード、フローの宛先リスト、ループ深度、デバッグ用の深さ、診断カウンタ、非エスケープノードのリスト）を保持します。
    • これにより、エスケープ解析がグローバルな状態に依存せず、独立したコンテキストで実行できるようになります。

  • analyze(NodeList *all, int recursive):

    • この関数は、SCC検出ロジックによって特定された関数群（all）と、それが再帰的であるかどうかのフラグ（recursive）を受け取ります。
    • 内部でEscStateのインスタンスを初期化し、その状態を使ってエスケープ解析の主要なステップ（escfunc、escflood、esctag）を呼び出します。
    • recursiveフラグは、将来的に再帰的なSCCと非再帰的なSCCで異なる最適化戦略を適用するためのフックとして機能します。

フロー解析関数の変更

  • escfunc, esclist, esc, escassign, esccall, escflows, escflood, escwalk, esctagといった既存の関数は、すべてEscState *eを第一引数として受け取るように変更されました。
  • これにより、これらの関数はグローバル変数ではなく、渡されたEscStateインスタンスのメンバーにアクセスして、解析の状態を読み書きします。例えば、theSinkはe->theSinkに、loopdepthはe->loopdepthに変わりました。
  • この変更は、エスケープ解析をよりモジュール化し、SCCごとに独立した解析を実行できるようにするために不可欠です。

これらの変更により、Goコンパイラのエスケープ解析は、関数間の複雑な依存関係、特に相互再帰をより効果的に処理できるようになり、コンパイラの最適化能力が向上しました。

関連リンク

参考にした情報源リンク