はじめに

LLVMを使って、コンパイラ（のフロントエンド）を作ってみようと思い立つ
とりあえず対象は Brainf*ck のコンパイラ（字句解析とか不要で簡単そうだし）
それならシェルスクリプトでも作れそう？
- せっかくだし POSIX シェル縛りで

【参考情報】

LLVM
- コンパイラ基盤、みたいなもの
- wikipedia - LLVM
- 今回は LLVM API は使わずに、LLVM IRを直接出力するだけ
- LLVM Language Reference Manual
Brainf*ck
- 8種類の文字だけでコーディングできる言語
- wikipedia Brainfuck
- Qiita内でもコンパイラやインタプリタがいくつも作られている（はず）
POSIX
- UNIX系OSが最低限備えるべき、共通的な仕様みたいな感じ？
- The Open Group
- つまり bash の独自機能などは使わないでがんばる
- 別に「どんな環境でも動くように」というわけではないのでPOSIXの比較的新しい機能も使ってよいとする

LLVM の IR を見てみる

まずは LLVM の IR(中間表現)を調べました。IRで出力すれば、とりあえず LLVM の機能で実行可能オブジェクトやライブラリにコンパイルすることが可能なはず。
LLVM の API を使えば、直接 IR を扱うより便利に使えるみたいだけど、今回は直接 IR を記述します。

まずは、適当なC言語のソースを用意しました。

hello.c

#include <stdio.h>

int main()
{
    printf("hello, world.\n");
    return 0;
}

LLVM IR に変換してみます。

$ clang -S -emit-llvm hello.c

こんな結果になりました。

hello.ll

; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@.str = private unnamed_addr constant [15 x i8] c"hello, world.\0A\00", align 1

; Function Attrs: noinline nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...) #1

attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 5.0.0 (trunk 294803)"}

順番に見ていきます。

; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

1行目はコメントでしょう。モジュール( Module Structure )とは LLVM の翻訳単位のことのようです。

2行目はソースファイル名の情報( Source Filename)。モジュールの識別子として使われるらしい。

3行目はデータ形式( Data Layout )で、各種データの格納状況をハイフン区切りで指定するみたい。

e : リトルエンディアン
m:e : ELFマングル形式
i64:64 : 整数型 i64 は 64bitアライメント
f80:128 : 浮動小数点型 f80 は 128bitアライメント
n8:16:32:64 : 対象CPUの自然な整数幅の指定. 8bit, 16bit, 32bit, 64bit.
S128 : スタックの自然なアライメントは128bit

4行目はターゲット環境( Target Triple )。
形式的にはハイフン区切りで ARCHITECTURE-VENDOR-OPERATING_SYSTEM あるいは ARCHITECTURE-VENDOR-OPERATING_SYSTEM-ENVIRONMENT を指定するようです。

x86_64 : アーキテクチャ
unknown : ベンダー
linux : OS
gnu : 環境？OSの一部？

@.str = private unnamed_addr constant [15 x i8] c"hello, world.\0A\00", align 1

次は文字列定数のグローバル変数( Global Variables )を定義しているのでしょう。
private は linkage-type で、別のモジュールからは見えない指定。
unnamed_addr は、重要なのは値で、アドレスは重要じゃないよ（なので、同じ定数が他にあったら、そっちとマージしてもいいよ）というマーク。
constant は定数を意味する（ほかに global がある）。
[15 x i8] はサイズと型でしょう。
定数値は自明かな。
align 1 はエリアのアライメントの指定。

; Function Attrs: noinline nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

次は、関数の定義( Functions )。
define が関数定義の開始。次の i32 は戻り値。
@main が関数名。#0 は関数定義より後ろで定義している属性グループ名らしい。コメントに書いてある noinline とか nounwind とかの属性をまとめて指定しているのだと思います。

%1 などの % から始まるのが変数。LLVMでは、静的単一代入(SSA)といって、一度入れたら変更できないらしい。
ここでは変数名が数字だけど、英字なども使えるみたい。

alloca はスタックに領域を確保する命令( ‘alloca’ instruction)。
store は指定のアドレスに値を設定する命令( ‘store’ instruction)。
call は関数呼び出し命令( ‘call’ instruction )。
ret は戻り値の設定( ‘ret’ instruction )。
なんとなくわかるかと。

