■

Sethi Ulluman Register Allocation
セシーウルマンレジスタアロケーション

あけましておめでとうございます。 h_sakurai です。今年もよろしくお願いします。
というわけで、＜どういうわけだ
レジスタアロケーションを勉強中なわけですが、基本からもう一度勉強してみました。

まず、スタックマシンを使えばレジスタアロケーションをせずに、言語を作る事ができます。
だから、スタックマシンは簡単でいいわけです。
でスタックマシンの次にレジスタアロケーションを簡単に行う方法が、Sethi Ullman Register Allocation です。
このアルゴリズムでは１つのネストした式に対して、レジスタアロケーションを行います。
セシウルマンのアルゴリズムは２つのパートに分かれていまして、
１つ目のパートでは、ラベル名をつけます。
２つ目のパートでは、ラベルを使ってルートから探索して、コードを生成します。
完全ではないかもしれませんが、以下にセシウルマンのレジスタアロケーションのサンプルコードを示します。

ということを、ここ３連休で調べてみてました。
次に、セミグローバルなレジスタアロケーションをやってみて、リニアレジスタアロケーションを把握して、
最後にグラフによるレジスタアロケーションをもう一度見直してみようと思っています。
やっぱり、基本をしっかり押さえないとねっ。

package compiler

object SethiUllmanRegisterAllocation {
  def main(argv: Array[String]) {
    val exp = ("add",
      ("mul", "a", "b"),
      ("add",
        ("add", "a", "c"),
        ("mul", "d", "e")))

    val rc = visit(null, exp)
    println(rc)
    genCode(rc, List("r1"), 1)
  }

  def max(a: Int, b: Int): Int = {
    if (a > b) a else b
  }
  def visit(parent: Any, t: Any): (Any, Int) = {
    (parent, t) match {
      // 親ノードのとき
      case (_, (op, n1, n2)) =>
        val (nn1, j) = visit(t, n1)
        val (nn2, k) = visit(t, n2)
        val v = if (j == k) j + 1 else max(j, k)
        ((op, (nn1, j), (nn2, k)), v)
      // 葉ノードのとき
      case ((op, a, b), c) =>
        val v = if (c == a) 1 else 0
        (c, v)
    }
  }

  def gen(s: String) {
    println(s)
  }
  def genCode(n: Any, reglist: List[String], tmp: Int): String = {
    n match {
      case (x: String, n) =>
        val r = reglist.first
        gen("load " + r + ", " + x)
        r
      case ((op: String, n1, (x, 0)), _) =>
        val r = genCode(n1, reglist, tmp)
        gen(op + " " + r + ", " + r + ", " + x)
        r
      case ((op: String, n1 @ (_, j: Int), n2 @ (_, k: Int)), _) =>
        if (k <= j && k < reglist.size) {
          val r1 = genCode(n1, reglist, tmp)
          val r2 = genCode(n2, reglist - r1, tmp)
          gen(op + " " + r1 + ", " + r1 + ", " + r2)
          r1
        } else if (k > j && j < reglist.size) {
          val r1 = genCode(n2, reglist, tmp)
          val r2 = genCode(n1, reglist - r1, tmp)
          gen(op + " " + r1 + ", " + r1 + ", " + r2)
          r1
        } else if (k >= reglist.size) {
          val r = genCode(n2, reglist, tmp)
          gen("store " + r + ", t" + tmp)
          val r2 = genCode(n1, reglist, tmp + 1)
          gen(op + " " + r2 + ", " + r2 + ", t" + tmp)
          r2
        } else {
          "error"
        }
      case _ => "error"
    }
  }
}

実行結果

((add,((mul,(a,1),(b,0)),1),((add,((add,(a,1),(c,0)),1),((mul,(d,1),(e,0)),1)),2)),2)
load r1, d
mul r1, r1, e
store r1, t1
load r1, a
add r1, r1, c
add r1, r1, t1
store r1, t1
load r1, a
mul r1, r1, b
add r1, r1, t1

参考

http://pages.cs.wisc.edu/~cs701-1/NOTES/5.REGISTER-ALLOCATION.html