Z80 vs 6502
目次
カウンタレジスタ化
2014.8.4 午前追記。
ここまでのプログラムでは、ループカウンタは、ゼロページメモリでした。レジスタは Y が余っているのですが、A と Y の足し算命令は無いため、使えない…と思っていました。
次のプログラムは、巧妙な手法で Y レジスタをループカンタに使い、事実上の「A と Y の足し算」を実現するものです。
LDY #100 ; 2
LDA #0 ; 3
TAX ; 2
JMP SKIP ; 3
INCH:
INX ; 2
DEY ; 2
BEQ EXIT ; 3 / 2
SKIP:
CLC ; 2
LOOP:
ADC TABLE,Y ; 4
BCS INCH ; 3 / 2
DEY ; 2
BEQ EXIT ; 3 / 2
ADC TABLE,Y ; 4
BCS INCH ; 3 / 2
DEY ; 2
BNE LOOP ; 3 / 2
EXIT:
STA >0 ; 3
STX >1 ; 3
プログラムとは別に、1ページ（256byte 単位に区切られたメモリ領域）を使って 0～255 を格納したテーブルを作る必要があります。上記コードは 34バイトなのですが、テーブルが 256バイト。
A と Y の足し算はできないのですが、特定アドレスに Y を足したメモリ内容との足し算は出来る、という仕様を使い、Y の値とメモリ内容が一致するようにする、というテクニックです。
ゼロページとの足し算は 3クロック、Yレジスタを利用した足し算は 4クロックで、足し算部分は 1クロック遅くなります。しかし、ループカウンタとしての「減算」は、5クロックから 2 クロックへと、3クロックも速くなります。差引 2クロックの高速化です。
ループカウンタは 100 回減算されるので、全体で 200クロック速くなります。前処理でもレジスタに直接値を入れられるため、3クロック速いです。
上記プログラムでは、ループ展開も使っています。元のプログラムでは5回分を展開していましたが、ループ展開競争になると歯止めが利かないので、2回に変更させてもらいました。（ローカルルール参照）
ループ前半で「終了タイミング」が来ると、BEQ EXIT で終了します。後半で終了タイミングが来ると、BNE LOOP でジャンプせずに終了します。
条件分岐命令は、ジャンプしないと 1クロック速いです。なので、終了条件時以外は、前半は 1クロック得している。後半で終了すれば、そこでも１クロック得できる。
これ、繰り上がりタイミングがわからないとクロック数計算できませんね。調べると… 3, 6, 8, 11, 14, 17, 20, 24, 27, 30, 34, 38, 42, 47, 52, 57, 64, 71, 82 回目の演算で繰り上がります。全部で19回。
前の計算との差（繰上りなしに計算する回数）を２で割って端数を切り捨てると、１クロック得する（ループ展開の効果が出る）回数がわかります。…全部で 42クロックです。
そして、最後の繰り上がりが 82 回目なので、最後のループ終了は、末尾で終わります。ここでも１クロック得する。…とはいえ、これは普通にループを作ったときと同じ条件。
総計で 245クロック速くなり、1150クロックになります。
1ページ使い切ってしまう巨大テーブルはどうなのか…と思ったのですが、実際にファミコンプログラムなどで使用されていたテクニックだった、ということで OK にしました。テーブルは他の同様の演算個所でも共有されるため、全体で見れば高速化のメリットの方が勝る、と考えられたようです。
条件省略
2014.8.4 午後追記。
後に出てくる（でも先に公開していた）Z80 のプログラムでは、ループ展開時にループ内の条件判断を無くす、という手法を使っていました。これは、非常に高速化できる手法です。
でも、先に書いた 6502 のカウンタレジスタ化では、ループ展開していますが繰り上がり時にループ先頭に戻ってしまうため、条件判断は無くせない。…僕はそう思っていました。
しかし、巧妙に実行順を保証したプログラムを作った人がいました。
LDY #100 ; 2
TYA ; 2
ROR A ; 2
LDA #0 ; 2
TAX ; 2
BCC LOOP ; 3/2
CLC ; 2
BCC MOD1 ; 3/2
INCH:
INX ; 2;
DEY ; 2
BEQ EXIT ; 3/2
CLC ; 2
LOOP:
ADC TABLE,Y ; 4
BCC SKIP ; 3/2
INX ; 2
CLC ; 2
SKIP:
DEY ; 2
MOD1:
ADC TABLE,Y ; 4
BCS INCH ; 3/2
DEY ; 2
BNE LOOP ; 3/2
EXIT:
STA >0 ; 3
STX >1 ; 3
全部で 37バイト。ループ展開時は40バイト以内、というルールに従っています。
そして、実行順を保証するために、２回分のループ展開をしているにもかかわらず、前半と後半で全然違うプログラムです。実行クロック数も異なります。
ラベル LOOPから MOD1 の前までが前半。繰り上がらない場合は SKIP にジャンプします。
繰り上がり有りで 12クロック、なしの場合は 9 クロック。
MOD1 から EXIT の前までと、INCH から LOOP の前までが後半。繰り上がる場合は INCH に、そうでない場合は LOOP にジャンプします。
繰り上がり有りで 15 クロック、なしの場合は11 クロック。ループのためのジャンプ(通常 3クロック)を含んでいるのに、繰り上がりなしの場合に 2クロックしか増加していない、というのが高速化ポイント。
これ、クロック計算面倒ですね…。前半はループの奇数回目、後半は偶数回目の計算になるので、先の繰り上がりタイミングを奇偶を別に数えてみると、前半で繰り上がるのが 7回、後半が 12回になります。
全体の計算回数は 100回なので、前半後半各 50 回。それに繰り上がりを考慮して…
12*7 + 9*43 + 15*12 + 11*38 -1 = 1068クロック。これが、ループ部分の所要時間になります。
計算式を見るとわかりますが、「1～100の足し算」に限って言えば、一番多く通る(43回)ルートが、一番短いクロック数(9クロック)なのが絶妙。狙って書いたならすごいし、偶然でも素晴らしい高速化。
ちなみに、最後に -1 しているのは、ループの最後はジャンプせず、１クロック速くなるためです。
前処理に13クロック、後処理に 6クロックかかりますので、総計は 1087クロックになります。