ソースからバイナリへ: GCCの内部機構

執筆：Diego Novillo

はじめに
コンパイルプロセス
GCCの内部構成
アーキテクチャ上の制限の克服
Tree SSA
結論
執筆者について
参考文献

はじめに

コンピュータは非常に複雑であると同時にたいへん愚かでもあります。コンピュータには、正確に「何をしてほしいのか」を、事細かに指示する必要があります。そのうえ、1と0からなるビットの並びが理解できるだけなので、たとえば、最新のPentiumプロセッサで2つの整数を足し算する、という単純な操作をするのに、約48ビットのビット列を必要とすることもあるのです。オペレーティングシステムを実装しようとすると何が必要になるのか想像してみてください。

言うまでもなく、通常は、ビット列を利用してコンピュータのプログラムを作成することはありません。ビット列を利用する代わりに、人間が理解できる言語を使用してすべての命令を記述し、その後でコンピュータが理解できる、1と0の適切な並びに変換します。変換の概念はコンピュータの世界の至る所で用いられています。コンピュータに指示する処理内容は、すべて、変換の過程を経る必要があります。こういった変換は、プログラムを実行しながら、インタプリテーションと呼ばれる処理で行われる場合もあれば（Perlのスクリプトやスプレッドシートなどの場合）、プログラムを起動する前に一度だけ、行われる場合もあります（CやC++のアプリケーションなどの場合）。また、JITコンパイルと呼ばれる処理でインタプリテーションとコンパイルを併用する複合型の手法もあり、この手法は人気を集めつつあります。

この記事では、GCC、すなわち、今やUnixの世界で最も一般的なコンパイラの1つになったGNU Compiler Collectionについて検討し、そのことを通じて、コンパイラ内部でどのような処理が行われているのか説明します。まず、一般的なコンパイラの構造の説明から開始し、続けて、GCCの内部構造の概要を説明します。最後に、GCCの以前のバージョンでは実装するのが困難ないしは不可能であった、より強力な機能の実現に道を開く、GCC-コア基盤のアーキテクチャ上の最近の進歩について説明します。

以下の説明は非常にレベルの高い内容の概要となることを心に留めておいてください。コンパイラはかなり複雑なソフトウェアの体系です（GCCは約210万行のコードからなり、15年以上もの間開発が続けられています）。そのため、コンパイラの詳細説明は流血現場を描写するようなものですが、うまく説明するつもりです。GCCや一般的なコンパイラに興味のある方は、「参考文献」にリストされているリンクを参照してください。

コンパイルプロセス

コンパイラは、1つの言語で記述されたプログラム（ソースコード）を入力とし、それを他の言語で記述された、意味的に等価なプログラム（オブジェクトコード）に変換します。コンパイラに関する最も的を得た考え方は、最終的なオブジェクトコードになるまで、プログラムを異なるいくつかの中間的な形に段階的に変換するパイプラインと考えることです。

このパイプラインには、3つの主要な要素があります。フロントエンドは、入力プログラムを読み、構文を検査します。ミドルエンドは、プログラムを解析し、より効率的な形式に変換します。最後に、バックエンドは、最終的にオブジェクトコードに落とし込むのが仕事です。

フロントエンド

コンピュータは、自由形式のテキストの扱いが非常に得意というわけではありません。そのため、フロントエンドは、すべての空白、コメント、およびその他の書式を取り除き、オリジナルプログラムを、中間表現（IR）と呼ばれる、より簡潔な形式に変換します。中間表現は、オリジナルのテキストストリームに比べるとはるかに扱いが易しい、単なる内部データ構造です。

一般的に、コンパイラは、入力プログラムに対し、1つ以上の表現を扱います。最初に、フロントエンドは、入力プログラムの構文解析を行い、階層構造で各命令文を表す、抽象構文木（AST：Abstract Syntax Tree）と呼ばれるデータ構造を生成します。たとえば、命令文x = y - z * 3が与えられた場合、対応するASTは図1「x = y - z * 3の抽象構文木」のようになります。

図1. x = y - z * 3の抽象構文木

フロントエンドは、入力プログラムの構文構造の正当性を検証するのが役割で、言語としての適合性に関するほとんどの診断結果の出力、プログラムで宣言されているデータ型と変数の内部データ構造の生成、ファイル名や行番号などの情報のデバッグ、および内部的なAST表現の生成を行います。

ミドルエンド

