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