マシン記述の実装例

ここでは、組込み向けマシンのTMD(マシン記述)のいくつかとx86の64ビットモードの実装について説明する。

実装されたtmdファイルはsrc/coins/backend/genディレクトリに入っている。

ARMのマシン記述の実装

ARMのマシン記述は組み込み向けに強化したバックエンドの新機能を使用す ることで TMD の記述量が減少することを検証するために実装したものである。

実装したARMのマシン記述ファイルは、arm.tmdという名前でCOINSのソースディ レクトリsrc/coins/backend/genの中に置いてある。

仕様

ARM Linux 用の gcc と互換性を取るという方針で実装した。ただし gcc はい ろいろなオプションを持っているので完全に互換なわけではない。なおターゲッ トは ARM Linux であるから hosted 環境(OS を持つ環境)となる。したがっ て特別な作業を行わずともターゲット上に用意されている各種のライブラリを 使用することができる。
なお浮動小数演算は FPU 命令を生成するが、実際には ARM Linux カーネルに よるソフトウェアエミュレーションで実行される。(gcc の hard float と同 等)

使用方法

ターゲットは ARM Linux であるから、基本的には通常の PC 用 Linux での使 用方法と同じである。異なる点はコンパイル・リンクして得られた実行ファイ ルを実行するさいに、ファイルをターゲットに転送する必要があることくらい である。 なおコンパイル時に以下のようにオプションを指定することで ARM マシン記 述によるコード生成が行われる。
 -coins:target=arm

THUMBのマシン記述の実装

組み込み用プロセッサによくある近接アドレスによる定数(リテラル)のロー ドや到達範囲の限られた分岐命令を簡単に利用できるように、バックエンドに リテラルとブランチの変換を追加した。このフィルタの動作を検証するために 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
標準ライブラリの利用
ARM 環境のライブラリをTHUMBのコードから利用するためには gcc を使用して 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      lr
THUMBのマシン記述の生成コードは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のマシン記述の実装

MicroBlazeのマシン記述はマルチコアの機種に対するTMDを実装したもので ある。命令パターン指定とコスト指定の多様性 (実行速度とコードサイズのコ スト) に対応する拡張機能を使用した記述を行っている。

実装したMicroBlazeのマシン記述ファイルは、mb.tmdという名前でCOINSのソースディレクトリsrc/coins/backend/genの中に置いてある。

実装方針

Xilinx社の提供する mb-gcc と互換性を取るという方針で実装した。ただし gcc はいろいろなオプションを持っているので完全に互換ではない。 なおターゲットは free standing 環境(組み込み環境で、OS を想定しない環境)を想定している。
命令セット

MicroBlaze はソフトコア CPU のため、合成時のオプション設定で一部の 機能を制限することができる。

デフォルトでは MicroBlaze の全機能を有効にすることを想定したコード 生成を行う。すなわち以下の機能を使用するコードを生成する。

ただし、オプションの指定でこれらの機能を使用しないコードを生成することもできる。
コード生成オプション
コンパイル時のオプション
-coins:x-mb=foo
で使用しない命令を指定できる。このfooでは以下の指定ができる。
speed と size のコスト
速度優先・スペース優先の指定 が出来るようになったので、以下のような命令に関してspeedとsizeのコストをtmdに 書き込んである。これらについては速度優先(デフォールト)かスペース優先
-coins:optspace
かを指定することによって違う命令が生成される。
シフトのコード生成

1ビットシフトについては、ALU による左シフト、1 ビットシフトユニット による右シフトが最速・最短 (1サイクル, 4バイト) であるので、add 命令あ るいは1ビット右シフトの命令が生成される。(MicroBlaze は1ビット左シフト 命令を持たない。)

2以上の定数nによるnビットのシフトは以下のようになる。
乗算のコード生成
2 倍は add命令が最速・最短 (1サイクル, 4バイト) であるのでそれを生成する。 それ以外の場合は乗算器が使えるか使えないかで異なる。乗算器による乗算は3サイクルで処理される。
その他の制限
以下の機能はサポートしていない。

