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

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

このコミットは、Goコンパイラのバックエンドにおける重要なリファクタリングを目的としています。具体的には、制御フローグラフ（CFG）の構築とドミネータ計算に関するロジックを、各アーキテクチャ固有のコンパイラ（5g, 6g, 8g）から、よりポータブルな共通コードベースであるcmd/gc/popt.cおよびcmd/gc/popt.hに移動しています。これにより、CFGの表現と操作が一元化され、異なる最適化が命令に異なるアノテーションを付加できるようになります。

コミット

commit dbf96addfb7fc868701fdf3d70ed6c2e1c920d63
Author: Russ Cox <rsc@golang.org>
Date:   Mon Aug 12 22:02:10 2013 -0400

    cmd/gc: move flow graph into portable opt

    Now there's only one copy of the flow graph construction
    and dominator computation, and different optimizations
    can attach different annotations to the instructions.

    R=ken2
    CC=golang-dev
    https://golang.org/cl/12797045

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

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

元コミット内容

cmd/gc: move flow graph into portable opt

このコミットの目的は、フローグラフの構築とドミネータ計算のロジックをポータブルな最適化レイヤーに移動することです。これにより、フローグラフの構築とドミネータ計算のコピーが1つになり、異なる最適化が命令に異なるアノテーションを付加できるようになります。

変更の背景

Goコンパイラ（gc）は、複数のターゲットアーキテクチャ（例: 5g for ARM, 6g for x86-64, 8g for x86）をサポートしています。以前は、これらの各アーキテクチャ固有のコンパイラが、それぞれ独自の制御フローグラフ（CFG）の表現、構築ロジック、およびドミネータ計算のアルゴリズムを持っていました。

このような設計は、コードの重複、メンテナンスの複雑さ、および新しい最適化の導入の困難さという問題を引き起こしていました。例えば、新しい最適化を導入する際には、各アーキテクチャ固有のコンパイラでCFG関連のコードを個別に変更または複製する必要がありました。

このコミットは、これらの問題を解決するために、CFGの表現と操作に関する共通の基盤を導入し、コードの再利用性と保守性を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下の概念に関する基本的な知識が必要です。

  1. コンパイラの最適化: コンパイラは、ソースコードを機械語に変換する際に、生成されるコードの実行速度やサイズを改善するための「最適化」を行います。これには、デッドコード削除、定数伝播、ループ最適化などが含まれます。

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

    • プログラムの実行パスを抽象的に表現したグラフ構造です。
    • ノード（またはブロック）は、連続して実行される命令のシーケンス（基本ブロック）を表します。
    • エッジは、基本ブロック間の制御の流れ（ジャンプ、条件分岐など）を表します。
    • CFGは、データフロー解析や多くの最適化の基盤となります。

  3. ドミネータ (Dominator):

    • CFGにおいて、ノード A がノード B のドミネータであるとは、B に到達するすべてのパスが A を通過する場合を言います。
    • 即時ドミネータ (Immediate Dominator, IDom) は、B を直接ドミネートするノードの中で、B に最も近いノードです。
    • ドミネータツリーは、プログラムの構造を理解し、ループ検出や最適化の範囲を決定するために使用されます。

  4. 逆ポストオーダー (Reverse Postorder, RPO):

    • CFGのノードを、深さ優先探索の終了順序の逆順に並べたものです。
    • 多くのデータフロー解析アルゴリズムで、ノードの処理順序を決定するために使用されます。

  5. Goコンパイラの構造:

    • Goコンパイラは、cmd/gcディレクトリ以下に存在します。
    • 5g, 6g, 8gといったディレクトリは、それぞれ異なるアーキテクチャ（ARM, x86-64, x86）向けのコンパイラバックエンドを含んでいます。
    • これらのバックエンドは、共通のフロントエンドから中間表現を受け取り、ターゲットアーキテクチャの機械語を生成します。

技術的詳細

このコミットの核心は、CFG関連のロジックをアーキテクチャ固有のコードから分離し、src/cmd/gc/popt.cとsrc/cmd/gc/popt.hに集約することです。