declare i32 @printf(i8*, ...) #1

使用している関数の宣言（仮定義）ですね。
declare の説明は Functions にちょこっと書いてありました。
#1 も @main の #0 と同様に属性の指定だと思います。

attributes #0 = { noinline nounwind uwtable 省略 }
attributes #1 = { 省略 }

関数定義や関数宣言のところで出ていた属性のグループ定義だろうと思います( Attribute Groups)。

!llvm.ident = !{!0}

!0 = !{!"clang version 5.0.0 (trunk 294803)"}

最後はコンパイラ情報をmetadataとして持っている感じ？

$ clang hello.c -o hello
$ objdump -s hello
（省略）
Contents of section .comment:
（省略）
 0030 36303900 636c616e 67207665 7273696f  609.clang versio
 0040 6e20352e 302e3020 28747275 6e6b2032  n 5.0.0 (trunk 2
 0050 39343830 332900                      94803).

Brainf*ck コンパイラを作るための情報を集める

次はBrainf*ck 用の動作を実現するためのIRの書き方を確認するソースを用意します。

チューリングマシン的には無限個の要素(セル)を使えないといけないですが、
Brainf*ckの場合、wikipedia の Brainfuck によると、要素の数は最低でも 30000 とあるので、最低限のサイズだけを確保。値は0クリアされるように calloc(3) を利用。ちなみに1セルは8bit。

あとのロジックは、wikipedia などでも書かれている、Brainf*ck の各命令の動作処理そのままです。各命令を１回づつ書いただけで、ロジックに意味はありません。

bf_test.c

#include <stdio.h>
#include <stdlib.h>

int main()
{
  void *buff = calloc(30000, sizeof(char));
  char *ptr = (char*) buff;

  (*ptr)++;
  ptr++;
  (*ptr)--;
  ptr--;
  while (*ptr) {
    *ptr = getchar();
    putchar(*ptr);
  }

  free(buff);
  return 0;
}

LLVM IRを出力しました。

$ clang -S -emit-llvm bf_test.c

bf_test.ll

; ModuleID = 'bf_test.c'
source_filename = "bf_test.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: noinline nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i8*, align 8
  %3 = alloca i8*, align 8
  store i32 0, i32* %1, align 4
  %4 = call noalias i8* @calloc(i64 30000, i64 1) #3
  store i8* %4, i8** %2, align 8
  %5 = load i8*, i8** %2, align 8
  store i8* %5, i8** %3, align 8
  %6 = load i8*, i8** %3, align 8
  %7 = load i8, i8* %6, align 1
  %8 = add i8 %7, 1
  store i8 %8, i8* %6, align 1
  %9 = load i8*, i8** %3, align 8
  %10 = getelementptr inbounds i8, i8* %9, i32 1
  store i8* %10, i8** %3, align 8
  %11 = load i8*, i8** %3, align 8
  %12 = load i8, i8* %11, align 1
  %13 = add i8 %12, -1
  store i8 %13, i8* %11, align 1
  %14 = load i8*, i8** %3, align 8
  %15 = getelementptr inbounds i8, i8* %14, i32 -1
  store i8* %15, i8** %3, align 8
  br label %16

; <label>:16:                                     ; preds = %20, %0
  %17 = load i8*, i8** %3, align 8
  %18 = load i8, i8* %17, align 1
  %19 = icmp ne i8 %18, 0
  br i1 %19, label %20, label %28

; <label>:20:                                     ; preds = %16
  %21 = call i32 @getchar()
  %22 = trunc i32 %21 to i8
  %23 = load i8*, i8** %3, align 8
  store i8 %22, i8* %23, align 1
  %24 = load i8*, i8** %3, align 8
  %25 = load i8, i8* %24, align 1
  %26 = sext i8 %25 to i32
  %27 = call i32 @putchar(i32 %26)
  br label %16

; <label>:28:                                     ; preds = %16
  %29 = load i8*, i8** %2, align 8
  call void @free(i8* %29) #3
  ret i32 0
}

; Function Attrs: nounwind
declare noalias i8* @calloc(i64, i64) #1

