denseなオペコード『を』考察する

この記事は悠里・大宇宙界隈 Advent Calendar 2018の14日目の記事です。

1. 発端

opcode.html、opcodeについてあまり考えていないという話が知られていてだな。

炭酸ソーダさんの案はあって、あれはコード長を多少冗長にする代わりにかなり回路の実装が単純されそうである。

ということで、その逆の「2003lk互換であって、かつかなりdenseな機械語」を考えてみようと思った。

2. 統計

実際のコードで2003lkの諸々の頻度がどんな感じなのか気になるし、統計を取っていく。

まずは頂いたc-compiler.sからコメントを取り除いてc-compiler__.sを作る。

2-1. ソート

まずはソートして(c-compiler-sorted.s)、あとラベルを吹っ飛ばそう。あ、'c'iで行きます

2-2. lifem

まずはlifemを手動で数える。

とりあえずlifem ラベル名が628個、lifem 4bitの数が69個、lifem 4294967295が33個、lifem 673775616~2037671208が114個。lifem8 0は392個、それ以外のlifem8が11121個（多いな）。

2-3. xokとkue

こいつらは命令ではない。xokが22個。kueが141個。

2-4. ラベル絡み

malkrz xx ラベル名が496個。krz xx ラベル名が243個。inj f5@ xx ラベル名が1421個。

krz f5+4@ ラベル名が270個。krz f5+8@ ラベル名が107個。krz f5+12@ ラベル名が28個。krz f5+16@ ラベル名が3個。krz f5+24@ ラベル名が47個。

krz f0/f1 ラベル名が12個。krz f0/f1/f2 ラベル名@が79個。

2-5. 残り

残りはc-compiler-sorted-nolabel.s。f0/f1/f2/f3を全部regと改名したものがreg_unified.sである。

とりあえず uniq -cする。上の方はこんな感じ

 788 krz f5+4@ REG
 660 krz f5+8@ REG
 573 krz REG f5
 457 krz f5+12@ REG
 434 nta f5 12
 428 nta f5 16
 425 ata f5 16
 410 ata f5 12
 400 nta f5 8
 370 krz xx f5@
 365 ata f5 8
 159 krz REG f5+16@
 134 krz REG f5+20@
 128 krz REG f5+24@
 120 nta f5 20
 119 ata f5 20
 115 krz f5+16@ REG
 100 krz REG@ REG
  92 ata f5 32
  91 fi REG 0 clo
  90 krz f5+28@ REG

スタック関連を数えてみるか。

まとめると

  1. f5に足されるオフセットは4の倍数のみ（まあそれはそう）（スタック上のchar配列に書き込むときのために一応サポートだけはしておくべきだが）
  2. f5@ ~ f5+12@ [2bit] で 54.21%
  3. f5@ ~ f5+28@ [3bit] で 73.83%
  4. f5@ ~ f5+60@ [4bit] で 84.78%
  5. f5@ ~ f5+124@ [5bit] で 87.34%
  6. f5@ ~ f5+252@ [6bit] で 91.39%
  7. f5@ ~ f5+508@ [7bit] で 93.98%
  8. f5@ ~ f5+1020@ [8bit] で 95.63%
  9. f5

という感じである。さてこの状況で短縮表現は何ビットにするかという話がある。残りを32ビットで表すとすると僅差で6bit(期待値8.23bit) < 4bit(期待値8.26bit) < 5bit(期待値8.41bit) だが、そもそもメモリ空間が32bitである。となると符号付き16bitにしておけばそうそう困ることはない（とはいえローカル変数のバイト数が30000行くことはありそうよな、まあそのときは32bit作っておけばいいか）ことを考えると4bit(5.83) < 5bit(6.39) < 3bit(6.40) なので、まあ4bitでいいか。

ということでf5@ ~ f5+60@をSTACK_NEAR、それ以外をSTACK_FARと改名してunified.sとした。上位はこんな感じ。

2805 krz STACK_NEAR REG
1423 krz REG STACK_NEAR
 664 krz REG STACK_FAR
 588 krz REG f5
 434 nta f5 12
 428 nta f5 16
 425 ata f5 16
 410 ata f5 12
 400 nta f5 8
 370 krz xx STACK_NEAR
 365 ata f5 8
 277 krz STACK_NEAR 0
 241 krz REG REG
 208 krz REG 0
 148 krz STACK_NEAR 1
 131 krz REG@ REG
 120 nta f5 20
 119 ata f5 20
 107 fi REG 0 clo
  99 krz REG REG@

f5に足される値も調べてみるか。

調べてみたら、ata f5は4 ~ 32で92.90%、nta f5は4 ~ 32で96.57%だそうだ。ふむふむ。

あ、krz xx STACK_NEARは全部krz xx f5@です。まあ特殊扱いすることになるでしょうな

2-6. いままでのあらすじ

xx周り

1421 inj f5@ xx ラベル名
 496 malkrz xx ラベル名
 370 krz xx f5@
 243 krz xx ラベル名

