ラズパイでARM入門（10. 関数その２ スタック）

前回：9. 関数その１ 次回：11.条件付き実行制御
目次（記事一覧）

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

第9章では関数について紹介し、他の関数とうまく連携するために従う必要のある規則について学びました。またスタックについても、関数が専有するメモリ領域である、といった簡単な知識を得ました。本章では、スタックと関数を使う上でのスタックの重要性について詳しく説明します。

関数の動的アクティブ化

関数の利点の１つは呼び出しが1回より多く行えることです。しかし、「1回より多く」には小さな罠が隠されています。制限なく誰でも関数を呼び出せるため、関数が自分自身を呼び出すこともできます。これは、再帰を使うときに起こります。

再帰の典型例は、nの階乗n!です。階乗はC言語で次のように書けます。

int factorial(int n)
{
   if (n == 0)
      return 1;
   else
      return n * factorial(n-1);
}

fuctorial関数の定義は1つだけですが、場合によっては何度も呼び出されることに注目してください。例えば、A→Bが「AがBを呼び出す」の意味だとして、factorial(3) → factorial(2) → factorial(1) → factorial(0)のようなことが起こります。ある関数が呼び出されてからリターンされていないとき、その関数は「動的アクティブ化状態」である、と定義しましょう。factorial関数は呼び出されるたびに動的にアクティブ化されます。同時に複数の関数が動的アクティブ化状態にあることもあります。動的アクティブ化状態の関数のすべての集合は、現在処理が行われている関数とそれを呼び出した動的アクティブ化状態の関数の集合を含みます。

さて、自分自身を呼び出す関数があるとします。どんな問題があるでしょうか？関数に従うべき規則がなければ問題はありませんが、実際は規則があります。さっと関数の規則をおさらいしてみましょう。
関数の規則：

• r0、r1、r2、r3に限り自由に変更できる。
• 関数の開始時におけるlrの値はどこかに保持する必要がある。なぜなら、関数を離れる（呼び出し元にリターンする）ためにそれが必要となるからである。
• 他のすべてのレジスタ、つまりr4からr11及びspは変更できるが、関数を離れるにあたり元の値に復元しなくてはならない。

第9章では、lrの保存にグローバル変数を使いました。しかし、factorial(3)でグローバル変数を使おうとすると、factorial関数の次のアクティブ化で上書きされてしまいます。この場合、factorial(0)がそのグローバル変数への最後の上書きを行い、factorial(0)からfactorial(1)にリターンをした後、処理の流れはfactorial(1)にずっと留まり続けます。

よって、少なくとも動的アクティブ化ごとにlrの値を維持する何らかの方法が必要となりそうです。また、lrだけではなくr4からr11までのレジスタを使う場合は、それらについても動的アクティブ化ごとに保存する必要がでてくるため、グローバル変数はこの場合も不適切になります。ここで、スタックが活躍します。

スタック

計算機科学では、スタックはデータ構造（であり興味を持つ特徴を提供するデータを整理する方法）です。一般的にスタックには、「トップ（一番上）にアクセスする」「トップにプッシュする」「トップからポップする」の３つの操作があります。このように純粋なスタックの場合、操作できるのはトップだけですが、ARMアセンブリ言語の場合はトップ以外の多くの要素にもアクセスできます。

さて、スタックとは何でしょうか？すでに第9章では、スタックは関数が専有するメモリ領域だと言いました。今これをもう少しうまく言い換えると、「スタックとは、現在の動的アクティブ化状態の関数が専有するメモリ領域である」になります。では、どのようにスタックを制御するのでしょうか？第9章では、レジスタspはstack pointerの略であると言いました。このレジスタはスタックのトップのアドレスを含みます。動的アクティブ化状態の関数が所有するメモリ領域は、現在のspの値と関数開始時のspの値の間に含まれるバイトの範囲です。その領域を関数の（より正確には動的アクティブ化状態の関数の）ローカルメモリと呼びます。関数の開始時に保存し終了前に復元する必要があるデータはすべてローカルメモリに置きます。また、（動的アクティブ化状態の）関数のローカル変数もローカルメモリに保存します。

関数は、スタックを扱うときにいくつかのルールに従う必要があります。
スタックを使うときのルール：

