続 PowerPC

プログラム

PowerPC って条件分岐命令内に分岐予測のヒント情報が載ってたのか、今更何を言っているって感じだけど。
分岐予測のデフォルトは以下の様に設定されるらしい。これを決定するのはアセンブラの仕事。もちろんユーザが taken(+) もしくは not taken(-) を明示的に指定する事もできる。

条件分岐で分岐先アドレスが現アドレスよりも前の場合
taken。ループ条件とか。
条件分岐で分岐先アドレスが現アドレスよりも後ろの場合
not taken。assert(3) などエラーチェックとか。
条件分岐で分岐先アドレスが LR もしくは CTR の場合
not taken。パラメータチェック NG で return とか。

gcc の __builtin_expect はこういうアーキテクチャで有効になるのか…。そりゃ IA-32 じゃ意味のあるコードは出てこないよなぁ。なるほど。
以下に例として strncpy(3)。コンパイルもアセンブルもしてないので注意(マテ

 0: /* 例: strncpy(3), dst と src の NULL チェックは省いた */
 1: char *
 2: strncpy(char *dst, const char *src, size_t n)
 3: {
 4:     if (n != 0) {
 5:         char *d = dst;
 6:         const char *s = src;
 7: 
 8:         do {
 9:             if ((*d++ = *s++) == '\0') {
10:                 while (--n != 0) {
11:                     *d++ = '\0';
12:                 }
13:                 break;
14:             }
15:         } while (--n != 0);
16:     }
17:     return dst;
18: }

; 引数は dst = r3, dst = r4, n = r5 でレジスタ渡し。戻り値 は r3 で返す。
; char *strncpy(char *dst, const char *src, size_t n)
    cmpwi r5, 0      ;  4: if (n != 0)
    belr-            ; 17: return dst; <- 3 番目の例 的中
    mr    r6, r3     ;  5: char *d = dst;
    mr    r7, r4     ;  6: const char *d = src;
1:                   ;  8: do {
    lbz   r8, 0(r7)  ;  9: tmp = *s;
    stb   r8, 0(r6)  ;  9: *d = tmp;
    addi  r6, r6, 1  ;  9: d++;
    addi  r7, r7, 1  ;  9: s++;
    cmpwi r8, 0      ;  9: tmp == '\0'
    bne+  4f         ;  9: tmp != '\0' の場合は 15 行目へ <- 2 番目の例 的中
    li    r9, 0      ;     tmp = '\0'
2:  addi  r5, r5, -1 ; 10: --n;
    cmpwi r5, 0      ; 10: n == 0
    be+   3f         ; 10: n == 0 の場合は 13 行目へ <- 2 番目の例 外れ
    stb   r8, 0(r6)  ; 11: *d = '\0';
    addi  r6, r6, 1  ; 11: d++;
    b     2b         ; 12: }
3:  b     5f         ; 13: break;
4:  addi  r5, r5, -1 ; 15: --n;
    cmpwi r5, 0      ; 15: n == 0
    bne-  1b         ; 15: n != 0 の場合 8 行目へ <- 1 番目の例 的中
5:  blr              ; 17: return dst;

最適化してみた…。

  • bdz/bdnz (カウンタレジスタをデクリメントして、カウンタレジスタの値が 0(bdz), 0 以外(bdnz) であれば分岐する)命令があるので、カウンタレジスタを使うともう少し小さくなる。
  • 条件レジスタを更新する命令(cmpwi)を使用した直後に条件レジスタを参照しない方が良いのか。並列に命令を実行してるからだろうな。gcc-3.3.2 の -O3 で出力されたコードを見ると 3 命令は間をあけた方が良いっぽい。
; 脳内最適化…
; char *strncpy(char *dst, const char *src, size_t n)
    cmpwi r5, 0      ;  4: if (n != 0)
    belr-            ; 17: return dst;
    li    r6, 0      ;     offset = 0
1:  addi  r5, r5, -1 ; 15: } while (--n != 0);
    lbzx  r7, r4, r6 ;  9: tmp = src[offset]
    stbx  r7, r3, r6 ;  9: dst[offset] = tmp
    addi  r6, r6, 1  ;     offset++
    cmpwi r7, 0      ;  9: if (dst[offset] == '\0')
    be-   2f         ;     10: while (--n != 0) へ
    cmpwi r5, 0      ; 15: } while (--n != 0);
    bne+  1b         ;     8: do { へ
    blr              ; 17: return dst;
2:  li    r8, 0      ;     tmp = '\0'
3:  stbx  r8, r3, r6 ; 11: dst[offset] = '\0';
    cmpwi r5, 0      ; 10: while (--n != 0)
    addi  r5, r5, -1 ;     --n (addi. ではないので Rc は update されない)
    bne+  3b         ;
    blr              ; 13: break; -> 17: return dst;