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

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ exp/ssa において、ローカルなメモリ割り当て（Alloc）をSSAレジスタに「リフト」し、完全に剪定されたSSA形式を構築するための主要な変更を導入します。これにより、後続の最適化や解析の精度とパフォーマンスが向上します。

コミット

commit 867121585ad4b524ae7b6de31ab13432a4e11ce3
Author: Alan Donovan <adonovan@google.com>
Date:   Thu Feb 21 11:11:57 2013 -0500

    exp/ssa: build fully pruned SSA form.
    
    Overview: Function.finish() now invokes the "lifting" pass which replaces local allocs and loads and stores to such cells by SSA registers.  We use very standard machinery:
    
    (1) we build the dominator tree for the function's control flow graph (CFG) using the "Simple" Lengauer-Tarjan algorithm.  (Very "simple" in fact: even simple path compression is not yet implemented.)
    
    In sanity-checking mode, we cross check the dominator tree against an alternative implementation using a simple iterative dataflow algorithm.
    This all lives in dom.go, along with some diagnostic printing routines.
    
    (2) we build the dominance frontier for the entire CFG using the Cytron et al algorithm.  The DF is represented as a slice of slices, keyed by block index.  See buildDomFrontier() in lift.go.
    
    (3) we determine for each Alloc whether it can be lifted: is it only subject to loads and stores?  If so, we traverse the iterated dominance frontier (IDF) creating φ-nodes; they are not prepended to the blocks yet.
    See liftAlloc() in lift.go.
    
    (4) we perform the SSA renaming algorithm from Cytron et al, replacing all loads to lifted Alloc cells by the value stored by the dominating store operation, and deleting the stores and allocs.  See rename() in lift.go.
    
    (5) we eliminate unneeded φ-nodes, then concatenate the remaining ones with the non-deleted instructions of the block into a new slice.  We eliminate any lifted allocs from Function.Locals.
    
    To ease reviewing, I have avoided almost all optimisations at this point, though there are many opportunities to explore.  These will be easier to understand as follow-up changes.
    
    All the existing tests (pending CL 7313062) pass.  (Faster!)
    
    Details:
    
    "NaiveForm" BuilderMode flag suppresses all the new logic.
    Exposed as 'ssadump -build=N'.
    
    BasicBlock:
    - add .Index field (b.Func[b.Index]==b), simplifying
      algorithms such as Kildall-style dataflow with bitvectors.
    - rename the Name field to Comment to better reflect its
      reduced purpose.  It now has a String() method.
    - 'dom' field holds dominator tree node; private for now.
    - new predIndex method.
    - hasPhi is now a method
    
    dom.go:
    - domTree: a new struct for a node in a dominator tree.
    - buildDomTree builds the dominator tree using the simple
      variant Lengauer/Tarjan algorithm with Georgiadis'
      bucket optimizations.
    - sanityCheckDomTree builds dominance relation using
      Kildall-style dataflow and ensures the same result is
      obtained.
    - printDomTreeDot prints the CFG/DomTree in GraphViz format.
    
    blockopt.go:
    - perform a mark/sweep pass to eliminate unreachable
      cycles; the previous prune() opt would only eliminate
      trivially dead blocks.  (Needed for LT algo.)
    - using .Index, fuseblocks can now delete fused blocks directly.
    - delete prune().
    
    sanity.go: more consistency checks:
    - Phi with missing edge value
    - local Alloc instructions must appear in Function.Locals.
    - BasicBlock.Index, Func consistency
    - CFG edges are all intraprocedural.
    - detect nils in BasicBlock.Instrs.
    - detect Function.Locals with Heap flag set.
    - check fn.Blocks is nil if empty.
    
    Also:
    - Phi now has Comment field for debugging.
    - Fixed bug in Select.Operands()
      (took address of temporary copy of field)
    - new Literal constructor zeroLiteral().
    - algorithms steal private fields Alloc.index,
      BasicBlock.gaps to avoid allocating maps.
    - We print Function.Locals in DumpTo.
    - added profiling support to ssadump.
    
    R=iant, gri
    CC=golang-dev
    https://golang.org/cl/7229074

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

