Elixirコンパイラ②をElixirで作る：LLVM IRをElixirで生成（ASTはElixirマクロ互換）→再帰下降構文解析→ネイティブコード生成

[fukuoka.ex](https://fukuokaex.connpass.com/)のpiacereです
ご覧いただいて、ありがとうございます :bow:

今回も、[前回に引き続き](https://qiita.com/piacerex/items/1b277177ca1a612cf6de)、Elixirにて、Elixirコードからネイティブコード生成する「Elixirコンパイラ」を作っていきます

内容が、面白かったり、役に立ったら、「いいね」よろしくお願いします :wink:

# C++と同等のコードをElixirで書く

前回、LLVM IR解析向けに作った、下記C++コードと同等のコードをElixirで書くと、こうなります

```cpp:add.cpp
int main()
{
	int a = 1;
	return a + 2;
}
```

```elixir:add_elixir.ex
defmodule Add do
	def main() do
		a = 1
		a + 2
	end
end
```

# 初期Elixirコンパイラの仕様を考える

現時点では、defmoduleの部分を、どうマッピングするかを無視したいので、コード生成対象外とし、内部の関数のみを生成対象とします

また、関数呼び出しも、現時点におけるLLVM IRの解析対象に含まれていないため、割愛し、コンパイルされたネイティブコードは、暗黙でmain()を呼び出すこととします

あとは、「関数生成」と「束縛」、「加算」、「関数からの戻り値返却」の4種類だけ、サポートします

いずれも、回を追う毎に、サポート範囲は、拡げていく予定ですが、まずは最低限、これだけコンパイルできるようにします

# LLVM IRを出力するElixirコードを作る

それでは、ようやく本丸のLLVM IRを出力するコードを作ります

そして、このLLVM IR出力系は、Elixirで作ります

これはつまり、LLVMを挟んではいるものの、「Elixirで、ネイティブコードを生成するElixirコンパイラを作る」ということを意味しています

自分で自分のコードをコンパイル可能にする、というブートストラップ … まさに「超絶 萌え展開」ですね :laughing:

## ａ）Elixirコンパイラ用PJを作成する

まず、Elixir PJを作ります

```
mix new elixir_compiler
cd elixir_compiler
```

## ｂ）コンパイル対象となるElixirコードを置く

次に、コンパイル対象となるElixirコードをファイル保存します

なお、lib配下では無く、PJルートに置いてください

```elixir:add_elixir.ex
defmodule Add do
	def main() do
		a = 1
		a + 2
	end
end
```

## ｃ）Elixirマクロと互換性あるASTでパーサを想定する

LLVM IRを出力する手前に、Elixirコードのパースを行いますが、パース結果を、Elixirマクロと互換性あるASTにしておきます

上記ｂ）のコードを、quoteでAST化します

```
> iex -S mix

iex> quote do
...>   defmodule Add do
...>     def main() do
...>       a = 1
...>       a + 2
...>     end
...>   end
...> end
```

結果は、こんな感じです

```elixir
{:defmodule, [context: Elixir, import: Kernel],
 [
   {:__aliases__, [alias: false], [:Add]},
   [
     do: {:def, [context: Elixir, import: Kernel],
      [
        {:main, [context: Elixir], []},
        [
          do: {:__block__, [],
           [
             {:=, [], [{:a, [], Elixir}, 1]},
             {:+, [context: Elixir, import: Kernel], [{:a, [], Elixir}, 2]}
           ]}
        ]
      ]}
   ]
 ]}
```

「Elixirコンパイラのパース結果が、Elixirマクロと同じAST」 … これもワクワク展開 :kissing_smiling_eyes:

ちなみに、.exファイルから読み込んだ内容を、AST化するには、quoteは直接使わず、以下のようなコードになります

```
iex> {:ok, ast} = Code.string_to_quoted(File.read!("add_elixir.ex"))
iex> ast
```

このASTには、モジュール名などが入らず、行番号に変わりますが、内容的には同じです

```elixir
{:defmodule, [line: 1],
 [
   {:__aliases__, [line: 1], [:Add]},
   [
     do: {:def, [line: 2],
      [
        {:main, [line: 2], []},
        [
          do: {:__block__, [],
           [
             {:=, [line: 3], [{:a, [line: 3], nil}, 1]},
             {:+, [line: 4], [{:a, [line: 4], nil}, 2]}
           ]}
        ]
      ]}
   ]
 ]}
```

## ｄ）ElixirコンパイラをElixirで書く

LLVM IRを出力するElixirコードを作ります

基本的には、コンパイル対象のElixirコードを読み込み、コード内容に応じて、IO.putsでLLVM IRを文字列出力するだけです

しかもAST生成は、Elixirのquoteがそのまま使えるので、面倒な字句解析／構文解析を全て省略できます … ここで1つ、先程の伏線回収しつつ、これまたセルフコンパイル的展開、萌え :rocket:

なお、LLVMとの連携のために、Elixirコンパイラを「単独のコマンド」として実行することを想定して、escript対応、つまり、エントリーポイントとしてのmain()関数をメイン処理とします

```elixir:lib/elixir_compiler.ex
defmodule ElixirCompiler do
	def main(args \\ []) do
		create_label_numbers()

		emit_prefix()

		Enum.at(args, 0)
		|> File.read!
		|> parse
		|> emit

		emit_postfix()

		drop_label_numbers()
	end

	def emit_prefix() do
		# 下記の設定は手元PCでは必須では無い模様（お手元でうまく動かないときは文字列中に含めてください）
		# source_filename = "add.cpp"
		# target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"

		"""
		target triple = "x86_64-pc-windows-msvc19.14.26433"
		""" |> IO.puts 
	end
	def emit_postfix() do
		# 下記の設定は手元PCでは必須では無い模様（お手元でうまく動かないときは文字列中に含めてください）
		# attributes #0 = {noinline norecurse nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "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"}
		#!llvm.module.flags = !{!0, !1}
		#!llvm.ident = !{!2}
		#!0 = !{i32 1, !"wchar_size", i32 2}
		#!1 = !{i32 7, !"PIC Level", i32 2}
		#!2 = !{!"clang version 8.0.0 (tags/RELEASE_800/final)"}
		"""
		""" |> IO.puts 
	end

	def parse(body) do
		{:ok, ast} = body |> Code.string_to_quoted
		ast
	end

	def emit({:defmodule, _, modules}), do: emit_module(modules)
	def emit({:def, _, functions}) do
		emit_function(functions)
		emit_return(max_number())
	end
	def emit({:=, _, [{operand1, _, _ }, operand2]}) do
		new_no = add_label_number(operand1)
		emit_bind(new_no, operand2)
	end
	def emit({:+, _, [{operand1, _, _ }, operand2]}) do
		from_no = get_number(operand1)
		no_tmp  = add_label_number(String.to_atom("#{ Atom.to_string(operand1)}_#{ unique()}"))
		new_no = add_label_number( "#{Atom.to_string(operand1)}_add_#{from_no}_#{no_tmp}")
		emit_add(from_no, new_no, no_tmp, operand2)
	end

	def emit_add(from_no, new_no, no_tmp, value) do
		"""
			%#{no_tmp} = load i32, i32* %#{from_no}, align 4
			%#{new_no} = add nsw i32 %#{no_tmp}, #{value}
		""" |> IO.puts 
	end

	def emit_bind(new_no, value) do	#TODO: 本当はElixirの束縛だが、暫定で代入のみ
		"""
			%#{new_no} = alloca i32, align 4
			store i32 #{value}, i32* %#{new_no}, align 4
		""" |> IO.puts 
	end

	def emit_function([{function_name, [_ ], []}, function_inside]) do	#TODO: 複数関数時はパターンが変わる
		"""
		define dso_local i32 @#{function_name}() #0
		{
		""" |> IO.puts 
		emit_function_inside(function_inside)
	end

	def emit_function_inside([do: { :__block__, [], units}]), do: units |> Enum.each(&emit(&1))

	def emit_return(no) do	#TODO: 戻り値の種類で変わる
		"""
			ret i32 %#{no}
		}
		""" |> IO.puts 
	end

	def emit_module_inside([do: functions]), do: emit(functions)

	def emit_module([{:__aliases__, [_], [_module_name_atom]}, module_insides]) do	#TODO: 複数モジュール時はパターンが変わる
		#TODO: ここでモジュールのためのコード生成IO.puts（今回は割愛）
		# IO.puts "[MODULE NAME] #{Atom.to_string(module_name_atom)}"
		emit_module_inside(module_insides)
	end

	def create_label_numbers(), do: :ets.new(:label_number_table, [:named_table])
	def drop_label_numbers(),   do: :ets.delete(:label_number_table)
	def get_number(label),      do: :ets.lookup(:label_number_table, label) |> List.first |> elem(1)
	def is_exist_label(label),  do: :ets.lookup(:label_number_table, label) != []
	def list_label_numbers(),   do: :ets.select(:label_number_table, [{{ :"$1", :"$2"}, [], [:"$_"]}])
	def list_numbers(),         do: list_label_numbers() |> Enum.map(&elem(&1, 1))
	def max_number(),           do: if list_numbers() != [], do: (list_numbers() |> Enum.max), else: 0
	def next_number(),          do: max_number() + 1
	def add_label_number(label) do
		result = next_number()
		:ets.insert(:label_number_table, {label, result})
		result
	end
	def unique() do
		{:ok, dt} = DateTime.now("Etc/UTC")
		((dt |> DateTime.to_unix) * :rand.normal) |> Float.to_string |> String.replace(".", "_") |> String.replace("-", "")
	end
end
```

ご覧の通り、ASTを、再帰下降で構文解析しています

ただし、演算子が連続するケースは、Elixir側のASTを未確認なので、次回以降にペンディングします

あと、LLVM IR内の変数で使う自動発番は、Elixirコード中の変数名（もしくは計算ワーク用のテンポラリ名）に紐付く、「ラベル-自動発番テーブル（label_number_table）」で管理し、これはElixir標準のETS（インメモリDB）で実装しています

こういうラベルテーブル管理は、C++で書くと、中々面倒な領域ですが、Elixirは、とてもラクに実装でき、やはり隔世の感がパナいです

## ｅ）Elixirコンパイラをコマンド実行し、ネイティブコード生成する

escriptでコマンド化するので、mix.exsには、escript用設定を追記します

```elixir:mix.exs
defmodule ElixirCompiler.MixProject do
  use Mix.Project

  def project do
    [
    …
      escript: escript(), 
      deps: deps()
    ]
  end

  def escript() do
    [main_module: ElixirCompiler]
  end
…
```

escriptでコマンド化します

```
> mix escript.build
```

コマンド化したElixirコンパイラでコンパイルします

```
> escript elixir_compiler add_elixir.ex > add_elixir.ll

> llc add_elixir.ll

> clang++ add_elixir.s -o add_elixir.exe

> add_elixir

> echo %ERRORLEVEL%
3
```

やった、うまく動きました :tada:

生成したLLVM IRは、こんな感じになります

```llvm:add_elixir.ll
target triple = "x86_64-pc-windows-msvc19.14.26433"

define dso_local i32 @main() #0
{

	%1 = alloca i32, align 4
	store i32 2, i32* %1, align 4

	%2 = load i32, i32* %1, align 4
	%3 = add nsw i32 %2, 3

	ret i32 %3
}
```

# コンパイル元コードを変えて挙動をテストしてみる

コンパイル元のコードを変更しても、期待通りに動くか、テストします

```elixir:add_elixir.ex
defmodule Add do
	def main() do
		a = 2
		a + 3
	end
end
```

数字を変えても、うまく動きました

```
> escript elixir_compiler add_elixir.ex > add_elixir.ll

> llc add_elixir.ll

> clang++ add_elixir.s -o add_elixir.exe

> add_elixir

> echo %ERRORLEVEL%
5
```

# 終わり

今回、LLVM IRの出力系をElixirで開発し、Elixirコードをネイティブコンパイルできるようになりました

対応するElixir構文は、非常に小さなものですが、「ElixirでElixirをネイティブコンパイルする」という野望の第一歩としては、イイ感じではないでしょうか？

<strike>次回は、Enum.mapの追加を目指してみます（余裕があれば乗算も）</strike> Elixir用マルチコア／GPUドライバ兼ネイティブコードコンパイラ[「Pelemay」](https://github.com/zeam-vm/pelemay)にて、Enum.mapやString.replaceなど含む本格実装を始めたので、Pelemay関連コラムをググってご覧ください

# p.s.「いいね」よろしくお願いします

ページ左上の ![image.png](https://qiita-image-store.s3.amazonaws.com/0/155423/4d515047-cc48-382e-c2b1-3ad0cc50dbbf.png) や ![image.png](https://qiita-image-store.s3.amazonaws.com/0/155423/a4e3da58-70a3-4197-95a2-6a6906650d01.png) のクリックを、どうぞよろしくお願いします:bow:
ここの数字が増えると、書き手としては「ウケている」という感覚が得られ、連載を更に進化させていくモチベーションになりますので、もっとElixirネタを見たいというあなた、私達と一緒に盛り上げてください！:tada: