コンパイラ 2012年11月1日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html.

Presentation on theme: "コンパイラ 2012年11月1日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html."— Presentation transcript:

1 コンパイラ 2012年11月1日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

2 演習（予習） 学生番号：____________ 名前：______________
C言語で全域的な変数を定義したとする。 この定義がコンパイラにより次のように翻訳された。 これらを次のように使うとエラーになる場合があった。 どこがエラーになるでしょうか？その理由は？ int a = 20; int b[3] = {1, 2, 3}; a: .word 20 b: .word 1, 2, 3 int *p = b; a = 1; b = 9; p += a; a = p[0] + b[1];

3 演習問題のとらえかた 名前表を作ってみる 自動的なモノにはasやldでは対応する静的な名前はない。
aは変数なので、aを参照したときはaの場所のメモリの値を使う、 aに代入するときにはaの場所のメモリに値を入れる。 bは配列なので、ｂを参照したときはそのアドレスを使う、一方b への代入操作はその場所に値を入れる文法にはなってない。 名前 何 型 語長 種別 a 変数 int 2 全域的・静的 b 配列 int[] 2*3 p int * 局所的・自動的 asで書いたときには同一であるにもかかわらず、aとbは参照する（使う・見る）という操作でさえも区別されている。

4 コード生成 ターゲットマシンモデル。 いわゆるスタックマシン。実例としてはJava VMやIA-32のFPU。
レジスタの代わりに、スタックを対象に処理する。 スタックに、データのpush/pop命令と、演算命令を作用させる。 演算器 変数エリア ０ １ ２ ３ ４ … データ オペランドスタック スタック ポインタ 演算系 の命令 push系 pop系

5 フォンノイマン型アーキテクチャ 構成要素 動作原理 演算装置・制御装置・記憶装置・入出力装置・情報経路
記憶装置からプログラムカウンタの指すアドレスから 次の命令を読み込む。 命令の長さ分プログラムカウンタを増やす。 「書かれた順番に処理する」を実装している。 制御装置で命令を解読し、その内容に応じて各構成要素を 制御する。 フラグとして、演算装置の内部状態を持つことが多い。 分岐はプログラムカウンタの変更（加減算やload）。 条件分岐は演算装置の内部状態に基づくプログラムカウンタの変更。 ステップ１に戻る。

6 記憶装置 プロセッサに関係する記憶装置。 レジスタ スタック キャッシュ 主記憶 ごく少量。最高速で高並列で動作する。
アーキテクチャにより、実装している場合がある。 ごく少量。最高速で動作する。 キャッシュ ソフトウェアからは見えない。主記憶とプロセッサの速度差を ごまかすために存在する。 少量・超高速・高並列～中量・高速・逐次まで数種類ある。 主記憶 多量。プロセッサから見ればとてつもなく遅い。 高級言語が想定しているスタックは、この記憶階層に作られる。 キャッシュは不可視なのでおいとくとして、記憶装置固有のアドレッシングが存在する。 実動する製品は、妥協の産物。いきなりコード生成は難しいので通常は中間言語という理想的なアーキテクチャを仮定してコンパイルをする。

7 Java VMバイトコード(データ操作) iload index
iload_<n> index nの位置のローカル変数の値を取り出しオペランドスタックにプッシュする。 istore index indexの位置のローカル変数にオペランドスタックからポップして格納する。 istore_<n> index nの位置のローカル変数にオペランドスタックからポップして格納する。 iconst_m1 -1をオペランドスタックにプッシュする。 iconst_<i> 定数iをオペランドスタックにプッシュする。 bipush<n> バイト定数nをオペランドスタックにプッシュする。 sipush<n> 短整数定数nをオペランドスタックにプッシュする。 pop オペランドスタックからポップする。値は捨てる。 レジスタマシンとスタックマシンの違いは、アドレッシングモード。

8 Java VMバイトコード(算術演算) iadd オペランドスタックからオペランドを２個ポップし、加算結果をプッシュする。 isub
オペランドスタックからオペランドを２個ポップし、減算結果をプッシュする。 まず１個ポップし、つぎに「ＴＯＳ -= ポップした値」処理に相当。 mul オペランドスタックからオペランドを２個ポップし、乗算結果をプッシュする。 idiv オペランドスタックからオペランドを２個ポップし、除算結果をプッシュする。 まず１個ポップし、つぎに「ＴＯＳ /= ポップした値」処理に相当。 ineg オペランドスタックからオペランドを１個ポップし、符号反転結果をプッシュする。 演算対象がＴＯＳから順に固定されている。だから、オペランドとして明記しない。

9 Java VMバイトコード(フロー制御) ifeq <address>
ifge <address> オペランドスタックから値を１個ポップし、正か０ならばaddress番地に相対ジャンプ。 ifgt <address> オペランドスタックから値を１個ポップし、正ならばaddress番地に相対ジャンプ。 ifle <address> オペランドスタックから値を１個ポップし、負か０ならばaddress番地に相対ジャンプ。 iflt <address> オペランドスタックから値を１個ポップし、負ならばaddress番地に相対ジャンプ。 goto <address> address番地に相対ジャンプ。 goto_w <address> address番地に相対ジャンプ。addressが大きいときに使う。farジャンプ相当。 invokestatic <method> オペランドスタックからメソッドのエントリ番号をポップし、引数をプッシュしてジャンプ。 ireturn メソッドの呼び出し元に戻る。

10 … 式と代入文の命令語生成 後順走査により、中間表現の木から逆ポーランド記法の 命令語を生成する。
後順走査により、中間表現の木から逆ポーランド記法の 命令語を生成する。 　　　 expressionの値が親に渡される 演算子の優先順の他に、評価順や結合順といったことも 考慮して中間表現を生成し、そこから命令語を生成する。 Ｃの代入演算子では右から左へ結合する。 例えば、x=y=z=1;という文では、最も右の=が最初に処理される。 =の演算の後は、その右辺の値を式の評価値とする。 identifier expression ＝ …

