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

このコミットは、Go言語のリンカ（cmd/link）にデッドコード削除（Dead Code Removal）機能を実装するものです。これにより、最終的な実行可能ファイルから到達不能なコードやデータを排除し、バイナリサイズを削減することを目的としています。

コミット

commit 7dcc652f10a5ca74101381bb27b6755ee2ab4691
Author: Russ Cox <rsc@golang.org>
Date:   Mon Jan 13 23:08:10 2014 -0500

    cmd/link: implement dead code removal
    
    R=iant
    CC=golang-codereviews
    https://golang.org/cl/51470043

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

https://github.com/golang/go/commit/7dcc652f10a5ca74101381bb27b6755ee2ab4691

元コミット内容

cmd/link: implement dead code removal

R=iant
CC=golang-codereviews
https://golang.org/cl/51470043

変更の背景

Go言語のプログラムは、コンパイル時に静的にリンクされ、単一の実行可能バイナリが生成されます。このバイナリには、プログラムが実際に使用するコードやデータだけでなく、標準ライブラリや依存関係に含まれるものの、最終的に実行されない（到達不能な）コードやデータが含まれる可能性があります。このような「デッドコード」は、バイナリサイズを不必要に増大させ、ディスク使用量やロード時間、さらには配布時のネットワーク帯域に影響を与えます。

このコミットの背景には、Goバイナリのサイズを最適化し、より効率的な配布と実行を可能にするという目的があります。特に、組み込みシステムやコンテナ環境など、リソースが限られた環境では、バイナリサイズの削減は重要な課題となります。デッドコード削除は、コンパイラやリンカが行う主要な最適化の一つであり、Go言語の設計思想である「シンプルさと効率性」に合致する改善です。

前提知識の解説

リンカ (Linker)

リンカは、コンパイラによって生成された複数のオブジェクトファイル（コンパイルされたソースコードの断片）やライブラリを結合し、最終的な実行可能ファイルやライブラリを生成するプログラムです。この結合プロセスには、シンボル解決（異なるオブジェクトファイル間で参照される関数や変数のアドレスを解決する）や、必要に応じてコードの再配置（メモリ上の最終的な位置に合わせてアドレスを調整する）などが含まれます。

シンボル (Symbol)

シンボルは、プログラム内の関数、グローバル変数、定数などの名前付きエンティティを表します。リンカはこれらのシンボルを管理し、プログラム全体で正しく参照されるようにします。各シンボルには、その種類（関数、データなど）、サイズ、アドレスなどの情報が関連付けられています。

リロケーション (Relocation)

リロケーションは、プログラムがメモリにロードされる際に、コードやデータ内のアドレス参照を修正するプロセスです。コンパイル時には、特定の関数やデータが最終的にメモリ上のどこに配置されるか不明なため、相対アドレスやプレースホルダーが使用されます。リンカは、これらのプレースホルダーを実際のメモリ位置に解決するための「リロケーションエントリ」を生成し、実行時にローダーがこれを利用してアドレスを修正します。

マーク＆スイープアルゴリズム (Mark-and-Sweep Algorithm)

マーク＆スイープは、主にガベージコレクション（GC）で用いられるアルゴリズムですが、デッドコード削除にも応用されます。

1. マークフェーズ (Mark Phase): プログラムのエントリポイント（例: main関数）から開始し、そこから到達可能なすべてのコードやデータを「マーク」します。これは、関数呼び出し、データ参照、リロケーションエントリなどを辿ることで行われます。到達可能なものだけがマークされます。
2. スイープフェーズ (Sweep Phase): マークされなかった（到達不能な）コードやデータを「スイープ」（削除）します。これにより、不要なリソースが解放されます。

Goのリンカにおけるデッドコード削除は、このマーク＆スイープの概念をシンボルグラフに適用します。プログラムのエントリポイントからシンボル間の依存関係を辿り、到達可能なシンボルをマークし、マークされなかったシンボルを最終バイナリから除外します。

Goのコンパイルプロセス

Goのコンパイルプロセスは、ソースコードから最終的な実行可能バイナリを生成するまでの一連のステップです。

1. コンパイル: 各Goソースファイル（.go）がコンパイラによってオブジェクトファイル（.oまたはプラットフォーム固有の形式）にコンパイルされます。
2. アーカイブ: 複数のオブジェクトファイルがライブラリアーカイブ（.a）にまとめられることがあります。
3. リンク: リンカ（cmd/link）が、これらのオブジェクトファイルやアーカイブ、およびGoランタイムライブラリを結合して、単一の実行可能バイナリを生成します。この段階で、デッドコード削除のような最適化が適用されます。

