６．４ コード最適化 （１）コード最適化（code optimization） コンパイル過程において生成するコードを最適化すること。 ①コードを小さくする最適化 ②実行時の効率化（これが中心課題） ③実行時の記憶容量の最小化 プログラム変換のひとつと考えてよい。

（a）機械独立と機械依存 ①機械独立（machine independent）な最適化 中間言語に対して最適化するもの。 　 中間言語に対して最適化するもの。 　　通常は四つ組みで表現されたものに対して最適化することが多い。 ②機械依存（machine dependent）な最適化 　　対象機械のアーキテクチャに対して行うもの。

（b）コード最適化の手法 ①共通部分式の除去 ②複写伝播 ③不要コードの除去 ④ループ不変量の抽出とコード移動 ⑤演算子の強さの軽減 等 以上は互いに関連している。

（c）局所的と大域的 ①局所的 演算命令だけからなる列に対する最適化 （比較的単純で容易） ②大域的（制御とデータの流れ解析） 　　演算命令だけからなる列に対する最適化 　　（比較的単純で容易） ②大域的（制御とデータの流れ解析） 　　ループなど分岐を含むプログラム部分に対する最適化 　　（プログラムの実行時の振る舞いに関する情報を得る必要がある）

（１）コード最適化の手法 （a） 共通部分式の除去 common subexpression elimination A = B / (C + D) - (C + D) (+, C, D, R1) (/, B, R1, R2) (+, C, D, R3) (-, R2, R3, A ) (+, C, D, R1) (/, B, R1, R2) (-, R2, R1, A ) R1とR3は同じ

（b） 複写伝播 copy propagation X = Y; Z = X + 1; W = X; X = Y; Z = Y + 1; W = Y; これだけでは最適化になっていないが、 この処理を行った後、 次の不要コードの除去と組み合わせると コードを除去できる可能性が多くなる。

（c） 不要コードの除去 dead code elimination ①　X = Y; ②　Z = Y + 1; ③　W = Y; この後、Xの値が使用されなければ、 ①を除去することができる。

（d） コード移動 code motion for(i=0; i<100; i++) X[i]=10*A[j]+Y[i] TP=10*A[j] for(i=0; i<100; i++) X[i]=TP+Y[i]

（e） ループ制御変数の除去 induction variable elimination for(i=0; i<100; i++) C[i]=A[j]*B[i] 1. i = 0 2. goto 0004 3. i = i + 1 4. if not(i<100) goto 8 5. p = 4 * i 6. C[p]=A[p]*B[p] 7. goto 3 8. 1. p = 0 2. goto 0004 3. p = p + 4 4. if not(p<400) goto 7 5. C[p]=A[p]*B[p] 6. goto 3 7.

（f） 演算子の強さの軽減 reduction in strength 演算命令をより「弱い」命令 （実行時間が短い命令）に変える MULTI R0, 2 ⇒　　ADD R0,R0　　 ADDI R0, 1 ⇒ INC R0