declare i32 @getchar() #2

declare i32 @putchar(i32) #2

; Function Attrs: nounwind
declare void @free(i8*) #1

attributes #0 = { noinline nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #3 = { nounwind }

!llvm.ident = !{!0}

!0 = !{!"clang version 5.0.0 (trunk 294803)"}

各処理の部分を切り出して、コンパイラ（のフロントエンド）が何を出力すべきかを考えます。

全体の初期処理/終了処理

初期処理

  void *buff = calloc(30000, sizeof(char));
  char *ptr = (char*) buff;

  %1 = alloca i32, align 4
  %2 = alloca i8*, align 8
  %3 = alloca i8*, align 8
  store i32 0, i32* %1, align 4
  %4 = call noalias i8* @calloc(i64 30000, i64 1) #3
  store i8* %4, i8** %2, align 8
  %5 = load i8*, i8** %2, align 8
  store i8* %5, i8** %3, align 8

変数 %1 は 0 を設定しているだけで、このあと使っていないので無視してよさそう。
LLVM の最適化が有効になれば消えてなくなると思う。

変数 %2 が buff のアドレス、変数 %3 が ptr のアドレスを指すみたい。

謎言語による疑似コードで表すなら以下のようなイメージ？

// allocate variables
const r2_buff = (char**) alloca(sizeof(char*));
const r3_ptr = (char**) alloca(sizeof(char*));

// buff = calloc(30000, sizeof(char));
const r4_tmp = (char*) calloc(30000, sizeof(char));
*r2_buff = r4_tmp;

// ptr = buff;
const r5_tmp = (*r2_buff);
*r3_ptr = r5_tmp;

静的単一代入の関係で変数の更新ができないので、 ptr の値はメモリ上に登録して、そのアドレスを %3 で保持している感じ。

同様に buff の値もメモリ上に持っているけど、こっちは変更しないで終了処理で使うだけなので、コンパイラの出力としては変数 %4 に相当するものだけあったらよいのかも。
（もちろん LLVM の最適化を通したら同じだと思うけど、コンパイラの出力を少なくするために）

終了処理

  free(buff);
  return 0;

  %29 = load i8*, i8** %2, align 8
  call void @free(i8* %29) #3
  ret i32 0

buff のアドレス( %2 )から値を取り出して free を呼んでいるだけ。

前述のように buff の値( %4 )をそのまま使えばよいのではないかと。

Brainf*ckの `+` 命令 / `-` 命令

`+` 命令

  (*ptr)++;

  %6 = load i8*, i8** %3, align 8
  %7 = load i8, i8* %6, align 1
  %8 = add i8 %7, 1
  store i8 %8, i8* %6, align 1

ptr の値( %3 の指すアドレスの中身 )を %6 に入れる
ptr の指す先( %6 の指すアドレスの中身)を %7 に入れる
その値に位置を加えた値を %8 に入れる
結果を ptr の指す先( %6 の指すアドレスの中身)に入れる

`-` 命令

  (*ptr)--;

  %11 = load i8*, i8** %3, align 8
  %12 = load i8, i8* %11, align 1
  %13 = add i8 %12, -1
  store i8 %13, i8* %11, align 1
  %14 = load i8*, i8** %3, align 8

add している値が -1 である以外は、 + 命令と同じですね。

Brainf*ckの `>` 命令 / `<` 命令

`>` 命令

  ptr++;

  %9 = load i8*, i8** %3, align 8
  %10 = getelementptr inbounds i8, i8* %9, i32 1
  store i8* %10, i8** %3, align 8

ptr の値( %3 の指すアドレスの中身 )を %9 に入れる
ptr の値を1加えて、%10 に入れる
結果を ptr の値( %3 の指すアドレスの中身)に入れる

getelementptr はおそらく get element pointer の略で、構造体の先頭アドレスから要素のアドレスを求める場合などに使う命令( ‘getelementptr’ Instruction )のようです。
ここではアドレスに1を加えるのに使っているみたい。

`<` 命令

  ptr--;

  %14 = load i8*, i8** %3, align 8
  %15 = getelementptr inbounds i8, i8* %14, i32 -1
  store i8* %15, i8** %3, align 8