https://github.com/golang/go/commit/867121585ad4b524ae7b6de31ab13432a4e11ce3

元コミット内容

このコミットは、Go言語の実験的なSSA (Static Single Assignment) パッケージ exp/ssa に、完全に剪定されたSSA形式を構築するための「リフティング」パスを導入するものです。これまでのSSA形式は、ローカル変数に対して明示的なロード（読み込み）とストア（書き込み）命令を持つ「素朴な」形式でした。このコミットにより、Function.finish() メソッドが新しいリフティングパスを呼び出し、ローカルな Alloc（メモリ割り当て）とそれらへのロード/ストア操作をSSAレジスタに置き換えることで、より最適化に適したSSA形式を生成します。

主な変更点は以下の通りです。

1. 支配木 (Dominator Tree) の構築: 関数の制御フローグラフ (CFG) の支配木を、Lengauer-Tarjanアルゴリズムの「Simple」バリアントを使用して構築します。デバッグモードでは、Kildallスタイルのデータフローアルゴリズムによる代替実装との相互チェックも行われます。
2. 支配フロンティア (Dominance Frontier) の構築: Cytron et al. のアルゴリズムを使用して、CFG全体の支配フロンティアを構築します。
3. φ-ノードの挿入: 各 Alloc がリフト可能かどうか（ロードとストアのみの対象であるか）を判断し、反復支配フロンティア (IDF) を走査してφ-ノードを生成します。
4. SSAリネームアルゴリズム: Cytron et al. のSSAリネームアルゴリズムを実行し、リフトされた Alloc セルへのすべてのロードを、支配的なストア操作によって格納された値に置き換え、ストアと Alloc 命令自体を削除します。
5. 不要なφ-ノードの削除と命令の連結: 不要なφ-ノードを削除し、残りのφ-ノードと削除されていないブロックの命令を新しいスライスに連結します。リフトされた Alloc は Function.Locals からも削除されます。

この変更は、既存のテストをすべてパスし、パフォーマンスの向上も報告されています。また、"NaiveForm" ビルダーモードフラグ (ssadump -build=N) を使用することで、この新しいロジックを抑制し、素朴なSSA形式を生成することも可能です。

変更の背景

このコミットの背景には、コンパイラの最適化におけるSSA形式の重要性があります。SSA形式は、各変数が一度だけ定義されるようにプログラムを変換する中間表現であり、データフロー解析や最適化を大幅に簡素化します。しかし、初期のSSA構築では、すべてのローカル変数をメモリ上の場所として扱い、明示的なロード/ストア命令を生成する「素朴な」形式が用いられることがあります。

この素朴な形式は、その後の最適化パスでレジスタ割り当てや他の変換を行う際に、余分なロード/ストア命令がオーバーヘッドとなる可能性があります。そこで、このコミットでは、素朴なSSA形式から、より最適化に適した「完全に剪定されたSSA形式 (fully pruned SSA form)」への変換パスを導入しています。

「リフティング (lifting)」と呼ばれるこのプロセスは、ローカルなメモリ割り当て（スタック上の変数など）をSSAレジスタに昇格させることを目的としています。これにより、メモリへのアクセスが減り、データフローがより明確になるため、コンパイラがより効果的な最適化（例: 共通部分式除去、定数伝播など）を実行できるようになります。

この変更は、GoコンパイラのSSAバックエンドの成熟度を高め、将来的な最適化の基盤を強化する重要なステップと言えます。

前提知識の解説

このコミットを理解するためには、以下のコンパイラ最適化に関する基本的な概念を理解しておく必要があります。

1. 制御フローグラフ (Control Flow Graph, CFG)

プログラムの実行パスを抽象化したグラフ構造です。ノードは「基本ブロック (Basic Block)」を表し、エッジは制御フローの遷移を表します。基本ブロックは、入り口が一つで出口が一つであり、内部に分岐を含まない命令のシーケンスです。

2. SSA (Static Single Assignment) 形式