技術的詳細

このコミットで実装されたデッドコード削除は、Goリンカのcmd/linkパッケージ内で行われます。基本的なアプローチは、マーク＆スイープガベージコレクションと同様です。

1. 到達可能性の特定: プログラムの開始シンボル（p.startSym、通常はmain関数など）を起点として、そこから到達可能なすべてのシンボルを特定します。これは、walkDead関数によって再帰的に行われます。

   • walkDead関数は、現在のシンボルがまだ到達可能としてマークされていない場合、それをマークし、そのシンボルが参照する他のシンボル（リロケーションターゲットや関数データ内のシンボル）を再帰的に辿ります。
   • リロケーションは、あるシンボルが別のシンボルを参照していることを示します。例えば、関数Aが関数Bを呼び出す場合、関数Aのコードには関数Bへのリロケーションエントリが含まれます。
   • 関数データ（s.Func.FuncData）は、Goのランタイムが使用するメタデータであり、特定の関数が参照する他のシンボル（例: ガベージコレクション情報、スタックマップなど）を含みます。これらも到達可能性の判断に考慮されます。

2. デッドシンボルの削除: dead関数内で、walkDeadによってマークされなかったシンボルは「デッド」と判断され、リンカの内部データ構造から削除されます。

   • p.Syms（すべてのシンボルのマップ）からデッドシンボルが削除されます。
   • p.Missing（解決されていない外部シンボルのマップ）からもデッドシンボルが削除されます。
   • p.SymOrder（シンボルの順序を保持するスライス）や、各パッケージのシンボルリスト（pkg.Syms）からもデッドシンボルが削除されます。これはremoveDeadヘルパー関数によって効率的に行われます。

このプロセスにより、最終的な実行可能ファイルには、プログラムの実行に必要な最小限のコードとデータのみが含まれるようになります。

ただし、Goの反射（reflection）機能を使用する場合、リンカは実行時にどのコードが呼び出されるかを完全に静的に判断できないため、保守的に多くのコードを残す傾向があります。これにより、反射を多用するプログラムでは、デッドコード削除の効果が限定的になることがあります。

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

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

1. src/cmd/link/dead.go:

   • 新規ファイルとして追加され、デッドコード削除の主要なロジックが実装されています。
   • Prog構造体にDeadマップ（削除されたシンボルを記録するため）が追加されています。
   • dead()関数が追加され、マーク＆スイープの全体的なフローを管理します。
   • walkDead()関数が追加され、到達可能なシンボルを再帰的にマークします。
   • removeDead()ヘルパー関数が追加され、シンボルリストからデッドシンボルを効率的に削除します。

2. src/cmd/link/dead_test.go:

   • 新規ファイルとして追加され、dead.goで実装されたデッドコード削除機能のテストが含まれています。
   • TestDead関数は、testdata/dead.6というテスト用のオブジェクトファイルを使用して、dead_プレフィックスを持つシンボルが正しく削除されることを検証します。
   • copyMap、checkDeadMap、copySlice、checkDeadSliceなどのヘルパー関数が、テストの検証を容易にするために定義されています。

3. src/cmd/link/testdata/dead.6:

   • テスト用のバイナリファイル（オブジェクトファイル）です。dead.sから生成されます。

4. src/cmd/link/testdata/dead.s:

   • テスト用のGoアセンブリ言語ファイルです。
   • start、text1、text2、data1などの到達可能なシンボルと、dead_start、dead_text1、dead_data1などの到達不能な（削除されるべき）シンボルが定義されています。
   • このファイルは、リンカがdead_プレフィックスを持つシンボルを正しくデッドコードとして識別し、削除できることを確認するために使用されます。

コアとなるコードの解説

src/cmd/link/dead.go

package main

import "debug/goobj"

