Compiler Construction Lecture 11/20

先週の復習

先週は、簡単なコンパイラを作成した。そして、そのコンパイラを中間木を生成する方法に変換した。

今週の課題は、問3について、

Subject: compiler report 11/20

というSubjectのメールにして、kono@ie.u-ryukyu.ac.jp まで送ること。また授業を受けなかったものは、問1についても、

Subject: compiler lecture 11/20

というサブジェクトで送ること。また、Micro-C のソースリストを配布したので、それも取りに来ること。

レジスタを使ったコンパイル

では簡単なコンパイラとその構成を調べて見よう。

Simple Compilerの構成

  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

Simple CompilerのMakefile

必ず 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 である。

問1

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 based compiler

今までの簡単なコンパイラでは、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が少なくなるような式の変形は自明ではない。このような変形を行うためには中間木への変換が必ず必要となる。このような式の変換に付いても後で議論することにしよう。

問2

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を作るには、どうすれば良いか考察してみよ。

問3

s-code-rs6k.c s-code-rs6k-r.c を使った、 s-rs6k と s-rs6k-r について、論理演算 &,| を拡張して見よう。余裕があれば他の拡張にも挑戦して見よう。

中間木を使い、a+(b+c) -> (a+b)+c のような変形をサポートする
配列をサポートする
Cの3項演算子 (cond)?(true):(false)
Pointer演算

Micro-Cの全体構成

これから、Micro-C をざっと読みながら、より詳細な技術について解説していく。そのまえに、Micro-C の全体構成をざっと見て見よう。

Micor-C の全体構成

おまけ: RowerPCの命令

RowerPCの命令の一部