Initial commit: fib (eqI_b and ltI version); nfib

8 files changed, 816 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..f948d98
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,9 @@
+*.abc
+*.bc
+*.o
+*.opt.ll
+*.s
+
+fib_eqI_b
+fib_ltI
+nfib
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..fee742d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,30 @@
+BIN:=fib_eqI_b fib_ltI nfib
+OPTLL:=$(addsuffix .opt.ll,$(BIN))
+OBJ:=$(addsuffix .o,$(BIN))
+ASM:=$(addsuffix .s,$(BIN))
+BC:=$(addsuffix .bc,$(BIN))
+
+all: $(BIN)
+
+$(BIN): %: %.o
+	clang-11 $^ -o $@
+
+$(OBJ): %.o: %.bc
+	llc-11 -filetype=obj $^ -o $@
+
+$(ASM): %.s: %.bc
+	llc-11 $^ -o $@
+
+$(BC): %.bc: %.opt.ll
+	llvm-as-11 $^ -o $@
+
+$(OPTLL): %.opt.ll: %.ll
+	opt-11 -S -always-inline $^ -o $@
+	opt-11 -S -instcombine $@ -o $@
+	opt-11 -S -O3 $@ -o $@
+	opt-11 -S -O3 $@ -o $@
+
+clean:
+	$(RM) $(BIN) $(OBJ) $(ASM) $(BC)
+
+.PHONY: all clean
diff --git a/fib_eqI_b.dcl b/fib_eqI_b.dcl
new file mode 100644
index 0000000..62cb4b7
--- /dev/null
+++ b/fib_eqI_b.dcl
@@ -0,0 +1,3 @@
+definition module fib_eqI_b
+
+fib :: Int -> Int
diff --git a/fib_eqI_b.icl b/fib_eqI_b.icl
new file mode 100644
index 0000000..315eac9
--- /dev/null
+++ b/fib_eqI_b.icl
@@ -0,0 +1,20 @@
+implementation module fib_eqI_b
+
+(+) :: !Int !Int -> Int
+(+) a b
+	= code inline {
+		addI
+	}
+
+(-) :: !Int !Int -> Int
+(-) a b
+	= code inline {
+		subI
+	}
+
+fib :: Int -> Int
+fib 0 = 1
+fib 1 = 1
+fib n = fib (n-2) + fib (n-1)
+
+Start = fib 43
diff --git a/fib_eqI_b.ll b/fib_eqI_b.ll
new file mode 100644
index 0000000..0566665
--- /dev/null
+++ b/fib_eqI_b.ll
@@ -0,0 +1,361 @@
+target triple = "x86_64-pc-linux-gnu"
+
+@heap = global [10000 x i64] zeroinitializer, align 16
+@astack = global [10000 x i64*] zeroinitializer, align 16
+
+declare i64 @printf(i8*, ...)
+@printf_d = private unnamed_addr constant [3 x i8] c"%d\00", align 1
+@printf_c = private unnamed_addr constant [3 x i8] c"%c\00", align 1
+@printf_cycle = private unnamed_addr constant [16 x i8] c"cycle in spine\0a\00", align 1
+
+@INT = constant {i64, i64, i64*, i64, i8, i8, i8}
+	{i64 0, i64 0, i64* inttoptr (i64 0 to i64*), i64 3, i8 73, i8 78, i8 84}
+
+attributes #0 = { alwaysinline }
+
+define private i64** @_push_local_astack(i64** %asp.0, i64** %aspstart, i64** %globasp.0) #0 {
+entry:
+	br label %loop
+
+loop:
+	%asp = phi i64** [%asp.0, %entry], [%asp.1, %loop.0]
+	%globasp = phi i64** [%globasp.0, %entry], [%globasp.1, %loop.0]
+	%t.0 = icmp eq i64** %asp, %aspstart
+	br i1 %t.0, label %done, label %loop.0
+done:
+	ret i64** %globasp
+
+loop.0:
+	%globasp.1 = getelementptr i64*, i64** %globasp, i64 1
+	%n = load i64*, i64** %asp
+	store i64* %n, i64** %globasp.1
+	%asp.1 = getelementptr i64*, i64** %asp, i64 -1
+	br label %loop
+}
+
+define private i64* @addI(i64* %bsp.0) #0 {
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = add i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64* @eqI_b(i64 %i, i64 %n, i64* %bsp.0) #0 {
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 -1
+	%t.0 = load i64, i64* %bsp.1
+	%t.1 = icmp eq i64 %t.0, %i
+	%t.2 = zext i1 %t.1 to i64
+	store i64 %t.2, i64* %bsp.2
+	ret i64* %bsp.2
+}
+
+define private i64** @fillI_b(i64 %b_offset, i64 %a_offset, i64* %bsp.0, i64** %asp.0) #0 {
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %b_offset
+	%t.0 = load i64, i64* %bsp.1
+
+	%asp.1 = getelementptr i64*, i64** %asp.0, i64 %a_offset
+
+	%n.0 = load i64*, i64** %asp.1
+	%INT.0 = ptrtoint {i64, i64, i64*, i64, i8, i8, i8}* @INT to i64
+	%INT.1 = add i64 %INT.0, 2
+	store i64 %INT.1, i64* %n.0
+
+	%n.1 = getelementptr i64, i64* %n.0, i64 1
+	store i64 %t.0, i64* %n.1
+
+	ret i64** %asp.0
+}
+
+define private i64** @jsr_eval(i64 %n, i64** %asp.0, i64** %aspstart, i64** %globasp.0) #0 {
+	; TODO in case %n != 0 do we need to push it to the top of the stack?
+	%asp.1 = getelementptr i64*, i64** %asp.0, i64 %n
+
+	%n.0 = load i64*, i64** %asp.1
+	%d.0 = load i64, i64* %n.0
+
+	%t.0 = and i64 %d.0, 2
+	%t.1 = icmp eq i64 %t.0, 0
+	br i1 %t.1, label %eval, label %done
+
+done:
+	ret i64** %asp.0
+
+eval:
+	%globasp.1 = call i64** @_push_local_astack(i64** %asp.0, i64** %aspstart, i64** %globasp.0)
+	%nentry.0 = inttoptr i64 %d.0 to i64*(i64*, i64**)*
+	%n.1 = call i64* %nentry.0(i64* %n.0, i64** %globasp.1)
+	store i64* %n.1, i64** %asp.1
+	ret i64** %asp.0
+}
+
+define private i64* @ltI(i64* %bsp.0) #0 {
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = icmp slt i64 %t.0, %t.1
+	%t.3 = zext i1 %t.2 to i64
+	store i64 %t.3, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64** @pop_a1(i64** %asp.0) #0 {
+	store i64* undef, i64** %asp.0
+	%asp.1 = getelementptr i64*, i64** %asp.0, i64 -1
+	ret i64** %asp.1
+}
+
+define private i64* @pop_b1(i64* %bsp.0) #0 {
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	ret i64* %bsp.1
+}
+
+define private i64* @print_int(i64* %bsp.0) #0 {
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %t.0)
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	ret i64* %bsp.1
+}
+
+define private i64* @push_b(i64 %n, i64* %bsp.0) #0 {
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %t.0, i64* %bsp.2
+	ret i64* %bsp.2
+}
+
+define private i64** @push_node(i64* %label, i64 %arity, i64** %asp.0) #0 {
+entry:
+	%n.0 = load i64*, i64** %asp.0
+	%label.0 = ptrtoint i64* %label to i64
+	store i64 %label.0, i64* %n.0
+	br label %loop
+
+loop:
+	%asp.1 = phi i64** [%asp.0, %entry], [%asp.2, %loop.0]
+	%arity.0 = phi i64 [%arity, %entry], [%arity.1, %loop.0]
+	%t.0 = icmp eq i64 %arity.0, 0
+	br i1 %t.0, label %done, label %loop.0
+done:
+	ret i64** %asp.1
+
+loop.0:
+	%n.1 = getelementptr i64, i64* %n.0, i64 %arity
+	%n.2 = load i64, i64* %n.1
+	%n.3 = inttoptr i64 %n.2 to i64*
+	%asp.2 = getelementptr i64*, i64** %asp.1, i64 1
+	store i64* %n.3, i64** %asp.2
+	%arity.1 = sub i64 %arity.0, 1
+	br label %loop
+}
+
+define private i64* @pushI(i64 %i, i64* %bsp.0) #0 {
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %i, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64* @pushI_a(i64 %n, i64* %bsp.0, i64** %asp.0) #0 {
+	%asp.1 = getelementptr i64*, i64** %asp.0, i64 %n
+	%n.0 = load i64*, i64** %asp.1
+	%n.1 = getelementptr i64, i64* %n.0, i64 1
+	%t.0 = load i64, i64* %n.1
+
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %t.0, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64* @subI(i64* %bsp.0) #0 {
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = sub i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64* @update_b(i64 %n1, i64 %n2, i64* %bsp.0) #0 {
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n1
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 %n2
+	store i64 %t.0, i64* %bsp.2
+	ret i64* %bsp.0
+}
+
+define private i64* @updatepop_b01(i64* %bsp.0) #0 {
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	store i64 %t.0, i64* %bsp.1
+	ret i64* %bsp.1
+}
+
+define private i64* @peek_a(i64** %asp) #0 {
+	%t = load i64*, i64** %asp
+	ret i64* %t
+}
+
+define private i64 @peek_b(i64* %bsp) #0 {
+	%t = load i64, i64* %bsp
+	ret i64 %t
+}
+
+define i64* @_cycle_in_spine(i64** %globasp) prefix {i8*, i64} {i8* inttoptr (i64 0 to i8*), i64 0} {
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([16 x i8], [16 x i8]* @printf_cycle, i64 0, i64 0))
+	unreachable
+}
+
+define i64* @e_fib_eqI_b_nfib(i64* %n, i64** %globasp) prefix {i8*, i64} {i8* inttoptr (i64 0 to i8*), i64 1} {
+	%astack = alloca i64*, i64 10
+	%asp.000 = getelementptr i64*, i64** %astack
+	%bstack = alloca i64, i64 10
+	%bsp.000 = getelementptr i64, i64* %bstack, i64 9
+
+	%asp.001 = getelementptr i64*, i64** %asp.000, i64 1
+	store i64* %n, i64** %asp.001
+
+	%t.0 = bitcast i64*(i64**)* @_cycle_in_spine to i64*
+	%asp.002 = call i64** @push_node(i64* %t.0, i64 1, i64** %asp.001)
+
+	%t.1 = call i64* @peek_a(i64** %asp.002)
+	%asp.003 = call i64** @pop_a1(i64** %asp.002)
+	%globasp.0 = call i64** @_push_local_astack(i64** %asp.003, i64** %asp.000, i64** %globasp)
+	%t.2 = call i64 @ea1(i64* %t.1, i64** %globasp.0)
+	%bsp.001 = call i64* @pushI(i64 %t.2, i64* %bsp.000)
+
+	%asp.004 = call i64** @fillI_b(i64 0, i64 -0, i64* %bsp.001, i64** %asp.003)
+	%bsp.002 = call i64* @pop_b1(i64* %bsp.001)
+
+	%t.3 = call i64* @peek_a(i64** %asp.004)
+	%asp.005 = call i64** @pop_a1(i64** %asp.004)
+	ret i64* %t.3
+}
+
+define private i64 @ea1(i64* %n, i64** %globasp) {
+	%astack = alloca i64*, i64 10
+	%asp.000 = getelementptr i64*, i64** %astack, i64 0
+	%bstack = alloca i64, i64 10
+	%bsp.000 = getelementptr i64, i64* %bstack, i64 9
+
+	%asp.001 = getelementptr i64*, i64** %asp.000, i64 1
+	store i64* %n, i64** %asp.001
+
+	%asp.002 = call i64** @jsr_eval(i64 -0, i64** %asp.001, i64** %asp.000, i64** %globasp)
+	%bsp.001 = call i64* @pushI_a(i64 -0, i64* %bsp.000, i64** %asp.002)
+	%asp.003 = call i64** @pop_a1(i64** %asp.002)
+
+	%t.0 = call i64 @peek_b(i64* %bsp.001)
+	%bsp.002 = call i64* @pop_b1(i64* %bsp.001)
+	%t.1 = tail call i64 @s1(i64 %t.0, i64** %globasp)
+	ret i64 %t.1
+}
+
+define i64 @e_fib_eqI_b_sfib(i64 %arg, i64** %globasp) #0 {
+	%r = tail call i64 @s1(i64 %arg, i64** %globasp)
+	ret i64 %r
+}
+
+define private i64 @s1(i64 %arg, i64** %globasp) #0 {
+	%astack = alloca i64*, i64 10000
+	%asp.000 = getelementptr i64*, i64** %astack
+	%bstack = alloca i64, i64 10000
+	%bsp.000 = getelementptr i64, i64* %bstack, i64 9999
+
+	%bsp.001 = call i64* @pushI(i64 %arg, i64* %bsp.000)
+
+	%bsp.002 = call i64* @eqI_b(i64 0, i64 0, i64* %bsp.001)
+	%t.0 = call i64 @peek_b(i64* %bsp.002)
+	%bsp.003 = call i64* @pop_b1(i64* %bsp.002)
+	%t.1 = trunc i64 %t.0 to i1
+	br i1 %t.1, label %case.1, label %l.0
+
+l.0:
+	%bsp.004 = call i64* @eqI_b(i64 1, i64 0, i64* %bsp.003)
+	%t.2 = call i64 @peek_b(i64* %bsp.004)
+	%bsp.005 = call i64* @pop_b1(i64* %bsp.004)
+	%t.3 = trunc i64 %t.2 to i1
+	br i1 %t.3, label %case.2, label %case.3
+
+case.1:
+	%bsp.100 = call i64* @pop_b1(i64* %bsp.003)
+	%bsp.101 = call i64* @pushI(i64 1, i64* %bsp.100)
+
+	%r.1 = call i64 @peek_b(i64* %bsp.101)
+	%bsp.102 = call i64* @pop_b1(i64* %bsp.101)
+
+	ret i64 %r.1
+
+case.2:
+	%bsp.200 = call i64* @pop_b1(i64* %bsp.005)
+	%bsp.201 = call i64* @pushI(i64 1, i64* %bsp.200)
+
+	%r.2 = call i64 @peek_b(i64* %bsp.201)
+	%bsp.202 = call i64* @pop_b1(i64* %bsp.201)
+
+	ret i64 %r.2
+
+case.3:
+	%bsp.300 = call i64* @pushI(i64 1, i64* %bsp.005)
+	%bsp.301 = call i64* @push_b(i64 1, i64* %bsp.300)
+	%bsp.302 = call i64* @subI(i64* %bsp.301)
+
+	%arg.0 = call i64 @peek_b(i64* %bsp.302)
+	%bsp.302.0 = call i64* @pop_b1(i64* %bsp.302)
+	%ret.0 = call i64 @s1(i64 %arg.0, i64** %globasp)
+	%bsp.303 = call i64* @pushI(i64 %ret.0, i64* %bsp.302.0)
+
+	%bsp.304 = call i64* @pushI(i64 2, i64* %bsp.303)
+	%bsp.305 = call i64* @push_b(i64 2, i64* %bsp.304)
+	%bsp.306 = call i64* @subI(i64* %bsp.305)
+
+	%arg.1 = call i64 @peek_b(i64* %bsp.306)
+	%bsp.306.0 = call i64* @pop_b1(i64* %bsp.306)
+	%ret.1 = call i64 @s1(i64 %arg.1, i64** %globasp)
+	%bsp.307 = call i64* @pushI(i64 %ret.1, i64* %bsp.306.0)
+
+	%bsp.308 = call i64* @update_b(i64 1, i64 2, i64* %bsp.307)
+	%bsp.309 = call i64* @updatepop_b01(i64* %bsp.308)
+	%bsp.310 = call i64* @addI(i64* %bsp.309)
+
+	%r.3 = call i64 @peek_b(i64* %bsp.310)
+	%bsp.311 = call i64* @pop_b1(i64* %bsp.310)
+
+	ret i64 %r.3
+}
+
+define i64 @main() {
+	%heap = bitcast [10000 x i64]* @heap to i64*
+	%astack = bitcast [10000 x i64*]* @astack to i64**
+
+	%n.0 = getelementptr i64, i64* %heap
+	%INT.0 = ptrtoint {i64, i64, i64*, i64, i8, i8, i8}* @INT to i64
+	%INT.1 = add i64 %INT.0, 2
+	store i64 %INT.1, i64* %n.0
+	%n.0.0 = getelementptr i64, i64* %n.0, i64 1
+	store i64 43, i64* %n.0.0
+
+	%n.1 = getelementptr i64, i64* %n.0, i64 2
+	store i64 ptrtoint (i64*(i64*,i64**)* @e_fib_eqI_b_nfib to i64), i64* %n.1
+	%t.0 = ptrtoint i64* %n.0 to i64
+	%n.1.0 = getelementptr i64, i64* %n.1, i64 1
+	store i64 %t.0, i64* %n.1.0
+
+	%n.2 = call i64* @e_fib_eqI_b_nfib(i64* %n.1, i64** %astack)
+	%n.3 = getelementptr i64, i64* %n.2, i64 1
+
+	%r = load i64, i64* %n.3
+
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %r)
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_c, i64 0, i64 0), i64 10)
+
+	ret i64 0
+}
diff --git a/fib_ltI.icl b/fib_ltI.icl
new file mode 100644
index 0000000..9b9e879
--- /dev/null
+++ b/fib_ltI.icl
@@ -0,0 +1,11 @@
+module fib_ltI
+
+import StdEnv
+
+fib :: !Int -> Int
+fib n
+	| n < 2
+		= 1
+		= fib (n-2) + fib (n-1)
+
+Start = fib 43
diff --git a/fib_ltI.ll b/fib_ltI.ll
new file mode 100644
index 0000000..52df35c
--- /dev/null
+++ b/fib_ltI.ll
@@ -0,0 +1,188 @@
+target triple = "x86_64-pc-linux-gnu"
+
+declare i64 @printf(i8*, ...)
+@printf_d = private unnamed_addr constant [3 x i8] c"%d\00", align 1
+@printf_c = private unnamed_addr constant [3 x i8] c"%c\00", align 1
+
+%S = type { i64*, i64* }
+
+attributes #0 = { alwaysinline }
+
+define private %S @addI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = add i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @ltI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = icmp slt i64 %t.0, %t.1
+	%t.3 = zext i1 %t.2 to i64
+	store i64 %t.3, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @pop_b1(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @print_int(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %t.0)
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @push_b(i64 %n, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %t.0, i64* %bsp.2
+	%s.1 = insertvalue %S %s.0, i64* %bsp.2, 1
+	ret %S %s.1
+}
+
+define private %S @pushI(i64 %i, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %i, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @subI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = sub i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @update_b(i64 %n1, i64 %n2, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n1
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 %n2
+	store i64 %t.0, i64* %bsp.2
+	ret %S %s.0
+}
+
+define private %S @updatepop_b01(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	store i64 %t.0, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private i64 @peek_b(%S %s) #0 {
+	%bsp = extractvalue %S %s, 1
+	%t = load i64, i64* %bsp
+	ret i64 %t
+}
+
+define private {i64, %S} @_s1(i64 %arg, %S %s.000) #0 {
+	%s.001 = call %S @pushI(i64 %arg, %S %s.000)
+
+	%s.100 = call %S @pushI(i64 2, %S %s.001)
+	%s.101 = call %S @push_b(i64 1, %S %s.100)
+	%s.102 = call %S @ltI(%S %s.101)
+
+	%t.0 = call i64 @peek_b(%S %s.102)
+	%s.103 = call %S @pop_b1(%S %s.102)
+	%t.1 = trunc i64 %t.0 to i1
+	br i1 %t.1, label %l.0, label %else.1
+
+l.0:
+	%s.200 = call %S @pop_b1(%S %s.103)
+	%s.201 = call %S @pushI(i64 1, %S %s.200)
+
+	%r = call i64 @peek_b(%S %s.201)
+	%s.202 = call %S @pop_b1(%S %s.201)
+
+	%rval.0 = insertvalue {i64,%S} undef, i64 %r, 0
+	%rval.1 = insertvalue {i64,%S} %rval.0, %S %s.202, 1
+	ret {i64, %S} %rval.1
+
+else.1:
+	%s.300 = call %S @pushI(i64 1, %S %s.103)
+	%s.301 = call %S @push_b(i64 1, %S %s.300)
+	%s.302 = call %S @subI(%S %s.301)
+
+	%arg.0 = call i64 @peek_b(%S %s.302)
+	%s.302.0 = call %S @pop_b1(%S %s.302)
+	%ret.0 = call {i64,%S} @_s1(i64 %arg.0, %S %s.302.0)
+	%r.0 = extractvalue {i64, %S} %ret.0, 0
+	%s.302.1 = extractvalue {i64, %S} %ret.0, 1
+	%s.303 = call %S @pushI(i64 %r.0, %S %s.302.1)
+
+	%s.304 = call %S @pushI(i64 2, %S %s.303)
+	%s.305 = call %S @push_b(i64 2, %S %s.304)
+	%s.306 = call %S @subI(%S %s.305)
+
+	%arg.1 = call i64 @peek_b(%S %s.306)
+	%s.306.0 = call %S @pop_b1(%S %s.306)
+	%ret.1 = call {i64,%S} @_s1(i64 %arg.1, %S %s.306.0)
+	%r.1 = extractvalue {i64, %S} %ret.1, 0
+	%s.306.1 = extractvalue {i64, %S} %ret.1, 1
+	%s.307 = call %S @pushI(i64 %r.1, %S %s.306.1)
+
+	%s.308 = call %S @update_b(i64 1, i64 2, %S %s.307)
+	%s.309 = call %S @updatepop_b01(%S %s.308)
+	%s.310 = call %S @addI(%S %s.309)
+
+	%relse = call i64 @peek_b(%S %s.310)
+	%s.311 = call %S @pop_b1(%S %s.310)
+
+	%rval.2 = insertvalue {i64,%S} undef, i64 %relse, 0
+	%rval.3 = insertvalue {i64,%S} %rval.2, %S %s.311, 1
+	ret {i64, %S} %rval.3
+}
+
+define private {i64, %S} @_s2(i64 %arg, %S %s.000) {
+	%ret = tail call {i64,%S} @_s1(i64 %arg, %S %s.000)
+	ret {i64, %S} %ret
+}
+
+define i64 @main() {
+	%stack = alloca [10000 x i64]
+
+	%asp = getelementptr [10000 x i64], [10000 x i64]* %stack, i64 0, i64 0
+	%bsp = getelementptr [10000 x i64], [10000 x i64]* %stack, i64 0, i64 9999
+
+	%s.001 = insertvalue %S undef, i64* %asp, 0
+	%s.002 = insertvalue %S %s.001, i64* %bsp, 1
+
+	%ret = call {i64,%S} @_s2(i64 43, %S %s.002)
+	%r = extractvalue {i64, %S} %ret, 0
+
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %r)
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_c, i64 0, i64 0), i64 10)
+
+	ret i64 0
+}
diff --git a/nfib.ll b/nfib.ll
new file mode 100644
index 0000000..e81f115
--- /dev/null
+++ b/nfib.ll
@@ -0,0 +1,194 @@
+target triple = "x86_64-pc-linux-gnu"
+
+declare i64 @printf(i8*, ...)
+@printf_d = private unnamed_addr constant [3 x i8] c"%d\00", align 1
+@printf_c = private unnamed_addr constant [3 x i8] c"%c\00", align 1
+
+%S = type { i64*, i64* }
+
+attributes #0 = { alwaysinline }
+
+define private %S @addI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = add i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @ltI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = icmp slt i64 %t.0, %t.1
+	%t.3 = zext i1 %t.2 to i64
+	store i64 %t.3, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @pop_b1(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @print_int(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %t.0)
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @push_b(i64 %n, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %t.0, i64* %bsp.2
+	%s.1 = insertvalue %S %s.0, i64* %bsp.2, 1
+	ret %S %s.1
+}
+
+define private %S @pushI(i64 %i, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 -1
+	store i64 %i, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @subI(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	%t.1 = load i64, i64* %bsp.1
+	%t.2 = sub i64 %t.0, %t.1
+	store i64 %t.2, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private %S @update_b(i64 %n1, i64 %n2, %S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 %n1
+	%t.0 = load i64, i64* %bsp.1
+	%bsp.2 = getelementptr i64, i64* %bsp.0, i64 %n2
+	store i64 %t.0, i64* %bsp.2
+	ret %S %s.0
+}
+
+define private %S @updatepop_b01(%S %s.0) #0 {
+	%bsp.0 = extractvalue %S %s.0, 1
+	%t.0 = load i64, i64* %bsp.0
+	store i64 undef, i64* %bsp.0
+	%bsp.1 = getelementptr i64, i64* %bsp.0, i64 1
+	store i64 %t.0, i64* %bsp.1
+	%s.1 = insertvalue %S %s.0, i64* %bsp.1, 1
+	ret %S %s.1
+}
+
+define private i64 @peek_b(%S %s) #0 {
+	%bsp = extractvalue %S %s, 1
+	%t = load i64, i64* %bsp
+	ret i64 %t
+}
+
+define private {i64, %S} @_s1(i64 %arg, %S %s.000) #0 {
+	%s.001 = call %S @pushI(i64 %arg, %S %s.000)
+
+	%s.100 = call %S @pushI(i64 2, %S %s.001)
+	%s.101 = call %S @push_b(i64 1, %S %s.100)
+	%s.102 = call %S @ltI(%S %s.101)
+
+	%t.0 = call i64 @peek_b(%S %s.102)
+	%s.103 = call %S @pop_b1(%S %s.102)
+	%t.1 = trunc i64 %t.0 to i1
+	br i1 %t.1, label %l.0, label %else.1
+
+l.0:
+	%s.200 = call %S @pop_b1(%S %s.103)
+	%s.201 = call %S @pushI(i64 1, %S %s.200)
+
+	%r = call i64 @peek_b(%S %s.201)
+	%s.202 = call %S @pop_b1(%S %s.201)
+
+	%rval.0 = insertvalue {i64,%S} undef, i64 %r, 0
+	%rval.1 = insertvalue {i64,%S} %rval.0, %S %s.202, 1
+	ret {i64, %S} %rval.1
+
+else.1:
+	%s.300 = call %S @pushI(i64 2, %S %s.103)
+	%s.301 = call %S @push_b(i64 1, %S %s.300)
+	%s.302 = call %S @subI(%S %s.301)
+
+	%arg.0 = call i64 @peek_b(%S %s.302)
+	%s.302.0 = call %S @pop_b1(%S %s.302)
+	%ret.0 = call {i64,%S} @_s1(i64 %arg.0, %S %s.302.0)
+	%r.0 = extractvalue {i64, %S} %ret.0, 0
+	%s.302.1 = extractvalue {i64, %S} %ret.0, 1
+	%s.303 = call %S @pushI(i64 %r.0, %S %s.302.1)
+
+	%s.304 = call %S @pushI(i64 1, %S %s.303)
+	%s.305 = call %S @push_b(i64 2, %S %s.304)
+	%s.306 = call %S @subI(%S %s.305)
+
+	%arg.1 = call i64 @peek_b(%S %s.306)
+	%s.306.0 = call %S @pop_b1(%S %s.306)
+	%ret.1 = call {i64,%S} @_s1(i64 %arg.1, %S %s.306.0)
+	%r.1 = extractvalue {i64, %S} %ret.1, 0
+	%s.306.1 = extractvalue {i64, %S} %ret.1, 1
+	%s.307 = call %S @pushI(i64 %r.1, %S %s.306.1)
+
+	%s.308 = call %S @addI(%S %s.307)
+	%s.309 = call %S @pushI(i64 1, %S %s.308)
+	%s.310 = call %S @push_b(i64 1, %S %s.309)
+	%s.311 = call %S @update_b(i64 1, i64 2, %S %s.310)
+	%s.312 = call %S @update_b(i64 0, i64 1, %S %s.311)
+	%s.313 = call %S @pop_b1(%S %s.312)
+	%s.314 = call %S @update_b(i64 1, i64 2, %S %s.313)
+	%s.315 = call %S @updatepop_b01(%S %s.314)
+	%s.316 = call %S @addI(%S %s.315)
+
+	%relse = call i64 @peek_b(%S %s.316)
+	%s.317 = call %S @pop_b1(%S %s.316)
+
+	%rval.2 = insertvalue {i64,%S} undef, i64 %relse, 0
+	%rval.3 = insertvalue {i64,%S} %rval.2, %S %s.317, 1
+	ret {i64, %S} %rval.3
+}
+
+define private {i64, %S} @_s2(i64 %arg, %S %s.000) {
+	%ret = tail call {i64,%S} @_s1(i64 %arg, %S %s.000)
+	ret {i64, %S} %ret
+}
+
+define i64 @main() {
+	%stack = alloca [10000 x i64]
+
+	%asp = getelementptr [10000 x i64], [10000 x i64]* %stack, i64 0, i64 0
+	%bsp = getelementptr [10000 x i64], [10000 x i64]* %stack, i64 0, i64 9999
+
+	%s.001 = insertvalue %S undef, i64* %asp, 0
+	%s.002 = insertvalue %S %s.001, i64* %bsp, 1
+
+	%ret = call {i64,%S} @_s2(i64 43, %S %s.002)
+	%r = extractvalue {i64, %S} %ret, 0
+
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_d, i64 0, i64 0), i64 %r)
+	call i64 (i8*, ...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @printf_c, i64 0, i64 0), i64 10)
+
+	ret i64 0
+}