比較照合法によるコンパイラ最適化の正しさの検証

比較照合法による
コンパイラ最適化の正しさの検証
佐々研究室
03M37191
須藤大二朗
研究の背景
コンパイラの最適化


目的コードの時間効率を向上
プログラム変換
 プログラムの意味を変えてはいけない


アルゴリズム
実装
最適化器のテスト

誤った最適化を行うと出力結果が異なる
 誤った変換場所を特定するのは困難

誤った最適化でも出力結果が一致する場合がある
研究の目的
最適化が正しく行われているか検証したい

検証
 最適化器の証明ではない
 正しいプログラム変換かどうか確認する

最適化の前後のプログラムを比較
 代入文の左辺の値
 条件式の比較演算の両辺の値
 関数呼び出しの引数の値

ＳＳＡ最適化において実験する
 最新の最適化
 変数の対応関係を作るのが容易


変数名が字面上唯一・・・変数名により対応付け
検証時間には重きをおかない
比較照合法
Jaramilloが99年に提案

最適化したプログラムのデバッグ
最適化の前後の変数を比較


代入文の左辺の値
条件式の値
アルゴリズム



対応付け
注釈付け
比較照合
ＳＳＡ形式
変数の定義がプログラムの字面上で唯一
変数に添字をつけて区別する
変数の異なった定義の合流点にφ関数を導入
a:=
a:=x+y
a:=a+3
b:=x+y
a1:=x0+y0
a2:=a1+3
b1:=x0+y0
通常形式
SSA形式
a:=
:=a
通常形式
a1:=
a2:=
a3:=φ(a1,a2)
:=a3
SSA形式
本研究の概要
最適化の前後のプログラム



代入文の左辺の値
条件式の比較演算の両辺の値
関数呼び出しの引数の値
ＳＳＡ最適化

変数名により対応付け
エラー表示

中間コードにおけるエラー情報






基本ブロックの番号
基本ブロック内の命令番号
変数名
値
最適化ごと、関数ごとに表示
中間コードをＣ言語風に変換
ソース
フロントエンド
本手法の概要
中間コード
中間コードを複製
(最適化はopt1/opt2/opt3とする)
中間コード
中間コード
中間コード
中間コード
ループ変換
ループ変換
ループ変換
ループ変換
ＳＳＡ変換
ＳＳＡ変換
ＳＳＡ変換
ＳＳＡ変換
最適化なし
opt1
opt1/opt2
opt1/opt2/opt3
ループ解析
ループ解析
ループ解析
ループ解析
トレース出力文の挿入
トレース出力文の挿入
トレース出力文の挿入
トレース出力文の挿入
ＳＳＡ逆変換
ＳＳＡ逆変換
ＳＳＡ逆変換
ＳＳＡ逆変換
目的コード
目的コード
目的コード
目的コード
実行
実行
実行
実行
変数情報
変数情報
変数情報
変数情報
比較照合
比較照合
比較照合
エラー表示
エラー表示
エラー表示
本手法の詳細
L0
1. 中間コードの複製
a=10
b=20
c=0
d=0

