レジスタ割り付けをしたい(2)生存情報を求める。

だいぶ、時間が空いてしまい、自分の中でもなにがどうなっているのかわからなくなってきてしまいました。
やばい。風化する。ソースがどこかに消えてしまう。
消える前に、多少分かりにくくとも、きちんと記録に残さねばならない。
という、使命感にかられこの記事を核次第なのであります。

で、前回は、データフローを作った訳ですが、今回はこのデータフローを元に、変数がどの時点で生きてて、
どの時点で使われなくなるかという生存情報(liveness)を求めます。
生存情報はデータフローのdef,use,succの情報から、入力(in)と出力(out)を再帰的に繰り返して値が変わらなくなるまで
計算する事で求めることができます。

まず最初に、out,inの集合を入れる為の各配列を用意します。長さはプログラムコードと同じサイズにします。
で、変更フラグをtrueにしておいて、全プログラムを更新します。
更新した結果、変化フラグがfalseになるまで繰り返します。

更新処理では、更新があったかどうかを調べる為に、in,outの集合のサイズを求めておきます。
そして、 in(n) = uses(n) ++ (out(n) -- defs(n))
の計算をして、inを更新します。
次に、outの更新を以下のように行います。
succ(n).foreach{ adr => out(n) = out(n) ++ in(adr) }
これで、in,outのサイズが変わっていれば更新したことになります。
と、この計算を繰り返すことで、生存区間を求める事が出来ます。
以下にソースを示します。
タイガーブック等では難しく感じてたのですが、書いてみればあっさりした物です。
これを、より高速化したり、追加することで発展する事ができるようです。
このプログラムで最終的などのデータが入って来て、どのデータが使われるのかが分かるようになります。
この生存情報を使えば、どの変数がどの変数と一緒に使われているかを求める事ができます。

次回は、ここで求めた生存情報を元に、どの変数とどの変数が同じ時間に使われるかを表す、干渉グラフを作ります。
干渉グラフというと難しそうですが、なんて事は無い、Map[変数名,Set[変数名]]を作るだけです。
Mapを写像、Setを集合というので難しく感じますけど。
そして、干渉グラフを使って、変数に色を塗れば、レジスタ割り付けが出来るのです。

object liveness extends Application {
  val (in,out) = liveness(uses, defs, succ)
  println("live in " + in.toList)
  println("live out " + out.toList)
  def liveness(
    uses:Array[Set[String]],
    defs:Array[Set[String]],
    succ:Array[Set[Int]]) : (Array[Set[String]],Array[Set[String]]) = {
    val size = uses.size
    val out = new Array[Set[String]](size)
    val in = new Array[Set[String]](size)
    var change = true
    def update(n:Int) {
      val (isize, osize) = (in(n).size, out(n).size)
      in(n) = uses(n) ++ (out(n) -- defs(n))
      succ(n).foreach{ adr => out(n) = out(n) ++ in(adr) }
      if (isize != in(n).size || osize != out(n).size) change = true
    }
    for (i <- 0 until size) {
      in(i) = Set[String]()
      out(i) = Set[String]()
    }
    while (change) {
      change = false
      for (i <- 0 until size) {
        update(i)
      }
      println("in  "+in .toList)
      println("out "+out.toList)

    }
    (in,out)
  }
}