Closed madmann91 closed 6 years ago
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.
Thx for sorting this out. I'll look into that
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.
fixed with the new PE.
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.