-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpentopt.htm
2700 lines (2131 loc) · 213 KB
/
pentopt.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<HTML>
<HEAD>
<TITLE>HOW TO OPTIMIZE FOR THE PENTIUM PROCESSOR</TITLE>
</HEAD>
<BODY>
<H1>HOW TO OPTIMIZE FOR THE PENTIUM PROCESSOR (In Japanese)</H1>
Original (in English): <A HREF="http://announce.com/agner/assem/assem.html">http://announce.com/agner/assem/assem.html</A><BR>
Copyright (c) 1996, 1997 by Agner Fog. Last modified 1997-08-19.</BR>
<P>このページは、Agner Fogさんによる同名のマニュアルの、藤波順久による日本語訳です。原文(英語)の著作権はAgner Fogさんにあります。また、日本語訳中の「私」とは、Agner Fogさんのことです。原文は<BR>
<A HREF="http://announce.com/agner/assem/assem.html">http://announce.com/agner/assem/assem.html</A><BR>
を参照してください。
<P>このページは、現在更新中であり、原文の古い版(1997-03-16)に基づいている章がいくつかあります。
<H2>目次</H2>
<OL>
<LI><A HREF="#INTRO">はじめに</A>
<LI><A HREF="#LITERATURE">文献</A>
<LI><A HREF="#DEBUGGING">デバッグと確認</A>
<LI><A HREF="#MEMORY">メモリモデル</A>
<LI><A HREF="#ALIGNMENT">アラインメント</A>
<LI><A HREF="#CACHE">キャッシュ</A>
<LI><A HREF="#AGI">番地生成インターロック</A>(PPlain and PMMX)
<LI><A HREF="#PAIRING">整数命令のペアリング</A>(PPlain and PMMX)
<LI><A HREF="#FIRST">初回の実行と、繰り返し実行</A>
<LI><A HREF="#IMPERFECT">不完全なペアリング</A>(PPlain and PMMX)
<LI><A HREF="#SPLITTING">複雑な命令を単純な命令に分割</A>(PPlain and PMMX)
<LI><A HREF="#JUMPS">ジャンプとブランチ</A>
<LI><A HREF="#PREFIXES">プリフィクス</A>
<LI><A HREF="#REDUCING">コードサイズの縮小</A>
<LI><A HREF="#SCHEDULING">浮動小数点コードのスケジューリング</A>(PPlain and PMMX)
<LI><A HREF="#LOOPS">ループの最適化</A>(PPlain and PMMX)
<LI><A HREF="#SPECIAL">特殊な命令について</A>
<LI><A HREF="#INTEGER-FLOATING">整数命令を使った浮動小数点演算</A>
<LI><A HREF="#FLOATING-INTEGER">浮動小数点命令を使った整数演算</A>
<LI><A HREF="#LIST-INTEGER">整数命令のリスト</A>(PPlain and PMMX)
<LI><A HREF="#LIST-FLOATING">浮動小数点命令のリスト</A>(PPlain and PMMX)
<LI><A HREF="#MMX">MMX命令</A>(PMMX)
<LI><A HREF="#TESTING">コードの速度のテスト</A>
<LI>(準備中)<A HREF="#PPRO">Pentium ProとPentium IIプロセッサ</A>
<LI>(準備中)<A HREF="#COMPARISON">いろいろなマイクロプロセッサの比較</A>
</OL>
<HR>
<H2><A NAME="INTRO">1. はじめに</A></H2>
このマニュアルは、最適化されたアセンブリ言語のコードの書き方について、詳述する。特に、Pentium(R)ファミリ・マイクロプロセッサに焦点をあてる。
<P>このマニュアルは他の情報源に比べて理解しやすく正確で、他に見られない細かい事項をたくさん含んでいる。この情報を使えば、あなたは多くの場合に、あるコード片が正確に何クロックサイクルかかるのか計算することができるようになる。
<P>このマニュアルでは次のようなバージョンのPentiumプロセッサについて議論する。
<PRE>略称 名前
------------------------------------------------
PPlain plain old Pentium (without MMX)
PMMX Pentium with MMX
PPro Pentium Pro
PII Pentium II
------------------------------------------------
</PRE>
<P>このマニュアルの情報は、私自身の調査と試験に基づいており、さまざまな人たちから受け取った情報で補足されている。このマニュアルのために追加情報を私に送ってくれた人々に感謝したい。これまでの私の調査はPPlainとPMMXしかカバーしていない。PProとPIIについては簡単に記述されているだけである。
<P>アセンブリ言語でのプログラミングは、高級言語よりはるかに難しい。バグを生成するのは容易であり、その発見はたいへん困難である。ここで警告である! 読者は既にアセンブリ言語の経験があると仮定する。もしそうでなければ、複雑な最適化を始める前に、どうかアセンブリ言語に関する本を何か読んで、プログラミングの経験を得てほしい。
<P>Pentiumチップのハードウェア設計は、一般的な最適化方法を使ったというよりはむしろ、いくつかのよく使われる命令やその組合せに特に最適化された、多くの特徴を持っている。その結果、ソフトウェアをこの設計向きに最適化するのはかなり複雑で、多くの例外があるが、相当な性能向上が可能かもしれない。
<P>コードをアセンブリ言語に変換する前に、使っているアルゴリズムが最適であることを確認してほしい。コード片をアセンブラコードに直すよりアルゴリズムを改良したほうがずっとよい結果になることがしばしばある。
<P>次に、プログラムの決定的に重要な部分を同定しなければならない。しばしば、99%以上のCPU時間がプログラムの最も内側のループで消費されている。この場合、そのループだけを最適化し、それ以外はすべて高級言語のままにしておくべきである。アセンブラプログラマの中には、プログラムの誤った部分を最適化するのにエネルギーを浪費し、努力の主な効果が、プログラムのデバッグや保守を難しくしただけという人もいる!
<P>もしプログラムの決定的に重要な部分がどこか明らかでなければ、プロファイラを使ってみつけるとよい。もしボトルネックがディスクアクセスであるとわかったら、アセンブリプログラミングに行くのではなくて、ディスクアクセスをシーケンシャルに行うようにプログラムを変更して、ディスクのキャッシングを改良するとよい。もしボトルネックがグラフィクスの出力なら、グラフィクスの手続きを呼ぶ回数を減らす方法を探すとよい。
<P>高級言語のコンパイラのいくつかは比較的よいPentium向けの最適化を提供しており、手でさらに最適化することは、最も決定的なコード片に対して(または娯楽のため)以外はその努力に見合わないかもしれない。
<P>どうか私にプログラミングの質問を送らないでほしい。私はあなたの宿題をするつもりはない。
<P>ナノ秒狩りの幸運を祈る!
<P>PS. 私は故意に「optimization」を間違って綴っている。なぜなら、「optimation」のほうが発音に最適だからである。
<HR>
<H2><A NAME="LITERATURE">2. 文献</A></H2>
たくさんの有用な文献が、インテルのWWWサイトから無料でダウンロード可能であり、また印刷物やCD-ROMとして得ることができる。
<P>文献のURLは頻繁に変わるので、ここで紹介しない。<BR>
<A HREF="http://www.intel.com/sites/developer/search.htm">http://www.intel.com/sites/developer/search.htm</A>の検索機能を使うか、<BR>
<A HREF="http://announce.com/agner/assem">http://announce.com/agner/assem</A>からリンクをたどることで、必要な文書を見つけることができる。
<P>いくつかの文書は.PDF形式である。.PDFファイルを見たり印刷したりするソフトウェアを持っていなければ、<A HREF="http://www.adobe.com">www.adobe.com</A>からAcrobatファイルリーダをダウンロードすればよい。
<P>特定のアプリケーションを最適化するためにMMX命令を使うことは、アプリケーションノートのいくつかで述べられている。MMX命令セットはいろいろなマニュアルやチュートリアルで述べられている。
<P>インテル以外にも有用な情報源がたくさんある。これらはニュースグループ<A HREF="news://comp.lang.asm.x86">comp.lang.asm.x86</A>のFAQにリストされている。シェアウェアのエディタASMEDITには、すべての命令コードなどをカバーするオンラインヘルプがある。ASMEDITは<BR>
<A HREF="http://www.inf.tu-dresden.de/~ok3/asmedit.html">http://www.inf.tu-dresden.de/~ok3/asmedit.html</A>から得られる。
<P>インタネットのリソースについては<BR>
<A HREF="http://announce.com/agner/assem/">http://announce.com/agner/assem/</A>からリンクをたどってほしい。
<HR>
<H2><A NAME="DEBUGGING">3. デバッグと確認</A></H2>
アセンブリコードをデバッグするのは、あなたがすでに気づいているかもしれないように、たいそう困難でいらいらする。私は次のようにすることを勧めたい。まず最適化したいコード片を高級言語のサブルーチンとして書くことから始め、次に、そのサブルーチンをすっかりテストするテストプログラムを書く。テストプログラムはすべての分岐や特別な場合を必ず通るようにする。
<P>高級言語で書いたサブルーチンがテストプログラムと共に動くようになったら、そのコードをアセンブリ言語に直す準備ができたことになる。インラインアセンブラを使ってもよいし、サブルーチン全体をアセンブリ言語で書いて、リンクしてもよい。後者を選んだ場合、高級言語のコードを直接アセンブリ言語に変換できるコンパイラを使うことを勧める。これであなたは確実に、関数呼び出し法を正しくできる。たいていのC++コンパイラはこれができる。(最近のバージョンのマイクロソフトvisual C++はできない。バージョン9以前のCL.EXEを使うとよい)。
<P>関数の呼び出しの方法と名前の変換はたいそう複雑である。多数の異なる呼び出し規約があり、コンパイラのブランドが異なればこの点で互換性がない。アセンブリ言語のサブルーチンをC++から呼び出そうとしているなら、整合性と互換性の点から最もよい方法は、関数を extern "C" と _cdecl で宣言することである。アセンブリ言語のコードは、アンダースコア(_)が先頭についた関数名を持ち、外部名の大文字小文字を区別する(オプション -mx)ようにアセンブルされるはずである。引数はスタックに逆順に積まれ、最初の引数が最下位の番地に来る。引数は呼び出された関数ではなく呼び出し側がスタックから取り除く。戻り値はレジスタeaxまたはst(0)にはいる。関数は、eax,ecx,edx(16ビットモードではax,bx,cx,dx,es)を除いて、使うレジスタをすべて保存し、戻る前に復元する。もし、名前の変換や別の呼び出し規約が必要なら、アセンブリ言語のコードを正しくするために、高級言語をアセンブリ言語に変換できるコンパイラを使わなければならない。
<P>これで最適化を始めることができる。変更をするたびにコードをテストプログラム上で走らせて、正しく動くか見るべきである。
<P>すべてのバージョンに番号をつけて保存せよ。そうすれば、テストプログラムではつかまらなかった(間違った番地に書き込んでしまうような)エラーを見つけた場合に戻ってテストし直せる。
<P>プログラムの最も決定的な部分の速度を<A HREF="#TESTING">23章</A>で述べる方法でテストせよ。コードが期待に比べてはっきり遅ければ、最もありそうな理由は、キャッシュミス(<A HREF="#CACHE">6章</A>)、オペランドのミスアラインメント(<A HREF="#ALIGNMENT">5章</A>)、最初の実行のペナルティー(<A HREF="#FIRST">9章</A>)、分岐予測ミス(<A HREF="#JUMPS">12章</A>)である。
<HR>
<H2><A NAME="MEMORY">4. メモリモデル</A></H2>
Pentiumは32ビットコード向けを第一に設計されており、16ビットコードでの性能は劣る。コードとデータをセグメント分けすることも性能をはっきり劣化させるので、あなたは32ビットフラットモードを選ぶべきであり、このモードをサポートするオペレーティングシステム(例えばWindows 95、OS/2、あるいは32ビットDOSエクステンダ)を選ぶべきである。このマニュアルにでてくるコードの例は、特に指定がなければ32ビットフラットメモリモデルを仮定している。
<HR>
<H2><A NAME="ALIGNMENT">5. アラインメント</A></H2>
RAM上のすべてのデータは下のように2、4、または8で割り切れる番地にアラインするべきである。
<PRE> アラインメント アラインメント
オペランドサイズ PPlainとPMMX PProとPII
--------------------------------------------------
1 (byte) 1 1
2 (word) 番地 MOD 4 < 3 2
4 (dword) 4 4
6 (fword) 4 8
8 (qword) 8 8
10 (tbyte) 8 16
--------------------------------------------------
</PRE>
ミスアラインされたデータのアクセスは最低3クロックサイクル余計にかかる。キャッシュラインの境界をまたぐと、ペナルティーはさらに高くなる。
<P>PPlainとPMMXで走らせるときにはコードをアラインする必要はないが、PProとPIIで最適な性能を得るために、サブルーチンやループの入口を16でアラインしてもよい。
<HR>
<H2><A NAME="CACHE">6. キャッシュ</A></H2>
PPlainとPProはコード用に8KB、データ用に8KBのオンチップキャッシュ(レベル1キャッシュ)を持っている。PMMXとPIIはコード用に16KB、データ用に16KB持っている。レベル1キャッシュにあるデータはちょうど1クロックサイクルで読み書きできる。一方、キャッシュミスするとたくさんのクロックサイクルを消費する。だから、キャッシュを最も有効に使うためにそれがどう働くか理解することは重要である。
<P>データキャッシュはそれぞれ32バイトのライン256個または512個から成る。キャッシュされていないデータ項目を読むたびに、プロセッサはキャッシュライン全体をメモリから読む。キャッシュラインは常に32で割り切れる物理番地にアラインされている。32で割り切れる番地から1バイト読んでしまえば、続く31バイトはほとんど追加コストなしで読み書きできる。互いに近く使われるデータ項目を32バイトのアラインされたメモリブロックにまとめることで、この利点を活用できる。もし、例えば二つの配列をアクセスするループがあるなら、二つの配列をインターリーブして一つの配列にすればよい。そうすると、いっしょに使われるデータをいっしょに格納できる。
<P>もし配列や他のデータ構造のサイズが32バイトの倍数なら、なるべく32でアラインするべきである。
<P>キャッシュはset-associativeである。その意味は、キャッシュラインには、任意のメモリ番地を割り当てられるわけではないということである。各キャッシュラインには7ビットのセット値があって、物理RAM番地のビット5から11とマッチする(ビット0～4はキャッシュラインの32バイトを定義する)。PPlainとPProは、128セット値のそれぞれについて二つのキャッシュラインを持つため、どんなRAM番地も割り当てられる可能性のあるキャッシュラインは二つである。PMMXとPIIは四つある。
<P>この結果、キャッシュは、番地のビット5～11の値が同じなら、たかだか二つまたは四つの異なるデータブロックしか保持できない。二つの番地が同じセット値を持つかどうかは次の方法で決められる。各番地の下5ビットを0にし、32で割り切れる値を得よ。二つの切り捨てた番地の差が4096(=1000H)の倍数なら、二つの番地は同じセット値を持つ。
<P>このことを次のコード片を使って例示しよう。ここでESIは32で割り切れる番地を保持しているとする。
<PRE>AGAIN: MOV EAX, [ESI]
MOV EBX, [ESI + 13*4096 + 4]
MOV ECX, [ESI + 20*4096 + 28]
DEC EDX
JNZ AGAIN
</PRE>
ここで使われている三つの番地は、切り捨てた番地の差が4096の倍数なので、同じセット値を持つ。このループはPPlainとPProではたいへん悲惨なふるまいをする。ECXを読むとき、適当なセット値を持つ空きキャッシュラインがないので、プロセッサは二つのキャッシュラインのうち最近使われてないほう(EAXのために使われたもの)を採用し、そのキャッシュラインを [ESI + 20*4096] から [ESI + 20*4096 + 31] までのデータで満たしてECXを読む。次に、EAXを読むとき、EAXのための値を保持していたキャッシュラインは今は破棄されていることに気づく。それで、最も近くに使われたのでないキャッシュラインを採用し、それはEBXの値を保持しているものである。以下同様である。これではキャッシュミスしか起きず、ループは60クロックサイクルとかかかる。もし第3行を変更して
<PRE> MOV ECX, [ESI + 20*4096 + 32]
</PRE>
とすれば、32バイト境界を越えたので、最初の2行と同じセット値ではなくなり、3つの番地のそれぞれに問題なくキャッシュラインを割り当てられる。ループは今は3クロックサイクルしかかからない(初回を除いて)。たいへん考慮に値する改良である!
<P>データの番地が同じキャッシュ値かどうか決めるのは、特に異なるセグメントに散らばっているときは、たいへん難しいかもしれない。この種の問題を避ける最もよい方法は、プログラムの決定的に重要な部分で使われるすべてのデータをキャッシュより大きくない一つの連続したブロックか、キャッシュのサイズの半分以下の二つのブロック(例えば静的データで一つのブロック、スタック上のデータで一つのブロック)に入れることである。これでキャッシュラインはきっと最適に使われるようになるだろう。
<P>コードの決定的に重要な部分が大きなデータ構造やランダムなデータ番地をアクセスするなら、すべてのよく使う変数(カウンタ、ポインタ、制御変数など)を一つの連続した4kバイト以下のブロックに入れて、ランダムなデータをアクセスするための、キャッシュラインの完全なセットがあるようにしたいかもしれない。たぶんサブルーチンの引数や戻り番地のためのスタックスペースは結局必要なので、最もよいのは、よく使う静的データをスタック上の動的変数にコピーし、変更があったものは決定的に重要なループの外でコピーし戻すことである。
<P>レベル1キャッシュにないデータ項目を読むことは、キャッシュライン全体をレベル2キャッシュから満たすことになる。これはだいたい200ns(つまり100MHzシステムでは20クロック、200MHzシステムでは40クロック)かかるが、最初に読みたかったバイトは50～100nsで利用可能になる。データ項目がレベル2キャッシュにもない場合、200～300nsの遅れが生ずる。DRAMのページ境界をまたぐと、この遅れは多少長くなる(DRAMのページサイズは、4MBの72ピンRAMモジュールで1KB、16MBモジュールで2KBである)。
<P>レベル1キャッシュにない番地に書いたときには、PPlainとPMMXでは、その値はそのままレベル2キャッシュかRAMに行く(レベル2キャッシュがどう設定されているかによる)。これはだいたい100nsかかる。もし8回かそれ以上同じ32バイトメモリブロックに書き、そこから読むことがなく、ブロックがレベル1キャッシュにないならば、そのブロックから最初にダミーの読み込みをしてキャッシュラインにロードするほうが有利かもしれない。同じブロックへの引き続く書き込みはすべて、キャッシュに行き、それは1クロックサイクルしかかからない。これは、書き込みミスで常にキャッシュラインをロードする、PProやPIIでは必要ない。PPlainとPMMXでは、同じ番地に繰り返し書き、その間に読まないと、ときどき小さなペナルティーがある。
<P>書き込みミスを減らす別の方法は、整数のレジスタを使って4バイトを一度に書く代わりに、QWORDオペランドのFILD / FISTPを使って8バイトを一度に書くことである。遅いFILDとFISTP命令の余分なコストは書き込みが半分ですむことで補償される。しかし、この方法が有利なのはPPlainとPMMXだけであり、しかも転送先がレベル1キャッシュにない場合に限る。この方法は<A HREF="#FLOATING-INTEGER">19章</A>で説明する。PProまたはPIIを持っているなら、8バイトを一度に移動するには、もちろん浮動小数点命令ではなくMMX命令を使えばよい。
<P>PPlainは二つの書き込みバッファを持っており、PMMXは四つ、PProとPIIは八つである。PMMXでは、キャッシュされていないメモリに対して最大四つまでの未完了の書き込みがあっても、引き続く命令を遅らせることはない。
<P>スタック領域はキャッシュにあることがたいへん多いので、一時データはスタックに格納すると便利である。しかしながらDWORDサイズのスタックにQWORDデータを格納したり、WORDサイズのスタックにDWORDデータを格納する場合は、アラインメントの問題の可能性があることを認識するべきである。
<P>もし二つのデータ構造の寿命の範囲が重ならない場合、キャッシュの効率を上げるために同じRAM領域を使うかもしれない。これは一時変数をスタックに割り付けるという日常習慣と整合性がある。
<P>一時データをレジスタに格納することはもちろんもっと効率的である。レジスタは希少なリソースなので、スタックのデータをアクセスするのに[EBP]ではなく[ESP]を使い、EBPを他の目的のために空けたいかもしれない。ESPの値はPUSHやPOPをするたびに変化することを忘れないでほしい(16ビットWindowsでは、ESPを使うことはできない。タイマ割り込みがコード中の予測できない場所でESPの上位ワードを変更する)。
<P>コード用には別のキャッシュがあり、それはデータキャッシュと似ている。コードキャッシュのサイズは、PPlainとPProで8KB、PMMXとPIIで16KBである。コードの決定的に重要な部分(最も内側のループ)がキャッシュに収まることは重要である。よく使われるコード片やいっしょに使われるルーチンはなるべく互いに近くに格納するべきである。めったに使われない分岐や手続きはコードの下のほうかどこか別の場所に離しておくべきである。
<HR>
<H2><A NAME="AGI">7. 番地生成インターロック(AGI) (PPlain and PMMX)</A></H2>
メモリをアクセスする命令で必要な番地の計算には1クロックサイクルかかる。普通はこの計算は、先立つ命令や命令ペアが実行されている間に、パイプラインの別のステージで行われる。しかしもし、番地が一つ前のクロックサイクルで実行された命令の結果に依存する場合は、番地の計算のために1クロックサイクル余分に待たなければならない。これはAGIストールと呼ばれる。
<PRE>例:
ADD EBX,4 / MOV EAX,[EBX] ; AGIストール
</PRE>
この例のストールは ADD EBX,4 と MOV EAX,[EBX] の間に何か他の命令をはさむか、コードを次のように書き換えることで取り除ける。
<PRE>MOV EAX,[EBX+4] / ADD EBX,4
</PRE>
<P>ESPを暗黙に番地指定に使う、PUSH、POP、CALL、RETのような命令でも、MOV、ADD、SUBのような命令で先立つクロックサイクル中にESPが変更された場合は、AGIストールが発生する。PPlainとPMMXはスタック操作の後のESPの値を予想する特別な回路を持つため、PUSH、POP、CALLでESPを変更した後のAGIによる遅れはない。RETの後のAGIストールは、ESPに足す即値を持つ場合に限ってある。
<PRE>例:
ADD ESP,4 / POP ESI ; AGIストール
POP EAX / POP ESI ; ストールなし、ペア
MOV ESP,EBP / RET ; AGIストール
CALL L1 / L1: MOV EAX,[ESP+8] ; ストールなし
RET / POP EAX ; ストールなし
RET 8 / POP EAX ; AGIストール
</PRE>
<P>LEA命令も、先立つクロックサイクルで変更された、ベースまたはインデックスレジスタを使う場合、AGIストールを受ける。
<PRE>例:
INC ESI / LEA EAX,[EBX+4*ESI] ; AGIストール
</PRE>
<P>PProとPIIには、AGIストールはない。
<HR>
<H2><A NAME="PAIRING">8. 整数命令のペアリング(PPlain and PMMX)</A></H2>
PPlainとPMMXは、命令の実行のための二つのパイプライン、UパイプとVパイプを持つ。ある条件の元で、二つの命令を同時に、一つはUパイプで、もう一つはVパイプで実行できる。これはほとんど実行速度を倍にする。そのため、命令を並べ変えてペアにするのは有益である。
次の命令はどちらのパイプでもペアにできる。
<PRE>MOV レジスタ、メモリ、または即値を、レジスタ、またはメモリへ
PUSH レジスタ、または即値
POP レジスタ
LEA, NOP
INC, DEC, ADD, SUB, CMP, AND, OR, XOR
TESTのいくつかの形式(<A HREF="#SPECIAL-3">段落17.3</A>を参照)
</PRE>
次の命令はUパイプでのみペアにできる。
<PRE>ADC, SBB
SHR, SAR, SHL, SAL 回数は即値
ROR, ROL, RCR, RCL 回数は即値の1
</PRE>
次の命令はどちらのパイプでも実行できるが、ペアにできるのはVパイプの時だけである。
<PRE>near call, shortまたはnearジャンプ, shortまたはnear条件ジャンプ
</PRE>
他のすべての整数命令はUパイプでのみ実行可能であり、ペアにできない。
<P>連続する二つの命令は次の条件が満たされたときペアにできる。
<DL COMPACT>
<DT>8.1
<DD>最初の命令はUパイプでペアにでき、二番目の命令はVパイプでペアにできる。
<DT>8.2
<DD>二番目の命令は最初の命令が書くレジスタを読み書きできない。
<PRE>例:
MOV EAX, EBX / MOV ECX, EAX ; 書き込み後読み込み、ペアにできない
MOV EAX, 1 / MOV EAX, 2 ; 書き込み後書き込み、ペアにできない
MOV EBX, EAX / MOV EAX, 2 ; 読み込み後書き込み、ペアOK
MOV EBX, EAX / MOV ECX, EAX ; 読み込み後読み込み、ペアOK
MOV EBX, EAX / INC EAX ; 読み込み後読み書き、ペアOK
</PRE>
<DT>8.3
<DD>規則8.2で部分レジスタはレジスタ全体として扱われる。
<PRE>例:
MOV AL, BL / MOV AH, 0 ; 同じレジスタの異なる部分への書き込み
; ペアにできない
</PRE>
<DT>8.4
<DD>規則8.2と8.3にかかわらず、フラグレジスタの一部に書き込む二つの命令はペアにできる。
<PRE>例:
SHR EAX,4 / INC EBX ; ペアOK
</PRE>
<DT>8.5
<DD>規則8.2にかかわらず、フラグに書き込む命令と条件ジャンプはペアにできる。
<PRE>例:
CMP EAX, 2 / JA LabelBigger ; ペアOK
</PRE>
<DT>8.6
<DD>次の命令の組合せは、両方がスタックポインタを変更するという事実にもかかわらず、ペアにできる。
<PRE> PUSH + PUSH, PUSH + CALL, POP + POP
</PRE>
<DT><A NAME="PAIRING-7">8.7</A>
<DD>プリフィックスつきの命令のペアリングには制限がある。プリフィックスにはいくつかの種類がある。
<UL>
<LI>デフォルトでないセグメントを番地指定する命令は、セグメントプリフィックスを持つ。
<LI>32ビットモードで16ビットデータを使ったり、16ビットモードで32ビットデータを使ったりする命令は、オペランドサイズプリフィックスを持つ。
<LI>16ビットモードで32ビットのベースまたはインデックスレジスタを使う命令は、アドレスサイズプリフィックスを持つ。
<LI>繰り返しストリング命令は、リピートプリフィックスを持つ。
<LI>ロックされる命令は、ロックプリフィックスを持つ。
<LI>8086プロセッサに実装されていなかった命令の多くは、2バイトのオペコードを持ち、その最初のバイトは0FHである。0FHのバイトは、PPlainではプリフィックスとしてふるまうが、他の版ではそうではない。0FHプリフィックスを持つ主な命令は、MOVZX, MOVSX, PUSH FS, POP FS, PUSH GS, POP GS, LFS, LGS, LSS, SETcc, BT, BTC, BTR, BTS, BSF, BSR, SHLD, SHRD, それから、2または3オペランド(即値でない)のIMULである。
</UL>
<P>PPlainでは、プリフィックスつき命令は、near条件ジャンプを除いてUパイプでのみ実行可能である。
<P>PMMXでは、オペランドサイズ、アドレスサイズ、0FHのプリフィックスつき命令は、どちらのパイプでも実行可能であるが、一方、セグメント、リピート、ロックプリフィックスつき命令はUパイプでしか実行できない。
<DT>8.8
<DD>変位と即値の両方を持つ命令は、PPlainではペアにできず、PMMXではUパイプでのみ実行可能である。
<PRE> MOV DWORD PTR DS:[1000], 0 ; ペアにできないかUパイプのみ
CMP BYTE PTR [EBX+8], 1 ; ペアにできないかUパイプのみ
CMP BYTE PTR [EBX], 1 ; ペアにできる
CMP BYTE PTR [EBX+8], AL ; ペアにできる
</PRE>
(PMMXにおける、変位と即値の両方を持つ命令の別の問題は、そのような命令は7バイトより長くなるかもしれないことで、それは、<A HREF="#PREFIXES">13章</A>で説明するように、1クロックサイクルで1命令しかデコードできないことを意味する。)
<DT>8.9
<DD>両方の命令があらかじめロードされ、デコードされている。これは<A HREF="#FIRST">9章</A>で説明されている。
<DT><A NAME="PAIRING-10">8.10</A>
<DD>PMMXのMMX命令には特別なペアリング規則がある。
<UL>
<LI>MMXのシフト、パック、アンパック命令はどちらのパイプでも実行できるが、他のMMXシフト、パック、アンパック命令とペアにできない。
<LI>MMX乗算命令はどちらのパイプでも実行できるが、他のMMX乗算命令とペアにできない。MMX乗算命令は3クロックサイクルかかり、後ろの2クロックサイクルは、浮動小数点命令と同様に、引き続く命令とオーバーラップできる(<A HREF="#SCHEDULING">15章</A>参照)。
<LI>メモリや整数レジスタをアクセスするMMX命令はUパイプでのみ実行でき、MMXでない命令とペアにできない。
</UL>
</DL>
<HR>
<H2><A NAME="FIRST">9. 初回の実行と繰り返し実行</A></H2>
コード片を最初に実行するときは、繰り返すときに比べて、普通はたいへん時間がかかる。理由は次の通りである。
<DL COMPACT>
<DT>9.1
<DD>コードをRAMからキャッシュにロードするのは、実行するより時間がかかる。
<DT><A NAME="FIRST-2">9.2</A>
<DD>ある場合にはコードのデコードがボトルネックになる。命令の長さを決めるのに1クロックサイクルかかるなら、プロセッサは二番目の命令がどこから始まるかわからないので、クロックサイクルあたり二つの命令をデコードすることはできない。Pentiumはこの問題を、キャッシュに残っている命令の長さを前回実行したときから覚えておくことで、解決している。この結果、PPlainとPMMXでは、二つの命令の前者の長さが1バイトの場合を除いて、初回には命令をペアにできない。
<DT>9.3
<DD>初回の実行では、ジャンプ命令はブランチターゲットバッファに入っていないので、正しく予測されないことが多い。<A HREF="#JUMPS">12章</A>を参照のこと。
<DT>9.4
<DD>コードがアクセスするどのデータもキャッシュにロードしなければならず、それは命令の実行よりずっと時間がかかるかもしれない。コードが繰り返されると、データはキャッシュにあることが多い。
</DL>
<P>この四つの理由のため、ループ中のコード片が最初に実行されるときには、次回以降より一般にずっと時間がかかる。
<P>コードキャッシュに収まらないようなループがあると、キャッシュから実行されることはないので、9.1と9.2のペナルティーを毎回に受けることになる。だから、ループを再構成してキャッシュに収まるように務めるべきである。
<P>ループ中にジャンプやブランチが多い場合、9.3のペナルティーを毎回に受けるかもしれない。
<P>同様に、データキャッシュに取って大きすぎるデータをループが繰り返しアクセスする場合、毎回キャッシュミスのペナルティーを受ける。
<HR>
<H2><A NAME="IMPERFECT">10. 不完全なペアリング</A></H2>
ペアの二つの命令が同時に実行されなかったり、時間的に一部だけオーバーラップしたりする状況がある。しかし、最初の命令がUパイプで、二番目の命令がVパイプで実行されるので、これも依然としてペアとして考慮するべきである。不完全なペアの両方の命令の実行が完了しないと、引き続く命令の実行は始まらない。
<P>不完全なペアリングは次のような場合に起きる。
<DL COMPACT>
<DT>10.1
<DD>二番目の命令がAGIストールを受ける場合(<A HREF="#AGI">7章</A>参照)。
<DT>10.2
<DD>二つの命令はメモリの同じDWORDを同時にアクセスできない。次の例はESIが4で割り切れると仮定している。
<PRE> MOV AL, [ESI] / MOV BL, [ESI+1]
</PRE>
二つのオペランドは同じDWORD内にあるので、同時には実行できない。このペアは2クロックサイクルかかる。
<PRE> MOV AL, [ESI+3] / MOV BL, [ESI+4]
</PRE>
ここでは二つのオペランドはDWORD境界の両側にあるので、完全にペアになれ、1クロックサイクルしかかからない。
<DT><A NAME="IMPERFECT-3">10.3</A>
<DD>規則10.2は二つの番地のビット2～4が同じである場合に拡張される(キャッシュバンク競合)。DWORDの番地に対しては、これは二つの番地の差が32で割り切れてはならないことを意味する。
<PRE>例:
MOV [ESI], EAX / MOV [ESI+32000], EBX ; 不完全なペアリング
MOV [ESI], EAX / MOV [ESI+32004], EBX ; 完全なペアリング
</PRE>
</DL>
<P>ペアにできる整数命令で、メモリにアクセスしないものは、予測ミスしたジャンプを除いて、実行に1クロックサイクルかかる。メモリから、またはメモリへのMOV命令は、データ領域がキャッシュにあって適当にアラインされていれば、やはり1クロックサイクルしかかからない。スケールされたインデックスレジスタのような複雑な番地指定モードの使用に速度のペナルティーはない。
<P>ペアにできる整数命令で、メモリから読み、何らかの計算をし、結果をレジスタやフラグに格納するものは、2クロックサイクルかかる。
<P>ペアにできる整数命令で、メモリから読み、何らかの計算をし、結果をメモリに書き戻すものは、3クロックサイクルかかる(read/modify/write命令)。
<DL COMPACT>
<DT>10.4
<DD>もし、read/modify/write命令がread/modify命令またはread/modify/write命令とペアになると、それは不完全なペアリングである。
<P>消費するクロックサイクル数は次の表のようになる。
<PRE> | 二番目の命令
| MOV or read/ read/modify/
最初の命令 | register only modify write
----------------------|----------------------------------------------
MOV or register only | 1 2 3
read/modify | 2 2 3
read/modify/write | 3 4 5
----------------------|-----------------------------------------------
</PRE>
<PRE>例:
ADD [mem1], EAX / ADD EBX, [mem2] ; 4クロックサイクル
ADD EBX, [mem2] / ADD [mem1], EAX ; 3クロックサイクル
</PRE>
<DT>10.5
<DD>ペアになった二つの命令が両方とも、キャッシュミス、ミスアラインメント、または分岐予測ミスによって余分な時間がかかるとき、そのペアは各命令単独よりは時間がかかるが、二つの和よりは少ない。
<DT>10.6
<DD>ペアにできる浮動小数点命令にFXCH命令が続いているものは、その次の命令が浮動小数点命令でなければ、不完全なペアリングとなる。
</DL>
<P>不完全なペアリングを避けるためには、どの命令がUパイプに、どの命令がVパイプに行くかを知らなければならない。これは、次のようにすればわかる。コードを逆方向に見て行って、ペアにできない、一方のパイプでしかペアにできない、または<A HREF="#PAIRING">8章</A>の規則のどれかのためにペアにできない命令をさがせばよい。
<P>不完全なペアリングはたいてい、命令の順序を変更することで避けられる。
<PRE>例:
L1: MOV EAX,[ESI]
MOV EBX,[ESI]
INC ECX
</PRE>
ここで二つのMOV命令は同じメモリ位置をアクセスするので、不完全なペアを形成する。この命令列は3クロックサイクルかかる。命令の順番を変えて、 INC ECX がMOV命令のどちらかとペアになるようにすれば、改良できる。
<PRE>L2: MOV EAX,OFFSET A
XOR EBX,EBX
INC EBX
MOV ECX,[EAX]
JMP L1
</PRE>
ペア INC EBX / MOV ECX,[EAX] は、後者の命令にAGIストールがあるため、不完全である。この命令列は4クロックかかる。NOPまたは他の命令を挿入して、 MOV ECX,[EAX] が代わりに JMP L1 とペアになるようにすれば、命令列は3クロックしかかからない。
<H3><A NAME="IMPERFECT-7">10.7</A></H3>
<P>次の例は16ビットモードで、SPが4で割り切れると仮定する。
<PRE>L3: PUSH AX
PUSH BX
PUSH CX
PUSH DX
CALL FUNC
</PRE>
ここでPUSH命令は二つの不完全なペアを形成する。なぜなら、各ペアの両方のオペランドがメモリの同じDWORDに行くからである。 PUSH BX は PUSH CX と完全なペアになれたかもしれない(DWORD境界の両側に行くから)のに、すでに PUSH AX とペアになってしまっているので、そうはならない。命令列は、従って、5クロックサイクルかかる。もしNOPか他の命令を挿入して、 PUSH BX が PUSH CX と、 PUSH DX が CALL FUNC とペアになるようにすれば、命令列は3クロックしかかからない。問題を解決する別の方法は、SPが必ず4で割り切れないようにすることである。16ビットモードでSPが4で割り切れるかどうか知るのは困難なので、この問題を避ける最もよい方法は、32ビットモードを使うことである。
<HR>
<H2><A NAME="SPLITTING">11. 複雑な命令を単純な命令に分割(PPlain and PMMX)</A></H2>
read/modifyまたはread/modify/write命令を分割して、ペアリングを改良してもよい。
<PRE>例:
ADD [mem1],EAX / ADD [mem2],EBX ; 5クロックサイクル
</PRE>
このコードは3クロックサイクルしかかからない命令列に分割できる。
<PRE>MOV ECX,[mem1] / MOV EDX,[mem2]
ADD ECX,EAX / ADD EDX,EBX
MOV [mem1],ECX / MOV [mem2],EDX
</PRE>
<P>同様に、ペアにできない命令を、ペアにできる命令に分割してもよい。
<PRE>PUSH [mem1] / PUSH [mem2] ; ペアにできない
</PRE>
これを分割して
<PRE>MOV EAX,[mem1] / MOV EBX,[mem2] / PUSH EAX / PUSH EBX ; すべてペアになる
</PRE>
<P>ペアにできない命令で、より単純なペアにできる命令に分割できる、他の例:
<PRE>CDQ を分割して MOV EDX,EAX / SAR EDX,31
NOT EAX の代わりに XOR EAX,-1
NEG EAX を分割して XOR EAX,-1 / INC EAX
MOVZX EAX,BYTE PTR [mem] を分割して XOR EAX,EAX / MOV AL,BYTE PTR [mem]
JECXZ を分割して TEST ECX,ECX / JZ
LOOP を分割して DEC ECX / JNZ
XLAT の代わりに MOV AL,[EBX+EAX]
</PRE>
<P>もし命令を分割することで速度が改良されなければ、コードサイズを縮小するために、複雑な、またはペアにできない命令をそのままにしてもよい。命令の分割は、PProとPIIでは必要ない。
<HR>
<H2><A NAME="JUMPS">12. ジャンプとブランチ</A></H2>
Pentiumファミリ・プロセッサは、ジャンプの先がどこか、そして条件ジャンプが分岐するか通り抜けるかを予測しようとする。予測が正しければ、ジャンプが実行される前に、引き続く命令をパイプラインにロードして、デコードを始めることで、考慮に値するべき時間を節約できる。予測が間違っていることがわかれば、パイプラインをフラッシュしなければならず、パイプラインの長さによって決まるペナルティーとなる。
<P>予測は、各分岐またはジャンプ命令の履歴を格納して、各命令の以前の実行履歴から予測を行う、 Branch Target Buffer (BTB)に基づいて行われる。BTBは、新しいエントリが擬似ランダム置換方式で割り当てられるようなset-associativeキャッシュと似た構成になっている。
<P>コードを最適化するとき、予測ミスのペナルティーの数を最小にすることが重要である。これには、分岐予測がどのように働くかよく理解することが要求される。
<P>分岐予測機構についてはインテルのマニュアルにも、また他のどこでも正確には書かれていない。だから私は、たいへん詳細な記述をここで与える。この情報は私自身の調査に基づいている(PPlainでは Karki Jitendra Bahadur の助けもあった)。
<P>以下で私は、「制御移行命令」という言葉を、IP(instruction pointer)を変更するどんな命令についても、条件つき、無条件、直接、間接、near、far、ジャンプ、コール、リターンを含めて、使うことにする。これらすべての命令が予測を使う。
<H3><A NAME="JUMPS-1-1">12.1.1 PPlainの分岐予測</A></H3>
PPlainの分岐予測機構は、他の3プロセッサとだいぶ異なる。この題目についてのインテルの文書や他の場所で見られる情報は、一直線に人を誤解させるもので、そのような文書の忠告に従うと、準最適なコードになってしまう。
<P>PPlainは branch target buffer (BTB)を持ち、それは256個までのジャンプ命令の情報を保存できる。BTBはウェイあたり64エントリの4ウェイset-associativeキャッシュと似た構成になっている。これの意味するところは、BTBは同じセット値を持つエントリをたった4つしか保持できないということである。データキャッシュと違って、BTBは擬似ランダム置換アルゴリズムを使っており、最近使われてないほうの、同じセット値のエントリを置き換えるわけでは必ずしもない。セット値がどのように計算されるかは後で述べる。各BTBエントリはジャンプ先の番地と、4つの異なる値をとる予測の状態を格納する。
<PRE>状態0: 強 分岐しない
状態1: 弱 分岐しない
状態2: 弱 分岐する
状態3: 強 分岐する
</PRE>
分岐命令は状態2と3ではジャンプすると、0と1では通り抜けると予測される。状態遷移は2ビットカウンタのように働き、分岐すると状態は1増え、通り抜けると1減る。カウンタはラップアラウンドせず飽和するので、0を超えて減ったり、3を超えて増えたりしない。理想的には、これはまずまずよい予測になるだろう。なぜなら、予測が変化する前に分岐命令は、よくする動作から2回はずれなければならないからである。
<P>しかし、状態0が「使われていないBTBエントリ」も意味するという事実により、この機構には妥協がある。だから、状態0のBTBエントリは、BTBエントリがないのと同じである。分岐命令はBTBエントリを持たない場合通り抜けると予測されるので、これは筋が通っている。ほとんど分岐しない分岐命令はほとんどの時間、BTBエントリの場所を取らないので、これはBTBの使用効率を改良する。
<P>ここで、もしジャンプする命令がBTBエントリを持たなければ、新しいBTBエントリが生成され、これはいつでも状態3にセットされる。これは、状態0から状態1に行くのは不可能であることを意味する(後に議論する非常に特別な場合を除く)。状態0からは、分岐した場合は状態3にしか行けない。分岐が通り抜けた場合、BTBにはいらないままになる。
<P>これは深刻な、設計の欠陥である。状態0のエントリを捨て、新しいエントリをいつでも状態3にセットすることで設計者は、無条件ジャンプやよく分岐する条件ジャンプの初回のペナルティーを少なくすることを優先し、これが機構の背後にある基本アイデアに対して重大な妥協をしていて、最も内側の小さいループの性能を落としていることを無視したようだ。この欠陥の帰結は、たいてい通り抜ける分岐命令は、たいてい分岐する分岐命令の3倍も予測ミスがあるということである。
<P>この非対称性を考慮に入れて、分岐命令は分岐するほうが多くなるように構成するとよい。
<P>例えばこのif-then-else構造を考えてみよう。
<PRE> TEST EAX,EAX
JZ A
<枝1>
JMP E
A: <枝2>
E:
</PRE>
もし枝1が枝2より多く実行され、枝2が続けて2回実行されることがめったになければ、二つの枝を交換して、分岐命令が通り抜けるよりジャンプするほうが多いようにすることで、分岐予測ミスを3分の1にまで減らすことができる。
<PRE> TEST EAX,EAX
JNZ A
<枝2>
JMP E
A: <枝1>
E:
</PRE>
(これは、インテルのマニュアルやチュートリにある勧めとは<STRONG>逆</STRONG>である。分岐予測の非対称性に気づいていないようである。しかし、後者の例が優れていることを示すのはたやすい。)
<P>だが、最もよく実行される枝を最初に置く理由もあるかもしれない。
<OL>
<LI>めったに実行されない枝をコードの最後に置くことで、コードキャッシュの使用効率を上げることができる。
<LI>めったに分岐しない分岐命令はたいていはBTBにはいらずにいて、BTBの使用効率を上げる可能性がある。
<LI>他の分岐命令によってBTBから追い出されてしまった分岐命令は、分岐しないと予測される。
<LI>分岐予測の非対称性は、PPlainにだけある。
</OL>
<P>これらの考慮は、しかしながら、小さく決定的に重要なループに関してはウェイトは小さいので、やはり、分布の偏った枝の構成は、分岐命令が分岐するほうが多いようにすることを勧める。ただし、枝2の実行頻度があまりに小さくて、予測ミスが問題にならないときを除く。
<P>同様に、ループの条件テストの分岐命令は、この例のように、なるべく最後に来るように構成するべきである。
<PRE> MOV ECX, [N]
L: MOV [EDI],EAX
ADD EDI,4
DEC ECX
JNZ L
</PRE>
もしNが大きければ、JNZ命令は分岐するほうが多く、続けて2回通り抜けることはない。
<P>1回おきに分岐が起きる状況を考えてみよう。最初にジャンプしたとき、BTBエントリは状態3に行き、その後状態2と3に交互に行くだろう。これはいつもジャンプすると予測され、50%の予測ミスとなる。今これがこの規則的なパターンからはずれ、1回余計に通り抜けたとしよう。ジャンプのパターンは、0がとばない、1がとぶの意味だとして、
<PRE>01010100101010101010101
^
</PRE>
増えた通り抜けは^で示してある。このできごとの後では、BTBエントリは状態1と2に交互に行き、100%の予測ミスとなる。この不運なモードはまた0101パターンからはずれるまで続く。これがこの分岐予測機構で最も悪い場合である。
<H3>12.1.2 BTBは先読みをしている(PPlain)</H3>
BTB機構は、命令を単独ではなくペアで数えているので、BTBのエントリがどこに格納されるかを解析するには、命令がどのようにペアになるのか知らなければならない。どの制御移行命令のBTBエントリも、その前の命令ペアのUパイプの命令の番地につく(ペアにならない命令も一つのペアと数える)。
<PRE>例:
SHR EAX,1
MOV EBX,[ESI]
CMP EAX,EBX
JB L
</PRE>
ここで、SHRはMOVと、CMPはJBとペアになる。従って、 JB L についてのBTBエントリは、 SHR EAX,1 命令の番地につく。このBTBエントリに出会ったとき、それが状態2か3なら、PentiumはBTBエントリから分岐先の番地を読み、ラベルL以降の命令をパイプラインにロードする。これは分岐命令がデコードされる前に起きるので、PentiumはこれをするときBTBの情報だけに頼っている。
<P>命令は、初回に実行されるときにはめったにペアにならないことを、ここで思い出すかもしれない(<A HREF="#FIRST-2">段落9.2</A>参照)。上の命令がペアにならなければ、BTBエントリはCMP命令の番地につくであろう。そして、次回の実行で命令がペアになるときには、このエントリは誤りになるだろう。しかしながら、多くの場合、PPlainは十分賢く、ペアになる機会を利用しなかったものがあるときには、BTBエントリを作らないので、2回目の実行まではBTBエントリはできず、だから、3回目の実行までは予測はされないだろう(一つおきに1バイト命令があるような、稀な場合では、2番目の実行では無効になるようなBTBエントリが最初の実行でできるかもしれないが、それならエントリのついている命令はVパイプに行くので、それは無視されてペナルティーを与えない。BTBエントリが読まれるのは、それがUパイプの命令の番地についているときだけである)。
<P>BTBエントリは、それがつく番地のビット0～5に等しいセット値で見分けられる。ビット6～31はタグとしてBTBに格納される。64の倍数だけ離れた番地は同じセット値を持つ。同じセット値を持つBTBエントリは4つまでしか作れない。制御移行命令のセット値が競合するかどうかチェックしたいなら、前の命令ペアのUパイプ命令のアドレスのビット0～5を比べなければならない。これはたいへんあきあきするし、誰かがやっていると聞いたこともない。この仕事をあなたの代わりにやってくれるような、利用可能なツールはない。
<H3><A NAME="JUMPS-1-3">12.1.3 連続する分岐(PPlain)</A></H3>
ジャンプが予測ミスすると、パイプラインはフラッシュされる。もし、次に実行される命令ペアも制御移行命令を含んでいると、PPlainはジャンプ先をロードしないのである。なぜなら、パイプラインのフラッシュ中に新しいジャンプ先をロードできないからである。この結果、二番目の制御移行命令はBTBエントリの状態に関係なく、通り抜けると予測される。それで、二番目の制御移行命令も分岐するなら、さらにペナルティーを受ける。二番目の制御移行命令のBTBエントリの状態は、それでも正しく更新される。もしジャンプする制御移行命令の長い鎖があって、鎖の最初のジャンプが予測ミスしたら、パイプラインは毎回フラッシュされ、ジャンプしない命令ペアに出会うまでずっと予測ミスしか起きない。これの最も極端な場合は、自分自身にジャンプするループであり、繰り返し毎に予測ミスのペナルティーを受ける。
<P>連続する制御移行命令の問題はこれだけではない。別の問題は、BTBエントリと、それが属する制御移行命令の間に、もう一つの分岐命令を置けることである。最初の分岐命令がどこか別の場所にジャンプすると、奇妙なことが起きるかもしれない。この例を考えてみよう。
<PRE> SHR EAX,1
MOV EBX,[ESI]
CMP EAX,EBX
JB L1
JMP L2
L1: MOV EAX,EBX
INC EBX
</PRE>
JB L1 が通り抜けるとき、 CMP EAX,EBX の番地につけられた、 JMP L2 のためのBTBエントリができる。しかし、後で JB L1 が分岐したとき何が起きるだろうか。 JMP L2 のためのBTBエントリが読まれるとき、プロセッサは次の命令ペアが制御移行命令を含んでいないことを知らないので、実際には命令ペア MOV EAX,EBX / INC EBX がL2にジャンプすると予測する。ジャンプでない命令がジャンプすると予測したときのペナルティーは3クロックサイクルである。 JMP L2 のためのBTBエントリは、何かジャンプしないものに適用されたために、その状態が1減らされる。もしL1に行き続けるなら、 JMP L2 のためのBTBエントリは状態1、そして0まで減らされて、次に JMP L2 が実行されるまでこの問題は姿を消すだろう。
<P>ジャンプでない命令をジャンプすると予測するペナルティーは、L1へのジャンプが予測されたときのみ発生する。 JB L1 が予測とはずれてジャンプする場合は、パイプラインがフラッシュされ、間違ったジャンプ先のL2はロードされないので、ジャンプでない命令をジャンプすると予測したペナルティーは見えないが、 JMP L2 のBTBエントリの状態はやはり減らされる。
<P>今、 INC EBX 命令を別の制御移行命令で置き換えてみよう。この三番目の制御移行命令は JMP L2 命令と同じBTBエントリを使い、誤ったジャンプ先を予測するペナルティーを受ける可能性がある(たまたまジャンプ先が同じL2である場合を除いて)。
<P>要約すると、連続するジャンプは、次のような問題につながる可能性がある。
<UL>
<LI>先行する予測ミスした制御移行命令によりパイプラインがフラッシュされているときに、ジャンプ先のロードに失敗。
<LI>ジャンプでない命令に誤って適用され、ジャンプすると予測してしまうBTBエントリ。
<LI>上の結果、誤って適用されたBTBエントリはその状態を減らされ、後でそれの属するジャンプの予測ミスにつながるかもしれない。無条件ジャンプであっても、この理由により通り抜けると予測され得る。
<LI>二つの制御移行命令が同じBTBエントリを共有し、誤ったジャンプ先の予測につながる。
</UL>
この混乱はすべて、たくさんのペナルティーを与えるので、うまく予測できない制御移行命令のすぐ後またはジャンプ先に、ジャンプを含む命令ペアを置くことは、絶対に避けるべきである。
<P>そろそろこれを説明する例を挙げるころである。
<PRE> CALL P
TEST EAX,EAX
JZ L2
L1: MOV [EDI],EBX
ADD EDI,4
DEC EAX
JNZ L1
L2: CALL P
</PRE>
これはなかなかよい、普通のコード片に見える。関数呼び出しと、回数が0のときは迂回されるループと、別の関数呼び出しである。あなたはこのプログラムにいくつの問題を見つけ出せるだろうか。
<P>まず、関数Pが交互に二つの異なる場所から呼ばれることに注意しよう。これはPからの戻り先が毎回変わることを意味する。その結果、Pからのリターンはいつも予測ミスする。
<P>今、EAXが0だと仮定しよう。すると、予測ミスしたPからのリターンはパイプラインフラッシュを起こしているので、L2へのジャンプはそのジャンプ先をロードしない。次に、 JZ L2 がパイプラインフラッシュを起こしたので、二番目の CALL P も分岐先のロードに失敗する。これが、最初のジャンプが予測ミスしたために、連続したジャンプの鎖が繰り返しパイプラインフラッシュを引き起こす状況である。 JZ L2 のためのBTBエントリはPのリターン命令の番地に格納される。このBTBエントリは二番目の CALL P の後に来るものが何であっても誤って適用されるが、予測ミスした二番目のリターンによってパイプラインがフラッシュされるので、ペナルティーを与えない。
<P>今度は、次回、EAXが0以外の値だったら何が起きるか見てみよう。フラッシュによって JZ L2 はいつでも通り抜けると予想される。二番目の CALL P は TEST EAX,EAX の番地にBTBエントリを持つ。このエントリはMOV/ADDのペアに誤って適用され、Pにジャンプすると予測するだろう。これはフラッシュを起こし、 JNZ L1 がそのジャンプ先をロードするのを妨げる。もし以前ここに来たことがあるのなら、二番目の CALL P は DEC EAX の番地にもう一つのBTBエントリを持つ。ループの2,3回目の繰り返しにおいて、このエントリもMOV/ADDのペアに誤って適用される(状態が1か0に減らされるまで)。2回目の繰り返しでは、 JNZ L1 によるフラッシュが誤ったジャンプ先のロードを止めるので、これはペナルティーを起こさないが、3回目の繰り返しではペナルティーを起こす。引き続くループの繰り返しではペナルティーはないが、出るときに、 JNZ L1 が予測ミスする。CALL P のためのBTBエントリが、何回か誤って適用されたために、すでに破壊されているという事実がなければ、これによるフラッシュは、今度は CALL P がジャンプ先をロードするのを妨げただろう。
<P>すべての連続するジャンプを分けるためにいくつかNOPを入れることで、このコードを改良できる。
<PRE> CALL P
TEST EAX,EAX
NOP
JZ L2
L1: MOV [EDI],EBX
ADD EDI,4
DEC EAX
JNZ L1
L2: NOP
NOP
CALL P
</PRE>
余分なNOPは2クロックサイクルかかるが、ずっと多くを節約する。さらに、 JZ L2 はUパイプに移動し、予測ミスしたときのペナルティーが4から3に減っている。残る唯一の問題は、Pからのリターンがいつも予測ミスすることである。この問題はPの呼び出しをインラインマクロで置き換えることによってのみ解決できる(もしコードキャッシュが十分なら)。
<P>この例から学ぶべき教訓は、いつも注意深く、連続するジャンプを探して、NOPをいくつか挿入すると時間を節約できるかどうか考えるべきであるということである。ループの出口やいろいろな場所から呼ばれる手続きからのリターンなど、予測ミスが避けられない状況を特に認識するべきである。NOPの代わりに挿入する有効なものがあるのなら、もちろんそうするべきである。
<P>多方向分岐(case文)は、分岐命令の木か、ジャンプする番地のリストで実装されるだろう。分岐命令の木を使うことを選ぶのなら、連続する分岐を分けるためにNOPかほかの命令を含めなければならない。PPlainでは従って、ジャンプする番地のリストがよい解かもしれない。ジャンプする番地のリストはデータセグメントに置くべきである。決してデータをコードセグメントに置くな!
<H3>12.1.4 複数のBTBエントリ(PPlain)</H3>
二つの制御移行命令は同じBTBエントリを共有し得るが、一方、一つの制御移行命令が、異なる場所からジャンプしてくるか、ペアリングが変化した場合に、複数のBTBエントリを持つこともあり得る。
<PRE>例:
JZ L1
MOV EAX,1
L1: MOV EBX,2
MOV ECX,3
JC L2
</PRE>
もし、 JZ L1 が通り抜けると、 MOV EAX,1 は MOV EBX,2 とペアになり、 MOV ECX,3 は JC L2 とペアになる。 JC L2 のためのBTBエントリは MOV EAX,1 の番地につくことになる。 JZ L1 が分岐したときには、 MOV EBX,2 は MOV ECX,3 とペアになり、 JC L2 はペアにならず、BTBエントリは MOV EBX,2 につくことになる。このように JC L2 には二つのBTBエントリができる。最初のエントリはゼロフラグが降りているとき、もう一つは立っているときに使われる。これは実は好都合かもしれない。なぜなら、二つの分岐命令に相関があるなら、二番目の分岐命令の予測可能性を向上させるからである。例えば、このコード列の前にCMP命令があると仮定しよう。すると、ゼロフラグとキャリーフラグが両方同時に立つことは決してないと確信できる。ゼロフラグが立っていると、 JC L2 は必ず通り抜けるので、 MOV EBX,2 に JC L2 のための二番目のBTBエントリはつかず、 JZ L1 が分岐したときは JC L2 の予測ミスはない。このトリックを利用できる状況は、しかしながら稀である。というのは、L1をキャリーフラグを全くテストしない別の枝に持って行ったほうがましだからである。
<H3>12.1.5 きついループ(PPlain)</H3>
小さなループでは、同じBTBエントリを短い間隔で繰り返しアクセスするものである。これは決してストールを起こさない。BTBエントリが更新されるのを待つのではなく、PPlainは何らかの方法でパイプラインをバイパスし、前のジャンプの結果の状態を、それがBTBに書かれる前に取得する。この機構は利用者にはほとんど透過であるが、ある場合におかしな効果がある。分岐予測が状態0から状態3ではなく、状態1に遷移するのが、状態0がまだBTBに書かれていないなら、見られる。ループがたった4命令ペアしかないと、これが起きる。2命令ペアしかないループではときどき、連続した2回の繰り返しで状態0がBTBから出て行かないかもしれない。そのような小さなループでは、前のではなく2回前の繰り返しの結果の状態を予測が使うということが、稀な場合に起きる。これらのおかしな効果は、通常は性能に負の効果をもたらさない。
<H3>12.2 PMMX、PPro、PIIの分岐予測</H3>
<H3>12.2.1 BTBの構成(PMMX, PPro and PII)</H3>
PMMXの branch target buffer (BTB)は、256個のエントリを持ち、それは16ウェイ×16セットの構成になっている。各エントリは、それの属する制御移行命令の最後のバイトの番地のビット2～31で特定される。ビット2～5がセットを定義し、ビット6～31がタグとしてBTBに格納される。64バイト離れた制御移行命令どうしは同じセット値を持つので、時には互いに相手をBTBから押し出したりする。セット毎に16のウェイがあるので、これはそんなには起きないだろう。
<P>PProとPIIの branch target buffer は512個のエントリを持つ。これがどのようなセットで構成されているかの情報を私は持っていない。
<P>PProとPIIはどんな制御移行命令でもそれが最初に実行されたときにBTBエントリを割り当てる。PMMXはそれが最初にジャンプしたときに割り当てる。PMMXでは、決してジャンプしない分岐命令はBTBには入らずにいる。そして一度ジャンプしたら、もう決して再びジャンプしなくても、それはBTBにとどまるのである。
<P>エントリは、同じセット値を持つ別の制御移行命令がBTBエントリを必要としたときに、BTBから押し出されることもある。
<H3>12.2.2 予測ミスのペナルティー(PMMX, PPro and PII)</H3>
PMMXでは、条件ジャンプの予測ミスのペナルティーは、Uパイプで4クロック、Vパイプで実行されたときは5クロックである。他のすべての制御移行命令では、4クロックである。
<P>PProとPIIでは、長いパイプラインのせいで、予測ミスのペナルティーは非常に高い。予測ミスは普通、10～20クロックサイクルかかる。そのため、PProとPIIで走らせるときには、予測のうまくいかない分岐を意識しておくことは非常に重要である。
<H3>12.2.3 条件ジャンプのパターン認識(PMMX, PPro and PII)</H3>
これらのプロセッサは、例えば、4回おきに分岐して残りの3回は通り抜けるような分岐命令を正しく予測できる、進んだパターン認識機構を持っている。実は、周期が高々5までのジャンプする/しないのどんな繰り返しパターンをも、そしてそれより長い周期の多くのパターンを予測できる。
<P>このメカニズムは、 T.-Y. Yeh と Y. N. Patt の発明した、いわゆる「2レベル適応型分岐予測スキーム」である。これはPPlainについて上で説明したのと同種の(ただし非対称性の欠陥はない)2ビットカウンタに基づいている。カウンタはジャンプが分岐したときは増加し、分岐しなかったときは減少する。3より上、0より下にラップアラウンドはしない。対応するカウンタが状態2か3のときは、分岐命令は分岐すると予測され、状態0か1のときは、通り抜けると予測される。今、各BTBエントリに対してこのようなカウンタを16個持つことで、劇的な改良が得られる。その分岐命令の最後の4回の実行の履歴に基づいて16個のカウンタのうちの一つが選ばれる。例えば、分岐命令が一度ジャンプし、3回通り抜けたらなら、履歴ビットとして1000(1=ジャンプした、0=ジャンプしなかった)を持つ。これはカウンタ8(1000は2進数としてみると8)を次回の予測として使い、その後カウンタ8を更新する。
<P>もし列1000の後にくるのがいつも1なら、カウンタ8はすぐに一番上の状態(状態3)に達し、1000の後はいつも1が来るだろうと予測する。予測が変化するには、このパターンから2回はずれる必要がある。繰り返しパターン100010001000は、カウンタ8を状態3に、カウンタ1,2,4を状態0にし、他の12個のカウンタは使わない。
<H3>12.2.4 完全に予測できるパターン(PMMX, PPro and PII)</H3>
以下は完全に予測できる繰り返しの分岐パターンのリストである。
<PRE>周期 パターン
-----------------------------------------------------------------------------
1 - 5 すべて
6 000011, 000101, 000111, 001011
7 0000101, 0000111, 0001011
8 00001011, 00001111, 00010011, 00010111, 00101101
9 000010011, 000010111, 000100111, 000101101
10 0000100111, 0000101101, 0000101111, 0000110111, 0001010011,
0001011101
11 00001001111, 00001010011, 00001011101, 00010100111
12 000010100111, 000010111101, 000011010111, 000100110111,
000100111011
13 0000100110111, 0000100111011, 0000101001111
14 00001001101111, 00001001111011, 00010011010111, 00010011101011
00010110011101, 00010110100111
15 000010011010111, 000010011101011, 000010100110111, 000010100111011
000010110011101, 000010110100111, 000010111010011, 000011010010111
16 0000100110101111, 0000100111101011, 0000101100111101,
0000101101001111
-----------------------------------------------------------------------------
</PRE>
<P>この表を読むとき、次のことを知っているべきである。あるパターンが正しく予測できるなら、同じパターンを反転したもの(後ろ向きに読んだもの)も、また、同じパターンの全ビットを反転したものも正しく予測できる。
<PRE>例:
表にはこのパターンがある: 0001011
パターンを反転すると: 1101000
全ビットを反転すると: 1110100
両方同時にやると: 0010111
</PRE>
これら四つのパターンはすべて認識できる。パターンを一つ左に回転すると、0010110になる。これはもちろん新しいパターンではなく、同じパターンの相がずれたものである。表の中のあるパターンから反転したり、ビット反転したり、回転したりして導出できるパターンもすべて認識できる。簡潔にするために、これらはリストされていない。(リストはPMMXで実験的に得られた)。
<P>BTBエントリが割り当てられた後、パターン認識機構が規則的な繰り返しパターンを学習するのに2周期かかる。学習期間での予測ミスのパターンには再現性がない。これはたぶん、BTBエントリには割り当てに先立って何かが入っているからだろう。BTBエントリはランダムに割り当てられるので、最初の学習期間の間に何が起きているか予測できる可能性はほとんどない。
<H3>12.2.5 規則的なパターンからのはずれの扱い(PMMX, PPro and PII)</H3>
分岐予測機構は「ほとんど規則的な」パターンや、規則的なパターンからのはずれを扱うのも得意である。分岐予測機構は、規則的なパターンがどのように見えるか学習するだけではない。規則的なパターンからのはずれがどのように見えるかも学習する。もしはずれ方がいつも同じなら、不規則なできごとの後で何が来るかを覚え、はずれのコストは予測ミス1回だけですんでしまうのである。
<PRE>例:
0001110001110001110001011100011100011100010111000
^ ^
</PRE>
この列で0はジャンプしない、1はジャンプすることを表す。分岐予測機構は繰り返される列が000111であることを学習する。最初の不規則性は、^でしるしをつけた、予期できない0である。0010,0101,1011の後に何が来るかはまだ学習していないので、この0の後の3つのジャンプは予測ミスする可能性がある。同じ種類の不規則性1回か2回の後では、分岐予測機構は0010の後に1、0101の後に1、1011の後に1が来ることを学習してしまう。その意味は、同じ種類の不規則性高々2回で、この種の不規則性を予測ミス1回だけで扱えるように学習してしまうということである。
<P>二つの異なる規則的なパターンが交互に起きるときも、予測機構はたいへん有効である。例えば、000111というパターン(周期6)が何度も繰り返され、次にパターン01(周期2)が何度も、そして000111のパターンにもどるとすると、分岐予測機構は000111のパターンを再学習する必要はない。なぜなら、000111の列で使われるカウンタは、01の列ではいじらないからである。二つのパターンが2～3回交替した後では、パターンの切り替え毎にたった1回だけの予測ミスで、パターンの変化も扱えるように学習してしまう。
<H3>12.2.6 完全には予測できないパターン(PMMX, PPro and PII)</H3>
完全には予測できない最も単純な分岐パターンは6回おきの分岐である。パターンは、
<PRE>000001000001000001
^^ ^^ ^^
ab ab ab
</PRE>
である。列0000の後には交互に、aの場所では0が、bの場所では1がくる。これはカウンタ0に影響し、毎回状態が上下する。もしカウンタ0がたまたま状態0で始まったら、状態0と1を交互に繰り返す。これは場所bで予測ミスすることになる。もしカウンタ0がたまたま3で始まったら、状態2と3を交互に繰り返し、場所aで予測ミスを起こす。最も悪い場合は状態2で始まったときである。カウンタ0は状態1と2を交互に繰り返し、場所aとbの両方で予測ミスが起きるという不運な成り行きとなる。(これは<A HREF="#JUMPS-1-1">12.1.1節</A>の終わりで説明したPPlainの最悪の場合と同類である)。この四つの状況のどれになるかは、この分岐へ割り当てる前の、BTBエントリの履歴による。ランダム割り当て法のため、これは制御できない。
<P>原理的には、カウンタを望みの状態に持っていくように特別に設計された初期分岐列を与えることで、1周期で2回の予測ミスが起きる最悪の状況を避けることは可能である。しかしながら、そのようなアプローチは勧められない。なぜなら、コードをだいぶ余計に複雑にするひつようがあるし、カウンタに込めた情報は何であれ、タイマ割り込みやタスクスイッチの間に失われてしまいがちだからである。
<H3>12.2.7 完全にランダムなパターン(PMMX, PPro and PII)</H3>
パターン認識の強力な能力には、規則性の全然ない完全にランダムな列の場合には小さな欠点がある。
次の表は、ジャンプする/しないの完全にランダムな列についての予測ミスの、実験的に求めた割合を表している。
<PRE>ジャンプする/しない 予測ミスの割合
---------------------------------------
0.001/0.999 0.001001
0.01/0.99 0.0101
0.05/0.95 0.0525
0.10/0.90 0.110
0.15/0.85 0.171
0.20/0.80 0.235
0.25/0.75 0.300
0.30/0.70 0.362
0.35/0.65 0.418
0.40/0.60 0.462
0.45/0.55 0.490
0.50/0.50 0.500
---------------------------------------
</PRE>
<P>プロセッサは、規則性の全然ない列の中で繰り返しパターンを見つけようとし続けるので、予測ミスの割合は、パターン認識なしでなるであろう割合より少し高い。
<H3>12.2.8 きついループ(PMMX)</H3>
パターン認識機構が次の分岐に出会う前にデータを更新する時間がないような小さいループでは、分岐予測は頼りにならない。この意味は、普通なら完全に予測できるような、単純なパターンを認識できないということである。偶然に、普通は認識できないようないくつかのパターンを、小さいループでは完全に予測する。例えば、毎回6回繰り返すループは、ループの末尾の分岐命令において、分岐パターン111110を持つ。このパターンでは普通は、繰り返し1回あたり1回または2回の予測ミスがあるが、きついループでは1回もない。同じことは7回繰り返すループにもあてはまる。他の繰り返し回数のループはほとんど、普通よりきついループのほうが予測がうまくいかない。この意味は、6回または7回繰り返すループはなるべくきつくするべきで、一方、他のループはなるべくきつくなくするべきだということである。ループをきつくなくする必要があるなら、ループを伸ばせばよい。
<P>PMMXでループが「きつい」ふるまいをするかどうか知るためには、次のようなおおざっぱなやり方に従うとよい: ループ中の命令数を数えよ。もしそれが6以下なら、ループはきついふるまいをする。7命令より多ければ、パターン認識は普通に働くと、かなり確信してよい。不思議なことに、各命令が何クロックサイクルかかるか、ストールがあるか、ペアになるかどうかは関係ない。複雑な整数命令も変わりない。複雑な整数命令をたくさん含んでいて、きついふるまいをするループもあり得る。複雑な整数命令とは、ペアにできない整数命令でいつでも2クロックサイクル以上かかるもののことである。複雑な浮動小数点命令やMMX命令もまた1と数える。このおおざっぱな方法は発見的なもので、完全に信頼できるものではないことに気をつけてほしい。重要な場合には、自分でテストしたいかもしれない。PMMXでは、分岐予測ミスを数えるのに性能モニタカウンタの35H(PProとPIIでは0C5H)が使える。分岐予測は、割り当てに先立つBTBエントリの履歴に依存するかもしれないので、テストの結果は完全に決定的ではないかもしれない。
<P>PProとPIIのきついループについては、正確な実験的情報を持っていない。
<H3>12.2.9 間接ジャンプとコール(PMMX, PPro and PII)</H3>
間接ジャンプやコールのためのパターン認識機構はなく、BTBは間接ジャンプのジャンプ先を一つしか覚えない。単純に、前回と同じジャンプ先にジャンプすると予測するだけである。
<H3>12.2.10 JECXZとLOOP(PMMX)</H3>
PMMXには、これら二つの命令のためのパターン認識機構はない。単純に、前回の実行と同じようになると予測するだけである。これら二つの命令は、PMMXの、時間的に決定的なコードでは、避けるべきである。
<H3>12.2.11 リターン(PMMX, PPro and PII)</H3>
PMMX、PPro、PIIプロセッサは Return Stack Buffer (RSB)を持っており、リターン命令を予測するのに使う。RSBは先入れ後出しバッファとして働く。CALL命令が実行される度に、対応する戻り番地がRSBに押し込まれる。そして、RET命令が実行される度に、戻り番地がRSBから引き出され、RETの予測のために使われる。この機構は、同じサブルーチンがいくつかの異なる場所から呼び出されるときにリターン命令が正しく予測されることを保証する。
<P>この機構が確かに正しく働くようにするために、すべてのコールとリターンが対応しているようにしなければならない。速度が決定的なところでは、リターンを実行しないでサブルーチンから飛び出したり、リターンを間接ジャンプとして使ったりは決してしてはいけない。
<P>PMMXでは、RSBは四つのエントリしか保持できない。RSBが空のときには、リターン命令は間接ジャンプと同じように、つまり、前回と同じジャンプ先に行くと予測される。サブルーチンが4段より深くネストするときは、最も内側の4段がRSBを使い、それより外側からのリターンでは、新しいコールがない限り、単純な予測機構を使う。RSBを使っているリターン命令もBTBエントリを専有する。
<P>RSBの四つのエントリは多くないと思うかもしれないが、おそらく十分である。4段より深いサブルーチンのネスティングはたしかに珍しくはないが、速度については、最も深い部分だけが問題になる。
<P>PProとPIIのRSBの大きさについての情報は持っていない。
<H3>12.2.12 静的予測(PMMX)</H3>
以前に出会ったことのない、すなわち、BTBに入っていない制御移行命令は、PMMXではいつでも通り抜けると予測される。前に行くか後ろに行くかは関係ない。
<P>いつでも通り抜ける分岐命令はBTBエントリを持たない。いったん分岐すると直ちに、それはBTBに入り、何度通り抜けてもそこにとどまる。制御移行命令がBTBから出られるのは、他の制御移行命令にBTBエントリを盗られて押し出されたときだけである。
<P>その直後の番地にジャンプするような制御移行命令は、BTBエントリを得ない。
<PRE>例:
JMP SHORT LL
LL:
</PRE>
<P>この命令はBTBエントリを得ることは決してなく、そのためいつでも予測ミスのペナルティーがある。???
<H3>12.2.13 静的予測(PPro and PII)</H3>
PProとPIIでは、以前に出会ったことのない、すなわち、BTBに入っていない制御移行命令は、前に行く場合は通り抜けると予測され、後ろに行く(つまりループ)場合は分岐すると予測される。これらのプロセッサでは、静的予測は動的予測より長い時間がかかる。
<H3>12.2.14 近接したジャンプ(PMMX)</H3>
PMMXでは、二つの制御移行命令が互いに近過ぎると、同じBTBエントリを共有する恐れがある。その明白な結果は、いつでも予測ミスすることである。
<P>制御移行命令のBTBエントリは、命令の最後のバイトの番地のビット2～31で同定される。二つの制御移行命令が接近し過ぎて番地のビット0～1しか違わないと、BTBエントリを共有する問題が起きる。
<PRE>例:
CALL P
JNC SHORT L
</PRE>
もし、CALL命令の最後のバイトとJNC命令の最後のバイトがメモリの同じDWORDにはいっていると、ペナルティーがある。アセンブラの出力リストを見て、二つの番地がDWORD境界で分離されているかどうかを見なければならない。(DWORD境界とは、4で割り切れる番地のことである)。
<P>この問題を解決するには、いろいろな方法がある。
<OL>
<LI>コード列をメモリ中で少し上か下に動かして、二つの番地の間にDWORD境界がくるようにする。
<LI>shortジャンプをnearジャンプ(4バイトの変位)に変えて、命令の終わりがもっと下に行くようにする。命令の最短の形式以外を使うようにアセンブラに強制する方法はないので、この解決法を選んだときには、near分岐をハードコードする必要がある。
<LI>CALL命令とJNC命令の間に何か命令を入れる。これは最も簡単な方法であり、セグメントがDWORDでアラインされていないとか、先行するコードを変更するにしたがってコードが上下するなどの理由で、DWORD境界がどこにあるかわからないときには、唯一の方法である。
<PRE> CALL P
MOV EAX,EAX ; 安全にするための、2バイトの詰め物
JNC SHORT L
</PRE>
</OL>
<P>もしPPlainでも問題を回避したいなら、代わりにNOPを二つ入れてペアリングを防ぐようにせよ(<A HREF="#JUMPS-1-3">12.1.3節</A>参照)。
<P>RET命令はわずか1バイト長なので、この問題が特に起きやすい。
<PRE> JNZ NEXT
RET
</PRE>
ここでは最大3バイトの詰め物が必要である。
<PRE> JNZ NEXT
NOP
MOV EAX,EAX
RET
</PRE>
<H3>12.2.15 連続するコールとリターン(PMMX)</H3>
コールの先のラベル続く最初の命令ペアが別のコール命令を含んでいたり、リターンが別のリターンの直後にあったりすると、ペナルティーがある。
<PRE>FUNC1 PROC NEAR
NOP ; コールの後のコールを避ける
NOP
CALL FUNC2
CALL FUNC3
NOP ; リターンの後のリターンを避ける
RET
FUNC1 ENDP
</PRE>
一つのNOPではCALLとペアになってしまうので、 CALL FUNC2 の前には二つのNOPが必要である。RETはペアになれないので、RETの前は一つのNOPで十分である。リターンの後のCALLにはペナルティーがないので、二つのCALL命令の間にNOPは必要ない。(PPlainではここにも二つのNOPが必要である)。
<P>コールの連鎖のペナルティーは、同じサブルーチンが二つ以上の場所から呼ばれるときだけ起きる(おそらくRSBの更新が必要なため)。リターンの連鎖はいつでもペナルティーがある。コールの後のジャンプには時々小さなストールがあるが、コールの後のリターン、リターンの後のコール、ジャンプの後のジャンプとコールとリターン、リターンの後のジャンプには、ペナルティーはない。
<H3>12.2.16 分岐予測可能性のための設計(PMMX, PPro and PII)</H3>
多方向分岐(switch/case文)はジャンプ番地のリストを使った間接ジャンプか、分岐命令の木で実現される。間接ジャンプの予測は貧弱なので、簡単に予測できるパターンが期待できてBTBエントリが十分あるなら、後者の方法のほうが好ましい。
<P>コードを再構成して、完全には予測できない分岐パターンを完全に予測できる別のパターンで置き換えたいと思うかもしれない。例えば、いつでも20回実行されるループを考えてみよう。ループの末尾の条件ジャンプは19回分岐し、20回目には毎回通り抜ける。このパターンは規則的であるが、パターン認識機構では認識できない。これを4回と5回のネストしたループにするか、ループを4回伸ばして5回実行するかして、認識できるパターンだけにすることができる。この種の複雑なスキームは、PProとPIIのような予測ミスが非常に高価なプロセッサでだけ余計なコストに見合う価値がある。これより大きいループ回数では、たった一つの予測ミスについて何かする理由は何もない。
<H3>12.3 分岐を避ける</H3>
時には、分岐と同じ効果をビットとフラグの巧妙な操作で得られる。例えば、符号つき数の絶対値を分岐なしで計算できる。
<PRE> CWD
XOR EAX,EDX
SUB EAX,EDX
</PRE>
(PPlainとPMMXでは、CWDの代わりに MOV EDX,EAX / SAR EDX,31 を使う)。
<P>キャリーフラグはこの種のトリックには特に役に立つ。
<PRE>値が0ならキャリーを立てる: CMP [value],1
値が0でなければキャリーを立てる: XOR EAX,EAX / CMP EAX,[value]
キャリーならカウンタを増やす: ADC EAX,0
キャリーが立つたびにビットをセットする: RCL EAX,1
キャリーが立っているならビットマスクを生成する: SBB EAX,EAX
任意の条件でビットをセットする: SETcond AL
任意の条件で8ビットをセットする: SETNcond AL / DEC AL
(最後の例では、条件を反転するのを忘れないように)
</PRE>
<P>この例は、二つの符号なし数の小さいほうを見つける: if (b < a) a = b;
<PRE> SUB EBX,EAX
SBB ECX,ECX
AND ECX,EBX
ADD EAX,ECX
</PRE>
<P>この例は二つの数の一つを選ぶ: if (a != 0) a = b; else a = c;
<PRE> CMP EAX,1
SBB EAX,EAX
XOR ECX,EBX
AND EAX,ECX
XOR EAX,EBX
</PRE>
<P>このようなトリックが余分なコードに見合うかどうかは、条件ジャンプがどれだけ予測できるか、分岐のないコードで増えたペアリングの機会を利用できるかどうか、そして、連続するジャンプのペナルティーを受けるようなジャンプが直後にあるかどうかによる。
<P>PProとPIIプロセッサは、特に分岐を避けることを意図した、条件つきMOV命令を持っている。これらのプロセッサでだけ走るようなコードでは、予測のうまくいかない分岐は可能ならすべて条件つきMOVで置き換えるべきである。
<HR>
<H2><A NAME="PREFIXES">13. プリフィックス(PPlain and PMMX)</A></H2>
一つまたは複数のプリフィックスを持つ命令は、Vパイプで実行できないかもしれず(<A HREF="#PAIRING-7">段落8.7</A>参照)、デコードに2クロック以上かかるかもしれない。
<P>PPlainでは、near条件ジャンプの0Fhプリフィックスを除いて、デコードの遅れは各プリフィックスあたり1クロックサイクルである。
<P>PMMXでは、0Fhプリフィックスについてのデコードの遅れはない。セグメントとリピートプリフィックスはデコードに1クロック余計にかかる。アドレスとオペランドサイズプリフィックスはデコードに2クロック余計にかかる。最初の命令がセグメントかリピートプリフィックスを持っているか、プリフィックスを持たず、二番目の命令がプリフィックスを持たないなら、PMMXはクロックサイクルあたり2命令デコードできる。アドレスまたはオペランドプリフィックスを持つ命令は、PMMXでは単独でしかデコードできない。二つ以上のプリフィックスを持つ命令は各プリフィックスについて1クロック余計にかかる。
<P>アドレスサイズプリフィックスは32ビットモードを使うことで避けられる。セグメントプリフィックスは、32ビットモードでは、フラットメモリモデルを使うことで避けられる。オペランドサイズプリフィックスは、32ビットモードでは、8ビットと32ビットの整数だけを使うことで避けられる。
<P>プリフィックスが避けられない場所では、先行する命令が実行に2クロック以上かかるなら、デコードの遅れはマスクされるかもしれない。PPlainのための規則は次の通りである。実行(デコードではない)にNクロックサイクルかかる任意の命令は、次の二つ(ときには三つ)の命令または命令ペアのN-1個のプリフィックスのデコードの遅れに「影を落とす」ことができる。言い換えれば、命令の実行にかかる余分なクロックは、それぞれ後の命令のプリフィックス一つをデコードするのに使えるということである。この影落とし効果は予測できた分岐をも越えて拡張される。2クロックサイクル以上かかる命令、AGIストール、キャッシュミス、ミスアラインメント、そのほか、デコードの遅れや分岐予測ミスを除くどんな理由によってでも遅れる命令は何でも、影落とし効果を持つ。
<P>PMMXは、同様の影落とし効果をもつが、その機構は異なる。デコードされた命令は透過な first-in-first-out (FIFO) バッファに格納され、バッファは4つまでの命令を保持できる。FIFOバッファに命令がある限り、遅れはない。バッファが空のときは、命令はデコードされるとすぐに実行される。命令が実行されるよりデコードされるのが速いとき、つまり、ペアにならない、または複数サイクルの命令があるときに、バッファは満たされる。命令がデコードされるより実行されるのが速いとき、つまり、プリフィックスによるデコードの遅れがあるとき、FIFOバッファは空になる。予測ミスした分岐の後は、FIFOバッファは空である。二番目の命令はプリフィックスなしで、どちらの命令も7バイトより長くないという前提で、FIFOバッファはクロックサイクルあたり2命令を受け取れる。二つの実行パイプライン(UとV)は、クロックサイクルあたりそれぞれFIFOバッファから1命令を受け取れる。
<PRE>例:
CLD / REP MOVSD
</PRE>
CLD命令は2クロックサイクルかかり、従ってREPプリフィックスのデコードの遅れに影を落とす。もしCLD命令が REP MOVSD から遠くにあったとしたら、コードはもう1クロックサイクルかかっていただろう。
<PRE>CMP DWORD PTR [EBX],0 / MOV EAX,0 / SETNZ AL
</PRE>
CMP命令はここではread/modify命令なので、2クロックサイクルかかる。SETNZ命令の0FhプリフィックスはCMP命令の第2クロックサイクルの間にデコードされるので、PPlainではデコードの遅れは隠される(PMMXは0FHのデコードの遅れはない)。
<HR>
<H2><A NAME="REDUCING">14. コードサイズの縮小</A></H2>
<A HREF="#CACHE">6章</A>で説明したように、コードキャッシュは8KBまたは16KBである。コードの決定的に重要な部分をコードキャッシュに納めるのに問題があるのなら、コードのサイズを縮小することを考慮するのもよい。
<P>アドレスとデータの定数は、32ビットコードでは4バイトかかるが16ビットコードでは2バイトしかかからないので、普通は、32ビットコードは16ビットコードより大きい。しかしながら、16ビットコードには、プリフィックスや、隣り合うワードを同時にアクセスするときの問題(<A HREF="#IMPERFECT">10章</A>参照)のような他のペナルティーがある。コードのサイズを減らす別の方法を以下で議論する。
<P>ジャンプの番地、データの番地、データ定数はどれも、符号拡張されるバイトで表現できるなら、つまり、-128から+127までの範囲なら、少ないスペースですむ。
<P>ジャンプの番地については、これの意味は、短いジャンプはコードが2バイトしかかからないが、一方、127バイトを越えるジャンプは無条件ジャンプなら5バイト、条件ジャンプなら6バイトかかるということである。
<P>同様に、データの番地がポインタと-128から+127までの変位で表現できるなら、少ないスペースですむ。
<PRE>例:
MOV EBX,DS:[100000] / ADD EBX,DS:[100004] ; 12バイト
これを縮小して:
MOV EAX,100000 / MOV EBX,[EAX] / ADD EBX,[EAX+4] ; 10バイト
</PRE>
ポインタを使うのは、それを何度も使うほど有利になる。だから、データをスタックに格納し、EBPまたはESPをポインタとして使うことは、もちろんデータがポインタから127バイト以内であるという前提で、静的メモリと絶対番地を使うことに比べて、コードを小さくする。一時データの読み書きにPUSHとPOPを使うことは、さらにもっと有利である。
<P>データ定数も-128から+127の間にあれば少ないスペースですむ。即値をもつ多くの命令は、オペランドが符号拡張されるバイトであるような短い形式を持つ。
<PRE>例:
PUSH 200 ; 5バイト
PUSH 100 ; 2バイト
ADD EBX,128 ; 6バイト
SUB EBX,-128 ; 3バイト
</PRE>
<P>短い形式のない即値つき命令で最も重要なのは、MOVである。
<PRE>例:
MOV EAX, 1 ; 5バイト
これは次のように変えるとよい:
XOR EAX,EAX / INC EAX ; 3バイト
または
PUSH 1 / POP EAX ; 3バイト
</PRE>
<P>4バイトの即値オペランドを持つMOVは、MOVの前のレジスタの値がわかっていれば、算術演算命令で置き換えるとよいことがある。
<PRE>例:
MOV [mem1],0 ; 10バイト
MOV [mem2],-1 ; 10バイト
MOV EAX,100 ; 5バイト
MOV EBX,150 ; 5バイト
これは次のように変更するとよい:
XOR EAX,EAX ; 2バイト
MOV [mem1],EAX ; 5バイト
DEC EAX ; 1バイト
MOV [mem2],EAX ; 5バイト
ADD EAX,101 ; 3バイト
LEA EBX,[EAX+50] ; 3バイト
</PRE>
LEA命令のAGIストールに気をつけてほしい。
<P>もし同じ定数を2回以上使うなら、もちろんレジスタにロードするのがよい。
<PRE>例:
MOV DWORD PTR [EBX],0 / MOV DWORD PTR [EBX+4],0 ; 13バイト
XOR EAX,EAX / MOV [EBX],EAX / MOV [EBX+4],EAX ; 7バイト
</PRE>
<P>異なる命令は異なる長さを持つことも考慮してよい。次の命令は1バイトしかかからず、従ってたいへん魅力的である。
<PRE>PUSH reg, POP reg, INC reg32, DEC reg32
</PRE>
8ビットレジスタのINCとDECは2バイトかかるので、 INC EAX は INC AL より短い。