６．５ 最終コード生成 （１）コードの形式 ①絶対２進コード（AB : absolute binary） 命令後のオペランドが絶対番地指定。

Presentation on theme: "６．５ 最終コード生成 （１）コードの形式 ①絶対２進コード（AB : absolute binary） 命令後のオペランドが絶対番地指定。"— Presentation transcript:

1 ６．５ 最終コード生成 （１）コードの形式 ①絶対２進コード（AB : absolute binary） 命令後のオペランドが絶対番地指定。
６．５　最終コード生成 （１）コードの形式 ①絶対２進コード（AB : absolute binary） 命令後のオペランドが絶対番地指定。 このまま主記憶装置にロードして実行可能。 ②相対２進コード（RB : relocatable binary） 命令後のオペランドが先頭からの相対番地指定。 他のプログラムへのデータ参照（外部参照）を含む。 絶対番地への変換はリンケージエディタやローダで行われる。 ③アセンブリ語プログラム 命令語が記号（ニーモニック）コードで記述され、 オペランドも記号である。 機械語への変換はアセンブラで行われる。

2 （２）コード生成における留意点 (a) 命令の選択 (b) 番地指定の選択 (c) レジスタ割り当て (d) 評価順序

3 （a） 命令の選択 ① 設定した仮想機械命令と対象計算機の命令が対応していることが理想的だが、適当な命令がなければ何らかの対処が必要である。
②命令の実行時間にも配慮して命令選択する。　　　 【例】値を１だけ加算する命令 INC が備わっているとき MOV A, R0 ADD #1, R0 MOV R0, A INC A

4 （ｂ）番地指定の選択 ①番地指定法の種類や範囲は、個々の計算機でかなり異なる。
②番地指定法が強力であれば、ある程度、命令の機能を補うことができる。 【例】 ① 配列におけるインデックスレジスタの指定 ② ベースレジスタの使用による相対番地の指定 　（動的リンクでの絶対番地計算を必要としないオブジェクト）

5 （ｃ）レジスタ割り当て ① 変数、定数、一時変数、スタックポインタなどをどのようにレジスタに振り分けるか。
②　レジスタへのアクセス速度はメインメモリへのアクセスに比べて拘束である 速度面で非常に重要となる

6 （ｄ）評価順序 式の評価順序の決定は、実行効率で大きな影響を及ぼす。 (以下、後述)

7 （３）制御構造のコード生成 バックパッチ（back patching） 前に戻って埋め込む処理 <exp> のオブジェクト
JNE L1 If <exp> then S1ブロック Else S2ブロック End If バックパッチ S1ブロック JMP L2 L1 S1ブロック L2

