前回：5. 分岐命令次回：7.インデクシングモード
 目次（記事一覧）

※この記事はRoger Ferrer IbáñezさんのブログARM assembler in Raspberry Pi – Chapter 6の翻訳です。

制御構造

前回は分岐命令について学びました。分岐命令は非常に便利で、制御構造を作ることができます。より優れた計算機工学を実現する上で構造化プログラミングは画期的な技術となりました（基本的ではありますが重要です）。よって、一般的な構造化プログラミング手法をアセンブリコードでも再現できるようになることは良いことです。

if - then - else構造

if - then - else構造は基本的なものです。前章でもこの構造が出てきています。次のような構造を考えてみましょう。Eは式、S1とS2は文（{SA; SB; SC}のような複合文も含む）です。

if (E) then
   S1
else
   S2

これをARMで書く方法は次の通りです。


if_eval: 
    /* Eを評価しcpsrレジスタを更新するコードを書く */
bXX else /* XXには適切な条件が入る */
then_part: 
   /* S1を書く */
   b end_of_if
else:
   /* S2を書く */
end_of_if:

elseパートが不要なら、bXX elseをbXX end_of_ifに書き換えます。

ループ構造

構造化プログラミングにおいて、ループ構造もまた基本的なものです。ループは何種類かありますが、実際にはすべて次のような構造に集約できます。

while (E)
  S

Sがおそらく何らかの作業をして、Eは最終的に偽になりループを抜けます。さもないと、ずっとループに留まることになります（サンプルコードには載せていませんがそうしたいこともあります）。上の例を実装する方法は次の通りです。

while_condition :
  /* Eを評価しcpsrレジスタを更新するコードを書く */
  bXX end_of_loop  /* Eが偽ならループを抜ける */
  /* Sを書く */
  b while_condition /* ループの最初へ無条件分岐 */
end_of_loop:

forループはある範囲を決めて繰り返すループです。

for (i = L; i < N; i += K)
  S

これは、このように表現できます。

  i = L;
  while (i < N)
  {
     S;
     i += K;
  }

したがって、今までの知識だけでforループを実装できます。

1+2+3+4+...+22=?

最初の例は1から22までの総和の計算です（なぜ22なのかは後ほど）。合計は253になります（電卓で確認できます）。結果がすでにわかっているものを計算するのはあまり意味がないですが、サンプルコードとしては十分です。

loop01.s

/* -- loop01.s */
.text
.global main
main:
    mov r1, #0       /* r1 ← 0 */
    mov r2, #1       /* r2 ← 1 */
loop: 
    cmp r2, #22      /* r2と22を比較 */
    bgt end          /* r2 > 22ならendに分岐 */
    add r1, r1, r2   /* r1 ← r1 + r2 */
    add r2, r2, #1   /* r2 ← r2 + 1 */
    b loop
end:
    mov r0, r1       /* r0 ← r1 */
    bx lr

1から22までカウントします。カウンターとしてr2レジスタを使用します。loopラベルの直前でr2レジスタは1で初期化されます。合計がr1レジスタに足されていき、プログラムの最後でr1の中身をr0に移し、合計した結果がプログラムのエラーコードになります（始めからr0レジスタに合計を入れていれば最後のmovは不要になりますが、エラーコードにしたい意図をはっきりさせるためにこのようにしています。）。

loopラベルの次の行でr2を22と比較します（r2は1から22までのカウンターでした）。これによりcpsrが更新され、その次の行でr2が22より大きいかを確認し、真の場合endに分岐してループを終了します。偽の場合は、r2が持っている値をr1に加えます（r1には合計を加算していくのでしたね）。

loopラベルから4行目の行は重要です。既にカウンターr2の現在値を合計を入れるr1に加算し終わっているので、次のループのためにr2の値をインクリメントします。そして、その次の行でループの始めのところまで分岐して戻ります。仮にインクリメントする行を書かないとr2 > 22が常に偽となりbgt endでループを終了させることができなくなるので注意です。

$ ./loop01; echo $?
253

さて、8行目を例えば100にしてみるとします。結果は5050になるべきです。

$ ./loop01; echo $?
186

何が起こったのでしょう？Linuxにおけるプログラムのエラーコードは0から255まで（8 ビット）です。リザルトが5050なら、下位8ビットだけが使われます。5050は2進数で1001110111010ですから、その下位8ビットは10111010、十進数の186となります。では、計算によりr1が5050となったことを確認するにはどうすればいいでしょうか？GDBを使いましょう。