SSA形式は、プログラム中の各変数が一度だけ定義されるように変換された中間表現です。もし同じ変数に複数の定義がある場合、SSA形式ではその変数を新しい「バージョン」として扱います（例: x1, x2, x3）。複数の制御フローパスが合流し、同じ変数に異なる定義が到達する可能性がある場所では、「φ-ノード (phi-node)」と呼ばれる特別な命令が挿入されます。φ-ノードは、どのパスから制御が到達したかに応じて、適切なバージョンの値を選択します。

例:

// 元のコード
x = 1
if (cond) {
  x = 2
}
y = x + 3

// SSA形式
x1 = 1
if (cond) {
  x2 = 2
}
x3 = φ(x1, x2) // φ-ノード
y1 = x3 + 3

SSA形式は、データフロー解析を簡素化し、多くのコンパイラ最適化（定数伝播、共通部分式除去、デッドコード削除など）を効率的に実行するための基盤となります。

3. 支配 (Dominance)

CFGにおいて、ノード A がノード B を「支配する (dominates)」とは、A から B へのすべてのパスが A を通過する場合を言います。特に、A が B を直接支配し、A と B の間に他の支配ノードが存在しない場合、A は B の「直接支配者 (immediate dominator, idom)」と呼ばれます。

4. 支配木 (Dominator Tree)

CFGの支配関係を木構造で表現したものです。各ノードの親は、そのノードの直接支配者になります。支配木は、SSA形式の構築や他のデータフロー解析において重要な役割を果たします。

5. 支配フロンティア (Dominance Frontier, DF)

ノード X の支配フロンティアは、X が支配するノード Y のうち、Y の直接の先行ノード P が X によって支配されないような P の集合です。簡単に言えば、X の支配フロンティアは、X が支配する領域から外に出るエッジのターゲットとなるブロックの集合です。φ-ノードの挿入位置を決定するために使用されます。

6. Lengauer-Tarjan アルゴリズム

支配木を効率的に構築するためのアルゴリズムです。このコミットでは、その「Simple」バリアントが使用されています。

7. Cytron et al. アルゴリズム

SSA形式を構築するための標準的なアルゴリズムです。特に、支配フロンティアを利用してφ-ノードの挿入位置を決定し、その後に変数のリネームを行う手法が有名です。

8. リフティング (Lifting)

この文脈での「リフティング」とは、メモリ上の変数（Alloc によって割り当てられたもの）をSSAレジスタに昇格させるプロセスを指します。これにより、メモリへのロード/ストア命令が不要になり、変数の値がSSAレジスタとして直接扱われるようになります。これは、コンパイラがより効率的なコードを生成するための重要なステップです。

技術的詳細

このコミットは、GoのSSAバックエンドにおける「リフティング」パスの実装に焦点を当てています。これは、コンパイラ最適化の分野で確立された複数のアルゴリズムを組み合わせて実現されています。

1. 支配木の構築 (dom.go)

• Lengauer-Tarjan (LT) アルゴリズム: 支配木構築の標準的なアルゴリズムです。このコミットでは、Georgiadis et al. のバケット最適化を適用した「Simple」バリアントが使用されています。この最適化により、バケットのサイズが1より大きくなる必要がなくなります。
• domNode 構造体: 支配木のノードを表す新しい構造体 domNode が導入されました。これには、対応する BasicBlock、直接支配者 (Idom)、子ノード (Children)、ツリー内のレベル、pre/postオーダー番号、およびLTアルゴリズムの作業状態（semi, parent, ancestor）が含まれます。
• ltDfs, ltEval, ltLink: LTアルゴリズムのDFS、EVAL、LINKステップを実装するヘルパー関数です。
• sanityCheckDomTree: デバッグおよび検証のために、支配木の正しさをチェックする機能が追加されました。これは、Kildallスタイルのデータフロー解析（「Dragon」本のアルゴリズム10.16）によって計算された支配関係と比較することで行われます。これにより、LTアルゴリズムの実装が正しいことを保証します。
• printDomTreeDot, printDomTreeText: 支配木をGraphViz形式やテキスト形式で出力する診断ルーチンが追加されました。

2. 支配フロンティアの構築 (lift.go)

