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

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

このコミットは、Go言語のリンカ（6l、x86-64アーキテクチャ向け）において、未使用のコードとデータを削除する「デッドコードエリミネーション」を実装したものです。これにより、生成されるバイナリのサイズが削減され、シンプルなテストバイナリでは約7%のサイズ削減が達成されました。リフレクションを使用しているコードについては、実行時に使用される可能性のある要素を静的に判断することが難しいため、削減効果が限定的であると述べられています。

コミット

commit c3fa54c48bcf21e1479ee203b9f577745f1b52fe
Author: Russ Cox <rsc@golang.org>
Date:   Wed Jan 21 14:50:27 2009 -0800

    delete unused code and data from 6.outs.
    cuts simple test binary by 7%.
    would be more except for reflection.

    R=r
    DELTA=126  (117 added, 4 deleted, 5 changed)
    OCL=23163
    CL=23237
---
 src/cmd/6l/asm.c  |   4 ++-
 src/cmd/6l/go.c   | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++--
 src/cmd/6l/l.h    |   7 ++--
 src/cmd/6l/list.c |   5 ++-\
 src/cmd/6l/obj.c  |  11 ++++--
 src/cmd/6l/pass.c |   3 ++\
 6 files changed, 123 insertions(+), 10 deletions(-)

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

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

元コミット内容

delete unused code and data from 6.outs.
cuts simple test binary by 7%.
would be more except for reflection.

R=r
DELTA=126  (117 added, 4 deleted, 5 changed)
OCL=23163
CL=23237

変更の背景

コンパイルされたプログラムのバイナリサイズは、実行効率、配布の容易さ、メモリ使用量など、多くの側面で重要です。特に、Goのような静的リンクを基本とする言語では、必要なライブラリコードがすべて最終バイナリに含まれるため、未使用のコードやデータがバイナリサイズを不必要に増大させる可能性があります。

このコミットの背景には、Goリンカが生成するバイナリから、実際に実行時に使用されない（到達不能な）コードやデータを効率的に削除し、バイナリサイズを最適化するという目的があります。リンカの役割は、コンパイルされたオブジェクトファイル群を結合し、実行可能なプログラムを生成することですが、その過程で不要な要素を排除する「デッドコードエリミネーション」は、現代のコンパイラやリンカにおける重要な最適化手法の一つです。

コミットメッセージにある「reflection」に関する言及は、リフレクションが実行時に動的に型情報やメソッドを操作する機能であるため、静的な解析だけではどのコードが使用されるかを完全に判断するのが難しいという、デッドコードエリミネーションにおける一般的な課題を示唆しています。

前提知識の解説

リンカ (Linker)

リンカは、コンパイラによって生成された複数のオブジェクトファイル（機械語コードとデータを含む）と、必要なライブラリファイルを結合して、最終的な実行可能プログラムを生成するツールです。リンカの主な役割は以下の通りです。

  1. シンボル解決 (Symbol Resolution): オブジェクトファイル間で参照されている関数や変数のアドレスを解決します。
  2. 再配置 (Relocation): コードやデータがメモリ上のどこに配置されるかに応じて、アドレス参照を調整します。
  3. デッドコードエリミネーション (Dead Code Elimination): 実行時に到達不能なコードやデータを最終バイナリから削除します。

デッドコードエリミネーション (Dead Code Elimination, DCE)

DCEは、プログラムの実行フローから決して到達しないコードや、使用されないデータを特定し、最終的な実行可能ファイルから削除する最適化手法です。これにより、バイナリサイズが削減され、ロード時間やメモリ使用量が改善される可能性があります。DCEは通常、以下のステップで行われます。

  1. 到達可能性解析 (Reachability Analysis): プログラムのエントリポイント（例: main関数）から開始し、呼び出しグラフやデータフローをたどって、実行時に到達可能なすべてのコードとデータをマークします。
  2. 削除 (Elimination): マークされなかった（到達不能と判断された）コードやデータをバイナリから削除します。

マーク・アンド・スイープ (Mark-and-Sweep) アルゴリズム

このコミットで実装されているDCEは、ガベージコレクションでよく用いられる「マーク・アンド・スイープ」アルゴリズムに似たアプローチを採用しています。

  • マークフェーズ (Mark Phase): プログラムの既知のエントリポイント（ルート）から開始し、そこから参照されるすべてのコードやデータを「到達可能」としてマークします。このプロセスは再帰的に行われ、到達可能なすべての要素がマークされるまで続きます。
  • スイープフェーズ (Sweep Phase): プログラム全体のコードやデータ構造を走査し、マークされなかった（到達不能な）要素を特定して削除します。

Goリンカの内部構造 (Prog, Sym)

