Problem

We have differing runtimes that have different costs for a given SSA instruction. In the case of inlining we are mostly concerned with the Brillig runtime as we expect all ACIR functions to be inlined.

However, when computing the weights of different functions we use the number of SSA instructions as our heuristic

This is imperfect as some SSA operations could translate to many different Brillig instructions while others could be closer to a one-to-one translation. This could lead to marking function weights incorrectly and an incorrect cost calculation.

The + 1 for the terminator also needs to be updated to accurately reflect real Brillig opcode costs. We can see how a jmpif terminator in fact requires two Brillig opcodes:

This then grows even more for jmp and return which require Mov instructions to pass along their arguments.

Happy Case

We should have cost estimates for how many Brillig instructions are generated from a given SSA instruction. This cost estimate should be used in computing the weights of functions in Brillig.

We actually do something similar in the basic_conditional optimization:

We could have a brillig_cost function on Instruction that returns this estimate and is used across passes that may need this estimate.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response