（g） オブジェクト生成時の作業領域の削減 式実行時の作業領域への格納と参照の無駄の排除 この削除によって生じる未使用作業領域の削除 B * C ＋ D LOD　R0,B MUL R0,C STR R0,Temp001 /* この部分が LOD　R0,Temp001 /* 無駄 ADD R0,D 　　　　　・ Temp001　DA　１ 　　　　　　/* 上記の部分を削除すると /* これもいらなくなる

（３） 制御の流れ解析 control flow analysis 原始プログラムを基本ブロック（basic block）と 分岐の形に変換して解析する。 1. i = 0 2. goto 0004 3. i = i + 1 4. if not(i<N) goto 8 5. p = 4 * i 6. if A[p]=X goto 10 7. goto 3 8. F = 0 9. Goto 11 10. F = 1 11. for(i=0; i<N; i++) if(A[I]==X) goto L1; F = 0; goto L2 L1: F = 1; L2:

（a） 流れグラフ flow graph 基本ブロック内を局所的（local） 基本ブロックにまたがる関係を大域的（global） 1. i = 0 2. goto 0004 3. i = i + 1 4. if not(i<N) goto 8 5. p = 4 * i 6. if A[p]=X goto 10 7. goto 3 8. F = 0 9. Goto 11 10. F = 1 11. i = 0 B2 i = i + 1 B3 if not(i<N) goto 8 B4 p = 4 * i if A[p]=X goto 10 B6 B5 F = 1 F = 0

頂点Aが頂点Bを支配する（dominant）とは ①流れグラフの出発点から Bに至るすべての経路が Aを通るとき 　　　A dom B と表記。 ②ある辺 B→ A が帰辺 (back edge)であるとは、 である。 B1 i = 0 B2 i = i + 1 B3 if not(i<N) goto 8 B4 p = 4 * i if A[p]=X goto 10 B6 B5 F = 1 F = 0 B3 dom B2, B2→B3は帰辺 B3 dom B4, B4→B3は帰辺 B4 dom B6, B6→B4は帰辺

（ｂ）自然なループ（定義） 自然なループ ある帰辺N→Dが存在して、 その部分グラフが 頂点DとDを通らず Nに到達できるような すべての頂点を 合わせたもの B1 i = 0 B2 i = i + 1 B3 if not(i<N) goto 8 B4 p = 4 * i if A[p]=X goto 10 左の例では、 　B3, B4, B2(先頭B3) が自然なループである （赤い線） B6 B5 F = 1 F = 0 B3 dom B2, B2→B3は帰辺 B3 dom B4, B4→B3は帰辺 B4 dom B6, B6→B4は帰辺

（ｃ）性質 流れグラフの中の2つの自然なループは、先頭が異なれば、 互いに共通部分がないか、一方が他方に含まれるかのいずれかである。 先頭が同じであれば、一方が他方に含まれるとはいえない場合が生じる。

（d）到達可能性解析の処理 ① ソースプログラムを解析してネットワークを作成。 このときブロック番号一覧を作成する。 　 このときブロック番号一覧を作成する。 ② 各ブロック番号に対して以下を行う。 ③ ブロック番号履歴を空リストとして到達可能性リストを作成する。 【到達可能性リストの作成】 ① 終了または現ブロック番号がブロック履歴にあった場合、 　 現ブロック履歴を到達可能リストとして登録して終わる。 ② 上記①でない場合、以下を行う。 ③ 現ブロック番号をブロック履歴に追加。 ④ 現ブロックからの分岐数分だけ、分岐先のブロック番号を現ブロック番号として再帰的に呼び出す。

到達可能性の処理 Excelによるアルゴリズムの確認

到達可能性の処理（１） Private History(100) As Integer Private ListData(100, 100) As Integer Private NumList(100) As Integer Private PntList As Integer Private Function Hsearch(Bno, History, P) History(P + 1) = Bno k = 1 Do While History(k) <> Bno k = k + 1 Loop Hsearch = k End Function Sub 登録(History, P) PntList = PntList + 1 NumList(PntList) = P For k = 1 To P ListData(PntList, k) = History(k) Next End Sub

到達可能性の処理（２） Sub 到達可能性リスト(Bno, History, P) If Bno = 0 Or Hsearch(Bno, History, P) <= P Then 登録 History, P Else With Worksheets("Sheet1") History(P + 1) = Bno num = Val(.Cells(Bno + 1, 2)) If num = 0 Then 登録 History, P + 1 For k = 1 To num nextBno = Val(.Cells(Bno + 1, k + 2)) 到達可能性リスト nextBno, History, P + 1 Next End If End With End Sub

到達可能性の処理（３） Sub 表示() With Worksheets("Sheet2") .Cells(1, 1) = PntList For i = 1 To PntList .Cells(i + 1, 1) = i .Cells(i + 1, 2) = NumList(i) For k = 1 To NumList(i) .Cells(i + 1, k + 2) = ListData(i, k) Next 　　Next End With End Sub Sub ボタン1_Click() PntList = 0 For i = 1 To 6 到達可能性リスト i, History, 0 表示

処理結果 出発点 到達点

（４） データの流れ解析 data flow analysis ①到達定義解析 ②生存変数解析 ③使用可能式解析

（a） 到達定義解析 ある定義 D が流れグラフ中の別のある点 P まて到達する D からが点 P までグラフ上の路があり、 その変数への値の代入またはその可能性がない。 （値の代入またはその可能性があることを「定義が殺される」という）

（b） 生存変数解析 流れグラフ中のある点のある変数の値が、 その点以降のどこかの経路で使用されるか 使用されないかを調べる ①どこかの経路で使用されるとき 　その変数は「その点で生きている」という。 ②どの経路でも使用されないときその変数は 　その変数は「その点で死んでいる」という。

（c） 使用可能式解析 available expression analysis 途中で式の値を評価し、 そのような評価で P に達するものはどれも、 また、その後 P に到達するまでの間、 式中に使われる変数への代入がない。 もっと簡単に「P 以降で代入がない」と言ってもよい。

言葉の定義 ①基本ブロック B が式 f(X,Y)を殺す。 　言葉の定義 ①基本ブロック B が式 f(X,Y)を殺す。 　基本ブロック中で X または Y の値の変更せず、その後 f(X,Y)を計算しないこと。基本ブロック中で殺される式の集合を次のように表記する。 　　　　e_kill[B] ②基本ブロック B が式 f(X,Y)を生成する。 　基本ブロック中で式 f(X,Y)を計算し、その後 X または Y の値の変更しないこと、基本ブロック中で生成される式の集合を次のように表記する。 　　　　e_gen[B]

基本ブロックでの使用可能式の集合 ①基本ブロック B の入り口での使用可能式の集合 in[B] 　基本ブロックでの使用可能式の集合 ①基本ブロック B の入り口での使用可能式の集合 　　　in[B] ②基本ブロック B の出口での使用可能式の集合 　　　out[B] 【関係】　データの流れの方程式 　　　out[B] = (in[B]－e_kill[B]) ∪ e_gen[B] in[B] = ∩ out[P] （Pは直前のブロック） 　　　 in[B1] = φ　　　　（ B1は出発ブロック）

アルゴリズム 入力：流れグラフ G, 出発ブロック B1 ，式全体の集合 U 　　　各ブロックB の e_kill[B] と e_gen[B] は計算されているものとする。 出力：各基本ブロック B における in[B] とout[B]

処理の流れ （for(B≠ B1) は、 B1 以外の各ブロックBに対して行うという意味） in[B1]=φ; out[B1]=φ; for(B≠ B1) U－ e_kill[B] change=true; while (change){ change=false; for(B≠ B1) {in[B]=∩ out[P]; /* Pは直前のブロック */ oldout=out[B]; out[B]=(in[B]－ e_kill[B]）∪ e_gen[B]; if(oldout ≠ out[B])change=true; }

（５） 大域的な変換 （a）共通部分式の大域的な変換 【例】文S　：　A = B + C B + C が文Sを含む基本ブロックの先頭において 使用可能式であり、かつこのブロック内のSより 前の部分でB、Cが定義されていないものとする。 ① このブロックに到達する B + C の評価を見つけるために流れグラフを逆にたどる。使用可能式なので必ず見つかる。 ② 新しい変数Uを作る。 ③ 上記１で見つかった文 X = B + C を 　　　　U = B　+　C; X = U; で置き換える。 ④ 文Sを　X = U で置き換える。 実行順序関係の同じ式を見つけたら、上記のような置き換えを行う。

（b）複写伝播と不要コードの除去 （a）使用可能式による変換 (b)複写伝播と不要コードの除去 B1 B1 U = B + C R1 = U R2 = C * D B1 R1 = B + C R2 = C * D U = B + C R2 = C * D 削除 B2 B2 B2 R3 = B + C R4 = X * R3 R3 = U R4 = X * R3 R4 = X * U 変更