６．４ コード最適化 （１）コード最適化（code optimization）

Presentation on theme: "６．４ コード最適化 （１）コード最適化（code optimization）"— Presentation transcript:

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

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

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

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

5 （１）コード最適化の手法 （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は同じ

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

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

8 （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]

9 （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.

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

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

12 （３） 制御の流れ解析 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:

13 （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

14 頂点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は帰辺

15 （ｂ）自然なループ（定義） 自然なループ ある帰辺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は帰辺

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

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

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

19 到達可能性の処理（１） 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

20 到達可能性の処理（２） 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

21 到達可能性の処理（３） 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 表示

22 処理結果 出発点 到達点

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

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

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

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

27 言葉の定義 ①基本ブロック 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]

28 基本ブロックでの使用可能式の集合 ①基本ブロック 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は出発ブロック）

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

30 処理の流れ （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; }

31 （５） 大域的な変換 （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 で置き換える。 実行順序関係の同じ式を見つけたら、上記のような置き換えを行う。

32 （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 変更