• スタックポインタは常に4バイト境界に置きます。これは絶対に必要です。しかしながら、AAPCS（Procedure Call Standard for the ARM architecture）の場合、スタックポインタは8バイト境界に置く必要があります。そうしないと、AAPCSがパブリックインターフェイスとして呼び出すもの（つまり、他の人が記述したコード）を呼び出すときに異常なことが起こるかもしれません。
• 関数終了時のspの値は関数開始時の値と同一である必要があります。

最初のルールは、たいていの場合アドレスに4バイト境界を強制するARMの規則と一致しています。AAPCSでは、さらに8バイト境界の制限がかかります。２つ目のルールは、ローカルメモリをどれほど大きく確保しても、必ず関数の終了時に消さねばならないことを意味します。関数のローカル変数はその関数の終了後保持する必要がなくなるため、このことは重要です。

スタック、つまりローカルメモリのサイズを定義する方法は慣習で決まっています。スタックは上向きか下向きのどちらかに成長できます。上向きに成長する、とはspレジスタの値を増やしてローカルメモリを大きくすることを意味します。下向きに成長する場合、spの値をローカルストレージのサイズと同じ数のバイト分、減らすという逆のことをします。Linux ARMでは、スタックは下向きにゼロに向かって（ただしゼロに達することはありません）成長します。ローカル変数のアドレスは、32ビットの範囲でとても大きな値であり、通常$2^{32}$に近い値です。

スタックを使うときのもう１つの慣習は、spレジスタが含むアドレスはスタックのトップかそれより数バイト上を指すのかというものです。Linux ARMでは、spレジスタはスタックのトップを直接指します。つまり、spが指すアドレスのメモリの中には現在使用中のデータが入っています。

ここまでで、スタックが下向きに成長し、spが必ずスタックのトップを指す必要があることを学びました。よって、ローカルメモリを大きくするにはspを減少させるだけで十分です。ローカルメモリの範囲は、現在のspの値から関数開始時のspの値までです。lrはこれまでグローバル変数に保存してきましたが、これをスタックに保存する方法を見てみましょう。

sub sp, sp, #8  /* sp ← sp - 8. スタックを8バイト増やす */
str lr, [sp]    /* *sp ← lr */
... // 関数の何かの処理
ldr lr, [sp]    /* lr ← *sp */
add sp, sp, #8  /* sp ← sp + 8. /* スタックを8バイト減らす
                                これでspは初期値に復元される */
bx lr

行儀良い関数は、spを変更することはあっても終了時に関数開始時と同じであることを保証します。上の例でも、最初にspから8を引きますが、最後には8を足して元に戻しています。

上の例は問題なく動作します。しかし、第8章にてロード命令、ストア命令でインデクシングモードを利用したことを覚えているかもしれません。最初の２つの命令がプレインデクシングモードとまったく同じに動作することに注目です。最初にspを更新し、そしてspの指すメモリにlrをストアします。これはまさにプレインデクシングです。最後の２つの命令も同様です。最初にspが指すメモリにlrをロードし、そしてspを減少させます。これはまさにポストインデクシングです。

