Anti-dependence related bug in GCM
Ran into the following that was impacting BFS:
#[entry]
fn bug<n: usize>() -> i32[n] {
let visited: bool[n];
let cost: i32[n];
for i = 0 to n {
if visited[i] {
cost[i] = cost[i] + 1;
}
}
for i = 0 to n {
visited[i] = true;
}
return cost;
}
The error occurs at the last execution of GCM, and reports
thread 'main' panicked at hercules_ir/src/dom.rs:157:17:
In DomChainIterator, top node (NodeID(40)) doesn't dominate bottom node (NodeID(1)).
Node 1 is the if of the first loop's guard while 40 is that loop's header.
The issue seems to be that GCM decides that the schedule_early of the read of visited in the first loop must is node 40 (inside the loop, this is correct) but that the schedule_late is Node 1 because it is computing the least common ancestors of its users (including anti-dependence users) and it has an anti-dependence user which is the write in the second loop and its actual user is the if inside the first loop, and their least common ancestor is Node 1.
Edited by Aaron Councilman