Compiler Construction Lecture 1/22

先週の復習

先週は、

Micro-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では、

.text
        .align 2,0x90
.globl _main
_main:
        pushl %ebp
        movl %esp,%ebp
        subl $4,%esp
        pushl %ebx
        pushl %edx
        pushl %eax
        movl -4(%ebp),%ecx
        pushl %ecx
        call _func_int
        movl %eax,-4(%ebp)
        movl (%ebx),%ebx
        pushl %ebx
        leal -4(%ebp),%eax
        pushl %eax
        call _func_ptr
        movl -8(%ebp),%ebx
        movl %ebp,%esp
        popl %ebp
        ret

問題 1

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

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

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

SPARCでは、変わった呼び出し方をしている。SPARCには overraped register window というのがあり、それぞれ、%i,%l,%o というように区別されている。それぞれ8本ずつある。call すると、caller の %o が、callee の%i となる。これを引数渡しに使う。(したがって8個以上の引数はregister渡しにできない。実際にはframe pointerやstack pointerがあるので、もっと少ない) また、浮動小数点には、regisger windowはない。 calleeからcallerに戻る時には、再び%iが%oとなる。これによって値を返すことができる。この切替えは、save/restore という命令によっておこなわれる。

この方法の良いところは、stackにいちいち値をcopyしなくても済むところである。しかし、register windowは無限にあるわけではないので、いつかはいっぱいになってしまう。その時にはsub routineを呼び出して、register windowの中身をスタックにcopyする。copyした後、戻る時には、また、スタックからregister windowにcopyする。実際のアプリケーションでは、この register window overflowが頻繁に起きるので、残念ながら、この方法が成功しているとはいえなかったようである。

実際には以下のような呼び出しを用いる。

        mov 4,%g3
        call _print,0
        mov %g3,%o0        callより、こちらが先に実行される
L1:
        ret
        restore            register window をもとにもどす
        .align 8
        .global _print
        .proc   04
_print:
        !#PROLOGUE# 0
        save %sp,-104,%sp        register window の切替え
        !#PROLOGUE# 1
        st %i0,[%fp+68]          %i0にcallerの%o0が入っている
        sethi %hi(LC0),%o1
        or %o1,%lo(LC0),%o0
        ld [%fp+68],%o1
        ld [%fp+68],%o2
        call _printf,0           この呼び出しはregister windowを使わない
        nop
L2:
        ret     
        restore                  ret より先にこちらが実行される

宿題 1

上の例にならって、PowerPC (AIX)上での関数の呼び出し方を示せ。

コードの例とアセンブラを示す。( gcc -O -S を使う )
stackやレジスタの動きを図で表す。

来週までに、実行結果と、変更した主要な部分をメールにして、 Compiler Construction Lecture 1/22 のSubjectを付けて kono@ie.u-ryukyu.ac.jp までメールすること。