Compiler Construction Lecture 1/31
Menu Menu
先週の復習
先週は、- Micro-Cにおけるリスト構造
- 右辺値と左辺値
- 式のコード生成
制御構造のコンパイル
コンパイラ全体の中から見ると制御構造のコンパイルは、それほど大きくない。statement()という一つの構文要素の中で閉じている。例えば、doif()では、if文の処理をおこなう。
742 doif()
743 {int l1,l2,slfree;
744 getsym();
745 checksym(LPAR);
746 slfree=lfree;
747 bexpr(expr(),0,l1=fwdlabel());
748 lfree=slfree;
749 checksym(RPAR);
750 statement();
751 if(sym==ELSE)
752 { if (l2 = control) jmp(l2=fwdlabel());
753 fwddef(l1);
754 getsym();
755 statement();
756 if (l2) fwddef(l2);
757 }
758 else fwddef(l1);
759 }
l1=fwdlabel()というのが未来に使うラベルの生成を行っている。ラベルの位置が決まった時点でfwddef(l1)を行う。if文にはelse
節がある場合があり、その場合には、ラベルは二つ必要である。(controlの役目はなにか?)
これと、ラベルにjumpするjump(label)を使えば、ほとんどの制御構造のコード生成が可能となる。残りは、switch文やreturn文、そして、関数呼び出しである。
条件分岐の取り扱い
条件分岐は、構文解析はexpr()を使うが、コード生成がgexpr()とは異なり、bexpr()により処理がおこなわれる。bexpr()は、引き数として、構文木、条件、ラベルを取り、構文木の一番上が条件比較だったら、それお条件分岐に書き換えている。
1560 bexpr(e1,cond,l1)
1561 int e1,l1;
1562 char cond;
1563 {int e2,l2;
1564 if (chk) return;
1565 e2=cadr(e1);
1566 switch(car(e1))
1567 {case LNOT:
1568 bexpr(e2,!cond,l1);
1569 return;
1570 case GT:
1571 rexpr(e1,l1,cond?"GT":"LE");
1572 return;
1573 case UGT:
1574 rexpr(e1,l1,cond?"HI":"LS");
1575 return;
Micro-C のcode生成部分の構造
- mc-code.html Micro-C のコード生成部の構成
先週の問題の解答
以下のCのstatementに対応するMicro-Cの中間木と生成されるi386のコードについて考察せよ。ただし、以下のint *a; という型を仮定する。- *a = 1;
- a = &a[3];
- *a = *(a + a[3] + 2);
- a = *( &a + 3);
答え
もちろん、生成されるコードはコンパイルすれば簡単にわかってしまう。これができなかった人は、さぼっているだけだろう。また、中間木に関しても、それを印刷するコンパイラを作成したので答を得るだけならば誰にでもできる。実際、/usr/open/lectures/kono/compiler/mc/mc1 を使うと、(source を list 中に含める -s option を使って) 以下のようにc.out が出力される。
# *a = 1;
* generate code on type:
* list(INT)
* expr:
* list(ASS,
* list(INDIRECT,
* list(RGVAR,0,a)),
* list(CONST,1))
movl $1,%eax
movl a,%ecx
movl %eax,(%ecx)
# a = &a[3];
* generate code on type:
* list(POINTER,
* list(INT))
* expr:
* list(ASS,
* list(GVAR,0,a),
* list(ADD,
* list(RGVAR,0,a),
* list(CONST,12)))
movl a,%eax
addl $12,%eax
movl %eax,a
# *a = *(a + a[3] + 2);
* generate code on type:
* list(INT)
* expr:
* list(ASS,
* list(INDIRECT,
* list(RGVAR,0,a)),
* list(RINDIRECT,
* list(ADD,
* list(ADD,
* list(MUL,
* list(RINDIRECT,
* list(ADD,
* list(RGVAR,0,a),
* list(CONST,12))),
* list(CONST,4)),
* list(RGVAR,0,a)),
* list(CONST,8))))
movl a,%ecx
movl 12(%ecx),%eax
sall $2,%eax
addl a,%eax
movl $8,%edx
movl (%edx,%eax),%edx
movl a,%ecx
movl %edx,(%ecx)
# a = *( &a + 3);
* generate code on type:
* list(POINTER,
* list(INT))
* expr:
* list(ASS,
* list(GVAR,0,a),
* list(RINDIRECT,
* list(ADD,
* list(ADDRESS,
* list(GVAR,0,a)),
* list(CONST,12))))
movl $a,%eax
movl $12,%edx
movl (%edx,%eax),%edx
movl %edx,a
どうして、このようなコード出力になるのかは木構造が分かってしまえば、gexpr() をトレースするだけの問題である。この木構造は、最後の例では単純な構文木とは少々異なる。それは、indirect()や、rvalue() などが構文木を変換しているからである。
問題2
&a = (int *)3; というのは、Micro-C ではエラーになる。なぜ、エラーなのかを説明せよ。
答え
実際にコンパイラを走らせてみれば、
9:Lvalue required.
&a = (int *)3;
^
というエラー出力される。このエラーメッセージを確認しないで答えを出そうと言うのは、少し虫が良すぎる。コードの(int *)3の部分にはエラーはない。実際、
# a = (int *)3;
* generate code on type:
* list(POINTER,
* list(INT))
* expr:
* list(ASS,
* list(GVAR,0,a),
* list(CONST,3))
movl $3,%eax
movl %eax,a
という形にコンパイルされる。問題は明らかに&aの部分にある。しかし、前の授業でも説明したように、構文的なエラーはない。このエラーは代入文(assignemnt)に特有なエラーである。実際、Lvalue required というエラーは、
257 (n==LVERR) ? "Lvalue required" :であり、LVERR は、expr13の&の部分と、
1363 lcheck(e)
1364 int e;
1365 { if(!scalar(type)||car(e)!=GVAR&&car(e)!=LVAR&&car(e)!=INDIRECT)
1366 error(LVERR);
1367 }
に出てくる。expr13()ではなくlcheck()でエラーになっているのはトレースしてみればすぐにわかる。この場合は、
994 expr1()
995 {int e1,e2,t,op;
996 e1=expr2();
997 switch (sym)
998 {case ASS:
999 lcheck(e1);
1000 t=type;
ここのlcheck()でエラーになるわけである。実際、lcheck では、左辺値は、整数(scalar)か、大域変数(GVAR)か、局所変数(LVAR)か、間接参照であるとしている。&a は、そのどれでもないのでエラーとなる。(ANSI-C では、この他にも、いくつか左辺値を許している。どのようなものがあるだろうか?)
手続き呼び出しと、変数の配置
コード生成で問題になるのは、手続き呼び出しである。これは局所変数(local variable)の配置とも密接に結び付いている。手続きは、引数を持つのが普通であり、これが呼び出し側(caller)と呼び出された側(callee)を結び付ける。Cは手続きは値渡しと呼ばれ、単に値をコピーして送るだけで良い。Pascal などは参照渡しと呼ばれ、アドレスを送る必要がある。参照渡しならば、引数をcallee側で変更することができるので、複数の値を返したい時になどには便利だ。しかし、Cでもアドレスを直接送れば同じことができる。この方が実装的には美しい。が、C++ では参照渡しを復活させてしまったようだ... 参照渡しには複雑な問題が付きまとい、理論的にもかなりうっとうしい。しかし、プログラムの記述は簡潔になる。見掛けを取るか、使いやすさを取るか、そういう問題かも知れない。
局所変数や引数は、手続きが終ればなくなる変数である。これらはスタック上にとられる。スタックは、通常、CPUに特別なサポートがあり、特別なregisterを使うことになっている。これでは不便なことも多いので、それをFrame Pointer というのにコピーして使うことが多い。Frame Pointerは、単なるindex registerを使うのが普通だが、どのregisterかは固定されているのが普通である。
6809の場合は、S がsystem stackで、Uがuser stackであり、UがFrame Pointer として使われている。例えば、
*
* int func_int();
* int *func_ptr();
*
* main() {
* int i,j,k;
* int *p;
*
* i = func_int(i,j,k);
main
PSHS U
LEAU ,S
LEAS -8,S
* generate code on type:
* list(INT)
* expr:
* list(ASS,
* list(LVAR,-2),
* list(FUNCTION,
* list(FNAME,func_int),
*))
LDD -6,U
PSHS D
LDD -4,U
PSHS D
LDD -2,U
PSHS D
LBSR func_int
LEAS 6,S
STD -2,U
* p = func_ptr(&i,*p);
* generate code on type:
* list(POINTER,
* list(INT))
* expr:
* list(ASS,
* list(LVAR,-8),
* list(FUNCTION,
* list(FNAME,func_ptr),
*))
LDD [-8,U]
PSHS D
LEAX -2,U
PSHS X
LBSR func_ptr
LEAS 4,S
STD -8,U
* }
LEAS ,U
PULS U,PC
_1 RTS
_INITIALIZE EQU _1
_GLOBALS EQU 0
END
というような感じになる。Intel 386では、
.file "tmp3.c"
.text
# int *a;
# main(ac,av)
# int ac;
.align 2
.globl main
main:
.type main,@function
pushl %ebx
pushl %ecx
pushl %edx
pushl %ebp
movl %esp,%ebp
# char *av[];
# {
# int i,j,k;
# *a = atoi(av[0]);
subl $12,%esp
* generate code on type:
* list(INT)
* expr:
* list(ASS,
* list(INDIRECT,
* list(RGVAR,0,a)),
* list(FUNCTION,
* list(FNAME,atoi)))
movl 24(%ebp),%ecx
movl 0(%ecx),%eax
pushl %eax
call atoi
addl $4,%esp
movl a,%ecx
movl %eax,(%ecx)
# i = 3;
* generate code on type:
* list(INT)
* expr:
* list(ASS,
* list(LVAR,-4),
* list(CONST,3))
movl $3,%eax
movl %eax,-4(%ebp)
# }
_2:
leave
popl %edx
popl %ecx
popl %ebx
ret
_3:
.size main,_3-main
.comm a,4
問題 1
main() から、atoi() を呼び出す場合のi386での関数呼び出しの時のスタックの動きを、以下の6809の図にならって図示せよ。
Micro-C では、手続き名の型はFNAMEであり、式を表す中間木の型はFUNCTION である。実際のコード生成はfunction()で行われる。(問題2 では、手続きの構文解析はどこで行われているか?)
引数はスタックにつまれ、callee側ではFrame pointerに対する負のオフセットを使ってアクセスすることになる。この引数はcallerに戻る時にはなくなってしまっているので、扱うことはできない。
宿題
今日は宿題なしとします。