Unnecessary phi instructions insert by to_ssa

[chsasank]

Here's an example bril for interp test add-overflow

@pow(base: int, exp: int): int {
  out: int = const 1;
  one: int = const 1;
.loop:
  end: bool = lt exp one;
  br end .ret .body;
.body:
  out: int = mul out base;
  exp: int = sub exp one;
  jmp .loop;
.ret:
  ret out;
}

Converting this to ssa using to_ssa.py gives following output

@pow(base: int, exp: int): int {
.b1:
  out.0: int = const 1;
  one.0: int = const 1;
  jmp .loop;
.loop:
  out.1: int = phi out.0 out.2 .b1 .body;
  exp.0: int = phi exp exp.1 .b1 .body;
  end.0: bool = phi __undefined end.1 .b1 .body;
  end.1: bool = lt exp.0 one.0;
  br end.1 .ret .body;
.body:
  out.2: int = mul out.1 base;
  exp.1: int = sub exp.0 one.0;
  jmp .loop;
.ret:
  ret out.1;
}

Note how end.0: bool = phi __undefined end.1 .b1 .body; is inserted and it's not necessary to have done that. In fact it's not used anywhere and tdce would remove it.

I will try to figure out where this issue is coming from.

[sampsyo]

Very broadly, unnecessary phis are indeed part of the implementation strategy for the SSA example. It tries to keep things as simple as possible by allowing the conversion to be somewhat wasteful, especially when the resulting waste can be cleaned up by a separate dead-code elimination pass. It would be nice to keep this example this way, i.e., prioritizing clarity of the implementation over efficiency of the output code.

Of course, it could be cool to make a separate version that is more efficient, even at the expense of more complicated code! Here, it probably suffices to just "collapse" phi-nodes before insertion if we detect that only one of their inputs is actually defined.

[chsasank]

I am ok with inefficient code. It's just that it makes my BRIL-> LLVM translator hard because of _undefined.

Here, it probably suffices to just "collapse" phi-nodes before insertion if we detect that only one of their inputs is actually defined.

I am not very sure about this actually. I see earlier discussion about _undefined in #108, #118 and so on. I don't really understand the semantics of _undefined here.

[chsasank]

Another option to get around this issue seems to be using mem2reg pass as in chapter 7 of the LLVM tutorial: https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl07.html#why-is-this-a-hard-problem. Do you recommend this over 'fixing' the issue? This mem2reg thing feels a bit dirty honestly, but it seems to be what everyone is doing.

[Pat-Lafon]

That's what I did for brillvm

[chsasank]

Is this the brillvm you refer to https://github.com/sampsyo/bril/tree/main/bril-llvm? This converts to SSA at BRIL level.

Would you recommend doing the same mem2reg again? Will it work fine for arrays etc as well?

I am using llvmlite to generate llvm text btw.

[Pat-Lafon]

See https://github.com/sampsyo/bril/tree/main/bril-rs/brillvm which does not do this conversion(though should support bril code that is already in ssa form).

Would you recommend doing the same mem2reg again? Will it work fine for arrays etc as well?

I think it depends on your use case. If your goal is to get to llvm ir quickly, then yes. I'm not sure in what way arrays are harder but it has been a while.

[chsasank]

Thanks. I will make this compromise for now. Makes my life easier.

I'm not sure in what way arrays are harder but it has been a while.

You know arrays are also represented with alloca stuff right. Worried if it effects my IR. I'll dig up more and keep you updated.

[Pat-Lafon]

I'm not sure in what way arrays are harder but it has been a while.

You know arrays are also represented with alloca stuff right. Worried if it effects my IR. I'll dig up more and keep you updated.

I think that is an implementation detail/optimization. On one hand, I allocated stack space for all of my variables first since the number of variables is statically known. So any alloca after that is independent of mem2reg. I also actually malloc'ed all of my bril arrays, it's less efficient but then I somewhat trust LLVM to optimize where it is safe and avoid issues related to lifetimes and stack sizes.

[chsasank]

Thanks, used alloca method to fix this. You can see the fix at chsasank/llama.lisp#6

cc: @GlowingScrewdriver.