先週は、簡単なコンパイラを作成した。そして、そのコンパイラに 簡単な改良を試みた。
Makefile どのようにcompileするかの指示 s-compile.c compiler本体(interpreterとほとんど同じ) s-code-09.c Code Generator ending.09 Code Generator Additional File s-code-rs6k.c Code Generator for RS6000 (etc...) s-token.c Tokenizer s-tree-compile.c Intermidiate Tree Version
必ず Makefile を 作り、make を使うことにしよう。つまらないタイプミスから開放される。 以下は Makefile の一部である。
TEST = s-09
CC = cc
COMPILER = s-compile.o s-token.o
CFLAGS = -g
MC09EMU = ../emulator/util09/v09
MC09ASM = ../emulator/util09/a09
test-09: s-09
./s-09 < s-input.txt > s-output.a09
$(MC09ASM) s-output.a09
$(MC09EMU) s-output
s-09: s-compile.h $(COMPILER) s-code-09.o
$(CC) $(CFLAGS) -o s-09 $(COMPILER) s-code-09.o
test: $(TEST)
$(TEST) < s-input.txt > s-output.s
$(CC) s-output.s
a.out
s-rs6k-r: s-compile.h $(COMPILER) s-code-rs6k-r.o
$(CC) $(CFLAGS) -o s-rs6k-r $(COMPILER) s-code-rs6k-r.o
ここで、make test-09 とすることにより、MC6809 emulator を使った
テストをすることができる。
最初の6行は変数の定義。ここではMC6809のemulatorとassemblerを指定している。 その後の$(COMPILER)などは最初に指定した変数で置き換えられる。
3行目では test-09 の作り方を説明している。:のすぐ後には、s-09 つまり、 s-09 が test09 を作るために必要なことを示している。s-09 の作り方は、 最後の2行に書いてある。ここでも : の後に、s-09 を作るための原料が書いてある。 s-compile.o と s-compile.h と s-code-09.o が必要である。*.o は object file であり、*.c があれば、それから自動的に作られる(と make は考えて いる。実際には、これらの暗黙のルールがライブラリなどに置いてある)。
実際の作り方は、: の行のあとにタブを先頭に持つ行を続けて書く。スペース ではいけない。良くある間違いなので気を付けよう。この 行が指定され変数を置換された後、 sh に渡されて実行される。test-09 では、s-09 が既に作られていれば、それを使ってs-input.txt をcompile して、assembler で assemble し、結果を emulator で emulate する。
make は、Makefile を参照しながら、ファイルの時間を見る。そして、生成 されたものよりも、新しい変更時間を持つ原料があれば、その生成をやり直す。 もちろん、原料の作り直しが必要かどうかも自動的に判断する。これは、 一種の interpreter である。
Makefile の中で、
TEST = s-rs6k-r COMPILER = s-compile-tree.o s-token.oとすると、rs6k の tree version が生成されてテストされる。すべての*.o が、まだ作成されていない時に、make test とすると、どのような順序で、 どのようなコマンドが実行されるかを記述せよ。そのコマンドが成功したとして 、さらにs-compile-tree.c を編集したする。その後、make test としたら、 コマンドはどのような順序で実行されるかを記述せよ。また、なぜ、その 順序で実行されたのかを Makefile の中のルールに合わせて、 簡単に説明せよ。
もし、8進、16進を許すだけならば、変更はs-compile.cだけで良い。実は これがもっとも簡単な変更である。
例えば、論理演算 & と | を付け加えたいとしよう。Parser(構文解析)部分の 変更は、Interpeterとの場合とほとんど変わらない。例えば、+ と同じ レベルに|を付け加えるとすると、(これは安易すぎる不便な構文である)
void
aexpr()
{
int d;
emit_comment();
mexpr();
while(last_token!=EOF) {
switch(last_token) {
case '|':
emit_push();
mexpr();
emit_calc(O_OR);
break;
case '&':
emit_push();
mexpr();
O_ORは s-compile.h で定義する。ここで OR を計算するcodeを生成しなければ
ならない。そのためには、code generator
emit_calc を拡張しなくてはならない。
void
emit_calc(op)
int op;
{
if(op==O_SUB) {
printf("\t%s ,S++\n",opcode[op]);
printf("\tNEGA\n");
printf("\tNEGB\n");
printf("\tSBCA #0\n");
} else if(op==O_ADD) {
printf("\t%s ,S++\n",opcode[op]);
} else if(op==O_SUB_R) {
printf("\tsubd ,S++\n");
などとなっているので、ここにORをおこなうcodeを付け加えれば良い。
ANDD ,S++ というのがあればO_ADDなどと同じ処理で良い。しかし、
残念ながら6809には、そういう命令はない。(前回の付録参照)
しかし、ちょっと考えれば引き算と同様、Register AとRegister Bを 順に計算すれば良いことがわかる。Stack 上の順番は、Bigendian である ことを考えれば、
ORA ,S+
ORB ,S+
という code を出せば良い。(S++でなく、S+であることに注意) このためには、
} else if(op==O_OR) {
printf("\tORA ,S+\n");
printf("\tORB ,S+\n");
とすれば良い。ANDに関しても、全く同じように実現できる。
このように MC6809では、D or A,B というAccumulatorとMemory間で計算を行うのが 普通である。これは、Register-Memory Computation 中心の Architecture である。一方、Registerをたくさん持っている場合は、まず必要なデータを loadし、Register-Register Computation をおこない、その後、結果を store するというのが一般的である。これは、Load-Store Architecture と呼ばれる。
例題のdirectoryにある compile.c では、さらにいろいろな拡張を試みている。 参考にして見よう。
今までの簡単なコンパイラでは、Register-Memory Architecture を使い、 Register 1つと、Stackの先頭の演算に式をコンパイルしていた。ここでは、 さらに、Load-Store Architecture を想定して、Register 上のでの演算に コンパイルして見よう。
最近ではRegisterの数は32が多く、その中で自由に使えるものは10-20程度 ある。通常の式であれば、スタックの深さは10以下であり、すべてRegister 上で計算できる。この部分を記述するのは簡単である。もっと難しいのは、 複数の式でRegisterを共有する場合であり、この時には、共有する変数は 非常に大量になる。これに対して適切なRegister割当をおこなうのがコンパイラ の最適化として重要である。この割当の善し悪しは、関数呼出時の手間や Cache(キャッシュ)の 占有度に影響し、最終的にプログラム全体のPerformanceに影響する。この 問題は、授業の後半で議論することにしよう。
さて、Registerを使った式の計算は、スタックに変数を取っておく代わりに Registerに取っておくだけである。したがって、コンパイラを変更しないで、 コード生成系のみを変更するようにしよう。s-code-rs6k.c がスタックを 使う場合のコード生成系である。これを Register 割当をおこなう s-code-rs68k-r.c に直そう。
スタック演算の場合は以下のようなコード生成を行う。
void
emit_push()
{
printf("\tstu r3,-4(SP)\n"); /* r3 を accumulator として使う */
} /* SP は自動的に -4(SP) になる */
void
emit_value(d)
int d;
{
printf("\tcal r3,%d(r0)\n",d&0xffff); /* 下位16bit */
if(d&0xffff0000) { /* 上位16bit (もしあれば) */
printf("\tcau r3,r3,%d\n",(d&0xffff0000)>>16);
}
}
void
emit_load(d)
int d;
{
printf("\tl r4,T.28.variable(RTOC)\n"); /* 配列のアドレスをr4へ */
printf("\tl r3,%d(r4)\n",d*4); /* r3 に load */
}
void
emit_store(assign)
int assign;
{
printf("\tl r4,T.28.variable(RTOC)\n");
printf("\tst r3,%d(r4)\n",assign*4);
}
char *opcode[] = {
"",
"sf",
"a",
"muls",
"divs",
"",
"",
"",
"",
"sf",
"divs",
};
void
emit_calc(op)
int op;
{
printf("\tl r4,0(SP)\n"); /* スタック上の値を r4 に */
printf("\tai SP,SP,4\n"); /* スタックを下げる */
if(op==O_DIV || op==O_SUB_R) { /* 順番が逆の演算 */
printf("\t%s r3,r4,r3\n",opcode[op]); /* 3項演算 */
} else {
printf("\t%s r3,r3,r4\n",opcode[op]); /* 3項演算 */
}
}
他の20本以上あるレジスタは使われてないし、いちいちスタックから
データを持って来るというかったるいコードが出力される。
emit_push() でスタックにaccumlatorの値をsaveする代わりに、新しく accumlator として使う Register を割り当てれば良い。このために、 get_register() という手続きを考える。
char *reg_name[] = {
"r0","r1","r2","r3","r4","r5","r6","r7",
"r8","r9","r10","r11","r12","r13","r14","r15",
"r16","r17","r18","r19","r20","r21","r22","r23",
"r24","r25","r26","r27","r28","r29","r30","r31"
};
#define MAX_REGISTER 32
char regs[MAX_REGISTER];
char reg_stack[MAX_REGISTER];
int
get_register() {
int i;
for(i=0;i <MAX_REGISTER;i++) {
if (! regs[i]) {
regs[i]=1;
return i;
}
}
error("Expression too complex (register overflow)");
return -1;
}
regs[]という配列に、そのRegisterが使われているかどうかを示すflagを
いれておく。get_register()では、最初のflagが開いているRegisterの
番号を返す。もちろん、番号とassemblerの中でのRegister名との対応を
示すものが必要なので、それは、reigster_name[]という配列を作って
おく。このうちいくつかは、最初から使用不可(システムやarchitectureが
使用している、例えば、SP, RTOC など)である。
どのRegisterをsaveに使ったかはコンパイラが自分で覚えてなくてはいけない。 これにはスタックを使う。これは、ちょうど実行時のスタックをコンパイル時に 部分計算していると考えることもできる。先に計算できる部分なわけである。 accumlatorを表す Registerの番号を current_register としよう。
void
emit_push()
{
reg_stack[reg_sp++] = current_register;
lrn = reg_name[current_register];
current_register = get_register();
crn = reg_name[current_register];
}
ここで、lrn は last regster name, crn は current register name につもり
である。どうせ、すぐ使うのだから、ここで代入しておこう。emit_load, emit_store,
emit_value は、current_register に値をいれるだけなので、以下のように簡単に
書くことができる。
void
emit_value(d)
int d;
{
printf("\tcal %s,%d(r0)\n",crn,d&0xffff);
if(d&0xffff0000) {
printf("\tcau %s,%s,%d\n",crn,crn,(d&0xffff0000)>>16);
}
}
void
emit_load(assign)
int assign;
{
printf("\tl r4,T.28.variable(RTOC)\n");
printf("\tl %s,%d(r4)\n",crn,assign*4);
}
void
emit_store(assign)
int assign;
{
printf("\tl r4,T.28.variable(RTOC)\n");
printf("\tst %s,%d(r4)\n",crn,assign*4);
}
r3が、crnに置き換わっただけである。
実際の計算を行うところでは、stackを一つ下げることをおこなう必要が ある。ここではRegister-Register演算をおこない、入らなくなった Registerの regs[] に 0 を入れれば良い。これは pop_register() という手続きにしよう。
char *
pop_register() {
int i,j;
j = current_register; /* 直前の値 */
i = reg_stack[--reg_sp]; /* どれと演算するのかを i にいれる */
lrn = reg_name[i]; /* それが last register name となる */
regs[j]=0;
current_register = i; /* 結果を直前の値の方に入れることにする */
crn = reg_name[i]; /* current register は新しくなる */
return reg_name[j]; /* 古い current register の値を返す */
}
void
emit_calc(op)
int op;
{
char *orn;
orn = pop_register(); /* old register name */
if(op==O_DIV || op==O_SUB_R) { /* current = old / last */
printf("\t%s %s,%s,%s\n",opcode[op],crn,lrn,orn);
} else {
printf("\t%s %s,%s,%s\n", opcode[op], crn, orn, lrn);
}
}
ここでは、スタックを使う場合のように、最後の結果が最初のRegisterに
なるように工夫している。
これにより、スタック上での演算よりも確実に高速なコードを出すことが できる。例えば、 0+(1+(2+(3+(4+(5+(6+(7+8)))))))-(0+(1+(2+(3+(4+(5+(6+(7+8)))))))) のような場合である。しかし、これを 0+1+2+3+4+5+6+7+8-(0+1+2+3+4+5+6+7+8)と書き換えるとReisterは一つ しか使わないで済む。もちろん、中間木を使ってコンパイル時に定数計算を してしまえば、もっと簡単になる。
このような書き換えは簡単だと思うかも知れないが、実際には同等な式への 変換は無数にあり、もっともRegisterが少なくなるような式の変形は自明 ではない。このような変形を行うためには中間木への変換が必ず必要となる。 このような式の変換に付いても後で議論することにしよう。
0+(1+(2+3))-(0+(1+(2+3))) の式の計算を上の2種類のcompiler によりRS6000の命令に変換した結果を記述せよ。0+1+2+3-0+1+2+3 の場合はどうなるか? RS6000には、
ai[.] ai r3,r1,-45 r3=r1+(-45) add immediate [set flag CR0]
16bit singed constatnd
という命令がある。これを使った場合はもっと短いコードになる。
この命令を出力するcompilerを作るには、どうすれば良いか考察し
てみよ。
s-code-rs6k.c s-code-rs6k-r.c を使った、 s-rs6k と s-rs6k-r について、論理演算 &,| を拡張して見よう。余裕が あれば他の拡張にも挑戦して見よう。
これから、Micro-C をざっと読みながら、より詳細な技術について解説して いく。そのまえに、Micro-C の全体構成をざっと見て見よう。
Micor-C の全体構成