Goリンカは、プログラムのコードとデータを内部的に表現するために、いくつかの重要なデータ構造を使用します。

  • Prog (Program Instruction): リンカが扱う個々の命令やデータ定義を表す構造体です。アセンブリ命令、データセグメントの開始、グローバルシンボルの定義などがこれに該当します。linkフィールドで次のProgに、dlinkフィールドで同じシンボルに属する次のデータProgにリンクされます。
  • Sym (Symbol): 関数名、変数名、ラベルなど、プログラム内の名前付きエンティティを表す構造体です。textフィールドはシンボルに関連付けられたコード（Progのリスト）の開始点を指し、dataフィールドはシンボルに関連付けられたデータ（Progのリスト）の開始点を指します。reachableフィールドは、このコミットで追加されたもので、シンボルが到達可能かどうかを示すフラグです。

技術的詳細

このコミットは、Goリンカのsrc/cmd/6lディレクトリ内の複数のファイルを変更し、デッドコードエリミネーションの機能を導入しています。

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

  1. 到達可能性のマーク付け:

    • src/cmd/6l/go.cにmark, markdata, marktextという関数が追加されました。
    • mark(Sym *s): シンボルsが到達可能であるとマークし（s->reachable = 1）、そのシンボルに関連付けられたコード（s->text）とデータ（s->data）を再帰的にマークします。
    • marktext(Prog *p): ATEXT（関数開始）命令から始まるコードブロックを走査し、そのブロック内の命令が参照するシンボル（p->from.sym, p->to.sym）をmarkします。
    • markdata(Prog *p, Sym *s): シンボルsに関連付けられたデータブロックを走査し、そのデータが参照するシンボルをmarkします。
    • デッドコードエリミネーションの開始点として、INITENTRY（プログラムのエントリポイント）とsys·morestack（Goランタイムのスタック拡張関数）が初期的に到達可能としてマークされます。これは、これらのシンボルが常に必要とされるためです。

  2. 到達不能な要素の削除（スイープ）:

    • src/cmd/6l/go.cにsweeplist(Prog **first, Prog **last)関数が追加されました。
    • この関数は、Progのリンクリストを走査し、ATEXT, ADATA, AGLOBLといったシンボル定義の開始点に遭遇した際に、そのシンボルがreachableでない場合、そのシンボルのtypeをSxxx（未使用を示す型）に設定します。これにより、後続のリンカ処理でそのシンボルが無視されるようになります。
    • sweeplistは、firstp（メインのプログラム命令リスト）とdatap（データ命令リスト）の両方に対して実行され、到達不能なコードとデータを効果的に「削除」します。

  3. データ構造の拡張:

    • src/cmd/6l/l.hにおいて、struct Progにdlinkフィールドが追加されました。これは、同じシンボルに属する複数のデータProgを連結するためのものです。
    • struct Symにdataフィールドとreachableフィールドが追加されました。dataはシンボルに関連付けられたデータProgのリストの開始点を指し、reachableは前述の到達可能性フラグです。

  4. リンカフローへの統合:

    • src/cmd/6l/obj.cのmain関数内で、definetypesigs()の後にdeadcode()関数が呼び出されるようになりました。これにより、リンカの処理の早い段階でデッドコードエリミネーションが実行され、その後の処理が最適化されたデータに対して行われるようになります。

  5. データProgの連結:

    • src/cmd/6l/obj.cとsrc/cmd/6l/pass.cにおいて、ADATAやnewdata関数で新しいデータProgが作成される際に、そのProgが属するSymのdataリストにdlinkを使って連結されるようになりました。これにより、markdata関数がシンボルに関連するすべてのデータを効率的に走査できるようになります。

これらの変更により、Goリンカは、プログラムの静的な解析に基づいて未使用のコードとデータを識別し、最終バイナリから取り除くことで、実行可能ファイルのサイズを削減する能力を獲得しました。

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

このコミットのコアとなる変更は、src/cmd/6l/go.cに新しい関数群（mark, markdata, marktext, sweeplist, deadcode）が追加され、デッドコードエリミネーションのロジックが実装された点です。

特に、deadcode関数がデッドコードエリミネーションの全体を調整し、mark関数が到達可能性のマーク付けを行い、sweeplist関数が到達不能な要素を削除する役割を担っています。

また、src/cmd/6l/l.hでProgとSym構造体に新しいフィールドが追加され、src/cmd/6l/obj.cとsrc/cmd/6l/pass.cでこれらの新しいフィールドが適切に設定されるように変更されています。

コアとなるコードの解説

src/cmd/6l/go.c

// mark, markdata, marktext: 到達可能なコードとデータをマークする関数群
static void mark(Sym *s) {
    if (s == S || s->reachable) // シンボルがNULLか、既に到達可能なら何もしない
        return;
    s->reachable = 1; // シンボルを到達可能とマーク
    if (s->text)
        marktext(s->text); // 関連するコードをマーク
    if (s->data)
        markdata(s->data, s); // 関連するデータをマーク
}

