tail calls, baby!

[Erick Tryzelaar]

Check this out! I just got the standard felix optimizations working.

:::felix
type int = "%i32";
typedef bool = 2;
fun add : int*int -> int = "%add";
fun sub : int*int -> int = "%sub";
fun eq : int*int -> bool = "%eq";
fun lnot : bool -> bool = "%lnot";
proc exit : int = "exit";

fun foo (x:int) = {
if x == 0 do
return 10;
done;

return foo (x - 1);
}

exit $ foo 2;

Which compiles down to this code:

:::llvm
declare void @exit(i32)

define i32 @foo(i32 %x) {
entry:
%foo.x = alloca i32 ; <i32*> [#uses=4]
store i32 %x, i32* %foo.x
br label %start_21

start_21: ; preds = %_ifdoend_1, %entry
%0 = load i32* %foo.x ; <i32> [#uses=1]
%1 = icmp eq i32 %0, 0 ; <i1> [#uses=1]
%2 = icmp eq i1 %1, false ; <i1> [#uses=1]
br i1 %2, label %_ifdoend_1, label %else

_ifdoend_1: ; preds = %start_21
%3 = load i32* %foo.x ; <i32> [#uses=1]
%4 = sub i32 %3, 1 ; <i32> [#uses=1]
store i32 %4, i32* %foo.x
br label %start_21

else: ; preds = %start_21
ret i32 10
}

define void @0() {
entry:
%0 = call i32 @foo(i32 2) ; <i32> [#uses=1]
call void @exit(i32 %0)
ret void
}

[john skaller]

On 27/09/2009, at 10:51 AM, Erick Tryzelaar wrote:

>
> Check this out! I just got the standard felix optimizations working.

Cool .. now ..

>
> :::felix
> type int = "%i32";
> typedef bool = 2;
> fun add : int*int -> int = "%add";
> fun sub : int*int -> int = "%sub";
> fun eq : int*int -> bool = "%eq";
> fun lnot : bool -> bool = "%lnot";

shouldn't this code be in the library?

Interestingly, llvm uses fixed sized ints, so the typedefs
between i32 and int for C++ would go backwards.

Hmmmm.. this is a challange for the conditional compilation
system.

--
john skaller
ska...@users.sourceforge.net

[Erick Tryzelaar]

On Sun, Sep 27, 2009 at 4:08 AM, john skaller
<ska...@users.sourceforge.net> wrote:
>
> shouldn't this code be in the library?

It does, I just noticed that once I got optimizations working it
automatically inlined the internal tail call. I expect when I start
tail calling external functions then I'll use llvm's tail call
mechanism.

> Interestingly, llvm uses fixed sized ints, so the typedefs
> between i32 and int for C++ would go backwards.
>
> Hmmmm.. this is a challange for the conditional compilation
> system.

Yeah, I haven't figured out yet how to do that in the long run. We
could do something different for the llvm backend and say that int
always means a 32 bit number, but I expect that I'll just define int8,
int16, int32, int64, etc, and typedef byte, short, int, long to the
corresponding c typename. Shouldn't be that bad.