ミドルエンドは、フロントエンドにより作成された中間表現を使用して、プログラムの解析と変換を開始します。ミドルエンドとバックエンドで行われるすべての変換は、通常、以下の2つの目的のため行われます。（a）できるだけ高速で稼動するオブジェクトコードを生成する（パフォーマンスの最適化）、または、（b）できるだけメモリ領域を使用しないオブジェクトコードを生成する（メモリ領域の最適化）。一般的には、これらの2つの最適化はマシンや最後に生成されるオブジェクトコードに左右されることはありません。

フロントエンドは、プログラムが実際にどのような処理をするのかほとんど知りません。最適化は、コンパイラがプログラムの制御の流れを理解し（コントロールフロー解析）、かつプログラム実行時にデータがどのように変換されるかを理解して（データフロー解析）、始めて可能になります。プログラムの制御とデータの流れを解析することにより、コンパイラは、オブジェクトコードの実行時パフォーマンスを向上できます。ひとたびプログラムの制御とデータの流れがコンパイラにより理解されると、多種多様な最適化が可能になります。以下に、最適化機能を持つ標準的なコンパイラで使用されている、最も定評のある最適化の手法をいくつか紹介します。

Algebraic simplifications（代数的簡素化）

演算子やオペランドの代数的特性を利用して、式を簡素化します。たとえば、i + 1 - iは1に変換されます。結合性、交換性、分布性など、その他の特性も式を簡素化するのに利用されます。

Constant folding（定数の畳み込み）

すべてのオペランドが定数である式は、コンパイル時に評価し、評価した値で置き換えることが可能です。たとえば、式a = 4 + 3 - 8はa = -1に置き換え可能です。この最適化は、定数の伝搬と共に使用されると、最も良い結果が得られます（以下を参照）。

Redundancy elimination（冗長性除去）

冗長な計算を除去する手法には、いくつかの手法があります。比較的よく使用される手法を、以下で説明します。

Loop-invariant code motion（ループ内不変値移動）

毎回の繰り返しで結果が同じになる、ループ内の計算をループの外に移動します。

Common sub-expression elimination（共通部分式の除去）

ある式が特定の実行パスで2度以上計算され、かつそのオペランドにまったく変更が加えられない場合、以下で繰り返される計算は最初に計算された結果で置き換えられます。

Partial redundancy elimination（部分冗長性除去）

ある実行パスに2度以上計算される式がある場合、その計算は部分的に冗長になります。この最適化では、実行パスに対しいくつかの計算を追加または削除し、プログラム内の冗長な計算の数が最小になるようにします。この最適化には、loop-invariant code motion（ループ内不変値移動）やcommon sub-expression elimination（共通部分式の除去）の効果もあります。

バックエンド

変換の最終段階では、目的とするアーキテクチャ用のマシンコードが生成されます。この段階では、コンパイラには、プログラムが実行されるハードウェアについての非常に詳細な知識が必要です。と言うのも、通常は、プログラムの中間表現は、機械語に類似した形式に変換されるからです。この形式では、目的とするアーキテクチャをうまく利用した変換が適用できます。以下はその例です。

レジスタの割り付け

メモリではなく、ハードウェアレジスタに割り当てられる変数の数が最大になるように努力します（レジスタは主記憶よりも桁違いに高速です）。

コードスケジューリング

最新のプロセッサのスーパースカラ機能を活用し、命令の順序を並び替えることで実行段階が異なる複数の命令を並行して実行するようにします。

最終的なコード生成が終了しても、通常は、生成されたコードはそのまま実行できる状態にはなっていません。コンパイラによっては、GCCはその中の1つですが、アセンブリコードが生成されます。そのアセンブリコードがアセンブラに渡され、アセンブラによりオブジェクトコードが生成されます。オブジェクトコードが生成された後は、リンカにより、必要なオブジェクトファイルやライブラリが種々結合され、最終的な実行可能プログラムが生成されます。

GCCの内部構成

GCCは、2つの異なる中間表現を中心にして、設計されています。その1つは「Tree」と呼ばれ、本質的には前述の抽象構文木です。もう1つの中間表現はRTL（Register Transfer Language:レジスタ転送言語）と呼ばれ、最適化とコード生成のためにGCCが使用します。次の図は、GCC内のコンパイル処理の概要を示します。

図2. GCCの既存のコンパイル処理

