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.

changed the description

assigned to @rarbore2

Is this w/ most recent main where forkify is in default schedule, or is this in an unstructured loop?

On main. The error occurs after unforkify, so everything is just unstructured loops. The first loops never gets forkified but the second does and then gets unforkified.

mentioned in merge request !154 (merged)

mentioned in commit 6a00ad37

mentioned in commit 9b3bb526

closed with merge request !154 (merged)