Compiler Construction Lecture No. 10

手続き呼び出しと、変数の配置

コード生成で問題になるのは、手続き呼び出しである。これは局所変数(local variable)の配置とも密接に結び付いている。手続きは、引数を持つのが普通であり、これが呼び出し側(caller)と呼び出された側(callee)を結び付ける。

Cは手続きは値渡しと呼ばれ、単に値をコピーして送るだけで良い。Pascal などは参照渡しと呼ばれ、アドレスを送る必要がある。参照渡しならば、引数をcallee側で変更することができるので、複数の値を返したい時になどには便利だ。しかし、Cでもアドレスを直接送れば同じことができる。この方が実装的には美しい。が、C++ では参照渡しを復活させてしまったようだ... 参照渡しには複雑な問題が付きまとい、理論的にもかなりうっとうしい。しかし、プログラムの記述は簡潔になる。見掛けを取るか、使いやすさを取るか、そういう問題かも知れない。

局所変数や引数は、手続きが終ればなくなる変数である。これらはスタック上にとられる。スタックは、通常、CPUに特別なサポートがあり、特別なregisterを使うことになっている。これでは不便なことも多いので、それをFrame Pointer というのにコピーして使うことが多い。Frame Pointerは、単なるindex registerを使うのが普通だが、どのregisterかは固定されているのが普通である。

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

問題 10.1

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

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

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

Register WindowとDelayed Slot

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 より先にこちらが実行される

call の後にある、,0 と、nop は、Delayed Slot と呼ばれるものである。昔のSparc は、jump や、call の際に、一つだけそのアドレスを先読みすることにより、パイプラインの乱れを吸収していた。ここにコンパイラがnopではなく、実際の命令を置くことにより、パイプラインを乱すことなく計算を続けることができる。

しかし、今のCPU技術では、命令の先読みは数命令に渡っており、1つのDelayed Slotではパイプラインの吸収しきれない。代わって、分岐予測が重要となっている。例えば、call文などでは、call 先が呼ばれることがわかっているので、先読みは、そちらを行えば良い。ここでもSPARCのRISCの技術は残念ながら失敗している。

また、PowerPCなどでは、分岐を判断するフラグを分岐命令よりも前に確定させることにより的確な先読みを可能にしている。フラグの確定を先に持って行くのは、コンパイラの責任である。