アルゴリズムとデータ構造1

コンパイラ
2012年11月5日
酒居敬一＠Ａ４６８([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
1
コード最適化
これまでの内容


ソースプログラムから機械語に翻訳する。




字句解析
構文解析
意味解析
コード生成
今回の内容



2
同じ機能を実現するにあたって、より最適なコードを説明する。
さらにコード生成の前後で、コードサイズの縮小や実行時間の
短縮のための変更ができるかどうか、を説明する。
解析と変換
最適化としての要求項目



オブジェクトコードの大きさの縮小。
オブジェクトコードの実行時間の短縮。
いずれにせよ、プログラム変換である



しかし、無闇に変換すると元のプログラムと動作が変わる。
そこで、制御フロー解析とデータフロー解析により、変換可能な
部分に限りプログラムを変換する。
最適化の目的




3
ソースプログラムで表現できない部分の変換。
ソースプログラムで表現しない部分の変換。
特殊な高性能ハードウェアの性能を引き出す変換。
ソースプログラムで表現できない部分
演算はレジスタ間か、レジスタ-メモリ間で行われる。



一方もしくは両方の被演算対象がレジスタに入る。
しかし、ソースプログラムからレジスタの割り当てはできない。
ソースプログラムからは指示できないこと


レジスタに入れた値の再利用。


レジスタに入れる値のアドレスの再利用。


構造型データでは実効アドレスの計算にも機械語命令が必要かも…
コンパイル時に計算できてしまう値の確定。

4
都度計算したところで、値が同じであることがわかれば再利用できる。
書いたとおりに翻訳するべきか、書いた機能だけを実現すべきか。
ソースプログラムで表現しない部分
保守のために、「読みやすさ」も重要。



コメントとして説明文を添える方法がひとつ。
プログラムそのもので説明する方法もある。
例：



回数固定の小さいループなのに、展開して書かない。
記号定数や定数を利用して、条件分岐の条件を固定する。




事前に計算可能な定数式の値を、計算しないでそのまま書く。
多重ループで説明しやすい順にネストする。
ループ中は結果が不変の式をループ内に書く。

5
１つの機能に２つの実装があり、コンパイル時に決めうちにする。
値を求める場所と使う場所を近づけて、説明を省く。
特殊な高性能ハードウェア
汎用プロセッサに内蔵されたShort vector命令



MMX, SSE, 3D Now! など。
演算器が別にある。データに制約がある。
ＤＳＰ命令


パイプライン処理のため、オペランドが３個以上ある。




メモリオペランドに制約がある。


6
先行命令の結果の格納。
現命令の演算。
後続命令で使う値たちのメモリからの読み込み。
Ｘメモリ・Ｙメモリといったメモリの場所の制約。
それらメモリを区別してアクセスするためのアドレス用レジスタの制約。
誤差・副作用
浮動小数点演算では、安易に演算順序を変えられない。


例：x + 1.0 - 1.0


構文解析では、(x + 1.0) - 1.0 として解釈されるとする。
数学的には (x + 1.0) - 1.0 = x なので、x に最適化していいのか？



数学では加算は交換則が成立するので x + (1.0 + (-1.0)) としてもいい。
ｘが単精度浮動小数点数で 0.000000001 だったとすると、
書いたとおりの解釈では結果は 0 になる。ｘに最適化した結果と違う。
ｘの表現に誤差が含まれるだけではなく、計算によって情報が落ちる。

計算機では加算に交換則が成り立ってない。
式の評価順の問題。


二項演算の被演算項が両方とも関数の戻り値である場合に、
どちらの関数を先に呼び出すべきか？

7
厳密な関数ではなく、手続きでは全域的な状態が異なる場合がある。
制御フロー解析
ノード


基本ブロックと呼ぶ逐次実行される連続する実行文のかたまり。

実行の途中から分岐したり、他から飛び込んでくることはない。
アーク


実行順にノードを結ぶ有向線分。
フローグラフ



ノードがアークで結ばれている。
グラフの形からループを検出することができる。

while, for といった予約語だけではなく、条件分岐・無条件分岐を
組み合わせてループになったものも含めることができる。


検出したループに対して最適化することができる。

8
グラフ化により、while・if・goto・for の区別はなくなります。
for・whileで０回か１回しか回らなければループより条件分岐に見える。
ソースプログラムと制御フローグラフ
i=0;
i=0;
while(eps > 0.01){
x[i] = q + x[i];
if(q > 0)
q = s/q;
else
q = s;
eps = x[i] - x[i-1];
i++;
}
次の実行文
eps > 0.01
true
true
false
x[i] = q + x[i];
q>0
q = s/q;
q = s;
eps = x[i] - x[i-1];
i++;
次の実行文
9
false
データフロー解析

使用点


定義点


プログラムの中で、変数に値を設定する場所。
使用定義連鎖


プログラムの中で、変数の値を参照する場所。
使用点に到達している定義点への連鎖
定義使用連鎖

10
定義点から、その定義が到達する使用点への連鎖。
到達する定義

定義ｄの直後の点からｕへ、定義が消滅しない経路が
少なくともひとつあること。

定義点ｄ１とｄ３の定義はそれぞれは使用点ｕに到達する。
使用点ｕに関しては、定義点ｄ２の定義は消滅する。

x= … 定義点d1
x= … 定義点d2
x= … 定義点d3
= x … 使用点u
11
到達定義を求めるアルゴリズム
 OUTB  GENB  INB  KILLB
基本ブロックＢの出口で生きている定義は、そのＢの中
で作り出される定義と、Ｂの入り口に達してかつ定義が
Ｂの中を通っても消滅しないものの、和集合である。
 GENB  d
定義ｄが基本ブロックＢの中に現れて、Ｂの中を通って
Ｂの終わりに達する。
 KILLB  d
定義ｄが基本ブロックＢの先頭に達したものの、Ｂの
終わりにその定義が達することがない。
12
95ページの直感的説明
GEN[S1]
KILL[S1]
KILL[S2]
GEN[S2]
GEN[S2]
KILL[S2]
GEN[S1;S2]=GEN[S2]∪(GEN[S1]-KILL[S2])
KILL[S1;S2]=KILL[S2]∪(KILL[S1]-GEN[S2])
２つの文が連接しているとき、
定義の生成はそれぞれの文が
生成する定義の和となる。
ただし、後続の文による定義が
先行する文の定義を消滅させて
しまう場合を考慮しないといけない。
２つの文が連接しているときに、
これらの文が消滅させる定義は
それぞれの和である。
ただし、先行する文が消滅した定義を
後続の文でも定義することで消滅
する場合を考慮しないといけない。
13
データフロー方程式を解く反復アルゴリズム
入力：フローグラフ
各基本ブロックのＧＥＮ［Ｂ］とＫＩＬＬ［Ｂ］
出力：各基本ブロックのＩＮ［Ｂ］とＯＵＴ［Ｂ］
初期化：すべての基本ブロックＢについてＩＮ［Ｂ］＝｛φ｝，
すべての基本ブロックＢについてＯＵＴ［Ｂ］＝ＧＥＮ［Ｂ］
while(すべてのＩＮ［Ｂ］が収束するまでフローグラフの入口から経路順に){
IN[B] ∪= ＯＵＴ［Ｐ］；
// ＰはＢの直接先行ブロック
ＯＵＴ［Ｂ］ = ＧＥＮ［Ｂ］∪（ＩＮ［Ｂ］ーＫＩＬＬ［Ｂ］）；
｝
14
Ａ
i=0;
i=0;
while(i > 100){
while(s > 0){
if(p > 0){
x = y/p;
}else{
s = s - p;
}
a = s;
}
s = s+q;
i = i + 1;
s = s + i;
a = s;
}
①
②
③
④
⑤
GEN
GEN
GEN
GEN
GEN
=
=
=
=
=
{①}
{φ}
{φ}
{φ}
{⑤}
KILL={⑨}
KILL={φ}
KILL={φ}
KILL={φ}
KILL={φ}
A
Ｂ
i > 100
true
s>0
⑥ GEN = {⑥} KILL={⑧, ⑩}
⑦ GEN = {⑦} KILL={⑪}
⑧
⑨
⑩
⑪
GEN
GEN
GEN
GEN
=
=
=
=
{⑧}
{⑨}
{⑩}
{⑪}
KILL={⑥, ⑩}
KILL={①}
KILL={⑥, ⑧}
KILL={⑦}
p>0
true
false
Ｃ
true
GEN={①}
KILL={⑨}
false
Ｄ
B
GEN={φ}
KILL={φ}
C
GEN={φ}
KILL={φ}
false
x = y/p;
Ｅ
s = s - p;
Ｆ
Ｇ
a = s;
D
GEN={φ}
KILL={φ}
E
GEN={⑤}
KILL={φ}
F
s = s+q;
i = i + 1;
s = s + i;
a = s;
Ｈ
GEN={⑥}
KILL={⑧，⑩}
G
GEN={⑦}
KILL={⑪}
H
GEN={⑨，⑩，⑪}
KILL={①，⑥，⑦，⑧}
15
到達定義から使用定義連鎖へ
基本ブロックごとに、ＩＮとＯＵＴの集合を求める。
基本ブロック内で使用される変数と、ＩＮに含まれる定
義のうち同じ変数に対するすべての代入文を結ぶ。
1.
2.

使用点で使われる定義を辿ることができる。
基本ブロックの入口までの使用定義連鎖は求まった。



16
しかし、基本ブロック内部については解析していない。
基本ブロック内を実行順にたどって不要な演算を省く。
最適化変換

ループにかかわる最適化変換

ループ不変式の追い出し



ループ展開



17
ループボディを実行している間、値が変化しない式を検出し、
ループの開始前に処理してしまう。
すべての不変式を追い出せるわけではない。
ループの繰り返し部分を展開し、ループの終了条件を判定する
機械命令やループするための分岐命令を削減する。
ループ回数を整数除で簡単にするために、展開するループの回数
を２のべき乗にすることが多い。
ループボディが小さく、ループ終了条件の処理の時間が目立つ
場合には効果が大きい。多重ループの場合は最内周ループに使う。
【ループ不変式の検出アルゴリズム】
1.中間表現をたどり、定数と、ループ内で使用される変数に届くすべての使用定義連鎖の
定義がループの外にある変数に「不変マーク」を付加する。
2.代入文に付加される不変マークが変化しなくなるまで、３と４の処理を繰り返す。
3.演算子ノードの第１オペランドと第２オペランドの両方に不変マークがついている場合、
その演算子にも不変マークを付加する。
4.右辺式に全体に不変マークが付いている場合は、その代入文と左辺変数に不変マー
クを付加し、その左辺変数からの定義が唯一届いている変数の使用にも不変マークを付
ける。
【ループ不変文の追出し】
ループ繰り返しの中で値の変わらない計算を行っている代入文も、必ずしも常にループ
の外に追い出せるわけではない。不変式としてループの外に追い出すことが可能である
式を、ある変数に代入する。不変代入文を追い出すためには、次の条件を満たす必要が
ある。
不変な文は、ループの各繰り返しで必ず実行される。
左辺の変数への代入処理は、そのループの中では検出した不変代入文だけが行う。
不変な代入文の左辺変数から、ループ内への使用定義連鎖が届く変数の使用には、
ほかの定義からの使用定義連鎖が届かない。
18
基本的な最適化変換

定数伝播


静式評価


コンパイル時に評価できるものは評価しておく。
コピー伝播



変数の使用点に唯一の定数定義が届くとき、定数に置換。
a=b;のように右辺に演算がない場合、aをbで置き換える。
ただし、aの使用にはその文からの使用定義連鎖しか届かない
ことと、その文から置き換えて使用するまでのいかなるパス
にも変数ｂへの代入がないこと。
命令強度の削減


19
乗算・除算にシフトを使う。
乗算に加算命令（算術加算・ＥＡ計算）を使う。

Download Report