Compiler Construction Lecture 1/18

先週の復習

先週は、

Micro-Cにおけるリスト構造
右辺値と左辺値

について勉強したのであった。

Micro-C のcode生成部分の構造

mc-code.html Micro-C のコード生成部の構成

先週の問題の解答

以下のCのstatementに対応するMicro-Cの中間木と生成される6809のコードについて考察せよ。ただし、以下の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 が出力される。

* int *a;
a	EQU	0
* main()
* {
* 
* *a = 1;
main
	PSHS	U
	LEAU	,S
* generate code on type:
* list(INT)
* expr:
*  list(ASS,
*  list(INDIRECT,
*   list(RGVAR,0)),
*  list(CONST,1))
	LDD	#1
	STD	[0,Y]
* a = &a[3];
* generate code on type:
*  list(POINTER,
* list(INT))
* expr:
*  list(ASS,
*  list(GVAR,0),
*  list(ADD,
*   list(RGVAR,0),
*   list(CONST,6)))
	LDD	0,Y
	ADDD	#6
	STD	0,Y
* *a = *(a + a[3] + 2);
* generate code on type:
* list(INT)
* expr:
*  list(ASS,
*  list(INDIRECT,
*   list(RGVAR,0)),
*  list(RINDIRECT,
*   list(ADD,
*    list(ADD,
*     list(MUL,
*      list(RINDIRECT,
*       list(ADD,
*        list(RGVAR,0),
*        list(CONST,6))),
*      list(CONST,2)),
*     list(RGVAR,0)),
*    list(CONST,4))))
	LDX	0,Y
	LDD	6,X
	ASLB
	ROLA
	ADDD	0,Y
	PSHS	D
	LDD	#4
	PULS	X
	LDD	D,X
	STD	[0,Y]
* a = *( &a  + 3);
* generate code on type:
*  list(POINTER,
* list(INT))
* expr:
*  list(ASS,
*  list(GVAR,0),
*  list(RGVAR,6))
	LDD	6,Y
	STD	0,Y

どうして、このようなコード出力になるのかは木構造が分かってしまえば、 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),
*  list(CONST,3))
        LDD     #3
        STD     0,Y

という形にコンパイルされる。問題は明らかに&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では、

        .align 2
.globl _main
_main:
        pushl %ebp
        movl %esp,%ebp
        subl $16,%esp
        call ___main
        movl -12(%ebp),%eax
        pushl %eax
        movl -8(%ebp),%eax
        pushl %eax
        movl -4(%ebp),%eax
        pushl %eax
        call _func_int
        addl $12,%esp
        movl %eax,%eax
        movl %eax,-4(%ebp)
        movl -16(%ebp),%eax
        movl (%eax),%edx
        pushl %edx
        leal -4(%ebp),%eax
        pushl %eax
        call _func_ptr
        addl $8,%esp
        movl %eax,%eax
        movl %eax,-16(%ebp)
L1:
        leave
        ret

問題 1

Intelでの関数呼び出しいの時のスタックの動きを、以下の図にならって図示せよ。

Micro-C では、手続き名の型はFNAMEであり、式を表す中間木の型はFUNCTION である。実際のコード生成はfunction()で行われる。(問題2 では、手続きの構文解析はどこで行われているか?)

引数はスタックにつまれ、callee側ではUに対する負のオフセットを使ってアクセスすることになる。この引数はcallerに戻る時にはなくなってしまっているので、扱うことはできない。

宿題

今日は宿題なしとします。