小ネタ 2015-008

LLVM中間コードを生成するTiny BASICコンパイラを作ってみた

以前、CIL(MSIL)中間コードを生成するTiny BASICコンパイラというのを作ってみた。(2012-09-01)
それを元にJavaバイトコードを生成するTiny BASICコンパイラを作ってみた。(2013-03-01)
今回、これらをベースにLLVM中間コード(LLVM-IR)を生成するTiny BASICコンパイラを作ってみた。(2015-12-04)

1. つくってみたもの

 Tiny Basic Compiler (LLVM中間コード版)

 [ Tiny Basic Compiler 実行ファイル+ソースコード tinybas_llvm-ir_01.zip (download) ]

 特徴
 ・整数型の小型なBASIC
 ・シンプルな言語仕様なのでソースコードも短く、コンパイラの仕組みを学習するサンプルとして活用できる


2. 使い方


 BASICのソースコードをコンパイルし、出力される.llファイルをllvm-asというLLVM-IR用のアセンブラを使ってアセンブルして.bcファイルを生成する。
 lliを使ってビットコードファイルをインタープリタ実行することができる。

 順番に手順を説明すると以下のとおり。

 サンプルのソースコードは例えば次のようになる。(example1.bas)
 10 INPUT X
 20 Y= x*x + 6*x + 9
 30 PRINT Y


 コマンドラインで、次のようにコマンド入力してコンパイルする。
 % tinybas example1.bas

 結果、example1.ll が得られる。
 この.ll ファイルはllvm-as用のアセンブリーソースコードである。
 llvm-asを使って.bcファイルを作る。
 % llvm-as example1.ll
 で、example1.bcが作られる。

 実行するには、次のようにする。
 % lli example1.bc

 ちなみにアセンブリーソースコード(example1.llファイル)は、以下のように生成される。

;============================================================
;	Compiler: Tiny Basic Compiler Ver 0.1
;	Source: example1.bas
;	Object: example1.ll
;============================================================

@.1 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@.2 = private unnamed_addr constant [3 x i8] c"?\0A\00", align 1
@buf = common global [1024 x i8] zeroinitializer, align 1
declare i32 @printf(i8*, ...) nounwind
declare i8* @gets(i8*) nounwind
declare i32 @atoi(i8*) nounwind

define i32 @main() {
;------------------------------------
	%acc = alloca i32 , align 4
	br label %_L10

_L10:
	%_V0 = alloca i32 , align 4
	%1 = call i32(i8*,...)* @printf(i8* getelementptr inbounds([3 x i8]* @.2, i32 0, i32 0)) nounwind
	%2 = call i8* @gets(i8* getelementptr inbounds ([1024 x i8]* @buf, i32 0, i32 0)) nounwind
	%3 = call i32 @atoi(i8* getelementptr inbounds ([1024 x i8]* @buf, i32 0, i32 0)) nounwind
	store i32 %3, i32* %_V0 ,align 4
	br label %_L20

_L20:
	%_V1 = alloca i32 , align 4
	%4 = load i32* %_V0, align 4
	store i32 %4, i32* %acc
	%5 = load i32* %acc, align 4
	%6 = load i32* %_V0, align 4
	store i32 %6, i32* %acc
	%7 = load i32* %acc, align 4
	%8 = mul nsw i32 %5, %7
	store i32 %8, i32* %acc
	%9 = load i32* %acc, align 4
	store i32 6 , i32* %acc, align 4
	%10 = load i32* %acc, align 4
	%11 = load i32* %_V0, align 4
	store i32 %11, i32* %acc
	%12 = load i32* %acc, align 4
	%13 = mul nsw i32 %10, %12
	store i32 %13, i32* %acc
	%14 = load i32* %acc, align 4
	%15 = add nsw i32 %9, %14
	store i32 %15, i32* %acc
	%16 = load i32* %acc, align 4
	store i32 9 , i32* %acc, align 4
	%17 = load i32* %acc, align 4
	%18 = add nsw i32 %16, %17
	store i32 %18, i32* %acc
	%19 = load i32* %acc, align 4
	store i32 %19, i32* %_V1 ,align 4
	br label %_L30

_L30:
	%20 = load i32* %_V1, align 4
	store i32 %20, i32* %acc
	%21 = load i32* %acc, align 4
	%22 = call i32(i8*,...)* @printf(i8* getelementptr inbounds([4 x i8]* @.1, i32 0, i32 0), i32 %21) nounwind
	br label %_END

_END:
;------------------------------------
	ret i32 0
}


Java版TinyBasicやMSIL版TinyBasicに比べると、冗長なコードが多い。
LLVM-IRのコード生成はSSA(静的単一代入形式)などの仕組みが少し難しく、うまいコード生成が作れなかった。


このページの上記の説明では説明不足なので、blogで補足を書き足していく予定。
http://twilog.org/kakocom/search?word=tinybasic%20llvm-ir&ao=a