case文(switch文)の実装

 Pascalでいうcase文、すなわちC/C++などでいうswitch文には、高速なコードを生成して欲しいという願いがこめられているように思う。仮想マシンのインタプリタを作るときなど長大なcase文が現れるが、これに対してcmp命令の羅列のコードが生成されたりすると、なんだこのタコ、と思わず叫びそうになる。
 だから、Cabezonの場合も、他のコードはともかく、case文だけは入念に最適化されたコードを生成するようにしている。具体例で見てみよう。
 Cabezonのcase文コードは、何種類かのパターンを用意しておいて、コストベースで最適なパターンを選ぶというアプローチをとっている。初期のCabezonは、以下の三種類のコードの中から、メモリ使用量が最も少ないコードを生成するようになっていた。

 具体的には以下のような感じになる。

	case n of
	1: (* ... *)
	2: (* ... *)
	3: (* ... *)
	end

	に対するコードは、

	mov	ax, word ptr _N
	cmp	ax, 1
	je	_76		; 1の場合のコード
	cmp	ax, 2
	je	_77		; 2の場合のコード
	cmp	ax, 3
	je	_78		; 3の場合のコード
				; そのほかの場合

 場合分けがもっと多い以下の場合は、

	case n of
	1: (* ... *)
	2: (* ... *)
	3: (* ... *)
	4: (* ... *)
	5: (* ... *)
	end

 以下のような、テーブルジャンプのコードになる

	mov	ax, word ptr _N
	mov	di, ax
	sub	di, 1
	cmp	di, 4
	ja	_73		; その他の場合
	shl	di, 1		; 二倍して
	jmp	cs:_75[di]	; テーブルジャンプする
;	...
;
_75	dw	_76, _77, _78, _79, _80

 ところが、最近のCabezonでは、コードの種類は二種類になった。これはNIFTYのFPLでsuto氏から教わった方法で、「バイナリサーチのコードをインライン展開する」というものである。具体的なコードで見てみよう。

	case n of
	1: (* ... *)
	2: (* ... *)
	4: (* ... *)
	8: (* ... *)
	16: (* ... *)
	end
 上記のように値の幅が大きいときには、テーブルジャンプではメモリ使用量が多くなってしまう。そのため、以下のようなコードを生成する。
	mov	ax, word ptr _N
	cmp	ax, 4		; まず4と比較して
	jg	_81		; 大きい場合
	je	_78		; =4 の場合
	cmp	ax, 1		; 4より小さい場合
	je	_76		; =1 の場合
	cmp	ax, 2
	je	_77		; =2 の場合
	jmp	_73
_81:
	cmp	ax, 8		; 4より大きい場合
	je	_79		; =8
	cmp	ax, 16
	je	_80		; =16

 上記のように、小さいものから順に比較するのではなく、バイナリサーチの順番、すなわち中央値から比較して、順に範囲を絞っていくようなコードを生成している。これは巧妙であり、STRING命令よりも効率が良いため、現在ではバイナリサーチのコードか、テーブルジャンプのコードのどちらかを生成するようになっている。

目次
Last update: '2000年05月31日