パターンマッチ実装奮闘記(4)

前回は、四則演算や、構造体等基本的な機能をLLVMで実装しました。というか、あるものを物置から探してきて、作り方を書いてみたのでした。今回は、まだ実装した事がないswitch構文を使ってみます。実装した事が無いので、ちゃんと記録を書いていました。偉い俺。ってことで、LLVMのswitchを作るんだぜ。


## LLVMのswitch

LLVMのswitchは値によってどこかにジャンプするいわゆるテーブルジャンプの機能しかありません。また、テーブルにある値でなければ、デフォルトのジャンプを行います。

```llvm
; %dataが0のときラベル%bbに、1のときラベル%bb1に、それ以外のときラベル%bb2にジャンプする。
switch i32 %data, label %bb2 [
    i32 0, label %bb
    i32 1, label %bb1
  ]
bb:
:
:
	br label %bb2
bb1:
:
:
	br label %bb2
bb2:
```

## コンパイラ上の表現

ASTは以下のようにする事にします。

```
case class ESwitch(t: T, a: E, cases:List[(E,E)] ) extends E
```

LLVMのswitchは以下のデータで表します。

```
case class LLSwitch(t: T, reg:Id, label:String, cases:List[(Long,String)]) extends LL
case class LLGoto(label:String) extends LL
```
LLGotoでブランチを表す事とします。

ESwichの使い方は、以下のように使います。

```scala
ESwitch(Ti(32), ELdc(Ti(32), 2), List(
  ELdc(Ti(32), 1) -> EPrint(Ti(32), ELdc(Ti(32), 1)),
  ELdc(Ti(32), 2) -> EPrint(Ti(32), ELdc(Ti(32), 2)),
  ELdc(Ti(32), 3) -> EPrint(Ti(32), ELdc(Ti(32), 3)),
  EUnit -> EPrint(Ti(32), ELdc(Ti(32), 0))
))
```

コンパイラではざっくり以下のような処理を行えば良さそうです。

```scala
case ESwitch(t: T, a;E, cases:(E,E)) extends E =>
  val ra = compile(a) // 式をコンパイル
  val lbl = genid("switch") // ラベルを作成
  // ケースごとにループして数値とラベルのペアを作成
  val (length,ls) = cases.foldLeft(0,List()) {
    case ((n,ls),(EInt(a),_))=> (n+1,(a, lbl+n)::ls)
  }
  // LLVMのswitchのコードを出力
  add(LLSwitch(t, ra, lbl, ls.reverse))
  // 分岐後のコードを出力
  cases.foldLeft(0) {
    case (n,(_,e))=> add(LLLabel(lbl+n)); compile(e); add(LLGoto(lbl)); n+1 
  }
  ```

## 実装

方針は固まったので実装しました。以下が実装した内容です。

```scala

// alpha
      case e @ ESwitch(t: T, a: E, cases:List[(E,E)]) =>
        val (a1, env1) = f(a, env)
        val (cases1, env2) = cases.foldLeft(List[(E,E)](), env1) {
          case ((ls, env), (a,b)) =>
            val (a1, env1) = f(a, env)
            val (b1, env2) = f(b, env1)
            (((a1,b1) :: ls), env2)
        }
        (e.copy(t, a1, cases1), env2)

// kNormal
      case ESwitch(t: T, a: E, cases:List[(E,E)]) =>
        val (rt, ra) = f(a)
        val lbl = genid("switch")
        val (length,ls) = cases.foldLeft(0,List[(Long,String)]()) {
          case ((n,ls),(ELdc(tl, a),_))=> (n+1,(a, lbl+n)::ls)
          case ((n,ls),(EUnit,_)) => (n+1, (-1L, lbl+n)::ls)
        }
        add(LLSwitch(t, ra, lbl, ls.reverse))
        
        cases.foldLeft(0) {
          case (n,(_,e))=> add(LLLabel(lbl+n)); f(e); add(LLGoto(lbl)); n+1 
        }
        add(LLLabel(lbl))
        (t, null)
      case EUnit =>
        (Tv, null)

// constFold
      case (ls, l @ LLSwitch(t, n, lbl, cases)) => l.copy(t, m(n), lbl, cases)::ls
      case (ls, l @ LLLabel(_)) => l::ls
      case (ls, l @ LLGoto(_)) => l::ls

// emit
      case LLSwitch(t, n, lbl, cases) =>
        asm("switch "+t+" "+n+", label %"+lbl+ " [")
        for((a,b) <- cases) {
          asm("  i32 " + a + ", label %"+b)
        }
        asm("]")
      case LLLabel(l) =>
        asm(l+":")
      case LLGoto(l) =>
        asm("br label %"+l)

```

とつぜん、ここだけソース書かれてもって感じですよね。
alphaでは別名付ける処理関数のfってのがあって、そいつの中で、トラバースしてます。kNormalがEっていう式のデータを受け取って、addっちうメソッドでLLうんたらいうデータを出力してます。で、このまま出力したいんだけど、a=1みたいなことをLLVMでは出来ないので、定数が入ったレジスタは展開sてしまうのがconstFoldで、mって関数でレジスタが定数だったらレジスタに書き換える処理です。
emitでは、LLSwitch,LLLabel,LLGotoを受け取って、文字列を出力してます。

## まとめ

今回はswitchを作ってみました。

細かい動作まで考えるともっとしっかり作り込まないと行けません。しかし、今回実装したレベルのswitchがあれば、パターンマッチは実装出来そうです。そして、簡単なパターンマッチを作るのが目的なのでこの辺にしておきましょう。次回は、パターンマッチの実装を考えて行きます。