feat: try to inline brillig calls with all constant arguments

[asterite]

Description

Problem

Resolves #6453

Summary

Alternative to #6466

For now this PR just finds the brillig calls with all constant values, creates a VM for each, executes them, and if we can get some output values, the call results are replaced with those values.

Pending:

• If we managed to replace some calls, do all SSA optimization passes again as the new values could help further optimize SSA, then check if we can find calls with constant values, and repeat until we can't optimize anymore.

Additional Context

Documentation

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[github-actions]

Changes to circuit sizes

Generated at commit: 44b625be771084dfb2b8a841b6d9ba4bfe5cbf26, compared to commit: efa5cc4bf173b0ce49f47b1954165a2bdb276792

🧾 Summary (10% most significant diffs)

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
brillig_nested_arrays	-6 ✅	-60.00%	-6 ✅	-26.09%
strings	-11 ✅	-27.50%	-2,769 ✅	-98.82%

---

Full diff report 👇

Program	ACIR opcodes (+/-)	%	Circuit size (+/-)	%
pedersen_check	22 (-1)	-4.35%	3,174 (-2)	-0.06%
side_effects_constrain_array	9 (-4)	-30.77%	2,769 (-4)	-0.14%
hashmap	25,657 (-102)	-0.40%	64,653 (-240)	-0.37%
conditional_regression_underflow	1 (-12)	-92.31%	64 (-9)	-12.33%
brillig_nested_arrays	4 (-6)	-60.00%	17 (-6)	-26.09%
strings	29 (-11)	-27.50%	33 (-2,769)	-98.82%

[TomAFrench]

LGTM, it would also be good to cache the linked bytecode to reuse it in ACIR gen but that can be done in a separate PR.

[jfecher]

I don't think this should be an SSA pass - maybe it should be included in Instruction::simplify instead, then we could have a pass just to remove unused functions. The advantage of that being that we can more easily take advantage of SSA optimizations as soon as the call becomes constant. Disadvantage being we'd be checking if it is constant on every pass.

[TomAFrench]

I think putting it in instruction simplification may be a bit OTT for now, maybe within the constant folding pass would be a good middle step.

The reason why I don't think it should be in instruction simplification is that we want to only do codegen once. With this we'd need to pass in this big structure of all of the functions whenever we push in any instruction even if there isn't a function call.

[jfecher]

With this we'd need to pass in this big structure of all of the functions

That's true, we'd need to pass in a reference to &Ssa somehow even though we need mutable access to a function inside it. That or rework globals away from the cranelift model.

Anyways, I'm fine with this as-is as well. Checking for constant calls on every simplification would be slower and we'd still need an extra pass to remove unused functions anyway.

[asterite]

As discussed with Tom on our 1 on 1, I moved the logic to constant folding, then we do another pass of DIE. I still need to continue refactoring a bit because I need to pass a mutable reference in a loop and I'm having some trouble doing that.

[asterite]

Sorry, I removed from the queue because contracts in Aztec-Packages break. I'll soon push a fix for this, though I'd like to refactor a bit more to avoid always having to pass &mut brillig_functions_we_could_not_inline (ideally I'd pass that as a property of BrilligInfo but I'm having a small fight with the borrow checker (understandably because I'm still not super familiar with it)).

[asterite]

I'm not sure how to refactor the code to avoid passing &mut brillig_functions_we_could_not_inline everywhere.

Alternatively, we could have a pass after this one that removes unused brillig functions. It could do that by starting with a set of all brillig functions, and removing from that set whenever we find a call to one of those functions. It would be slightly slower than doing it in one go, but will surely lead to simpler code. What do you think?

I'm also not sure about doing constant folding plus this new thing in one go, it makes the code a bit more complex... though looking at the optimization results it might be worth it.

That said, I'm running time nargo compile --silence-warnings --inliner-aggressiveness 0 in noir-contracts and it's been running since a few minutes ago... it might be that running all of these functions through the VM slows down things a lot.

[asterite]

Actually, it seems it already takes a long time to finish without this PR. I'll push another commit to remove the unused brillig functions as a separate pass in the meantime.

[TomAFrench]

Interesting... Seems like putting this in the constant folding pass allows us to benefit in brillig functions as well. This makes sense as when we're linking brillig functions together we don't do any constant folding between them so this ends up acting as a simple case of that.

[asterite]

I pushed another commit and this is now ready for review.

By the way, the nargo compile above took 29 minutes on my machine, on master. I'll leave it running on this branch to see if it takes much longer... I think previously nargo compile took around 1 minute, not sure if something on our SSA optimizations changed, or it's just that now we are passing --inliner-aggressiveness 0 in bootstrap.

[TomAFrench]

Yeah, nargo compilation in aztec-packages is pretty dire atm, a lot of that time is spent inside of the DIE pass (although I was looking at the protocol circuits rather than the contracts). My aim is to get these two codebases back into one and then we can look into it more deeply.

[TomAFrench]

Alternatively, we could have a pass after this one that removes unused brillig functions. It could do that by starting with a set of all brillig functions, and removing from that set whenever we find a call to one of those functions. It would be slightly slower than doing it in one go, but will surely lead to simpler code. What do you think?

I'm also not sure about doing constant folding plus this new thing in one go, it makes the code a bit more complex... though looking at the optimization results it might be worth it.

I'd say lets do this in iterations. Best to create some new issues for followups than do mega-PR.

[asterite]

nargo compile with this PR took 27 minutes on noir-contracts, compared to 29 minutes on master. Not sure why it's faster, but at least it's not slower.