フロントエンドとミドルエンドが一種の融合状態にある様子に注目してください。その理由は、GCCの処理がそれほど「Tree」に基づいて行われてはいないことにあります。「Tree」は、主に、RTLを生成する際の足掛かりとして使用されます。最近まで、「Tree」に基づいて行われた唯一の処理は関数のインライン化でした。他のほとんどの処理は RTLオプティマイザにゆだねられていました。一面では、これは意味のあることです。なぜなら、図から分かるように、各言語のフロントエンドは独自の形式の「Tree」を生成しているからです。たとえば、Cの構文解析ではC木が生成され、C++の構文解析ではC++木が生成されます。各言語の「Tree」は、独自の方式があり、異なっています。そのため、「Tree」に基づく解析や分析にはN個の異なる実装、つまり各フロントエンドに対し1つの実装が必要になります。これにはほとんど拡張性がなく、そのため、すべての最適化の処理はRTL内で行われます。

RTLは、無限大の個数のレジスタを持つマシンに対応したアセンブリ言語と考えられます。低レベルの表現であるため、RTLは、レジスタの割り付け、遅延スロットの最適化、peephole最適化などの、目的に密着した最適化にはうまく機能します。加えて、GCCを新しいアーキテクチャに移植する際に開発者が目的とするマシンを記述するための、かなり柔軟性にとんだ方法が、GCCにより提供されています。事実、GCCの最初の実装では、RTLはほぼ起動直後に生成されたため、コンパイラのほとんどの部分がRTLを中心にして実装されたのは自然な成り行きです。

しかし、ある種の解析や変換では、RTLから入手するのが不可能ないしは困難な、プログラムに関するより高度な情報が必要になります（たとえば配列の参照、データ型、プログラム変数の参照、制御の流れの構造など）。一般的に、RTLには、やり方のまずい目的機能が多すぎます。たとえば、目的とするマシンのレジスタが32ビットを超える数値を処理できない場合、RTLの表現では、32ビットより大きな値は複数の値に分割されます。また、関数呼び出しの仕様のような情報もRTLに詳細に置かれるため、1つの関数呼び出しが複数のRTL命令にまたがることがあります。これらのすべての詳細情報は、目的事項の詳細と関係を持つ必要がまったくない解析や最適化を実装するのを困難にする原因になっています。長い間に、いくつかの変換がRTLに実装されましたが、最後に得られる生成コードは、過度に入り組んだ、保守が困難で、エラーが生じやすいコードになっています。

アーキテクチャ上の制限の克服

GCCの従来の最適化のフレームワークは当社が意図する改良を実装するには柔軟性が十分でなかたため、Red Hat社はGCCのアーキテクチャを徹底的に再検討するプロジェクトを支援しました。どのように取り組んでいくか、いくつかの手法を検討し、当社は「Tree」の表現から開始するアイデアに同意しました。「Tree」には、データ型、変数、およびオリジナルプログラムの制御構造に関する詳細な情報が含まれています。GCCの「Tree」の表現を最適化することは、（a）よりソースプログラムに密着した、新しい解析と最適化の実装が容易になる、（b）RTLオプチマイザの処理を簡素化し、コンパイル処理を高速化する可能性がある、または生成されるコードを改良する可能性がある、点で魅力的です。

この新しい基盤は、最近の何年かに生じた、GCCに関する大きな変化の代表的なものです。GCCコミュニティの30以上の開発業者の協力を得て基本機能を完成するのに、約3年かかりました。フレームワークは静的単一代入（SSA: Static Single Assignment form）と呼ばれるコンパイラ形式を基礎にしています。SSAは、プログラム内でデータがどのように流れるのか追跡するために、コンパイラにより内部的に使用される表現です。この表現の情報は、コンパイラが最適化のための決定を導き出すための、本質的な情報です。「Tree」のデータ構造上に構築され、かつSSAが使用されることから、このフレームワークはTree SSAと名づけられました。

Tree SSA

GCCの構文解析木は、オリジナルのプログラムに関する非常に詳細な情報を含んでいますが、主に以下の2つの理由により、最適化には向いていません。

共通の表現の欠如

すべてのフロントエンドで共有される単一の表現が存在しません。図2「GCC の従来のコンパイル処理」で、すべてのフロントエンドがどのようにして独自の特徴を持つ「Tree」を生成しているのかに注目してください。「Tree」のオプチマイザを実装しようとすると、GCCによりサポートされるすべてのフロントエンドに対応したオプチマイザを実装する必要があります。このことは、保守の観点からは悪夢であり、新しいフロントエンドを開発する際には大きな負担になります。

構造的な複雑さ

