読者です 読者をやめる 読者になる 読者になる

LSI C-86 の最適化

ちょっと前にうろおぼえでこんなツイートをしていたのですが、

確認したところ、階乗ではループになりませんでした(ダメですねうろおぼえで書いては)。
LSI C-86 試食版を実行できる環境を作ったので、それで実際に生成させた、末尾再帰がループになる例を紹介します。
関数は 1, 2, ...n の総和を計算する sum という関数です。
まず簡単に、末尾再帰でないソースコードコンパイル結果を示します( lcc -S で出力された a86 用コード)。

int
sum(int x)
{
	return x ? (x + sum(x-1)) : x;
}
sum_::
	PUSH	CX
	MOV	CX,AX
	TEST	CX,CX
	JE	_4
	MOV	AX,CX
	DEC	AX
	CALL	sum_
	ADD	AX,CX
	JMP	_6
_4:
	MOV	AX,CX
_6:
	POP	CX
	RET

LSI C-86 は、他の多くの 8086 をターゲットとしたコンパイラと違い、可変長でない関数の引数がレジスタ渡しな点で、人間がアセンブリ言語で書くような感じにちょっと近いコードが生成されます。
累加変数用の引数を追加して、末尾再帰に書き換えると、こんな感じになります。

int
sum(int x, int a)
{
	return x ? sum(x-1, a+x) : a;
}
sum_::
	PUSH	CX
	MOV	CX,AX
	TEST	CX,CX
	JE	_4
	MOV	AX,CX
	DEC	AX
	ADD	BX,CX
	CALL	sum_
	MOV	BX,AX
_4:
	MOV	AX,BX
	POP	CX
	RET

こんなコードが生成されます。LSI C-86 の呼出規約では CX はcallee saveなので、関数の入口・出口にプッシュ・ポップがあるため、呼出しをジャンプにできません(同じ理由で、DX が壊れる MUL 命令が必要な階乗もループにならない)。
ここで、関数の返す値は AX を使いますから、累加変数用の引数 a は AX で渡される第1引数にしたほうが良いコードが生成されるような気がしませんか? しますよね。というわけで、引数の順序を変えてみます。

int
sum(int a, int x)
{
	return x ? sum(a+x, x-1) : a;
}
sum_::
	TEST	BX,BX
	JE	_4
	ADD	AX,BX
	DEC	BX
	JMP	sum_
_4:
	RET

というわけで、見事にループになりました。

余談

(4月4日、ちょっと加筆)
LSI C(-86、とは確定できない)についてはこんな話があります。
中村正三郎さんの『電脳騒乱節 VOL.2』(1991、初出は『ざベ』'89/Jun)p. 45 に、LSI C の作者の森さん( @kmori58 さんである)が LSI C は「(ドラゴンブック)を読めば,誰でも作れますからと涼しげに」言っていた、という話が書かれています。で、このように書かれているのを読んだことがある、と、とあるコンパイラ最適化ハッカーに話したところ(2010年の夏)、言下に「そんなはずがない」(間違いなく、それは謙遜して言っているか、何かだろう)と否定されました。そのハッカーによると、おすすめはドラゴンブックではなくタイガーブックとのことでした(龍と虎と、というジョークではなしに)。
どうも他の話なども総合すると「コンパイラを書くというだけならそんなに凄いことでもない、ドラゴンブックを読めば書ける」という趣旨だったようで、LSI C(特にその最適化)については別の話、と考えるのが良いようです。
LSI C は最適化オプションこそ控えめですが( -O0 で、アセンブラによるジャンプ命令の最適化(多分、届くならばニアジャンプを生成する、だと思う)が抑止される、という1種類だけ)、ここで見たように(ここでの例はtinyなものでしたが)きっちりと良いコードが生成される処理系です。