L1
a>5
L2
b>10
L3
c=a+b
c=3
d=a+b
a=0
L4
a=1
L5
printf(c)
最適化の数＋１個
2．自然なループへループ変換
L0
L0
a=10
b=20
c=0
d=0
a=10
b=20
c=0
d=0
L1
L1
a>5
a>5
L2
L2
b>10
b>10
L3
L3
c=a+b
c=3
d=a+b
a=0
L4
a=1
L5
c=a+b
c=3
d=a+b
a=0
L4
a=1
Lt
printf(c)
L5
printf(c)
3．ＳＳＡ変換
L0
a_0 =10
b_0=20
c_0 =0
d_0=0
L0
a=10
b=20
c=0
d=0
L1
a_1=Φ(a_0,a_4)
c_1=Φ(c_0,c_4)
d_1=Φ(d_0,d_3)
a_1>5
L1
a>5
L2
L2
b_0 >10
b>10
L3
L3
c=a+b
c=3
d=a+b
a=0
L4
a=1
c_2=a_1+b_0
c_3=3
d_2=a_1+b_0
a_2=0
L4
a_3=1
Lt
Lt
a_4=Φ(a_2,a_3)
c_4=Φ(c_3,c_1)
d_3=Φ(d_2,d_1)
L5
printf(c)
L5
printf(c_1)
4-1．ループ不変式のループ外追い出し
L0
L0
a_0=10
b_0=20
c_0=0
d_0=0
c_3=3
a_2=0
a_3=1
a_0 =10
b_0=20
c_0 =0
d_0=0
L1
a_1=Φ(a_0,a_4)
c_1=Φ(c_0,c_4)
d_1=Φ(d_0,d_3)
a_1>5
L1
a_1= Φ(a_0,a_4)
c_1= Φ(c_0,c_4)
d_1= Φ(d_0,d_3)
a_1>5
L2
b_0 >10
L2
L3
c_2=a_1+b_0
c_3=3
d_2=a_1+b_0
a_2=0
b_0>10
L4
a_3=1
Lt
a_4=Φ(a_2,a_3)
c_4=Φ(c_3,c_1)
d_3=Φ(d_2,d_1)
L5
L3
c_2=a_1+b_0
d_2=a_1+b_0
L4
Lt
a_4= Φ(a_2,a_3)
c_4= Φ(c_3,c_1)
d_3= Φ(d_2,d_1)
L5
printf(c_1)
printf(c_1)
4-2．共通部分式の除去
L0
L0
a_0=10
b_0=20
c_0=0
d_0=0
c_3=3
a_2=0
a_3=1
a_0=10
b_0=20
c_0=0
d_0=0
c_3=3
a_2=0
a_3=1
L1
L1
a_1= Φ(a_0,a_4)
c_1= Φ(c_0,c_4)
d_1= Φ(d_0,d_3)
a_1>5
a_1= Φ(a_0,a_4)
c_1= Φ(c_0,c_4)
d_1= Φ(d_0,d_3)
a_1>5
L2
L2
b_0>10
L3
c_2=a_1+b_0
d_2=a_1+b_0
L4
Lt
b_0>10
L3
c_2=a_1+b_0
d_2=c_2
L4
Lt
a_4= Φ(a_2,a_3)
c_4= Φ(c_3,c_1)
d_3= Φ(d_2,d_1)
L5
a_4= Φ(a_2,a_3)
c_4= Φ(c_3,c_1)
d_3= Φ(d_2,d_1)
L5
printf(c_1)
printf(c_1)
4-3．無用命令の除去
L0
L0
a_0=10
b_0=20
c_0=0
d_0=0
c_3=3
a_2=0
a_3=1
a_0=10
b_0=20
c_0=0
c_3=3
a_2=0
a_3=1
L1
L1
a_1= Φ(a_0,a_4)
c_1= Φ(c_0,c_4)
d_1= Φ(d_0,d_3)
a_1>5
a_1= Φ(a_0,a_4)
c_1= Φ(c_0,c_4)
a_1>5
L2
L2
b_0>10
L3
c_2=a_1+b_0
d_2=c_2
L4
Lt
b_0>10
L3
L4
Lt
a_4= Φ(a_2,a_3)
c_4= Φ(c_3,c_1)
d_3= Φ(d_2,d_1)
L5
a_4= Φ(a_2,a_3)
c_4= Φ(c_3,c_1)
L5
printf(c_1)
printf(c_1)
本手法の詳細
5. ループ解析


ループ内の命令は実行時に
複数回計算される可能性がある
コード移動が起こる場合
6. トレース出力文の挿入
7. ＳＳＡ逆変換

中間コード（ＳＳＡ形式）を
Ｃ言語風に変換したものを出力
8. 実行

全てに同じ入力を与える
出力結果
9. 比較照合

