言語プロセッサ

言語プロセッサ
第１2日目
平成20年1月9日
コード生成の概要
原始プログラム
目的コード
字句解析
構文解析
意味解析
中間コード生成
中間コード
コード生成
最適化
中間コード
コード生成の概要
目的言語
原始プログラム
目的コード
字句解析
構文解析
意味解析
中間コード生成
中間コード
中間言語
コード生成
最適化
中間コード
目的言語
1. 絶対形式２進コード
2. 再配置可能コード(相対形式２進コード）
3. アセンブラ言語プログラムなど
１．絶対形式２進コード
• 命令のオペランドの番地指定が、絶対番地に
なっている２進の機械コード
２．再配置可能コード
• 命令のオペランドの番地指定がプログラムの
先頭からの相対番地になっているもの
３．アセンブラ言語プログラム
• 命令やオペランド、番地指定が記号で指定さ
れているもの
選択基準
• 教育用コンパイラ
– 絶対形式２進コードを採用し、コンパイル即実行
方式(compile-and-go方式)。
• 一般のコンパイラ
– 再配置可能２進コードを採用し、リンカ(linker)や
ローダ(loader)により、相対番地の絶対番地への
変換等を行う方式。
• UNIXやLinuxのCコンパイラ
– アセンブラ言語プログラムを生成する方式。
例１: ( -, y, z, x )
MOV
SUB
MOV
Y, R1
Z, R1
R1, X
% Y → register R1
% R1 - Z → R1
% 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
ADD
MOV
A， R1
＃１， R1
R1，A
INC
命令を上手く選ぶ
とより最適なコードが
生成されることがある。
A
練習問題１
式（ X ＋ Y ） / （ Z － U＊V ）に対して以下
の問に答よ。なお、割当て可能なレジスタは
R1とR2の２個だけとする。
1. この式の目的コードを生成せよ。
2. 生成した目的コードが最適化できるか検討
し、最適化できる場合は、その最適化目的
コードを作成せよ。
（ヒント：分母から計算するようにしてみよ。）
目的コードレベルでの最適化
• コードの最適化はあらゆる局面で実施するこ
とが多い。以下では、目的コードレベルでの
最適化の１例(のぞき穴最適化, peephole
optimization)を示す。
のぞき穴最適化
1. 冗長な命令の除去
2. 機械（命令セット）の特徴の活用
3. 制御の流れの最適化など
１．冗長な命令の除去(例１)
MOV
MOV
R1， X
X， R1
MOV
冗長な命令の除去
R1， X
１．冗長な命令の除去(例２)
ADD
MUL
０， R1
１， R1
ともにいつでも
除去可能
２．機械（命令セット）の
特徴の活用の例
X=X+1
に対して、インクリメント命令INCがあれば、
INC
X
とする。
３．制御の流れの最適化(例1)
目的コード：
JUMP
・・・
Label1: Op
Label1
最適化:
Label1:
JUMP
Op
Label1
３．制御の流れの最適化(例2)
JUMP
・・・
L1: JUMP
L1
JUMP
・・・
L1: JUMP
L2
L2
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 := xyz + abc * 123
• （目的コード生成）
（＊，abc，123，t1）
（＋，xyz，t1，t2）
（:＝，t2，abc，0）
目的コードへの変換
MOV
MUL
MOV
MOV
ADD
MOV
MOV
abc,
#123,
R1,
xyz,
t1,
R1,
t2,
R1
R1
t1
R1
R1
t2
abc
abc := xyz + abc * 123
• （目的コードレベルの最適化）
MOV
abc, R1
MOV
abc, R1
MUL
#123,R1
MUL
#123,R1
MOV
R1, t1
ADD
xyz, R1
MOV
xyz, R1
MOV
R1, abc
ADD
t1, R1
MOV
R1, t2
MOV
t2, abc
最適化
これが最終出力
自主レポート課題
• 課題：
コンパイラ自動生成器としてYaccやBisob以外に
どのようなものがあるのか調べなさい。
•
•
•
•
（例：Rie など）
提出期限：平成20年2月7日（木）17:00
提出場所：研A６階八王子側エレベータを降りて右
手窓前にあるレポートボックス。
書式：A4レポート用紙（表紙に氏名・学籍番号・提出
日を明確な文字にて記載すること）
その他枚数等は特に指定しない。
試験に関して
• 試験日：平成19年１月23日（水)３限目
（６０分）持ち込み付加
• 試験対策用の問題集を1月１２日までにWeb
に挙げておきます。良く練習しておくこと。
( url:kameken.clique.jp/compiler/ )
以上

Download Report