パターンマッチの作り方(2) LLVM入門

今回は、加算、減算が出来るコンパイラをScalaで実装します。
ターゲットとしている環境はx86-64のmac osxです。

## 実装内容

Scalaで行う事は構文木からe.llファイルを出力し、LLVMのllcコマンドでe.sを作成しgccでe.sを実行ファイルに変換します。テストが面倒なので実行もして結果を表示します。

コンパイラの構成は[MinCaml](http://min-caml.sourceforge.net/)[1]を参考にしています。

## LLVMのインストール

OSXの環境の場合、[LLVMのダウンロードページ](http://llvm.org/releases/download.html)からバイナリをダウンロードし、パスを通します。xcodeが入っていない場合は、xcodeのインストールも必要です。

LLVMの言語の詳細については[LLVM言語マニュアル(翻訳版)](http://www.h3.dion.ne.jp/~mu-ra/llvm/LangRefJ.html)[2]や[LLVM言語マニュアル](http://llvm.org/docs/LangRef.html)[3]を参照してください。LLVMのインストールの詳細はここでは説明しません。LLCが使えるように環境を整えてください。[LLVM入門](http://www.slideshare.net/herumi/llvm-17911004)[4]や[EmscriptenとLDCを使えばD言語のSDLゲームがブラウザで動かせる、かも](http://d.hatena.ne.jp/ABA/20130331#p1)[5]等を参考にインストールしてください。書籍では[きつねさんでもわかるLLVM PDF版](http://tatsu-zine.com/books/llvm)[6]や[きつねさんでもわかるLLVM](http://www.amazon.co.jp/%E3%81%8D%E3%81%A4%E3%81%AD%E3%81%95%E3%82%93%E3%81%A7%E3%82%82%E3%82%8F%E3%81%8B%E3%82%8BLLVM-~%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%92%E8%87%AA%E4%BD%9C%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%AC%E3%82%A4%E3%83%89%E3%83%96%E3%83%83%E3%82%AF~-%E6%9F%8F%E6%9C%A8-%E9%A4%85%E5%AD%90/dp/4844334158)[7]が参考になるでしょう。

## 実装の詳細

Eが式を表します。

```scala:
sealed trait E {
  def t:T
}
case class ELdc(t:T, i:Long) extends E
case class EBin(t:T, s:String, l:E, r:E) extends E
case class EPrint(t:T, a:E) extends E
case class EBlock(t: T, ls: List[E]) extends E
```

Tが型を表します。

```scala:
sealed trait T
case class Ti(i:Int) extends T
case object Tv extends T
case class TFun(t: T, prms: List[T]) extends T
```

補助関数としてEAdd,EMulを作ります。ここはkmizuさんに教えてもらって短く書けています。

```scala:
case class Op(s: String) {
  def apply(t: T, a: E, b: E): E = {
    EBin(t, s, a, b)
  }
}
object EAdd extends Op("add")
object EMul extends Op("mul")
```

Rはレジスタを表します。

```scala:
sealed trait R {
  def t:T
  def id:String
}
case class RG(t:T, id: String) extends R
case class RL(t:T, id: String) extends R
case class RR(t:T, id: String) extends R
case class RN(t:T, id: String) extends R
```
emit.llrでプリンターを定義しています。

```scala:
  def llr(r:R): String = {
    r match {
      case RG(t,id) => "@" + id
      case RL(t,id) => "%" + id
      case RR(t,id) => "%." + id
      case RN(t,id) => "" + id
    }
  }
```

testオブジェクトがメイン関数で、テスト用のastを用意し、コンパイル、実行をしています。

```scala:
object test {
  def main(argv: Array[String]) {
    try {
      val ast = EBlock(Tv, List(
        EPrint(Ti(32), ELdc(Ti(32), 11)),
        EPrint(Ti(32), EAdd(Ti(32), ELdc(Ti(32), 11), ELdc(Ti(32), 22)))
      ))
      println("ast=" + ast)
      val ll = kNormal(ast)
      println("ll=" + ll)
      emit("e.ll", ll)
      println(exec("llc e.ll -o e.s"))
      println(exec("llvm-gcc -m64 e.s -o e"))
      println(exec("./e"))
    } catch {
      case e:Throwable => e.printStackTrace()
    }
  }
}
```

object kNormal は長くなるのでソースは省略しますが、複雑な式を平たくしEをLLに変換します。addメソッドでリストにLLを追加しています。

LLはLLVMのアセンブラをデータとして扱えるようにしたものです。

```scala:
sealed trait LL
case class LLCall(id: R, op: R, prms: List[(T, R)]) extends LL
case class LLBin(id: R, op: String, a: R, b: R) extends LL
```

最後にemitでLLをasmを使ってファイルに出力します。
lltで型を文字列に変換し、llrでレジスタを文字列に変換します。
oは```a=hoge```という出力をするための補助関数です。fが変換の本体。applyでは、print_i32とprint_i8関数とメイン関数を作成し、fを呼び出しています。

genidは新しくidを作る関数で、文字列を受け取り、毎回カウントアップされるカウント値を付けて返します。
asmはファイルをオープンし文字列を出力するオブジェクトです。ラベルを使う時はlabelメソッドを使い、通常はasmで出力します。インラインアセンブラを使うような感覚でLLVMのコードを出力するので分かりやすいのではないかと考えています。
execは外部プロセスを起動して、結果の値と標準出力、エラー出力の結果をタプルで返します。

以下に実装の全体を示します。

```scala:
package chapter02

import java.io._

sealed trait E {
  def t:T
}
case class ELdc(t:T, i:Long) extends E
case class EBin(t:T, s:String, l:E, r:E) extends E
case class EPrint(t:T, a:E) extends E
case class EBlock(t: T, ls: List[E]) extends E

sealed trait T
case class Ti(i:Int) extends T
case object Tv extends T
case class TFun(t: T, prms: List[T]) extends T

case class Op(s: String) {
  def apply(t: T, a: E, b: E): E = {
    EBin(t, s, a, b)
  }
}
object EAdd extends Op("add")
object EMul extends Op("mul")

sealed trait R {
  def t:T
  def id:String
}
case class RG(t:T, id: String) extends R
case class RL(t:T, id: String) extends R
case class RR(t:T, id: String) extends R
case class RN(t:T, id: String) extends R

object test {
  def main(argv: Array[String]) {
    try {
      val ast = EBlock(Tv, List(
        EPrint(Ti(32), ELdc(Ti(32), 11)),
        EPrint(Ti(32), EAdd(Ti(32), ELdc(Ti(32), 11), ELdc(Ti(32), 22)))
      ))
      println("ast=" + ast)
      val ll = kNormal(ast)
      println("ll=" + ll)
      emit("e.ll", ll)
      println(exec("llc e.ll -o e.s"))
      println(exec("llvm-gcc -m64 e.s -o e"))
      println(exec("./e"))
    } catch {
      case e:Throwable => e.printStackTrace()
    }
  }
}

object kNormal {
  def gid(t:T): R = {
    RR(t,genid(""))
  }
  var ls: List[LL] = null
  def add(l: LL) {
    ls = l :: ls
  }
  
  def f(a: E): R = {
    a match {
      case EBin(t, op, a1, b1) =>
        (f(a1), f(b1), gid(t)) match {
          case (a, b, id) =>
            if (t != a.t || t != b.t) throw new Exception("type mismatch " + t)
            add(LLBin(id, op, a, b))
            id
        }
      case ELdc(t, i) => RN(t, ""+i)
      case EPrint(t, a) =>
        f(a) match {
          case a =>
            if (t != a.t) throw new Exception("type mismatch t=" + t + " ta=" + a.t)
            add(LLCall(null, RG(TFun(Tv, List(t)), "print_" + emit.llt(t)), List((a.t, a))))
            a
        }
      case EBlock(t, ls) =>
        ls.foldLeft(null: R) {
          case (tid, l) => f(l)
        }
    }
  }

  def apply(a: E): List[LL] = {
    ls = List[LL]()
    f(a)
    ls.reverse
  }
}

sealed trait LL
case class LLCall(id: R, op: R, prms: List[(T, R)]) extends LL
case class LLBin(id: R, op: String, a: R, b: R) extends LL

object emit {

  def llt(t:T):String = {
    t match {
      case Ti(i) => "i" + i
      case Tv => "void"
      case TFun(t, ls) => llt(t) + "(" + ls.map(llt).mkString(", ") + ")*"
    }
  }

  def llr(r:R): String = {
    r match {
      case RG(t,id) => "@" + id
      case RL(t,id) => "%" + id
      case RR(t,id) => "%." + id
      case RN(t,id) => "" + id
    }
  }
  
  def o(id: R, out: String) {
    if (id != null) asm(llr(id) + " = " + out)
    else asm(out)
  }
  def f(l: LL) {
    l match {
      case LLCall(id, op, prms) =>
        val ps = prms.map { case (a, b) => llt(a) + " " + llr(b) }.mkString(", ")
        o(id, "call " + llt(op.t) + " " + llr(op) + "(" + ps + ") nounwind")
      case LLBin(id, op, a, b) =>
        o(id, op + " " + llt(id.t) + " " + llr(a) + ", " + llr(b))
    }
  }


  def apply(file: String, ls: List[LL]) {
    asm.open(file)
    asm.label("@.str = private constant [4 x i8] c\"%d\\0A\\00\"")
    asm.label("define void @print_i32(i32 %a) nounwind ssp {")
    asm.label("entry:")
    asm("call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), i32 %a) nounwind")
    asm("ret void")
    asm.label("}")
    asm.label("define void @print_i8(i8 %a) nounwind ssp {")
    asm.label("entry:")
    asm("call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), i8 %a) nounwind")
    asm("ret void")
    asm.label("}")

    asm.label("declare i32 @printf(i8*, ...) nounwind")

    asm.label("define i32 @main() nounwind ssp {")
    asm.label("entry:")
    ls.foreach(f)
    asm("ret i32 0")
    asm.label("}")
    asm.close()
  }
}

object genid {
  var id = 0
  def apply(s: String): String = {
    id += 1
    s + id
  }
}
object asm {
  var p: PrintWriter = null
  def open(file: String) {
    p = new PrintWriter(new BufferedWriter(new FileWriter(file)))
  }

  var indent: String = ""

  def apply(s: String, n: String = "") {
    val v = indent + s + "\t" + n + "\n"
    p.print(v)
  }
  def label(s: String) {
    asm.indent = "";
    apply(s)
    asm.indent = "\t";
  }
  def close() {
    p.close()
  }
}

object exec {
  def apply(cmd: String): (Int, String, String) = {
    val p = Runtime.getRuntime().exec(cmd)
    val stdin = (readAll(p.getInputStream()))
    val stderr = (readAll(p.getErrorStream()))
    (p.waitFor(), stdin, stderr)
  }

  def readAll(p: InputStream): String = {
    def f(s: String, i: BufferedReader): String = {
      i.readLine() match {
        case null => s
        case a => f(s + a + "\n", i)
      }
    }
    f("", new BufferedReader(new InputStreamReader(p)))
  }
}
```

## まとめ

LLVMを使って加算、乗算が出来るコンパイラをつくりました。


## 参考文献

- [1][MinCaml](http://min-caml.sourceforge.net/)
- [2][LLVM言語マニュアル(翻訳版)](http://www.h3.dion.ne.jp/~mu-ra/llvm/LangRefJ.html)
- [3][LLVM言語マニュアル](http://llvm.org/docs/LangRef.html)
- [4][LLVM入門](http://www.slideshare.net/herumi/llvm-17911004)
- [5][EmscriptenとLDCを使えばD言語のSDLゲームがブラウザで動かせる、かも](http://d.hatena.ne.jp/ABA/20130331#p1)
- [6][きつねさんでもわかるLLVM 柏木餅子, 風薬 PDF版](http://tatsu-zine.com/books/llvm)
- [7][きつねさんでもわかるLLVM 柏木餅子, 風薬](http://www.amazon.co.jp/%E3%81%8D%E3%81%A4%E3%81%AD%E3%81%95%E3%82%93%E3%81%A7%E3%82%82%E3%82%8F%E3%81%8B%E3%82%8BLLVM-~%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%82%92%E8%87%AA%E4%BD%9C%E3%81%99%E3%82%8B%E3%81%9F%E3%82%81%E3%81%AE%E3%82%AC%E3%82%A4%E3%83%89%E3%83%96%E3%83%83%E3%82%AF~-%E6%9F%8F%E6%9C%A8-%E9%A4%85%E5%AD%90/dp/4844334158)