前回に引き続き、Zen2の方向分岐予測器の仕組みを明らかにしていきます。
分岐履歴に使われる情報
分岐元アドレス
前回と同様のアセンブリを用いて、分岐命令のアドレスのみを変化させていき、パターン長1～48の予測を当てることができるかを調べていきます。 分岐命令のアドレスを変えるためには、NOPを詰める位置（分岐命令の上に置くか下に置くか）を変化させました。
その結果、以下のことが分かります。
- 分岐命令のアドレスが2n+1の時と2n+2の場合は正答パターンがほぼ一致
- 2n+1と2n+2の間で繰上りが発生することもある
- 上位ビットが同じで下位ビットが01と10の組でパターンが一致するということではなさそう
このことから、以下の仮説を立てます。
- 分岐命令のアドレス＋1が分岐履歴に使われる。この時、アドレスの下位1ビットは使われない。
分岐先アドレス
前回の調査の結果、パターン長が9以上で常に予測失敗する命令配置があることを知っています。
このようなことが発生するのは、jne L1の生成する分岐履歴情報とjne L0の生成する分岐履歴情報が完全に一致しているからとみて間違いないでしょう。
これを利用すると、どのような分岐履歴情報を生成しているかを調べることができそうです。
具体的には、jne L0の生成する分岐履歴情報を固定し、jne L1の生成する分岐履歴情報がそれと一致する場合を探索することで、法則性を見つけていきます。
以下では、手を抜いてパターン長が9の時だけ調べます。 以下のアセンブリを実行したとき、分岐予測が十分多く外れるNOPを詰める量を調べてみます。
.text .intel_syntax noprefix .globl main main: mov rcx, 20000000 mov rax, 1 .p2align 6, 0x90 L0: （nopを何個か） sub rax, 1 jne L1 mov rax, 9 （nopを何個か） L1: （nopを何個か） sub rcx, 1 jne L0 ret
すると、NOPを詰める量が例えば以下の値の時、分岐予測が十分多く外れることが分かります。
| 上 | 中 | 下 | jne L1分岐元 |
jne L1分岐先 |
jne L0分岐元 |
jne L0分岐先 |
|---|---|---|---|---|---|---|
| 3 | 9 | 2 | 0x400547 | 0x400559 | 0x40055f | 0x400540 |
| 3 | 9 | 3 | 0x400547 | 0x400559 | 0x400560 | 0x400540 |
| 3 | 8 | 4 | 0x400547 | 0x400558 | 0x400560 | 0x400540 |
| 3 | 7 | 5 | 0x400547 | 0x400557 | 0x400560 | 0x400540 |
| 3 | 6 | 6 | 0x400547 | 0x400556 | 0x400560 | 0x400540 |
| 3 | 5 | 7 | 0x400547 | 0x400555 | 0x400560 | 0x400540 |
| 3 | 4 | 8 | 0x400547 | 0x400554 | 0x400560 | 0x400540 |
| 3 | 3 | 9 | 0x400547 | 0x400553 | 0x400560 | 0x400540 |
この結果から、以下の結論を得ます。
- 分岐先アドレスの情報は分岐履歴に使われない
方向分岐しか存在しない場合、実行経路を一意に特定するためには分岐先アドレスは不要（間接分岐がある場合は分岐先アドレスも必要）であり、このような分岐履歴の持ち方になっていることは理解できます。
分岐元アドレスのハッシュ関数の特定
パターン長が9以上で常に予測失敗する命令配置をまとめてみました。
| 上 | 中 | 下 | jne L1分岐元 |
jne L0分岐元 |
(A&~1)^(B&~1) | 備考 |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0x400545 | 0x400552 | 0x14 | 前回発見 |
| 3 | 7 | 0 | 0x400547 | 0x40055b | 0x14 | |
| 3 | 8 | 0 | 0x400547 | 0x40055c | 0x14 | |
| 4 | 6 | 0 | 0x400548 | 0x40055b | 0x14 | |
| 4 | 7 | 0 | 0x400548 | 0x40055c | 0x14 | |
| 5 | 7 | 0 | 0x400549 | 0x40055d | 0x14 | |
| 5 | 8 | 0 | 0x400549 | 0x40055e | 0x14 | |
| 7 | 0 | 0 | 0x40054b | 0x400558 | 0x14 | 前回発見 |
| 9 | 0 | 0 | 0x40054d | 0x40055a | 0x14 | 前回発見 |
| 3 | 9 | 2 | 0x400547 | 0x40055f | 0x28 | |
| 3 | 9 | 3 | 0x400547 | 0x400560 | 0x28 | |
| 3 | 0 | 7 | 0x400547 | 0x40055b | 0x14 | |
| 3 | 0 | 11 | 0x400547 | 0x40055f | 0x28 | |
| 3 | 0 | 31 | 0x400547 | 0x400573 | 0x3c | |
| 3 | 0 | 123 | 0x400547 | 0x4005cf | 0x9c | jne L0は6Byte命令 |
| 3 | 0 | 143 | 0x400547 | 0x4005e3 | 0xa0 | jne L0は6Byte命令 |
| 3 | 0 | 163 | 0x400547 | 0x4005f7 | 0xb4 | jne L0は6Byte命令 |
| 58 | 0 | 58 | 0x40057e | 0x4005c5 | 0xb4 | jne L0は6Byte命令 |
| 58 | 0 | 78 | 0x40057e | 0x4005d9 | 0xa0 | jne L0は6Byte命令 |
| 58 | 0 | 82 | 0x40057e | 0x4005dd | 0x9c | jne L0は6Byte命令 |
| 58 | 0 | 102 | 0x40057e | 0x4005f1 | 0x88 | jne L0は6Byte命令 |
| 60 | 0 | 6 | 0x400580 | 0x400593 | 0x14 | jne L0は6Byte命令 |
| 60 | 0 | 26 | 0x400580 | 0x4005a7 | 0x28 | jne L0は6Byte命令 |
| 60 | 0 | 46 | 0x400580 | 0x4005bb | 0x3c | jne L0は6Byte命令 |
| 60 | 0 | 1142 | 0x400580 | 0x400a03 | 0xf88 | jne L0は6Byte命令 |
| 60 | 0 | 1162 | 0x400580 | 0x400a17 | 0xf9c | jne L0は6Byte命令 |
| 60 | 1142 | 0 | 0x400580 | 0x400a07 | 0xf88 | 共に6Byte命令 |
| 60 | 1154 | 0 | 0x400580 | 0x400a13 | 0xf9c | 共に6Byte命令 |
| 60 | 2542 | 0 | 0x400580 | 0x400f7f | 0xa00 | 共に6Byte命令 |
| 60 | 2798 | 0 | 0x400580 | 0x40107f | 0x1500 | 共に6Byte命令 |
| 60 | 3118 | 0 | 0x400580 | 0x4011bf | 0x1440 | 共に6Byte命令 |
| 60 | 3886 | 0 | 0x400580 | 0x4014bf | 0x1140 | 共に6Byte命令 |
| 60 | 3958 | 0 | 0x400580 | 0x401507 | 0x1088 | 共に6Byte命令 |
| 60 | 3982 | 0 | 0x400580 | 0x40151f | 0x10a0 | 共に6Byte命令 |
| 60 | 4078 | 0 | 0x400580 | 0x40157f | 0x1000 | 共に6Byte命令 |
| 60 | 4090 | 0 | 0x400580 | 0x40158b | 0x1014 | 共に6Byte命令 |
| 60 | 4118 | 0 | 0x400580 | 0x4015a7 | 0x1028 | 共に6Byte命令 |
| 60 | 8174 | 0 | 0x400580 | 0x40257f | 0x2000 | 共に6Byte命令 |
| 60 | 16366 | 0 | 0x400580 | 0x40457f | 0x4000 | 共に6Byte命令 |
| 60 | 32750 | 0 | 0x400580 | 0x40857f | 0x8000 | 共に6Byte命令 |
まず「分岐命令のアドレス＋1が分岐履歴に使われる」の謎が解明できました。 先ほどまでの実験に使っている分岐命令は全て2Byteのものだったので＋1になっていましたが、正確には「分岐命令の最後のバイトのアドレスが使われる」ということのようです。
また、アドレスのXORで見た差分が0x14の時に分岐履歴情報が区別できないことから、アドレスの2bit目（Addr[2]）とアドレスの4bit目（Addr[4]）はXORされた形でのみ分岐履歴上に存在することが分かります。 同様に、以下のような組み合わせでXORされていることが分かります。
| (A&~1)^(B&~1) | ||
|---|---|---|
| 0x14 | Addr[2] | Addr[4] |
| 0x28 | Addr[3] | Addr[5] |
| 0x88 | Addr[3] | Addr[7] |
| 0xa0 | Addr[5] | Addr[7] |
| 0x140 | Addr[6] | Addr[8] |
| 0x440 | Addr[6] | Addr[10] |
| 0x500 | Addr[8] | Addr[10] |
| 0xa00 | Addr[9] | Addr[11] |
したがって、ハッシュ関数は以下のようになっており、分岐元アドレスの情報を5bitに圧縮していることが分かります。
- Hash_0(Addr) = Addr[1]
- Hash_1(Addr) = Addr[2]^Addr[4]
- Hash_2(Addr) = Addr[3]^Addr[5]^Addr[7]
- Hash_3(Addr) = Addr[6]^Addr[8]^Addr[10]
- Hash_4(Addr) = Addr[9]^Addr[11]
まとめ
- 分岐履歴の構築には、分岐命令の最後のバイトのアドレスが使用される
- 分岐履歴の構築には、分岐先のアドレスは使用されない
- 分岐命令の最後のバイトのアドレスの最下位ビットは使われない
- 全ての分岐命令は2Byte以上なので、最下位ビットのみ異なる分岐命令の組は通常存在しない
- 分岐命令の最後のバイトのアドレスの2の位～2048の位（合計11ビット）がハッシュ関数に通されて5ビットに圧縮されて使用される
