Arbitrary CFG as Binaryen IR

[manuranga]

We are evaluating Binaryen for the ballerina-lang wasm backend.

Is it possible to express arbitrary CFG in Binaryen IR ? Or is it only possible via the Relooper C API?

From experimenting and reading the code, it looks like the answer is "it's only available via the C API". If the answer is that, appreciate it if you can explain if it makes sense for Binaryen to have a textual input format that can express arbitrary CFG, or is there a fundamental reason this doesn't make sense.

[tlively]

Binaryen IR is designed to be as similar as possible to WebAssembly itself (with the exception that it is an AST rather than a stack machine), so the IR can only directly represent control flow that WebAssembly itself can directly represent. As you've noted, the C API provides a utility for constructing IR from arbitrary CFGs using the relooper, but there is currently no textual representation for arbitrary CFGs.

Whether it makes sense to add a text format for arbitrary CFGs is an interesting question. Just like the IR itself, Binaryen's text format is as close as possible to WebAssembly's standard text format. We've even discussed options for replacing Binaryen's text format parser with one that conforms to the standard completely. A text format for supporting arbitrary CFGs would have to be an additional non-standard text format on top of that, and it's not clear whether the benefit outweighs the cost of defining and maintaining a new non-standard text format when it is generally more efficient to pass code to Binaryen as a binary or via the C API, where text formats are not involved.

[kripken]

I think it would make sense to add some form of text or binary support for arbitrary CFGs. This has come up before - it feels like a real missing feature in the wasm space.

But I agree with @tlively 's points about the downsides. Specifically, if we do this we'd need to have a plan for what to do if we want to stop supporting the binaryen text parser in the future (if we replace it). One option is that people could still use older versions of binaryen to read CFG wat files in that case, which would prevent immediate breakage for them.

[tlively]

Perhaps another option would be to have a separate tool (i.e. not part of Binaryen) for converting from the CFG text format to the standard text or binary formats. Maintaining a separate tools might be easier than maintaining an additional parser in Binaryen going forward (e.g. a separate tool could be written in Rust and re-use existing Rust crates, etc.)

[manuranga]

Thank you very much for the calcification.
We don't have C FFI yet, maybe in an year or so, that is why we were thinking of going via a text format to get started.

You mentioned

pass code to Binaryen as a binary

I assume this is wasm binary format. If so it'll have to be structured as well, isn't it?

It seems like a way forwarded for us would be to replicate what Relooper does just enough to get to a structured CFG for now, and switch over to Relooper C API when we get C FFI.

[tlively]

Yes, I meant passing a wasm binary to Binaryen, and yes, it would have to be structured as well. Until you get C FFI or we add a new text format, your plan sounds like the best option.