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.