< 命令も -1 している以外は > 命令と同じですね。

Brainf*ckの `,` 命令 / `.` 命令

`,` 命令

    *ptr = getchar();

  %21 = call i32 @getchar()
  %22 = trunc i32 %21 to i8
  %23 = load i8*, i8** %3, align 8
  store i8 %22, i8* %23, align 1

getchar 関数を呼び出し、結果を %21 に設定
trunc 命令は、数値項目のサイズの切り捨て( ‘trunc .. to’ Instruction )。
32bit整数( i32 ) から8bit整数( i8 )にダウンキャストしている感じ。
ptr の値を取得して
trunc した結果を ptr の指す先に代入

`.` 命令

    putchar(*ptr);

  %24 = load i8*, i8** %3, align 8
  %25 = load i8, i8* %24, align 1
  %26 = sext i8 %25 to i32
  %27 = call i32 @putchar(i32 %26)

ptr の値を取得して
ptr の指す先の値を取得
sext 命令は、符号拡張( ‘sext .. to’ Instruction )。
その結果を putchar で出力

, 命令と、ほぼ逆の動作ですね。

Brainf*ckの `[` 命令 / `]` 命令

`[` 命令

  while (*ptr) {

  br label %16

; <label>:16:                                     ; preds = %20, %0
  %17 = load i8*, i8** %3, align 8
  %18 = load i8, i8* %17, align 1
  %19 = icmp ne i8 %18, 0
  br i1 %19, label %20, label %28

; <label>:20:                                     ; preds = %16

; <label>:16: などはコメントですが、ラベルを表します。
厳密にはラベルは省略されていて、自動で数字のラベルが採番されているのだと思います。
そして、その自動採番されたラベルをコメントで表しているのでしょう。

公式ドキュメントを見ると明示的に書く場合には ラベル名: という形になるようです。
分岐先のラベルを指定するときには label %ラベル名 と書くみたい。

C言語やその他の言語では、ラベルはどちらかというとおまけみたいな感じですが、
LLVM IR では、ラベルは結構重要なポジションにあるみたい。

LLVM IR の基本構造は大きいものから順番に、以下のようになっているようです。

モジュール。コンパイルの単位で、複数の関数、大域変数、シンボルエントリなどが含まれる。
関数。複数の基本ブロックからなる。
基本ブロック。１つのラベルと複数の命令からなる。入口は１つ。出口も１つ。
命令。

基本ブロックは、ラベルから始まり各種命令が続いて、最後は終端命令( Terminator Instructions )で終わるようです。
基本ブロックの途中から処理を開始することはできず、基本ブロックの途中から分岐することもできないようです。

逆にいえば分岐する命令（終端命令）の次に命令があれば、その間には省略されたラベルが存在するはずで、ラベルは自動で採番されるらしい。

ちなみに値を返す命令を明示的に変数に入れないと、その変数名も自動で採番されるようです。
そして、その場合の数字は、ラベルと変数で共用されるみたい。

見方を変えると、ラベルは基本ブロックの先頭アドレスを示す値（変数）なのかも。
そうすると、普通の変数だと i32 とか i8* みたいな型を書く代わりに、ラベルでは label という「型」を書いているわけですね。

上記 [ 命令の展開結果は

br 命令で次の基本ブロック( 16: )にジャンプ ( ‘br’ Instruction )
新しい基本ブロック( 16: )の開始。ループの条件判定部分に相当
ptr の値を取得して %17 に設定
ptr の指す先の値を取得して %18 に設定
その値を icmp 命令で 0 と比較して結果を %19 に設定( ‘icmp’ Instruction )
比較結果をもとに、後続の基本ブロック( 20: )かループの終了部( 28: )に分岐（ジャンプ）する
次の基本ブロックのラベル

`]` 命令

  br label %16

; <label>:28:                                     ; preds = %16

無条件でラベル 16: にジャンプしています。
ループの終了（ループの次の基本ブロック）のラベル

Brainf*ck コンパイラの作成

これで、LLVM IR の必要な情報は出そろったので、コンパイラ（のフロントエンド）が作れるはず。
今回はシェルスクリプトで実装してみたいと思います。
できるだけ POSIX で定義されている範囲内でおさめたいと思っています。

1文字づつ処理する方法

bash などでは以下のようにすることで、ファイルから1文字づつ読み取り処理することができます。

#!/bin/bash

while IFS= read -rN1 char
do
  case "$char" in
  ">") echo "ptr++;" ;;
  "<") echo "ptr--;" ;;
  "+") echo "(*ptr)++;" ;;
  "-") echo "(*ptr)--;" ;;
  ".") echo "putchar(*ptr);" ;;
  ",") echo "*ptr = getchar();" ;;
  "[") echo "while (*ptr) {" ;;
  "]") echo "}" ;;
  esac
