Invalid Phis Generated

[ryan-berger]

We have the following bril program:

@main(v0: int) {
  v1_: int = const 0;
  v2_: int = const 3;
  v3_: int = const 5;
  v4_: int = const 1;
  v5_: int = id v1_;
  v6_: int = id v2_;
  v7_: int = id v3_;
  v8_: int = id v4_;
  v9_: int = id v0;
.v10_:
  v11_: bool = lt v5_ v9_;
  br v11_ .v12_ .v13_;
.v12_:
  v14_: int = add v8_ v5_;
  v15_: bool = eq v7_ v14_;
  br v15_ .v16_ .v17_;
.v16_:
  v18_: int = add v14_ v6_;
  v19_: int = id v18_;
  v20_: int = id v6_;
  v21_: int = id v7_;
  v22_: int = id v8_;
  v23_: int = id v9_;
.v24_:
  v25_: bool = const true;
  v26_: bool = id v25_;
  v27_: int = id v19_;
  v28_: int = id v6_;
  v29_: int = id v7_;
  v30_: int = id v8_;
  v31_: int = id v9_;
.v32_:
  v5_: int = id v27_;
  v6_: int = id v6_;
  v7_: int = id v7_;
  v8_: int = id v8_;
  v9_: int = id v9_;
  br v11_ .v10_ .v33_;
.v17_:
  v19_: int = id v14_;
  v20_: int = id v6_;
  v21_: int = id v7_;
  v22_: int = id v8_;
  v23_: int = id v9_;
  jmp .v24_;
.v13_:
  v34_: bool = const false;
  v26_: bool = id v34_;
  v27_: int = id v5_;
  v28_: int = id v6_;
  v29_: int = id v7_;
  v30_: int = id v8_;
  v31_: int = id v9_;
  jmp .v32_;
.v33_:
}

Which after running through brilc/bril_llvm gives us this IR:

define dso_local void @__main(i64 %v0) {
pre_entry:
  br label %v10_
v10_:
  %v9__1 = phi i64 [ %v9__1, %v32_ ], [ %v0, %pre_entry ]
  %v8__1 = phi i64 [ %v8__1, %v32_ ], [ 1, %pre_entry ]
  %v7__1 = phi i64 [ %v7__1, %v32_ ], [ 5, %pre_entry ]
  %v6__1 = phi i64 [ %v6__1, %v32_ ], [ 3, %pre_entry ]
  %v5__1 = phi i64 [ %v27__1, %v32_ ], [ 0, %pre_entry ]
  %v11__0 = icmp slt i64 %v5__1, %v9__1
  br i1 %v11__0, label %v12_, label %v13_
v12_:
  %v14__0 = add i64 %v8__1, %v5__1
  %v15__0 = icmp eq i64 %v7__1, %v14__0
  br i1 %v15__0, label %v16_, label %v17_
v16_:
  %v18__0 = add i64 %v14__0, %v6__1
  br label %v24_
v24_:
  %v23__1 = phi i64 [ %v9__1, %v17_ ], [ %v9__1, %v16_ ]
  %v22__1 = phi i64 [ %v8__1, %v17_ ], [ %v8__1, %v16_ ]
  %v21__1 = phi i64 [ %v7__1, %v17_ ], [ %v7__1, %v16_ ]
  %v20__1 = phi i64 [ %v6__1, %v17_ ], [ %v6__1, %v16_ ]
  %v19__1 = phi i64 [ %v14__0, %v17_ ], [ %v18__0, %v16_ ]
  %v18__1 = phi i64 [ %v18__1, %v17_ ], [ %v18__0, %v16_ ]
  br label %v32_
v32_:
  %v31__1 = phi i64 [ %v9__1, %v13_ ], [ %v9__1, %v24_ ]
  %v30__1 = phi i64 [ %v8__1, %v13_ ], [ %v8__1, %v24_ ]
  %v29__1 = phi i64 [ %v7__1, %v13_ ], [ %v7__1, %v24_ ]
  %v28__1 = phi i64 [ %v6__1, %v13_ ], [ %v6__1, %v24_ ]
  %v27__1 = phi i64 [ %v5__1, %v13_ ], [ %v19__1, %v24_ ]
  %v26__1 = phi i1 [ 0, %v13_ ], [ 1, %v24_ ]
  %v25__1 = phi i1 [ %v25__1, %v13_ ], [ 1, %v24_ ]
  %v23__3 = phi i64 [ %v23__3, %v13_ ], [ %v23__1, %v24_ ]
  %v22__3 = phi i64 [ %v22__3, %v13_ ], [ %v22__1, %v24_ ]
  %v21__3 = phi i64 [ %v21__3, %v13_ ], [ %v21__1, %v24_ ]
  %v20__3 = phi i64 [ %v20__3, %v13_ ], [ %v20__1, %v24_ ]
  %v19__3 = phi i64 [ %v19__3, %v13_ ], [ %v19__1, %v24_ ]
  %v18__2 = phi i64 [ %v18__2, %v13_ ], [ %v18__1, %v24_ ]
  %v15__1 = phi i1 [ %v15__1, %v13_ ], [ %v15__0, %v24_ ]
  %v14__1 = phi i64 [ %v14__1, %v13_ ], [ %v14__0, %v24_ ]
  br i1 %v11__0, label %v10_, label %v33_
v17_:
  br label %v24_
v13_:
  br label %v32_
v33_:
  ret void
}