主な変更点:

  1. Flow 構造体の導入:

    • 新しいFlow構造体は、CFGのノードに関する共通の情報をカプセル化します。これには、前任者（p1, p2, p2link）、後続者（s1, s2）、リンク（link）、関連するプログラム命令（prog）、ループ情報（loop）、逆ポストオーダー番号（rpo）、アクティブ状態（active）、参照セット（refset）などが含まれます。
    • これにより、CFGの構造とトラバーサルに関するロジックが、アーキテクチャ固有のレジスタ割り当てやデータフロー情報から分離されます。

  2. Graph 構造体の導入:

    • Graph構造体は、CFG全体を表し、グラフの開始ノード（start）や終了ノード（end）などの情報を含みます。

  3. Reg 構造体の変更:

    • 各アーキテクチャ固有のopt.hファイル（例: src/cmd/5g/opt.h）にあるReg構造体は、Flow f;というフィールドを持つように変更されました。これは、Reg構造体がFlow構造体を埋め込む（composition）ことを意味します。
    • これにより、Reg構造体は引き続きアーキテクチャ固有のデータフロー情報（set, use1, use2, act, reguなど）を保持しつつ、CFG関連の共通情報は埋め込まれたFlow構造体を介してアクセスされるようになります（例: r->f.p1、r->f.loop）。

  4. CFG操作関数のポータブル化:

    • flowstart、flowend、flowrpo、uniqp、uniqs、dumpitなどのCFGを操作する関数が、src/cmd/gc/popt.cに移動され、FlowおよびGraph構造体を使用するように変更されました。
    • flowstartは、プログラム命令のリストからCFGを構築し、Graphオブジェクトを返します。
    • flowrpoは、逆ポストオーダー順序を計算し、ドミネータ情報を更新します。
    • uniqpとuniqsは、それぞれユニークな前任者と後続者を見つけるためのヘルパー関数です。

  5. アーキテクチャ固有コードの簡素化:

    • src/cmd/*/peep.cとsrc/cmd/*/reg.cの各ファイルでは、CFGの構築とトラバーサルに関する手動のロジックが削除され、新しく導入されたポータブルなCFG関数（flowstart、flowrpoなど）の呼び出しに置き換えられました。
    • これにより、各バックエンドのコードが大幅に削減され、よりクリーンで保守しやすくなりました。

影響:

  • コードの重複排除: CFG構築とドミネータ計算のロジックが1箇所に集約され、各アーキテクチャ固有のコンパイラでのコード重複がなくなりました。
  • メンテナンス性の向上: CFG関連のバグ修正や機能追加は、popt.cの1箇所で行うだけでよくなります。
  • 最適化の容易化: 新しい最適化を実装する際に、CFGの共通表現を利用できるため、開発が容易になります。異なる最適化が、共通のCFG表現に対して独自のアノテーション（例えば、特定の最適化に必要な追加情報）を付加できるようになります。
  • パフォーマンス: CFGの構築と解析がより効率的になる可能性があります。

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

このコミットは、主に以下のファイル群に影響を与えています。

  • src/cmd/5g/opt.h, src/cmd/6g/opt.h, src/cmd/8g/opt.h:
    • Reg構造体からCFG関連のフィールド（p1, s1, loopなど）が削除され、Flow f;が追加されました。
    • CFG関連のグローバル変数や関数プロトタイプが削除または変更されました。
  • src/cmd/5g/peep.c, src/cmd/6g/peep.c, src/cmd/8g/peep.c:
    • peep関数内で、手動でのReg構造体のリンク構築が削除され、flowstartの呼び出しに置き換えられました。
    • copyprop, subpropなど、CFGをトラバースする多くの関数がFlow*またはGraph*を引数に取るように変更され、static関数になりました。
  • src/cmd/5g/reg.c, src/cmd/6g/reg.c, src/cmd/8g/reg.c:
    • regopt関数内で、Reg構造体の初期化とリンク構築がflowstartとflowrpoの呼び出しに置き換えられました。
    • rega関数（Reg構造体を割り当てる関数）が削除されました。
    • loopit関数（ループ構造を解析する関数）の呼び出しがflowrpoに置き換えられました。
    • dumpitなどのデバッグ出力関数がFlow*を引数に取るように変更されました。
  • src/cmd/gc/popt.c:
    • 新しく追加されたファイルで、FlowおよびGraph構造体の定義と、flowstart, flowend, flowrpo, uniqp, uniqs, dumpitなどのポータブルなCFG操作関数の実装が含まれています。
  • src/cmd/gc/popt.h:
    • 新しく追加されたファイルで、FlowおよびGraph構造体の宣言と、popt.cで実装されるポータブルなCFG操作関数のプロトタイプが含まれています。

コアとなるコードの解説

このコミットの最も重要な変更は、src/cmd/gc/popt.cとsrc/cmd/gc/popt.hに導入された新しい抽象化です。

src/cmd/gc/popt.h:

// Flow represents a node in the control flow graph.
// It contains generic information about the control flow.
typedef struct Flow Flow;
struct Flow
{
	Flow*	link;   // next instruction in function code
	Prog*	prog;   // actual instruction

	Flow*	p1;     // predecessors of this instruction: p1,
	Flow*	p2;     // and then p2 linked though p2link.
	Flow*	p2link;

	Flow*	s1;     // successors of this instruction (at most two: s1 and s2).
	Flow*	s2;

	uint16	loop;   // x5 for every loop
	int32	rpo;    // reverse post ordering
	int32	active; // used for various traversals
	uchar	refset; // diagnostic generated
};

// Graph represents the entire control flow graph for a function.
typedef struct Graph Graph;
struct Graph
{
	Flow*	start; // first Flow node in the graph
	Flow*	last;  // last Flow node in the graph
	int	len;   // number of Flow nodes
};

