Divergent PE

[madmann91]

In rodent, when all the variants are enabled, PE (simple-pe) seems to diverge. Each variant can be compiled separately, though, so I suspect a bug in Thorin. To trigger this bug, compile rodent with commit d3424cb0a7235aca8b731e33ac6d9bd9d9a0284e. To disable a variant, edit tools/bench_traversal/bench_traversal.impala.

[madmann91]

Actually, I may have a program that's easier to understand for this bug:

extern "thorin" {
    fn pe_info[T](&[u8], T) -> ();
}

struct Array {
    read: fn (int) -> int,
    write: fn(int, int) -> ()
}

fn unroll(a: int, b: int, body: fn (int) -> ()) -> () {
    if a < b {
        pe_info("unroll", a);
        body(a);
        @unroll(a + 1, b, body, return)
    }
}

fn cmp_swap(dir: bool, i: int, j: int, array: Array) -> () {
    let d = (j - i) / 2;
    pe_info("cmp_swap d", d);
    for k in unroll(i, i + d) {
        pe_info("cmp_swap k", k);
        pe_info("cmp_swap k + d", k + d);
        let (a, b) = (@array.read(k), @array.read(k + d));
        if (a < b) == dir {
            @array.write(k,     b);
            @array.write(k + d, a);
        }
        @pe_info("cmp_swap dir", dir);
    }
}

fn merge(dir: bool, i: int, j: int, array: Array) -> () {
    if i < j - 1 {
        pe_info("merge i", i);
        pe_info("merge j", j);
        let m = (i + j) / 2;
        cmp_swap(dir, i, j, array);
        merge(dir, i, m, array);
        merge(dir, m, j, array)
    }
}

fn sort(dir: bool, i: int, j: int, array: Array) -> () {
    if i < j - 1 {
        pe_info("sort i", i);
        pe_info("sort j", j);
        let m = (i + j) / 2;
        sort(true, i, m, array);
        sort(false, m, j, array);
        merge(dir, i, j, array);
    }
}

extern fn sort_n(values: &mut [int], n: int) -> () {
    let mut values : [int * 4];
    let array = Array {
        write: |i, v| { values(i) = v; },
        read: |i| { values(i) }
    };
    for i in @unroll(2, 3) {
        if n == i @{
            for j in unroll(0, i) { @array.write(j, values(j)); }
            sort(true, 0, i, array);
            for j in unroll(0, i) { values(j) = @array.read(j); }
        }
    }
}

Compile with impala bug.impala -emit-llvm -O3 -log-level info -simple-pe. Everything is known at compile time in this program, but somehow the partial evaluator stops earlier than it should. It seems the order of evaluation of @ signs is incorrect.

[leissa]

Thx for sorting this out. I'll look into that

[madmann91]

I have looked into this more. The issue is the (only) dynamic branch in cmp_swap:

if (a < b) == dir

If you add @return() at the end of cmp_swap, the code works correctly. Interestingly, this should not be necessary in normal PE mode (without -simple-pe), because partial evaluation should continue after the if. Nethertheless, the code does not compile without this explicit @return, whether in simple PE mode or not.

[leissa]

fixed with the new PE.