レジスタ割り付けをしたい(1)データフローを作る

Scalaでx86_64コンパイラを作っているわけですが、現状のコンパイラはスタックに変数のメモリを割り当てて、
変数はメモリから取り出して計算してまたメモリに入れるという計算をしています。
通常のコンパイラでは出来るだけメモリアクセスは無くしてレジスタに割り付けた状態で処理を進める事で
高速化されています。

ですから、レジスタ割り付けがちゃんと行えるように出来ると非常によいコンパイラが作れることになります。
レジスタ割り付けをしたい。しかし、レジスタ割り付けをするには結構難しそうな、データフロー解析なるものを
しなくてはならないらしく、俺コンパイラプログラマにとって大きな難題となり立ちはだかっています。

そこで、ここではデータフロー解析を行いレジスタ割り付けを出来るようになろうと試みます。
試みた後成功した暁には、その成功した結果を元にできるだけ分かりやすく説明する事を試みたいと思います。

データフローはアセンブラのような命令リストから作る事ができる、データの流れを表した物です。

データフローは3つの集合(Set)の配列(Array)で表すことが出来ます。Setは連想配列の値が無いキーだけの物です。
JavaやScalaにはSetなるクラスがあるのでそれを使えばよいわけです。

データフローをScalaでClass定義として書けば以下のようになります。
class DataFlow(defs:Array[Set[String], uses:Array[Set[String]], succ:Array[Set[Int]])

defsは値を設定した変数名の集合(Set)の配列、
usesは使った変数名の集合(Set)の配列、
succは後続のアドレスの集合(Set)の配列です。
各集合の配列の長さはプログラムの命令列と同じ長さです。

例)
defは、a = 1だったら、Set("a")です。 b = c + d だったら b がdefに入ります。値が設定された変数名が入るのが、defです。
useは使われた変数なので a = 1ならつかわれた変数は無いのでSet() b = c + dだったら cとdが使われるので、Set(c,d)です。
succは、次のアドレスが入るので、通常は次のアドレスが入るだけです。分岐命令では2つ goto文はとび先、returnは次が無いので空になります。

データフローの作成はプログラム配列からこれらの集合の配列を作る事だけなのでとても簡単です。
簡単なので、タイガーブックで等では記述されてなくて、初心者としては困ると思うのですけど、エロい人には分からんのです。

Scalaの関数として作れば以下のような関数を作る事になります。

def dataflow(prgs:List[Instruction]):DataFlow

以下にScalaで書いたデータフローを作成するプログラムを示します。
上の説明で用いたデータ構造は短く書く為に使用していませんが動作します。

object dataflow extends Application {

  // プログラム命令列
  val prgs = List(
    ("mov", "a",0),
    ("add", "b","a",1),
    ("add", "c","c","b"),
    ("mul", "a","b",2),
    ("cmpjp", "a", 10, 1),
    ("return", "c")
  )
  println("prgs "+prgs)

  // データフロー作成
  def dataflow(prgs:List[Any]):
   (Array[Set[String]], Array[Set[String]], Array[Set[Int]]) = {


	// プログラムのサイズ
    val size = prgs.size
	
	// 各集合を作成
    val defs = new Array[Set[String]](size)
    val uses = new Array[Set[String]](size)
    val succ = new Array[Set[Int]](size)

	// 変数を使っている集合を取得
    def set(n:Any):Set[String] = n match {
      case n:String => Set(n)
      case n => Set()
    }

	// サイズ分ループ
	for(i <- 0 until size) {

	  val n = i + 1 // 命令の次のアドレス
	  
	  // 命令ごとに値を取得
      val (def1, use1, succ1) = prgs(i) match {
        case ("mov", a, b) =>
          (set(a),set(b),Set(n))
        case ("add",a, b, c) =>
          (set(a), set(b) ++ set(c), Set(n))
        case ("mul",a, b, c) =>
          (set(a), set(b) ++ set(c), Set(n))
        case ("cmpjp", a, b, c:Int) =>
          (Set[String](), set(a) ++ set(b), Set(n, c))
        case ("return", a) =>
          (Set[String](), set(a), Set(n))
      }
	  // 各集合配列に保存
      defs(i) = def1
      uses(i) = use1
      succ(i) = succ1
    }
	// 結果を返す
    (defs, uses, succ)
  }
  val (defs,uses,succ) = dataflow(prgs)
}

prgsがプログラムのListです。
dataflow関数がデータフローを作成する関数で、prgsを受け取って,defs,uses,succを返します。
dataflow関数ではまず、プログラムのサイズを求め、そのサイズの集合の配列を3つ作ります。
次に命令リストをループで周り取り出して、各命令の変数の定義、仕様、後続アドレスを求めて配列に保存しています。
内部のset関数は変数かどうかを判定して変数だった場合にのみ集合に追加して返す補助関数となっています。
このようにして、データフローを作る事ができます。

いかがでしょうか？データフロー解析がより身近に感じる事が出来たのではないでしょうか？
実際にコンパイルして実行してみてください。そして、自分なりによく考えて書き換えてみてください。
そうすればより理解が進み、たいした事ではなくなるでしょう。

参考文献:

タイガーブック: http://www.amazon.co.jp/dp/4798114685/?tag=hatena_st1-22&ascsubtag=d-9br2
ブログ: http://d.hatena.ne.jp/matt-k/20080530
mincaml: http://min-caml.sourceforge.net/

https://github.com/joshcough/Compilers
http://www.eecs.northwestern.edu/~robby/courses/322-2011-spring/