Continuation based C の GCC 4.6 上の実装について

大城信康^{†} 河野真治^{†}

GCC-4.6 をベースとした CbC コンパイラの実装を行った. CbC のコンパイラは GCC-4.2 ベースのコンパイラが 2008 年に開発されており, 以来 GCC のアップデートにあわせて CbC のコンパイラもアップデートが行われてきた. 今回は GCC-4.6 への実装を行った. 本論文では GCC-4.6 への CbC の具体的な実装について述べる。

The implementation of Continuation based C Compiler on GCC 4.6

Nobuyasu Oshiro^{†} and Shinji Kono^{†}

We implemented Continuation based C Compiler on GCC-4.6. CbC Compiler on GCC-4.2 was developed on 2008. Since then we kept to update it. In this paper, we introduce implemented Continuation based C Compiler on GCC-4.6.

1. 歴史的経緯

当研究室では, 継続により処理を行うプログラミング言語 Continuation based C (以下 CbC) を開発している. CbC の構文は C と同じであるが, 継続によりループ制御や関数コールが取り除かれる.

CbC のコンパイルには元々 Micoro-C 版の独自のコンパイラを用いていたが, 2008 年の研究において GCC-4.2 ベースの CbC コンパイラが開発され, 2010 年には GCC-4.4 へとアップデートが行われた. GCC への実装により,GCC の最適化やデバッガの機能を使うことができより実用的な CbC プログラミングが行えるようになった.

今回,CbC コンパイラを GCC-4.6 へとアップデートを行った. 本論文では, CbC,GCC の簡単な説明と,GCC-4.6 への実装を述べる.

2. Continuation based C (CbC)

Continuation based C (以下 CbC) は当研究室で開発しているプログラミング言語である. 構文は C と同じであるが, ループ制御や関数コールを取り除き継続 (goto) を用いている. また, コードセグメント単位で処理を記述するという特徴がある. 図 1 は CbC におけるプログラムの処理の流れを表している.

図 1 コードセグメント間の継続 (goto)

2.1 継続 (goto)

コードセグメントへと移った処理は C の関数と違って呼び出し元の関数に戻ることはない. コードセグメントは自身の処理が終えると goto により次のコードセグメントへと処理に移る. この goto によるコードセグメント間の移動を継続と言う.

継続の実態は jmp による関数の移動となる. 2.2 コードセグメント (code segment) CbC におけるプログラムの基本単位としてコードセグメントという概念がある. コードセグメントの記述の仕方は C の関数と同じだが, 型に“ code”を使って宣言を行うところだけが違う. 関数と同じように引数を持たせて継続させることもできる. しかし, 関数とは違ってリターンを行わない為返り値を取得することはできない. 図??は CbC で書いたプログラムの例である. 与えられた数 x の階上を計算して出力するプログラムとなっている.

† 琉球大学

University of the Ryukyu

c o d e p r i n t f a c t o r i a l ( int prod )

{

p r i n t f ( ” f a c t o r i a l = %d\n” , prod ) ;
e x i t ( 0 ) ;

}

c o d e f a c t o r i a l 0 ( int prod , int x )

{

i f ( x >= 1) {
goto f a c t o r i a l 0 ( prod ∗x , x −1);
} else {
goto p r i n t f a c t o r i a l ( prod ) ;

} }

c o d e f a c t o r i a l ( int x )

{

goto f a c t o r i a l 0 ( 1 , x ) ;

}

図 2 階上を計算する CbC プログラムの例

3. GCC の 3 つの内部表現

GCC-4.6 への実装の前に,GCC で扱われる 3 つの内部表現について触れておく.

3.1 3 つの内部表現 GCC は内部で Generic Tree, GIMPLE, RTL と

いう 3 つの内部表現を扱う. それぞれが読み込んだソースコードは Generic Tree, GIMPLE, RTL の順に変換されていき, 最後にアセンブラ言語へと出力される. 図 3 はアセンブラ出力までの流れを表した図である.

図 3 GCC によるコンパイルの一連の流れ

3.1.1 Generic Tree ソースコードより読み込んだ関数の情報を木構造で

表したものが Generic Tree となる. 関数の返り値, 引数, 変数の型, 条件式とプログラムの処理全てが木構造で表される. CbC の実装では parse の部分からこの Generic Tree 生成の部分に手が加わっている.

3.1.2 GIMPLE

Generic Tree で表現されたデータは GIMPLE というデータ構造に変換される. GIMPLE も Generic Tree と同じ構文木だが、より制約がかかった状態で作成された構文木となる. 制約は「1 つの枝に 4 つ以上の子を持たせない」等といったもので, GIMPLE へと変換されたデータは Generic Tree より簡単な命令で表されることになり最適化がかけやすくなる. CbC の実装では特に修正は加えていない.

3.1.3 Register Transfer Language (RTL)

構文木 GIMPLE は解析が行われた後 RTL へと変換される. RTL はレジスタの割り当てといった低レベルの表現で, アセンブラとほぼ同じ表現を行うことができる. プログラム内部では RTL も木構造で表される.