Loop Lv.0
Loop Lv.0
0_1:a_0:10
0_2:b_0:20
0_3:c_0:0
0_4:d_0:0
5_1:CALL_printf_1_1_bef:3
5_1:CALL_printf_1_1_aft:3
Loop Lv.1
<L0>
1_1:a_1:10
1_2:c_1:0
1_3:d_1:0
1_4:JUMP_l:10
1_4:JUMP_r:5
2_1:JUMP_l:20
2_1:JUMP_r:10
3_1:c_2:30
3_2:c_3:3
3_3:d_2:30
3_4:a_2:0
t_1:a_4:0
t_2:c_4:3
t_3:d_3:30
1_1:a_1:0
1_2:c_1:3
1_3:d_1:30
1_4:JUMP_l:0
1_4:JUMP_r:5
</L0>
(a) 最適化なし
値が一致しない場合はエラーを表示
Loop Lv.0
0_1:a_0:10
0_2:b_0:20
0_3:c_0:0
0_4:d_0:0
0_5:c_3:3
0_6:a_2:0
0_7:a_3:1
5_1:CALL_printf_1_1_bef:3
5_1:CALL_printf_1_1_aft:3
Loop Lv.0
0_1:a_0:10
0_2:b_0:20
0_3:c_0:0
0_4:d_0:0
0_5:c_3:3
0_6:a_2:0
0_7:a_3:1
5_1:CALL_printf_1_1_bef:3
5_1:CALL_printf_1_1_aft:3
Loop Lv.1
Loop Lv.1
Loop Lv.1
<L0>
1_1:a_1:10
1_2:c_1:0
1_3:d_1:0
1_4:JUMP_l:10
1_4:JUMP_r:5
2_1:JUMP_l:20
2_1:JUMP_r:10
3_1:c_2:30
3_2:d_2:30
t_1:a_4:0
t_2:c_4:3
t_3:d_3:30
1_1:a_1:0
1_2:c_1:3
1_3:d_1:30
1_4:JUMP_l:0
1_4:JUMP_r:5
</L0>
(b) ループ不変式の
ループ外追い出し
0_1:a_0:10
0_2:b_0:20
0_3:c_0:0
0_4:c_3:3
0_5:a_2:0
0_6:a_3:1
5_1:CALL_printf_1_1_bef:3
5_1:CALL_printf_1_1_aft:3
<L0>
1_1:a_1:10
1_2:c_1:0
1_3:d_1:0
1_4:JUMP_l:10
1_4:JUMP_r:5
2_1:JUMP_l:20
2_1:JUMP_r:10
3_1:c_2:30
3_2:d_2:30
t_1:a_4:0
t_2:c_4:3
t_3:d_3:30
1_1:a_1:0
1_2:c_1:3
1_3:d_1:30
1_4:JUMP_l:0
1_4:JUMP_r:5
</L0>
(c) 共通部分式除去
<L0>
1_1:a_1:10
1_2:c_1:0
1_4:JUMP_l:10
1_4:JUMP_r:5
2_1:JUMP_l:20
2_1:JUMP_r:10
t_1:a_4:0
t_2:c_4:3
1_1:a_1:0
1_2:c_1:3
1_3:JUMP_l:0
1_3:JUMP_r:5
</L0>
(d) 無用命令の除去
誤りのある最適化例
実際に誤りを発見できた最適化
Common Subexpression Elimination With
Efficient Question Propagation
SSA変換後に3番地コードへ変換


main()
{
a = 1;
b = a + 2;
c = b + a * c;
x = a + (b + c) * a;
}
出力結果
0_1:a:1
0_2:t_0:1
0_3:b:3
0_4:t_1:3
0_5:t_2:1
0_6:t_3:0
0_7:t_4:0
0_8:c:3
0_9:t_5:1
0_10:t_6:3
0_11:t_7:3
0_12:t_8:6
0_13:t_9:1
0_14:t_10:6
0_15:x:7
３番地コード
0_1:a:1
0_2:t_0:1
0_3:b:3
0_4:t_1:3
0_5:t_2:1
0_6:t_3:0
0_7:t_4:0
0_8:c:3
0_9:t_5:1
0_10:t_6:3
0_11:t_7:0
0_12:t_8:3
0_13:t_9:1
0_14:t_10:3
0_15:x:4
ＣＳＥＱＰ