• domFrontier 型: 各ブロックの支配フロンティアの集合を表現するための新しい型 domFrontier が導入されました。これは、Block.Index をキーとするスライスのスライスとして実装されています。
• buildDomFrontier: Cytron et al. のアルゴリズムを使用して、関数全体の支配フロンティアを構築します。このアルゴリズムは、支配木のポストオーダー順にノードを走査し、各ノードの支配フロンティアを計算します。

3. リフティングパス (lift.go)

lift(fn *Function) 関数がリフティングパスの主要なロジックを実装しています。

• リフト可能な Alloc の特定: liftAlloc 関数は、Alloc がレジスタにリフト可能かどうかを判断します。リフト可能な Alloc は、ロードとストア操作のみの対象であり、集約型（配列や構造体）ではないものに限られます。
• φ-ノードの挿入: Cytron et al. のアルゴリズムの主要ループが liftAlloc 内で実装されています。これは、反復支配フロンティア (IDF) を走査し、必要な場所にφ-ノードを生成します。newPhiMap は、各基本ブロックに挿入される新しいφ-ノードの集合を記録します。
• SSAリネーム (rename 関数): 支配木のプリオーダー走査によってSSAリネームアルゴリズムが実行されます。
  • 各φ-ノードは、関連する Alloc の新しい名前となります。
  • Store 命令は削除され、その値が支配的なストア操作として記録されます。
  • Load 命令は、支配的なストア操作によって格納された値に置き換えられ、Load 命令自体も削除されます。
  • 後続ブロックのφ-ノードのエッジは、現在のリネームマップに基づいて更新されます。
  • renaming マップは、Alloc をその支配的な格納値にマッピングするために使用されます。
• 不要なφ-ノードの削除: リフティング後、参照されていないφ-ノードは削除されます。
• 命令の圧縮と Function.Locals の更新: BasicBlock.Instrs から削除された命令（Alloc, Load, Store）のギャップを埋め、新しいφ-ノードをブロックの先頭に連結します。リフトされた Alloc は Function.Locals からも削除されます。

4. その他の変更

• BasicBlock の変更:
  • Index フィールドが追加され、Kildallスタイルのデータフローアルゴリズムなどでビットベクトルを使用する際に、ブロックのインデックスとして利用されます。
  • Name フィールドが Comment にリネームされ、その目的がより明確になりました。
  • dom フィールドが追加され、支配木ノードへの参照を保持します。
  • predIndex メソッドと hasPhi メソッドが追加されました。
• blockopt.go の変更:
  • 到達不能なブロックを削除するためのマーク＆スイープパスが導入され、以前の prune() 関数が削除されました。これは、Lengauer-Tarjanアルゴリズムの前提条件を満たすために必要です。
  • fuseBlocks 関数が BasicBlock.Index を使用して、融合されたブロックを直接削除できるようになりました。
• sanity.go の変更:
  • SSA表現の不変条件をチェックするためのより多くの整合性チェックが追加されました。これには、φ-ノードのエッジ値の欠落、ローカル Alloc が Function.Locals に存在すること、BasicBlock.Index と Func の整合性、CFGエッジがプロシージャ内であること、BasicBlock.Instrs 内の nil 命令の検出、Function.Locals の Heap フラグのチェック、空の fn.Blocks のチェックなどが含まれます。
• literal.go の変更:
  • 新しい zeroLiteral() コンストラクタが追加され、指定された型のゼロ値を表すリテラルを生成できるようになりました。
• ssadump.go の変更:
  • 新しいビルドモードフラグ N (NaiveForm) が追加され、リフティングパスを抑制できるようになりました。
  • CPUプロファイリングのサポートが追加されました。

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

このコミットにおけるコアとなるコードの変更は、主に以下のファイルに集中しています。

1. src/pkg/exp/ssa/dom.go (新規ファイル):
   • 支配木構築のための domNode 構造体、Lengauer-Tarjanアルゴリズムの実装 (ltDfs, ltEval, ltLink, buildDomTree)、および支配木の検証 (sanityCheckDomTree) と出力 (printDomTreeDot, printDomTreeText) ルーチンが含まれます。