done < "$1"

今回は POSIX 縛りで、read に -N1 などのオプションがないので、もうちょっと考えました。
とりあえず以下のようにしてみました。
もっと良い方法がありそうですが。

#!/bin/sh

while IFS= read -r string ; do
  while [ -n "$string" ] ; do
    case "$string" in
    ">"*) echo " ptr++;" ;;
    "<"*) echo " ptr--;" ;;
    "+"*) echo " (*ptr)++;" ;;
    "-"*) echo " (*ptr)--;" ;;
    "."*) echo " putchar(*ptr);" ;;
    ","*) echo " *ptr=getchar();" ;;
    "["*) echo " while(*ptr){" ;;
    "]"*) echo " }" ;;
    esac
    string="${string#?}"
  done
done <"$1"

せっかくなので、Brainf*ck をC言語に変換するトランスレータ（トランスパイラ？）っぽくしてみました。

bf2c.sh

#!/bin/bash
# brainf*ck to c-lang translator
# date: 2018-04-24

VERSION="$(basename $0) version 0.0.1 (2018-04-24)"

if [ $# -ne 1 -o "$1" = "-h" -o "$1" = "--help" ] ; then
  echo "usage: $(basename $0) SOURCE_FILE"
  exit 1
elif [ "$1" = "-v" -o "$1" = "--version" ] ; then
  echo "${VERSION}"
  exit 0
fi

IN_FILE="$1"
OUT_FILE="${1%.*}.c"

cat >"${OUT_FILE}" <<EOD
#include <stdio.h>
#include <stdlib.h>
int main(){
 void *buff=calloc(30000,sizeof(char));
 char *ptr=(char*)buff;
EOD

NEST=0
LINE_NUM=0
while IFS= read -r string ; do
  LINE_NUM=$((LINE_NUM + 1))
  COLUMN_NUM=0
  while [ -n "$string" ] ; do
    COLUMN_NUM=$((COLUMN_NUM + 1))
    case "$string" in
    ">"*) echo " ptr++;" ;;
    "<"*) echo " ptr--;" ;;
    "+"*) echo " (*ptr)++;" ;;
    "-"*) echo " (*ptr)--;" ;;
    "."*) echo " putchar(*ptr);" ;;
    ","*) echo " *ptr=getchar();" ;;
    "["*)
      echo " while(*ptr){"
      NEST=$((NEST + 1))
      ;;
    "]"*)
      if [ ${NEST} -eq 0 ] ; then
        echo "$(basename $0):${LINE_NUM}:${COLUMN_NUM}: found loop-end without loop-start" 1>&2
        exit 1
      fi
      NEST=$((NEST - 1))
      echo " }"
      ;;
    esac
    string="${string#?}"
  done
done < "${IN_FILE}" >>"${OUT_FILE}"

cat >>"${OUT_FILE}" <<EOD
 free(buff);
 return 0;
}
EOD

exit 0

C言語のソースを出力している個所を LLVM IR を出力するように変更したら、コンパイラ（のフロントエンド）が出来上がるはず。

スタックっぽいものを実現する方法

またループのネストなどを考慮して、ループラベル管理用のスタック的なデータ構造が欲しいのですが、標準的なPOSIXシェルでは配列などもないので、自力でCSV風なデータを処理することにしました。

最初に適当な変数を用意しておいて

STACK=""

pushにあたる処理は以下のような感じ。

ITEM=...
STACK="$ITEM,$STACK"

popにあたる処理は以下のような感じ。