static void marktext(Prog *p) {
    // ATEXT命令から始まるコードブロックを走査し、参照されるシンボルをマーク
    // ... (詳細な実装は省略)
}

static void markdata(Prog *p, Sym *s) {
    // シンボルsに関連するデータブロックを走査し、参照されるシンボルをマーク
    // ... (詳細な実装は省略)
}

// sweeplist: 到達不能な要素を削除する関数
static void sweeplist(Prog **first, Prog **last) {
    int reachable;
    Prog *p, *q;

    reachable = 1; // 初期状態では到達可能と仮定
    q = P; // 前のProgへのポインタ
    for (p = *first; p != P; p = p->link) {
        switch (p->as) {
        case ATEXT:
        case ADATA:
        case AGLOBL:
            // シンボル定義の開始点に遭遇した場合
            reachable = p->from.sym->reachable; // そのシンボルが到達可能か確認
            if (!reachable) {
                // 到達不能であれば、シンボルタイプをSxxxに設定して削除対象とする
                if (debug['v'] > 1)
                    Bprint(&bso, "discard %s\n", p->from.sym->name);
                p->from.sym->type = Sxxx;
            }
            break;
        }
        if (reachable) {
            // 到達可能であれば、リストに保持
            if (q == P)
                *first = p;
            else
                q->link = p;
            q = p;
        }
    }
    if (q == P)
        *first = P;
    else
        q->link = P;
    *last = q;
}

// deadcode: デッドコードエリミネーションのメインエントリポイント
void deadcode(void) {
    if (debug['v'])
        Bprint(&bso, "%5.2f deadcode\n", cputime());

    // プログラムのエントリポイントとスタック拡張関数をマーク
    mark(lookup(INITENTRY, 0));
    mark(lookup("sys·morestack", 0));

    // メインのプログラム命令リストとデータ命令リストをスイープ
    sweeplist(&firstp, &lastp);
    sweeplist(&datap, &edatap);
}

src/cmd/6l/l.h

struct Prog {
    // ... 既存のフィールド ...
    Prog *dlink; // 同じシンボルに属する次のデータProgへのリンク
    // ... 既存のフィールド ...
};

struct Sym {
    // ... 既存のフィールド ...
    Prog *text; // シンボルに関連付けられたコードの開始点
    Prog *data; // シンボルに関連付けられたデータの開始点 (新規追加)
    int reachable; // シンボルが到達可能かどうかを示すフラグ (新規追加)
    // ... 既存のフィールド ...
};

// ... 関数プロトタイプ宣言 ...
void deadcode(void); // deadcode関数の宣言
void nopout(Prog *); // nopout関数の宣言 (新規追加)
// ...

src/cmd/6l/obj.c

void main(int argc, char *argv[]) {
    // ... 既存の処理 ...
    ignoreoptfuncs();
    definetypestrings();
    definetypesigs();
    deadcode(); // ここでデッドコードエリミネーションが実行される
    // ... 既存の処理 ...
}

// ADATA命令の処理ループ内で、データProgをシンボルのdataリストに連結
// ...
    if (s != S) {
        p->dlink = s->data; // 新しいProgを既存のdataリストの先頭に追加
        s->data = p;
    }
// ...

src/cmd/6l/pass.c

Prog *newdata(Sym *s, int o, int w, int t) {
    // ... 既存の処理 ...
    p->from.sym = s;
    p->from.offset = o;
    p->to.type = D_CONST;
    p->dlink = s->data; // 新しいデータProgをシンボルのdataリストに連結
    s->data = p;
    return p;
}

これらの変更により、Goリンカは、プログラムの静的な解析に基づいて未使用のコードとデータを識別し、最終バイナリから取り除くことで、実行可能ファイルのサイズを削減する能力を獲得しました。

関連リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • Go言語のリンカに関するドキュメント（もしあれば、Goの公式ドキュメントやブログ記事）

参考にした情報源リンク

  • デッドコードエリミネーションに関する一般的な情報源（例: Wikipedia, コンパイラ最適化に関する書籍）
  • マーク・アンド・スイープアルゴリズムに関する情報源（例: Wikipedia, ガベージコレクションに関する書籍）
  • Go言語のリンカの内部構造に関する情報源（Goのソースコード、Goのコンパイラ/リンカに関する技術ブログや論文）
    • 特に、Goのリンカの設計に関するRuss Cox氏の発表や記事があれば、より深い理解に役立ちます。
    • GoのリンカはPlan 9のリンカをベースにしているため、Plan 9のツールチェインに関する情報も参考になる場合があります。