t_7,t_8,t_10,xに誤り
エラー表示
-----NG!----opt::LoopLevel=0,BlkID=0,InstrNumber=11,t_7:0
unopt::LoopLevel=0,BlkID=0,InstrNumber=11,t_7:3
-----------------NG!----opt::LoopLevel=0,BlkID=0,InstrNumber=12,t_8:3
unopt::LoopLevel=0,BlkID=0,InstrNumber=12,t_8:6
-----------------NG!----opt::LoopLevel=0,BlkID=0,InstrNumber=14,t_10:3
unopt::LoopLevel=0,BlkID=0,InstrNumber=14,t_10:6
-----------------NG!----opt::LoopLevel=0,BlkID=0,InstrNumber=15,x:4
unopt::LoopLevel=0,BlkID=0,InstrNumber=15, x:7
-------------
_L2:
((int)(*(((int *)(unsigned char *)&(a))))) = ((int)( 1));
divexI32_0 = ((int)(((int)(*(((int *)(unsigned char *)&(a)))))));
((int)(*(((int *)(unsigned char *)&(b))))) = ((int)(((int)(divexI32_0 + 2))));
divexI32_1 = ((int)(((int)(*(((int *)(unsigned char *)&(b)))))));
divexI32_2 = ((int)(((int)(*(((int *)(unsigned char *)&(a)))))));
divexI32_3 = ((int)(((int)(*(((int *)(unsigned char *)&(c)))))));
divexI32_4 = ((int)(((int)(divexI32_2 * divexI32_3))));
((int)(*(((int *)(unsigned char *)&(c))))) = ((int)(((int)(divexI32_1 + divexI32_4))));
divexI32_5 = ((int)(((int)(*(((int *)(unsigned char *)&(a)))))));
divexI32_6 = ((int)(((int)(*(((int *)(unsigned char *)&(b)))))));
divexI32_7 = ((int)(((int)(*(((int *)(unsigned char *)&(c)))))));
divexI32_8 = ((int)(((int)(divexI32_6 + divexI32_7))));
divexI32_9 = ((int)(((int)(*(((int *)(unsigned char *)&(a)))))));
divexI32_10 = ((int)(((int)(divexI32_8 * divexI32_9))));
((int)(*(((int *)(unsigned char *)&(x))))) = ((int)(((int)(divexI32_5 + divexI32_10))));
_L2:
((int)(*(((int *)(unsigned char *)&(a))))) = ((int)( 1));
divexI32_0 = ((int)(((int)(*(((int *)(unsigned char *)&(a)))))));
((int)(*(((int *)(unsigned char *)&(b))))) = ((int)(((int)(divexI32_0 + 2))));
divexI32_1 = ((int)(((int)(*(((int *)(unsigned char *)&(b)))))));
divexI32_2 = ((int)(divexI32_0));
divexI32_3 = ((int)(((int)(*(((int *)(unsigned char *)&(c)))))));
divexI32_4 = ((int)(((int)(divexI32_2 * divexI32_3))));
((int)(*(((int *)(unsigned char *)&(c))))) = ((int)(((int)(divexI32_1 + divexI32_4))));
divexI32_5 = ((int)(divexI32_0));
divexI32_6 = ((int)(divexI32_1));
divexI32_7 = ((int)(divexI32_3));
divexI32_8 = ((int)(((int)(divexI32_6 + divexI32_7))));
divexI32_9 = ((int)(divexI32_0));
divexI32_10 = ((int)(((int)(divexI32_8 * divexI32_9))));
((int)(*(((int *)(unsigned char *)&(x))))) = ((int)(((int)(divexI32_5 + divexI32_10))));
中間コードをＣ言語風に出力
L0
L0
a=1
t_0=a
b=t_0+2
t_1=b
t_2=a
t_3=c
t_4=t_2*t_3
c=t_1+t_4
t_5=a
t_6=b
t_7=c
t_8=t_6+t_7
t_9=a
t_10=t_8*t_9
x=t_5+t_10
３番地コード
a=1
t_0=a
b=t_0+2
t_1=b
t_2=t_0
t_3=c
t_4=t_2*t_3
c=t_1+t_4
t_5=t_0
t_6=t_1
t_7=t_3
t_8=t_6+t_7
t_9=t_0
t_10=t_8*t_9
x=t_5+t_10
ＣＳＥＱＰ
ループ構造の最適化への
ベクトル計算機、並列計算機
ループの構造を変える


インデックス変数の対応関係がとれないもの
がある →比較照合の対象としない
ループ内の変数名
○  変わらない最適化
・・・ループ分配、ループ融合、ループ展開、．．．
△  変わる最適化
・・・ループ傾斜、ループつぶし
実験
COINS上で実装および実験



CVSの2004年7月10日のバージョン
小さなプログラム700本
SPEC CPU2000 CINT 181.mcf
対象とする最適化器





Copy Propagation
Constant Propagation
Dead Code Elimination
Common Subexpression
Elimination
Partial Redundancy
Elimination（立川）





Hoisting Loop Invariant
Variables
Operator Strength Reduction
Common Subexpression
Elimination With Efficient
Question Propagation
Redundant Phi Elimination
Empty Block Elimination
実験結果
最適化器のバグを4つ発見



Operator Strength Reductionのバグを１つ発見
Common Subexpression Elimination With
Efficient Question Propagationのバグを１つ発見
立川のPartial Redundancy Eliminationのバグを2
つ発見
（知られていなかったバグ）
関連研究
Neculaらの方法


記号実行を使って検証
gcc2.7.2.2のバグを発見
 ループ展開、レジスタ割り当て
Zuck,Pnueliらの方法


計算モデルに対応付ける
validating toolで確認
大熊,南出らの方法


定理証明システムで各パスの定義を証明
コンパイラプログラムを自動生成
まとめ
比較照合法による最適化器の正しさの検証


最適化の前後の値
ＳＳＡ最適化
最適化器のバグを発見できる


最適化器のバグ４つ
実装上
誤った変換場所を容易に探すことができる


エラー表示
中間コードをＣ言語風に出力
今後の課題
ループ構造の最適化

ＣＯＩＮＳ上で実装、実験
ベンチマーク


ＣＯＩＮＳの最新版
SPEC CPU2000の181.mcf以外

Download Report