ここでは、組込み向けマシンのTMD(マシン記述)のいくつかとx86の64ビットモードの実装について説明する。
実装されたtmdファイルはsrc/coins/backend/genディレクトリに入っている。
ARMのマシン記述は組み込み向けに強化したバックエンドの新機能を使用す ることで TMD の記述量が減少することを検証するために実装したものである。
実装したARMのマシン記述ファイルは、arm.tmdという名前でCOINSのソースディ レクトリsrc/coins/backend/genの中に置いてある。
-coins:target=arm
組み込み用プロセッサによくある近接アドレスによる定数(リテラル)のロー ドや到達範囲の限られた分岐命令を簡単に利用できるように、バックエンドに リテラルとブランチの変換を追加した。このフィルタの動作を検証するために ARMよりも制限の強いThumb命令セットのマシン記述を実装した。
実装したTHUMBのマシン記述ファイルは、thumb.tmdという名前でCOINSのソー スディレクトリsrc/coins/backend/genの中に置いてある。
ターゲットは free standing 環境(組み込み環境で、OS を想定しない環 境)を想定している。したがってライブラリは一般に使用者が用意する必要が ある。 具体的な仕様は以下のとおりである。
THUMBのマシン記述は OS の存在しない組み込み環境を想定しているため、 すべての場合に通用する一般的な使用方法というものは記述できない。
また THUMB を完全にサポートする OS は一般的ではないため、ここでは一 例として入手の容易な ARM 環境 (具体的には Armadillo9 のような ARM Linux 環境や Linux 上の ARM ソフトウェアエミュレータ) 上で THUMB コー ドを実行するための方法を記述する。
なおコンパイル時に以下のようにオプションを指定することで THUMB マシン記述によるコード生成が行われる。
-coins:target=thumb
-marm -mthumb-interwork
THUMBには整数除算命令が存在しないため gcc のランタイムライブラリ (__divsi3, __modsi3等) を利用する。
ただし、これらはARMのサブルーチンであり、THUMBモードからbx命令で直 接呼び出した場合には正しくTHUMBモードに復帰することができない。そこで 以下のラッパを被せて使用する。
.text .align 2 .global wrapper__divsi3 wrapper__divsi3: str %lr,[%sp,#-4]! bl __divsi3 ldr %lr,[%sp],#4 bx lr .global wrapper__modsi3 wrapper__modsi3: str %lr,[%sp,#-4]! bl __modsi3 ldr %lr,[%sp],#4 bx lr .global wrapper__udivsi3 wrapper__udivsi3: str %lr,[%sp,#-4]! bl __udivsi3 ldr %lr,[%sp],#4 bx lr .global wrapper__umodsi3 wrapper__umodsi3: str %lr,[%sp,#-4]! bl __umodsi3 ldr %lr,[%sp],#4 bx lrTHUMBのマシン記述の生成コードはblx命令でこれらのラッパを呼び出す。
あるいは__divsi3などをCで記述し、リンクすることでもこの問題を回避す ることができる。ただし、もともとのルーチンと名前を同じにしないよう、 thumb__divsi3のようにthumbを前置する必要がある。
以下に例を示す。このファイルをTHUMBのマシン記述を使用してコンパイル することでTHUMBモードで使用可能なランタイムライブラリが得られる。
/* div.c - runtime routine for thumb */ static unsigned int main__udivsi3(unsigned int x, unsigned int y, unsigned int *p) /* x / y */ { unsigned int z = 0; int i; for (i = 32; i != 0; i--) { z <<= 1; z |= (x >> 31); x <<= 1; if (z >= y) { z -= y; x++; } } *p = z; return x; } unsigned int thumb__udivsi3(unsigned int x, unsigned int y) /* x / y */ { unsigned int z; return main__udivsi3(x, y, &z); } unsigned int thumb__umodsi3(unsigned int x, unsigned int y) /* x % y */ { unsigned int z; main__udivsi3(x, y, &z); return z; } int thumb__divsi3(int x, int y) { int xs = x ^ y; x = thumb__udivsi3(x >= 0 ? x : -x, y >= 0 ? y : -y); if (xs < 0) { x = -x; } return x; } int thumb__modsi3(int x, int y) { int ys = x < 0; x = thumb__umodsi3(x >= 0 ? x : -x, y >= 0 ? y : -y); if (ys) { x = -x; } return x; }
MicroBlazeのマシン記述はマルチコアの機種に対するTMDを実装したもので ある。命令パターン指定とコスト指定の多様性 (実行速度とコードサイズのコ スト) に対応する拡張機能を使用した記述を行っている。
実装したMicroBlazeのマシン記述ファイルは、mb.tmdという名前でCOINSのソースディレクトリsrc/coins/backend/genの中に置いてある。
MicroBlaze はソフトコア CPU のため、合成時のオプション設定で一部の 機能を制限することができる。
デフォルトでは MicroBlaze の全機能を有効にすることを想定したコード 生成を行う。すなわち以下の機能を使用するコードを生成する。
-coins:x-mb=fooで使用しない命令を指定できる。このfooでは以下の指定ができる。
-coins:optspaceかを指定することによって違う命令が生成される。
1ビットシフトについては、ALU による左シフト、1 ビットシフトユニット による右シフトが最速・最短 (1サイクル, 4バイト) であるので、add 命令あ るいは1ビット右シフトの命令が生成される。(MicroBlaze は1ビット左シフト 命令を持たない。)
2以上の定数nによるnビットのシフトは以下のようになる。MicroBlazeのマシン記述は OS の存在しない組み込み環境を想定している ため、すべての場合に通用する一般的な使用方法というものは記述できない。
そのため、ここでは Xilinx社のEDK(Embedded Development Kit)に含ま れている mb-gdb のソフトウェアシミュレータ上で COINS のテストプログラ ム集を実行するための手順を簡単に記述する。
なおコンパイル時に以下のようにオプションを指定することでMicroBlazeマシン記述によるコード生成が行われる。
-coins:target=mb
#!/bin/sh # compile *one* C file and link it. CP=./classes TARGET=mb LIB=/work/coins/src/lib.c MBROOT=/var/tmp/mb/release/linux/microblaze/bin CPP="$MBROOT/mb-gcc -E" AS=$MBROOT/mb-as LD=$MBROOT/mb-gcc LFLAGS=-Zxl-no-libxil TMPOUT=/tmp/`basename $1 .c`.s OUT=`basename $1 .c`.mb-exe rm -f $TMPOUT $OUT java -cp $CP coins.driver.Driver -coins:target=mb,preprocessor="$CPP",x-mb=no-fpu \ $2 -S -o $TMPOUT $1 $LD -msoft-float -fshort-double $LFLAGS \ -Xlinker -defsym -Xlinker _STACK_SIZE=0x10000 \ -Xlinker -Map -Xlinker a.map \ $TMPOUT $LIB -o $OUT -lm_m_bs_sfps -lc_m_bs_sfps
実機で動かす場合には最後の部分が例えば以下のようになる。
java -cp $CP coins.driver.Driver -coins:target=mb,preprocessor="$CPP" \ $2 -S -o $TMPOUT $1 $LD -mhard-float -fshort-double $LFLAGS \ -Xlinker -defsym -Xlinker _TEXT_START_ADDR=0x24000000 \ -Xlinker -defsym -Xlinker _STACK_SIZE=0x10000 \ -Xlinker -Map -Xlinker a.map \ $TMPOUT $LIB -o $OUT -lm_m_bs_hfps -lc_m_bs_hfps
#!/bin/sh MBROOT=/var/tmp/mb/release/linux/microblaze/bin MBGDB=$MBROOT/mb-gdb ANS=_tmp.ans rm -f $ANS $MBGDB -nw $1 <<EOF | tee log.$1 target sim load b _program_clean set print elements 0 run bt x /s &print_buffer__ quit EOF echo echo -- result grep print_buffer_ log.$1 | tr -d \" | sed -e 's/.*__>: //' | \ sed -e 's/\\n/\n/g' | sed -e 's/\\t/\t/g' > $ANS
実機で動かす場合には中間部分が例えば以下のようになる。
$MBGDB -nw $1 <<EOF | tee log.$1 target remote 192.168.1.1:1234 load b _program_clean set print elements 0 c bt x /s &print_buffer__ quit EOF
#!/bin/sh OUT=`basename $1 .c`.mb-exe ANS=`dirname $1`/`basename $1 .c`.ans BIN=/work/coins/bin CMD=`dirname $1`/`basename $1 .c`.cmd # skip test which read *.cmd if [ -f $CMD ] ; then echo ::: excluded $1 exit 0 fi # skip long long if grep "long long" $1 ; then echo ::: excluded $1 exit 0 fi # skip long double if grep "long double" $1 ; then echo ::: excluded $1 exit 0 fi $BIN/mbccc.sh $1 $BIN/mbgdb.sh $OUT if grep 'N/A' _tmp.ans; then echo ::: excluded $1 else if diff -Bc $ANS _tmp.ans ; then echo ::: passed $1 else echo ::: failed $1 fi fi
mb-gdb のシミュレータ上には OS が存在しないため入出力を実行すること ができない。したがって COINS のテストプログラムを実行するには少し工夫 が必要である。以下のファイルをテストプログラムと一緒にリンクすることで COINS のテストプログラムの多くのものが実行可能になる。
#include <stdarg.h> #ifdef __i386 int flag; int _program_clean(); #endif int __errno; /* dummy allocator */ char space[1000]; char *top = space; void *calloc(int n, int size) { char *tmp = top; if (sizeof(space) - (top - space) < n * size) { printf("failed: calloc\n"); exit(11); } top += n * size; return tmp; } void *malloc(int n) { return calloc(n, 1); } /* output buffer */ char print_buffer__[30000]; /* tpprimed requires 24754bytes */ int print_i__ = 0; int printf(const char *fmt, ...) { va_list ap; va_start(ap, fmt); print_i__ += vsprintf(&print_buffer__[print_i__], fmt, ap); // check buffer overflow. va_end(ap); #ifdef __i386 if (!flag) { atexit(_program_clean); flag = 1; } #endif } int fprintf(void *fp, const char *fmt, ...) { va_list ap; va_start(ap, fmt); print_i__ += vsprintf(&print_buffer__[print_i__], fmt, ap); // check buffer overflow. va_end(ap); #ifdef __i386 if (!flag) { atexit(_program_clean); flag = 1; } #endif } int putchar(int c) { print_buffer__[print_i__++] = c; #ifdef __i386 if (!flag) { atexit(_program_clean); flag = 1; } #endif return c; } int puts(char *s) { char *tmp = s; while (s && *tmp) { print_buffer__[print_i__++] = *tmp++; } print_buffer__[print_i__++] = '\n'; #ifdef __i386 if (!flag) { atexit(_program_clean); flag = 1; } #endif return s; } void __assert(const char *f, int n, const char *s) { printf("%s: %d: %s\n", f, n, s); } /* dummy handler */ int _program_clean() {} int _program_init() {} int _hw_exception_handler() {} int _exception_handler() {} int _interrupt_handler() {} /* not supported function, exit */ #define die(name) \ int name() { printf("N/A: " # name "()\n"); exit(1); } die(read); die(write); die(lseek); die(getchar); die(getc); die(__srget); die(scanf);
浮動小数点レジスタとしては、従来からのx87 FPUのものもあるが、それは使わないことにする。 GCCのx86_64版でもそれは使っていない。これでスタック型レジスタなどの使いにくさから ようやく解放されることになる。その他にSIMD用のレジスタや命令が使えるのであるが、 それはここでは扱わない。
ABI(Application Binary Interface)は
に従う。レジスタが大幅に増えたことに伴って、 ABIがx86のものとは大きく違っている。 特に、関数呼び出しの規約が、多くのレジスタを利用するように大幅に変更されている。
64ビット汎用レジスタの右端の(least significant)8, 16, 32ビットは、それぞれ その幅のレジスタ(64ビットレジスタのサブレジスタ)として使うことが出来る。 右端の8ビットレジスタだけでなく、以前からのahやbhレジスタも使えるのであるが、 64ビットモードでは使い方に制限が付けられており、それを使わなくてもレジスタは 十分にあると思われるので、ここでは使わないことにする。
32ビットレジスタがdestination registerとなった場合は、その結果は64ビットにゼロ拡張 される。したがって、値が正であることが保証できる場合には、32ビットレジスタにセット するだけで64ビットレジスタにセットしたことになる。 しかし、8ビット, 16ビットレジスタがdestination registerとなった場合は、その 上位ビットは変化しない。
レジスタとしては、その他に、rsp, rbp, ripがある。rspはスタックポインタとして使われ、 rbpはフレームポインタとして使われるものであるが、rbpは必ずしもそのためでなく使って もよいとされている。ripは命令ポインタであり、rip相対アドレスが使える。
マシン記述は主としてLIRからコードを生成するために記述するのであり、HIRはほとんど マシンに依存するところはないのであるが、HIRで扱うデータ型がマシンでは何バイトで 表現されるかということだけは知る必要がある。そのデフォールトの値はcoins/MachineParam.java に記述されており、
char: 1, float: 4, pointer: 4 short: 2, double: 8, address: 4 int: 4, long double: 8, offset: 4 long: 4, long long: 8
などとなっている。ここで、offsetの値は、配列や構造体の要素の番地が、 「その配列や構造体の先頭番地+オフセット」 として表されるときのオフセットの表現に使われるバイト数である。
このデフォールト値と違うマシンの場合は、その違う定義をしたものを使う必要 がある。coins/MachineParamX86_64.javaでは、上記のうち、long, pointer, address, offset をそれぞれ8に設定している。したがって、先頭番地もオフセットも 8バイトで表現される。
ところで、通常のプログラムでは、配列の添字の値をint型で表現することが多い。 int型は4バイトである。したがって、配列要素のアドレス計算では、int型から offset型への変換が必要になる。そのためにLIRの命令列には
(CONVSX I64 (REG I32 temp))
の形の命令が挿入される。このtempの値が正であることが保証されれば、前節で述べたことに よって、CONVSXのためのマシン命令を生成する必要はないが、 この形の命令はオフセット計算以外の場所でも現われ得るし、一般にはそれは保証できない。 また、COINSには、SSA最適化の中でCONVSX命令のことは考慮されていないという問題もある。 これらのことから、配列を扱うプログラムに対しては必ずしも効率のよいコードが生成されない 可能性がある。
そこで、offsetの値を4とすることを考えてみる。この場合、配列要素のアドレス計算の ためのLIR命令は次のような形になる。(ADD I64 (REG I64 "base-reg")(REG I32 "offset-reg32"))もし、レジスタ"offset-reg32"の値が正であることが保証されるならば、これは
(ADD I64 (REG I64 "base-reg")(REG I64 "offset-reg64"))と同じであると見なして、コードを生成することができ、効率のよいコードが得られる。 ここで、"offset-reg64"は"offset-reg32"をサブレジスタとして含む64ビットレジスタの名前である。
x86_64.tmdでは、offsetの値が4でも8でも対応できるように書かれている。 もし、配列の添字の値が常に正であると保証できるのであれば、offsetの値を4としてもよい。 試みに、行列の掛算のプログラムの実行時間(単位は秒)を、最適化のレベルをいろいろ変えて、 比べてみると次のようになる。
no-opt O1 O2 O3 O4 offset=8 6.45 6.06 4.14 4.14 3.80 offset=4 4.81 4.44 3.24 3.23 3.05
このプログラムは、float型の500×500の行列の掛算を20回実行するものであり、 実行マシンはインテルXeon 3GHzである。offsetの値を4とすると大分速くなることが分かる。
なお、このようなプログラムを速くするもう一つの方法は、offsetの値は8のままで、 プログラムを書き換えて、 配列の添字用の変数の型をlongとすることである。今の例では実行時間は次のようになる。offset=8 no-opt O1 O2 O3 O4 int 6.45 6.06 4.14 4.14 3.80 long 5.71 5.44 3.07 3.07 3.08
(def *real-reg-symtab* (SYMTAB ;; general registers (foreach @g (rax rcx rdx rsi rdi r8 r9 rbx r10 r11 r12 r13 r14 r15) ("%@g" REG I64 8 0)) (foreach @g (eax ecx edx esi edi r8d r9d ebx r10d r11d r12d r13d r14d r15d) ("%@g" REG I32 4 0)) .....
ここでレジスタの名前を並べる順序が意味を持つ。レジスタ割付けの際に、 この順で割付けられていくからである。
上記のリストはcaller-saveレジスタを先に並べ、callee-saveレジスタを後に並べてある。 もし、ある関数のコンパイルにおいて、callee-saveレジスタに割当ててしまうと その関数のprologue/epilogueにそのレジスタのsave/restoreの命令を置く必要が 生ずるからである。
一方、caller-saveレジスタに割付けた場合は、その必要はないが、もし そのレジスタの生存区間内に他の関数呼び出し(LIRではCALL式があると) があると、その呼び出しの前後でsave/restoreが必要になる。 しかし、レジスタ割付けでは、caller-saveレジスタとCALL式は干渉する ことが分かってそのような割付けは一般には避けられるので、その心配は あまりない。 なお、そのために、CALL式のEarlyRewritingで、CALL式のCLOBBER属性と してcaller-save レジスタのリストを付加するようにしている。
これらのリストは、tmdに以下のように記述してある。
(def *reg-call-clobbers* ;; caller save registers ((REG I64 "%rax")(REG I64 "%rcx")(REG I64 "%rdx") (REG I64 "%rsi")(REG I64 "%rdi")(REG I64 "%r8") (REG I64 "%r9")(REG I64 "%r10")(REG I64 "%r11") (foreach @n (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) (REG F64 "%xmm@n")) )) (def *reg-callee-saves* ;; callee save registers ((REG I64 "%rbx")(REG I64 "%rbp")(REG I64 "%r12") (REG I64 "%r13")(REG I64 "%r14")(REG I64 "%r15")))
レジスタの使い方の制限を表現するためにレジスタ集合の定義を使っている。 割算に使われるレジスタの例を挙げる。
(defrule regq (DIVS I64 regq regq) (eqreg $1 $0) (regset ($0 *reg-rax-I64*) ($2 *reg-not-rdx-I64*)) (code (cqto) ; propagete raxs sign bit through rdx. (idivq $2)) (clobber (REG I64 "%rdx")) (cost 22))
割算命令"idivq r"は、rdxとraxレジスタを繋いだ128ビットを レジスタrの値で割算し、商をrax、余りをrdxに求める命令である。 上記のルールでは、raxの値をrdxに符号拡張したものに"idivq $2" を適用するコードを生成するので、$1と$0はraxでなければならないし、 $2はrdxであってはならない。そのために、 *reg-rax-I64*はraxレジスタだけからなる集合、*reg-not-rdx-I64* はrdxレジスタ以外のレジスタからなる集合、として定義してある。
64ビットモードでの関数呼び出しの規約の概要は次のようになっている。 引数は、一般に整数型のものと浮動小数点型のものが入り交じっているが、 ここでは、その中で、たとえば整数型のものだけについて1番目の引数、2番目の引数、 などという言い方をする。整数型の1番目の引数と2番目の引数の間には 浮動小数点型の引数がいくつかあるかも知れない。
struct型やunion型の引数に関してはさらに複雑な規約がある。ここには、その概略だけを記述する。 詳細はABIのドキュメントを参照して欲しい。
以下にいくつかの例をあげる。
struct { int a, b; // 汎用レジスタ渡し double c; // %xmmレジスタ渡し } struct { // スタック渡し int a; double c; int b; } struct { int a; float c; // 汎用レジスタ渡し int b; // 汎用レジスタ渡し } struct { float a, b; // %xmmレジスタ渡し float c; // %xmmレジスタ渡し }
関数の戻り値がstruct型やunion型である場合も、それが1つまたは2つの8バイトに納まればレジスタ に返される。その場合のレジスタは、次のものが順に使われる。
1つまたは2つの8バイトに納まらない場合は呼び出しの際に「隠れた第1引数」として、返す値 を入れるアドレスを%rdiに渡す。
最初は単純なケースだけ処理できるようにして、順次機能を充実させていく、という方針に したがって、最初は引数がすべてレジスタ渡しになり、常にフレームポインタ%rbpを使うとする。
である。このうち、最初の3項目の命令列は必要なすべての情報が得られる最後のアセンブリコード生成 のときに生成すればよい。それにはx86.tmdの
%defemit(prologue =f) { ... }
の真似をしている。ただし、この関数から別の関数が呼び出されることを考えて、 3項目の命令列を実行したときには%rspの値が16の倍数になるようにしている。
最初の項目1で生成するコードはpushq %rbp movq %rsp,%rbp
である。%rspの値が16の倍数の状態でこの関数が呼ばれれば、戻り番地がpushされていること と上記のpush命令により、その(%rspの値が16の倍数であるという)状態は保たれている。 3項目の命令列を実行した後もそれを保つ ために、確保したフレーム領域のバイト数、スタックに 退避したレジスタの数が偶数(バイト数で16の倍数)か奇数か、などを考慮 して、必要ならフレーム領域として確保する大きさを調整する必要がある。
最後の項目は、命令選択のフェーズより前にLIR式として作成しなければならない。 これも、x86.tmdの
LirNode rewritePrologue(LirNode node, BiList post) {...}
の真似をしている。これはLateRewritingで実行されるものである。 ただし、x86.tmdのものがスタックから仮引数への代入であるのに対して レジスタからの代入になる。何番目の引数であるか、型はI8, I16, I32, I64のどれであるか によってレジスタの名前が異なるから、プログラムしやすいように、 それらのレジスタ名を2次元配列として並べてある。
%defemit(epilogue =f rettype) { ... }の真似をしている。ただし、そこには
X86Attr attr = (X86Attr)getFunctionAttr(func); ... if (attr.allocaCalled && n != 0) ...
という部分がある。このX86Attrは FunctionAttrのサブクラス としてx86.tmdの中に書かれているクラスである。この関数の中でalloca関数が呼ばれて いたとしたら、EarlyRewritingフェーズで attr.allocaCalledの値をtrueにセットしている。
allocaは特殊な関数で、 それが呼ばれると、%rspの値が変更されてしまうから(あるいは、%rspの値を 変更するアセンブリ命令のようなものであるから)、 %rspの値をもとに戻してから callee-saveレジスタをスタックから回復しなければならない。それには、PROLOGUEで %rspの値を進めたのと同じことをもう一度すればよい。PROLOGUEの先頭での%rspの値 は%rbpに入っているから、%rbpの値を使って%rspの値をもとに戻すことができる。
最後の項目で生成するコードはleave retである。
LirNode rewriteCall(LirNode node, BiList pre, BiList post)
の真似をしているが、x86.tmdでは引数をスタックに積むのに対して x86_64.tmdではレジスタにセットしている。
たとえばfunc(int-exp1, int-exp2)という関数呼び出しがあって、funcの戻り値の型が整数であるときは、
(SET I32 (REG I32 "%edi") (int-exp1のLirNode)) (SET I32 (REG I32 "%esi") (int-exp2のLirNode)) (PARALLEL (CALL (STATIC I64 "func") () ((REG I32 "%eax"))) (USE (REG I64 "%rdi") (REG I64 "%rsi")) (CLOBBER (REG I64 "%rax") ...))
のように変換しなければならない。ここで、最初の行はint-exp1の値を %ediレジスタにセットする命令であるが、最後から2行目の (USE (REG I64 "%rdi") はそのレジスタがCALL式で使われる、すなわちその生存区間がCALL式まで続く、ことを示すものである。これがないと int-exp2が複雑な式であったときに、(レジスタ割付けのフェーズで)その式の計算に %rdiレジスタが使われてしまう可能性がある。
USEには、実際に引数をセットしたレジスタのリストを入れればよい。CLOBBERには、 前にも述べたようにcaller-saveレジスタを入れる。
実は、x86の64ビットモードでは、整数型の引数については、 上記のUSEを使っても解決しない問題がある。 特定のレジスタが特定の命令で使われ、その特定のレジスタが引数にも使われる場合が あるからである。そのためにUSEが、かえってレジスタ割付けの障害になる場合がある。
たとえば、%rdxレジスタは割算命令で特定のレジスタとして使われ、 関数呼び出しの3番目の引数の渡し場所としても使われる。したがって、もし 3番目の引数を%rdxレジスタに載せてから4番目の引数の計算をした場合に、 その計算の中に割算があると3番目の引数の値が壊されてしまう。それを避けるためには、 まずすべての引数について、その値を求めて一時的なレジスタに入れておいてから、 呼び出しの直前でそれらを引数用のレジスタに移すようにすればよい。 こうすると、レジスタ間の転送の命令が増えそうな気がするかも知れないが、 レジスタ割付けのフェーズではレジスタ間の転送の命令が出来るだけ出ないように 割付けるから、あまり気にする必要はない。
整数型の引数については、このようにすれば、上記のUSEを使う必要はない。
スタック渡しの引数はpush命令で渡せばいいと思うかも知れない。しかし、64ビットモードでは 64ビット、16ビットなどのデータをpushする命令はあるが、32ビットのデータをpushする命令は 使えない。また引数は8バイト間隔で積まなければならないという規約がある。そこで、push命令 は使わずに
mov 実引数,-8(%rsp) subq $8,%rsp
のような命令で、実引数を1つずつ積んでいくことが考えられる。しかし、これを毎回やるのも 効率が悪いし、呼ぶ直前には%rspの値を16の倍数にしなければならないという問題もある。
そこで、PROLOGUEであらかじめ%rspの値を適当に進めておいて、実引数を積むときにはmov 実引数,n(%rsp)
だけですむようにする(GCCでもそのようにしている)。nの値は、スタックに積まれる 順に0, 8, 16, ...と8きざみになる。スタックに最初に積まれるのは7番目の整数型引数か9番目の浮動小数点型引数であり、そのとき nの値は0である。
あらかじめ%rspの値を進めておく値は、その関数の中にある他の関数呼び出しの中で引数を スタックに積む個数が最大であるものによって決めればよい。ただし、alloca呼び出しがある 場合は問題である。その場合は、あらかじめ%rspの値をPROLOGUEで進めておくのでなく、 必要ならば、それぞれのCALLの直前に、そのCALLで必要となる分だけ%rspの値を進め、 CALLの直後でもとに戻しておけばよい。
関数呼び出しの中でスタックに積まなければならない引数がいくつあるかは、rewriteCall メソッドの中で調べることが出来るが、そこでは上記のnの値が必要になるから、 個数の変わりにnの値で調べることにする。各関数呼び出しについて、 rewriteCallメソッドでnの値の最大値(x86_64.tmdではstackOffsetの値)を求め、 その関数からのすべての関数呼び出しについてのその値の最大値(x86_64.tmdではmaxStackOffsetの値) を求め、rewriteEpilogueメソッドでそれをX86_64Attrオブジェクト(X86_64AttはFunctionAttrの サブクラス)のstackRequiredの値として登録し、それを%defemit(prologue =f)で取り出して、 必要なだけ%rspを進めるのに使っている。
PROLOGUEでスタック渡しの引数を仮引数に代入するときには、n(%rsp)に積まれたものは n+16(%rbp)から取り出せばよい。%rbpには、もとの%rspの値から、戻り番地と %rbpをpushしたために16だけ進んだものが入っているからである。
関数のプロローグ、エピローグのコードは一般に次の形になるprolog: pushq %rbp movq %rsp,%rbp subq frameSize,%rsp pushq命令列によるレジスタの退避 subq stackRequired,%rsp epilog: leaq frameSize+退避数*8(%rbp),%rsp popq命令列によるレジスタの回復 leave retただし、必要のない命令は省かれる。また%rspの値を16の倍数とするための調整が必要である。 エピローグの最初の命令は、%rspの値を、プロローグでpushq命令を実行した直後の値とする ものである。
pushq %rbp movq %rsp,%rbp
の2命令が入るが、その関数で%rbpが使われていない場合は、この命令は無駄である。 簡単な関数の場合はこの命令を削除する効果も大きい。
%rbpが使われないのは、その関数のフレームのサイズ(frameSize(func)として求められる)が0であり、 かつ、その関数がスタック渡しの引数を持たない場合である。さらに、 その関数の中でallocaが呼ばれている場合は、EPILOGUEで%rbpが使われる可能性がある から、その場合も除く必要がある。
その関数がスタック渡しの引数を持たないかどうかはrewritePrologueメソッドで 調べることが出来る。スタック渡しのために必要なバイト数(必要なければ0)を X86_64Attrオブジェクトに登録(名前はstackParams)しておいて、 %defemit(prologue =f)で使っている。
%rbpを使わない場合のプロローグ、エピローグのコードは次のようになる。prolog: 必要ならcallee-saveレジスタの退避(pushq命令による) 必要なら subq n,%rsp (CALLがある場合) epilog: 必要なら addq n,%rsp (CALLがある場合) 必要ならcallee-saveレジスタの回復(popq命令による) retsubqなどが必要なのは、CALLでスタックを必要とする場合だけではない。 この関数が呼ばれる直前には%rspの値が16の倍数であり、 呼ばれた直後には戻り番地が積まれてそれが崩れているから、 %rspの値が16の倍数になるようにsubqを使うのである。 退避するレジスタの個数が偶数(0も含む)で、CALLがあり、CALLでスタックを 必要としない場合は、n=8とする。
前節までのプロローグ、エピローグのコード生成をまとめて、より詳細に記述 すると以下のようになる。
次の値を使う。int frameSize: その関数のフレームの大きさ int stackParams: その関数の仮引数でスタック渡しのもののサイズ int numberOfCALLs: その関数の中のCALLの個数 int stackRequired: CALLで必要とするスタックサイズの最大値 boolean push: callee-saveレジスタの退避あり boolean pushOdd: callee-saveレジスタの退避の個数が奇数 boolean allocaCalled: その関数内にallocaの呼び出しがある
これらの値のうち、frameSize以外はLateRewritingのフェーズの rewritePrologue、rewriteEpilogue、rewriteCallなどで求めて FunctionAttrクラスのX86_64Attrオブジェクトに記録しておき、それを %defemit(prologue)や %defemit(epilogue) などで使う。
なお、allocaが呼ばれているかどうかは、EarlyRewritingでセットし、 それをrewritePrologue、rewriteEpilogue、rewriteCallなどで知ることが できる。(frameSize != 0) || (stackParams != 0) || allocaCalled の場合
(1-1) (stackRequired != 0) && push の場合
このときallocaCalled==falseである。生成される命令は次のようになる。prolog: pushq %rbp movq %rsp,%rbp subq fSize, %rsp ;; fSize == 0 なら不要 pushq callee-save registers ;; pushq命令の列 subq cSize, %rsp epilog: leaq -m(%rbp), %rsp ;; m = fSize + (pushq命令の数)*8 popq callee-save registers ;; popq命令の列 leave retここで、fSizeはframeSizeを切り上げて
fSize == 0 (mod 16) if !pushOdd == 8 (mod 16) if pushOddとしたもので、cSizeはstackRequiredを切り上げて
cSize == 0 (mod 16)としたものである。
(1-2) (stackRequired == 0) || !push の場合
生成される命令は次のようになる。prolog: pushq %rbp movq %rsp,%rbp subq fcSize, %rsp ;; fcSize == 0 なら不要 pushq callee-save registers ;; !pushのときは不要 epilog: leaq -m(%rbp), %rsp ;; !pushのときは不要 popq callee-save registers ;; !pushのときは不要 leave retここで、fcSizeは(frameSize+stackRequired)を切り上げて
fcSize == 0 (mod 16) if !pushOdd (!push の場合も含む) == 8 (mod 16) if pushOddとしたもので、mは(2-1)の場合と同様に
m = fcSize + (pushq命令の数)*8である。
(frameSize == 0) && (stackParams == 0) の場合
生成される命令は次のようになる。
prolog: pushq callee-save registers ;; !pushのときは不要 subq m,%rsp ;; m == 0 || numberOfCALLs == 0 なら不要 epilog: addq m,%rsp ;; m == 0 || numberOfCALLs == 0 なら不要 popq callee-save registers ;; !pushのときは不要 retここで、mはstackRequired(0の場合も含む)を切り上げて
m == 0 (mod 16) if pushOdd == 8 (mod 16) if !pushOdd (!push の場合も含む)としたもので、stackRequired == 0 の場合は、n=0 か n=8 である。
struct型やunion型の引数のコードを生成するためには、 その構成要素の型を知る必要がある。しかし、COINSのLIRでは そのような情報を得ることが出来ない。
COINSのLIRを設計する時点では x86_64のABIのようにstruct型やunion型の構成要素の型によって 引数としての渡し方を決めるようなABIは知られていなかった。 それまでのABIでは、引数として渡すときは、ひとかたまりのデータとして 渡していたので、LIRではひとかたまりのデータとしてのバイト数の 情報だけあれば十分であるとして、その情報しかシンボルテーブルに 持っていない。
そこで、x86_64.tmdでは、HIRのシンボルテーブルから情報を 取り出すことにした。LirNodeオブジェクトの型がAGGREGATE型である ときに、次のメソッドによってHIRでの型の情報を取り出している。
coins.sym.Type hirType(LirNode arg) { LirSymRef lval = (LirSymRef)arg.kid(0); Symbol symbol = func.localSymtab.get(lval.symbol.name); if (symbol == null) symbol = func.module.globalSymtab.get(lval.symbol.name); String aggrName = ((QuotedString)symbol.opt().elem2nd()).body.intern(); Sym symAggr = getSymRoot().sym.getOriginalSym(aggrName); coins.sym.Type aggrType = symAggr.getSymType(); return aggrType; } SymRoot symRoot = null; SymRoot getSymRoot() { if (symRoot != null) return symRoot; Thread th = Thread.currentThread(); IoRoot io = null; if (th instanceof CompileThread) io = ((CompileThread) th).getIoRoot(); symRoot = io.symRoot; return symRoot; }
int varargfunc(int x, float y, ...);のような形で、可変引数関数であることを宣言する。この関数の本体は、たとえば 次のような書き方をする。
#include <stdarg.h> int varargs_print(int length, double dbl, ...) { va_list args; /* va_list type */ int i; va_start(args, dbl); /* initialize var_args */ printf("varargs_print\n"); printf("1 : double %f\n", dbl); for (i = 2; i <= length; i++){ if (i%2 == 0) printf("%d : int %d\n", i, va_arg(args, int)); else /* get next int type argument */ printf("%d : double %f\n", i, va_arg(args, double)); } /* get next double type argument */ va_end(args); } int main(){ varargs_print(2, 1.1, 2); varargs_print(14, 1.1, 2, 3.3, 4, 5.5, 6, 7.7, 8, 9.9, 10, 11.0, 12, 13.0, 14); return(0); }
va_listが可変引数リストの型を表し、va_startで可変引数リストの初期設定を行い、 va_argで可変引数リストから次々に実引数を取り出すことになっている。 va_startの第2引数は固定部分の仮引数の最後のものを示し、va_argの第2引数は 取り出す実引数の型を示している。va_endは実引数の取り出しが終わった後で呼ぶものである。
AMD64のABIには、これらの関数の実装法が書いてある。それに忠実に従って 実装することも可能であるが、ここでは、GCCでどのようなコードが生成されるかを見て、 それと同じようなコードを生成する方法を実装している。
GCCで生成されるコードを見ると、可変引数関数のプロローグで、引数用の レジスタの内容がフレームの先頭の決まった場所に取り込まれている。 これは、レジスタ渡しの引数がそれらのレジスタに入っているかも知れないからである。 ただし、固定引数に使われているレジスタは、通常の関数の場合と同じように取り込まれる はずであるから、ここでは特定場所に取り込むことはしない。 また、実引数の数が多くなってスタック渡しになっている分については、スタックに積まれて いるはずであるから、それを使えばよい。それらは出現順に
16(%rbp), 24(%rbp), ...に積まれている。
ところで、浮動小数点レジスタからの取り込みにはmovapsという比較的時間がかかる 命令が使われるので、無駄な取り込みをしなくてすむようにするために、浮動小数点型の 実引数の個数を、隠れた引数として%alに渡すようになっている。しかし、その%alの値を 使って不必要な取り込みをしないようにするコードは複雑であるので、その実装はしていない。
レジスタ渡しの引数を取り込む決まった場所は以下の通りである。-16(%rbp) 第8float引数、float引数は16バイト間隔 -32(%rbp) 第7float引数 -48(%rbp) 第6float引数 -64(%rbp) 第5float引数 -80(%rbp) 第4float引数 -96(%rbp) 第3float引数 -112(%rbp) 第2float引数 -128(%rbp) 第1float引数 -136(%rbp) 第6int引数、int引数の領域は6*8=48バイト -144(%rbp) 第5int引数 -152(%rbp) 第4int引数 -160(%rbp) 第3int引数 -168(%rbp) 第2int引数 -176(%rbp) 第1int引数
この場所にレジスタの内容を取り込むコードを生成するためには、まずこの場所を確保する 必要がある。この場所はフレームの先頭部分であるから、176バイトの大きさを占める フレーム変数がフレームの先頭部分に割当てられるようにすればよい。
バックエンドでフレーム変数の場所(オフセット)を決めているのはCodeGenerator のprocessFramesメソッドであり、それが最初に呼ばれるのはLateRewritingのフェーズである。 processFramesメソッドでは、既にオフセットの決まっている変数があったら、決まっていない 変数に対してはそれ以降のオフセットを割当てる。また、フレーム変数を登録するときに オフセットを強制的に指定することも出来る。
これらのことから、フレームの先頭部分を確保するには、LateRewriting以前のフェーズで フレーム変数を登録し、そのときにオフセットを強制的に指定すればよいことが分かる。 x86.tmdでは、EarlyRewritingフェーズでva_startが呼ばれていることが 分かったときに、その関数が可変引数関数であると判定している。ここでもその方式で、 EarlyRewritingフェーズでva_startが呼ばれていることが 分かったときに、setVaStartCalledメソッドで、フレームの先頭の176バイトを確保することにする。 それには、そのメソッドで
func.localSymtab.addSymbol("__argSaveArea", Storage.FRAME, Type.AGGREGATE, 16, -176, null);
を実行すればよい。実際にレジスタから取り込むコードを生成するのは %defemit(prologue)である。
さらにGCCが生成するコードを調べると、上記の場所から値をとり出す方法が分かる。 それをC言語のプログラムの形で書いてみると次のようになる。
int varargs_print(int length, double dbl, ...) { va_list args; int i; int *int_address; /* = -176(%rbp); int型の第1引数の番地 */ void *stack_address; /* = 16(%rbp); スタック渡しの最初の引数の番地 */ /* va_start(args, dbl); */ int int_offset = 8; /* int型の仮引数の個数*8 */ int float_offset = 64; /* float型の仮引数の個数*16 + 48 */ printf("varargs_print\n"); printf("1 : double %f\n", dbl); for (i = 2; i <= length; i++){ if (i%2 == 0) { /* printf("%d : int %d\n", i, va_arg(args, int));*/ int *target_address; if (int_offset < 48) { target_address = int_address + int_offset; int_offset += 8; } else { target_address = stack_address; stack_address += 8; } printf("%d : int %d\n", i, *target_address); } else { /* printf("%d : double %f\n", i, va_arg(args, double));*/ double *target_address; if (float_offset < 16*8+48) { target_address = int_address + float_offset; float_offset += 16; } else { target_address = stack_address; stack_address += 8; } printf("%d : double %f\n", i, *target_address); } } /* va_end(args); */ /* do-nothing */ }
これに相当するコードを生成するために、stdarg.hを 作成した。(COINSでは、sparcとx86用のstdarg.hがlang/c/include/stdarg.h に用意してあったので、それにx86_64用のものを追加し、それでlang/c/include/stdarg.h を置換えてある)
そのマクロ定義によって、前記の例のva_list args; va_start(args, dbl); va_arg(args, type); // typeは型名 va_end(args);がそれぞれ
volatile long __int_address; // int *__int_address; volatile long __stack_address; // void *__stack_address; volatile int __int_offset; // int __int_offset; volatile int __float_offset; // int __float_offset; volatile long args; // long args; __va_start(__int_address, __stack_address, __int_offset, __float_offset, dbl); *(type *)__va_arg(__int_address, __stack_address, __int_offset, __float_offset, (type)args) ; /* do-nothing */
に展開される。これで、引数の場所に書かれていた型名が 型名を書くべき場所に移される。volatileとしたのは、これらの変数が SSA最適化の対象とならないようにするためである。
その結果得られるLIR式に対して、EarlyRewritingで レジスタ渡しの引数を取り込む場所を確保し、 LateRewritingで__va_startの呼び出しを__int_address = -176(%rbp); __stack_address = 16(%rbp); __int_offset = 8; /* int型の仮引数の個数*8 */ __float_offset = 64; /* float型の仮引数の個数*16 + 48 */に相当するLIR式に書き換える。そのためには、その時点で仮引数の個数が分かる必要がある から、
(defrewrite (PROLOGUE) (to (eval "paramCount($0)")) (phase early))
というdefrewriteを追加して、このparamCountメソッドで仮引数の 個数を数えてX86_64Attrオブジェクトに記録しておく。 (CALL __va_startとPROLOGUE式に対しては、EarlyRewritingもLateRewritingも行われることになる。)
なお、ここで、最後の引数dblもX86_64Attrオブジェクトに記録している。 その記録があれば、PROLOGUEのLateRewritingで、関数の最後の仮引数が それに等しいかというチェックをすることが出来る。
__va_argの呼び出しは、(type)argsの型が整数型であるときはif (__int_offset < 48) { temp = __int_address + __int_offset; __int_offset += 8; } else { temp = __stack_address; __stack_address += 8; } returnvalue = *temp;に、(type)argsの型が浮動小数点型であるときは
if (__float_offset < 16*8+48) { temp = __int_address + __float_offset; __float_offset += 16; } else { temp = __stack_address; __stack_address += 8; } returnvalue = *temp;
に相当するLIR式に、それぞれ書き換えている。この書き換えには新しいラベルを 作って、それを使ったJUMPC式などを作る必要がある。
新しいラベルを作るときはLabel tLabel = new Label("xx"+lir.getLabelVariant());のようにすると、文字列"xx"の後に新しい番号が付いたラベルが得られる。 そのラベルを参照するノードは
lir.labelRef(tLabel)で作られる。そのラベルの値(location)を定義するノードは
lir.node(Op.DEFLABEL, I64, lir.labelRef(tLabel))で作られる。 このように、if文に相当するLIR式を追加したときには制御フローグラフも 変わることになる。そのような変更をしたときは、
func.touch();を呼んでおく必要がある。これによって、これ以後で制御フローグラフが 必要になったときにはそれの作り直しが行われる。
int fact_trec(int n, int im) { if (n == 0) return im; return fact_trec(n-1, n*im); }この最後の
return fact_trec(n-1, n*im);
が末尾再帰の関数呼び出しである。これを見つけて、そのCALL命令を 関数の先頭へのJUMP命令に置換えればよい。ただし関数の先頭の PROLOGUEからは、いろいろな命令が生成される。それらの命令の中の どの部分にJUMPすればよいかを考える必要がある。
PROLOGUEに関して生成される命令のうち、スタック操作に関する命令は コード生成の最終段階で生成され、その生成のプログラムは
%defemit(prologue =f)
に書かれている。 もう一つの、引数を引数レジスタから仮引数に取り込む命令は、 LateRewritingのrewritePrologueメソッドによって作られる。 JUMP命令の飛び先はこの後者の部分である。
末尾再帰の関数呼び出しを見つけることと、それをJUMP命令に置換えるのを、 バックエンドのどのフェーズで行うのがよいかを考えるために、上記の例題が コンパイルされるときのトレースを眺めてみる。
まず、HIRでは(return 21 int line 6 (call 22 int (addr 23 <PTR <SUBP <( int int )> false false int>> <subp 24 <SUBP <( int int )> false false int> fact_trec>)
となっているから、この段階で見つけるのは比較的簡単である。呼んでいるsubpの名前が 自分の名前と同じであるかの判定をすればよい。 しかし、その判定結果をどのようにL式に反映させるかを考える必要がある。
次に、Before LateRewritingの段階では(CALL (STATIC I64 "fact_trec") ((SUB I32 (REG I32 "n.1%") ...) .. (SET I32 (REG I32 "returnvalue.4%") (REG I32 "functionvalue.5%"))
となっているから、この段階で見つけるのも比較的簡単である。しかし、 CALLの実引数の式はCALL式の中に入っている。その実引数の処理を済ませてから JUMP命令に置換える必要がある。
次に、After LateRewritingの段階では(PARALLEL (CALL (STATIC I64 "fact_trec") () ((REG I32 "%eax"))) ...) (SET I32 (REG I32 "functionvalue.5%") (REG I32 "%eax")) (SET I32 (REG I32 "returnvalue.4%") (REG I32 "functionvalue.5%"))
となっているから、少しパターンが長くなるが、見つけられないことはない。 この段階では、実引数を計算する式はCALL式の前に出されているから、この空になったCALL式を JUMP命令に置換え、残りの2つのSET式と、それに続くJUMP式を削除すればよい。
ところで、tmdではdefruleやdefrewriteで記述できるパターンは一つのL式であり、 上記のようなL式の列をパターンとして記述することは出来ない。そのようなパターンを見つけるには L式の列をスキャンするプログラムを書く必要がある。
以上のことから、x86_64.tmdでは、以下のようにして実現している。
まず、LateRewritingのrewriteCallで、自分自身の呼び出しである場合は X86_64AttrのisRecursiveをtrueにする。次に
public Transformer[] lateRewritingSequence() { return new Transformer[] { localLateRewritingTrig, TailRecursionTrig, ProcessFramesTrig }; }
とすることによって、localLateRewritingがすんだ後(rewriteCallなどが実行された後) でTailRecursionの処理をするメソッドtailRecursion()を呼び出す。
tailRecursion()では、X86_64AttrのisRecursiveがtrueであるときに、 L式の列をスキャンして、上記のパターン
(PARALLEL (CALL (STATIC I64 自分自身) ...) (SET (REG "functionvalue...") ...) (SET (REG "returnvalue...") (REG "functionvalue...")) (JUMP ... )
があったらそれを関数の先頭の引数取り込みの場所(この時点でのPROLOGUE式の直後: この時点ではPROLOGUE式の直後には引数取り込みの命令があるから、その直前) へのJUMP式に置換える。
その結果、上記のfact_trec関数に関しては、以下のコードが生成される。
fact_trec: subq $8,%rsp .L13: cmpl $0,%edi ; if (n == 0) jne .L5 .L4: jmp .L6 ; return .L5: leal -1(%rdi),%eax ; %edi(1st arg n) - 1 imull %esi,%edi ; %esi(2nd arg im) * %edi(1st arg n) movl %edi,%esi ; n*im --> 2nd arg movl %eax,%edi ; n-1 --> 1st arg jmp .L13 .L6: movl %esi,%eax ; 2nd arg --> return value addq $8,%rsp ret
void quickSort(int* a,int i,int j){ printf("quickSort(a, %d, %d)\n", i, j); int p, k; if(i==j) return; p=pivot(a,i,j); if(p!=-1){ k=partition(a,i,j,a[p]); quickSort(a,i,k-1); quickSort(a,k,j); } }
このプログラムには2ヶ所に再帰呼び出しがあるが、後のものが 末尾再帰の呼び出しである。
Late Rewritingの直前のLIRでは、このあたりは次のようになっている。(CALL (STATIC I64 "quickSort") (引数)) (CALL (STATIC I64 "quickSort") (引数)) (JUMP (LABEL I64 ".L7")) (DEFLABEL (LABEL I64 ".L7")) (EPILOGUE (0 0))また、localLateRewritingがすんだ後には"(CALL ...)"の部分は、
引数を求めるコード (PARALLEL (CALL (STATIC I64 "quickSort") () ())となっている。そこで、localLateRewritingの後で呼ばれる tailRecursion()の中で、
(PARALLEL (CALL (STATIC I64 自分自身) ...) (JUMP target)というパタ−ンを見つけ、それを記録しておいて、最後のEPILOGUEの直前のラベル定義 のラベルと同じものがtargetとして使われていたら、記録しておいた部分を この時点でのPROLOGUE式の直後へのJUMP式に置換える。