coins memo no.5

コンパイラ coins

前回の記事はこちら

coins関係はこちら

で，具体的に最適化器をつくる．

今回はビットベクタ法を用いたデータフロー解析を行って定数伝搬の最適化を行う．

(ビットベクタ法に関する論文はコチラ : Uday.P, et.al., A generalized theory of bit vector data flow analysis, ACM Tran. on Prog. Lang. and Sys. ,16 ,5 ,1472 (1994))

で，実装の参考にこちらの"データフロー解析を用いた共通部分式除去"のソースコードを,

coins組み込みにはこちらの"低水準中間表現(LIR)での最適化"を参考にした．

また，coinsの低水準中間表現方式(Low Intermediate Representaion, LIR)についてはこちら．このリンク先の図を見ながらLIRの内部表現を学習すると理解が早い．

で，まずは全体の流れ．

4つ組(3番地形式)の制御フローグラフのデータフロー解析をおこない，到達定義を計算して定数伝搬の最適化を行う．

到達定義は教科書等に出ているその定義をもとに計算する．

それ以外の実装の基本となるアルゴリズムは

  • ビットベクタ法

要素iを持つ有限領域上の集合Sはビットベクタで表現できる．
ビットベクタを用いると各種演算が集合演算になる為，実行が高速である．
具体的にはcoinsでは"coins.ssa.BitVector"クラスが利用可能である．

  • 基本ブロック

基本ブロックにinstructionをまとめることによりgenとkillとinとoutの数を減らせる．
coinsでは基本ブロックを"coins.backend.dfg.BasicBlk"クラス，基本ブロック内の文を"coins.backend.lir.LirNode"で表現する．
その中身はリスト構造である．
他にもLirNodeへのリンクやリストを表す"coins.backend.uti.BiLink", "coins.backend.util.BiLink"などがある．
JavaScriptのDOMや，S式の操作を考えると理解しやすい．

  • 節の順序付け

制御フローグラフをトポロジカル整列することによりデータフロー解析を1パスで完了する．
LIR内部表現の仕様BasicBlkクラスのオブジェクトはpredecessorとsuccessorのリストを返すメソッドを持つので(predList()とsuccList())
多分おk．

  • 使用定義(UD)チェイン

到達定義の情報は，変数の各使用に到達する定義リスト"使用定義チェイン"を用いて保持できる．
これを用いる事で効率的に最適化アルゴリズムを実装できる．

UDチェインはいずれかのout集合が変更されると，すべての4つ組を再計算する必要が有る．
これを効率的に行うために，out集合が再計算されなければならない部分だけをワークリストに保持しておく．
実際はprocedure initの最後で，outの変化のチェックを行い，outの変化の有ったものをワークリストに入れておく．
procedure settleで，ワークリストの中身をprocedure propagateに渡してやり，何度もoutを再計算させ，
変化が無くなるまでprocedure propagateを再帰させる．

となる．参考にしたprocedure doItの流れ.

だいたいこんな感じ．

0.ターゲットとなる関数functionと不変リストargs(実際ここでは使わない多分)を受け取る
1.kill,gen,in,outのビットベクタの配列を作成(すべての要素数のサイズで)
2.変数代入が生じる箇所のid(変数名)を作成し，idMapの数をカウント(expId)する．ここがgenとkillの対象となる．
prcedure collectExpは，基本ブロックを引数に取り，基本ブロックのBiLinkを辿って各文をチェックする．
代入文，すなわちoperater SETのものにユニークなidを振る．
d : t <- b binop c
d : t <- M[b]
d : t <- f(a1, ... ,an)
3.kill,gen,in,outの各ビットベクタにexpIdのサイズで初期化
4.procedure init
4.1各基本ブロックのgenとkillを初期化(procedure initGenKill)
4.1.1procedure initGenKill
genとkillを設定して，置き換えできそうなところをスタックに詰めておく．
4.2inからoutを計算
4.3outの変化したものをワークリストworklistに詰めておく．
5.procedure settle
ワークリストworklistにそってを用いてoutの再計算をする．
procedure propagateは再帰関数になっているので，再計算前後のoutを比較してさらに伝播をおこなう
6.update()
実際に定数伝播の置換を行う．
7.f.flowGraph.touch()
変更の適用
8return
おわた

多分，こんなかんじか．．．うお，キツい．

続きはまた．．．