読者です 読者をやめる 読者になる 読者になる

マシンスタックをコピペするのはやめたほうがいい

Picrinでcall/cc周りのissueが届いた。masterがlinux環境でsegvを起こすらしい。発生条件は2つで、-O2でコンパイルすることとcall/ccを使うこと。Macでは大丈夫っていうのもアレだけれども-O2をつけた時だけっていうのもなかなか味わい深い。

f:id:wasabiz:20160304033419p:plain

とりあえずcallccのコードを眺めてみる。基本的にはscheme VMのスタックとマシンスタックをがばっとコピーしてヒープに保存しているだけ。残りの処理はschemeの手続き化するためのもの。

static pic_value
pic_callcc(pic_state *pic, pic_value proc)
{
  struct fullcont *cont = pic_malloc(pic, sizeof(struct fullcont));   // 継続関連の情報全部入り構造体

  save_cont(pic, cont);                          // VMスタック、VMレジスタ、マシンスタックを保存
  if (setjmp(cont->jmp) != 0) {            // マシンレジスタを保存
    return pic_valuesk(pic, cont->retc, cont->retv);
  } else {
    pic_value c[1];

    /* save the continuation object in proc */
    c[0] = pic_lambda(pic, cont_call, 1, pic_data_value(pic, cont, &cont_type)); // Schemeの値に変換

    return pic_applyk(pic, proc, 1, c);
  }
}

volatileつけたりしてみたけど特に効果なし。仕方ないのでこいつのアセンブリを眺めてみる。以下コード内のコメントの通り。

_pic_callcc:
LFB39:
LM155:
LVL84:
    pushq   %r14
LCFI38:
    movq    %rdi, %r14
    pushq   %rbx
LCFI39:
    subq    $56, %rsp
LCFI40:
LM156:
    movq    %rsi, 24(%rsp)
LM157:
    movl    $288, %esi
LVL85:
    call    _pic_malloc // contを確保。まだメモリには保存していない(contはraxの中)
LVL86:
LM158:
    movq    %r14, %rdi
    movq    %r14, 16(%rsp)
LM159:
    movq    %rax, %rbx
LM160:
    movq    %rax, %rsi
    call    _save_cont // マシンスタックをコピー。この時点でもまだcontはレジスタの中
LVL87:
LM161:
    movq    %rbx, %rdi
    movq    %rbx, 8(%rsp) // setjmpを呼ぶためにcontを退避
    call    _setjmp
LVL88:
    testl   %eax, %eax
    je  L61
LM162:         // 継続が起動
    movq    8(%rsp), %rax // contをraxではなくメモリから取ってきているだと…
    movq    16(%rsp), %rdi
    movq    280(%rax), %rdx
    movl    272(%rax), %esi
    call    _pic_valuesk

ぼく「(1)マシンスタックを保存したあと、(2)マシンレジスタを保存しよう」 gcc「(1')マシンスタックを保存するまではレジスタを使って、(2')マシンレジスタを保存した後はスタックを使おう」

みなさんも未定義動作を悪用したりすると痛い目にあうので気をつけましょう。

Operationalモナドを使って動的型付言語で多相的にモナドする

もう2ヶ月以上前ですが「Schemeのための合成可能かつ多相的なモナドライブラリ」というタイトルで発表してきました。「Schemeのための」とついてますが動的型付き言語全般で使える話です。

Brainfxxkの処理系を書くというアレ

言語実装Advent Calendar 2015の記事です。6日目です。

本当に何もネタを思いつかなかったので昔書いたBrainfxxkの処理系を作った話をします。ただし回路です。

wasabiz/chisel-brainfuck · GitHub

実はブログで以前ちょろっと言及していたようですが中身の話はしていなかったので細かいところについて書きます。誰向けの記事なのか自分でも全くわからないですがとにかく書いてみます。

chisel-brainfuckはChiselというHDLで書かれたBFを実行する何かです。一応メモリのような何かとIOのような何かが付いているのでCPUと言っても良さそうです。ChiselはScalaDSLで、コンパイルして実行するとVerilogC++のシミュレータを吐いてくれます(≠高位合成)。もともとchisel-brainfuckは半年以上前にChiselを勉強するために書いたものでした。なので今から見るといろいろアレな部分があるので中身の解説をしながらリファクタリングしていって残りの余白を埋めようと思います。

中身は単一サイクルのシンプルなCPUです。BFを直接実行するわけではなくコンパイル済みのバイナリを実行します。ちなみにリポジトリをよく見るとコンパイラも付属してます。最初に作ろうとした時はBFを直接実行できるようにしようかと思ったのですがHWスタックを使うのはダサいのでやめました。いろいろ考えるのが面倒だったのでハーバード・アーキテクチャにしてあります。あとChiselをよく知らなかったので無駄にBehavioralに書いてます。その辺を直しながら話を進めていきます。主記憶は読み出し非同期のRAMを想定しているのでソースコードを読むとそのまんま動作が分かります。