xxはこれだけ。

残るラベル名

 455 krz STACK_NEAR ラベル名
  79 krz REG ラベル名@
  12 krz REG ラベル名

一般的な命令（トップ目）

2805 krz STACK_NEAR REG
1520 nta f5 4~32
1504 ata f5 4~32
1423 krz REG STACK_NEAR
 664 krz REG STACK_FAR
 588 krz REG f5
 370 krz xx STACK_NEAR

2-7. 残りをね

krz STACK_NEAR 即値

即値については…もう単純に全部の即値を一貫して扱うか。オフセットは一応分けよう。

頑張った結果(imm.s)、期待値はこうなった。

0	23.88905282
1	19.66037179
2	18.60666863
3	17.59840661
4	17.21923871
5	15.34110357
6	14.14753615
7	12.65801121
8	11.7816465
9	11.34139864
10	11.33726763
11	11.74358218
12	12.5665388
13	13.39805252

やっぱり符号なし8bitになりそうですな。負の数は32bit使うことになりそう。x86でそうなってるのはそうなってるからなんだなぁ。

今度はオフセット。REG+REG@は50件。それ以外のREG+値@は

0	21.324861
1	21.09213662
2	21.34868944
3	18.01826847
4	12.91818904
5	9.653693407
6	9.65528197
7	8.588562351
8	9.39158062
9	10.22398729
10	10.27958697
11	11.21683876

ということで符号なし7bitか8bit。じゃあ符号なし8bitでええやん。

なるほどなぁ。

以降は悠里・大宇宙界隈 Advent Calendar 2019の9日目の記事です。

3. 実際のオペコード

実はオペコード自体は考えていたのだが公開していないまま一年が経ってしまった。ウケる。

説明を書いているとさらに公開が遅れるのでもう最低限の説明で出してしまおう。これで如何にして現状の全命令がカバーできているかを考えるのは読者への課題とする。

凡例

