コンパイラとプログラミング言語
第11週 条件分岐文と繰り返し文のコード生成
2014年6月18日 金岡 晃
授業計画
第1週
(4/9)
コンパイラの概要
第2週
(4/16)
コンパイラの構成
第3週
(4/23)
プログラミング言語の形式的な
記述
第4週
(4/30)
プログラミング言語の形式的な
記述
第5週
(5/7)
字句解析の概要と非決定性有限
オートマトン、決定性有限オー
トマトン・字句解析プログラム
第6週
(5/14)
中間試験
第7週
(5/21)
構文解析の概要/上向き構文解析
第8週
(5/28)
下向き構文解析/構文解析プ
ログラム
第9週
(6/4)
中間表現と意味解析
第10週
(6/11)
Java仮想マシンとその機械語
第11週
(6/18)
条件分岐文と繰り返し文の
コード生成
第12週
(6/25)
関数呼び出しのコード生成
第13週
(7/2)
休講
第14週
(7/9)
休講
(7/23-8/5)
期末試験
【復習】第10週
JAVA仮想マシンとその機械語
コンパイラの論理的な構成
ソース プログラム プログラム目的 コンパイラ 字句 解析 構文 解析 意味 解析 最適化 コード 生成中間情報（中間語、名前表）
目的プログラムを出力する、コンパイラの最終フェーズ
コンピュータが読むため、目的プログラムの形式は
コンピュータの種類などの環境に強く依存
本講義ではJavaをターゲットにする
Javaの仕組み
• コンパイラの種類とバイトコードの実行
– Javaコンパイラ → インタプリタ
– 動的コンパイラ（Just-In-Timeコンパイラ）→実行
– ネイティブコンパイラ → 実行
ソースコード バイトコード（クラスファイル） コンパイラ 字句 解析 構文 解析 意味 解析 コード 生成中間情報（中間語、名前表）
• コンパイラを各計算機の環境ごとにつくらないといけない • 目的プログラムは各環境に応じたものを用意しなければならない • 実行プログラムは各環境に応じたものになる
仮想計算機とJava
エディタ ソース プログラム ソース プログラム ・ ・ ・ コンパイラ コンパイラ 目的 プログラム 目的 プログラム リンケージ エディタ プログラム実行 コンパイルした環境と同じ計算機環境で実行するようにコンパイルされる 環境に依存しない仮想的に考えられた計算機（バーチャルマシン、仮想計算機）と、 仮想計算機用のプログラムを実行可能なソフトを計算機とOSの組ごとに作成すれば、 プログラム作成者は1つのプログラムを作るだけで様々な環境でプログラムが実行できるJavaの場合、JavaVM
スタックマシン
0
1
2
3
4
・・・
・・・
変数エリア
load系
の命令
store系
の命令
データ
データ
データ
・・・
オペランドスタック
演算系の
命令
演算器
Java VM バイトコード：データ操作（１）
ローカル変数を 保持数変数エリ ア領域から、値 を計算に使うた めに、オペラン ドスタックに積 む命令iload 形式：iload index
indexは符号なし1バイト整数。ローカル変数へアクセスできるイ ンデックス。indexにあるローカル変数の値をオペランドスタッ クへプッシュする。
iload_<n> 形式：iload_0, iload_1,…
インデックス<n>のローカル変数の値をオペランドスタックへ プッシュする 計算結果がある オペランドス タックの先頭の 値を、ローカル 変数を保持する 領域に格納する 命令
istore 形式：istore index
indexは符号なしの1バイトの整数で、ローカル変数へアクセスで きるインデックスである。オペランドスタックの先頭の値をポッ プして、ローカル変数のindexが示すエリアにその値を格納する istore_<n> 形式：istore_0, istore_1, …
オペランドスタックの先頭の値をポップして、インデックス<n> のローカル変数のエリアへ格納する
Java VM バイトコード：データ操作（２）
定数を計算に用 いる場合、直接 値をオペランド スタックに積む 命令 iconst_m1 オペランドスタックに-1を積む iconst_<i> 形式：iconst_1, iconst_2, …<i>は1,2,3,4,5のいずれかである。整定数iをスタックに積む。 bipush<n> 整定数nをオペランドスタックに積む。<n>は符号付整数で -128≦<n>≦127の範囲である sipush<n> 整定数nをオペランドスタックに積む。<n>は符号付整数で -32768≦<n>≦32767の範囲である
定数値の処理
pop オペランドスタックの先頭の1ワードをポップする。データを1つ オペランドスタックから捨てるための命令である。スタック操作
Java VM バイトコード：算術演算
iadd オペランドスタックから2つの整数値をポップし、加算した結果をオペラン ドスタックにプッシュする isub オペランドスタックから2つの整数値をポップし、先頭の値を減数、1つ前 の値を被減数として減算した結果をオペランドスタックにプッシュする imul オペランドスタックから2つの整数値をポップし、乗算した結果をオペラン ドスタックにプッシュする idiv オペランドスタックから2つの整数値をポップし、先頭の値を除数、1つ前 の値を被除数として除算した結果をオペランドスタックにプッシュする ineg オペランドスタックの先頭の値の符号を反転させる。Java VM バイトコード：フロー制御（１）条件分岐
ifeq <address> オペランドスタックの先頭の値をポップし、これが0ならば、指定した <address>を分岐オフセットとして、このifeq命令からオフセットだけ離れた命 令に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフ セットを表す16ビットの符号付き整数である。 ifge <address> オペランドスタックの先頭の値をポップし、これが0以上であれば、指定した <address>を分岐オフセットとして、このifge命令からオフセットだけ離れた命令 に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフ セットを表す16ビットの符号付き整数である。 ifgt <address> オペランドスタックの先頭の値をポップし、これが0より大きければ、指定した <address>を分岐オフセットとして、このifgt命令からオフセットだけ離れた命令 に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフ セットを表す16ビットの符号付き整数である。 ifle <address> オペランドスタックの先頭の値をポップし、これが0以下ならば、指定した <address>を分岐オフセットとして、このifle命令からオフセットだけ離れた命令 に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフ セットを表す16ビットの符号付き整数である。 iflt <address> オペランドスタックの先頭の値をポップし、これが0未満ならば、指定した <address>を分岐オフセットとして、このiflt命令からオフセットだけ離れた命令 に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフJava VM バイトコード：フロー制御（２）
goto <address> 指定した<address>を分岐オフセットとして、このgoto命令からオフセットだ け離れた命令に制御が移る。<address>は、分岐オフセットを表す16ビット の符号付き整数である。
goto_w <address> 指定した<address>を分岐オフセットとして、このgoto_w命令からオフセッ トだけ離れた命令に制御が移る。基本的にはgoto命令と同じだが、分岐先が 16ビットの符号付き整数で表現できないほど離れている場合に用いる。 <address>は、分岐オフセットを表す32ビットの符号付き整数である。
無条件分岐
invokestatic <method> スタティックメソッドを呼び出し、引数の値を順にスタックに積んでクラス メソッドを呼び出す。返戻値がある場合は、それがスタックの先頭に積まれ た状態で戻る。<method>はメソッドのエントリ番号を示す指定するコード である。 ireturn オペランドスタックの先頭の整数値をポップして、返戻値とし（呼び出し元 のメソッドのオペランドスタックにプッシュして）、実行中のメソッドを終 了して呼び出し元に戻る。メソッド呼び出しと復帰
バイトコード生成と後置記法
d=a*(b+c)
=
d
*
a
+
b
c
iload 1
iload 2
iload 3
iadd
imul
istore 4
エントリ番号 名前 データ型 番地 領域長1
a
int
12
4
2
b
int
16
4
3
c
int
20
4
4
d
int
24
4
後置記法で表すと
dabc+*=
=は代入なので最
後に持ってくる
abc+*
第11週
条件分岐文と繰り返し文のコード生成
本日の到達目標と概要
• 到達目標
– Java VM バイトコードにおける分岐と繰り返しの理解
• 概要
– 分岐に関するJava VM バイトコード
– バイトコードにおける繰り返しの実現
Java VM バイトコード：条件分岐その２
if_icmpeq <address> オペランドスタックから2つの整数値をポップし、両方の値が等しければ、 指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。 if_icmpne <address> オペランドスタックから2つの整数値をポップし、両方の値が異なる場合、 指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。 if_icmplt <address>オペランドスタックから2つの整数値をポップし、先頭の値＞1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ
次の命令に制御が移る。
if_icmpgt <address>オペランドスタックから2つの整数値をポップし、先頭の値＜1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ
次の命令に制御が移る。
if_icmple <address>オペランドスタックから2つの整数値をポップし、先頭の値≧1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ
次の命令に制御が移る。
if_icmpge <address>オペランドスタックから2つの整数値をポップし、先頭の値≦1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ
次の命令に制御が移る。
分岐をつかったコード例（１）
0: iconst_3
1: istore_1
2: iconst_4
3: istore_2
4: iload_1
5: iconst_2
6: if_icmple
5
9: iconst_5
10: istore_2
11: return
class Test01{
public static void main(String[] arg){
int i;
int j;
i=3;
j=4;
if(i>2){
j = 5;
}
}
}
ソースコード
バイトコード
分岐をつかったコード例（２）
0: iconst_3
1: istore_1
2: iconst_4
3: istore_2
4: iload_1
5: iload_2
6: iadd
7: istore_3
8: iload_3
9: iconst_5
10: if_icmplt
5
13: iconst_5
14: istore_3
15: return
class Test03{
public static void main(String[] arg){
int i;
int j;
int k;
i=3;
j=4;
k=i+j;
if(k>=5){
k=5;
}
}
}
ソースコード
バイトコード
分岐をつかったコード例（３）
class Test03{
public static void main(String[] arg){
int i;
int j;
i=3;
j=4;
if(j>=3){
i=2;
}
}
}
ソースコード
バイトコード
Java VM バイトコード：算術演算その2
iinc 形式：iinc index, value
indexにあるローカル変数の値をvalueだけ増加させ、indexが示すエリアにそ の値を格納する
