Kengo's blog

Technical articles about original projects, JVM, Static Analysis and JavaScript.

How to implement Brainf*ck on LLVM IR

I am still thinking...

Brainf*ckLLVM IR
> (incr pointer)load, add nsw, store
phi
< (decr pointer)load, sub nsw, store
phi
+ (incr value)getelementptr, load, add nsw, store
- (decr value)getelementptr, load, sub nsw, store
. (output)call i32 @putchar(i32)
, (input)call i32 @getchar()
[ (while) br
] (while-end)br

,*. (increment input)

define i32 @main() uwtable ssp {
  %1 = call i32 @getchar()
  %2 = add nsw i32 %1, 1
  %3 = call i32 @putchar(i32 %2)
  ret i32 0
}

declare i32 @getchar()

declare i32 @putchar(i32)

say "hello"

define i32 @main() uwtable ssp {
  call i32 @putchar(i32 104)
  call i32 @putchar(i32 101)
  call i32 @putchar(i32 108)
  call i32 @putchar(i32 108)
  call i32 @putchar(i32 111)
  ret i32 0
}

declare i32 @putchar(i32)

+[>,.<] (echo)

define i32 @main() uwtable ssp {
entry:
  br label %loop

loop:
  %input = call i32 @getchar()
  call i32 @putchar(i32 %input)
  %continue = icmp ne i32 %input, 0
  br i1 %continue, label %loop, label %return

return:
  ret i32 0
}

declare i32 @getchar()

declare i32 @putchar(i32)

print argc

define i32 @main(i32 %argc) uwtable ssp {
  %argc.addr = alloca i32, align 4

  store i32 %argc, i32* %argc.addr, align 4
  %1 = load i32* %argc.addr, align 4
  %char = add nsw i32 %1, 47
  call i32 @putchar(i32 %char)

  ret i32 0
}

declare i32 @putchar(i32)

print argument

#include <stdio.h>
int main(int argc, char const* argv[])
{
  int i;
  for(i=1; i<argc; ++i)
  {
    printf("%s¥n", argv[i]);
  }
  return 0;
}
$ clang++ p.cpp -emit-llvm -S -o -
; ModuleID = 'p.cpp'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.8.0"

@.str = private unnamed_addr constant [4 x i8] c"%s¥0A¥00", align 1

define i32 @main(i32 %argc, i8** %argv) uwtable ssp {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i8**, align 8
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 %argc, i32* %2, align 4
  store i8** %argv, i8*** %3, align 8
  store i32 1, i32* %i, align 4
  br label %4

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

; <label>:8                                       ; preds = %4
  %9 = load i32* %i, align 4
  %10 = sext i32 %9 to i64
  %11 = load i8*** %3, align 8
  %12 = getelementptr inbounds i8** %11, i64 %10
  %13 = load i8** %12, align 8
  %14 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i8* %13)
  br label %15

; <label>:15                                      ; preds = %8
  %16 = load i32* %i, align 4
  %17 = add nsw i32 %16, 1
  store i32 %17, i32* %i, align 4
  br label %4

; <label>:18                                      ; preds = %4
  ret i32 0
}

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