わからない、資料が変だ、等、どんな些細なことでもbummerroad@gmail.comに連絡してください。
すぐに改訂します。
教科書には Aho ( カタカナ読みではエイホと呼ばれることが多い ) らの
「ドラゴンブック」 ( 原書の表紙 ( 訳本も同様の表紙 ) : 無目的コンピュータ用語辞典の図版にリンクしてます ) が挙げられて
います。これは、「これを読めばそれなりの C コンパイラが書ける」と言う人も
いるほど、良く網羅されている本で、コンパイラに関しては定番の本とされて
います。初学者にも、参考書としては最高ですが、入門には向きません。また、
高価いので、図書館で借りるなどするのがいいでしょう。
入門に向いた本は、あまり数が無いこともあって、「これ」といった本が
存在しません。図書館で端からあたってみるとか、本気でコンパイラについて
勉強するなら、専門書がある本屋 ( 神田神保町や秋葉原など ) で自分に
合いそうな安い本をさがし、まず 1 冊買ってみて読み潰し、
次を買って読む、というのを 3 冊ぐらい繰り返す、という方法もありでしょう。
絶版になったなどして入手困難な本にも参考になるものがありますので、
特定の事柄について参考文献があげられている場合など、図書館等を活用すると
いいかもしれません
ZINC 言語において、データ型は "word" の 1 種類だけである。386 のサブセットを ターゲットにしている現在のコンパイラでは、word は 32 bit の固定長の整数で、2 の 補数表現である。従って、表現可能な値の範囲は - 231 ≦ x ＜ 231 である。
ZINC 言語の変数は、C 言語のそれとほぼ同じである。すなわち、手続き定義の 外側で定義された変数はグローバル変数で、モジュール内の全ての手続きから 読み書き可能で、プログラムが実行中は生存している。手続き定義の内側で 定義された変数はローカル変数で、定義された手続き内からのみ読み書き 可能で、その手続きが呼ばれるたびに生成され、手続きの終了まで生存し、 手続きの終了と同時に破棄される。
変数名は、手続き名と同様の「名前」、すなわち、英アルファベット文字か 下線 ( '_' ) が先頭文字で、そのあとに 0 個以上の数字または英アルファベット 文字または下線を続けたものである。手続き名と変数名の衝突や、グローバル変数どうし、 ローカル変数どうしの名前の衝突は許されない。グローバル変数と同じ名前のローカル 変数は許されており、名前の衝突する範囲、すなわち、名前が衝突するローカル変数が 定義された手続き内では、グローバル変数が見えなくな ( マスクされ ) る
サブルーチンとの値のやり取りには、グローバル変数を使わなければならない。 他の手続きの実行の間にグローバル変数の値が変わってしまう可能性がある場合、 特に、手続きが再帰的に呼ばれる場合などには、ローカル変数を使って、 グローバル変数の値の保存と復帰を適当におこなうことが必要になるかもしれない。
C 言語における代入の文は、構文定義の面から見て簡単に書けば、
<文> ::= <式文> | ... <式文> ::= <式> ; <式> ::= <代入式> | ... <代入式> ::= <左辺式> = <式>
<左辺式> とは、変数 "x" のように「代入が可能」な式。例えば 定数 "10" のような式には代入は不可能
( これはあくまでわかりやすいように簡略化した例である。正確な定義は
仕様なりなんなりを見ること ( K&R には定義が示されているが、K&R が仕様では
ないので注意 ))
となっている。代入自体は、値と副作用を持つ代入式という式で実現されていて、
式文という文の存在により、あたかも「代入文」のように見える文が
存在する
これに対し、ZINC における代入は、
<文> ::= <代入文> | ... <代入文> ::= set <変数名> := <式> ;
となっている。代入文という文が存在する。また、":=" という記号は Pascal 系 ( おおもとは Algol ? ) の言語からいただいてきたものである
ZINC 言語の if 文と while 文は、どちらも同じ形
if ( <式> ) <複文> while ( <式> ) <複文>
をしている。
if 文は、式を評価した値が 0 以外ならば続く複文を
実行し、式を評価した値が 0 ならば続く複文は飛ばして次の文に飛ぶ。
while 文は、
式を評価した値が 0 以外ならば続く複文を実行し、さらに式の
評価に戻る、というループを構成する。式を評価した値が 0 ならば、
ループを終了し、次の文に飛ぶ
比較も参照せよ
ZINC の入出力は、それぞれ getchar と putchar を使っておこなう。 getchar は代入文の 1 形式、putchar は putchar 文という独立した 文である。それぞれ、C 言語の ( 標準ライブラリの入出力関数の ) getchar と putchar に相当し、標準入力 からの 1 文字読み込みと標準出力への 1 文字書き込みを行う。 実験で使用した znc では、p386 エミュレータ ( 後述 ) で実行する ために、OS 機能呼びだしを想定したソフトウェア割り込み命令 int を 生成している
ZINC の演算子を優先順位が高い順に示す。構文規則では、図 2 において あとのほうで示されている ( 構文木の、葉に近いほう ) ほど、優先順位が 高いことに注意。
他に注意すべきことは、C 言語と同様の演算子が存在するが、 優先順位が非常に異なっているということである。 とくに、算術演算子とビット演算子に関して、まとめて 2 種類の優先順位 しか存在せず、さらにそれより低い優先順位として、比較があり、 それだけしか優先順位が存在しない。C では、もっと細かく多くの順位に 分けられている。
0 ≦ シフト幅 ＜ 32 でない場合の動作は不定。符号拡張シフトでは、 シフトによって空く最上位ビット側には、シフト前の値の最上位ビットが 1 ならば 1 が、0 ならば 0 が詰められる。左シフトとゼロ拡張シフト では、シフトによって空くビットには、0 が詰められる。 右シフト演算子の使い分けは、Java からいただいてきたものである
例 15 << 2 ＝ 60 15 >> 2 ＝ 3 -15 >> 2 ＝ -4 -15 >>> 2 ＝ 1073741820
これらの演算の結果の値は、比較をおこない、条件が成立していたら ~0 ( "~" は、ビット毎の NOT の単項演算子 ) 、成立していなければ 0 となる。
例 15 == 15 ＝ ~0 15 == 2 ＝ 0 15 != 15 ＝ 0 15 != 2 ＝ ~0 15 < 15 ＝ 0 15 < 30 ＝ ~0 15 > 2 ＝ ~0 15 > 15 ＝ 0 15 <= 15 ＝ ~0 15 >= 15 ＝ ~0
制御構造も参照せよ
セミコロン ( ";" ) は、<複文> で終らない <文> の最後や、
宣言における、カンマ ( "," ) で区切ったリストの最後に
付いている。プログラムを書くときには、直感的に C 言語と同様の
ところにセミコロンを置けば良いようになっている。
言語設計としては、Pascal 風の規則や、複文を「 <文> の後にセミコロンを 付けたものを並べたもの」とするやりかたなど、様々な選択肢がある
znc が出力するコードの目的プロセッサは、インテルの 386 から、大幅に機能を
取り除いたプロセッサである。以下における、機械語のアセンブリ言語による
表記方法は、GNU のアセンブラ gas に準ずる。gas の表記は、Microsoft の
デバッガや MASM 、インテルの資料などとは異なっているので、特に注意が必要な
ことに関してはその旨を記した。
また、znc の他に、znas, p386
という処理系も作ってある。これらは、p386 が znc の目的プロセッサ ( すなわち
386 サブセット ) のエミュレータで、znas は znc の出力するアセンブリ言語
( gas ) のコードを、p386 用の入力ファイル用の形式に変換する簡易アセンブラで
ある ( awk(1) で書かれている ) 。これらはどちらも、必要最低限の機能しか
実装していないので、znc の出力を実行する以外の、他の目的で使うためには、
機能を追加しなければならないだろう。
便宜的に、目的プロセッサを p386 と呼ぶことにする
p386 の構成については、教科書 図 4 を参照すること
レジスタは、メモリと同様に、値を記憶する装置である。p386 の場合、32 ビット の汎用レジスタが 4 個、メモリのアドレスを示す目的を持った 32 ビットのレジスタ ( ポインタ ) が 3 個、演算の結果に関する情報 ( オーバーフローが起きた、等 ) 等を保持するためのフラグレジスタが 1 個、用意されている。 アセンブリ言語において、レジスタを示すには、レジスタ名 ( "eax", "eip" など ) の先頭に "%" を付けて、"%eax" のように書く
メモリと比べ、レジスタは CPU の内部に存在するので読み書きが高速で、 たいてい、レジスタと CPU の機能は互いに関連していることが多い
汎用レジスタ (eax, ebx, ecx, edx) は、自由に読み書きでき、演算命令や転送命令の対象になる。
また、一部の命令は、汎用レジスタの中の特定のレジスタのみを演算の対象に
することができる ( 乗除算命令やシフト命令 )
ポインタは、メモリのアドレスを示す目的を持ったレジスタである。
eip は、インストラクションポインタ ( プログラムカウンタ ) で、CPU
が実行する命令のアドレスを示している。命令実行毎に規則的に暗黙で増加し、
制御系命令 ( ジャンプ等 ) によって操作される。利用者が直接触ることは
できない。
esp はスタックポインタで、push/pop 命令によって値を 保存/復帰 したり、
call/ret 命令や割込みによるプログラムの流れの 中断/再開 のアドレスを
保存/復帰 するためのメモリのアドレスを示している。保存/復帰 にあわせて、
暗黙で減少/増加 する。
スタックフレームのために操作される
ebp はベースポインタで、スタックを使ってローカル変数を記憶する
ためのメモリ ( スタックフレーム ) を確保するためなどに使われる
( スタックフレームを参照 )
フラグレジスタは、CPU がおこなった演算の結果に従って暗黙で変化し、 ユーザが直接触ることはできない。O ( オーバフロー ), S ( 符号 ), Z ( ゼロ ) の各フラグは、フラグレジスタの特定のビットで、演算結果を それぞれ反映する。また、条件ジャンプ命令は、この各ビット ( すなわち フラグ ) の状態を見て、ジャンプしたりしなかったりする
p386 は、32 ビット幅のデータバスと 32 ビット幅のアドレスバスを持っており、 このバスを通してメモリにつながっている。メモリのアドレス空間はセグメントに 分割されており、コードセグメント、データセグメント、スタックセグメントがある。 それぞれ、機械語の実行プログラム、一般に読み書きするためのデータ、 スタックポインタが指すスタックが置かれる空間である。このあたりの 詳細は、アセンブラとか実行環境 ( p386 エミュレータや、実機の場合は OS ) が 面倒を見てくれるので、知らなくとも当面はなんとかなる
あるアドレス a を指定して、メモリへワードを書き込んだりメモリから
ワードを読みだす場合、ワードは、メモリのアドレス {a, a + 1, a + 2, a + 3}
のバイトに置かれる。この時、ワードの上位側と下位側がどういう風に
メモリに置かれるかが問題になることがある ( 本実験では気にする
必要は発生しないと思う ) 。386 の実機では、リトルエンディアンと呼ばれる、
アドレス a に下位側が、a + 3 に上位側が置かれる方式がとられている。
また、386 はそうではないが、a が 4 の倍数でないといけないプロセッサも
存在する。
p386 エミュレータ内部では、C 言語で実装したことなどにより、いろいろと
ややこしいことになっている。
純粋ないわゆるノイマンマシンでは、プロセッサが実行する命令はメモリから
順番に取り出される。しかし、実用上、たいていのコンピュータ
( 特に、コントローラとも言われるマイコン ) には、外部の事象に対応して
プログラムの実行を中断し変更する機構が備わっている。
この機構を、割り込み機構といい、実行の中断を割り込みという。
割り込み機構は、外部事象に対してだけではなく、プログラム内部から OS の機能を使用するためにも使われる。特にそのような目的に使う ための、割り込みをプログラム中から発生させる命令をソフトウェア割り込み 命令と言い、その命令による割り込みをソフトウェア割り込みと言う
p386 エミュレータには、OS の入出力機能の呼びだしを想定して、
割り込みによる入出力機能が組み込まれている。znc は、この機能を
利用する getchar と putchar に対した出力を生成する。出力中に
見られる "int $192" と "int $193" という命令が
それで、$192 のほうはエミュレータの標準入力から 1 文字読んでその
文字コードをエミュレーション環境内の eax レジスタに書き込む。
$193 のほうは eax を文字コードとして 標準出力に出力する
( $192 $193 というのは即値の表現で、プログラム中に数値を直接記述する
場合はこのように先頭に "$" を付ける )
p386 の命令については、教科書 表 1 〜 3 を参照すること ( 訂正にも注意 )
アセンブリ言語のコード内には、CPU の命令の他に、アセンブラに対して
指示を与えるための、「疑似命令」と呼ばれるものが存在する。
znc の出力が準拠している gas というアセンブラ ( Gnu ASsembler ) の場合、
アセンブラ疑似命令には、"." ( ピリオド ) が先頭に
付いている。
以下に、znc の出力中に見られる疑似命令を示し、説明する。
行の頭から空白を置かずに、名前のあとにセミコロンが続いた文字列を
置くと、ラベルになり、その位置をその名前で参照できる
( 例 : "_main:", "gcd:", "L.10:" ) 。
例にもある通り、先頭以外にはピリオド ( "." ) も使うことができる。
このラベルは、制御命令のオペランドにおいて "call gcd" のように使うことができる。
表 1 の、label とは、これのことで、他に、本実験の範囲では出て来ないが、
mem の「メモリ直接」にもラベルを使うことができる ( 実は、.lcomm という
アセンブラ疑似命令は、ラベル定義とメモリ空間確保を複合したものである )
p386 の命令について以下に示す。各の機械語命令に対して付けられた 名前 ( addl など ) をニモニック ( mnemonic ) ということがある。また、 あるプロセッサの命令全体を指して、命令集合 ( instruction set ) という
ひとつの命令のコードのうち、命令そのものの種類を表す部分を指して、 オペレーション・フィールド ( operation field ) といい、そのコードを 指してオペコード ( op-code ( operation code )) という。命令の意味する 操作の対象とするレジスタやメモリを指定する部分をオペランド・フィールド ( operand field ) といい、そのコードや操作対象を指してオペランドという
オペランドが、命令が対象とするものがどこにあるのかを示すことを、
アドレス指定 ( addressing ) という。メモリのアドレスだけではなく、
レジスタを指定することまでを含めてアドレス指定という ( こともある )
p386 のアドレス指定方式とパタンについて説明する
gas における 2 アドレスの指定では、右側すなわち後に示されるオペランドの
側が、基本的には書き込まれて値の変わるほう ( ディスティネーション ) となる。
( ディスティネーションに対して値の変わらないほうをソースとも言う )
例えば、"addl
%ecx, %eax" というコードの場合、 ecx レジスタの値 ＋ eax レジスタの値 が、
eax レジスタに書き込まれる ( これは、Microsoft の デバッガや MASM などや、
インテル社の資料などの表記法と逆なので注意 ) 。
例外としては、レジスタの内容を入れ換える ( したがって、ソース側、
ディスティネーション側の両方とも書き換えられる ) xchgl や、
フラグを変化させるだけでディスティネーションには書き込まない命令 cmpl など
がある ( cmpl は subl と同様の引き算の計算をするが、その結果は
フラグ変化のみに反映させ、ディスティネーション側への書き込みは
おこなわない。なお、subl, cmpl のどちらも、引き算の向きは、
ディスティネーション − ソース である )
レジスタやメモリから値を読みだしたり、レジスタやメモリに値を書き込んだり する命令群
386 では、このような命令でフラグは変化しない
( モトローラの 680x0 のように、転送命令でもフラグが変化する
プロセッサもまた存在する )
オペランドのパタンと例 movl reg, reg ex. movl %ecx, %edx ecx レジスタの内容を読みだし、その値を edx レジスタに書き込む movl reg, mem ex. movl %eax, x eax レジスタの内容を読みだし、その値を x ( グローバル変数 ) に書き込む ex. movl %ebx, -12(%ebp) ebx レジスタの内容を読みだし、その値をアドレス ebp - 12 の メモリ ( ローカル変数 ) に書き込む movl mem, reg ex. movl y, %edx y ( グローバル変数 ) の内容を読みだし、その値を edx レジスタに書き込む ex. movl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだし、 その値を eax レジスタに書き込む movl imm, reg ex. movl $0, %eax 即値 0 を eax レジスタに書き込む movl imm, mem ex. movl $10, z 即値 10 を z ( グローバル変数 ) に書き込む ex. movl $-2, -8(%ebp) 即値 -2 をアドレス ebp - 8 のメモリ ( ローカル変数 ) に書き込む
pushl %eax ; (1)
movl -8(%ebp), %eax
pushl %eax ; (2)
movl -4(%ebp), %eax
popl %ecx ; (3)
cltd
idivl %ecx, %eax
movl %edx, %eax
popl %ecx ; (4)
; 注 : (2) と (3) が対応しており、(1) と (4) が対応している。
途中に入る他のコードを「またぎ越して」値をレジスタからレジスタに
転送するコードが頻繁にあらわれる ( ような規則に従ってコード生成を
するようにコンパイラが書かれている ) 。
; *** ( 手続き定義に相当するコードの始まり ) 導入 ***
.text
.align 2
.type gcd, @function
gcd:
pushl %ebp
movl %esp, %ebp
subl $12, %esp ; ローカル変数が無い手続きの場合、この行は無い
; *** ここまで ***
; *** 脱出 ***
leave
ret
; *** ここまで ( 手続き定義に相当するコードの終り ) ***
この命令も、実機の 386 ではもっといろいろなオペランドが指定できる
オペランドのパタンと例 popl reg ex. popl %ebp esp レジスタの値をアドレスとするメモリの内容を読みだして、その値を ebp レジスタに書き込み、 esp レジスタに 4 を足し込む pushl reg ex. pushl %eax eax レジスタの内容を読みだして、その値を esp レジスタの値 - 4 を アドレスとするメモリに書き込み、esp レジスタに esp - 4 を書き込む
オペランドのパタンと例 xchgl reg, reg ex. xchgl %ecx, %edx ecx レジスタの内容と edx レジスタの内容を入れ換える xchgl reg, mem ex. xchgl %eax, x eax レジスタの内容と x ( グローバル変数 ) の内容を入れ換える ex. xchgl %ebx, -12(%ebp) ebx レジスタの内容とアドレス ebp - 12 のメモリの内容 ( ローカル変数 ) を入れ換える xchgl mem, reg ex. xchgl y, %edx y ( グローバル変数 ) の内容と edx レジスタの内容を入れ換える ex. xchgl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) と eax レジスタの 内容を入れ換える
算術演算を行う命令。加減乗除やそれらを補助する演算をおこなう。 演算の結果はフラグにも反映される。
フラグ変化の例 32 ビット固定長 2 の補数による符号無し 16 進表現 ( 符号付き 10 進表現 ) 0x00000001 + 0x00000001 = 0x00000002 ( 1 + 1 = 2) Z:reset, S:reset, O:reset 0x80000001 + 0x80000001 = 0x00000002 (-2147483647 + -2147483647 = 2) Z:reset, S:reset, O:set 0xffffffff + 0xffffffff = 0xfffffffe ( -1 + -1 = -2) Z:reset, S:set, O:reset 0x7fffffff + 0x7fffffff = 0xfffffffe ( 2147483647 + 2147483647 = -2) Z:reset, S:set, O:set 0x00000001 + 0xffffffff = 0 ( 1 + -1 = 0) Z:set, S:reset, O:reset 0x80000000 + 0x80000000 = 0 (-2147483648 + -2147483647 = 0) Z:set, S:reset, O:set
オペランドのパタンと例 addl reg, reg ex. addl %ecx, %edx ecx レジスタの内容を読みだし、その値を edx レジスタに足し込む addl reg, mem ex. addl %eax, x eax レジスタの内容を読みだし、その値を x ( グローバル変数 ) に足し込む ex. addl %ebx, -12(%ebp) ebx レジスタの内容を読みだし、その値をアドレス ebp - 12 の メモリ ( ローカル変数 ) に足し込む addl mem, reg ex. addl y, %edx y ( グローバル変数 ) の内容を読みだし、その値を edx レジスタに足し込む ex. addl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだし、 その値を eax レジスタに足し込む addl imm, reg ex. addl $3, %eax 即値 3 を eax レジスタに足し込む addl imm, mem ex. addl $10, z 即値 10 を z ( グローバル変数 ) に足し込む ex. addl $-2, -8(%ebp) 即値 -2 をアドレス ebp - 8 のメモリ ( ローカル変数 ) に足し込む
フラグ変化の例 32 ビット固定長 2 の補数による符号無し 16 進表現 ( 符号付き 10 進表現 ) 0x00000001 - 0xffffffff = 0x00000002 ( 1 - -1 = 2) Z:reset, S:reset, O:reset 0x80000001 - 0x7fffffff = 0x00000002 (-2147483647 - -1 = 2) Z:reset, S:reset, O:set 0xffffffff - 0x00000001 = 0xfffffffe ( -1 - 1 = -2) Z:reset, S:set, O:reset 0x7fffffff - 0x80000001 = 0xfffffffe ( 2147483647 - -2147483647 = -2) Z:reset, S:set, O:set 0x00000001 - 0x00000001 = 0 ( 1 - 1 = 0) Z:set, S:reset, O:reset
オペランドのパタンと例 subl reg, reg ex. subl %ecx, %edx ecx レジスタの内容を読みだし、その値を edx レジスタから読みだした値から引いた 値を edx レジスタに書き込む subl reg, mem ex. subl %eax, x eax レジスタの内容を読みだし、その値を x ( グローバル変数 ) から読みだした値から 引いた値を x に書き込む ex. subl %ebx, -12(%ebp) ebx レジスタの内容を読みだし、その値をアドレス ebp - 12 のメモリ ( ローカル変数 ) から読みだした値から引いた値をアドレス ebp - 12 のメモリに書き込む subl mem, reg ex. subl y, %edx y ( グローバル変数 ) の内容を読みだし、その値を edx レジスタから読みだした値から 引いた値を edx レジスタに書き込む ex. subl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだし、その値を eax レジスタから読みだした値から引いた値を eax レジスタに書き込む subl imm, reg ex. subl $3, %eax 即値 3 を eax レジスタから読みだした値から引いた値を eax レジスタに書き込む subl imm, mem ex. subl $10, z 即値 10 を z ( グローバル変数 ) から読みだした値から引いた値を z に書き込む ex. subl $-2, -8(%ebp) 即値 -2 をアドレス ebp - 8 のメモリ ( ローカル変数 ) から読みだした値から 引いた値を ebp - 8 のメモリに書き込む
Z:set -- ソース ＝ ディスティネーション Z:reset -- ソース ≠ ディスティネーション S:reset かつ O:reset または S:set かつ O:set -- ソース ≦ ディスティネーション S:reset かつ O:set または S:set かつ O:reset -- ソース ＞ ディスティネーション
フラグ変化の例 0x00000003 × 0x00000007 = 0x00000000_00000015 O:reset 0x00000003 × 0xfffffff9 = 0xffffffff_ffffffeb O:reset 0x000f0000 × 0x00100000 = 0x000000f0_00000000 O:set 0x0000f000 × 0x00010000 = 0x00000000_f0000000 O:set 0xfffffff0 × 0x10000000 = 0xffffffff_00000000 O:set
オペランドのパタンと例 imull reg, %eax ex. imull %ecx, %eax ecx レジスタの内容を読みだした値と、eax レジスタから読みだした値を乗算した 値を edx:eax レジスタに書き込む imull mem, %eax ex. imull y, %eax y ( グローバル変数 ) の内容を読みだした値と、eax レジスタから読みだした値を 乗算した値を edx:eax レジスタに書き込む ex. imull -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだした値と、 eax レジスタから読みだした値を乗算した値を edx:eax レジスタに書き込む
オペランドのパタンと例 idivl reg, %eax ex. idivl %ecx, %eax ecx レジスタの内容を読みだした値で、edx:eax レジスタから読みだした値を除算し、 商の値を eax, 余りの値を edx レジスタに書き込む idivl mem, %eax ex. idivl y, %eax y ( グローバル変数 ) の内容を読みだした値で、edx:eax レジスタから読みだした値を 除算し、商の値を eax, 余りの値を edx レジスタに書き込む ex. idivl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだした値で、 edx:eax レジスタから読みだした値を除算し、商の値を eax, 余りの値を eax レジスタに書き込む
フラグ変化の例 0xffffffff → 0x00000001 Z:reset S:reset O:reset 0x80000000 → 0x80000000 Z:reset S:set O:set 0x00000001 → 0xffffffff Z:reset S:set O:reset 0x00000000 → 0x00000000 Z:set S:reset O:reset
オペランドのパタンと例 negl reg ex. negl %ecx ecx レジスタの内容を読みだし、その値の符号を反転した値を ecx レジスタに 書き込む negl mem ex. negl y y ( グローバル変数 ) の内容を読みだし、その値の符号を反転した値を y に書き込む。 ex. negl -4(%ebp) アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだし、その 値の符号を反転した値をアドレス ebp - 4 のメモリに書き込む。
演算例 0x00001234 → 0x00000000_00001234 0xffff1234 → 0xffffffff_ffff1234
論理演算をおこなう命令。フラグは notl を除き、結果に従って変化する
フラグ変化の例 0x0000ffff & 0xffffffff = 0x0000ffff Z:reset, S:reset, O:reset 0x0000ffff & 0xffff0000 = 0 Z:set, S:reset, O:reset 0xffff0000 & 0xffffffff = 0xffff0000 Z:reset, S:set, O:reset
オペランドのパタンと例 andl reg, reg ex. andl %ecx, %edx ecx レジスタの内容を読みだした値と、edx レジスタの内容を読みだした 値のビット毎の論理積をとった値を edx レジスタに書き込む。 andl reg, mem ex. andl %eax, x eax レジスタの内容を読みだした値と、x ( グローバル変数 ) の内容を 読みだした値のビット毎の論理積をとった値を x に書き込む ex. andl %ebx, -12(%ebp) ebx レジスタの内容を読みだした値と、アドレス ebp - 12 のメモリ ( ローカル変数 ) の内容を読みだした値のビット毎の論理積をとった 値を ebp - 12 のメモリに書き込む andl mem, reg ex. andl y, %edx y ( グローバル変数 ) の内容を読みだした値と、edx レジスタの内容を 読みだした値のビット毎の論理積をとった値を edx レジスタに書き込む ex. andl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだした値と、 eax レジスタの内容を読みだした値のビット毎の論理積をとった値を eax レジスタに書き込む andl imm, reg ex. andl $3, %eax 即値 3 と、eax レジスタの内容を読みだした値のビット毎の論理積を とった値を eax レジスタに書き込む andl imm, mem ex. andl $10, z 即値 10 と、z ( グローバル変数 ) の内容を読みだした値のビット毎の 論理積をとった値を z に書き込む ex. andl $-2, -8(%ebp) 即値 -2 と、アドレス ebp - 8 のメモリ ( ローカル変数 ) の内容を 読みだした値のビット毎の論理積をとった値をアドレス ebp - 8 の メモリに書き込む
フラグ変化の例 0x00000f0f | 0x0000f0f0 = 0x0000ffff Z:reset, S:reset, O:reset 0x00000000 | 0x00000000 = 0 Z:set, S:reset, O:reset 0x00000000 | 0xffff0000 = 0xffff0000 Z:reset, S:set, O:reset
オペランドのパタンと例 orl reg, reg ex. orl %ecx, %edx ecx レジスタの内容を読みだした値と、edx レジスタの内容を読みだした 値のビット毎の論理和をとった値を edx レジスタに書き込む。 orl reg, mem ex. orl %eax, x eax レジスタの内容を読みだした値と、x ( グローバル変数 ) の内容を 読みだした値のビット毎の論理和をとった値を x に書き込む ex. orl %ebx, -12(%ebp) ebx レジスタの内容を読みだした値と、アドレス ebp - 12 のメモリ ( ローカル変数 ) の内容を読みだした値のビット毎の論理和をとった 値を ebp - 12 のメモリに書き込む orl mem, reg ex. orl y, %edx y ( グローバル変数 ) の内容を読みだした値と、edx レジスタの内容を 読みだした値のビット毎の論理和をとった値を edx レジスタに書き込む ex. orl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだした値と、 eax レジスタの内容を読みだした値のビット毎の論理和をとった値を eax レジスタに書き込む orl imm, reg ex. orl $3, %eax 即値 3 と、eax レジスタの内容を読みだした値のビット毎の論理和を とった値を eax レジスタに書き込む orl imm, mem ex. orl $10, z 即値 10 と、z ( グローバル変数 ) の内容を読みだした値のビット毎の 論理和をとった値を z に書き込む ex. orl $-2, -8(%ebp) 即値 -2 と、アドレス ebp - 8 のメモリ ( ローカル変数 ) の内容を 読みだした値のビット毎の論理和をとった値をアドレス ebp - 8 の メモリに書き込む
フラグ変化の例 0x00ff00ff ^ 0x00ffff00 = 0x0000ffff Z:reset, S:reset, O:reset 0x00ffff00 ^ 0x00ffff00 = 0 Z:set, S:reset, O:reset 0x00ffff00 ^ 0xffff0000 = 0xff00ff00 Z:reset, S:set, O:reset
オペランドのパタンと例 xorl reg, reg ex. xorl %ecx, %edx ecx レジスタの内容を読みだした値と、edx レジスタの内容を読みだした 値のビット毎の排他的論理和をとった値を edx レジスタに書き込む。 xorl reg, mem ex. xorl %eax, x eax レジスタの内容を読みだした値と、x ( グローバル変数 ) の内容を 読みだした値のビット毎の排他的論理和をとった値を x に書き込む ex. xorl %ebx, -12(%ebp) ebx レジスタの内容を読みだした値と、アドレス ebp - 12 のメモリ ( ローカル変数 ) の内容を読みだした値のビット毎の排他的論理和をとった 値を ebp - 12 のメモリに書き込む xorl mem, reg ex. xorl y, %edx y ( グローバル変数 ) の内容を読みだした値と、edx レジスタの内容を 読みだした値のビット毎の排他的論理和をとった値を edx レジスタに書き込む ex. xorl -4(%ebp), %eax アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだした値と、 eax レジスタの内容を読みだした値のビット毎の排他的論理和をとった値を eax レジスタに書き込む xorl imm, reg ex. xorl $3, %eax 即値 3 と、eax レジスタの内容を読みだした値のビット毎の排他的論理和を とった値を eax レジスタに書き込む xorl imm, mem ex. xorl $10, z 即値 10 と、z ( グローバル変数 ) の内容を読みだした値のビット毎の 排他的論理和をとった値を z に書き込む ex. xorl $-2, -8(%ebp) 即値 -2 と、アドレス ebp - 8 のメモリ ( ローカル変数 ) の内容を 読みだした値のビット毎の排他的論理和をとった値をアドレス ebp - 8 の メモリに書き込む
演算例 0xffffffff → 0x00000000 0x00000000 → 0xffffffff 0x00000000 → 0x00000000 0x8fbc9534 → 0x70436acb
オペランドのパタンと例 notl reg ex. notl %ecx ecx レジスタの内容を読みだし、その値のビット毎の論理否定をした値を ecx レジスタに書き込む notl mem ex. notl y y ( グローバル変数 ) の内容を読みだし、その値のビット毎の論理否定を した値を y に書き込む。 ex. notl -4(%ebp) アドレス ebp - 4 のメモリの内容 ( ローカル変数 ) を読みだし、その 値のビット毎の論理否定をした値をアドレス ebp - 4 のメモリに書き込む。
フラグ変化の例 0x00000001 << 1 = 0x00000002 Z:reset S:reset O:reset 0x80000001 << 1 = 0x00000002 Z:reset S:reset O:set 0xf0000000 << 1 = 0xe0000000 Z:reset S:set O:reset 0x40000000 << 1 = 0x80000000 Z:reset S:set O:set 0x00000000 << 1 = 0x00000000 Z:set S:reset O:reset 0x80000000 << 1 = 0x00000000 Z:set S:reset O:set 0x0000000f << 4 = 0x000000f0 Z:reset S:reset O:unknown 0xff000000 << 4 = 0xf0000000 Z:reset S:set O:unknown 0xf0000000 << 4 = 0x00000000 Z:set S:reset O:unknown
オペランドのパタンと例 shll %cl, reg ex. shll %cl, %edx cl レジスタの内容を読みだした値で、edx レジスタの内容を読みだした値を 左シフトした値を edx レジスタに書き込む shll %cl, mem ex. shll %cl, y cl レジスタの内容を読みだした値で、y ( グローバル変数 ) の内容を 読みだした値を左シフトした値を y に書き込む ex. shll %cl, -4(%ebp) cl レジスタの内容を読みだした値で、アドレス ebp - 4 のメモリの 内容 ( ローカル変数 ) を読みだした値を左シフトした値をアドレス ebp - 4 のメモリに書き込む
フラグ変化の例 0x00000002 >> 1 = 0x00000001 Z:reset S:reset O:reset 0xf0000000 >> 1 = 0xf8000000 Z:reset S:set O:reset 0x00000001 >> 1 = 0x00000000 Z:set S:reset O:reset 0x000000f0 >> 4 = 0x0000000f Z:reset S:reset O:not change 0xff000000 >> 4 = 0xfff00000 Z:reset S:set O:not change 0x0000000f >> 4 = 0x00000000 Z:set S:reset O:not change
オペランドのパタンと例 sarl %cl, reg ex. sarl %cl, %edx cl レジスタの内容を読みだした値で、edx レジスタの内容を読みだした値を 右に符号付き拡張でシフトした値を edx レジスタに書き込む sarl %cl, mem ex. sarl %cl, y cl レジスタの内容を読みだした値で、y ( グローバル変数 ) の内容を 読みだした値を右に符号付き拡張でシフトした値を y に書き込む ex. sarl %cl, -4(%ebp) cl レジスタの内容を読みだした値で、アドレス ebp - 4 のメモリの 内容 ( ローカル変数 ) を読みだした値を右に符号付き拡張でシフトした値を アドレス ebp - 4 のメモリに書き込む
フラグ変化の例 0x00000002 >>> 1 = 0x00000001 Z:reset S:reset O:reset 0xf0000000 >>> 1 = 0x78000000 Z:reset S:reset O:set 0x00000001 >>> 1 = 0x00000000 Z:set S:reset O:reset 0x000000f0 >>> 4 = 0x0000000f Z:reset S:reset O:unknown 0x0000000f >>> 4 = 0x00000000 Z:set S:reset O:unknown 0xf0000000 >>> 0 = 0xf0000000 Z:reset S:set O:unknown
オペランドのパタンと例 shrl %cl, reg ex. shrl %cl, %edx cl レジスタの内容を読みだした値で、edx レジスタの内容を読みだした値を 右にゼロ拡張でシフトした値を edx レジスタに書き込む shrl %cl, mem ex. shrl %cl, y cl レジスタの内容を読みだした値で、y ( グローバル変数 ) の内容を 読みだした値を右にゼロ拡張でシフトした値を y に書き込む ex. shrl %cl, -4(%ebp) cl レジスタの内容を読みだした値で、アドレス ebp - 4 のメモリの 内容 ( ローカル変数 ) を読みだした値を右にゼロ拡張でシフトした値を アドレス ebp - 4 のメモリに書き込む
プロセッサが次以降に実行する命令列を、メモリ上で次に並んでいる命令列ではなく、 指定したアドレスからはじまる命令列に変更する命令である。基本的にはフラグは 変化しない。特に、本実験の範囲ではフラグが変化する命令はない
例
.text
.align 2
.type gcd, @function
gcd:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
movl y, %eax
pushl %eax
movl x, %eax
popl %ecx
.
. ( 中略 )
.
andl %eax, %eax
jz L.3
movl y, %eax
movl %eax, -4(%ebp)
movl x, %eax
movl %eax, -8(%ebp)
L.3:
L.5:
movl $0, %eax
pushl %eax
movl -8(%ebp), %eax
pushl %eax
movl -4(%ebp), %eax
.
. ( 中略 )
.
cltd
idivl %ecx, %eax
movl %edx, %eax
movl %eax, -8(%ebp)
movl -12(%ebp), %eax
movl %eax, -4(%ebp)
jmp L.5
L.6:
movl -8(%ebp), %eax
movl %eax, z
leave
ret
ニモニックの命名規則について考えてみる。
まず、jz と jnz は、Zero と NotZero の意味である。znc の出力では、
if や while の分岐において、andl 命令によるゼロテストをおこなった
あと、これらの命令で分岐がある。
他の命令でも、n は同様に Not の意味である。また、g は Greater、l は
Lesser、e は Equal あるいは ge や le の場合 〜 or Equal の意味である。
これらの命令の条件と、cmpl 命令によるフラグ変化 ( 再掲 )
Z:set -- ソース ＝ ディスティネーション Z:reset -- ソース ≠ ディスティネーション S:reset かつ O:reset または S:set かつ O:set -- ソース ≦ ディスティネーション S:reset かつ O:set または S:set かつ O:reset -- ソース ＞ ディスティネーション
を比べてみると、条件ジャンプ命令の大小表現は、「直前の cmpl 命令に おいて、ディスティネーションはソースより大きかったか小さかったか ( "cmpl ソース, ディスティネーション" ) 」 に対応していることがわかる。znc の出力で、これらの条件分岐は、 比較の演算子に対応するコードの中にあらわれる。
例
.text
.align 2
.type gcd, @function
gcd:
pushl %ebp
movl %esp, %ebp
subl $12, %esp
movl y, %eax
pushl %eax
movl x, %eax
popl %ecx
cmpl %ecx, %eax
movl $0, %eax
jng L.2
notl %eax
L.2:
andl %eax, %eax
jz L.1
movl x, %eax
movl %eax, -4(%ebp)
movl y, %eax
movl %eax, -8(%ebp)
L.1:
movl y, %eax
pushl %eax
movl x, %eax
popl %ecx
cmpl %ecx, %eax
movl $0, %eax
jnle L.4
notl %eax
L.4:
andl %eax, %eax
jz L.3
movl y, %eax
movl %eax, -4(%ebp)
movl x, %eax
movl %eax, -8(%ebp)
L.3:
L.5:
movl $0, %eax
pushl %eax
movl -8(%ebp), %eax
pushl %eax
movl -4(%ebp), %eax
popl %ecx
cltd
idivl %ecx, %eax
movl %edx, %eax
popl %ecx
cmpl %ecx, %eax
movl $0, %eax
je L.7
notl %eax
L.7:
andl %eax, %eax
jz L.6
movl -8(%ebp), %eax
movl %eax, -12(%ebp)
movl -8(%ebp), %eax
pushl %eax
movl -4(%ebp), %eax
popl %ecx
cltd
idivl %ecx, %eax
movl %edx, %eax
movl %eax, -8(%ebp)
movl -12(%ebp), %eax
movl %eax, -4(%ebp)
jmp L.5
L.6:
movl -8(%ebp), %eax
movl %eax, z
leave
ret
サブルーチンの先頭の、
pushl %ebp movl %esp, %ebp
という命令列に、サブルーチンの最後の、
leave ret
という命令列が対応している、ということに注意
サブルーチンの ( ネストした ) 呼び出しと実行にかかわる、
プログラミング言語が必要な情報の記録を、「手続き活動記録」という。
( この用語は、文献「エキスパート C プログラミング」より )
サブルーチン呼び出しの度に、スタックに作られる手続き呼び出し記録
を、スタックフレームと呼ぶ。( CPU によっては、CPU のスタックとは
別の所に置かれる場合もある )
p386 用 znc の場合、これがどうなっているかを説明する。
まず、p386 の call / ret 命令におけるスタックの使われかた
をみる。call / ret 命令や push / pop 命令の動作を考えながら
追っかけてほしい
まず、f という手続きを実行中で、スタックポインタの値が 0x80000000 であるとする。スタックはまだ使われていないとすると、スタックポインタ とそれが指す周辺のメモリの状態を図にすると以下のようになる
.
.
.
0x7fffffc0 0x********
0x7fffffc4 0x********
0x7fffffc8 0x********
0x7fffffcc 0x********
0x7ffffff0 0x********
0x7ffffff4 0x********
0x7ffffff8 0x********
0x7ffffffc 0x********
← esp = 0x80000000
ここで、手続き f から g が call 命令により呼ばれたとする。 すると、スタックは
. . . 0x7fffffc0 0x******** 0x7fffffc4 0x******** 0x7fffffc8 0x******** 0x7fffffcc 0x******** 0x7ffffff0 0x******** 0x7ffffff4 0x******** 0x7ffffff8 0x******** 0x7ffffffc (f への戻りアドレス ) ← esp = 0x7ffffffc
というようになる。さらに、g から h 、h から i を呼ぶと、 i の実行中は
. . . 0x7fffffc0 0x******** 0x7fffffc4 0x******** 0x7fffffc8 0x******** 0x7fffffcc 0x******** 0x7ffffff0 0x******** 0x7ffffff4 (h への戻りアドレス ) ← esp = 0x7ffffff4 0x7ffffff8 (g への戻りアドレス ) 0x7ffffffc (f への戻りアドレス )
というようになる。
ここから逆に、ret 命令により i から h に戻ると
. . . 0x7fffffc0 0x******** 0x7fffffc4 0x******** 0x7fffffc8 0x******** 0x7fffffcc 0x******** 0x7ffffff0 0x******** 0x7ffffff4 (h への戻りアドレス ) 0x7ffffff8 (g への戻りアドレス ) ← esp = 0x7ffffff8 0x7ffffffc (f への戻りアドレス )
さらに h から g 、g から f に戻ると
.
.
.
0x7fffffc0 0x********
0x7fffffc4 0x********
0x7fffffc8 0x********
0x7fffffcc 0x********
0x7ffffff0 0x********
0x7ffffff4 (h への戻りアドレス )
0x7ffffff8 (g への戻りアドレス )
0x7ffffffc (f への戻りアドレス )
← esp = 0x80000000
となる。( 上の図では古いスタックの内容は保持されているかのように 書かれているが、割り込みなどにより、アドレス > esp となるメモリ の内容は破壊されているかもしれない。これは OS などにも関連している 事柄である )
さて、手続き定義に相当するコードについて、以前に、「導入部」と 「脱出部」というものを示した ( 再掲 )
; *** ( 手続き定義に相当するコードの始まり ) 導入 ***
.text
.align 2
.type gcd, @function
gcd:
pushl %ebp
movl %esp, %ebp
subl $12, %esp ; ローカル変数が無い手続きの場合、この行は無い
; *** ここまで ***
.
.
; === 手続きの本体部分 ===
.
.
; *** 脱出 ***
leave
ret
; *** ここまで ( 手続き定義に相当するコードの終り ) ***
ここで、前の例の手続き f から、この例で示されている手続き gcd を 呼び出したとして、ここで示されているコードを追いかけてみると、 「=== 手続きの本体部分 ===」を実行している時のスタックは
. . . 0x7fffffc0 0x******** 0x7fffffc4 0x******** 0x7fffffc8 0x******** 0x7fffffcc 0x******** ← esp = 0x7fffffcc 0x7ffffff0 0x******** 0x7ffffff4 0x******** 0x7ffffff8 (esp を代入される前の ebp の値 ) ← ebp = 0x7ffffff8 0x7ffffffc (f への戻りアドレス )
のようになっている。このようにすると、この例の場合、
0x7ffffff8 ＜ アドレス ≦ 0x7fffffcc のメモリは、
手続きの本体部分において "-4($ebp)" のような
オペランドで参照して自由に使うことができる。
また、leave 命令が、esp と ebp をもとに戻していることにも
注意してほしい。
このような仕掛けで、「手続きの呼び出し」にローカルな変数が
実現されている