$ gdb loop01
...
(gdb) start
Temporary breakpoint 1 at 0x8390
Starting program: /home/roger/asm/chapter06/loop01 

Temporary breakpoint 1, 0x00008390 in main ()
(gdb) disas main,+(9*4)
Dump of assembler code from 0x8390 to 0x83b4:
   0x00008390 <main+0>:	mov	r1, #0
   0x00008394 <main+4>:	mov	r2, #1
   0x00008398 <loop+0>:	cmp	r2, #100	; 0x64
   0x0000839c <loop+4>:	bgt	0x83ac <end>
   0x000083a0 <loop+8>:	add	r1, r1, r2
   0x000083a4 <loop+12>:	add	r2, r2, #1
   0x000083a8 <loop+16>:	b	0x8398 <loop>
   0x000083ac <end+0>:	mov	r0, r1
   0x000083b0 <end+4>:	bx	lr
End of assembler dump.

mov r0, r1を実行する直前、0x000083acで停止するようにgdbに指示します。

(gdb) break *0x000083ac
(gdb) cont
Continuing.

Breakpoint 2, 0x000083ac in end ()
(gdb) disas
Dump of assembler code for function end:
=> 0x000083ac <+0>:	mov	r0, r1
   0x000083b0 <+4>:	bx	lr
End of assembler dump.
(gdb) info register r1
r1             0x13ba	5050

（※訳注：0x000083acはお使いの環境で異なる値になりますので適宜置き換えてください。）

エラーコードからは確認できませんでしたが、ここには期待通りの値が表示されていますね。

ラベルが関数として認識され奇妙なことが起きていると気づいたかもしれません。この問題については今後の章で取り上げますが、たいていの場合は無害です。

3n+1

少し複雑な別の例を作りましょう。これは有名な3n+1問題でコラッツの予想とも知られています。任意の正の整数nが偶数ならば2で割り、奇数ならば3を掛けてから1を足します。

if (n % 2 == 0)
  n = n / 2;
else
  n = 3*n + 1;

話を進める前に、ARMプロセッサーは2つの数を乗算することもできますが新たな命令mulを知る必要が出てきてしまいます。それは少々回り道になるので、代わりに次の恒等式3 * n = 2*n + nを使用します。まだ2を掛けたり2で割ったりする方法を学んではいませんが、これについては今後の章で扱います。よって今は以下のアセンブリコードのようにすれば動くものと思ってください。

コラッツの予想は、任意の数nについて繰り返しこの手順を適用すると最終的には1になると主張します。理論上はそうならないこともあり得ます。今のところはそのような数は見つかっていませんが、別の方法で証明されていません。前述の手順を繰り返し適用したい場合、プログラムはこのようなことをします。

n = ...;
while (n != 1)
{
  if (n % 2 == 0)
     n = n / 2;
  else
     n = 3*n + 1;
}

コラッツの予想が間違っている場合、無限ループを引き起こすnが存在するはずです。しかし、前述の通りそのような数は見つかっていません。

collatz.s

/* -- collatz.s */
.text
.global main
main:
    mov r1, #123           /* r1 ← 123 */
    mov r2, #0             /* r2 ← 0 */
loop:
    cmp r1, #1             /* r1と1を比較 */
    beq end                /* r1 == 1ならendまで分岐 */

    and r3, r1, #1         /* r3 ← r1 & 1 */
    cmp r3, #0             /* r3と0を比較 */
    bne odd                /* r3 != 0ならoddまで分岐 */
even:
    mov r1, r1, ASR #1     /* r1 ← (r1 >> 1) */
    b end_loop
odd:
    add r1, r1, r1, LSL #1 /* r1 ← r1 + (r1 << 1) */
    add r1, r1, #1         /* r1 ← r1 + 1 */

end_loop:
    add r2, r2, #1         /* r2 ← r2 + 1 */
    b loop                 /* loopまで分岐 */

end:
    mov r0, r2
    bx lr

r1に正の整数nを保持します。今回は123を使用します。123は46ステップで1に到達します。[123, 370, 185, 556, 278, 139, 418, 209, 628, 314, 157, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]。ステップ数をr2レジスタにカウントします。よって、r1は123でr2は0で初期化します（まだステップは実行されていません）。

