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

C言語をコンパイルするSELECT文(SQLite3用)を作った

SQL ELVM

@shinhさん作のコンパイラインフラストラクチャELVMに SQLite3シェル用のSQLを吐き出すバックエンドを足して@rui314さん作のCコンパイラ8ccSQLコンパイルし、29万行のSELECT文から成るCコンパイラが出来上がりました。

https://github.com/youz/8cc-sqlite3

こちらからCコンパイラ&ELVM IRアセンブラが ビューの形で入っているSQLite3のデータベースファイルを入手できます。

使い方

JSON1拡張が有効になっているバージョンのSQLite3シェルを使用します。 SQLite公式サイトで配布しているバイナリやDebianパッケージのsqlite3 ver.3.11 とかでOK。

$ sqlite3 elvm.db3

1. Cソース読み込み

elvm.db3を読み込んだら、テーブルsrc(b BLOB)コンパイルしたいCプログラムを入れます。

(注意) #includeを含むCソースはコンパイルできません

DELETE FROM src;
INSERT INTO src(b) VALUES('
int putchar(int c);
int main() {
  const char* p = "Hello, world!\n";
  for (; *p; p++)
    putchar(*p);
  return 0;
}');

あるいはreadfile関数を使ってファイルから読み込むと簡単です。

INSERT INTO src(b) VALUES(readfile('sample/hello.c'));

2. C → ELVM IR コンパイル

8ccをSQL化したビューelvm_8ccからstdout列をSELECTし、テーブルeir(b BLOB)に入れます。

DELETE FROM eir;
INSERT INTO eir(b) SELECT stdout FROM elvm_8cc;

(注意) 先のHelloWorldのコンパイルにはCore i5 2.5GHzのマシンで30分ほどかかります

3. ELVM IRのアセンブル

最後にELVM IRをELVMが対応している各種バックエンド言語にアセンブルするわけですが、 出力先言語は設定テーブル option(target TEXT) のtarget列に書き込んで指定します。 (optionテーブルには1行だけレコードが入っています)

UPDATE option SET target = 'rb';

出力先言語とそれに対応する文字列はREADMEに書いてあります。 もしくはDB内のsupported_targetsテーブルを見てください。

アセンブル処理はビュー elvm_elc からSELECT。

SELECT writefile('hello.rb', stdout) FROM elvm_elc;

(注意) HelloWorldのELVM IR→Rubyへのアセンブルには大体20分ほどかかります

Rubyアセンブルした結果はこんな感じ

$ cat hello.rb
@a = 0
@b = 0
@c = 0
@d = 0
@bp = 0
@sp = 0
@pc = 0
@mem = [0] * (1 << 24)
@mem[0] = 72
@mem[1] = 101
@mem[2] = 108
@mem[3] = 108
@mem[4] = 111
@mem[5] = 44
@mem[6] = 32
@mem[7] = 119
@mem[8] = 111
@mem[9] = 114
@mem[10] = 108
@mem[11] = 100
@mem[12] = 33
@mem[13] = 10
@mem[15] = 16


def func0
 while 0 <= @pc && @pc < 512
  case @pc

  when 0
   true && @pc = 1 - 1

  when 1
   @d = @sp
   @d = (@d + 16777215) & 16777215
   @mem[@d] = @bp
   @sp = @d
   @bp = @sp
   @sp = (@sp - 1) & 16777215
   @a = 0
   @b = @sp
   @a = 0
   @b = @bp
   @b = (@b + 16777215) & 16777215
   @mem[@b] = @a

  when 2
   @b = @bp
   @b = (@b + 16777215) & 16777215
   @a = @mem[@b]
   @b = @a
   @a = @mem[@b]
   @a == 0 && @pc = 4 - 1

  when 3
   true && @pc = 5 - 1

  when 4
   true && @pc = 7 - 1

  when 5
   @b = @bp
   @b = (@b + 16777215) & 16777215
   @a = @mem[@b]
   @b = @a
   @a = @mem[@b]
   @d = @sp
   @d = (@d + 16777215) & 16777215
   @mem[@d] = @a
   @sp = @d
   putc @a
   @sp = (@sp + 1) & 16777215

  when 6
   @b = @bp
   @b = (@b + 16777215) & 16777215
   @a = @mem[@b]
   @d = @sp
   @d = (@d + 16777215) & 16777215
   @mem[@d] = @a
   @sp = @d
   @a = (@a + 1) & 16777215
   @b = @bp
   @b = (@b + 16777215) & 16777215
   @mem[@b] = @a
   @a = @mem[@sp]
   @sp = (@sp + 1) & 16777215
   true && @pc = 2 - 1

  when 7
   @a = 0
   @b = @a
   exit
   exit
  end
  @pc += 1
 end
end

while true
 case @pc / 512
 when 0
  func0
 end
end

$ ruby hello.rb
Hello, world!

コンパイル&アセンブルを1度に済ませたい時はelvm_8cc_elcからSELECTしてください。最初から書くと

DELETE FROM src;
INSERT INTO src(b) VALUES(readfile('source.c'));
UPDATE option SET target = 'js';
SELECT writefile('output.js', stdout) FROM elvm_8cc_elc;

samplesフォルダにELVM本家のテストから3つほど#includeのない(あるいは処理済みの)物を 選んで入れてありますので、暇だったら遊んでみてください。

(注意) sample/fizzbuzz.cのコンパイルはめっちゃ時間かかります(計測放棄)

バックエンドの解説

SQL文中でループ等の制御構文を使えるDBMSならRubyやJS等とほぼ変わらない仕組みで バックエンドが書けそうですが、制御構文もストアドプロシージャもないSQLite3で どうやってやるかっていうと、ver 3.8.3でサポートされたRecursive Common Table Expression(以下再帰CTE)で実現できます。

再帰CTE

再帰CTEっていうのは、知らない人向けに説明すると関数型言語に良くある unfold関数と同じような再帰的展開処理をSELECT文で実現できる仕組みです。

Scheme(SRFI-1)のunfoldの定義は以下の通り

(unfold p f g seed [tail-gen]) =
  (if (p seed)
      (tail-gen seed)
      (cons (f seed)
            (unfold p f g (g seed))))
;; Gaucheでの使用例
(use srfi-1)
(unfold (lambda (e) (> e 10))    ; 終了判定をする関数 p
        (lambda (e) (* e e))     ; seedをリストの要素に変換する関数 f
        (lambda (e) (+ e 1))     ; seedから次のseedを生成する関数 g
        0)                       ; seed
        ; tail-genは省略可。デフォルトは (lambda (x) '())
;-> (0 1 4 9 16 25 36 49 64 81 100)
-- 再帰CTEの例
WITH RECURSIVE
  rec(e) AS (
    SELECT 0                      -- seed
    UNION SELECT e + 1 FROM rec   -- g
    WHERE e < 10                  -- p
  )
SELECT e * e FROM rec;            -- f

0
1
4
9
16
25
36
49
64
81
100

見比べるとコードのコメントにp, f, g, seedと書いてある行がそれぞれ 対応している事が分かるかと思います。

ちなみに再帰CTEでのseedは単一レコードではなくても良いので、再帰する毎に レコード数が変化するような処理も書けます。 (UNION SELECTが返すレコードセットが0件になった時点で再帰が止まる、 という仕組みになっています。)

-- 7回再帰して255レコードを生成する例
WITH
  d(i) AS (SELECT 0 UNION SELECT 1),
  r(i, v) AS (
    SELECT 1, 1
    UNION SELECT r.i + 1, r.v*2 + d.i
    FROM r CROSS JOIN d
    WHERE r.i < 8
  )
SELECT i, v FROM r;

1|1
2|2
2|3
3|4
3|5
3|6
3|7
4|8
4|9
4|10
...
8|253
8|254
8|255

その他のサンプル

ELVMの実装

さてこの再帰CTEでELVMバックエンドをどうやって作るかというと、

  • VMの状態(レジスタ、プログラムカウンタ(pc)、メモリ、IO等)を1レコードで表現する
  • インストラクション列を状態遷移としてUNION SELECTの部分で表現する

これが出来ればOK。

レジスタ、pc、フラグ等はINT、stdin/stdoutはTEXTとして単純に持てば良いのですが メモリがちょっと面倒。テーブルで表現できれば楽なんですがSELECT文中からテーブルを 更新するような事は出来ないので値として持つ必要があります。

BLOBでメモリを表してみたら書き換え時にメモリ食いまくって一瞬でメモリ不足エラーになってダメだったので、 遅そうだけれども省メモリで着実に動作してくれるJSON1拡張のjson_object形式でメモリを持つことにしました。

状態遷移ですが、1つのpcが指すコードブロック中の命令列に連番(コード中ではstepと表現)を振って、 pcとstepの組で状態を表す事にします。

で、あとはCASE式を機械的に組んでいけばOKなんですが、CASE式が表現できるのは あくまで1つの値なので、VMを表すレコードの各列ごとに状態遷移を書く必要があり、 単純な処理でもコンパイル結果は大分悲惨な事になります。

例えばELVMのテストにある02mov.eirは

mov A, 43    # pc=1 step=0
putc A       # pc=1 step=1
exit         # pc=1 step=2
  • (pc, step) = (0, 1)だったらレジスタAに43をセット
  • (pc, step) = (0, 2)だったらstdoutにstdout+char(A)をセット
  • (pc, step) = (0, 3)だったらrunningに0をセット

という状態遷移になるのですが、SQLアセンブルした結果がこちら↓

DROP TABLE IF EXISTS stdin;
CREATE TABLE stdin(i BLOB);
INSERT INTO stdin(i) VALUES(readfile('input.txt'));
DROP TABLE IF EXISTS data;
CREATE TABLE data(i INT PRIMARY KEY, v INT);
INSERT INTO data VALUES
  (0,1)
;
-- .stats on
WITH
 elvm AS (
  SELECT
   0 a,
   0 b,
   0 c,
   0 d,
   0 bp,
   0 sp,
   0 pc,
   0 step,
   1 running,
   (SELECT json_group_object(i, v) FROM data) mem,
   (SELECT i FROM stdin) stdin,
   '' stdout,
   0 cycle
  UNION ALL SELECT
   CASE pc / 512
   WHEN 0 THEN
    CASE pc
    WHEN 1 THEN
     CASE step
     WHEN 0 THEN 43
     ELSE a END
    ELSE a END
   ELSE a END
   ,
   b
   ,
   c
   ,
   d
   ,
   bp
   ,
   sp
   ,
   CASE pc / 512
   WHEN 0 THEN
    CASE pc
    WHEN 0 THEN
     CASE step
     WHEN 0 THEN 1
     WHEN 1 THEN pc+1
     ELSE pc END
    WHEN 1 THEN
     CASE step
     WHEN 2 THEN pc+1
     ELSE pc END
    END
   END
   ,
   CASE pc / 512
   WHEN 0 THEN
    CASE pc
    WHEN 0 THEN
     CASE step
     WHEN 0 THEN 0
     WHEN 1 THEN 0
     ELSE step + 1 END
    WHEN 1 THEN
     CASE step
     WHEN 2 THEN 0
     ELSE step+1 END
    END
   END
   ,
   CASE pc / 512
   WHEN 0 THEN
    CASE pc
    WHEN 1 THEN
     CASE step
     WHEN 2 THEN 0
     ELSE running END
    ELSE running END
   ELSE running END
   ,
   mem
   ,
   stdin
   ,
   CASE pc / 512
   WHEN 0 THEN
    CASE pc
    WHEN 1 THEN
     CASE step
     WHEN 1 THEN stdout||char(a)
     ELSE stdout END
    ELSE stdout END
   ELSE stdout END
   ,
   cycle + 1
  FROM elvm WHERE running = 1
 )
SELECT writefile('output.txt', stdout) FROM elvm WHERE running = 0;

恐ろしく見通しが悪いですね!

コンパイラSQLともなると、JMPするわけでもない連続した処理なのに次は10万行後、 その次はそこから15万行前とか、そういう酷いコードになります。 printfデバッグがしやすいのがせめてもの救い。(最後のSELECT文をいじって stdout以外の列も持ってきたり途中経過を持ってきたりするようにするだけ)

つい先日SQLite3に導入されたRow Valuesが使えたら 大分マシになるのかなと思いますが、残念ながら現時点ではCASE式の値としては使えません。

というわけでちょっとしたコードでも悪夢のようなSQLになってしまいますが、 無事ELVMの全テストをパスするバックエンドが出来上がりました。

おまけ:処理速度について

メモリの書き換えが

  1. JSON形式の文字列データをパースする
  2. 指定されたキーの値を書き換える
  3. データをJSON形式で文字列化する

という処理になっている(JSON1拡張はDBにJSON型を導入するのではなく、 文字列型データをJSONとしてパースした上で色々する機能を導入する拡張)ので、 メモリアクセスがボトルネックになってるだろうなと。 (そもそもテーブルでなく値で持ってるので、書き換えの度にコピーする前提)

という訳で実験として、単純で邪悪なSQLite3拡張を作ってみました。

garray.c

gainitでメモリ上に1つ配列を作り、garefで参照、gasetで書き換えます。 評価順が一意に決まるような所でしか使えない、DBMSには入れるべきでないアレな代物です。

JSONの代わりにこの配列拡張を使ってみた結果、30分かかっていたHelloWorldの コンパイル時間が2分ちょうど位になりました。

ドメイン特化言語で2分なら割と良い性能なのではないでしょうか(要出典)