From c6d632ea339d20ccba169088c389ecf9ee0aa25c Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Thu, 7 Jan 2021 21:52:21 +0100 Subject: Add version of nfib without strictness analysis --- .gitignore | 1 + Makefile | 2 +- fib_eqI_b.ll | 2 +- fib_ltI.ll | 2 +- nfib.ll | 2 +- nfib_nsa.icl | 26 +++++++ nfib_nsa.ll | 239 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ rts.ll | 60 ++++++++++++++- 8 files changed, 329 insertions(+), 5 deletions(-) create mode 100644 nfib_nsa.icl create mode 100644 nfib_nsa.ll 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 -- cgit v1.2.3