Document

最適化の各操作の適用順序
•
•
•
•
中田育男著
コンパイラの構成と最適化
朝倉書店, 1999年
第１２章第２節１３
最適化の各操作の適用順序
• 高レベルから低レベルへ
• ぞれぞれのレベルの中では？
–
–
–
–
ループ不変式の移動
演算の強さの軽減（帰納変数）
判定の置き換え
無用命令の除去
最適化の例
do i = 1, n
do j = 1, n
sum = 0
do k = 1, n
sum = sum + A(i,k)*B(k,j)
end do
C(i,j) = sum
end do
end do
kのループ
L:
k = 1
t1 = k*n*4 + i*4
t2 = j*n*4 + k*4
sum = sum + A(t1)*B(t2)
k = k + 1
if k  n then goto L
最適化の操作
• ループ不変式のループ外への移動
n*4
t3
i*4
t4
j*n*4
t5
n
• 帰納変数に対する強さの軽減
– v=c*k+c’の形をとる変数
– ループの外でv=c+c’とし、
– ループの最後でv=v+cとする。
t1=k*t3+t4 t2=t5+k*4
t1=t1+t3
t2=t2+4
• 判定の置き換え
• 無用命令の削除
kのループ
L:
k = 1
t1 = k*n*4 + i*4
t2 = j*n*4 + k*4
sum = sum + A(t1)*B(t2)
k = k + 1
if k  n then goto L
ループ不変式のループ外への移動
t3 = n*4
t4 = i*4
t5 = j*n*4
L:
k = 1
t1 = k*t3 + t4
t2 = t5 + k*4
sum = sum + A(t1)*B(t2)
k = k + 1
if k  n then goto L
帰納変数に対する強さの軽減
t3
t4
t5
t1
t2
L:
=
=
=
=
=
n*4
i*4
j*n*4
t3 + t4
t5 + t3
k = 1
t1 = t1 + t3
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
k = k + 1
if k  n then goto L
判定の置き換え
L:
t3 = n*4
t4 = i*4
t5 = j*n*4
t1 = t3 + t4
t2 = t5 + t3
t6 = t5 + t3
k = 1
t1 = t1 + t3
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
k = k + 1
if t2  t6 then goto L
無用命令の削除
t3
t4
t5
t1
t2
t6
L:
=
=
=
=
=
=
n*4
i*4
j*n*4
t3 + t4
t5 + t3
t5 + t3
t1 = t1 + t3
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
if t2  t6 then goto L
jのループ
j = 1
Lj: sum = 0.
t3 = n*4
t4 = i*4
t5 = j*n*4
t1 = t3 + t4
t2 = t5 + t3
t6 = t5 + t3
L: t1 = t1 + t3
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
if t2  t6 then goto L
t7 = j*n*4 + i*4
C(t7) = sum
j = j + 1
if j  n then goto Lj
最適化後
t3 = n*4
t4 = i*4
t5 = t3
t8 = n*t3
Lj: sum = 0.
t1 = t3 + t4
t2 = t5 + t3
t6 = t5 + t3
L: t1 = t1 + t3
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
if t2  t6 then goto L
t7 = t5 + t4
C(t7) = sum
t5 = t5 + t3
if t5  t8 then goto Lj
jとkのループ
j = 1
Lj: sum = 0.
L:
k = 1
t1 = k*n*4 + i*4
t2 = j*n*4 + k*4
sum = sum + A(t1)*B(t2)
k = k + 1
if k  n then goto L
先に強さの軽減をすると
j = 1
Lj: sum = 0.
t2 = j*n*4 + 4
t6 = j*n*4 + n*4
L: t1 = k*n*4 + i*4
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
if t2  t6 then goto L
jのループの際に
. . .
t3 = n*4
t5 = t3 + 4
Lj: sum = 0.
t2 = t5
t6 = j*n*4 + n*4
L: t1 = k*n*4 + i*4
t2 = t2 + 4
sum = sum + A(t1)*B(t2)
if t2  t6 then goto L
一般に、
• 最適化の操作の適用順序によって最適化
の効果に違いがある。
• どんな場合にも最適な効果を得るような順
序を求めることは困難である。
• １つの最適化の操作は１回だけすればよ
いとも限らない。

Download Report