case文(switch文)の実装

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

• CMP命令の羅列（リニアサーチ）
• STRING命令による検索
• テーブルジャンプ

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

	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命令よりも効率が良いため、現在ではバイナリサーチのコードか、テーブルジャンプのコードのどちらかを生成するようになっている。

目次