Forkify with control flow

Was poking around at forkify a little bit and found a simpler example that demonstrates the issues it's having:

#[entry]
fn bug<n: usize>(x: i32[n], m: usize) -> i32[n] {
  let result: i32[n];

  for i = 0 to n {
    for j = 0 to m {
      result[i] += x[i];
    }
  }

  return result;
}

Using the schedule

gvn(*);
phi-elim(*);
dce(*);

let out = auto-outline(*);
cpu(out.bug);

ip-sroa(*);
sroa(*);
dce(*);
gvn(*);
phi-elim(*);
dce(*);

forkify(out.bug);
xdot[true](out.bug);

The outer loop here should be able to be forkified, but the inner can't be since its number of iterations is variable. The outer loop is not forkified, however, because the phi node (for result on the outer loop) is rejected by analyze_phis at line 549.

It seems like that condition is just there to prevent reduces that contain control flow, so I tried removing it which does seem to fix this example. However, then if we add a conditional inside the inner loop, say

for j = 0 to m {
  if j % 2 == 0 {
    result[i] += x[i];
  }
}

now forkify fails again with the same phi being rejected at line 583; it seems like there may be some issue here with how users and uses and being calculated when phis are involved. It looks like the phi associated with the if is halting identifying uses and so it never identifies the cycles (the phi associated with the if uses the phi associated with the inner loop which is a user of the phi that should become a reduce). Based on the comments in computing stop_on it seems that we're only meant to stop on "External" phis and reduces but it's treating the if's phi as external (since it just check that it's control is not the loop header).

Edited 5 months ago

Forkify with control flow

Designs

Child items ...

Activity