2. src/pkg/exp/ssa/lift.go (新規ファイル):
   • リフティングパスの主要なロジックが含まれます。支配フロンティアの構築 (buildDomFrontier)、リフト可能な Alloc の特定とφ-ノードの挿入 (liftAlloc)、SSAリネームアルゴリズム (rename)、および関連するヘルパー型 (domFrontier, blockSet, newPhi, newPhiMap) が定義されています。
3. src/pkg/exp/ssa/func.go:
   • Function.finish() メソッドが変更され、新しいリフティングパス (lift(f)) を呼び出すようになりました。
   • BasicBlock 構造体に Index, Comment, dom, gaps フィールドが追加されました。
   • BasicBlock の String() メソッド、predIndex() メソッド、hasPhi() メソッドが追加されました。
   • removeNilBlocks() ヘルパー関数が追加されました。
   • numberRegisters() 関数が追加され、SSAレジスタに番号を割り当てるようになりました。
4. src/pkg/exp/ssa/blockopt.go:
   • 到達不能なブロックを削除するロジックが prune() から deleteUnreachableBlocks() に変更され、マーク＆スイープ方式になりました。
   • jumpThreading と fuseBlocks が BasicBlock.Index を利用するように変更されました。
5. src/pkg/exp/ssa/sanity.go:
   • SSA表現の整合性チェックが大幅に強化され、新しいリフティングパスによって導入される可能性のある不整合を検出できるようになりました。
6. src/pkg/exp/ssa/ssa.go:
   • BasicBlock, Alloc, Phi 構造体に新しいフィールドが追加されました。
   • Phi 構造体に Comment フィールドが追加されました。

コアとなるコードの解説

src/pkg/exp/ssa/dom.go

このファイルは、支配木を構築するための中心的なロジックを含んでいます。

• domNode:

  type domNode struct {
      Block     *BasicBlock // the basic block; n.Block.dom == n
      Idom      *domNode    // immediate dominator (parent in dominator tree)
      Children  []*domNode  // nodes dominated by this one
      Level     int         // level number of node within tree; zero for root
      Pre, Post int         // pre- and post-order numbering within dominator tree
      // Working state for Lengauer-Tarjan algorithm
      semi     *domNode // semidominator
      parent   *domNode // parent in DFS traversal of CFG
      ancestor *domNode // ancestor with least sdom
  }
  

  domNode は支配木の各ノードを表し、対応する基本ブロック、直接支配者、子ノード、およびLTアルゴリズムの内部状態を保持します。

• buildDomTree(f *Function): この関数は、Lengauer-Tarjanアルゴリズムを使用して関数の支配木を構築します。

  1. 各 BasicBlock に対応する domNode を初期化します。
  2. ltDfs を呼び出して、CFGの深さ優先探索を行い、preorder番号とsemidominatorを計算します。
  3. 逆preorder順にノードを走査し、semidominatorと直接支配者を計算します。Georgiadisのバケット最適化が適用されています。
  4. 最後に、支配木のpre/postオーダー番号とレベルを割り当てます。
  5. デバッグモードでは、sanityCheckDomTree を呼び出して支配木の正しさを検証します。

src/pkg/exp/ssa/lift.go

このファイルは、リフティングパスの主要な実装を含んでいます。

• domFrontier:

  type domFrontier [][]*BasicBlock
  

  支配フロンティアを表す型です。buildDomFrontier 関数によって構築されます。

• lift(fn *Function): この関数がリフティングパスのエントリポイントです。

  1. buildDomTree(fn) を呼び出して支配木を構築します。
  2. buildDomFrontier(fn) を呼び出して支配フロンティアを構築します。
  3. 各 Alloc に対して liftAlloc を呼び出し、リフト可能かどうかを判断し、必要なφ-ノードを newPhis マップに記録します。
  4. rename(fn.Blocks[0], renaming, newPhis) を呼び出して、SSAリネームアルゴリズムを実行します。これは支配木を走査し、ロード/ストアを置き換え、φ-ノードのエッジを更新します。
  5. 不要なφ-ノードを削除し、ブロックの命令を圧縮します。
  6. リフトされた Alloc を fn.Locals から削除します。

