Flow-insensitiveな別名情報とフロー構造を用いた最適化対象の拡大 2007/3/08 東京工業大学大学院佐々研究室修士２年狩野祐介背景 p a 0→1 p=&a; a=0; *p=1;  メモリアクセスをレジスタアクセスに置き換える  (x) 実行時間の改善という意味で有用  p a ra 1 0 p=&a; ra=0; *p=1; (y) raはレジスタを表す  レジスタアロケーションやレジスタプロモーションにより既に実現別名の存在による対象の制限   アドレスを取られているもの別名解析による解決  (x)においてp→{a}という情報を得る。背景２  どちらの別名解析を使うべき？  Flow-sensitiveな別名解析   高精度の別名情報が得られる解析時間が長い   4 多くのアルゴリズムではプログラムのサイズnに対してO( n ) 以上の解析時間 Flow-insensitiveな別名解析   精度は低め（フロー情報が考慮されない）解析時間は短い  早いものでは、プログラムのサイズに対して線形時間研究の目的  Flow-insensitiveな別名情報を独自の手法で補い、それを使ってレジスタへの置き換え   レジスタへの置き換え箇所数を増やすことで実行時間の改善を図るコンパイル時間の増大を抑える  Flow-insensitiveな別名解析の長所である解析時間の短さを帳消しにはしたくない概要  Flow-insensitiveな別名情報＋フローグラフの再調査によるレジスタへの置き換え  フローグラフの再調査で別名情報を補い、それを元にレジスタへの置き換えを行う。    COINS（コンパイラインフラストラクチャ）上で実装   ブロックごとの別名参照のチェックブロックのグループ化実行時間とコンパイル時間を計測前提   スカラー変数のみをレジスタに置き換える対象とする入力言語はC言語で、シングルスレッドプログラムのみ。 Flow-insensitiveな別名情報のみを使ったレジスタへの置き換えの欠点 a=ra b=rb *p=a+1 B1 B2  *rp=a+1 B1 rb=b ra=a b=a+1 a=a+1 B3  B4  rb=ra+1 B2 ra=ra+1 (y) Flow-insensitiveな別名情報 p→{a,b} フローグラフ全体で１つの結果 (x)のすべての場所で p→{a,b}   (x) Flow-insensitiveな別名解析 a,bの値はレジスタには乗せられないしかし  a,bの値を(y)のように出来ないか？   B1ではメモリアクセス B2ではレジスタアクセス手法１つ目（ブロックごとの別名参照のチェック）  *p=a+1 B1 b=a+1 a=a+1  B2  (x) 別名情報 p→{a,b} フローグラフ中の変数 v について  vが別名参照受けているブロック  vの値をメモリにしまった状態にする  ブロックの前後にメモリ-レジスタ転送命令の挿入 vが別名参照を受けていないブロック  vをレジスタに置き換える。 Flow-insensitiveな別名情報はあらかじめ得られていることが前提 AliasSourse(B)={x | Alias reference by x is in block B} Target(x)={v | v is alias target of x} AliasedBlock(v)={B | AliasSource(B) contains x such that Target(x) contains v} 手法１つ目（ブロックごとの別名参照のチェック）の例別名情報 p→{a} q→{c}  c=rc *q=a+1 B1 *rq=ra+1 B1 rc=c B5 B2 *p=a+b B4  B6 rc=c B7   a=ra (x) B3 B3 rc=ra+rb (y) B8   入口ブロックB7 出口ブロックB8 cが別名参照を受けているブロック=B1  B2 a=*rp+rb ra=a c=a+b aが別名参照を受けているブロック=B2 入口ブロックB4 出口ブロックB5,B6 それ以外の変数は別名参照を受けていない。手法２つ目（ブロックのグループ化） v=rv v=rv rv=v  B1 rv=v  v=rv B2 rv=v v=rv グループ形成の例 B3 斜線をつけたブロックで変数vが別名参照を受ける  rv=v B4 rv=v B5  v=rv B6 rv=v グループは {B1,B2,B3,B4}の１グループのみ B6はグループにならない手法２つ目（ブロックのグループ化）  先述の手法で、次の場合は別名参照の存在するブロックをグループ化する  変数vが別名参照を受けるブロック同士が有向辺でつながっている場合   先述の手法では、ブロック間のメモリ命令が無駄つながっているブロック同士をグループとして考える   グループの入口ブロックと出口ブロックを作り、メモリ-レジスタ転送命令を挿入グループ化できなかったブロックは先述の手法で処理手法２つ目（ブロックのグループ化）の例別名情報 p→{a,b} q→{a}  B1 *p=b B2 B3 *q=a+1 *p=a+1 B6 (x) B4 B5 *rp=b B1    rb=b B3 B2 *rq=a+1 B7 a=a+1 b=b+a a=ra b=rb aが別名参照を受けるブロック={B1,B2,B3} *rp=a+1 rb=b ra=a B8 ra=a ra=ra+1 rb=rb+ra (y) B4  {B1,B2,B3}がグループとなるグループの入口ブロック =B5 グループの出口ブロック =B7,B8 bが別名参照を受けるブロック={B1,B3}    {B1,B3}がグループとなるグループの入口ブロック =B5 グループの出口ブロック =B6,B8 利得の計算 b=0 (x) B1 *p=a+1 B2  削減できたメモリアクセス数より、挿入したメモリ命令数の方が多い場合  提案した手法は逆効果   利得の計算により未然にこれを防ぐ  rb=0 (y) a=ra B1 ra=a B4 Benefit(v) = Convert_v – Insert_v   B3 *rp=a+1 B2 (x)から(y)でメモリ命令が２つ増えている    Benefit(v) : 利得 Convert_v : 削減できるメモリ命令数 Insert_v : 挿入されるメモリ命令数利得が0を超える変数のみ置き換え静的なメモリアクセスの削減数を調べるので、必ずしも正確ではない。（近似的方法）実装について   Flow-insensitiveな別名解析アルゴリズムとして、Steensgaardのアルゴリズムを採用した COINSのLIR（低水準中間表現）に対して、提案した２つの手法を使い、レジスタへの置き換えを行う実験環境アーキテクチャ Superscalar SPARC Version9 プロセッサ種別 750MHz UltraSPARCⅢ １次キャッシュ 64KBデータ、32KBインストラクション２次キャッシュ 8MB 外部キャッシュメモリ容量 1GByte オペレーティング環境 SunOS 5.8 実験内容  テストプログラム   SPEC CPU2000より、164.gzip、175.vpr、181.mcf、197.parser、 254.gap、256.bzip2、300.twolf、183.equake、188.ammp、179.artの１０個。（複数のSSA最適化）=「最適化セットA」をかけてコンパイルを行った  実験１(coins)：COINS+最適化セットA  実験２(regpro)：COINS+最適化セットA+グローバル変数のみを対象としたレジスタプロモーション  実験３(steens)： COINS+最適化セットA+Steensgaardの別名解析結果を使ったレジスタ割り当て  実験４(bcheck)： COINS+最適化セットA+本研究の手法1 （ Steensgaardの別名解析結果を使用）  実験５(bgroup)： COINS+最適化セットA+本研究の手法2 （ Steensgaardの別名解析結果を使用）実験結果（実行時間） 110 105 100 95 90 85 80 75 70 65 60 164.gzip 175.vpr 181.mcf 197.parser coins 254.gap regpro steens 256.bzip2 bcheck 300.twolf 183.equak e bgroup coinsの実行時間を100%とした場合の相対比 188.ammp 179.art 実験結果（コンパイル時間） 275 250 225 200 175 150 125 100 75 50 25 0 164.gzip 175.vpr 181.mcf 197.parser coins 254.gap regpro steens 256.bzip2 bcheck 300.twolf 183.equak e bgroup coinsの実行時間を100%とした場合の相対比 188.ammp 179.art 実行時間に対する考察  提案した手法により平均３％、最大１５％程度の改善  181.mcf以外で、常にcoins,regpro>bcheck,bgroup が成立。   利得の計算が一定以上の水準を保てたことが伺える regpro>bcheck,bgroupは当然か   steensの順位は千差万別   regproの手法は非常に保守的 steensでは利得計算を行っていないためか 300.twolfではsteensよりもbcheck,bgroupが実行時間が長い  レジスタ圧力の増大が原因コンパイル時間に対する考察  全体的には増大は数％以内   coinsからbgroupの５つで、一部を除いて大きな変化はない 300.twolfではbcheck,bgroupでコンパイル時間が２倍以上かかっている  レジスタ圧力増大により、レジスタ割り当てフェーズで時間をとられたことが主な原因まとめと今後の課題  まとめ    本研究では、Flow-insensitiveな別名情報の精度の低さを独自の手法で補い、それを元にスカラー変数のレジスタへの置き換えを行った。全体的には、コンパイル時間の増大を抑え、かつ実行時間数％改善できた。今後の課題  レジスタ圧力による実行時間、コンパイル時間の改悪が目につく   レジスタ圧力をある程度予測する手法を考える利得の計算の精度を上げる   ループ構造など実行頻度を考慮した計算プロファイリングなどで取った動的なデータを元に計算するおしまい