フロントエンドによって生成される構文解析木は、オリジナルの入力プログラムのほぼ正確な表現です。そのため当然ながら、ほとんど無限大のパターンの式の組み合わせが可能になります（かって、わけの分からないCプログラムをご覧になったことがある方は、この意味がお分かりです）。この柔軟性は、その豊かな表現力ゆえに、人間にとっては極めて便利なものです。しかし、単純な自動機械であるコンパイラには、簡単に対応できません。これらの限界を克服するために、GENERICおよびGIMPLEと呼ばれる、2つの新しい「Tree」を基礎にした中間表現が導入されました。GENERICは各種フロントエンドの間で共通の木の表現が存在しない問題に対処します。GIMPLEは、プログラムのデータフローと制御フローを見つけ出すのを容易にする、複雑さの問題を解決します。

図3. Tree SSAによるGCCのコンパイル処理

GENERIC とGIMPLE

いくつかのフロントエンドは同じ「Tree」の表現を共有していますが、すべてのGCCのフロントエンドで使用される表現は1つもありません。どのフロントエンドも、独自の構文解析木を直接RTLに変換する責任があります。この問題に対処するために、GENERICと名前が付けられた新しい表現が導入されました。GENERICは、単純に、GCCで使用されている既存の木の表現すべてのスーパーセットです。RTLを生成する代わりに、すべてのフロントエンドは独自の構文解析木をGENERIC「Tree」に変換する責任を負います。GENERIC「Tree」は言語から独立しているため、入力言語の動作は、すべて、各フロントエンドにより正確に記述される必要があります。言語の動作の一部は"generic化"パスで変換され、その他の部分は"簡素化"パスで変換されます。

GENERICへ変換することで、プログラムの表現から言語依存性を取り除きます。しかし、なおGENERIC「Tree」は構造的に複雑なため、次の段階でさらに取り扱いやすい要素に分解されます。GIMPLEと呼ばれる新しい表現は、辞書的にはGENERICと同じですが、命令文に構造上の制約を付加します。たとえば、3つ以上のオペランドを持つ表現は許されない、関数を呼び出すときの引数には変数だけが許される（すなわち、関数の呼び出しをネストすることは許されない）、if文の述部には比較が1つのみ許さる、などの制約です。この形式は、McGill大学のMcCATコンパイラで使用されているSIMPLE表現[1]を取り入れたものです。

「GENERICとGIMPLE」と表題が付けられた節のプログラムにより、GENERICとGIMPLEの違いが示されています。図の中の形の異なる2つのプログラムは同じプログラムですが、GIMPLE形式で表現したプログラムの方がより簡潔になっていることに注目してください（長くはなっていますが）。これは、オプチマイザにとって物事をより易しくするための、キーとなる特性です。なぜなら、最終的には保守と改良がより容易なコンパイラにとって役に立つ、種々の単純化の前提になりうるからです。

GENERIC			  	GIMPLE

if (foo (a + b, c))		t1 = a + b
c = b++ / a			t2 = foo (t1, c)
endif				if (t2 != 0)
return c			  t3 = b
				  b = b + 1
				  c = t3 / a
				endif
				return c

図4. 同じコードのGENERIC形式とGIMPLE形式

静的単一代入（SSA）

静的単一代入形式は、GIMPLE上に構築される表現で、プログラム内のデータの流れを非常に明示的に明らかにします。中心となるアイデアはバージョニングというアイデアです。変数Xに新しい値が代入されるたびに、コンパイラによりXの新しいバージョンが生成されます。次に変数Xが使用されるときには、コンパイラにより最新のバージョンのXが調べられ、使用されます。この表現は完全にコンパイラ内部で使用されもので、生成されるコードに何らかの形で現れるものでも、デバッガにより観察できるものでもないことに注意してください。

たとえば、図5「プログラムの静的単一代入形式」のプログラムを取り上げてみましょう。左側はオリジナルのGIMPLEプログラムで、右側には、同じプログラムがSSA形式で示されています。

	GIMPLE program		  	SSA form

1	a = 3				a_1 = 3
2	b = 9				b_2 = 9
3	c = b++ / a			c_3 = a_1 + b_2
4	b = b + 1			a_4 = b_2 + 21
5	d = a + c			d_5 = a_4 + c_3
6	return d			return d_5

図5. プログラムの静的単一代入形式

すべての代入において、変数を修飾する新しいバージョン番号が生成されていることに注目してください。そして、式の中で変数が使用されるときは、常に、最新のバージョンが使用されています。従って、3行目で変数aを使用するときにはa_1を使用するように修正されていますが、5行目でaを使用するときには、a_1ではなく、a_4を使用するように修正されています。