CbC における継続は, この RTL で行われる最適化の 1 つ Tail Call Elimination が重要となってくる.

4. GCC-4.6 への実装

前節までで CbC の基本仕様と GCC でのアセンブラ出力までの流れを確認した. ここからは GCC-4.6 への実装について述べていく.

4.1 “ code ”のパース

4.2 Tail Call Elimination

CbC の継続の実装には GCC の最適化の 1 つである Tail Call Elimination (末尾除去) が使われる. Tail Call Elimination とは関数の最後の処理で別の関数呼び出しを行った際に, call ではなく jmp を用いることができるという最適化である. 図 4 は Tail Call Elimination が行われた際のプログラムの処理を表している.

funcB の処理の最後に呼ばれた funcC は, 返り値を funcB ではなく funcA へと返す.

4.2.1 expand call

ある関数が Tail Call Elimination を行えるかどうかは expand call 関数で判断される. expand call 関数内でチェックされる Tail Call Elimination が行える条件は以下になる. caller 側と callee 側の返す値の型が一致している. 関数呼び出しがリターンの直前に行われている. 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.

図 4 Tail Call Elimination

CbC の実装では上記の条件を, 以下の様にして解決させている. 呼び出す関数がコードセグメントの場合返す値の型チェックを行わない.

コードセグメントへの継続を Generic Tree で表す際に,return の情報も直後に持たせる.

スタックサイズは決め打ちで行う.

スタックサイズを決め打ちで行うことで, ベースポインタを変えずにスタックを扱うことができる. これも CbC の 1 つの特徴である. 図 5 はコードセグメントの継続の際にスタックに積まれる引数を表している.

図 5 継続による引数のスタック格納の様子

expand call 関数の中で try tail call フラグ

4.3 引数渡し

通常コードセグメントの継続において, 引数は C の関数と同じスタックを用いて渡される. GCC には引数渡しをスタックではなくレジスタを用いて行う機能として fastcall がある. fastcall を用いてコードセグメントを宣言することで, レジスタを用いた速度の向上を図る.

4.3.1 fastcall

コードセグメントの引数渡しを fastcall によりできるだけレジスタを用いて行うようにする. C において fastcall を用いる場合は関数にキーワード “ attribute ((fastcall))”をつけて行う. だが, コードセグメントを全てこのキーワードをつけて宣言することは実用できではない. そこで, コードセグメントで宣言された場合,fastcall が自動で付くように実装を行う. 図 6 はコードセグメントに fastcall 属性を付与しているソースである.

図 6 コードセグメントへの fastcall 属性付与

if 文で条件を決めているのは,64 bit の場合 fastcall が標準で行れ, fastcall 属性を付けると warning を出すからである.

5. 評価

今回実装を行った GCC-4.6 ベースのコンパイラを GCC-4.4 ベース, Micro-C コンパイラとそれぞれ比較を行った. 比較を行うのはクイックソートのプログラムである. クイックソートは再帰的にプログラムされる為 CbC に向いているプログラムだと言える. 比較を行うのは以下のアーキテクチャと OS になる. x86/Linux x86/OS X また, 比較を行うプログラムは最適化 (-O0 オプション) を行わないものと, 速度最適化 (-O2 -fomit-frame-pointer) を行うものの 2 つ, それと -m32 オプションと -m64 オプションをつけたものそれぞれで行う.

表 1 が最適化無し, 表 2 が速度最適化有りとなる.

参考文献

1) 河野真治: “継続を基本とした言語 CbC の gcc 上の実装” . 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002

CPU/OS  GCC-4.4 GCC-4.6 Micro-C
x86/Linux  7.378  0.829  2.890
x86 64/OS X(-m32)  3.890  0.382  2.288
x86 64/OS X  4.078  0.450

表 1 アーキテクチャ毎の GCC と micro-c の速度比較（単位: 秒)(最適化無し)

CPU/OS  GCC-4.4 GCC-4.6 Micro-C
x86/Linux  3.252  2.906  2.890
x86 64/OS X(-m32)  1.827  0.934  2.288
x86 64/OS X  1.101  2.896

表 2 アーキテクチャ毎の GCC と micro-c の速度比較（単位: 秒)(速度最適化)

2) 河野真治: “継続を持つ C の回言語によるシステム記述” . 日本ソフトウェア科学会第 17 回大会論文集, Sep, 2000

3) 与儀健人, 河野真治: “ Continuation based C コンパイラの GCC-4.2 による実装” . 琉球大学 情報工学科学位論文, 2008

4) 与儀健人, 河野真治: “組み込み向け言語 Continuation based C の GCC 上の実装” . 琉球大学大学院 理工学研究科学位論文 (修士), 2010

5) 下地篤樹, 河野真治: “線形時相論理を用いた Continuation based C プログラムの検証” . 琉球大学大学院 理工学研究科情報工学専攻学位論文 (修士), 2008

6) 楊挺, 河野真治: “ Continuation based C の実装” . 琉球大学大学院 理工学研究科情報工学専攻学位論文 (修士), 2002

7) GNU Compiler Collection (GCC) Internals: “ http://gcc.gnu.org/onlinedocs/gccint/ ”