ó¥Ö¥ê¸À¸ì¤ÎÎý½

..
プログラミング言語処理系 (1)
アセンブリ言語の練習
田浦健次朗
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
世の中は言語処理系だらけ
▶
▶
▶
▶
▶
▶
C, C++, Java, Fortran など「いわゆる」計算用のプロ
グラミング言語
スクリプト言語 (Perl, Python, Ruby, . . . )
Web 用言語 (PHP, JavaScript, . . . )
アプリケーションカスタマイズ, 自動操縦用の「マク
ロ」言語 (VisualBasic, Emacs Lisp, . . . )
統計処理用 (R, Octave, . . . )
etc.
そんなに必要なの? ⇒ むしろ目的に応じた「言語」を作る
のが普通
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
本課題全体のゴール
▶
▶
C 言語の極小サブセットのコンパイラを作る
コンパイラとは?
▶
▶
▶
プログラミング言語 (本課題では C 言語) を, 機械語ま
たはアセンブリ言語に変換するプログラム
機械語: CPU が「自分で」実行できる唯一の言語
(bit 列)
アセンブリ言語: ほとんど機械語その物. 各命令の表記
が, 一応読めるテキストになっているだけ.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
進行の目安
回
1
2
3
4
5
6
7
8
9
10
11
12
説明
アセンブリ言語の練習
モジュール化
分割コンパイル, make, subversion
字句解析
課題
字句解析
構文解析
コード生成
構文解析
コード生成・プレゼン
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
本日の目標
▶
▶
▶
▶
▶
▶
既存コンパイラ (gcc) を通し, 課題で作るものをイ
メージ
x86 の命令セット・アセンブリ言語を理解する
既存コンパイラ (gcc) が, どんな C プログラムをどんな
アセンブリ言語プログラムに変換しているかを理解
する
演習: 簡単な C プログラムを「手動で」アセンブリ言語
に変換できるようになる
コンパイラはそのプロセスを自動化したものだから, コ
ンパイラを作るための必須要件
副産物: C 言語の仕組みが分かると, 仕様・挙動がよく
理解できる
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
gcc のコンパイルを構成する段階・部品
(-v オプション) で, コンパイル過程が表示される.
gcc -v filename.c
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
各段階・部品の役割
▶
コンパイル (cc1):
▶
▶
▶
アセンブル (as):
▶
▶
▶
アセンブリ言語 → オブジェクトファイル (.o ファイル)
.o ファイル ≈ 機械語命令列をバイナリ表現したもの
リンク (collect2):
▶
▶
C (.c ファイル)→ アセンブリ言語 (.s ファイル)
.s ファイル ≈ 機械語命令列をテキスト表記したもの
(複数の) オブジェクトファイルやシステムライブラリ
(.a や.so) → 実行可能ファイル (exe ファイル)
’gcc’ はそれらを統括する賢いドライバ (どの段階も, そ
の組み合わせもできる)
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
本課題では
▶
▶
cc1 相当の部品だけを作り, 残りは既存部品 (つまり
gcc) をそのまま使う
⇒ gcc がコンパイルしたものとリンクできる (お互いに
呼んだり呼ばれたりが可能な) コードを生成する
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
GCC の動作調節
gcc に以下のオプションを与えると. . .
▶ -S :
▶
▶
▶
-c :
▶
▶
▶
コンパイル (.s) までで終了
.s は残す (つまり出力を見る事ができる)
アセンブル (.o) までで終了
.o は残す (分割コンパイル時などに使われる)
(おまけ) -E :
▶
▶
プリプロセッサ (マクロ展開; ≈ #define の展開) までで
終了
先の観察では独立した段階ではなく cc1 の機能の一部
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
CPU に関する最小限の知識
▶
レジスタ: 数バイト × 数個 ∼ 数十個の記憶領域
▶
メモリ: CPU 外の (レジスタに比べれば) 広大な記憶領
域 (数百 MB∼ 数 GB)
▶
番地: メモリの個々のバイトを指定する数字
CPU は以下を繰り返し実行するだけの機械
▶
1. 命令を PC (プログラムカウンタ) レジスタが示す番地
から取り出す
2. その命令を実行する. 結果としてレジスタやメモリが
(通常 PC レジスタ以外に一ヶ所) 書き換わる
3. PC レジスタはすべての命令が書き換える. 通常はその
命令のバイト数分増加 (⇒ メモリ上に並んだ命令を順に
実行).
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
命令の一般的種類
▶
▶
▶
▶
ロード命令: メモリのある番地からあるレジスタへ値を
移動
ストア命令: あるレジスタからメモリのある番地へ値を
移動
演算命令: 1∼2 レジスタ (またはメモリ番地) 間で演算
をし, 結果をあるレジスタに入れる
ジャンプ命令: PC の値を指定した番地に設定 (次の命
令を指定した場所から実行 ⇒ ジャンプ)
▶
▶
▶
条件分岐: ある条件が成り立ったらジャンプ
無条件分岐: 無条件にジャンプ
メモリの番地をレジスタで指定できる (レジスタにある
値を番地とみなして, そこを対象にロード・ストア・
演算)
.
.
.
.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
..
IA-32 命令セット
本実験で必要な範囲
▶ 命令から見える整数レジスタ: 32 bit × 8 個
▶
▶
▶
汎用の 6 個: eax, ebx, ecx, edx, esi, edi
特定目的 2 個: ebp, esp
命令から見えないレジスタ: eip (PC), eflags (比較結果
を格納)
▶
命令は 2 オペランドが基本:
例: addl b,a ⇒ a := a + b
▶
a はレジスタ. b は即値, レジスタ, メモリ番地のどれか
メモリ番地の記法:
▶
▶
▶
16(%eax) ⇒ 「eax + 16」番地
-32(%eax,%edx,4) ⇒ 「eax + 4 edx - 32」番地
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
「よく出る」命令
xxxl の, l は, 32 bit 演算の印.
演算
addl, subl, imull, idivl, leal
比較
cmpl
ロード・ストア movl, pushl, popl
ジャンプ (1)
je, jne, jl, jle, jg, jge, jmp
ジャンプ (2)
call, ret
その他
leave
注: IA-32 では, 演算命令がメモリ番地中の値 (メモリオペラ
ンド) を演算対象に出来るので, 演算と, ロード・ストアの区
別は曖昧
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
演算
▶
例
addl %esi,%eax
addl -12(%ebx),%eax
addl 8(%edx,%ecx,4), %eax
はそれぞれ C 言語風に書けば,
%eax = %eax + %esi;
%eax = *(int*)(%ebx - 12);
%eax = *(int*)(%edx + 4 * %ecx + 8);
の意味.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
演算命令: 諸注意
▶
GNU assembler で引き算は多くの人の直感に反する
subl %esi,%eax
は,
%eax = %eax - %esi;
▶
割り算は入力や出力の格納場所に注意が必要. 自分で
gcc にやらせて, その仕様を調べてみよ.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
LEA という変な命令 (1)
▶
lea (Load Eﬀective Address の略) という, 意味深な命令
があるが実は複合的な演算に過ぎない
leal -4(%eax),%ecx
leal 4(%eax,%ebx,1),%ecx
leal -8(%eax,%ebx,4),%ecx
はそれぞれ,
%ecx = -4 + %eax
%ecx = 4 + %eax + %ebx
%ecx = -8 + %eax + 4 * %ebx
の意味. 特に最初の二つは単なる足し算に過ぎない
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
LEA という変な命令 (2)
▶
配列の要素のアドレスを計算するのに便利 (例: a が int
配列なら a[i] のアドレスは, a + 4 * i) なのでこの名
がついたのだろうが, 実体は単なるシフト, 足し算の組
み合わせ
▶
しかし addl 命令と異なり, 3 オペランドを取ることがで
きるため, コンパイラが単なる足し算をするのにこの命
令を使うこともある
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
「比較」という演算
▶
▶
▶
比較命令:
cmpl %esi,%eax
は, %esi と%eax を比較してその結果を eflags という特
別なレジスタに格納する.
条件分岐命令 (後述) が eflags を参照してジャンプした
りしなかったりする
行っている演算自身は, 「引き算のような物」と思って
おけば良い
cmpl %esi,%eax
≈
%eflags = %eax - %esi
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
ロード・ストア
▶
ロード:
movl -16(%ebp),%eax
movl 8(%eax,%edx,4), %eax
▶
ストア:
movl %eax,-4(%esp)
movl %eax,8(%eax,%edx,4)
など
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
push/pop という変わったロード・ストア
▶
push
pushl x
=
subl $4,%esp
movl x,(%esp)
▶
pop
popl x
=
movl (%esp),x
addl $4,%esp
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
ジャンプ
▶
条件なし分岐:
jmp ラベル
でラベルへジャンプ
▶
条件分岐: 例えば je (jump if equal) は,
je ラベル
で, eflags = 0 ならばジャンプという意味.
▶
他に jne, jl, jle, jg, jge など
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
call ≈ push + ジャンプ
▶
call 命令
call ラベル
の動作は以下.
push その次の命令の番地
jmp ラベル
▶
call 命令は, 「一旦どこかにジャンプして, しばらくした
らまた元の場所にもどってきたい」ときに使われる. つ
まり, 関数呼び出しをするのに都合よく作られた命令.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
ret ≈ ジャンプ + pop
▶
ret 命令
ret
の動作は,
popl ra
jmp *ra
▶
ただし ra というレジスタが実際存在するわけではなく,
ここでは動作の説明のために書いている. つまり, esp
が指している場所へジャンプし, esp を 4 増やすという
こと.
実際の使い道としては call 命令が push したアドレスへ,
もどるために使われる. つまり関数呼び出しを終了する
際に使われる.
.
.
.
.
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
..
本当は要らないけど使われる leave
▶
leave
という一命令で以下の複合的な動作が行われる
esp = ebp;
popl ebp;
▶
何に使うのかはこの後関数呼び出しがどう実現されて
いるかを見ると理解できるでしょう
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
gcc に教えてもらう
▶
▶
▶
▶
gcc -S ⟨ ファイル.c⟩ ⇒ ファイル.s ができる. それを覗
くと, gcc がプログラムをどうコンパイルしたかを見る
ことが出来る
C 言語の色々な構文を変換する際の「基本作戦」を学
べる (魔法のような変換が行われている訳ではない)
「この演算は何て命令でやるのか」を教えてもらえる
頭の使い方:
▶
▶
本当に CPU は単純な事しかしない. 個々の命令は, KY.
なぜこれで所望の動作をするのかを細かく見る
「特定の例が結果的にこうなった」で終わらせずに, こ
のような C プログラムは「一般的に」こう変換すれば
良さそうだ「規則」を見つけ・理解する (⇒ 自分を「人
間コンパイラ」化)
.
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
..
コンパイルさせてみる関数
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1.5.1 空の関数
1.5.2 他の関数を呼ぶ関数
1.5.3 大域変数・配列を使う関数
1.5.4 値を返す関数 (∗)
1.5.5 引数を使う関数 (∗)
1.5.6 局所変数を使う関数 (∗)
1.5.7 引数を渡して関数を呼ぶ関数 (∗)
1.5.9 if 文を使う関数
1.5.10 while 文を使う関数
1.5.11 配列・ポインタを使う関数
∗: 山場・難所
プログラミング言語処理系 (1) アセンブリ言語の練習
.
.
.
.
.
.

Download Report