Running this through clang sometimes succeeds because it "figures it out" (or sometimes miscompiles?? I don't recommend using clang here) but running said IR through llc gives us an error (there are many more with different variable names):

Instruction does not dominate all uses!
  %v18__1 = phi i64 [ %v18__1, %v17_ ], [ %v18__0, %v16_ ]
  %v18__1 = phi i64 [ %v18__1, %v17_ ], [ %v18__0, %v16_ ]

Since a phi cannot refer to itself.

Is this similar to this issue? It doesn't appear the SSA'd bril has any __undefined in it, so is bril's SSA choosing the value itself as the initial value?

The original program (this was what happened after we ran an optimizer on it) did have all values defined before their use (and it appears that this bril program that I've posted also does), this code seems reachable so I'm unsure as to why it would be hitting any of the limitations of phis in bril

[Pat-Lafon]

Just passing by but this looks unrelated to the linked issue. I'm imagining that brilc isn't taking into account that some of your variables are constant and don't need phi nodes.

[Pat-Lafon]

To restate some of an off github conversation, Bril to LLVM compilers have this edge case with phi nodes because the Bril currently imposes very few constraints on their usage unlike LLVM. A different example of this is that LLVM requires that phi nodes be at the top of the block, Bril currently does not. See the following; a direct translation of this valid Bril code would be invalid LLVM code.

# ARGS: true
@main(cond: bool) {
.top:
  a: int = const 5;
  br cond .here .there;
.here:
  b: int = const 7;
.there:
  f: int = const 42;
  c: int = phi a .top b .here;
  print c;
}

[ryan-berger]

To add to some more analysis I've done since then, it does appear that %v18__1 is not yet defined when passing through %v17 (which I thought was not the case). Theoretically, that'd mean that the value should be __undefined, but that is probably a different can of worms.

It is likely part of the problem in tandem with what you mentioned @Pat-Lafon that is creating this sort of behavior. For example,

I can offer a simple patch to insert __undefined into phi args that attempt to use themselves in their definition, but as mentioned in our off Github conversation, this isn't the thing that brilc/ssa.py were really built for

[oflatt]

I was under the impression that ssa.py should insert these __undefined variable references, and so this is a bug. I'd also worry that your patch would hide this bug for this particular case @ryan-berger

Edit: re-reading, I understand that it's not a bug in ssa.py but a bug in translation to LLVM. However I'm still not sure in particular what invariant we violated. Something about phi nodes for constants?

[Alex-Fischman]

The error above is not actually that a phi node refers to itself. Rather, it is because the definition of v18__2 can be reached without ever going through the definition of v18__1 (so it isn't dominated) by going from v10_ to v13_ to v32_.

[ryan-berger]

@Alex-Fischman nice catch, I didn't see that. I do believe that is one of two errors however (which may be why it prints it out twice?).

v18__2 also gives the same error but it has a singular definition, and its only use is itself.

[chsasank]

Similar issue at #318