ループ開始時、8,9行目でr1が1であるか確認します。r1を1と比較し、等しければループを抜けてendに分岐します。

現時点でr1が1ではないことがわかっているので、偶数か奇数かを確認します。そうするために新たな命令andを使います。andはビット単位のAND演算を実行します。偶数は最下位ビット（LSB: least significant bit）が1になり、奇数は0になります。したがって、1とのビット単位AND演算で偶数、奇数はそれぞれ0、1を返します。loopから4行目でビット単位ANDの結果をr3レジスタに保持し、その次の行で0と比較します。もしゼロでないならoddに分岐し、そうでないならevenに続けます。

今、evenの次の行でちょっとした魔法が使われます。これはARMで実行可能な複合操作です。これはmovですが、r1の値を直接r1に入れるのではなく（これでは何も起こりませんね）、最初に算術右シフト（ASR: arithmetic shift right）をr1の値に行います（レジスタ自体ではなく値に行います）。次に、このシフトされた値がr1レジスタに移されます。「算術右シフト」はレジスタのすべてのビットを右にシフトします。この時、右端のビットは事実上破棄され、左端にはシフト前の左端のビットと同じ値がセットされます。ある数を1ビットだけ右にシフトすることは、その数を2で割ることと同じです。したがって、mov r1, r1, ASR #1は実際にはr1 ← r1 / 2をしています。

同じようにoddの次の行でも魔法が使われます。ここではaddを使用します。第1、第2オペランドは必ずレジスタです（宛先オペランドと、第1ソースオペランド）。第3オペランドは論理左シフト（LSL: logical shift left）との複合操作です。第3オペランドの値は左に1ビットだけシフトされます。この時、左端の値は破棄され、右端の値は0にセットされます。これは実質的に値に2を掛けることと同じです。したがって、nを保持しているr1に2*r1を足しているので、これは3*r1つまり3*nです。計算した値は再びr1に保持します。さらに次の行では1をその値に足すので、r1は最後には欲しい値の3*n+1を持つことになります。

今はLSLとASRについてはあまり気にせず、そういうものだと思ってください。後ほどの章でさらに詳しく見ていきます。

最後に、end_loopでステップ数を記録するカウンターr2を更新してループの最初に戻ります。プログラムを終了する前にカウンターの値をr0に移して、1に到達するまでのステップ数を返します。

$ ./collatz; echo $?
46

うまくいきました。

今日はここまで。

追記

Kevin Millikinのコメントの通り（※訳注　原文のサイトにはかつてコメント欄がありました。）通常、ループは上の例のようには実装されません。実際、Kevinはloop01.sのループを実行するためのより良い方法は次の通りだと言います。

loop02.s

/* -- loop02.s */
.text
.global main
main:
    mov r1, #0       /* r1 ← 0 */
    mov r2, #1       /* r2 ← 1 */
    b check_loop     /* ループの最後へ無条件分岐 */
loop: 
    add r1, r1, r2   /* r1 ← r1 + r2 */
    add r2, r2, #1   /* r2 ← r2 + 1 */
check_loop:
    cmp r2, #22      /* r2と22を比較 */
    ble loop         /* r2 <= 22ならループの始めに分岐 */
end:
    mov r0, r1       /* r0 ← r1 */
    bx lr

2つのコードの命令数を数えると、両方とも命令が9つあります。しかし、Kevinの提案を注意深く見ると、ループの最後へ無条件分岐し条件判定を逆にすることで、分岐の1つを省くことができ、ループ自体の命令数を5から4に減らすことができることがわかります。

もっとも、この2番目のバージョンには別の利点もあります。ループ自体には分岐が1つしかなく、条件チェックを担当する2命令に再び到達するのには暗黙的順次実行を利用します。詳しくはこの記事の範囲を超えてしまいますが、分岐命令の実行はプログラムのパフォーマンスに悪影響を与えることがあります。プロセッサーは分岐によるパフォーマンスの低下を軽減する仕組みを備えています（実際、Raspberry Piのプロセッサーにはその仕組があります）。とはいえ、分岐命令を避ければ分岐命令実行によるパフォーマンスの低下の可能性を完全に無くすことができます。

今は、アセンブラのパフォーマンスについてはあまり気にしないようにしていましたが、Kevinのコメントについて解説する価値があると考えました。

次回：7.インデクシングモード