言語プロセッサ 第１2日目 平成20年1月9日

コード生成の概要 原始プログラム 目的コード 字句解析 構文解析 意味解析 中間コード生成 コード生成 最適化 中間コード 中間コード

コード生成の概要 目的言語 原始プログラム 目的コード 字句解析 構文解析 意味解析 中間コード生成 コード生成 最適化 中間コード 中間言語

目的言語 絶対形式２進コード 再配置可能コード(相対形式２進コード） アセンブラ言語プログラム　など

１．絶対形式２進コード 命令のオペランドの番地指定が、絶対番地になっている２進の機械コード

２．再配置可能コード 命令のオペランドの番地指定がプログラムの先頭からの相対番地になっているもの

３．アセンブラ言語プログラム 命令やオペランド、番地指定が記号で指定されているもの

選択基準 教育用コンパイラ 一般のコンパイラ UNIXやLinuxのCコンパイラ 絶対形式２進コードを採用し、コンパイル即実行方式(compile-and-go方式)。 一般のコンパイラ 再配置可能２進コードを採用し、リンカ(linker)やローダ(loader)により、相対番地の絶対番地への変換等を行う方式。 UNIXやLinuxのCコンパイラ アセンブラ言語プログラムを生成する方式。

例１: ( -, y, z, x ) MOV Y, R1 % Y → register R1 SUB Z, R1 % R1 - Z → R1 MOV R1, X % R1 → X

例２： 次の中間言語で書かれたコード列を、目的コード列に変換してみると… （＋，B，C，A） （＋，A，E，D）

例２： （＋，B，C，A） （＋，A，E，D） 次の中間言語で書かれたコード列を、目的コード列に変換してみると… MOV B， R1 ADD C， R1 MOV R1， A MOV A， R1 ADD E， R1 MOV R1， D

例２： （＋，B，C，A） （＋，A，E，D） 次の中間言語で書かれたコード列を、目的コード列に変換してみると… MOV B， R1 ADD C， R1 MOV R1， A MOV A， R1 ADD E， R1 MOV R1， D 冗長！ 機械的変換は危険

例３：（＋，A，１，A） MOV A， R1 ADD ＃１， R1 MOV R1，A INC A 命令を上手く選ぶ とより最適なコードが 生成されることがある。

練習問題１ 式 （ X ＋ Y ） / （ Z － U＊V ） に対して以下の問に答よ。なお、割当て可能なレジスタは R1とR2の２個だけとする。 この式の目的コードを生成せよ。 生成した目的コードが最適化できるか検討し、最適化できる場合は、その最適化目的コードを作成せよ。 （ヒント：分母から計算するようにしてみよ。）

目的コードレベルでの最適化 コードの最適化はあらゆる局面で実施することが多い。以下では、目的コードレベルでの最適化の１例(のぞき穴最適化, peephole optimization)を示す。

のぞき穴最適化 冗長な命令の除去 機械（命令セット）の特徴の活用 制御の流れの最適化　など

１．冗長な命令の除去(例１) MOV R1， X MOV X， R1 MOV R1， X 冗長な命令の除去

１．冗長な命令の除去(例２) ADD ０， R1 MUL １， R1 ともにいつでも除去可能

２．機械（命令セット）の 特徴の活用の例 X = X + 1 に対して、インクリメント命令INCがあれば、 INC X とする。

３．制御の流れの最適化(例1) 目的コード： JUMP Label1 ・・・ Label1: Op 最適化: 最適化

３．制御の流れの最適化(例2) JUMP L1 ・・・ L1: JUMP L2 JUMP L2

練習問題２ 　次のコード列に対して、（共通部分式の除去による）最適化を行いなさい。 A ＝ C ー D B = C C = B ー D

まとめ

abc := xyz + abc * 123 （読み込み）

abc := xyz + abc * 123； トークンへの分解（字句解析） （ 変数１，　abc ） （ 代入記号，　:= ） （ 変数２，　xyz ） （ 加算記号，　＋ ） （ 変数１， abc ） （ 乗算記号，　＊ ） （ 定数１，　123 ） （ 文区切り記号，　； ）

abc := xyz + abc * 123 （構文解析） 代入記号 変数１ 加算記号 変数２ 乗算記号 変数１ 定数１

abc := xyz + abc * 123 整数型 整数型 整数型 整数型 整数型 整数型 整数型 （意味解析） 代入記号 変数１ 加算記号 整数型 整数型 変数２ 乗算記号 整数型 変数１ 定数１ 整数型 整数型

abc := xyz + abc * 123 ４つ組への変換（中間コード生成） （乗算，変数１，定数１，一時変数１） （加算，変数２，一時変数１，一時変数２） （代入，一時変数２，変数１，０） （＊，abc，123，t1） （＋，xyz，t1，t2） （:＝，t2，abc，０） そこにはデータがないことを意味することとする。

abc := xyz + abc * 123 （＊，abc，123，t1） （＋，xyz，t1，t2） （:＝，t2，abc，0） （最適化） 中間言語レベルでの最適化はいまは特になし。 （＊，abc，123，t1） （＋，xyz，t1，t2） （:＝，t2，abc，0）

abc := xyz + abc * 123 MOV abc, R1 MUL #123, R1 MOV R1, t1 MOV xyz, R1 （目的コード生成） MOV abc, R1 MUL #123, R1 MOV R1, t1 MOV xyz, R1 ADD t1, R1 MOV R1, t2 MOV t2, abc （＊，abc，123，t1） （＋，xyz，t1，t2） （:＝，t2，abc，0） 目的コードへの変換

abc := xyz + abc * 123 最適化 （目的コードレベルの最適化） MOV abc, R1 MUL #123,R1 MOV R1, t1 MOV xyz, R1 ADD t1, R1 MOV R1, t2 MOV t2, abc MOV abc, R1 MUL #123,R1 ADD xyz, R1 MOV R1, abc 最適化 これが最終出力

自主レポート課題 課題： コンパイラ自動生成器としてYaccやBisob以外にどのようなものがあるのか調べなさい。 （例：Rie など） 提出期限：平成20年2月7日（木）17:00 提出場所：研A６階八王子側エレベータを降りて右手窓前にあるレポートボックス。 書式：A4レポート用紙（表紙に氏名・学籍番号・提出日を明確な文字にて記載すること） その他　枚数等は特に指定しない。

以上 試験に関して 試験日：平成19年１月23日（水)３限目 （６０分）持ち込み付加 試験日：平成19年１月23日（水)３限目 　　　　　（６０分）持ち込み付加 試験対策用の問題集を1月１２日までにWebに挙げておきます。良く練習しておくこと。 ( url:kameken.clique.jp/compiler/ ) 以上