ITEM="${STACK%%,*}"
STACK="${STACK#*,}"

Brainf*ck コンパイラ(LLVMフロントエンド)を作成

とりあえず完成です。

bfc.sh

#!/bin/sh
# brainf*ck compiler (LLVM front-end)
# date: 2018-04-24

VERSION="$(basename $0) version 0.0.1 (2018-04-24)"

if [ $# -ne 1 -o "$1" = "-h" -o "$1" = "--help" ] ; then
  echo "usage: $(basename $0) SOURCE_FILE"
  exit 1
elif [ "$1" = "-v" -o "$1" = "--version" ] ; then
  echo "${VERSION}"
  exit 0
fi

IN_FILE="$1"
OUT_FILE="${1%.*}.ll"
IDX=0

out_header() {
  echo "; ModuleID = '${IN_FILE}'"
  echo "source_filename = \"${IN_FILE}\""
  echo ""
  echo "define i32 @main() {"
  echo "  %ptr = alloca i8*, align 8"
  echo "  %buff = call noalias i8* @calloc(i64 30000, i64 1)"
  echo "  store i8* %buff, i8** %ptr, align 8"
  echo ""
}

out_footer() {
  echo "  call void @free(i8* %buff)"
  echo "  ret i32 0"
  echo "}"
  echo ""
  echo "declare noalias i8* @calloc(i64, i64)"
  echo "declare i32 @getchar()"
  echo "declare i32 @putchar(i32)"
  echo "declare void @free(i8*)"
  echo ""
  echo "!llvm.ident = !{!0}"
  echo "!0 = !{!\"${VERSION}\"}"
}

out_add_value() {
  echo "  %r${IDX} = load i8*, i8** %ptr, align 8"
  echo "  %r$((IDX+1)) = load i8, i8* %r${IDX}, align 1"
  echo "  %r$((IDX+2)) = add i8 %r$((IDX+1)), ${1}"
  echo "  store i8 %r$((IDX+2)), i8* %r${IDX}, align 1"
  echo ""
  IDX="$((IDX+3))"
}

out_move_ptr() {
  echo "  %r${IDX} = load i8*, i8** %ptr, align 8"
  echo "  %r$((IDX+1)) = getelementptr inbounds i8, i8* %r${IDX}, i32 ${1}" 
  echo "  store i8* %r$((IDX+1)), i8** %ptr, align 8"
  echo ""
  IDX="$((IDX+2))"
}

out_put_char() {
  echo "  %r${IDX} = load i8*, i8** %ptr, align 8"
  echo "  %r$((IDX+1)) = load i8, i8* %r${IDX}, align 1"
  echo "  %r$((IDX+2)) = sext i8 %r$((IDX+1)) to i32"
  echo "  %r$((IDX+3)) = call i32 @putchar(i32 %r$((IDX+2)))"
  echo ""
  IDX="$((IDX+4))"
}

out_get_char() {
  echo "  %r${IDX} = call i32 @getchar()"
  echo "  %r$((IDX+1)) = trunc i32 %r${IDX} to i8"
  echo "  %r$((IDX+2)) = load i8*, i8** %ptr, align 8"
  echo "  store i8 %r$((IDX+1)), i8* %r$((IDX+2)), align 1"
  echo ""
  IDX="$((IDX+3))"
}

out_loop_start() {
  echo "  br label %LOOP_COND${1}"
  echo ""
  echo "LOOP_COND${1}:"
  echo "  %r${IDX} = load i8*, i8** %ptr, align 8"
  echo "  %r$((IDX+1)) = load i8, i8* %r${IDX}, align 1"
  echo "  %r$((IDX+2)) = icmp ne i8 %r$((IDX+1)), 0"
  echo "  br i1 %r$((IDX+2)), label %LOOP_MAIN${1}, label %LOOP_END${1}"
  echo ""
  echo "LOOP_MAIN${1}:"
  IDX=$((IDX+3))
}

out_loop_end() {
  echo "  br label %LOOP_COND${1}"
  echo ""
  echo "LOOP_END${1}:"
}

out_header >"${OUT_FILE}"

LABEL=0
STACK=""
LINE_NUM=0
while IFS= read -r string ; do
  LINE_NUM=$((LINE_NUM + 1))
  COLUMN_NUM=0
  while [ -n "$string" ] ; do
    COLUMN_NUM=$((COLUMN_NUM + 1))
    case "$string" in
    ">"*) out_move_ptr 1 ;;
    "<"*) out_move_ptr -1 ;;
    "+"*) out_add_value 1 ;;
    "-"*) out_add_value -1 ;;
    "."*) out_put_char ;;
    ","*) out_get_char ;;
    "["*)
      LABEL=$((LABEL+1))
      STACK="${LABEL},${STACK}"
      out_loop_start $LABEL
      ;;
    "]"*)
      if [ -z "${STACK}" ] ; then
        echo "$(basename $0):${LINE_NUM}:${COLUMN_NUM}: found loop-end without loop-start" 1>&2
        exit 1
      fi
      POP="${STACK%%,*}"
      STACK="${STACK#*,}"
      out_loop_end $POP
      ;;
    esac
    string="${string#?}"
  done