8 バックパッチの例（スタックマシンにおける例）
if(tokenX[i].type=="Name" && tokenX[i].str=="if"){ 　 if論理式(ref i); numPolish=0; SA0(); numStatementNo++; int oldP=numStatement; SA設定("StNo",0,numStatementNo.ToString()); 現Polishのオブジェクト設定(); IfPush(oldP,numStatement,0); // 埋め込み位置の保存 SA設定("Number",0,""); SA設定("then",0,"then"); if(i+1 < numTokenX) MessageBox.Show("thenの後に文は書けません"); } else if(tokenX[i].type=="Name" && tokenX[i].str=="else"){ ifStack[ifStackP].ThenP=numStatement; 　　// elseがあった場合 SA設定("Number",0,""); SA設定("goto",0,"goto"); numStatementNo++; AllStatement[IfStack[IfStackP].IfP].str=numStatement.ToString(); //バックパッチ SA設定("StNo",0,numStatementNo.ToString()); if(i+1 < numTokenX) MessageBox.Show("elseの後に文は書けません"); else if(tokenX[i].type=="Name" && tokenX[i].str=="endif"){ numStatementNo++; SA設定("StNo",0,numStatementNo.ToString()); int IP=IfStack[IfStackP].IfP; // Elseがあった場合となかった場合の判別が必要 if(AllStatement[IP].str=="") AllStatement[IP].str=numStatement.ToString(); else AllStatement[IfStack[IfStackP].ThenP].str=numStatement.ToString(); if(i+1 < numTokenX) MessageBox.Show("endifの後に文は書けません"); IfStackP--;

9 （４）呼出しのコード生成 計算機の機種やオペレーティングシステムによって定まっているのでそれに従う。
【スタックを持たない（Call命令がない）機種の場合の例】 　　　　（汎用大型計算機等） 　　　 LA R0,L0001 JMP SUB L00000 DC RET001 /* リターンアドレス DC ARG001　/* 引数1のアドレス DC ARG002　/* 引数2のアドレス DC ARG003　/* 引数3のアドレス DC ARG004　/* 引数4のアドレス RET001 * /*　リターンアドレス

10 スタックを持つ（一般にCALL命令を持つ）機種の場合
呼び出す側 呼び出される側 入口コード ・ ・ 引数評価の オブジェクト Call Call命令 出口コード ・ Return Return命令 スタック

11 呼出しコード ①実引数を引き渡す準備を行う。ただし、値渡しと参照渡しの区別は呼び出される側で行う。Cの場合は値渡しになっているので、ここで処理してもよい。 ②Call命令を発する。Call命令がなければ、復帰する番地を何らかのレジスタに保存して呼ぶべき関数にジャンプする。 ③上記②の方法が機種やOSによっては定まっている場合がある。

12 入口コード ① レジスタ類を保存する。 ② 新たなデータフレームを確保する。具体的には実引数と仮引数の関係付け、ローカル変数領域の確保等である。 ③ 動的リンク、ディスプレイ、スタックポインタなどの各種制御情報を更新する。

13 出口コード ① 関数の結果を用意する。 ② フレームを開放し、各種の制御情報を呼び出し前に戻す。 ③ レジスタを元に戻す。
④ Return命令の発行

14 （５）算術式のコード生成 スタックマシンにおける逆ポーランド記法の 実行エミュレーションとほぼ同じ。
① 変数名はプッシュする（エミュレーションのときと同じ）。 ② 演算子のときにコードを生成する（エミュレーションのとき「実行」だったことを思い出すこと）。 ③ 結果をプッシュするときは、作業用の変数を生成してその変数をプッシュする（エミュレーションのとき「演算結果」をプッシュしたことを思い出すこと）。

15 演算子のときのコード生成 （作業用変数名は前シートの③と同じもの）
① 単項演算子のとき、変数名をポップ 　　　　LOD R0,変数名 　　　　<OP> R0 　　　　STR　R0,作業用変数名 　 （<OP>は演算子種別で異なる） ② 2項演算子のとき, 2個変数名をポップ。最初にポップしたものを変数名1, 2番目にポップしたものを変数名2とすると 　　　　LOD R0,変数名2 　　　　<OP> R0,変数名1

16 できあがった命令列に対して次の最適化を行う （覗き穴最適化のひとつ（後述））
① 以下のシーケンスの命令を削除する 　　　　STR　R0,作業用変数名 　　　　LOD　R0,作業用変数名 ② 上記①の結果、使用されなくなった作業用変数名を削除する。

17 （６）論理式のコード生成 基本的には算術式と同じであるが、論理式のある部分式だけで全体が決まってしまうことがある。これをJump命令で代替することも多い。 【例】 X > 20 And Y < 30 　　LOD R0,X SUB R0,#20 JME L001 LOD R0,Y SUB R0,#30 JPE L001 [trueのときの処理] L001 [falseのときの処理]

18 （７）四つ組からのコード生成 四つ組は機械命令に近い 四つ組中の変数や一時変数を レジスタおよび主記憶上に どのように割り付けるか？

19 コード生成で用いるデータ ①変数の番地記述（レジスタかメモリかの別を含む） ②レジスタに現在保持されている変数または一時変数

20 レジスタを得る関数getreg ①変数 y がレジスタ上にあり、値がその後にも使われない場合、そのレジスタを返す。
② 空きレジスタがあるときはそれを返す。 ③ あるレジスタの内容を主記憶内の一時変数に退避し、そのレジスタを返す。 ④上記③の方法には、最も古くアクセスされたレジスタを返す方法、最も古く使われたレジスタを返す方法の2種類がある（タスク管理に似ている）

21 X = Y op Zのときのレジスタの割り当て ① 変数 Y (RY)および変数 Z (RZ)がレジスタにあれば、
　　　　<OP> RY,RZ を生成する。 ② 変数 Y (RY)がレジスタ上にあり、変数 Z がレジスタ上になければ、 　　　　<OP> RY,Z ③ 変数 Y がレジスタ上になく、変数 Z （RZ)がレジスタ上にあれば、前出 getreg でレジスタを得る→RY。 　　　　(getregで出力されたメモリへの退避) ④ 変数 Y および変数 Z がレジスタ上になければ、前出 getreg でレジスタを得る→RY。

22 （８）機械依存のコード最適化 ① 変数をレジスタに割り付けるほうが効率が良い。
② 2つ以上の基本ブロックでレジスタに割り付けることを大域的割付（global register allocation）という。ループの制御変数をレジスタに割り付けることも多い。 ③ 機械依存型プログラミング言語の中には、レジスタ変数を用意して、プログラマがレジスタ割付を行う場合もある。 ④ 生成された結果の機械語コードに対する最適化として覗き穴最適化（peephole optimization）がある。

23 覗き穴最適化 ①無駄なLOAD/STORE命令の組の除去
前出にあったが、機械語によってはMOVE命令の組として 表現されることもある 　　　MOV A,R0 (LOD　R0,A) 　　　MOV　R0,A　　 (STR R0,A)

24 覗き穴最適化 ②到達不能コードの除去 無条件分岐の直後の命令で、 かつ別の場所から分岐されない場所の命令 JMP L002
　　　MOV　R0,A　　 (無駄な命令)

25 覗き穴最適化 ③分岐命令の連鎖 無条件分岐の飛び先が、さらに無条件分岐のとき JMP L001 →（JMP L002に変更する） ……
なお、この処理を行った結果、L001が到達不能コードとなることがある。このときは、L001も前述の②で除去される。