str lr, [sp, #-8]!  /* preindex: sp ← sp - 8; *sp ← lr */
... // 関数の何かの処理
ldr lr, [sp], #+8   /* postindex; lr ← *sp; sp ← sp + 8 */
bx lr

お気づきの通り、このアドレッシングモードはこの種の作業に役立てるため発明されました。単一の命令を使用するほうが、コードサイズの観点で適切です。これとは無関係に見えるかもしれませんが、スタックの増減の管理は関数を作るときほぼすべての場合に必要になると心に留めておいてください。

スタックで階乗

階乗関数を実装しましょう。

最初に、２つの数字を乗算する新たな命令、mulを学ぶ必要があります。使い方は、mul Rdest, Rsource1, Rsource2です。乗算に32ビット値を２つ用いると計算結果に64ビットが必要となることに注意です。この命令は、オペランドの下位32ビットだけを使って計算します。この例では64ビット値を使用しないため、階乗を計算できる最大の値は12です（13!だと$2^{32}$を超えます）。例を単純にするため、入力値が13未満であることを確認しません（とはいえ、この確認を例に付け足すことをお勧めします）。ARMv6以前のバージョンのARMアーキテクチャでは、この命令はRdestとRsource1を同じレジスタにはできませんでした。このため、GNUアセンブラは-march=armv6を渡さないと警告を出力することがあります。

factorial01.s

/* -- factorial01.s */
.data

message1: .asciz "Type a number: "
format:   .asciz "%d"
message2: .asciz "The factorial of %d is %d\n"

.text

factorial:
    str lr, [sp,#-4]!  /* lrをスタックのトップにプッシュ */
    str r0, [sp,#-4]!  /* r0をスタックのトップにプッシュ */
                       /* 注意：この時点でspは8バイト境界にある */
    cmp r0, #0         /* r0と0を比較 */
    bne is_nonzero     /* r0 != 0 なら分岐 */
    mov r0, #1         /* r0 ← 1. リターン値を格納 */
    b end
is_nonzero:
                       /* これからfactorial(n-1)を呼ぶ準備 */
    sub r0, r0, #1     /* r0 ← r0 - 1 */
    bl factorial
                       /* 呼び出し後r0に(n-1)!の値が入る */
                       /* スタックに保存しておいたr0の値をr1にロード */
    ldr r1, [sp]       /* r1 ← *sp */
    mul r0, r0, r1     /* r0 ← r0 * r1 */
    
end:
    add sp, sp, #+4    /* スタックに保存したr0の値を破棄 */
    ldr lr, [sp], #+4  /* スタックのトップからlrにポップ */
    bx lr              /* factorial を離れる */

.global main
main:
    str lr, [sp,#-4]!            /* lrをスタックのトップにプッシュ */
    sub sp, sp, #4               /* スタックに4バイト整数用の場所を作る */
                                 /* この4バイトにユーザの入力値を入れる */
                                 /* 注意：この時点でスタックは8バイト境界 */
    ldr r0, address_of_message1  /* &message1をprintfの第1パラメーターにセット */
    bl printf                    /* printf呼び出し */

    ldr r0, address_of_format    /* &formatをscanfの第1パラメーターにセット */
    mov r1, sp                   /* スタックのトップをscanfの第2パラメーターにセット */
    bl scanf                     /* scanf呼び出し */

    ldr r0, [sp]                 /* scanfが読み取った整数をr0にロード */
                                 /* つまり、factorialの第1パラメーターとなる */
    bl factorial                 /* factorial呼び出し */

    mov r2, r0                   /* factorialの返り値をr2にムーブ */
                                 /* つまりprintfの第3パラメーターとなる */
    ldr r1, [sp]                 /* scanfが読み取った整数をr1にロード */
                                 /* つまりprintfの第2パラメーターとなる */
    ldr r0, address_of_message2  /* &message2をprintfの第1パラメーターにセット */
    bl printf                    /* printf呼び出し */


    add sp, sp, #+4              /* scanfの読み取った値を破棄 */
    ldr lr, [sp], #+4            /* スタックのトップをlrにポップ */
    bx lr                        /* mainを離れる */

address_of_message1: .word message1
address_of_message2: .word message2
address_of_format: .word format

コードの大部分は非常に簡単です。mainとfactorialの両方の関数とも、スタックのトップにlrの保存用とは別に追加で4バイトを割り当てます。factorialはその領域にr0の値を保存します。再帰呼び出しの際（第1パラメーターのためと関数呼び出し後の返り値のために２回）上書きされてしまうためです。そして、mainはその領域にユーザーの入力値を保存します（第９章ではこの場合グローバル変数を使いました）。

ここでのスタックは純粋なスタックと同様に、最後に積まれた（トップにプッシュされた）要素が最初にスタックから取り出され（トップからポップされ）ます。このことを覚えておくことが大切です。上の例では、lrをストアし、さらに追加で4バイトの整数用の場所を作りました。これはスタックのため、スタックを元の状態に戻すため、逆の順序が必要となります。最初に整数を破棄し、そしてlrを復元します。subで整数のためのスタックストレージを予約し、反対の操作であるaddでそのストレージを破棄していることにも注意してください。

改善できる点

データをスタックにプッシュするおよびデータをスタックからポップするための命令数は、データ項目の数に比例して増加します。ARMは組み込みシステムを対象に設計されているため、ARMの設計者はスタックの管理に必要な命令数を減らすための方法を考案しました。ldm（load multiple 複数ロード）命令とstm（store multiple 複数ストア）命令です。

この２つの命令はかなり協力であり、１つの命令で多くのことを実行できます。構文は次の通りです。（波括弧{}に閉じられた要素を省略することもありますが、命令の挙動が変化します。）

ldm addressing-mode Rbase{!}, register-set
stm addressing-mode Rbase{!}, register-set

addressing-modeについては後ほど検討します。Rbaseはregister-setに対してロードまたはストアするのに使うベースアドレスです。ARMの16個のレジスタはどれもregister-setに指定できます（ただしstmではpcは指定できません）。命令を実行すると、register-set中のレジスタの数だけアドレスが生成されます。そして、昇順に並べられた各レジスタと、同じく昇順に並べられた各アドレスがペアとなります。つまり、最小の数字のレジスタが最小のメモリアドレスとペアになり、最大の数字のレジスタが最大のメモリアドレスとペアになります。その後、レジスタ-アドレスの各ペアはロードまたはストアのメモリ操作に使用されます。「!」の指定はRbaseが上書きされることを意味します。上書きする値はaddressing-modeに依存します。

レジスタがレジスタ番号に基づいてアドレスとペアになる場合、常に同じ方法でロードおよびストアされるように見えます。例えば、r4、r5、r6を含んでいるregister-setは、常にr4を命令が生成したアドレスの最小のアドレスに、r6を最大のアドレスにストアします。しかしながら、最小のアドレスまたは最大のアドレスとみなすものは指定することができます。Rbaseは実際のところ複数ロード/ストアにおける最大のアドレスまたは最小のアドレスのどちらでしょうか？これは、addressing-modeが制御する２つの側面のうちの１つです。２つ目の側面は、メモリ操作の前後どちらでアドレスが変化するのかに関するものです。

Rbaseの値を最大のアドレスとみなす場合、最初にRbaseをレジスタの数が要求するバイト数（レジスタの数の4倍）だけ減少させ最小のアドレスを作ります。そして、それぞれのレジスタを連続的に最小アドレスから、レジスタ番号昇順でロードまたはストアします。このアドレッシングモードを減少（decreasing）モードと呼びdで指定します。逆に、Rbaseを最小アドレスとみなす場合は最初からすでに最小のアドレスがあるため少し簡単です。これまで通り、各レジスタをレジスタ番号昇順にロードまたはストアするだけです。このアドレッシングモードは増加（increasing）モードと呼びiで指定します。

各ロードまたはストアで、メモリ操作のために生成されたアドレスはメモリ操作の後（after）または前（before）に更新されます。これはそれぞれa、bを使って指定できます。

「!」を指定すると、命令の後でRbaseは、増加モードの場合、生成されたアドレスのうち最大のもので上書きされ、減少モードの場合、生成されたアドレスのうち最小のもので上書きされます。メモリ操作の後で更新するモード（「a」モード）の場合、Rbaseの最終的な値は、最後の加算または減算を含みます。

したがって、アドレッシングモードにはia、ib、da、dbの４種類があります。これらのアドレッシングモードはstmおよびldm命令の接尾辞として指定されます。よって、全命令は、stmia、stmib、stmda、stmdb、ldmia、ldmib、ldmda、ldmdbとなります。過度に複雑に思えますが、この８つのモードすべてを使う必要はありません。関心があるのは２つだけです。

スタックに何かをプッシュする場合、実際にはスタックポインタを減少させます（Linuxではスタックは下向きに成長するため）。より正確には、最初にスタックポインタを必要なバイト数だけ減少させてから、今計算されたばかりのスタックポインタに基づき実際のストアを行います。したがって、スタックにプッシュする場合の適切なaddressing-modeはstmdbです。逆に、スタックからポップする場合はロードの実行の後でスタックポインタを増やすので、ldmiaを使います。
（※訳注　減少モードdの説明の「最初にスタックポインタをレジスタの個数分減少させる」とbの説明の「メモリ操作の前にスタックポインタを増減する」はうまく噛み合ってないように思われます。ここは「増加モードも減少モードもレジスタ番号が大きいほどレジスタのペアとなるアドレスも大きくなる」程度にとらえ、実際の減少モードは「スタックポインタの減少とメモリ操作が交互に行われる」と理解した方が良さそうです。）

再び階乗

これら2つの命令を実例で説明する前に、少しだけ階乗の例を書き直します。

階乗のコードを見てみると、n * factorial(n-1)を計算するときにr0の初期値が必要になる瞬間があります。nの値は、関数開始時のときr0に入っていますが、r0は呼び出した関数によって自由に変更できてしまいます。上の階乗の例では、r0のコピーをスタックに保存することを選びました。そして後から、乗算の計算直前にそれをスタックからr1にロードしました。

階乗の２つ目のバージョンでは、r0の初期値のコピーをr4に保存します。しかし、r4は関数終了時に値が復元されなければならないレジスタです。そのため、r4レジスタの値を関数の最初にスタックへと保存します。終了時にスタックから復元します。このようにしてr4を行儀良い関数であるためのルールを破ることなく使うことができます。

factorial:
    str lr, [sp,#-4]!  /* lrをスタックのトップにプッシュ */
    str r4, [sp,#-4]!  /* r4をスタックのトップにプッシュ */
                       /* この時点でspは8バイト境界にある */
    mov r4, r0         /* r0の初期値のコピーをr4に保存 */


    cmp r0, #0         /* r0と0の比較 */
    bne is_nonzero     /* r0 != 0なら分岐 */
    mov r0, #1         /* r0 ← 1 リターン値をセット */
    b end
is_nonzero:
                       /* factorial(n-1)を呼ぶ準備をする */
    sub r0, r0, #1     /* r0 ← r0 - 1 */
    bl factorial
                       /* 呼び出し後r0に(n-1)!の値が入る */
                       /* r4に保持しておいたr0の初期値をr1にコピー */
    mov r1, r4         /* r1 ← r4 */
    mul r0, r0, r1     /* r0 ← r0 * r1 */

end:
    ldr r4, [sp], #+4  /* スタックのトップからをr4にポップ */
    ldr lr, [sp], #+4  /* スタックのトップからをlrにポップ */
    bx lr              /* factorialを終了する */

プログラムの残りを変更する必要がないことに注意してください。これは関数の良いところです。

上の階乗の例から２箇所抜粋して見てましょう。

    str lr, [sp,#-4]!  /* lrをスタックのトップにプッシュ */
    str r4, [sp,#-4]!  /* r4をスタックのトップにプッシュ */

    ldr r4, [sp], #+4  /* スタックのトップからをr4にポップ */
    ldr lr, [sp], #+4  /* スタックのトップからをlrにポップ */

ではこれらを、さきほど説明したstmdbとldmiaで置き換えてみましょう。

    stmdb sp!, {r4, lr}    /* r4とlrをスタックのトップにプッシュ */

    ldmia sp!, {r4, lr}    /* スタックのトップからをlrとr4にポップ */

注意：register-set内のレジスタの順番は実際は関係ありませんが、プロセッサーはレジスタをレジスタ番号昇順に処理するため、書くときも昇順に並べるべきです。register-setを昇順に並べて書かない場合、GNUアセンブラは警告を出力します。lrはr14の別名のため、r4の後に書かなくてはなりません。このように、r4がlrより低いアドレスとペアになるため、書き換える前と書き換えた後のコードは100％同等です。そのため、スタックが下に向かって成長することを念頭に置けば、r4の初期値を格納するfactorialのスタックのトップは最小のアドレスになることがわかります。

stmdb sp!とldmia sp!を覚えておくのは少し大変です。また、それらは関数の開始と終了時に使われることが多いです。そのため、GNUアセンブラは２つのニーモニックpushとpop（それぞれstmdb sp!、ldmia sp!に対応）を提供します。これらは、実際のARM命令ではなく、覚えやすい便利なニーモニックであることに注意してください。

    push {r4, lr}

    pop {r4, lr}

今日はここまで。

次回：11.条件付き実行制御