成果物・Githubリンク

注意

この記事で示すソースコードはクラス・メソッドなどが簡略化されている場合があります。

導入・背景

こんにちは。あきっち @akicchi1234です。

私がコンパイラを開発しようと思ったきっかけは単なる興味でした。
コンパイラを開発する前までは、コンパイラはいわゆる究極のブラックボックスで"""魔術"""でした。
中身がどうなってるのか知りたいという気持ちを抑えきれず、初めは趣味の範囲でコンパイラ開発を始めましたが、難しくて何回も挫折しました。
そして、当時"やらざるを得ない環境"があれば開発できると考え、運よくSecHack365というイベントを知りました。
2019年度、SecHack365に参加し、セキュアなコンパイラ開発をテーマに自作言語を開発を始めました。
SecHack365という名前の通り365日間のイベントです。一年間を通してモノづくりをします。
こうして"やらざるを得ない環境"を作ることに成功しました。

とはいえ、フルスクラッチで開発するのは大変だと思ったので、LLVMを使いながら開発を進めました。
しかし開発は難航し大変でした...

開発環境

Windows
Visual Studio 2019
LLVM 8.0.1
MSVC
C++

LLVMとは

公式: The LLVM Compiler Infrastructure
コンパイラを作るための基盤です。
実行時, リンク時などあらゆる段階で最適化をしてくれます。
LLVMを用いてLLVM-IR(中間言語)を生成、あとはLLVMが機械語を生成し、実行ファイルを作ります。

コンパイラが実行ファイルを生成するまでの流れ

大雑把な手順としては以下です。

全てをやるのは大変です。LLVMを使うと黄色の部分のみ開発すればいいので、比較的簡単になりますがLLVMにある程度詳しくなる必要があります。

"コンパイル"はサブタスク多いですが...

リンクはclangにお任せしました。

自作言語について

nek-otという言語を作りました。名前に特に意味はありません。

構文としてはGo, C/C++, Rustなどを参考にさせていただきました。

静的型付け、実行速度が速く、C/C++より安全というコンセプトです。

静的型付け

静的型付けとは、「コンパイル時に型が決まっていること」です。
以下のようなC#コードは型が違うのでコンパイル時にエラーになります。

SampleClassA a = new SampleClassB();

nek-otでもコンパイル・ランタイム時に型が違うエラーを検出することができます。

実行速度が速い

自作言語からLLVM-IR(LLVM-Intermidiate Representation:LLVM中間言語)にトランスパイルします。
LLVM-IRにするときに最適化され、必要のないコードなど削除されたり、効率の良い命令に変換されたりします。素晴らしいですね。

最適化例

最適化例を以下に示します。

左のコードはnek-otです。右がLLVM-IRです。
左のコードのLoop Unrollingではsum += i;をして結果的にsumは55になります。
LLVM-IRはコンパイル時に計算してLLVM-IRに定数として55を埋め込みます...すごい！

Inline expansionではmain関数内にインライン展開します。これにより関数呼び出しのオーバヘッドなどを軽減できます。
mumble(10);の結果は10*20なので200になります。
そして最適化すると

fn main() {
    writefln("%d", 55);
    writefln("%d", 200);
    ret;
}

と同等のコードに変換されます！すごい！

以下に実行速度を計測した結果を示します。 -O3とは、「最適化優先」でコンパイルするという引数オプションです。
ClangもLLVMで開発されているので、だいたい実行速度は同じです。

C/C++より安全

Java, C#などの言語には実装されている配列の範囲外アクセスです。

以下C#の例です。

int[] ary = new int[3] {1, 2, 3};

//System.IndexOutOfRangeException
ary[5] = 0;

nek-otでの同等のコードはこちらです。

fn main(){
    arr := i32[3] {1, 2, 3};
    arr[5] = 0;
    ret;
}

これをコンパイルすると"Array index out of range!"というエラーメッセージが表示されます。

もちろん、ランタイム時にも配列の範囲外アクセスを検出することができます。

import "io";

fn main(){
    arr := i32[5]{2, 4, 6, 8, 10};
    i := 0;
    for(i := 0; i < 10; i = i + 1)
        writef("%d ", arr[i]);
    ret;
}

他にも、0徐算・オーバーフロー・変数初期化前の使用などをコンパイル・ランタイム時に検出できます。

自作言語で書いた例

例の一覧はこちらにあります。
よければご覧ください。

以下にいくつか例を示します。
冒頭のプログラムのカレンダーを表示するコードです。うるう年なども考慮されています。

2021/4/12 追記
コード中にうるう年の判定に関するif-else ifブロックが記述されていますが、上手くコンパイルされていないのか動作せず、実行結果のGIFには2020/２の終わりは29日ですが28日までとなっております。

import "io";
fn calendar(year: i32, month: i32) {
    month0 := month--;
    t0 := i32[12]{1, 4, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};
    t1 := i32[12]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    if(year % 400 == 0)
        t1[1] = 29;
    else if(year % 4 == 0 && year % 100 != 0)
        t1[1] = 29;

    mstr := string[12]{"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};
    writefln("%13s%6d", mstr[month], year);
    writefln("%4s%4s%4s%4s%4s%4s%4s", "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat");
    w := i32;
    if(month <= 1) w = year - 1; else w = year;
    w0 := w / 4;
    w1 := w / 100;
    w2 := w / 400;
    w3 := t0[month];
    w = (w + w0 - w1 + w2 + w3) % 7;

    if(w > 0) {
        for(i := 1; i <= w; i++)
            writef("    ");
    }

    d1 := t1[month];
    for(j := 1; j <= d1; j++){
        writef("%4d", j);
        w = (w + 1) % 7;
        if(w == 0)
            writefln(" ");
    }
    if(w > 0)
        writefln(" ");
    month++;
    ret;
}

fn main(){
    calendar(2020, 2);
    ret;
}

フィボナッチ数列を求めるコード（計算量的に良いコードではありません）

import "io";
fn fibo(n : i32) -> i32 {
    if(n < 2)
        ret n;
    else 
        ret fibo(n-1) + fibo(n-2);
}
fn main() {
    i := 1; 
    while(i < 36) {
        writefln("fibo(%d) -> %d", i, fibo(i));
        i = i + 1;
    }
    ret;
}

成果物

冒頭のGIFと同じものです。

苦労話

自作言語をLLVM-IRにする必要があるのでそこで大変でした。
自作言語もイメージだけ持ってる状態で開発を開始したので後から構文を変えたりしました。
それに伴って別のところがエラー起きるというのがザラでした。よくわからないバグやエラーに悩まされました。

うまく進まず、自分の無力さを知ったりと色々勉強になる一年でした。
LLVMを使うと確かに簡単かもしれませんが、アーキテクチャのことを考えないので面白みにはかけるかもしれません。

最後に

大変でした。
普段はこのような低レイヤーのことはツイートしませんがもしかしたらツイートするかもしれません。
最近はAR関連のことをやっています。
よかったらぜひあきっち @akicchi1234、フォローお願いします！