// Functions for building and manipulating the flow graph.
Graph*	flowstart(Prog *firstp, int nodesize);
void	flowend(Graph *g);
void	flowrpo(Graph *g);
Flow*	uniqp(Flow *r);
Flow*	uniqs(Flow *r);
void	dumpit(char *str, Flow *r0, int isreg);

src/cmd/gc/popt.c (抜粋):

// flowstart builds the control flow graph from a list of Prog instructions.
Graph*
flowstart(Prog *firstp, int nodesize)
{
	Graph *g;
	Prog *p;
	Flow *r, *r1;
	ProgInfo info, info2;

	g = mal(sizeof(*g));
	g->start = nil;
	g->last = nil;
	g->len = 0;

	// Iterate through Prog instructions to create Flow nodes
	for(p=firstp; p != P; p = p->link) {
		proginfo(&info, p);
		if(info.flags & Skip)
			continue;

		r = mal(nodesize); // Allocate a node of the specified size (e.g., sizeof(Reg))
		g->len++;
		if(g->start == nil) {
			g->start = r;
			g->last = r;
		} else {
			g->last->link = r;
			r->p1 = g->last; // Set predecessor
			g->last->s1 = r; // Set successor
			g->last = r;
		}
		r->prog = p;
		p->opt = r; // Link Prog back to Flow/Reg node

		// Handle control flow breaks (e.g., returns, jumps)
		r1 = r->p1;
		if(r1 != nil) {
			proginfo(&info2, r1->prog);
			if(info2.flags & Break) {
				r->p1 = nil;
				r1->s1 = nil;
			}
		}
	}

	// Connect branch targets
	for(r=g->start; r != nil; r=r->link) {
		p = r->prog;
		if(p->to.type == D_BRANCH) {
			if(p->to.u.branch == P)
				fatal("pnil %P", p);
			r1 = p->to.u.branch->opt; // Get Flow/Reg node for branch target
			if(r1 == nil)
				fatal("rnil %P", p);
			if(r1 == r) {
				continue;
			}
			r->s2 = r1; // Set second successor for branches
			r->p2link = r1->p2; // Link to second predecessor list
			r1->p2 = r;
		}
	}
	return g;
}

// flowrpo computes reverse postorder and dominator information.
void
flowrpo(Graph *g)
{
	// ... (implementation of postorder traversal and dominator computation)
}

// uniqp returns a "unique" predecessor to instruction r.
// If the instruction is the first one or has multiple
// predecessors due to jump, nil is returned.
Flow*
uniqp(Flow *r)
{
	Flow *r1;

	r1 = r->p1;
	if(r1 == nil) {
		r1 = r->p2;
		if(r1 == nil || r1->p2link != nil)
			return nil;
	} else
		if(r->p2 != nil)
			return nil;
	return r1;
}

// uniqs returns a "unique" successor to instruction r.
Flow*
uniqs(Flow *r)
{
	Flow *r1;

	r1 = r->s1;
	if(r1 == nil) {
		r1 = r->s2;
		if(r1 == nil)
			return nil;
	} else
		if(r->s2 != nil)
			return nil;
	return r1;
}

flowstart関数は、Goコンパイラの命令列（Progのリンクリスト）を受け取り、それらを基にFlowノードのリンクリストと、それらの間の制御フローエッジ（p1, p2, s1, s2）を構築します。各Prog命令は、対応するFlowノードへのポインタ（p->opt）を持つようになります。

flowrpo関数は、構築されたCFGに対して逆ポストオーダー順序とドミネータ情報を計算します。これらの情報は、ループ検出やデータフロー解析などの後続の最適化パスで利用されます。

uniqpとuniqsは、特定のFlowノードが単一の前任者または後続者を持つかどうかを効率的に判断するためのヘルパー関数です。これは、線形なコードパスをたどる最適化で頻繁に利用されます。

この変更により、各アーキテクチャ固有のpeep.cやreg.cは、CFGの低レベルな構築やトラバーサルの詳細を意識する必要がなくなり、popt.cで提供される共通のAPIを呼び出すだけでよくなりました。これにより、コンパイラのコードベースが大幅に整理され、将来的な拡張や最適化の追加が容易になっています。

関連リンク

  • Go言語の公式リポジトリ: https://github.com/golang/go
  • このコミットのChange-ID: 12797045 (GoのコードレビューシステムGerritでのID)

参考にした情報源リンク

  • Goコンパイラのソースコード (特にsrc/cmd/gc/popt.c, src/cmd/gc/popt.h, src/cmd/*/opt.h, src/cmd/*/peep.c, src/cmd/*/reg.c)
  • コンパイラ最適化に関する一般的な知識（制御フローグラフ、ドミネータ、データフロー解析）
    • "Compilers: Principles, Techniques, and Tools" (通称 "Dragon Book") by Aho, Lam, Sethi, and Ullman
    • オンラインのコンピュータサイエンスの講義資料や記事
  • Go言語のGerritコードレビューシステム: https://go-review.googlesource.com/
  • GoのIssue Tracker: https://go.dev/issue