NAKAMURA Minoru の日記 (2009年4月)

[CPU] NetBurst アーキテクチャ以降の分岐予測はオレよりかしこいかも

Intel の x86 系 CPU の分岐ミスペナルティを計測しようと、 手元にある NetBurst アーキの Xeon CPU を調べていたのだが、 NetBurst アーキの段階で Intel の分岐予測は結構キていることが分かった。

とりあえず分岐1回あたりの実行サイクル数を調べてみると、

• 「常に分岐成立」や「常に分岐不成立」のパターンでは分岐ミスはなし。
• 「分岐成立・不成立を交互」、「2回成立の後に2回不成立」、「4回成立の後に4回不成立」は ほぼ1サイクル増に納まっていることから、ほとんど分岐ミスが起きていないようだ。 これらの BTB にパターンは読みきられている。
• 「8回成立の後に8回不成立」のパターンで実行時間が増加。

どういうアルゴリズムで判定をしているのか確かめようと、 16回のパターンを1億回以上繰り返して、 1回の分岐にかかる時間を計測してみる。 だが結果からパターンが読みきれない orz

分岐予測器はかなり正確な予測をしているのが分かるが、 1 0 の繰り返しのような単純なパターンでも全分岐予測を当てるわけではないようだ。 pfmon が動けばパフォーマンスモニタカウンタの分岐予測ミス回数を測れるので、 もっと正確な事情が分かるのだが、 今は忙しいのでまた今度。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>

#define rdtsc()\
    ({uint64_t high, low;\
        __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));\
       ((high << 32) | low);})

static volatile int dummy;

// All 0 (全て分岐しない)
// static volatile int pat[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

// All 1 (全て分岐する)
// static volatile int pat[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

// 交互に分岐と非分岐を繰り返す
// static volatile int pat[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1};

// 2回づつ分岐と非分岐を繰り返す
// static volatile int pat[] = {0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1};

// 4回づつ分岐と非分岐を繰り返す
// static volatile int pat[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1};

// 8回づつ分岐と非分岐を繰り返す
// static volatile int pat[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1};

extern void foo(int i);

int main(int argc, char** argv) {
    const unsigned long REPEAT = 10000000000;
    unsigned long i;
    uint64_t before = rdtsc();
    for (i=0 ; i<REPEAT ; i++) {
        foo(pat[i % (sizeof(pat)/sizeof(pat[0]))]);
    }
    uint64_t after = rdtsc();
    printf("%f\n", 1.0*(after - before)/REPEAT);
    return 0;
}

        .file   "branch_miss_callee.c"
        .text
        .p2align 4,,15
.globl foo
        .type   foo, @function
foo:
        andl    $1, %edi
        je      .L3
.L3:
        ret

特許書類の確認

特許の関係の書類のチェックで一日が潰れてしまった。

[CPU] インテルの出しているx86-64 命令の資料ではまったよ…

昔作った IA-32 用の機械語生成ライブラリを Intel64 に対応させようと命令仕様書を見ながら改造していたのだが、悲しい箇所ではまってしまった。

IA-32 の命令は清く正しい可変長の CISC 命令だが、内部はバイト単位に分かれている(下の図は Intel64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M からの抜粋)。

プレフィックスを除くと、IA-32 の命令は以下の構成をとる。

1. Opcode だけ (レジスタ指定は opcode に含まれる)
2. Opcode + Immediate
3. Opcode + ModR/M
4. Opcode + ModR/M + Immediate
5. Opcode + ModR/M + Displacement
6. Opcode + ModR/M + Displacement + Immediate
7. Opcode + ModR/M + SIB + Immediate
8. Opcode + ModR/M + SIB + Displacement + Immediate

即値(immediate)がいるかどうかはオペコードで決まるが、SIB と Displacement が必要かどうかは ModR/M と呼ばれる1バイト情報で決まる。 SIB と Displacement はメモリアドレスをさすために使うのだが、原則的に [eax + 8] のようにベースレジスタだけでアドレス計算をする場合には SIB は不要で、[eax + ebx * 4 + 28] のようにベースレジスタとインデックスレジスタの両方を指定する場合に SIB を使う。

ただこのルールは一部に例外がある。 IA-32 はディスプレイスメントをつけずに SIB のベースレジスタフィールドに ebp (=5) を指定すると、「ベースレジスタは使用しない」を意味する。 「これは IA-32 の ebp レジスタはもともとフレームポインタなので、どうせ [ebp + (オフセット定数)] で使うでしょう？オフセット 0 なら無効値ね」という設計方針があったためだと思われる。

ところで IA-32 は汎用レジスタが 8 本だったため、レジスタ指定は 3 ビットで可能である。 ところが Intel64 の汎用レジスタは 16 本に拡張されたために 1 ビット余分に必要となる。 AMD はこの余分の 1 ビットを組み込むために既存の IA-32 の命令フォーマットを変更せずに、「汎用レジスタの8本目以上を使うよ」という指示をオペコードの前にプレフィックスをつけて誤魔化すことにしている。

そのため rbp (実際は r5) と r13 は、SIB の表現が同じになるのだがインテル エクステンデッド・メモリー 64 テクノロジー・ソフトウェア・デベロッパーズ・ガイド、第1巻(PDF形式)の1-16ページにある表1-10. REXエンコーディングの特殊な条件 に見ると、「rbp を指定するとベースレジスタは無効だけど r13 は大丈夫よ」と書いてある。

で、このドキュメントを信じて命令のフォーマッタを書いていたのだが、生成される命令がどうも正しくデコードできない。

ふと気づいて Intel64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M の方を見ていると、 Table 2-5. Special Cases of REX Encodings. には、「r13 も駄目よ〜」となっている。

Intel64 and IA-32 Architectures Software Developer's Manual の方が正しいようだ。 というわけでムダ骨を折ってしまったよ orz

[Prog] BFDライブラリを使った簡易ディスアセンブラ

自分のプログラムにディスアセンブラを組み込みたい場合のサンプルを作成 (disassembler.c)。 x86-64 でもちゃんと動作しているようだ。

[Prog] x86-64 gcc で -fPIC と __attribute__((visibility("protected"))) がビルドエラー

x86-64 用の gcc で visibility を付けた関数を -fPIC でコンパイルして、 共有ライブラリとしてリンクしようとするとエラーが出る。

__attribute__((visibility("protected"))) extern void func_protected(void);

void func_protected(void) {
    printf("%s in %s\n", __FUNCTION__, __FILE__);
}

void call_func_protected(void) {
    func_protected();
}

call_func_protected からの func_protected の呼び出しがリンクエラーの原因のようだ。

> gcc -shared -fPIC visibility.c -o libvisibility.so
/usr/bin/ld: /tmp/ccq9bvj0.o: relocation R_X86_64_PC32 against `func_protected' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: final link failed: Bad value
collect2: ld returned 1 exit status

エラーは gcc 3.4.6 と gcc 4.1.0 で発現。 icc は問題なく動作するし、 visibility の動作も規定通りだ。

objdump で gcc -c -fPIC visibility.c の結果を見ると、 gcc でコンパイルされた func_protected は R_X86_64_PC32 となるのが問題のようだ。

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE 
0000000000000005 R_X86_64_PC32     func_protected+0xfffffffffffffffc

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE 
0000000000000002 R_X86_64_PLT32    func_protected

追記：4/21

RHEL5.3 の gcc 4.1.2 は、 リロケーション型が R_X86_64_PC32 のままだがパスする。