done <"${IN_FILE}" >>"${OUT_FILE}"

out_footer >>"${OUT_FILE}"
exit 0

適当な Brainf*ck のソースを用意します。

hello_world.bf

>++++++++[<+++++++++++++>-]<.
---.
+++++++..
+++.
>++++++[<----------->-]<-.
------------.
>++++++++[<+++++++++++>-]<-.
--------.
+++.
------.
--------.
>+++++++++[<------>-]<.
[-]++++++++++.

Brainf*ck のソースをコンパイルして実行します。本当は llc とかを使うべきかもしれませんが、面倒なの clang からコンパイル。

$ ./bfc.sh hello_world.bf
$ clang hello_world.ll -o hello_world
warning: overriding the module target triple with x86_64-unknown-linux-gnu
      [-Woverride-module]
1 warning generated.
$ ./hello_world
hello, world.

いろいろ削ったせいで、なにやらワーニングが出ていますが、とりあえず動きました。
（ target triple を追加すればワーニングが消えるのは確認済）

もう一つ、Brainf*ck業界(?)では有名なErik Bosman氏の作ったとされるマンデルブロ集合を表示するプログラムをコンパイルしてみました。

オフィシャルなサイトがどこかわからないのですが githubのとあるリポジトリやとあるサイトで公開されているものです。

問題なく動きました。

$ ./bfc.sh mandelbrot.bf
$ time clang mandelbrot.ll -o mandelbrot -O2
（省略）

real    0m5.882s
user    0m5.833s
sys     0m0.037s
$ time ./mandelbrot
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB

real    0m1.263s
user    0m1.240s
sys     0m0.011s

コンパイルが6秒弱。実行は1秒ちょっと。最適化がかなり効いている感じですね。

最適化無しだと以下のような感じ。

$ ./bfc.sh mandelbrot.bf
$ time clang mandelbrot.ll -o mandelbrot -O0
（省略）

real    0m0.203s
user    0m0.168s
sys     0m0.034s
$ time ./mandelbrot
（省略）

real    0m20.517s
user    0m20.457s
sys     0m0.012s

コンパイルは一瞬。実行は20秒ぐらい。しょぼいノートPCの実行結果です。
頑張って計算している感じがして、これはこれでいいよね。

ついでにトランスパイラ＋gccの結果も。

$ ./bf2c.sh mandelbrot.bf
$ time gcc mandelbrot.c -o mandelbrot -O2
（省略）

real    0m1.938s
user    0m1.886s
sys     0m0.046s
$ time ./mandelbrot
（省略）

real    0m1.272s
user    0m1.256s
sys     0m0.003s

最後に

ソースは githubにも置きました。

[LLVM] シェルでBrainf*ckコンパイラを作る

はじめに

LLVM の IR を見てみる

Brainf*ck コンパイラを作るための情報を集める

全体の初期処理/終了処理

初期処理

終了処理

Brainf*ckの + 命令 / - 命令

+ 命令

- 命令

Brainf*ckの > 命令 / < 命令

> 命令

< 命令

Brainf*ckの , 命令 / . 命令

, 命令

. 命令

Brainf*ckの [ 命令 / ] 命令

[ 命令

] 命令