`phi` instructions have the "swap problem"

[sampsyo]

@pervognsen pointed out on Mastodon that phi instructions behave in a weird and probably bad way. Because they are "just normal instructions," they take effect immediately, i.e., all subsequent instructions immediately see the update to the variable they write. That includes other phi instructions that use the same variable on their right-hand sides.

Here's a self-contained example showing this behavior:

@main {
  i: int = const 5;
  one: int = const 1;
  zero: int = const 0;

.l0:
  x0: int = const 0;
  y0: int = const 1;
  jmp .l1;

.l1:
  x1: int = phi .l0 x0 .l1 y1;
  y1: int = phi .l0 y0 .l1 x1;
  print x1 y1;

  cond: bool = gt i zero;
  i: int = sub i one;
  br cond .l1 .end;

.end:
}

Under Bril's current semantics (as implemented by the reference interpreter and my from_ssa.py example), the two phis execute in order, so the first one clobbers x1 before the second one reads it.

This behavior is nonstandard and problematic. Under a more normal SSA semantics, the phis would execute "simultaneously," i.e., they would all read the RHS values from the start of the basic block, never from earlier phis in the same basic block. This program would then swap the values of x1 and y1 on every trip around the loop.

In the context of out-of-SSA transformations, this issue is called the "swap problem" in this classic Preston Briggs banger.

Anyway, my take here is that this (along with #108) is yet another consequence of my trying too hard to treat φ-nodes as "just normal Bril instructions." I was enamored with the idea that Bril's SSA form could be a tiny extension on top of the baseline non-SSA language, that interpreters wouldn't have to work too hard to tack on this one additional feature, and that we wouldn't need awkward restrictions like having all the φ-nodes appear at the beginnings of basic blocks. I think this has worked out poorly, and an SSA variant needs deeper changes to the language. At the very least, we cannot treat φ-nodes as normal instructions that read their arguments and write their results in order, like any other instruction.

If we do a more holistic redesign, I wonder whether something closer to MLIR-style basic block arguments might be a better choice. If nothing else, they make it more explicit that φ-nodes are semantically distinct from other instructions.

[0adb]

In case it is of use, I think I was able to slightly modify the interpreter to handle the swap problem, at least in the specific example in the issue. My modified interpreter is at https://github.com/0adb/bril. Instructions for compiling it are in the README, but the main changes are in bril2i.ts. The main change was to add a second environment variable to the state maintained during function execution, which would be updated to the most recent environment only when changing labels, and which would be what a phi instruction would check when assigning to a variable.

I uploaded the example given in the issue as test/interp/ssa/ssa-swap.bril in the fork, and was able to obtain the following results (behavior from the original bril interpreter, and then from the new one):

arthur@myMachineName:~/Documents/bril$ bril2json < test/interp/ssa/ssa-swap.bril | brili
0 1
1 1
1 1
1 1
1 1
1 1
arthur@myMachineName:~/Documents/bril$ bril2json < test/interp/ssa/ssa-swap.bril | bril2i
0 1
1 0
0 1
1 0
0 1
1 0

I also checked that the other SSA test cases would behave the same between brili.ts and bril2i.ts and they seem to be good. Have not tested the other interpreter tests though.

[sampsyo]

Hi, @0adb—sorry I somehow missed your very useful comment a few months ago! This was good thinking: to change the phi instruction's semantics to (a) require at least contiguous runs of phis, and probably require them to start at the top of a block, and (b) change their semantics to be "simultaneous" within these contiguous runs. This would have been the way to go if we had stuck with the existing SSA extension design.

In #403, however, I ended up designing an entirely new SSA extension that sidesteps the "simultaneity" requirement. Here is a version of the program above written using the new extension:

@main {
  i: int = const 5;
  one: int = const 1;
  zero: int = const 0;

.l0:
  x0: int = const 0;
  y0: int = const 1;
  upsilon x1 x0;
  upsilon y1 y0;
  jmp .l1;

.l1:
  x1: int = phi;
  y1: int = phi;
  print x1 y1;

  cond: bool = gt i zero;
  i: int = sub i one;

  upsilon x1 y1;
  upsilon y1 x1;
  br cond .l1 .end;

.end:
}

Fortunately, the reference interpreter now does the right thing with this program:

$ bril2json < ssa/swap-problem.bril | brili
0 1
1 0
0 1
1 0
0 1
1 0

Case closed!