11 参考：Cの演算子の優先度と結合規則 演算子 結合規則 () [] -> . 左から右 関数参照、配列参照、構造体参照
() [] -> . 左から右 関数参照、配列参照、構造体参照 ! ~ * & (型名) sizeof 右から左 いずれも単項演算子 * / % 乗算・除算・剰余の二項演算子 + - 加算・減算の二項演算子 << >> 左シフト・右シフトの二項演算子 < <= > >= 大小を比較する二項演算子 == != 同値を判定する二項演算子 & ビットごとＡＮＤの二項演算子 ^ ビットごとＸＯＲの二項演算子 | ビットごとＯＲの二項演算子 && ＡＮＤ条件の二項演算子 || ＯＲ条件の二項演算子 ?: 条件による選択の三項演算子 = += -= *= /= %= &= ^= |= <<= >>= 代入の二項演算子 , 連接の二項演算子

12 結合順と評価順 /と＊は同じ優先順位なので、A/B＊C の解釈としては (A/B)＊C と A/(B＊C) の２通りあってもいいはず。
加算や乗算だけの組み合わせならどちらの解釈でもいい。 しかし、減算や除算では解釈により結果が異なってしまう。 「左から右」という意味は、同じ優先順位の演算が並ぶ場合、 左側の演算子から順に作用させましょう、ということ。 この場合の解釈は、(A/B)＊C　になる。 実は文法で結合順は決められている。 ＡとＢとＣが関数呼び出しの場合など、演算対象がどの順 で評価されるかについての規定は無いことが多い。 A/B　でＡの値とＢの値のどちらを先に求めるのか？は不定。 文法の中で結合順は考慮されている。評価順は文法に書かれておらず、実際にはコード生成のときに決まる。

13 演算と副作用 レジスタマシンでも、ソフトウェアスタックがある。 ＣやJavaには ++ や -- という単項演算子がある。
push/pop命令が、特殊な形式のオペランドの mov命令の別名定義になっている場合がある。 「push r0」は「mov ＣやJavaには ++ や -- という単項演算子がある。 それに対応する機械命令が存在するので、効率化のために 高級言語でもそのまま演算子として使えるようにした。 レジスタやメモリの値のincrement/decrementの命令。 レジスタ間接メモリ参照の際のレジスタ（ポインタ）の increment/decrement操作。さきのpush/popなど。 機械命令では作用する時期が明確だけど、高級言語 では、その作用が終わる時期が不明確。 たとえば、a[i] = i++;で++の作用が完了するのはいつ？

14 式と代入文の命令語生成 ノードごとにバイトコードを生成 ① iload 2 // y ② iconst_1 ③ iload 1 // x
ノードごとにバイトコードを生成　 ①　iload 2 // y ②　iconst_1 ③　iload 1 // x ④　iconst_1 ⑤　isub ⑥　idiv ⑦　iadd ⑧　istore 2 // z + = / z y 1 - x zに関しては、代入対象ｚの参照、代入 する値の参照、代入操作が後順走査 各処理に対応する。 しかし、代入操作のときにｚを直接参照 できるため、＝ノードを探索したときに 生成されるコードの中で代入対象が 直接示されている。

15 制御構造（条件分岐） L-expressionとR-expressionの値を比較し、 条件が成立すればstatementを実行する。
IF-statement L-expression R-expression statement condition <condition>の実行オブジェクトコード (L-expressionの計算コード R-expressionの計算コード 比較演算コード) 条件付分岐命令 <condition>が不成立のとき前方の９へジャンプ <statement>の実行コード ９：

16 制御構造（繰り返しループ） L-expressionとR-expressionを比較し、条件が成立 している限りは、<statement>を繰り返し実行する。 WHILE-statement L-expression R-expression statement condition 無条件分岐　1f // 条件判定部分へジャンプ 0: // ループボディーの開始位置 <statement>の実行オブジェクト 1: <condition>の実行オブジェクト 条件分岐 0b // 繰り返し条件成立時は後方の0へジャンプ 9: // ループの終了。

17 … 制御構造（関数呼び出し） まず、引数を順にスタックに積み上げる。 次に、エントリーポイントを求めてcall命令でジャンプする。
expression arg-vector identifier … 実引数の数だけ その場合はldなどのリンケージエディタがエントリーポイントへのオフセットを計算する。

18 引数などの渡し方 何かを渡すにあたっては、領域の確保と、そこへのコピー が行われる。領域はスタックに確保するか、レジスタ。
何かを渡すにあたっては、領域の確保と、そこへのコピー が行われる。領域はスタックに確保するか、レジスタ。 値渡し（Pass by Value) オブジェクトの値をコピーして渡す。 受け取り側で値型として参照できる。 参照渡し（Pass by Reference) オブジェクトへのアドレスを渡す。 名前渡し（Pass by Name) オブジェクトの名前を渡す。

19 関数などの呼び出し方 呼ぶにあたっては、そのエントリーポイントが必要。 参照による呼び出し（Call by Reference)
エントリーポイントのアドレスから呼び出す。 Ｃではld が名前からアドレスに置き換える。 動的束縛や、関数のポインタを介した呼び出し。 名前による呼び出し（Call by Name) 動的リンクでは、名前により該当オブジェクトを呼び出す。 Javaだと知らず知らずのうちに動的リンクをやっている。 ClassNotFoundException に垣間見えるかな？ ＣとかJavaとは違う言語では、こういう呼び出しもある。 schemeとかPostScriptなど。