６．４ コード最適化
（１）コード最適化（code optimization）
コンパイル過程において生成するコードを最適化すること。
①コードを小さくする最適化
②実行時の効率化（これが中心課題）
③実行時の記憶容量の最小化
プログラム変換のひとつと考えてよい。
（a）機械独立と機械依存
①機械独立（machine independent）な最適化
中間言語に対して最適化するもの。
通常は四つ組みで表現されたものに対して最適化するこ
とが多い。
②機械依存（machine dependent）な最適化
対象機械のアーキテクチャに対して行うもの。
（b）コード最適化の手法
①共通部分式の除去
②複写伝播
③不要コードの除去
④ループ不変量の抽出とコード移動
⑤演算子の強さの軽減
等
以上は互いに関連している。
（c）局所的と大域的
①局所的
演算命令だけからなる列に対する最適化
（比較的単純で容易）
②大域的（制御とデータの流れ解析）
ループなど分岐を含むプログラム部分に対する最適化
（プログラムの実行時の振る舞いに関する情報を得る必
要がある）
（１）コード最適化の手法
（a） 共通部分式の除去
common subexpression elimination
A = B / (C + D) - (C + D)
(+,
(/,
(+,
(-,
C,
B,
C,
R2,
D,
R1,
D,
R3,
R1)
R2)
R3)
A )
R1とR3は同じ
(+, C, D, R1)
(/, B, R1, R2)
(-, R2, R1, A )
（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.
2.
3.
4.
5.
6.
7.
8.
i = 0
goto 0004
i = i + 1
if not(i<100) goto 8
p = 4 * i
C[p]=A[p]*B[p]
goto 3
1.
2.
3.
4.
p = 0
goto 0004
p = p + 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
Temp001
LOD R0,B
MUL R0,C
STR R0,Temp001
LOD R0,Temp001
ADD R0,D
・
・
DA １
/* この部分が
/* 無駄
/* 上記の部分を削除すると
/* これもいらなくなる
（３） 制御の流れ解析
control flow analysis
原始プログラムを基本ブロック（basic block）と
分岐の形に変換して解析する。
for(i=0; i<N; i++)
if(A[I]==X) goto L1;
F = 0; goto L2
L1: F = 1;
L2:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
i = 0
goto 0004
i = i + 1
if not(i<N) goto 8
p = 4 * i
if A[p]=X goto 10
goto 3
F = 0
Goto 11
F = 1
（a） 流れグラフ
flow graph
基本ブロック内を局所的（local）
基本ブロックにまたがる関係を大域的（global）
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
i = 0
goto 0004
i = i + 1
if not(i<N) goto 8
p = 4 * i
if A[p]=X goto 10
goto 3
F = 0
Goto 11
F = 1
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
F = 1
B5
F = 0
頂点Aが頂点Bを支配する（dominant）とは
①流れグラフの出発点から
Bに至るすべての経路が
Aを通るとき
A dom B
と表記。
②ある辺 B→ A が帰辺
(back edge)であるとは、
A dom B
である。
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
F = 1
B3 dom B2,
B3 dom B4,
B4 dom B6,
B5
F = 0
B2→B3は帰辺
B4→B3は帰辺
B6→B4は帰辺
自然なループ
ある帰辺N→Dが存在して、
その部分グラフが
頂点DとDを通らず
Nに到達できるような
すべての頂点を
合わせたもの
左の例では、
B3, B4, B2(先頭B3)
が自然なループである
（赤い線）
（ｂ）自然なループ（定義）
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
F = 1
B3 dom B2,
B3 dom B4,
B4 dom B6,
B5
F = 0
B2→B3は帰辺
B4→B3は帰辺
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
Else
For k = 1 To num
nextBno = Val(.Cells(Bno + 1, k + 2))
到達可能性リスト nextBno, History, P + 1
Next
End If
End With
End If
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
Next
表示
End Sub
処理結果
出発点
到達点
（４） データの流れ解析
data flow analysis
①到達定義解析
②生存変数解析
③使用可能式解析
（a） 到達定義解析
ある定義 D が流れグラフ中の別のある点 P まて到達する
D からが点 P までグラフ上の路があり、
その変数への値の代入またはその可能性がない。
（値の代入またはその可能性があることを「定義が殺され
る」という）
（b） 生存変数解析
流れグラフ中のある点のある変数の値が、
その点以降のどこかの経路で使用されるか
使用されないかを調べる
①どこかの経路で使用されるとき
その変数は「その点で生きている」という。
②どの経路でも使用されないときその変数は
その変数は「その点で死んでいる」という。
（c） 使用可能式解析
available expression analysis
式がある点 P で使用可能式であるとは
流れグラフの出発点から P までのどの経路でも
途中で式の値を評価し、
そのような評価で P に達するものはどれも、
また、その後 P に到達するまでの間、
式中に使われる変数への代入がない。
もっと簡単に「P 以降で代入がない」と言ってもよい。
言葉の定義
①基本ブロック 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 の出口での使用可能式の集合
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
B1
R1 = B + C
R1 = U
U = B + C
R2 = C * D
R2 = C * D
R2 = C * D
削除
B2
B2
B2
R3 = B + C
R3 = U
R4 = X * U
R4 = X * R3
R4 = X * R3
変更
© Copyright 2024 ExpyDoc
