プログラミング言語を作る。第6回：LLVM入門

引き続いて LLVM を勉強します。今回は、 FizzBuzz のC言語プログラムを LLVM に変換して、その内容を確認してみようと思います。

C言語の FizzBuzz プログラムです。

#include <stdio.h>

int main(void){
    int i;

    for(i = 1; i <= 100; i++){
        if(i % 15 == 0){
            printf("FizzBuzz\n");
        }else if(i % 5 == 0){
            printf("Buzz\n");
        }else if(i % 3 == 0){
            printf("Fizz\n");
        }else{
            printf("%d\n", i);
        }
    }

    return 0;
}

clang -emit-llvm -S FizzBuzz.c で、 LLVM コードを生成しました。明らかに不必要な部分を取り除いたのが次のコードになります。

@.str = private unnamed_addr constant [10 x i8] c"FizzBuzz\0A\00", align 1
@.str1 = private unnamed_addr constant [6 x i8] c"Buzz\0A\00", align 1
@.str2 = private unnamed_addr constant [6 x i8] c"Fizz\0A\00", align 1
@.str3 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1

; Function Attrs: nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 1, i32* %i, align 4
  br label %2

; <label>:2                                       ; preds = %29, %0
  %3 = load i32* %i, align 4
  %4 = icmp sle i32 %3, 100
  br i1 %4, label %5, label %32

; <label>:5                                       ; preds = %2
  %6 = load i32* %i, align 4
  %7 = srem i32 %6, 15
  %8 = icmp eq i32 %7, 0
  br i1 %8, label %9, label %11

; <label>:9                                       ; preds = %5
  %10 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([10 x i8]* @.str, i32 0, i32 0))
  br label %28

; <label>:11                                      ; preds = %5
  %12 = load i32* %i, align 4
  %13 = srem i32 %12, 5
  %14 = icmp eq i32 %13, 0
  br i1 %14, label %15, label %17

; <label>:15                                      ; preds = %11
  %16 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([6 x i8]* @.str1, i32 0, i32 0))
  br label %27

; <label>:17                                      ; preds = %11
  %18 = load i32* %i, align 4
  %19 = srem i32 %18, 3
  %20 = icmp eq i32 %19, 0
  br i1 %20, label %21, label %23

; <label>:21                                      ; preds = %17
  %22 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([6 x i8]* @.str2, i32 0, i32 0))
  br label %26

; <label>:23                                      ; preds = %17
  %24 = load i32* %i, align 4
  %25 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str3, i32 0, i32 0), i32 %24)
  br label %26

; <label>:26                                      ; preds = %23, %21
  br label %27

; <label>:27                                      ; preds = %26, %15
  br label %28

; <label>:28                                      ; preds = %27, %9
  br label %29

; <label>:29                                      ; preds = %28
  %30 = load i32* %i, align 4
  %31 = add nsw i32 %30, 1
  store i32 %31, i32* %i, align 4
  br label %2

; <label>:32                                      ; preds = %2
  ret i32 0
}

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

lli FizzBuzz.ll を実行すると、 FizzBuzz が出力されます。

プログラムを解読します。
まず気になるのが、ラベルがコメントアウトされていることです。試しにコメントアウトされた行を消去してみると、問題なく動作しました。ラベルの実体が存在しないのになぜ動くのか分かりませんので要調査ですが、自分が書く分にはきちんとラベルなどを記述すれば問題ないので後回しにしましょう。

LLVM コードにおいて、再代入は許されていないようです。例えば次のコードは %i に二回の代入が行われているためエラーとなります。

define i32 @main(){
    %i = alloca i32, align 4
    %i = add i32 1, 2
}

add の前を %j とすれば正常に動作します。しかし、再代入ができないとなると i=i+1 などを行う for 文などがかけないような気がしますが、 FizzBuzz のプログラムを読めば分かる通り、 load や store を使ってそれを行っています。

alloca という命令が目立ちますが、スタックフレームからローカル変数の場所を確保しているようです。 FizzBuzz.c においてのローカル変数 i は alloca で場所を確保し、load で値を読み込み、 store で値の代入を行っていますが、基本的にポインタで扱っています。後ろの align 4 は、メモリ番地が 4 の倍数であることを確かにするためのもので、無くても大丈夫のようです。 long long の変数を定義して LLVM コードを生成すると、ここが align 8 に変わりました。

その他、 add や cmp など、アセンブリに近い命令が並んでいます。ここまで理解できれば、 FizzBuzz.ll を自力で書くことができそうなので、次回（？）にそれを記載したいと思います。