Cコンパイラの創り方
はじめに
CQ出版社のDesign Wave Magazine 11月号に掲載されている第11回LSIデザインコンテストの課題は命令数が9つのとても小さいRISCプロセッサです．このRISCプロセッサのCコンパイラを作ります．命令数9つと限られていてメモリ空間もデータと命令にそれぞれ64ワードずつしかありませんから，汎用のCコンパイラではなく，1から100までの整数の和を計算する機械語を生成できればよしとします．
なぜコンパイラを作るのか.
ソフトウェアの開発速度を劇的に向上できるからです．
例えば先ほどの1から100までの和の合計を求めるコードを，アセンブラとC言語で書いてみて，記述にかかる時間と書いたコードの読みやすさを比較するとよく分かります．C言語はアセンブラと同等の効率のコードを読みやすく記述することができます．
また1からプロセッサを設計するということは，ソフトウェア開発は設計開発環境の構築からスタートすることになります．誰でも作れるわけではないという意味で，この設計環境構築で最もネックになるのがCコンパイラです.(次がデバッガ．アセンブラやプリプロセッサの文字列処理系は誰でも作れる.)
このボトルネックを越えるために，手軽に誰にでもできるCコンパイラの作り方を紹介します．
お仕事でやるのにメリットがあるか?
お仕事でCコンパイラを採用するかどうかは，状況によります．Cコンパイラがあって嬉しいのは開発者だけ，の場合がほとんどです．最終成果物としてのファームを作る観点からは，Cコンパイラの有無は関係ありません．Cコンパイラを作るメリットは，開発労力の低減，機械語変更やコード再利用が容易など開発者へのものがほとんどです．デメリットは，Cコンパイラができるまで本当の意味での開発がスタートできない(開発完了までの時間がかかる)など開発スケジュールに関するものになります．
通常SOCに入れるマイコン程度のファームウェアの規模は最大でもアセンブラで3万行を超えない(30kワードくらい)程度です．この規模では，機械語をがりがり書いてもよし，あるいはもう少しスマートにC言語でソースを書いて市販のマイコンなどでデバッグを完了させた後に人手でコンパイルする(人間コンパイラ ^^；)のもよしです．
プロセッサコアを再利用するなどしてファーム開発規模がそこそこあるならば(最低でも20万行程度の開発規模を超えないと割りに合わないでしょうが)，コンパイラによる開発労力低減はコスト低減の観点から大きな意味を持つでしょう．
System On a Chip (SOC)でプロセッサを1から設計する利点
SOCで1からプロセッサを設計する利点は，使用目的に合わせて徹底的に作りこめる，回路サイズや電力などを小さくできるなどです．使用目的が明確であるゆえに，汎用プロセッサでは手が届かないところまで作りこめます．
コンパイラの構成
一般的にCコンパイラは，C言語を解析してコンパイラ特有の中間言語に変換するフロントエンドと，その中間言語をプロセッサ特有の機械語に変換するバックエンドで構成されます．プロセッサ特有のためにバックエンドは作らざるを得ません．しかし，フロントエンドはC言語で共通なので，既存コンパイラのフロントエンド，もしくはコンパイラを作るための共通インフラストラクチャが利用できます．
コンパイラインフラストラクチャを使う?
コンパイラの共通インフラストラクチャとして，SUIF，LLVMおよびCOINSがあります．これらはC言語などを中間コードに変換するフロントエンドと，バックエンドを作成するのに便利なライブラリを提供しています．SUIFおよびLLVMはフロントエンドにgccを移植しており，COINSは独自にJavaで記述しています．バックエンドは，SUIFはJavaおよびC++のライブラリが，LLVMはC++のライブラリが，COINSはJavaのライブラリがあります．中間言語から機械語への変換をコードで書く手間を低減するために，COINSはLISB風の機械記述ファイルを受け付けます．
ちょっといじってみる
実際にLLVMをいじってみました．LLVMを特定ターゲットに移植する方法はサイトに書かれているので情報に不足はありません．
ですが例えばレジスタ割り当てはC++のどのクラスを使えばよいかなど，こう動かしたいのだがどう書けばいいか，これがさっぱりつかめません．(C++は苦手)
COINSの機械記述は(多分 gcc から大きく影響を受けたのであろう) LISP風言語で記述します．これもLISPを知らない人間には，さっぱり読みづらい．
そのため，コンパイラインフラストラクチャを利用することはあきらめました．
既存コンパイラを使う
既存コンパイラを移植することにします．既存コンパイラには，The GNU C compiler (gcc), lccおよびpccなどがあります．
それぞれいじってみました．まずgcc (version 3)は移植の手間が半端ではありません．gccの中間言語から機械語への変換をRTL(register transfer language)というLISP風言語で記述します．これが読みづらい．読むことすら難しいのに，希望の処理を書くことや，というものです．
次にlcc.こちらは書籍に詳細があります．機械記述はC言語に独自記述が混ざる独特の記載をします．ですが，先ほどのgccのRTLよりも読みやすいと思います．SDCCは多くのマイコンがサポートされたコンパイラですが，これの機械記述はlccとほとんど同じです(lcc由来?)．
最後に試したのがpccです．これの機械記述はC言語で構造体宣言で行い，このコードを変換プログラムでCコードに変換しています．中間言語から機械語変換ルールをC言語で書けるので記述言語を新たに覚える必要もなく，またルールも(コードを追っていけば動きが分かりやすく書かれているために)非常に読みやすい．そこでpccを移植することにしました．
pccの移植方法
PCCの構成は http://pcc.ludd.ltu.se/ftp/pub/pcc-docs/porttour.ps に移植方法は http://pcc.ludd.ltu.se/ftp/pub/pcc-docs/targdocs.txt に分かりやすいドキュメントがあります．拡張子.psのドキュメントはPostScript形式です．オンラインサービス http://www.ps2pdf.com などでPDF形式に変換できます．
フロントエンドおよびバックエンドそれぞれの移植方法を書いていきます．
ソースコード
PCCのコードは pcc-08613.tgz を使用しました．また移植したコードは http://febhare.bake-neko.net/Src/pcc_porting_diff.tgz です．
移植したコードを走らせるには，pccのコードを展開した後に，上記の移植コードを上書きでコピーしたのちにMakeします．
pccは厳密に同じ日付ではなくてもコンパイルできると思います．
コマンドは以下のとおりです:
% tar xzf pcc-080613.tgz % tar xzf pcc_porting_diff.tgz % cd pcc-080613 % cp -Rf ../pcc_porintg_diff/* ./ % ./configure --target=srp-unknown-netbsd % make
コードをコンパイルできるようにする
pccはビルドにThe GNU configure and build systemを利用しています．まずは移植用コードをビルドできるようにします．
まずプロセッサ名をSimple Risc Processor の頭文字をとりsrpとします．移植コードは "arch/srp"以下に置くとします．
サポートするOSはNetBSDとします．
まずconfigure.acの20行目あたりを以下のように編集します．ターゲットCPUがsrpのときにtargmachにsrpを設定します．
case "$target_os" in
netbsd*)
targos=netbsd
abi=elf
case "$target_cpu" in
srp*) targmach=srp ;;次に"os/netbsd/ccconfig.h"の57行目に以下を追加します．ターゲットマシンがsrpのときにコンパイル引数に定義__srp__を追加します．
#if defined(mach_srp)
#define CPPMDADD { "-D__srp__", NULL, }このあたりはarmなど既存の設定をそのままコピーすればよいです．
機械の記述
"arch/srp/machdef.h"にターゲットのビット幅，アライメント，値域，そしてレジスタを記述します．ビット幅は，例えばChar型ならば
#define SZCHAR 8
のようにビット幅を定義します．アライメントも同様です．
レジスタの定義は，クラス，レジスタの状態，そして重なりをそれぞれ指定します．
レジスタは，例えば8-bit幅と16-bit幅のレジスタ，浮動小数点用のレジスタと，いくつかのクラスに分けます．
それらのクラスは，RSTATUSにSAREGのようにSxREGの形で定義します．クラスはAからDまでの4通りが取れます．
今回のターゲット SPR の0番のレジスタは常に0の定数なので，レジスタ割り当てに使いません．そのようなレジスタは0を設定します．レジスタが関数呼び出し側で保存されるならTEMPREG，被呼び出し側で保存されるならPERMREGとします．
最後にレジスタの重なりを指定します．SPRはそうではないのですが，ターゲットによっては例えば16-bitレジスタを2本の8-bitレジスタとして使うことができます．このようなレジスタの重なりをROVERLAPに指定します．これは重なり合うレジスタを配列で指定します．
フロントエンドの移植
フロントエンドは，"arch/srp/local.c" と "arch/srp/code.c" から構成されます．解析したソースコードから構築した解析木をバックエンドに送る前に処理をすることができます．ここで機械依存の処理をすることはないので，他の適当なアーキテクチャからファイルをコピーしてくればよいです．
バックエンドの移植
"arch/srp/local2.c", "arch/srp/table.c", および"arch/srp/order.c"を書きます．まず中間言語を機械語に変換するルールを記述するtable.cを説明します．
table.c にはstruct optab の配列 table[]を書きます．struct optab は"mip/pass2.h"で定義される下記の構造体です．
/* code tables */ extern struct optab { int op; int visit; int lshape; int ltype; int rshape; int rtype; int needs; int rewrite; char *cstring; } table[];
この構造体に，例えば加算ならば下記のように値を設定します．
{ PLUS, INAREG,
SAREG, TINT,
SAREG, TINT,
NAREG|NASL, RESC1,
" add A1, AL, AR ; plus\n", },
イメージとして，ツリー構造の中間言語の節にあてはまるstruct optabをそれぞれ適用して，その都度機械語に変換していきます．
struct optab のフィールドopにはマッチするノードタイプを設定します．ノードタイプは"mip/node.h" 109行目から定義されています．演算"+"を意味するノートタイプPLUSを指定しています．
struct optab のフィールドvisitには，このルールを適用する場面をかく(みたい?)です．コードを生成するときに，このフィールドのビットが立っているかどうかで，ルールの適用を行っているみたいです．例えば 条件分岐の機械語を生成するときは FORCC が立っている物を使うようです．よく理解していないのですが，結果をレジスタに収めるものはINAREG (クラスAのレジスタ?)を指定しています．
struct optabのフィールドlshapeおよびltypeは，変数の型などを指定します．lxxは木の左ノード，rshape, rtypeは木の右ノードを示します．shapeはpass2.hの73行目から定義されていて，レジスタクラス SxREG ，コンスタントSCON，レジスタ間接アドレッシングSORえｇなどが設定できます．typeはpass2.hの112行目から定義されており，C言語の変数型が例えばTCHARのように設定できます．
フィールド needsは，このルールを適用するのに必要なレジスタなどを指定します．なにも必要ないなら0を設定します．例えばCLASS A のレジスタが2つ必要ならば 2*NAREGとします．さらにこの2つのレジスタを，ツリーの左要素のレジスタと共有してよいならばNASL(ツリーの右要素と共有するなら NASR)を追加します．ここで確保したレジスタは，最後の機械語生成で，例えばクラスAのレジスタならばA1, A2のように指定できます．
フィールドrewriteは，このルールの結果をどこに保存されるかを設定します．確保したレジスタ(先ほどの例でいえばA1)に収められるならRESC1 (同様にA2ならばRESC2)を設定します．
下記のような単なる型変換ならば，RLEFT/RRIGHTのように木の子要素をそのまま指定します．下記の例ではTCHARのノードをTSWORDもしくはTSHORTの型に変換します．
{ SCONV, INAREG,
SAREG, TCHAR,
SAREG, TSWORD|TSHORT,
0, RLEFT,
" # convert char to short/int\n", },
代入を行うASSIGNなどは，rewriteにRDESTを指定しなければいけません．(文法チェックにそう書かれている.)
最後のcstringは変換結果を文字列で指定します．アルファベット小文字はそのまま出力されます．アルファベット大文字のものは以下のルールで置換されます．
この置換は mip/match.cの 265行目の関数expand()が行います．使うのは'A'のアドレス指定だと思います．関数expand()は'A'で始まる要素を見つけると，local2.c にある関数adrput()を呼び出します．この関数adrput()は自分で実装します．また，'Z'で始まるものは"spr/arch/local2.c"に記述する関数zzzcode()を呼び出しますから，ターゲット固有の特別な変換をしたいときに頭文字Zで始めておけば便利かもしれません．
2番目の文字が，'L' , 'R'ならば木の左/右要素を示します．数字'1'~'4'ならば，例えばフィールドneedsで要求したレジスタが割り当てられます．
生成されるアセンブラコードの品質
make すると cc/ccom/srp-unkown-ccom という実行ファイルができます．これがプリプロセッサもない本当のコンパイラ本体になります．
以下のサンプルコード"sample.c"をコンパイルしてみます．
void main()
{
int j = 0;
int index = 0;
for(index = 0; index < 100; index++)
j = index + j;
}% cc/ccom/srp-unkown-ccom sample.c
以下のアセンブラが出力されます．変数の初期化の為に，もともとのSRPにはなかった定数をレジスタに読み込む命令"ld"を追加しています．これを見ると変数をいちいちメモリに書き戻すなど，かなり無駄の多いコードが生成されています．変数宣言にregisterをつけても同様．また試しに他のアーキテクチャ(arm, mips)のコードも見てみましたが，同様にメモリに変数を書き戻すアセンブラが出力されていました．
レジスタファイルのみで演算するコードを生成して欲しいところです．
.main: ; function
.L11:
.L13:
ld r1, #0 ; opltype sany scon
sw r1, -16 (fp) ; store (u)int/(u)long
ld r1, #0 ; opltype sany scon
sw r1, -20 (fp) ; store (u)int/(u)long
ld r1, #0 ; opltype sany scon
sw r1, -20 (fp) ; store (u)int/(u)long
.L16:
ld r1, #100 ; opltype sany scon
lw r2, -20 (fp) ; load (u)int to reg
beq r2, r1, .L15
lw r1, -16 (fp) ; load (u)int to reg
lw r2, -20 (fp) ; load (u)int to reg
add r2, r2, r1 ; plus
sw r2, -16 (fp) ; store (u)int/(u)long
.L14:
ld r1, #1 ; opltype sany scon
lw r2, -20 (fp) ; load (u)int to reg
add r2, r2, r1 ; plus
sw r2, -20 (fp) ; store (u)int/(u)long
l .L0 ; goto
.L15:
.L12:
PCCの利点，コンパイルが早い
このようにPCCの移植はtable.cに適切な変換ルールを記述していきます．コンパイルエラーなどが発生するたびにルールを見直し，コンパイルをすることになります．pccが移植に必要とするのはたかだか5つのファイルだけですから，例えばtable.cを変更しても，たかだか5秒程度で再コンパイルが完了します．
PCCのこの再コンパイルの早さは，ちょっとコードを変更しては都度対応するような，ホビーな開発スタイルでは重宝します．
まとめ
SOC開発で1からプロセッサを設計するときのソフトウェア設計環境構築として，(簡単にすぐ作るのが難しいためにネックになる)Cコンパイラの作り方を紹介しました．非常に簡略化されたRISCプロセッサ向けだったこともあり，整数演算とforループをアセンブラにできるものを作りました．このコードを骨として追加することで，今回省略した関数呼び出し(prolog, epilog)，変数の変換(char -> intなど)，構造体や列挙型のサポートなどC言語としてサポートすべきものを作れるはずです．
参考文献