まずはメモリからデータを読みだして、

    // read
    val operand = data(dp)

実行して、

    // exec
    switch (op) {
      is(UInt(Inc)) {
        res := operand + UInt(1)
      }
      is(UInt(Dec)) {
        res := operand - UInt(1)
      }
      is(UInt(Get)) {
        res := Mux(io.rx.valid, io.rx.bits, operand)
      }
    }

メモリに書き込むと。

    // write
    switch (op) {
      is(UInt(Inc), UInt(Dec), UInt(Get)) {
        data(dp) := res
      }
    }

BFの場合この他にも命令に種類があって、ジャンプ命令のようにip(命令ポインタ)に作用する命令とか、

    // update ip
    switch (op) {
      is(UInt(Jz)) {
        when (operand === UInt(0)) {
          ip := ip + UInt(1) + addr
        } .otherwise {
          ip := ip + UInt(2) // skip addr operand
        }
      }
      is(UInt(Jmp)) {
        ip := ip + UInt(1) - addr
      }
      ...
    }

データポインタに作用する命令とか

    // update dp
    switch (op) {
      is(UInt(PInc)) {
        dp := dp + UInt(1)
      }
      is(UInt(PDec)) {
        dp := dp - UInt(1)
      }
    }

あとは外部IO命令があります。

    // IO
    switch (op) {
      is(UInt(Put)) {
        io.tx.valid := Bool(true)
        io.tx.bits := operand
      }
      is(UInt(Get)) {
        io.rx.ready := Bool(true)
      }
    }

ただしCPUの初期化処理(このCPUは中にコード用・データ用メモリを持っているのでその初期値の設定)のために以上の処理が全部unlessの中に入っています。

  when (io.init) {
    when (io.code.valid) { code(io.code.addr) := io.code.bits }
    when (io.data.valid) { data(io.data.addr) := io.data.bits }
  }
  when (io.boot) {
    dp := UInt(0)
    ip := UInt(0)
  }

  unless (io.init || io.boot) {
    // 上でみた処理はこの中に入ってる
  }

io.initが立っているときはCPUは停止して外部からのメモリ書き込み要求を優先させるという感じですね。あとはio.bootでipとdpを初期化して起動みたいな感じです。

以上が全体図です。めちゃくちゃ構造化されてて読みやす過ぎますね。構造化されすぎててどういう回路に落ちるのかぱっと見わかりにくいです。なのでこれをRTLっぽく書きなおしてみます。

まず実行の部分ですがこれはそれなりに分かりやすいです。ただまあ回路書いてるという気持ちはしないですね。なので書き換えます。

    // exec
    switch (op) {
      is(UInt(Inc)) {
        res := operand + UInt(1)
      }
      is(UInt(Dec)) {
        res := operand - UInt(1)
      }
      is(UInt(Get)) {
        res := Mux(io.rx.valid, io.rx.bits, operand)
      }
    }

以下のように書き換えてみました。

  // exec
  val inc_res = operand + UInt(1)
  val dec_res = operand - UInt(1)
  val get_res = io.rx.bits
  val res = MuxLookup(op, UInt(0), Seq(
    Inc -> inc_res,
    Dec -> dec_res,
    Get -> get_res))

断然回路書いてる感じがしますね!普通のVerilogとかVHDLに当てはまる話ですがビヘイビアルに書きすぎるとどういう回路が何個出来上がるのかがわかりにくいですね。HW資源は無限ではないので節約していきたいところです。書き換えた後のコードでは+1回路と-1回路、あとは比較器が3個とマルチプレクサが使われているのがはっきりわかります(実際に合成したあとどうなるかは知りませんが)。

書き出しの部分も書き換えるとこんな感じ。

    // write
    switch (op) {
      is(UInt(Inc), UInt(Dec), UInt(Get)) {
        data(dp) := res
      }
    }
    val we = op === UInt(Inc) || op === UInt(Dec) || op === UInt(Get)
    when (we) { data(dp) := res }

write enableを計算するのに必要な回路がわかりやすくなりました(まあ普通に元のコードだけみても考えればすぐわかりますが)。 次にipの更新処理を書きなおしてみます。

    // update ip
    switch (op) {
      is(UInt(Jz)) {
        when (operand === UInt(0)) {
          ip := ip + UInt(1) + addr
        } .otherwise {
          ip := ip + UInt(2) // skip addr operand
        }
      }
      is(UInt(Jmp)) {
        ip := ip + UInt(1) - addr
      }
      is(UInt(Put)) {
        when (io.tx.ready) {
          ip := ip + UInt(1)
        }
      }
      is(UInt(Get)) {
        when (io.rx.valid) {
          ip := ip + UInt(1)
        }
      }
      is(UInt(PInc), UInt(PDec), UInt(Inc), UInt(Dec)) {
        ip := ip + UInt(1)
      }
    }
  val ip2 = ip + UInt(2)
  val ipf = ip1 + addr
  val ipb = ip1 - addr
  val jz_test = operand === UInt(0)
  val jz_addr = Mux(operand === UInt(0), ipf, ip2)
  val next_ip = MuxLookup(op, ip1, Seq(
    Jz  -> jz_addr,
    Jmp -> ipb,
    Put -> Mux(io.tx.ready, ip1, ip),
    Get -> Mux(io.rx.valid, ip1, ip)))

