Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Apply ssa optimizations to brillig functions #2066

Closed
sirasistant opened this issue Jul 27, 2023 · 3 comments · Fixed by #2348
Closed

Apply ssa optimizations to brillig functions #2066

sirasistant opened this issue Jul 27, 2023 · 3 comments · Fixed by #2348
Assignees
Labels
brillig Unconstrained functions / brillig IR enhancement New feature or request

Comments

@sirasistant
Copy link
Contributor

Problem

Right now brillig is generated before any ssa optimizations are applied. We should generate brillig just before ACIR is generated, after all optimization steps are applied.

Happy Case

All optimization steps apply succesfully to ssa containing both brillig and acir functions.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

@sirasistant sirasistant added enhancement New feature or request brillig Unconstrained functions / brillig IR labels Jul 27, 2023
@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Jul 27, 2023
@sirasistant
Copy link
Contributor Author

I think this issue should be implemented in phases:

  • First, do runtime separation, right now if brillig calls an ACIR function it's targeted as is when it's going to be compiled to brillig. We should, after defunctionalization, find out all acir functions reachable by brillig, clone those as brillig and substitute all calls to the brillig versions. That way subsequent optimization steps can be sure that function.runtime() corresponds to the actual compilation target
  • Then move brillig gen after all optimization passes, we should be able to do it without issue after the previous step...
  • Then start modifiying optimizations to be applicable to brillig. For example, Inlining in brillig makes sense, but stopping at recursion boundaries. Or loop unrolling can make sense for a maximum of compile-time known iterations, etc

@vezenovm
Copy link
Contributor

vezenovm commented Aug 8, 2023

A good starting point for this issue would be the runtime separation pass. An example of reachability analysis for Brillig funcs is already performed here: https://github.com/noir-lang/noir/blob/master/crates/noirc_evaluator/src/brillig/mod.rs#L59. These ACIR funcs called from Brillig would then be cloned and replaced with a Brillig runtime.

@kevaundray
Copy link
Contributor

For reference, once this is complete, we should remove the code added in this PR : #2190

@vezenovm vezenovm added P-HIGH and removed P-LOW labels Aug 16, 2023
@kevaundray kevaundray assigned jfecher and unassigned sirasistant Aug 30, 2023
@github-project-automation github-project-automation bot moved this from 📋 Backlog to ✅ Done in Noir Sep 1, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
brillig Unconstrained functions / brillig IR enhancement New feature or request
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

4 participants