Binaryen: Using Binaryen to optimize AssemblyScript's ARC code?

[dcodeIO]

I'm currently thinking about how to tackle an optimization of ARC code the AssemblyScript compiler emits, that is hard to come by on our end because we are reusing Binaryen's IR instead of rolling our own.

For example, if we have code like

{
  let a = new Ref();
  let b = a;
  let c = b;
}

the compiler conservatively generates

{
  let a = new Ref();
  let b = __retain(a);
  let c = __retain(b);
  __release(a);
  __release(b);
  __release(c);
}

which can be optimized by eliminating pairs of __retain and __release calls:

{
  let a = new Ref();
  let b = a;
  let c = b;
  __release(a);
}

in turn enabling other optimizations, like removing unnecessary locals or similar, potentially enabling eliminating pairs again. None of the solutions I've come up with so far seem ideal:

• Add a PostAssemblyScript pass, but one could argue that Binaryen should not include such passes for every possible language
• Use a custom build of Binaryen with custom passes, but that'd hurt dependents' integration with the binaryen npm module
• Attempt to use the C-API to build custom passes on our end, but that'd ultimately lead to reinventing wheels like data flow analysis

How would you approach this if your goal was to reuse as much of Binaryen as possible (we are really using it as our primary compiler framework, not just as an optimizer)?

[tlively]

This seems like an ideal use case for a future framework for binaryen plugins. Probably the "cleanest" solution today would be to use the C API to build custom passes, but you're right that that would involve reinventing a lot of wheels. Lacking a full-featured plugin system, I wouldn't have a problem merging AS-specific passes into mainline Binaryen. There is more than enough precedent with Emscripten having crazy bespoke tools in Binaryen, and I don't expect the number of languages wanting to have custom Binaryen passes to be very high.

[MaxGraey]

As another crazy option would be support for generating peephole optimizations from a DSL rules or python's script. Similar idea already exists in Go and mesa's compiler

[kripken]

I agree with @tlively that a PostAssemblyScript pass sounds good for now.

In the longer term it would be good to have a pass plugin API, which we have some ideas about.

[kripken]

A DSL is also an interesting idea, we had some ideas on that topic in our souper integration but so far nothing has been done.

[dcodeIO]

I agree with @tlively that a PostAssemblyScript pass sounds good for now.

Great, will give it a try! The algorithm here is about

• When we see a local = __retain(X), remember (retain, localIndex, location).
• When we see a __release(local), check if there is a (retain, localIndex. *) reachable linearly and eliminate. If control flow is non-linear, remember (release, localIndex, location) for the current branch.
• When non-linear control flow converges, match releases present in all branches leading here vs retains before the branches and eliminate.

So far I have glimpsed at LinearExecutionWalker and ControlFlowWalker, but I must admit that I'd appreciate any hints on approaching this correctly :)

[kripken]

Yeah, one of those would be relevant. I'd start with LinearExecutionWalker, which will optimize linear traces with no branches, which would be enough for your example, but not for e.g.

if (..) {
  ...
  retain
} else {
  retain
  ...
}
release

If that's important too then you can cook up a flow algorithm later on, but linear traces may give big wins already.

[dcodeIO]

Thanks, I indeed started with that but found that lots of the code looks like

function example(a: Ref, cond: bool): void {
  __retain(a); // can only cancel out if all subsequent branches do
  if (cond) {
    __release(a);
    return;
  }
  __release(a);
}

which complicates things. Currently toying around with CFGWalker, using contents to remember retains and releases in basic blocks with the intend to cancel them out. Have something working for retains and releases in the same basic block so far. Does that sound like the right direction?

[kripken]

Yeah, that sounds right.