かなり行数が短くなりました(単に一行一行に情報を詰め込んだだけです)。動作は元のコードのほうが分かりやすいですが部分式を全部書きだしてみると回路の無駄がよくわかります。見たところ無駄に構成要素が多いですね。どうもISAがひどいようです。このISAを設計した人は一体何を考えているんでしょうか。たぶん何も考えてませんね。

こんな感じでコードを書き換えていくんですが、あくまでunlessブロックの中でごにょごにょ書き換えているだけです。unlessが効果を発揮するのはその中にあるレジスタに対してだけなので、ブロック内のコンビネーショナルな回路を全部外に出してみます。

  val ip1 = ip + UInt(1)

  val inst = code(ip)
  val addr = code(ip1)

  val op = inst(2, 0)

  // read
  val operand = data(dp)

  // exec
  val inc_res = operand + UInt(1)
  val dec_res = operand - UInt(1)
  val get_res = io.rx.bits
  val res = MuxLookup(op, UInt(0), Seq(
    Inc -> inc_res,
    Dec -> dec_res,
    Get -> get_res))

  // write
  val we = op === UInt(Inc) || op === UInt(Dec) || op === UInt(Get)

  // update ip
  val ip2 = ip + UInt(2)
  val ipf = ip1 + addr
  val ipb = ip1 - addr
  val jz_test = operand === UInt(0)
  val jz_addr = Mux(operand === UInt(0), ipf, ip2)
  val next_ip = MuxLookup(op, ip1, Seq(
    Jz  -> jz_addr,
    Jmp -> ipb,
    Put -> Mux(io.tx.ready, ip1, ip),
    Get -> Mux(io.rx.valid, ip1, ip)))

  // update dp
  val dp_inc = dp + UInt(1)
  val dp_dec = dp - UInt(1)
  val next_dp = MuxLookup(op, dp, Seq(
    PInc -> dp_inc,
    PDec -> dp_dec))

  // IO
  val tx_valid = op === UInt(Put)
  val rx_ready = op === UInt(Get)
  io.tx.bits := operand

  when (io.init) {
    when (io.code.valid) { code(io.code.addr) := io.code.bits }
    when (io.data.valid) { data(io.data.addr) := io.data.bits }
  }
  when (io.boot) {
    dp := UInt(0)
    ip := UInt(0)
  }

  unless (io.init || io.boot) {
    when (we) { data(dp) := res }
    ip := next_ip
    dp := next_dp
    io.tx.valid := tx_valid
    io.rx.ready := rx_ready
  }

unlessがちっさくなりすぎて最後の7行だけになってしまいました。ここまでくるとどういう回路に落ちるのか分かりやすいですね。最後の方のwhenやunlessも潰してみます。

  ip := Mux(io.boot, UInt(0), next_ip)
  dp := Mux(io.boot, UInt(0), next_dp)

  val iwe = io.init && io.code.valid
  when (iwe) { code(io.code.addr) := io.code.bits }

  val dwe = io.init && io.data.valid
  when (dwe) { data(io.data.addr) := io.data.bits }

  val run = !(io.init || io.boot)
  io.tx.valid := run && tx_valid
  io.rx.ready := run && rx_ready

  val real_we = run && we
  when (real_we) { data(dp) := res }

まあこんなもんですかね。さすがにこれぐらいまで落とすと超わかりやすいですがデータメモリの書き込みポートが2本なのが完全に無駄なのがわかります。いや、最初から無駄なのはわかっていたけれどこんなに分かりやすく無駄だと流石に書き換えたくなりますね。というわけで書き換えます。

  val dwe = io.init && io.data.valid
  val real_we = run && we

  val data_we = dwe || real_we
  val data_addr = Mux(io.init, io.data.addr, dp)
  val data_bits = Mux(io.init, io.data.bits, res)

  when (data_we) { data(data_addr) := data_bits }

書き込みポートが1本になりました。やったぜ。

はい。そういうわけでChiselのコードをChiselのコードに書き換える何かが無事完了しました。要するに何がいいたいかっていうとあんまりビヘイビアルに書きすぎるのは良くないよっていうことです。当然ですね。あとはなんだろう、Chisel結構たのしいのでみんな使ってみようってことです。仮にFPGAを持ってなくてもシミュレータ上で動かすだけでも結構たのしいです。ぜひ試してみてください。