[eurollvm] divergence while compiling factorial with recursive record

[wizzard0]

This one never finishes too ;)
Object encoding via recursive record as in [Cardelli 1984]

type char = u8;
type str = [char];


extern "C" {
    fn atoi(&str) -> int;
    fn print_int(int) -> ();
}

struct MyInt { 
    get: fn() -> int,
    set: fn(int) -> MyInt,
    bump: fn() -> MyInt
}

fn makeInt(a: int) -> MyInt {
   MyInt {
        get: || a,
        set: |a2| makeInt(a2),
        bump: || makeInt(a-1)
   }
}

fn fac_oo(n : MyInt)->MyInt {
    if (n.get() <= 0) {
        makeInt(1)
    } else {
        let dec = n.bump();
        makeInt(n.get() * fac_oo(dec).get())
    }
}

fn fac_wrap(n : int) -> int {
    fac_oo(makeInt(n)).get()
}

fn main(argc: int, argv: &[&str]) -> int {
    let n = if argc >= 2 { atoi(argv(1)) } else { 6 };

    let res = fac_wrap(n);

    print_int(res);
    res 
}

[leissa]

That's too much for our magic :)

In a nutshell, we can only eliminate closures, if the functions are either not recursive at all or tail-recursive. See our paper for details. The eurollvm branch does some additional trickery in order to optimize even other functions.

We are currently lacking an analysis+transformation to see, if we are actually able to optimize higher-order functions and closure-convert them otherwise.

That being said, if you rewrite your example using an ordinary while in fac_oo it should work on master.

TL;DR: duplicate of AnyDSL/thorin#3

[wizzard0]

We are currently lacking an analysis+transformation to see, if we are actually able to optimize higher-order functions and closure-convert them otherwise.

You mean, the k-CFA in paper means thorin tries to optimize K paths which the closure creation can be reached thru, and if there's an countably-infinite number of them (as in recursive invocations of fac), then it cannot detect that and tries to spawn int32 (or something) amount of flows anyway?

[leissa]

Not exactly. For the closure-elimination we actually don't need a CFA.