// dead removes unreachable code and data from the program.
// It is basically a mark-sweep garbage collection: traverse all the
// symbols reachable from the entry (startSymID) and then delete
// the rest.
func (p *Prog) dead() {
	p.Dead = make(map[goobj.SymID]bool) // 削除されたシンボルを記録するマップ
	reachable := make(map[goobj.SymID]bool) // 到達可能なシンボルを記録するマップ

	// プログラムの開始シンボルから到達可能なシンボルをマークする
	p.walkDead(p.startSym, reachable)

	// p.Syms (すべてのシンボル) から到達不能なシンボルを削除する
	for sym := range p.Syms {
		if !reachable[sym] {
			delete(p.Syms, sym)
			p.Dead[sym] = true // 削除されたシンボルとして記録
		}
	}

	// p.Missing (解決されていない外部シンボル) から到達不能なシンボルを削除する
	for sym := range p.Missing {
		if !reachable[sym] {
			delete(p.Missing, sym)
			p.Dead[sym] = true // 削除されたシンボルとして記録
		}
	}

	// p.SymOrder (シンボルの順序) から到達不能なシンボルを削除する
	p.SymOrder = removeDead(p.SymOrder, reachable)

	// 各パッケージのシンボルリストから到達不能なシンボルを削除する
	for _, pkg := range p.Packages {
		pkg.Syms = removeDead(pkg.Syms, reachable)
	}
}

// walkDead traverses the symbols reachable from sym, adding them to reachable.
// The caller has verified that reachable[sym] = false.
func (p *Prog) walkDead(sym goobj.SymID, reachable map[goobj.SymID]bool) {
	reachable[sym] = true // 現在のシンボルを到達可能としてマーク

	s := p.Syms[sym]
	if s == nil {
		return // シンボルが存在しない場合は終了
	}

	// シンボルのリロケーションを辿り、参照先のシンボルもマークする
	for i := range s.Reloc {
		r := &s.Reloc[i]
		if !reachable[r.Sym] { // 参照先のシンボルがまだマークされていなければ
			p.walkDead(r.Sym, reachable) // 再帰的に辿る
		}
	}

	// 関数データ内のシンボルを辿り、参照先のシンボルもマークする
	if s.Func != nil {
		for _, fdata := range s.Func.FuncData {
			if fdata.Sym.Name != "" && !reachable[fdata.Sym] { // 関数データ内のシンボルがまだマークされていなければ
				p.walkDead(fdata.Sym, reachable) // 再帰的に辿る
			}
		}
	}
}

// removeDead removes unreachable (dead) symbols from syms,
// returning a shortened slice using the same underlying array.
func removeDead(syms []*Sym, reachable map[goobj.SymID]bool) []*Sym {
	keep := syms[:0] // 新しいスライスを作成し、元の配列を再利用
	for _, sym := range syms {
		if reachable[sym.SymID] { // シンボルが到達可能であれば
			keep = append(keep, sym) // 新しいスライスに追加
		}
	}
	return keep // 到達可能なシンボルのみを含むスライスを返す
}

dead()関数は、デッドコード削除プロセスのエントリポイントです。reachableマップを使用して到達可能なシンボルを追跡し、p.startSym（プログラムのエントリポイント）からwalkDeadを呼び出してマークフェーズを開始します。マークフェーズが完了すると、p.Syms、p.Missing、p.SymOrder、および各パッケージのシンボルリストから、reachableマップに存在しない（つまり到達不能な）シンボルを削除します。

walkDead()関数は、再帰的にシンボルグラフを辿り、到達可能なシンボルをマークします。これは、シンボルのリロケーションエントリ（他のシンボルへの参照）や、関数データ（ランタイムが使用するメタデータ内のシンボル参照）を検査することで行われます。

removeDead()関数は、スライスから到達不能なシンボルを効率的に削除するためのヘルパーです。元のスライスの基盤となる配列を再利用することで、メモリ割り当てを最小限に抑えます。

src/cmd/link/dead_test.go

このファイルは、dead.goで実装されたデッドコード削除機能が正しく動作するかを検証するためのテストケースを含んでいます。特に、dead_プレフィックスを持つシンボルが期待通りに削除されることを確認します。checkDeadMapやcheckDeadSliceといったヘルパー関数は、テストの検証ロジックを簡潔に保つために使用されています。

関連リンク

• Go言語のリンカに関する公式ドキュメントやブログ記事は、Goの公式ウェブサイトやGoのソースコードリポジトリで参照できます。
• Goのバイナリサイズ最適化に関する議論やツールについては、GoコミュニティのフォーラムやGitHubリポジトリで情報が見つかることがあります。

参考にした情報源リンク

• Go linker dead code removal mark-sweep - Google Search Results
  • 特に、検索結果で示されたgolab.io、huizhou92.com、medium.comなどの記事は、Goリンカのデッドコード削除の仕組みについて詳細な情報を提供しています。
• Go言語の公式ドキュメント: https://go.dev/
• Go言語のソースコードリポジトリ: https://github.com/golang/go