• liftAlloc(df domFrontier, alloc *Alloc, newPhis newPhiMap) bool: この関数は、特定の Alloc がリフト可能かどうかを判断し、リフト可能であればφ-ノードを挿入します。

  1. 集約型（配列や構造体）の Alloc はリフトしません。
  2. Alloc の参照元を調べ、ロードとストア以外の操作があればリフト不可と判断します。
  3. Alloc の定義ブロック（ストア命令と Alloc 命令自体）を defblocks に記録します。
  4. Cytron et al. のφ-ノード挿入アルゴリズムの主要部分を実行します。defblocks から開始し、反復支配フロンティアを走査して、φ-ノードが必要なブロックに新しいφ-ノードを作成し、newPhis マップに追加します。

• rename(u *BasicBlock, renaming []Value, newPhis newPhiMap): この関数は、SSAリネームアルゴリズムを実装しています。支配木の深さ優先走査を行います。

  1. 現在のブロック u に関連付けられた新しいφ-ノードを処理し、それらを renaming マップの新しい名前として設定します。
  2. ブロック u 内の命令を走査します。
     • Store 命令の場合、その Alloc へのストアを削除し、ストアされた値を renaming マップの現在の値として設定します。
     • UnOp（ロード）命令の場合、その Alloc からのロードを、renaming マップの現在の値に置き換え、ロード命令自体を削除します。
  3. 現在のブロック u の後続ブロックのφ-ノードのエッジを更新します。
  4. 支配木の子ノードに対して再帰的に rename を呼び出します。この際、renaming マップのコピーを渡すことで、各サブツリーが独立したリネーム状態を持つようにします。

src/pkg/exp/ssa/func.go

• Function.finish():

  func (f *Function) finish() {
      // ... (既存のロジック) ...
  
      if f.Prog.mode&NaiveForm == 0 {
          // For debugging pre-state of lifting pass:
          // numberRegisters(f)
          // f.DumpTo(os.Stderr)
  
          lift(f) // ここでリフティングパスが呼び出される
      }
  
      numberRegisters(f) // リフティング後にレジスタ番号を再割り当て
  
      // ... (既存のロジック) ...
  }
  

  この変更により、SSAコード生成の最終段階で lift(f) が呼び出され、素朴なSSA形式から完全に剪定されたSSA形式への変換が行われます。NaiveForm フラグが設定されている場合は、このリフティングパスはスキップされます。

関連リンク

• Static Single Assignment form: https://en.wikipedia.org/wiki/Static_single_assignment_form
• Dominator (graph theory): https://en.wikipedia.org/wiki/Dominator_(graph_theory)
• Lengauer-Tarjan algorithm: https://en.wikipedia.org/wiki/Lengauer%E2%80%93Tarjan_dominators_algorithm
• Dominance frontier: https://en.wikipedia.org/wiki/Dominance_frontier

参考にした情報源リンク

• Ron Cytron et al. 1991. Efficiently computing SSA form...: http://doi.acm.org/10.1145/115372.115320 (SSA形式構築の古典的な論文)
• Cooper, Harvey, Kennedy. 2001. A Simple, Fast Dominance Algorithm. Software Practice and Experience 2001, 4:1-10.: http://www.hipersoft.rice.edu/grads/publications/dom14.pdf (支配アルゴリズムに関する論文)
• Daniel Berlin, llvmdev mailing list, 2012.: http://lists.cs.uiuc.edu/pipermail/llvmdev/2012-January/046638.html (LLVM開発メーリングリストでのSSA構築に関する議論)
• Georgiadis et al, Finding Dominators in Practice, JGAA 2006,: http://jgaa.info/accepted/2006/GeorgiadisTarjanWerneck2006.10.1.pdf (Lengauer-Tarjanアルゴリズムの最適化に関する論文)
• "Dragon" book (Compilers: Principles, Techniques, and Tools): コンパイラ設計に関する標準的な教科書。特にデータフロー解析とSSAに関する章が関連します。