使用方法

MicroBlazeのマシン記述は OS の存在しない組み込み環境を想定している ため、すべての場合に通用する一般的な使用方法というものは記述できない。

そのため、ここでは Xilinx社のEDK(Embedded Development Kit)に含ま れている mb-gdb のソフトウェアシミュレータ上で COINS のテストプログラ ム集を実行するための手順を簡単に記述する。

なおコンパイル時に以下のようにオプションを指定することでMicroBlazeマシン記述によるコード生成が行われる。

 -coins:target=mb
必要なもの
コンパイル・リンク方法
mbccc.sh
指定されたソースファイルをコンパイル・リンクする。(複数ファイルは処理できない。)
#!/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
mbgdb.sh
指定されたファイルをシミュレータ上で実行する。
#!/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
mbtest.sh
指定されたファイルをコンパイル・リンク・実行し結果を正解と照合する。
#!/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
lib.c
サポートファイル

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);

x86_64のマシン記述の実装

x86_64のマシン記述x86_64.tmdの実装は、x86.tmdをベースとして始めた。 x86の既存の命令は64ビットモードでも使えるから、その部分はそのまま残している。しかし、 使える汎用レジスタの数や浮動小数点レジスタが大きく違うし、関数呼び出しの規約も 全く違うので、書き直すべきところは多い。 以下では,主としてx86.tmdの簡単な真似ではすまないものについて説明する。

インテルx86の64ビットモード

64ビットモードでは次のものが使える.

浮動小数点レジスタとしては、従来からの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相対アドレスが使える。

HIR用のマシン記述

マシン記述は主として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レジスタ以外のレジスタからなる集合、として定義してある。

関数呼び出しのコード生成

関数呼び出しの規約(calling convention)にしたがってPROLOGUE, EPILOGUE, CALLなどのコードを生成するのは、コード生成の中でもっとも重要であり、 かつ、一般にもっとも労力を要する仕事である。x86の64ビットモードのように その規約が複雑である場合は特にそうである。
64ビットモードでの関数呼び出しの規約

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を使うとする。

PROLOGUEのコード
PROLOGUEで行うことは、
  1. フレームポインタの退避とこの関数のフレームポインタの設定
  2. フレーム領域の確保
  3. この関数の中でcallee-saveレジスタが使われていたらそれをスタックに退避
  4. レジスタ上の実引数の値を仮引数に代入

である。このうち、最初の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次元配列として並べてある。

EPILOGUEのコード
EPILOGUEで行うことは、 であるが、 これらもアセンブリコード生成のときに考慮すれば良く、x86.tmdの
%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
である。
CALLのコード
CALLで行うことも、基本的にはx86.tmdの
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命令を実行した直後の値とする ものである。
%rbpを使わない場合のコード生成
今までのやり方では、関数のプロローグには必ず
	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命令による)
   ret
subqなどが必要なのは、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などで知ることが できる。
(1) %rbpを使う場合

(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
である。
(2) %rbpを使わない場合:

(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型の引数のコード生成

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;
}

可変引数関数のコード生成

ここでは、引数の個数が可変であるような関数を可変引数関数と呼ぶことにする。 C言語では、たとえば
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();
を呼んでおく必要がある。これによって、これ以後で制御フローグラフが 必要になったときにはそれの作り直しが行われる。

末尾再帰の関数呼び出しのJUMP命令化

末尾再帰の関数呼び出しのCALL命令はJUMP命令に置換えることが出来る。 そのような関数には、値を返す関数と値を返さない関数とがあるが、 LIRの命令列の形がそれぞれ異なるので、分けて考えてみる。
値を返す末尾再帰
たとえば、次のような末尾再帰の関数呼び出しがあるプログラムを考えてみる。
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
値を返さない末尾再帰
たとえば、下記の"quickSort"は値を返さない末尾再帰の関数である。
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式に置換える。