今まである程度は読んでたけど,
『Intel 64 and IA-32 Architectures Optimization Reference Manual』を読み直して, 気づいたことなどをまとめてみようという試み.
今手元にあるのは248966-024 April 2011のもの.
日本語版もありますが, 多少古いので英語版がよいでしょう.
表記について
プロセッサと書いたり, CPUと書いたりします.
Intel64をx64と書いたりします.
例えば3サイクルのことを個人的な慣習で3clkと書くことが多いです. すいません.
間違いなどございましたらメール(herumi@nifty.com)か@herumiにお願いします.
命令キャッシュから16bteずつ読んで命令長を決定する. 命令長を変更するプレフィックス(LCP:length changing prefix)があるとLCPあたり3clkのペナルティがある.
以前のCPUでは16byteあたり6clkのペナルティだった. 16byte内に2個以上LCPが無ければSandy Bridgeの方が優れている.
LCPは次のものがある:
命令をμopに変換する4個のユニットがある. 一つは全ての命令を最大4個のμopに変換する. 残りの三つは一つのμopのみを扱う.
複数のμopを一つの複雑なμopに変換する.
メモリへの書き込み, メモリからの読み込みと何らかの演算, 読み込みとジャンプの形はマクロフュージョンされる.
rip相対アドレスアドレッシングはフュージョンされない.
二つの命令を一つの簡単なμopに変換する. ある条件の元でcmp, test(Nehalemまで), add, sub, and, inc, dec(Sandy Bridgeから)と条件分岐がペアになったときにマクロフュージョンされる(詳細は略).
命令のデコーダの出力結果を保持する. 次回からは命令でコードをせずに, icacheから直接実行することで効率化する.
SSE命令を多用すると命令長が長くなるので命令predecodeの制約(1clkに最大16byte)にひっかかることがあるが, icacheがあると大丈夫.
# perfでL1命令キャッシュミスをみてみる参照.
条件分岐や直接call, jump, 間接call, jumpやretなどに対して予測する.
命令を実行コアに移動する. 複数のμop間の偽の依存関係を排除する. 1clkあたり最大4μopを移動する. zeroイデオム(後述), nop, vzeroupper, fxchgなどの命令はこの処理の中で実行されてパイプラインからは消える. indexレジスタを使うメモリアドレッシングは二つのμopに分解される.
μopの全てのソースオペランドの値が確定したら, そのμopを実行可能として実行ユニットに割り当てる. 実行ユニットは6ポートあり, 1clkあたり各ポートに一つ, 最大6μopを割り当てる.
命令やμopを正しい順序でリタイアする. フォールトや例外も扱う.
命令の並列性はレジスタの中身を0クリアすることで改善できる. リネーマはzeroイデオム, つまりデスティネーションレジスタが0になる命令群, たとえば
xor reg, reg
などを検出する. 他には
xor, sub, pxor, vpxor, psubb/w/d/q, vpsubb/w/d/q, xorps/pd, vxrops/pd
などがある.
命令を順序に関係なく(out-of-order)スーパースカラーで実行する. out-of-orderコアは三つの実行スタックからなる. 各スタックはデータの型(汎用整数, SIMD整数と浮動小数点数, x87)をカプセル化する.
実行後, データはライトバックバス(writeback bus)に書き込まれる.
異なるスタック間でデータ(SSE-intとSSE-fpの間でも)をやりとりする場合は, 1clkのレイテンシが発生する.
LLCは他の全てのレベルのキャッシュを含む. LLCの各キャッシュラインには, それがL2やL1キャッシュにあるかもしれないという目印(indication)が付与されている.
| レベル | レイテンシ |
|---|---|
| L1 Data | 4 |
| L2 | 12 |
| LLC | 26～31 |
| 他のコアのL2やL1 | cleanなら43, dirtyなら60 |
キャッシュの検索時に他のコアからデータをフェッチする必要がないならcleanという. そうではなくて, 他のコアのキャッシュから修正されたデータをフェッチしなければならないとき, dirtyという.
メモリを書き込む際, L1キャッシュ内のそのメモリラインがE(排他), またはM(変更)状態であることを確認する. もし, 正しい状態で, キャッシュラインが無かったら, 次のメモリ階層からRFO(Read for Ownership)に従ってデータをフェッチする.
キャッシュラインは次の順序で探される:
データを書き込んだあと, そのデータを読み直す場合, store操作からload側に直接データを転送することができる. これによりサイクルを短縮できる. 但しいくつかの条件がある. ざっくり言うと, データのアライメントがあっていて, それをまたがず, かつstoreよりもloadのサイズが小さい場合のみ可能.
pcmpXstrY命令は, 文字列として0終端なものかサイズ指定のもの, そして出力結果の取得方法によって使う命令が変わる.
| 0終端による不定長文字列を扱う(i) | edx/eax指定による固定長文字列を扱う(e) | |
|---|---|---|
| 処理の結果をecxに出力する(i) | pcmpistri | pcmpestri |
| 処理の結果をxmm0のビットマスクに出力する(m) | pcmpistrm | pcmpestrm |
これらの命令には8bitの即値(imm8)を指定することで様々な機能を選択できる.
imm8[0]が0ならbyte(1byte), 1ならword(2byte)となる.
imm8[1]が0なら符号無し, 1なら符号ありとなる.
文字列の比較方法を選択できる.
比較命令 str, text, imm8のimm8[3:2]に関する部分の擬似命令
src ← 検索したい文字列
text ← 検索対象のテキスト
int len = (入力の型がbyte) ? 16 : 8;
switch (imm8[3:2]) {
case 00b:
for (int j = 0; j < len; j++) {
int tmp = 0;
for (int i = 0; i < len; i++) {
tmp |= text[j] == str[i];
}
IntRes1[j] = tmp;
}
break;
case 01b:
for (int j = 0; j < len; j++) {
int tmp = 0;
for (int i = 0; i < len; i += 2) {
tmp |= (str[i] <= text[j]) && (text[j] <= str[i + 1]);
}
IntRes1[j] = tmp;
}
break;
case 10b:
for (int j = 0; j < len; j++) {
IntRes1[j] = text[j] == str[j];
}
break;
case 11b:
for (int j = 0; j < len; j++) {
int tmp = 1;
for (int i = 0; i < len - j; i++) {
tmp &= text[j + i] == str[i];
}
IntRes1[j] = tmp;
}
break;
}
上記比較の際に, EOS(end-of-string)を越えた部分の文字はinvalidとして処理できる. invalidな文字とvalidな文字との比較は次のルールに従う.
| xmm1(str) | xmm2(text) | equal any | ranges | equal each | equal ordered |
|---|---|---|---|---|---|
| valid | valid | 通常通り | 通常通り | 通常通り | 通常通り |
| valid | invalid | 常に0 | 常に0 | 常に0 | 常に0 |
| invalid | valid | 常に0 | 常に0 | 常に0 | 常に1 |
| invalid | invalid | 常に0 | 常に0 | 常に1 | 常に1 |
polarity(極性) : 各文字に対して集計操作をするときに反転操作などの操作を挿入できる.
pcmpestri, pcmpistriとpcmpestrm, pcmpistrmそれぞれについて2種類の方法を設定可能.
pcmpestri, pcmpestrmの二つの命令の'e'はexplicit lengthの意味. eaxで一つ目の文字列(str)の長さ, edxで二つ目の文字列(text)の長さを指定する.
これらの文字列処理命令は同時にフラグレジスタも変更する.
| pcmpestri/pcmpestrm | pcmpistri/pcmpistrm | |
|---|---|---|
| CF | IntRes2 != 0 | |
| ZF | |edx| < 16(or 8) | 二つ目のオペランドのどれかのbyte/wordが0なら1. そうでなければ0 |
| SF | |eax| < 16(or 8) | 一つ目のレジスタのどれかのbyte/wordが0なら1. そうでなければ0 |
| OF | IntRes2[0] | |
複雑なのでIDF Shanghai 2008にあるPhoto46の右下の図で確認してみよう.
| text文字列 : "BABCAB\0S" | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0(j) | |||
| 'S' | '\0' | B | 'A' | 'C' | 'B' | 'A' | 'B' | |||
| src文字列 : "ABCA\0XYZ" | 0(i) | 'A' | fF | fF | F | T | F | F | T | F |
| 1 | 'B' | fF | fF | T | F | F | T | F | x | |
| 2 | 'C' | fF | fF | F | F | T | F | x | x | |
| 3 | 'A' | fF | fF | F | T | F | x | x | x | |
| 4 | '\0' | fT | fT | fT | fT | x | x | x | x | |
| 5 | 'X' | fT | fT | fT | x | x | x | x | x | |
| 6 | 'Y' | fT | fT | x | x | x | x | x | x | |
| 7 | 'Z' | fT | x | x | x | x | x | x | x | |
"BABCAB\0S"から"ABCA\0XYZ"を探すサンプルである. '\0'の後ろに文字があるが見ないので(invalid)何であっても影響はない.
文字列命令を実行すると, byte単位での文字列なら内部で16x16(上記サンプルは8x8になってるが)のTrue/Falseのテーブルができる.
'\0'以後の文字列はinvalidとなり, 「invalid文字の扱い」におけるルールに従ってsrc文字列の'\0'以後はfT(force True), text文字列の'\0'の後はfF(force False)となっている.
equal orderedの場合は右上から左下への対角成分の論理積をとるので順に, F, T, F, F, F, F, F, FとなりIntRes1 = 0b00000010となる.
さてstrlen()を実装する場合を考えてみよう. 位置情報がそのまま欲しく, 0終端の文字列を扱うのでpcmpistri.
符号無しbyte単位なのでimm8[0] = imm8[1] = 0. 集計は0なもの探索の否定, つまり1～255に入ってるを見るためrangesを選択する. よってimm8[3:2] = 01b.
中間結果操作はビット反転なのでimm8[5:4] = 01b.
最終結果は下から何ビットかをみたいのでLSB. よってimm8[6] = 0. 全部合わせてimm8 = 0x14となる.
テキストに0が含まれればZF = 1となるのでそれでループする.
// 上記 Phot47にあるソースコード(注意 : これは遅い)
int sttni_strlen(const char *src)
{
char eom_vals[32] = { 1, 255, 0 };
__asm{
mov eax, src
movdqu xmm2, eom_vals
xor ecx, ecx
topofloop:
add eax, ecx
movdqu xm1, oword ptr [eax]
pcmpistri xm2, xm1, imm8
jnz topofloop
endofstring:
add eax, ecx
sub eax, src
ret
}
}
Intelの当初の解説には「こうせよ」あったようだが, 今のマニュアルには遅いのでこれは使うなとのこと. 理由はpcmpistriでecxが確定するまでアドレス解決ができないためout-of-order実行ができないからだそうな.
殆どの場合はecx = 16になるので次のようにせよとある. 実際ベンチマークをとってみるとかなり差がでる.
// Xbyakによるstrlen by SSE4.2
struct StrlenSSE42 : Xbyak::CodeGenerator {
StrlenSSE42()
{
using namespace Xbyak;
#if defined(XBYAK64_WIN)
const Reg64& p1 = rdx;
const Reg64& c = rcx;
const Reg64& a = rax;
mov(rdx, rcx);
#elif defined(XBYAK64_GCC)
const Reg64& p1 = rdi;
const Reg64& c = rcx;
const Reg64& a = rax;
#else
const Reg32& p1 = edx;
const Reg32& c = ecx;
const Reg32& a = eax;
mov(edx, ptr [esp + 4]);
#endif
mov(eax, 0xff01);
movd(xm2, eax);
xor(c, c);
lea(a, ptr [p1 - 16]);
L("@@");
add(a, 16);
pcmpistri(xm2, ptr [a], 0x14);
jnz("@b");
add(a, c);
sub(a, p1);
ret();
}
};
cf. strlen for SSE4.2のベンチマークをとってみた.
pcmpistriは出力をecxとフラグの二つを出力するのに, intrinsic版は戻り値を一種類しかとれない. 仕方がないのでecxを取得する_mm_cmpistriや, ZFフラグを取得する_mm_cmpistrz, 他には_mm_cmpistrc(CF取得)などいくつか種類がある.
| 返り値 | pcmpestri | pcmpestrm | pcmpistri | pcmpistrm |
|---|---|---|---|---|
| ecx/xmm | _mm_cmpestri | _mm_cmpestrm | _mm_cmpistri | _mm_cmpistrm |
| CF = 0 && ZF == 0 | _mm_cmpestra | _mm_cmpistra | ||
| CF | _mm_cmpestrc | _mm_cmpistrc | ||
| OF | _mm_cmpestro | _mm_cmpistro | ||
| SF | _mm_cmpestrs | _mm_cmpistrs | ||
| ZF | _mm_cmpestrz | _mm_cmpistrz | ||
IntelのマニュアルにはAFは常に0とあるので_mm_cmpestraって何を返すの?と思った. MSDN(_mm_cmpestra)には, IntRes2 == 0かつedxの絶対値が16(or 8)以上のときは1とある. それから推測すると多分CF == 0 && ZF == 0を返す.
ループ内では_mm_cmpistrzを使ってループを抜けたら_mm_cmpistriを使うのは無駄だなあと思っていたが, 試してみたgcc(4.4.5)もVC10も命令が一つにまとめられていた. 抜かりはないなあ.
#ifdef _WIN32
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
size_t strlenSSE42_C(const char* top)
{
const __m128i im = _mm_set1_epi32(0xff01);
const char *p = top - 16;
do {
p += 16;
} while (!_mm_cmpistrz(im, *(__m128i*)p, 0x14)); // ZF
p += _mm_cmpistri(im, *(__m128i*)p, 0x14); // get ecx
return p - top;
}
(注意)上記コードはたまたまうまく動くが危険. pcmpistri自体はアライメントされていないメモリについても動作するが, *(__m128i*)pは場合によってはmovdqaが発行されて例外で落ちてしまうことがある. _mm_loadu_si128((const __m128i*)p)を使うべき. SSE4.2の文字列処理命令の紹介に関する補足も参照してください.
これが次のように出力された(これはgcc 4.4.5の例).
lea rax, [rdi-16]
movdqa xmm0, XMMWORD PTR .LC3[rip]
.p2align 4,,10
.p2align 3
.L98:
add rax, 16
pcmpistri xmm0, XMMWORD PTR [rax], 20
jne .L98
movsx rcx, ecx ; pcmpistriの結果のecxを流用してる
add rax, rcx
sub rax, rdi
ret
これがgcc 4.6.0だと少しループ処理が違う. よりpcmpistriのアドレス生成に使う計算を先にすませようとしている. 試してみると文字列長が短いところでは若干速いが, 長いところでは逆に若干遅い雰囲気.
lea rdx, [rdi-16]
movdqa xmm0, XMMWORD PTR .LC0[rip]
jmp .L11
.p2align 4,,10
.p2align 3
.L12:
mov rdx, rax
.L11:
lea rax, [rdx+16]
pcmpistri xmm0, XMMWORD PTR [rdx+16], 20
jne .L12
ちなみにVCもgccもループから抜けたところでecxからrcxを作るためにmovzxを呼んでいたけど必要なのかな. パーシャルレジスタストールでも発生するのだろうか.