計算機システム II ・第 4 回 2015 年 10 月 15 日 今回の内容 4.1 分岐命令 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4–1 4.2 サブルーチンの呼び出しとスタック領域 . . . . . . . . . . . . . . . . . . . . . 4–2 4.3 付録 : Intel 64 アーキテクチャ 64 bit モードの分岐命令の概要 . . . . . . . . . 4–6 4.1 分岐命令 CPU は、基本的には、メモリ中に並んでいる機械語命令の列をアドレス順に実行していきます。 CPU は、プログラムカウンタが記憶しているメモリアドレスから機械語命令を読み取り、その命 令を実行するということを繰り返していきますが、CPU が命令を 1 つ読み取ると、その実行を行 うとともに、読み取った機械語命令の大きさだけ、プログラムカウンタの値を増やします。このた め、その命令の実行が終わると、CPU は、その命令が格納されていたメモリアドレスの範囲の次の アドレスから、次に実行すべき命令を読み取ることになります。 以上が CPU の行う作業の基本ですが、CPU の命令セットには、プログラムカウンタの値を変 更するような命令が用意されており、その命令の次に実行する命令を読み取るメモリアドレスを変 更することができるようになっています。このような命令を分岐命令 (branch instruction) あるい は ジャンプ命令 (jump instruction) と呼びます。また、分岐命令の実行によってプログラムカウ ンタの値が変更されて、機械語のプログラムの実行の流れが変ることを分岐、またはジャンプと言 います。 無条件分岐命令と条件分岐命令 分岐命令には、無条件に分岐する (プログラムカウンタの値を変更する) 無条件分岐命令と、何らか の条件が満たされている場合にのみ分岐する 条件分岐命令があり、後者は、たとえば、ゼロ (Zero)、 サイン (Sign)、キャリー (Carry)、オーバーフロー (Overflow) などのフラグの状態を調べて、分岐 するかしないかを判断します。 多くの CPU では、2 つの整数値 a と b の間で a − b の計算を行う演算命令を実行すると、その 結果に応じてこれらのフラグが設定され、この演算に続いて、条件分岐命令を実行することで、a と b が特定の大小関係にあるときのみ分岐を起こさせることができます。たとえば、次の表にあ る 10 通りの状態それぞれに対して、その状態にあるときのみ分岐する条件分岐命令が用意されて います。 フラグの状態 a、b が符号なし整数の場合 a、b が符号付き整数の場合 Zero = 1 Zero = 0 Carry1 = 1 Carry = 0 Carry = 0 かつ Zero = 0 Carry = 1 または Zero = 1 1 Sign ̸= Overflow Sign = Overflow Sign = Overflow かつ Zero = 0 Sign ̸= Overflow または Zero = 1 a − b 演算に対する意味 a=b a ̸= b a<b a> −b a>b a< −b CPU によっては、Carry = 0 で、減算での最上位ビットから繰り下がりの発生を示し、Carry = 1 で、繰り下がり 4–1 分岐命令のオペランド 分岐命令は、通常、分岐先のメモリアドレスを指定するためのオペランドを持ちます。前回紹介し た、絶対、レジスタ間接、プログラムカウンタ相対、メモリ間接などのアドレッシングモードのオ ペランドで分岐先のアドレスを指定します。分岐命令で使用されるのはメモリオペランドを指定 するアドレッシングモードのみです。指定されたメモリオペランドのアドレスが分岐先となりま す2 。即値やレジスタ直接アドレッシングはメモリオペランドを示すものではありませんので分岐 命令のオペランドにはなりません。 無条件分岐命令に比べると、条件分岐命令で使用可能なアドレッシングモードは限定されてい るのが普通です。無条件分岐命令のアドレッシングモードが豊富に用意されている場合でも、条件 分岐命令のアドレッシングモードは、プログラムカウンタ相対アドレッシングのみというようなこ ともあります。 プログラムカウンタ相対アドレッシングは特に重要なアドレッシングモードです。このモード の分岐命令のみを使用することで、どのメモリアドレスに置いても正しく動作する機械語プログラ ムを作成することが可能になります3 。もし、分岐先アドレスが絶対アドレッシングで指定されて いると、機械語プログラムの置かれるアドレスが変わる毎に、分岐先のアドレスを変更しなくては なりません。 4.2 サブルーチンの呼び出しとスタック領域 C 言語における関数呼び出しの場合など、機械語プログラムがサブルーチンを呼び出す際には、呼 び出されるサブルーチンプログラムの先頭に分岐するだけではなく、サブルーチンの実行終了後に 呼び出した側のプログラムに戻って来て (これも分岐の一種) 呼び出した側の機械語プログラムを 続行することが必要となります。どのアドレスに戻ってくるかは、どこからそのサブルーチンが呼 び出されたかによって変わってきますので、固定したアドレスを分岐先に指定して呼び出し元に戻 ることはできません。 そこで、サブルーチンを呼び出す側のプログラムは、戻り先となるアドレスを、呼び出されるサ ブルーチンの側に何らかの方法で伝えてやる必要があります。戻り先のアドレスは、サブルーチン を呼び出す機械語命令の次の機械語命令が置かれたアドレス、つまり、その時点のプログラムカウ ンタの値となります。この戻り先となるアドレスのことをリターンアドレスと呼びます。 リターンアドレスを伝える最も単純な方法は、それを特定のレジスタに格納しておくことです。 呼び出されたサブルーチンの側では、この特定のレジスタを使って (レジスタ間接アドレッシング モードの分岐命令で) 呼び出し元へ戻ることができます。ただし、この方法の難点は、呼ばれた側 のサブルーチンが、また別の (場合によっては自分自身を再帰的に) 呼び出す場合です。この呼び が発生しなかったことを示すものもあります。その場合、この表中の Carry の 0/1 はすべて逆になります 2 そのアドレスに格納されているデータが分岐先アドレスとなるのではありません。 3 どのメモリアドレスに配置しても正しく動作するような機械語プログラムのことを再配置可能 (relocatable) なプロ グラムと言います。部品となる機械語プログラムを多数つなぎ合わせて 1 つの大きなプログラムを組み立てる際には、 部品となる機械語プログラムが再配置可能となっていることが重要です。さらに、同一の物理アドレスに格納された機 械語プログラムを、CPU のアドレス変換機構を利用して、複数のプロセスが仮想アドレス空間のそれぞれ異なる場所に 対応させて共有するためには、その機械語プログラムは再配置可能であることが必須となります。 4–2 出しで、また、その特定のレジスタを使用しなければなりませんから、そこに格納されている (その サブルーチン自身の) リターンアドレスを、どこか別の場所に退避しておかなければならなくなり ます。 リターンアドレスに限らず、サブルーチンが呼び出されると、そのサブルーチンが使用するメモ リ領域4 が新たに必要となるのが普通です。何重にもサブルーチンが呼び出されることを考えると、 この領域はサブルーチンが呼び出される度に増加していき、サブルーチンからその呼び出し元に戻 る度に減少し元の状態に戻っていくことになります。 スタック領域とスタックポインタ 通常、(仮想) アドレス空間の一部のメモリ領域を、このような用途に割り当てて、その端から5 少し ずつ使用していきます。この領域はスタック領域6 (stack area) と呼ばれ、その領域の内、(その時) 使用されている部分をスタック (stack) と呼びます。多くの CPU は、スタック領域の内、その端か らどこまでを使用しているのかを特定のレジスタに記憶するようにしています。このレジスタは 一般にスタックポインタ (stack pointer) と呼ばれ、汎用レジスタの内の 1 つとなっている場合もあ れば、別の特殊なレジスタとなっていることもあります。 スタック領域を使用する方法には 2 通りの方式があり、その 1 つは、スタック領域の先頭からア ドレスの大きい方へ使用していく方式です。この場合、スタックポインタは、通常、使用している 範囲の終り (使用中の最後のアドレスの次) のアドレスを記憶します。もう 1 つは、スタック領域 の末尾からアドレスの小さい方へ使用していくもので、スタックポインタは、通常、使用している 範囲の先頭のアドレスを記憶します7 。どちらの場合でも、割り当てを開始した側の端をスタック の底 (bottom) とよび、最後に割り当てた側 (スタックが伸びていく方向) の端をトップ (top) と呼 びます。 プッシュ命令とポップ命令 スタックに対する最も基本的な命令は、プッシュ (push) 命令とポップ (pop) 命令です。これらは データ転送命令の一種で、通常、それぞれ 1 つのオペランドをとり、次のような操作を行います。 プッシュ命令 オペランドのデータ大きさ (バイト数) だけスタックを拡大してできる新しい領域 に、オペランドのデータをコピーします。このデータがスタックの新しいトップとなります。 プッシュ命令は自動増減分付きレジスタ間接アドレッシングによるストア命令の一種です。 アドレスが大きくなる方向へスタックが伸びる方式では、スタックポインタの現在の値をメ モリアドレスとしてオペランドのデータをストアし、その後、スタックポインタの値をその データの大きさだけ増やします。また、アドレスが小さくなる方向へスタックが伸びる方式 4 C 言語の関数定義内で宣言された自動変数など。 5 アドレスの小さい方の端 (領域の先頭) から大きい方へ使用していく場合と、アドレスの大きい方の端 (領域の末尾) から小さい方へ使用いしていく場合の 2 通りがあります。Intel の IA-32 や Intel 64 アーキテクチャでは後者が採用さ れています。 6 セグメント方式のアドレス変換機構を使用する場合は、通常、独立したセグメントとします。 7 Intel の IA-32 や Intel 64 アーキテクチャを含め、こちらの方が主流です。 4–3 の場合は、ストアの前にスタックポインタの値を減らし、その新しいスタックポインタの値 をデータの格納先のアドレスとして使用します。 プッシュ命令のオペランド α アドレスが 大きくなる 方向 @ @ ←スタック ポインタ ? @ @ @ R @ α ←スタック ポインタ ⇒ プッシュ命令の効果 (アドレスが小さくなる向きに伸びるスタックの例) ポップ命令 スタックのトップに位置するデータをオペランドへコピーするとともに、その大きさ だけスタックを縮めます。ポップ命令は自動増減分付きレジスタ間接アドレッシングによる ロード命令の一種です。アドレスが大きくなる方向へスタックが伸びる方式では、ロードす る前に、まず、オペランドのデータの大きさだけスタックポインタの値を減らし、その新しい スタックポインタの値をメモリアドレスとして使用します。また、アドレスが小さくなる方 向へスタックが伸びる方式の場合は、スタックポインタの現在の値をメモリアドレスとして ロードを行い、その後で、スタックポインタの値を増やします。 ポップ命令のオペランド アドレスが 大きくなる 方向 α α ←スタック ポインタ ? ←スタック ポインタ ⇒ ポップ命令の効果 (アドレスが小さくなる向きに伸びるスタックの例) レジスタの値のスタックへの退避 機械語プログラムがサブルーチンを呼び出す場合、特定のレジスタにリターンアドレスを格納する 方法を紹介しましたが、呼ばれたサブルーチンが、さらにサブルーチンを呼び出す場合は、この特 定のレジスタの値を退避する必要があることを指摘しました。このような際の、レジスタに置かれ た値の退避先としてスタックが用いられます。 まず、そのレジスタの値をスタックにプッシュし退避しておきます。そして、同じレジスタに新 しいリターンアドレスを書き込んでサブルーチンに分岐します。そのサブルーチンから戻って来 たところで、退避しておいた値をスタックから同じレジスタにポップすれば、そのレジスタの元の 値 (このサブルーチン自身のリターンアドレス) を復元することができます。 4–4 CPU には限られた数のレジスタしか内蔵されていませんから、計算の途中結果などを格納する ために必要な一時的な記憶領域が不足しがちになります。また、複雑な計算の途中で、その途中結 果を記憶したまサブルーチンを呼び出さなければならない場合もありますので、そうなると、せっ かくレジスタに記憶していた途中結果を、呼び出したサブルーチンが壊してしまうことになりかね ません。スタックへのデータのプッシュ (退避) やポップ (復元) は、機械語プログラムにおける非 常に基本的な道具となっています。 呼び出し命令と復帰命令 サブルーチンの呼び出しの際のリターンアドレスを特定のレジスタに格納してしまうと、サブルー チンの呼び出しの度に、そのレジスタの値のプッシュやポップが必要となってしまいますので、ス タックを直接使ってリターンアドレスをサブルーチンに伝える方式が採用されることがよくあり ます8 。 スタックを直接利用してリターンアドレスを伝える方式の場合、サブルーチンを呼び出す側で は、呼び出したいサブルーチンに分岐する前に、リターンアドレスをスタックへプッシュしておき ます。呼び出されたサブルーチンの側では、呼び出し元へ戻る際にスタックからリターンアドレス をポップし、そのアドレスへ分岐します。 多くの CPU には、この 2 種類の作業を行うことのできる特別な分岐命令がそれぞれ用意されて います。 呼び出し命令 call 命令とも呼ばれる命令で、スタックを使ってサブルーチンを呼び出す際に必要 な 2 つの操作、つまり、リターンアドレスのプッシュと、指定したアドレスへの分岐をまとめ て行います。プッシュされるリターンアドレスは、この呼び出し命令の次の命令が置かれた アドレスとなります。通常、分岐先アドレスは、無条件分岐命令と同様に、オペランドで、絶 対、レジスタ相対、プログラムカウンタ相対、メモリ間接などのアドレッシングモードで指定 します。 復帰命令 return 命令とも呼ばれる命令で、サブルーチンから呼び出し元へ戻る際に必要な 2 つの 操作、つまり、リターンアドレスのポップと、ポップして得られたアドレスへの分岐をまとめ て行います9 。 8 スタックを直接使ってリターンアドレスをサブルーチンに伝える方式でも、サブルーチンを全く呼び出すことのな いサブルーチンを呼び出す際に限って、レジスタにリターンアドレスを格納する方法が使われる場合があります。 9 return 命令は、プログラムカウンタをデスティネーションオペランドとしたポップ命令と考えることができます。 4–5 4.3 付録 : Intel 64 アーキテクチャ 64 bit モードの分岐命令の概要 Intel 64 アーキテクチャの 64 bit モードの命令セットには以下のような分岐命令群が用意されてい ます。 各命令のアセンブリ言語 (情報処理実習室の Linux 環境)での書式 主要な分岐命令 jmp *α jmp a メモリオペランド α の値のアドレスへ分岐する アドレス a にプログラムカウンタ相対モードで分岐する je a jne a jb a jae a ja a jbe a jl a jge a jg a jle a js a jns a jo a jno a ZF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する ZF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する CF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する CF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する CF = 0 かつ ZF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する CF = 1 または ZF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する SF ̸= OF なら、アドレス a にプログラムカウンタ相対モードで分岐する SF = OF なら、アドレス a にプログラムカウンタ相対モードで分岐する SF = OF かつ ZF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する SF ̸= OF または ZF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する SF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する SF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する OF = 1 なら、アドレス a にプログラムカウンタ相対モードで分岐する OF = 0 なら、アドレス a にプログラムカウンタ相対モードで分岐する call *α %rip (プログラムカウンタ) の現在の値 (次の機械語命令の置かれている 64 bit 長のアド レス) をスタックにプッシュし、メモリオペランド α の値のアドレスへ分岐する。 %rip (プログラムカウンタ) の現在の値 (次の機械語命令の置かれている 64 bit 長のアド レス) をスタックにプッシュし、アドレス a にプログラムカウンタ相対モードで分岐する スタックからアドレス (64 bit 長) をポップし、そのアドレスへ分岐する。 call a ret ただし、ZF はゼロフラグ、SF はサインフラグ、CF はキャリーフラグ、OF はオーバーフローフラグ で、減算に対しては、最上位ビットでの繰り下がりの発生を CF = 1 で示します。また、call 命令 や ret 命令では、レジスタ %rsp がスタックポインタとして使用されます。 分岐命令のアドレッシングモード jmp *α や call *α の * は間接アドレッシングであることを 示しています。α の部分には、即値以外のアドレッシングモードが使用できますが、実際に、分岐 先アドレスとなるのは、α に格納されている値です。このため、α 自身がレジスタ直接アドレッシ ングであっても、*α ではレジスタ間接アドレッシングを指定したことになり、そのレジスタに格 納されているアドレスに分岐します。 一方、jmp a, je a, . . . , call a では、a で絶対アドレスを指定しますが、実際には、この命令の 次の命令が置かれるアドレス10 から a までの変位を指定したプログラムカウンタ相対アドレッシ ングで分岐する命令となります。 以下は、いろいろなアドレッシングモードを使用した分岐命令の例です。 10 IA-32 や Intel 64 アーキテクチャでは、命令の実行の前にプログラムカウンタが更新されますので、分岐命令が実 行されるときのプログラムカウンタの値はその分岐命令の次に置かれている命令のアドレスとなっています。 4–6 jmp *rax レジスタ rax に格納されているアドレスに分岐する (レジスタ間接ア ドレッシング) jmp *(rax) レジスタ rax に格納されているメモリアドレスに格納されているアド レスに分岐する (レジスタメモリ間接アドレッシング) jmp *0x12345678 メモリアドレス 0x12345678 に格納されているアドレスに分岐する (絶 対メモリ間接アドレッシング) jmp 0x12345678 アドレス 0x12345678 に (プログラムカウンタ相対モードで) 分岐する je 0x12345678 ZF = 1 の場合に限ってアドレス 0x12345678 に (プログラムカウンタ 相対モードで) 分岐し、ZF = 0 の場合は何もしない 条件分岐命令のニーモニック 前ページの表中の条件分岐命令のニーモニック je, jne, . . . , jno は、それぞれ以下のような意味を持っています。 je Jump if Equal jne Jump if Not Equal jb Jump if Below jae Jump if Above or Equal ja Jump if Above jbe Jump if Below or Equal jl Jump if Less jge Jump if Greater or Equal jg Jump if Greater jle Jump if Less or Equal js Jump if Sign jns Jump if Not Sign jo Jump if Overflow jno Jump if Not Overflow je から jle までの 10 通りの条件分岐命令のニーモニックは、cmp α, β や sub α, β という命令 を実行した際に設定される各フラグの状態に基づく、α を基準とした β の大きさを表しています。 above や below は符号なし整数としての大小を、greater や less は符号付き整数とての大小を意味 します。 たとえば、次のような 2 つの機械語命令を順に実行すると、rax と rbx に格納されているビット 列を符号付き整数とみなして、rbx > rax が成り立っている場合にのみ、アドレス 0x1234 へ分岐 します。 cmp %rax, %rbx jg 0x1234 計算機システム II ・第 4 回・終り 4–7
© Copyright 2024 ExpyDoc
