Fuzix-Compiler-Kitの6800用コンパイラ(6)（ベーシックマスター開発 その38）

2024/11/22BASICMASTER, 昔のパソコン

私がFuzix-Compiler-Kitを使うようになって、6800で動くコードが出るようになったのは2024年10月上旬ごろ。issueが反映されたのが10月下旬。

commit logを確認すると 2ad3a0f56b0f07f4ac3a705827f9bb09428c5a09 のあたりである。

その頃のコードと現在のコード、手元ていじってるコードを比較して、どれぐらいコード生成が良くなったのかを確認してみよう。


8 Queen

最初のサンプルは8 Queenである。昔から探索の入門に使われている。

プログラム：

再帰呼び出しで解くプログラム。盤面チェックのためにグローバル変数 col/up/down を使っている。

cpu_counter は、現時点までのCPU cycle数を報告するようにemulatorに伝える関数。


/*
 *	8 queens
 */

#include	"common.h"

char	x[8],col[8],up[15],down[15];
int		count=0;

void
generate(char n)
{
	char	k;
	char	h;
	char	i;

	for(h=0; h<8; h++){
		if(col[h] && up[n-h+7] && down[n+h]){
			x[n] = h;
			col[h] = 0;
			up[n-h+7] = 0;
			down[n+h] = 0;
			if(n==7){
				for(k=0; k<8; k++){
					putch(x[k]+'0');
				}
				putch('\n');
				count++;
			}else{
				generate(n+1);
			}
			down[n+h] = 1;
			up[n-h+7] = 1;
			col[h] = 1;
		}
	}
}

int main(int argc, char *argv[])
{
	char	k;

	cpu_counter();
	for(k=0; k<8; k++){
		x[k]=-1;
		col[k]=1;
	}
	for(k=0; k<15; k++){
		up[k] = 1;
		down[k] = 1;
	}
	generate(0);
	cpu_counter();
	putstr("total=");print(count);print_cr();

	return 0;
}


速度比較

最初の頃と比べると、実行時間は半分以下になっている。

最適化オプションは -Os でも -O3 でも実行時間に変化はなかった。

バージョン-O3速度比オブジェクト行数
2024/10/28版67088141.001246
2024/11/22版59611290.881185
手元最新31163850.461151


コード比較(1)

関数generateの中のfor文がどのようにコンパイルされたかを見てみよう。


	for(h=0; h<8; h++){

2024/10/28版

ローカル変数 h は、スタックトップから2番目にあるので、 tsx / clr 1,x で初期化する。

ループ回数の比較は h をintにした後に 8 と比較するサブルーチン（cclt）を呼んでいる。fccでは、charのデフォルトはunsignedなので、clraでint化できる。

h++ を行うために、xplusplusc　（0,xを増やす関数） を呼んでいる。


        tsx
        clr 1,x
;
L29_l:
        tsx
        ldb 1,x
        clra
        pshb
        psha
        ldab #8
        jsr __cclt
;
        jeq L29_b
        jmp L29_n
L29_c:
        ldab #1
        tsx
        inx
        jsr __xplusplusuc
;
        jmp L29_l


2024/11/22版

初期化と比較は同じ。ループ変数を増やすのは、ヘルパー関数を呼ばずに inc 1,x を行っている。


        tsx
        clr 1,x
;
L29_l:
        tsx
        ldb 1,x
        clra
        pshb
        psha
        ldab #8
        jsr __cclt
;
        jeq L29_b
        jmp L29_n
L29_c:
        tsx
        inc 1,x
;
        jmp L29_l


手元最新

比較もヘルパーを呼ばずに、cmpb / jge 命令を使っている。これは、peep hole optimize （rules.6800）を使っている。

Fuzix-Bintools の6800アセンブラは、bgeの代わりにjgeと書けて、短い分岐で届かないときはjmpを生成してくれる。かしこい。


        tsx
        clr 1,x
;
L29_l:
        tsx
        ldb 1,x
        cmpb #8
;       optimized by rule
        jge L29_b
        jmp L29_n
L29_c:
        tsx
        inc 1,x
;
        jmp L29_l

コード比較(2)

関数generateの中の大域変数への代入文を見てみる。


	col[h] = 0;

2024/10/28版

変数 col の先頭アドレスと添字 h を足し、それをスタック経由で IX に移動して 0 を stb している。


        tsx
        ldb 1,x
        clra
        addb #<_col+0
        adca #>_col+0
        pshb
        psha
        clrb
        tsx
        ldx ,x
        ins
        ins
        stb 0,x

2024/11/22版

IX への移動がゼロページ経由になり、クリアも clr 0,x を使っている。手元最新版も同じ。

6800はアドレス計算が苦手なので、コードが長くなるのが難点。サイズを無理やり短くするなら（-Osするなら）、IXへの移動をサブルーチン化するぐらいか（3バイト減る）。


        tsx
        ldb 1,x
        clra
        addb #<_col+0
        adca #>_col+0
        staa @tmp
        stab @tmp+1
        ldx @tmp
        clr 0,x

TL/1 は、このような配列アクセスを自己書き換えで行なっていて速かった （TL/1コンパイラの作り方、ASCII 1980年08月号 P.148～）。

富士通MB8861/8871なら、adxが使えるので少し短くなるし、6803/68HC11ならabxやxgdxがあるので楽勝である。ほんと、6800ツラい。

コード比較(3)

配列の添字が式の場合。


	up[n-h+7] = 0;

2024/10/28版

素直に左から計算。minusはスタックトップからAccABを引いた値を返すヘルパー関数。


        tsx
        ldb 5,x
        clra
        pshb
        psha
        ldb 1,x
        clra
        jsr __minus
        addb #7
        adca #0
        addb #<_up+0
        adca #>_up+0
        pshb
        psha
        clrb
        tsx
        ldx ,x
        ins
        ins
        stb 0,x

2024/11/22版

アドレスのIXへの転送が@tmp経由になり、クリアが clr 0,x になった。


        tsx
        ldb 5,x
        clra
        pshb
        psha
        ldb 1,x
        clra
        jsr __minus
        addb #7
        adca #0
        addb #<_up+0
        adca #>_up+0
        staa @tmp
        stab @tmp+1
        ldx @tmp
        clr 0,x

手元最新

スタックに積まずに直接引き算。定数7と配列アドレスの加算命令は1つに纏められそう。そのうち考える。


        tsx
        ldb 5,x
        clra
        subb 1,x
        sbca #0
        addb #7
        adca #0
        addb #<_up+0
        adca #>_up+0
        staa @tmp
        stab @tmp+1
        ldx @tmp
        clr 0,x

続く


参考文献

オブジェクトコードの生成は、全命令を頭に入れておいて使えそうな組み合わせを捻り出す作業と、それをコンパイラのコードに落とす作業が必要である。

命令セットについては、モトローラの本が確実で良い。日本語だと国会図書館デジタルコレクションで何冊か読める。

コンパイラについては、Fuzixや他のコンパイラのコードを見るのが良いのだが、参考になるMC6800用のコンパイラは少ない。6809用のコンパイラを見て考えてもいいのだけど、そもそも発想を変えないといけない部分もあって難しい。

BASICMASTER, 昔のパソコン

Posted by ず＠沖縄