Compiler Construction Lecture 12/02

Compiler Construction Lecture 12/02

先週の復習

先週は、簡単なコンパイラを作成した。そして、そのコンパイラに 簡単な改良を試みた。

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

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 について、論理演算 &,| を拡張して見よう。余裕が あれば他の拡張にも挑戦して見よう。



Micro-Cの全体構成

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

Micor-C の全体構成

字句解析 getsym



おまけ: RowerPCの命令

RowerPCの命令の一部

prev
next