> トップページ > GBA > ドキュメント

GBA と __builtin_expect について

■ GBA と __builtin_expect について

高速化を期待して、ループの終了条件 (約 1/512) とかに __builtin_expect を付けると、かえって最適化が無効化されて速度が落ちてしまって、なんとも。

GBA に搭載されている CPU は携帯機用だけあってシンプルな機能しかありません。

そのため最適化の戦略が「執拗な inline 化」になり、アセンブリの可読性が最悪な感じになっているのですが、比較コードが以下。

通常時の「ややこしい処理」への突入部分が (その他の処理部分にある条件分岐と共有できるため) どっかに行ってしまっているのが泣かせますが、 gcc の想像を越える最適化はすばらしいということで。

それよりも何で __builtin_expect を付けた際に最適化が解けるんだ……。

通常時	__builtin_expect 使用時
eae: mov r5, #22 eb0: ldrsh r4, [r0, r5] eb2: asr r3, r4, #7 eb4: mov r5, #8 eb6: add r2, r3, r5 eb8: bmi f5a eba: asr r2, r2, #2 ebc: lsl r2, r2, #2 ebe: ldr r3, [r2, r6] ec0: add r3, #1 ec2: str r3, [r2, r6] ec4: ldr r0, [r0, #4] ec6: cmp r0, #0 ec8: beq f5e eca: ldrb r3, [r0, #18] ecc: cmp r3, #8 ece: beq ec4 ed0: cmp r3, #2 ed2: bne eae f5a: add r2, #3 f5c: b eba f5e: mov r2, #0 ……その他の処理へ……	ebc: ldrb r3, [r0, #18] ebe: cmp r3, #8 ec0: beq ee0 ec2: cmp r3, #2 ec4: bne ec8 ec6: b 101e ec8: mov r2, #22 eca: ldrsh r4, [r0, r2] ecc: asr r3, r4, #7 ece: mov r1, #8 ed0: add r2, r3, r1 ed2: bpl ed6 ed4: b 10ba ed6: asr r2, r2, #2 ed8: lsl r2, r2, #2 eda: ldr r3, [r2, r7] edc: add r3, #1 ede: str r3, [r2, r7] ee0: ldr r0, [r0, #4] ee2: cmp r0, #0 ee4: bne ebc ee6: mov r2, #0 ……その他の処理へ…… 101e: mov r5, #20 ……ややこしい処理開始…… 10ba: add r2, #3 10bc: b ed6

通常時

__builtin_expect 使用時

     eae: mov     r5, #22
     eb0: ldrsh   r4, [r0, r5]
     eb2: asr     r3, r4, #7
     eb4: mov     r5, #8
     eb6: add     r2, r3, r5
     eb8: bmi     f5a
     eba: asr     r2, r2, #2
     ebc: lsl     r2, r2, #2
     ebe: ldr     r3, [r2, r6]
     ec0: add     r3, #1
     ec2: str     r3, [r2, r6]
     ec4: ldr     r0, [r0, #4]
     ec6: cmp     r0, #0
     ec8: beq     f5e
     eca: ldrb    r3, [r0, #18]
     ecc: cmp     r3, #8
     ece: beq     ec4
     ed0: cmp     r3, #2
     ed2: bne     eae

     f5a: add     r2, #3
     f5c: b       eba

     f5e: mov     r2, #0
     ……その他の処理へ……

     ebc: ldrb    r3, [r0, #18]
     ebe: cmp     r3, #8
     ec0: beq     ee0
     ec2: cmp     r3, #2
     ec4: bne     ec8
     ec6: b       101e
     ec8: mov     r2, #22
     eca: ldrsh   r4, [r0, r2]
     ecc: asr     r3, r4, #7
     ece: mov     r1, #8
     ed0: add     r2, r3, r1
     ed2: bpl     ed6
     ed4: b       10ba
     ed6: asr     r2, r2, #2
     ed8: lsl     r2, r2, #2
     eda: ldr     r3, [r2, r7]
     edc: add     r3, #1
     ede: str     r3, [r2, r7]
     ee0: ldr     r0, [r0, #4]
     ee2: cmp     r0, #0
     ee4: bne     ebc
     ee6: mov     r2, #0
     ……その他の処理へ……

    101e: mov     r5, #20
    ……ややこしい処理開始……

    10ba: add     r2, #3
    10bc: b       ed6

ちなみに、元の C++ のコードはコレ。 __builtin_expect 付きのコードのほうが C++ に近いコードです。

  BulletInfo *bi;
  bi = ListBullets::getFirstItem();
  for (;;) {
#if NO_BUILTIN
    if (bi == NULL) {
      break;
    }
#else
    if (__builtin_expect(bi == NULL, 0)) {
      break;
    }
#endif
    if (bi->getType() == BULLET_TYPE_HIDDEN) {
      bi = ListBullets::iterator(bi);
      continue;
    } else if (bi->getType() == BULLET_TYPE_NORMAL) {
      // ややこしい処理
      shotHitCheck(bi, listShotMinPosX, listShotMaxPosX);
    }

    p->registItemNumInBlock(bi->getPosY().toInt());

    bi = ListBullets::iterator(bi);
  }

  // その他の処理へ

■ 追記 (08/20)

kashiwa さんのところでは実際に速くなる状況が、 wo さんのところでは __builtin_expect の興味深い解説が行われています。

ちなみに、 wo さんの通り、

for (;;) {
  if (終了条件) {
    break
  }
}

よりも

for (; ! 終了条件; ) {
}

のほうが最適なコードが吐かれるようです。

しかし __builtin_expect を付けると遅くなる症状はかわらず、やはり関数扱いされる仮説が有力の模様。

Comments for This Page.

Date: 2006-08-15 00:00 (JST)