引数 上＼下0123
() 0.00f0++;f1++;f2++;f3++;
() 0.01f0--;f1--;f2--;f3--;
() 0.10f0 = ~f0;f1 = ~f1;f2 = ~f2;f3 = ~f3;
() 0.11f0 = 0;f1 = 0;f2 = 0;f3 = 0;
() 1.00flag = (f0 == 0);flag = (f1 == 0);flag = (f2 == 0);flag = (f3 == 0);
() 1.01flag = (f0 != 0);flag = (f1 != 0);flag = (f2 != 0);flag = (f3 != 0);
() 1.10f0 = *f5; f5 += 4;f1 = *f5; f5 += 4;f2 = *f5; f5 += 4;f3 = *f5; f5 += 4;
() 1.11f0 = f5;f1 = f5;f2 = f5;f3 = f5;
(L0) 2.00L0++;L0--;L0 = ~L0;L0 = 0;
(L0) 2.01flag = (L0 == 0);flag = (L0 != 0);L0 = *f5; f5 += 4;?
(B0) 2.10xx += B0;xx -= B0;if(flag) xx += B0;if(flag) xx -= B0;
(V0) 2.11f0 = *V0;f1 = *V0;f2 = *V0;f3 = *V0;
(V0) 3.0xx += V0;xx -= V0;if(flag) xx += V0;if(flag) xx -= V0;f5 += V0;f5 -= V0;f5 -= 4; *f5 = V0;inj V0 xx f5@
() 3.10xx = *f5;???
(V0) 3.11f0 = xx + V0;f1 = xx + V0;f2 = xx + V0;f3 = xx + V0;
(L0,V1) 4.00lat V1 f0 L0lat V1 f1 L0lat V1 f2 L0lat V1 f3 L0
(L0,V1) 4.01latsna V1 f0 L0latsna V1 f1 L0latsna V1 f2 L0latsna V1 f3 L0
(L0,V1) 4.10inj V1 f0 L0inj V1 f1 L0inj V1 f2 L0inj V1 f3 L0
(L0,L1,V2) 4.11lat V2 L1 L0latsna V2 L1 L0inj V2 L1 L0?
5.00????
5.01????
5.10????
5.11????
6.00????
6.01????
(B0) 6.10f0 = (int8_t) B0; f1 = (int8_t) B0; f2 = (int8_t) B0; f3 = (int8_t) B0;
(B0,L1) 6.11L1 = (int8_t) B0;???
(C+S0) 7.00; C=000f0 &lt;<= S0;f1 <<= S0;f2 <<= S0;f3 <<= S0;
(C+S0) 7.00; C=001f0 >>>= S0;f1 >>>= S0;f2 >>>= S0;f3 >>>= S0;
(C+S0) 7.00; C=010f0 >>= S0;f1 >>= S0;f2 >>= S0;f3 >>= S0;
(C+S0) 7.00; C=011flag = (0 == ((1 << S0) & f0));flag = (0 == ((1 << S0) & f1));flag = (0 == ((1 << S0) & f2));flag = (0 == ((1 << S0) & f3));
(C+S0) 7.00; C=100flag = (0 != ((1 << S0) & f0));flag = (0 != ((1 << S0) & f1));flag = (0 != ((1 << S0) & f2));flag = (0 != ((1 << S0) & f3));
(C+S0) 7.00; C=101f5 += 4 * S0;???
(C+S0) 7.00; C=110f5 -= 4 * S0; ???
(C+S0) 7.00; C=111f0 = *(f5 + 4 * S0);f1 = *(f5 + 4 * S0);f2 = *(f5 + 4 * S0);f3 = *(f5 + 4 * S0);
(C+S0,L1) 7.01; C=000L1 <<= S0;???
(C+S0,L1) 7.01; C=001L1 >>>= S0;???
(C+S0,L1) 7.01; C=010L1 >>= S0;???
(C+S0,L1) 7.01; C=011flag = (0 == ((1 << S0) & L1));???
(C+S0,L1) 7.01; C=100flag = (0 != ((1 << S0) & L1));???
(C+S0,V1) 7.01; C=101*(f5 + 4 * S0) = f0;*(f5 + 4 * S0) = f1;*(f5 + 4 * S0) = f2;*(f5 + 4 * S0) = f3;
(C+S0,V1) 7.01; C=110*(f5 + 4 * S0) = V1;???
(C+S0,B1) 7.01; C=111????
(V0,V1) 7.1flag = (uint32_t)V0 >= (uint32_t)V1;flag = (uint32_t)V0 < (uint32_t)V1;flag = (V0 == V1);flag = (V0 != V1);flag = (int32_t)V0 >= (int32_t)V1;flag = (int32_t)V0 < (int32_t)V1;flag = (0 == (V0 & V1));flag = (0 != (V0 & V1));
(V0) 8.00f0 += V0;f1 += V0;f2 += V0;f3 += V0;
(V0) 8.01f0 -= V0;f1 -= V0;f2 -= V0;f3 -= V0;
(V0) 8.10lat V0 f0 f0lat V0 f1 f1lat V0 f2 f2lat V0 f3 f3
(V0) 8.11f0 &= V0;f1 &= V0;f2 &= V0;f3 &= V0;
(V0) 9.00f0 |= V0;f1 |= V0;f2 |= V0;f3 |= V0;
(V0) 9.01f0 = ~(f0 ^ V0);f1 = ~(f1 ^ V0);f2 = ~(f2 ^ V0);f3 = ~(f3 ^ V0);
(V0) 9.10f0 <<= V0;f1 <<= V0;f2 <<= V0;f3 <<= V0
(V0) 9.11f0 >>>= V0;f1 >>>= V0;f2 >>>= V0;f3 >>>= V0
(V0) A.00f0 >>= V0;f1 >>= V0;f2 >>= V0;f3 >>= V0
(V0) A.01f0 = V0;f1 = V0;f2 = V0;f3 = V0;
(V0) A.10if (flag) f0 = V0;if (flag) f1 = V0;if (flag) f2 = V0;if (flag) f3 = V0;
(L0) A.11(f0, L0) = (L0, f0);(f1, L0) = (L0, f1);(f2, L0) = (L0, f2);(f3, L0) = (L0, f3);
(V0) B.00f0 = V0 >> 24;f1 = V0 >> 24;f2 = V0 >> 24;f3 = V0 >> 24;
(V0) B.01f0 = (f0 & 0x00ffffff) | (V0 << 24);f1 = (f1 & 0x00ffffff) | (V0 << 24);f2 = (f2 & 0x00ffffff) | (V0 << 24);f3 = (f3 & 0x00ffffff) | (V0 << 24);
(V0) B.10f0 = V0 >> 16;f1 = V0 >> 16;f2 = V0 >> 16;f3 = V0 >> 16;
(V0) B.11f0 = (f0 & 0x0000ffff) | (V0 << 16);f1 = (f1 & 0x0000ffff) | (V0 << 16);f2 = (f2 & 0x0000ffff) | (V0 << 16);f3 = (f3 & 0x0000ffff) | (V0 << 16);
(V0,L1) C.00L1 += V0;???
(V0,L1) C.01L1 -= V0;???
(V0,L1) C.10lat V0 L1 L1???
(V0,L1) C.11L1 &= V0;???
(V0,L1) D.00L1 |= V0;???
(V0,L1) D.01L1 = ~(L1 ^ V0);???
(V0,L1) D.10L1 <<= V0;???
(V0,L1) D.11L1 >>>= V0;???
(V0,L1) E.00L1 >>= V0;???
(V0,L1) E.01L1 = V0;???
(V0,L1) E.10if (flag) L1 = V0;???
(L0,L1) E.11(L1, L0) = (L0, L1);???
(V0,L1) F.00L1 = V0 >> 24;???
(V0,L1) F.01L1 = (L1 & 0x00ffffff) | (V0 << 24);???
(V0,L1) F.10L1 = V0 >> 16;???
(V0,L1) F.11L1 = (L1 & 0x0000ffff) | (V0 << 16);???