aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore1
-rw-r--r--Makefile2
-rw-r--r--fib_eqI_b.ll2
-rw-r--r--fib_ltI.ll2
-rw-r--r--nfib.ll2
-rw-r--r--nfib_nsa.icl26
-rw-r--r--nfib_nsa.ll239
-rw-r--r--rts.ll60
8 files changed, 329 insertions, 5 deletions
diff --git a/.gitignore b/.gitignore
index f948d98..c551dea 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,4 @@
fib_eqI_b
fib_ltI
nfib
+nfib_nsa
diff --git a/Makefile b/Makefile
index a37ac26..e30c528 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-BIN:=fib_eqI_b fib_ltI nfib
+BIN:=fib_eqI_b fib_ltI nfib nfib_nsa
OPTLL:=$(addsuffix .opt.ll,$(BIN))
OBJ:=$(addsuffix .o,$(BIN))
ASM:=$(addsuffix .s,$(BIN))
diff --git a/fib_eqI_b.ll b/fib_eqI_b.ll
index 8b7f547..58be88a 100644
--- a/fib_eqI_b.ll
+++ b/fib_eqI_b.ll
@@ -133,7 +133,7 @@ case.3:
}
define i64 @main() {
- %hp.0 = bitcast [10000 x i64]* @heap to i64*
+ %hp.0 = bitcast [100000000 x i64]* @heap to i64*
%astack = bitcast [10000 x i64*]* @astack to i64**
%n.0 = getelementptr i64, i64* %hp.0
diff --git a/fib_ltI.ll b/fib_ltI.ll
index b8e5fbf..3c26df7 100644
--- a/fib_ltI.ll
+++ b/fib_ltI.ll
@@ -57,7 +57,7 @@ define private i64 @_s2(i64 %arg, i64** %globasp) {
}
define i64 @main() {
- %heap = bitcast [10000 x i64]* @heap to i64*
+ %heap = bitcast [100000000 x i64]* @heap to i64*
%astack = bitcast [10000 x i64*]* @astack to i64**
%r = call i64 @_s2(i64 43, i64** %astack)
diff --git a/nfib.ll b/nfib.ll
index 967ca19..ccec313 100644
--- a/nfib.ll
+++ b/nfib.ll
@@ -63,7 +63,7 @@ define private i64 @_s2(i64 %arg, i64** %globasp) {
}
define i64 @main() {
- %heap = bitcast [10000 x i64]* @heap to i64*
+ %heap = bitcast [100000000 x i64]* @heap to i64*
%astack = bitcast [10000 x i64*]* @astack to i64**
%r = call i64 @_s2(i64 43, i64** %astack)
diff --git a/nfib_nsa.icl b/nfib_nsa.icl
new file mode 100644
index 0000000..5764e8f
--- /dev/null
+++ b/nfib_nsa.icl
@@ -0,0 +1,26 @@
+module nfib_nsa
+
+// compile with -nsa -h 2000m -gci 2000m
+
+(+) :: !Int !Int -> Int
+(+) a b = code inline {
+ addI
+}
+
+(-) :: !Int !Int -> Int
+(-) a b = code inline {
+ subI
+}
+
+(<) :: !Int !Int -> Bool
+(<) a b = code inline {
+ ltI
+}
+
+nfib :: Int -> Int
+nfib n
+ | n < 2
+ = 1
+ = nfib (n-2) + nfib (n-1) + 1
+
+Start = nfib 34
diff --git a/nfib_nsa.ll b/nfib_nsa.ll
new file mode 100644
index 0000000..051cdb0
--- /dev/null
+++ b/nfib_nsa.ll
@@ -0,0 +1,239 @@
+define {i64*,i64*} @n5(i64* %n, i64** %globasp.0, i64* %hp.0) align 8
+ prefix {i8*, i64} {i8* inttoptr (i64 0 to i8*), i64 0} {
+ %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*}(i64**,i64*)* @_cycle_in_spine to i64*
+ %asp.002 = call i64** @push_node(i64* %t.0, i64 0, i64** %asp.001)
+
+ %t.1 = call {i64,i64*} @ea5(i64** %globasp.0, i64* %hp.0)
+ %t.2 = extractvalue {i64,i64*} %t.1, 0
+ %hp.1 = extractvalue {i64,i64*} %t.1, 1
+ %bsp.001 = call i64* @pushI(i64 %t.2, i64* %bsp.000)
+
+ %asp.003 = call i64** @fillI_b(i64 0, i64 -0, i64* %bsp.001, i64** %asp.002)
+ %bsp.002 = call i64* @pop_b1(i64* %bsp.001)
+
+ %t.3 = call i64* @peek_a(i64** %asp.003)
+ %asp.004 = call i64** @pop_a1(i64** %asp.003)
+
+ %ret.0 = insertvalue {i64*, i64*} undef, i64* %t.3, 0
+ %ret.1 = insertvalue {i64*, i64*} %ret.0, i64* %hp.1, 1
+ ret {i64*, i64*} %ret.1
+}
+
+define private {i64,i64*} @ea5(i64** %globasp.0, i64* %hp.0) {
+ %ret.0 = tail call {i64,i64*} @s5(i64** %globasp.0, i64* %hp.0)
+ ret {i64,i64*} %ret.0
+}
+
+define private {i64,i64*} @s5(i64** %globasp.0, i64* %hp.0) {
+ %astack = alloca i64*, i64 10
+ %asp.000 = getelementptr i64*, i64** %astack
+ %bstack = alloca i64, i64 10
+ %bsp.000 = getelementptr i64, i64* %bstack, i64 9
+
+ %t.0 = call {i64**,i64*} @buildI(i64 34, i64** %asp.000, i64* %hp.0)
+ %asp.001 = extractvalue {i64**,i64*} %t.0, 0
+ %hp.1 = extractvalue {i64**,i64*} %t.0, 1
+
+ %t.1 = call i64* @peek_a(i64** %asp.001)
+ %asp.002 = call i64** @pop_a1(i64** %asp.001)
+ %t.2 = tail call {i64,i64*} @s4(i64* %t.1, i64** %globasp.0, i64* %hp.1)
+ ret {i64,i64*} %t.2
+}
+
+define {i64,i64*} @s4(i64* %n, i64** %globasp.0, i64* %hp.0) noinline {
+ %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
+
+ %asp.002 = call i64** @push_a(i64 -0, i64** %asp.001)
+ %hp.1 = call i64* @jsr_eval(i64 -0, i64** %asp.002, i64** %asp.000, i64** %globasp.0, i64* %hp.0)
+ %bsp.001 = call i64* @pushI_a(i64 -1, i64* %bsp.000, i64** %asp.002)
+ %asp.003 = call i64** @pop_a1(i64** %asp.002)
+ %bsp.002 = call i64* @pushI(i64 2, i64* %bsp.001)
+ %bsp.003 = call i64* @push_b(i64 1, i64* %bsp.002)
+ %bsp.004 = call i64* @update_b(i64 1, i64 2, i64* %bsp.003)
+ %bsp.005 = call i64* @update_b(i64 0, i64 1, i64* %bsp.004)
+ %bsp.006 = call i64* @pop_b1(i64* %bsp.005)
+ %bsp.007 = call i64* @ltI(i64* %bsp.006)
+
+ %t.0 = call i64 @peek_b(i64* %bsp.007)
+ %bsp.008 = call i64* @pop_b1(i64* %bsp.007)
+ %t.1 = trunc i64 %t.0 to i1
+ br i1 %t.1, label %l.0, label %else.1
+
+l.0:
+ %asp.100 = call i64** @pop_a1(i64** %asp.003)
+ %bsp.100 = call i64* @pushI(i64 1, i64* %bsp.008)
+
+ %t.2 = call i64 @peek_b(i64* %bsp.100)
+ %bsp.101 = call i64* @pop_b1(i64* %bsp.100)
+
+ %ret.0 = insertvalue {i64, i64*} undef, i64 %t.2, 0
+ %ret.1 = insertvalue {i64, i64*} %ret.0, i64* %hp.1, 1
+ ret {i64, i64*} %ret.1
+
+else.1:
+ %t.3 = call {i64**,i64*} @buildI(i64 1, i64** %asp.003, i64* %hp.1)
+ %asp.200 = extractvalue {i64**,i64*} %t.3, 0
+ %hp.2 = extractvalue {i64**,i64*} %t.3, 1
+
+ %asp.201 = call i64** @push_a(i64 -1, i64** %asp.200)
+
+ %t.4 = bitcast {i64*,i64*}(i64*,i64**,i64*)* @n2 to i64*
+ %t.5 = call {i64**,i64*} @build(i64* %t.4, i64 2, i64** %asp.201, i64** %asp.000, i64** %globasp.0, i64* %hp.2)
+ %asp.202 = extractvalue {i64**,i64*} %t.5, 0
+ %hp.3 = extractvalue {i64**,i64*} %t.5, 1
+
+ %t.6 = call i64* @peek_a(i64** %asp.202)
+ %asp.203 = call i64** @pop_a1(i64** %asp.202)
+ %t.7 = call {i64,i64*} @s4(i64* %t.6, i64** %globasp.0, i64* %hp.3)
+ %t.8 = extractvalue {i64,i64*} %t.7, 0
+ %hp.4 = extractvalue {i64,i64*} %t.7, 1
+ %bsp.200 = call i64* @pushI(i64 %t.8, i64* %bsp.008)
+
+ %t.9 = call {i64**,i64*} @buildI(i64 2, i64** %asp.203, i64* %hp.4)
+ %asp.204 = extractvalue {i64**,i64*} %t.9, 0
+ %hp.5 = extractvalue {i64**,i64*} %t.9, 1
+
+ %asp.205 = call i64** @push_a(i64 -1, i64** %asp.204)
+
+ %t.10 = bitcast {i64*,i64*}(i64*,i64**,i64*)* @n2 to i64*
+ %t.11 = call {i64**,i64*} @build(i64* %t.10, i64 2, i64** %asp.205, i64** %asp.000, i64** %globasp.0, i64* %hp.5)
+ %asp.206 = extractvalue {i64**,i64*} %t.11, 0
+ %hp.6 = extractvalue {i64**,i64*} %t.11, 1
+
+ %t.12 = call i64* @peek_a(i64** %asp.206)
+ %asp.207 = call i64** @pop_a1(i64** %asp.206)
+ %t.13 = call {i64,i64*} @s4(i64* %t.12, i64** %globasp.0, i64* %hp.6)
+ %t.14 = extractvalue {i64,i64*} %t.13, 0
+ %hp.7 = extractvalue {i64,i64*} %t.13, 1
+ %bsp.201 = call i64* @pushI(i64 %t.14, i64* %bsp.200)
+
+ %bsp.202 = call i64* @addI(i64* %bsp.201)
+ %bsp.203 = call i64* @pushI(i64 1, i64* %bsp.202)
+ %bsp.204 = call i64* @push_b(i64 1, i64* %bsp.203)
+ %bsp.205 = call i64* @update_b(i64 1, i64 2, i64* %bsp.204)
+ %bsp.206 = call i64* @update_b(i64 0, i64 1, i64* %bsp.205)
+ %bsp.207 = call i64* @pop_b1(i64* %bsp.206)
+ %bsp.208 = call i64* @addI(i64* %bsp.207)
+
+ %t.15 = call i64 @peek_b(i64* %bsp.208)
+ %bsp.209 = call i64* @pop_b1(i64* %bsp.208)
+
+ %ret.2 = insertvalue {i64, i64*} undef, i64 %t.15, 0
+ %ret.3 = insertvalue {i64, i64*} %ret.2, i64* %hp.7, 1
+ ret {i64, i64*} %ret.3
+}
+
+define {i64*,i64*} @n2(i64* %n, i64** %globasp.0, i64* %hp.0) align 8
+ prefix {i8*, i64} {i8* inttoptr (i64 0 to i8*), i64 2} {
+ %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*}(i64**,i64*)* @_cycle_in_spine to i64*
+ %asp.002 = call i64** @push_node(i64* %t.0, i64 2, i64** %asp.001)
+
+ %t.1 = call i64* @peek_a(i64** %asp.002)
+ %asp.003 = call i64** @pop_a1(i64** %asp.002)
+ %t.2 = call i64* @peek_a(i64** %asp.003)
+ %asp.004 = call i64** @pop_a1(i64** %asp.003)
+ %globasp.1 = call i64** @_push_local_astack(i64** %asp.004, i64** %asp.000, i64** %globasp.0)
+ %t.3 = call {i64, i64*} @ea2(i64* %t.1, i64* %t.2, i64** %globasp.1, i64* %hp.0)
+ %t.4 = extractvalue {i64, i64*} %t.3, 0
+ %hp.1 = extractvalue {i64, i64*} %t.3, 1
+ %bsp.001 = call i64* @pushI(i64 %t.4, i64* %bsp.000)
+
+ %asp.005 = call i64** @fillI_b(i64 0, i64 -0, i64* %bsp.001, i64** %asp.004)
+ %bsp.002 = call i64* @pop_b1(i64* %bsp.001)
+
+ %t.5 = call i64* @peek_a(i64** %asp.005)
+ %asp.006 = call i64** @pop_a1(i64** %asp.005)
+
+ %ret.0 = insertvalue {i64*, i64*} undef, i64* %t.5, 0
+ %ret.1 = insertvalue {i64*, i64*} %ret.0, i64* %hp.0, 1
+ ret {i64*, i64*} %ret.1
+}
+
+define private {i64, i64*} @ea2(i64* %arg1, i64* %arg2, i64** %globasp.0, i64* %hp.0) {
+ %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* %arg2, i64** %asp.001
+ %asp.002 = getelementptr i64*, i64** %asp.001, i64 1
+ store i64* %arg1, i64** %asp.002
+
+ %hp.1 = call i64* @jsr_eval(i64 -1, i64** %asp.002, i64** %asp.000, i64** %globasp.0, i64* %hp.0)
+ %hp.2 = call i64* @jsr_eval(i64 -0, i64** %asp.002, i64** %asp.000, i64** %globasp.0, i64* %hp.1)
+ %bsp.001 = call i64* @pushI_a(i64 -1, i64* %bsp.000, i64** %asp.002)
+ %bsp.002 = call i64* @pushI_a(i64 -0, i64* %bsp.001, i64** %asp.002)
+ %asp.003 = call i64** @pop_a1(i64** %asp.002)
+ %asp.004 = call i64** @pop_a1(i64** %asp.003)
+
+ %t.0 = call i64 @peek_b(i64* %bsp.002)
+ %bsp.003 = call i64* @pop_b1(i64* %bsp.002)
+ %t.1 = call i64 @peek_b(i64* %bsp.003)
+ %bsp.004 = call i64* @pop_b1(i64* %bsp.003)
+
+ %ret = tail call {i64, i64*} @s2(i64 %t.0, i64 %t.1, i64* %hp.2)
+ ret {i64, i64*} %ret
+}
+
+define private {i64, i64*} @s2 (i64 %arg1, i64 %arg2, i64* %hp.0) {
+ %astack = alloca i64*, i64 10
+ %asp.000 = getelementptr i64*, i64** %astack
+ %bstack = alloca i64, i64 10
+ %bsp.000 = getelementptr i64, i64* %bstack, i64 9
+
+ %bsp.001 = call i64* @pushI(i64 %arg2, i64* %bsp.000)
+ %bsp.002 = call i64* @pushI(i64 %arg1, i64* %bsp.001)
+
+ %bsp.003 = call i64* @subI(i64* %bsp.002)
+
+ %t.0 = call i64 @peek_b(i64* %bsp.003)
+ %bsp.004 = call i64* @pop_b1(i64* %bsp.003)
+
+ %ret.0 = insertvalue {i64, i64*} undef, i64 %t.0, 0
+ %ret.1 = insertvalue {i64, i64*} %ret.0, i64* %hp.0, 1
+ ret {i64, i64*} %ret.1
+}
+
+define i64 @main() {
+ %hp.0 = bitcast [100000000 x i64]* @heap to i64*
+ %astack = bitcast [10000 x i64*]* @astack to i64**
+
+ %n.0 = getelementptr i64, i64* %hp.0
+ store i64 ptrtoint ({i64*,i64*}(i64*,i64**,i64*)* @n5 to i64), i64* %n.0
+ %hp.1 = getelementptr i64, i64* %hp.0, i64 3
+
+ %t.0 = call {i64*,i64*} @n5(i64* %n.0, i64** %astack, i64* %hp.1)
+ %n.1 = extractvalue {i64*,i64*} %t.0, 0
+ %hp.2 = extractvalue {i64*,i64*} %t.0, 1
+
+ %n.1.0 = getelementptr i64, i64* %n.1, i64 1
+ %r = load i64, i64* %n.1.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/rts.ll b/rts.ll
index 7109f10..1a7d587 100644
--- a/rts.ll
+++ b/rts.ll
@@ -5,7 +5,7 @@ declare i64 @printf(i8*, ...)
@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
-@heap = global [10000 x i64] zeroinitializer, align 16
+@heap = global [100000000 x i64] zeroinitializer, align 16
@astack = global [10000 x i64*] zeroinitializer, align 16
attributes #0 = { alwaysinline }
@@ -40,6 +40,56 @@ define private i64* @addI(i64* %bsp.0) #0 {
ret i64* %bsp.1
}
+; TODO gc
+; TODO for arity < 2, we must reserve more space on the heap
+define private {i64**,i64*} @build(i64* %label, i64 %arity, i64** %asp.0, i64** %aspstart, i64** %globasp.0, i64* %hp.0) #0 {
+entry:
+ %label.0 = ptrtoint i64* %label to i64
+ store i64 %label.0, i64* %hp.0
+ %hp.1 = getelementptr i64, i64* %hp.0, i64 1
+ br label %loop
+
+loop:
+ %asp.1 = phi i64** [%asp.0, %entry], [%asp.2, %loop.0]
+ %hp.2 = phi i64* [%hp.1, %entry], [%hp.3, %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:
+ %asp.3 = getelementptr i64*, i64** %asp.1, i64 1
+ store i64* %hp.0, i64** %asp.3
+ %ret.0 = insertvalue {i64**,i64*} undef, i64** %asp.3, 0
+ %ret.1 = insertvalue {i64**,i64*} %ret.0, i64* %hp.2, 1
+ ret {i64**,i64*} %ret.1
+
+loop.0:
+ %t.1 = call i64* @peek_a(i64** %asp.1)
+ %asp.2 = call i64** @pop_a1(i64** %asp.1)
+ %t.2 = ptrtoint i64* %t.1 to i64
+ store i64 %t.2, i64* %hp.2
+ %hp.3 = getelementptr i64, i64* %hp.2, i64 1
+ %arity.1 = sub i64 %arity.0, 1
+ br label %loop
+}
+
+; TODO pass aspstart for gc
+define private {i64**,i64*} @buildI(i64 %i, i64** %asp.0, i64* %hp.0) #0 {
+ %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* %hp.0
+
+ %hp.1 = getelementptr i64, i64* %hp.0, i64 1
+ store i64 %i, i64* %hp.1
+
+ %asp.1 = getelementptr i64*, i64** %asp.0, i64 1
+ store i64* %hp.0, i64** %asp.1
+
+ %hp.2 = getelementptr i64, i64* %hp.0, i64 2
+ %ret.0 = insertvalue {i64**,i64*} undef, i64** %asp.1, 0
+ %ret.1 = insertvalue {i64**,i64*} %ret.0, i64* %hp.2, 1
+ ret {i64**,i64*} %ret.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
@@ -122,6 +172,14 @@ define private i64* @print_int(i64* %bsp.0) #0 {
ret i64* %bsp.1
}
+define private i64** @push_a(i64 %n, i64** %asp.0) #0 {
+ %asp.1 = getelementptr i64*, i64** %asp.0, i64 %n
+ %t.0 = load i64*, i64** %asp.1
+ %asp.2 = getelementptr i64*, i64** %asp.0, i64 1
+ store i64* %t.0, i64** %asp.2
+ ret i64** %asp.2
+}
+
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
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-13 09:03:57 +0000