では、なぜ、このことがオプチマイザにとって利点になるのでしょうか。たとえば、定数の伝搬と呼ばれる、非常によく使用される最適化について考えてみましょう。この最適化では、コンパイラは、定数値を使用して、コンパイル時にできるだけ多くの式を計算することを試みます。プログラムはSSA形式で表現されていて、かつ変数にはすべてバージョン番号が付けられているため、コンパイラは、簡単に、バージョン番号で指標付けされた配列を作成し、定数値を追跡できます。配列CSTがそのための配列だと仮定します。この場合、CST[3]の値は3で、CST[2]の値は9です。従って、3行目の命令文、c_3 = a_1 + b_2、を調べるときは、コンパイラはc_3は常に12に違いないと推定します（すなわち、CST[3]に12を保存します）。このようにしてすべての命令文を調べた後、次のような結果が得られます。

1	a_1 = 3
2	b_2 = 9
3	c_3 = 12
4	a_4 = 30
5	d_5 = 42
6	return 42

そして、今や、すべての定数を伝搬してしまったので、1行目から5行目までのすべての命令文がまったく何の意味がないことが分かります。このプログラムは単純に42を計算し、返しているだけです。

では、変数の最新のバージョンが何であるか決められないときには、どうなるのでしょう。実際のプログラムは、直線的に順番に実行されるコードであることはほとんどなく、制御の流れを変えるループや条件文を含みます。たとえば、次のプログラムでは、プログラムの実行時に条件文よる分岐がどうなるのか、コンパイラが判断することは不可能です。

x = foo ()
if (x > 10)
  a = 92
else
  a = 23
endif
return a

プログラムをSSA形式に変換しようとするとき、コンパイラは変数aの2つのバージョンのどちらを使用すべきか判断できません。このあいまいさを解消するために、2つの矛盾するバージョンをマージした3番目のバージョンが生成されます。このマージ操作は、次のPHI関数として知られています。

x_1 = foo ()
if (x_1 > 10)
  a_2 = 92
else
  a_3 = 23
endif
a_4 = PHI (a_2, a_3)
return a_4

コンパイラは、a_2とa_3のどちらが返えされるのか前もって知ることができないため、それらの2つのバージョンをマージしてa_4を生成します。これは、a_4はa_2とa_3の中のどちらかではあるけれど、どちらであるかは分からない、ということをオプチマイザに示しています。

結論

エンドユーザにはほとんど見えないものですが、コンパイラはシステムの重要な構成要素です。Linuxの人気が高まるにつれて、強力なコンパイラのニーズも高くなっています。この重要性に気づき、当社はGCCの内部を最新の技術で再構築するための、Tree SSAプロジェクトをスタートさせました。

Tree SSAにより、GCCに高度な解析と最適化の実装を可能にする、新しい最適化のフレームワークが提供されます。最初の実装は、GCC 4.0のリリースにより、ご利用いただけます。このフレームワークは現在も開発中ですが、次のリリースでは、ポインタおよび配列の境界のチェック（-fmudflap）、Fortran 90のサポート、自動ベクトル化、種々の高度なループ変換と既存のほとんどのスカラ最適化パスなど、いくつかの新機能がご利用になれます。

すべての解析と変換の基礎を広く知られ公表されているアルゴリズムに置くことにより、当社はGCCの保守と新機能開発に関するレッドハットの能力の向上を目指しています。さらに、標準的な技術を使用していますので、GCCに必ずしも精通してはいないコンパイラコミュニティのグループが、外部から参加し易くなっています。

作成者について

Diego Novilloはアルゼンチンのコルドバに生まれました。1993年にカナダに移り、アルバータ大学（エドモントン）で博士号を取得しました。彼は2000年にコンピュータ科学で博士号を得て卒業しました。現在、Red Hat Canadaでコンパイラグループのメンバです。このグループの主な業務の1つは、新しいポートの開発と新しい分析および最適化の実装でGCCを改良することです。彼はGCC用の新しいグローバル最適化フレームワークであるTree SSAの主要な設計者の1人です。

参考文献

[1] R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph.ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991.

[2] L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, B. Sridharan, "Designing the McCAT Compiler Based on a Family of Structured Intermediate Representations", Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, no. 457, Springer-Verlag.

[3] Robert Morgan.Building an Optimizing Compiler, Butterworth-Heinemann, 1998.

メインリンク:

Links for this section:

翻訳記事：

RED HAT SPEAKS