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.

Sign up for GitHub

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

Jump to bottom

Consider introducing BrilligFunctionPointer into ACIR #3907

Closed
kevaundray opened this issue Dec 21, 2023 · 6 comments · Fixed by AztecProtocol/aztec-packages#5737
Closed

Consider introducing BrilligFunctionPointer into ACIR #3907

kevaundray opened this issue Dec 21, 2023 · 6 comments · Fixed by AztecProtocol/aztec-packages#5737
Assignees
@vezenovm
Labels
enhancement New feature or request

Comments

@kevaundray
Copy link
Contributor

Problem

Currently we inline the bytecode into ACIR for each ACIR call.

A brillig opcode in ACIR will therefore contain the bytecode to be executed. This is a problem because if the same Brillig function is called N times, we will be duplicating the bytecode for that function N times.

Happy Case

We can store the bytecode in an ordered set and replace the bytecode for Brillig in the ACIR opcode, with a pointer to that ordered set.

If the same function is called multiple times, we only duplicate the pointer/index to the ordered set.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response
@kevaundray kevaundray added enhancement New feature or request P-MEDIUM labels Dec 21, 2023
@kevaundray
Copy link
Contributor Author

When we want to have ACIR functions, this might be a good way to do it too instead of inlining the ACIR into ACIR

@TomAFrench
Copy link
Member

Duplicate of #2936

@TomAFrench TomAFrench marked this as a duplicate of #2936 Dec 22, 2023
@TomAFrench TomAFrench mentioned this issue Jan 10, 2024
Closed
5 tasks
@kevaundray kevaundray modified the milestones: 1.1, 0.24.0 Jan 15, 2024
@TomAFrench TomAFrench mentioned this issue Jan 23, 2024
Closed
5 tasks
@Savio-Sou Savio-Sou removed this from the 0.24 milestone Feb 9, 2024
@vezenovm
Copy link
Contributor

vezenovm commented Mar 4, 2024

This feels like something that can be handled with this general solution: #4428

@TomAFrench
Copy link
Member

Agreed, I'm going to assign this to you and we can close it at the same time as when we handle the folding case.

@TomAFrench
Copy link
Member

It just occurred to me that we should potentially still keep brillig and ACIR separated to resolve this rather than just treating them as circuits with a single Brillig opcode in them. Reason for this being that then have the backend completely ignore the brillig entirely and treat it as a binary blob as it doesn't need to understand it at all which should help speed up deserialization on the backend (or make it easier to strip them out before sending it to the backend).

@vezenovm
Copy link
Contributor

vezenovm commented Apr 8, 2024

It just occurred to me that we should potentially still keep brillig and ACIR separated

Yup agreed

@TomAFrench TomAFrench mentioned this issue Apr 9, 2024
Closed
This was referenced Apr 11, 2024
Merged
Merged
vezenovm added a commit to AztecProtocol/aztec-packages that referenced this issue Apr 16, 2024
@vezenovm @TomAFrench
feat(acir)!: BrilligCall opcode (#5709)
f06f64c 
This starts work towards noir-lang/noir#3907
but is only the breaking serialization change.

Codegen and evaluation will come in a follow-up. This PR is purely
additive and does not remove the current way we do Brillig gen during
ACIR gen. Codegen for normal Brillig functions is working in my
follow-up, however, removing the existing Brillig opcode will most
likely have to come once we settle on how to [handle the brillig std
lib](noir-lang/acvm#471) as we are currently
generating code such as calculating a quotient during ACIR gen.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
AztecBot added a commit that referenced this issue Apr 16, 2024
@AztecBot @TomAFrench
feat(acir)!: BrilligCall opcode (AztecProtocol/aztec-packages#5709)
8222fc8 
This starts work towards #3907
but is only the breaking serialization change.

Codegen and evaluation will come in a follow-up. This PR is purely
additive and does not remove the current way we do Brillig gen during
ACIR gen. Codegen for normal Brillig functions is working in my
follow-up, however, removing the existing Brillig opcode will most
likely have to come once we settle on how to [handle the brillig std
lib](noir-lang/acvm#471) as we are currently
generating code such as calculating a quotient during ACIR gen.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
AztecBot pushed a commit to AztecProtocol/barretenberg that referenced this issue Apr 16, 2024
@vezenovm @TomAFrench @AztecBot
feat(acir)!: BrilligCall opcode (#5709)
b2e6d24 
This starts work towards noir-lang/noir#3907
but is only the breaking serialization change.

Codegen and evaluation will come in a follow-up. This PR is purely
additive and does not remove the current way we do Brillig gen during
ACIR gen. Codegen for normal Brillig functions is working in my
follow-up, however, removing the existing Brillig opcode will most
likely have to come once we settle on how to [handle the brillig std
lib](noir-lang/acvm#471) as we are currently
generating code such as calculating a quotient during ACIR gen.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
vezenovm added a commit to AztecProtocol/aztec-packages that referenced this issue Apr 16, 2024
@vezenovm @TomAFrench @jfecher
feat: Brillig pointer codegen and execution (#5737)
a7b9d20 
Resolves noir-lang/noir#3907

This PR builds upon
#5709.

These changes do not yet include a Brillig stdlib and removal of the
`Brillig` opcode itself. The generated stdlib Brillig (such as for
quotient) is not created in the same manner as other Brillig calls which
are generated during SSA. I have decided to leave this for another
follow-up where we can actually remove `Brillig`.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
Co-authored-by: jfecher <jfecher11@gmail.com>
AztecBot added a commit that referenced this issue Apr 16, 2024
@AztecBot @TomAFrench @jfecher
feat: Brillig pointer codegen and execution (AztecProtocol/aztec-pack…
b3849c9 
…ages#5737)

Resolves #3907

This PR builds upon
AztecProtocol/aztec-packages#5709.

These changes do not yet include a Brillig stdlib and removal of the
`Brillig` opcode itself. The generated stdlib Brillig (such as for
quotient) is not created in the same manner as other Brillig calls which
are generated during SSA. I have decided to leave this for another
follow-up where we can actually remove `Brillig`.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
Co-authored-by: jfecher <jfecher11@gmail.com>
This was referenced Apr 16, 2024
Closed
Merged
github-merge-queue bot pushed a commit that referenced this issue Apr 22, 2024
@vezenovm @TomAFrench @jfecher
feat(acir_gen): Brillig stdlib (#4848)
0c8175c 
# Description

## Problem\*

Expands usage of #3907 to our
Brillig directives.

## Summary\*

The Brillig stdlib differs slightly from normal Brillig functions calls.
We can insert the generated Brillig bytecode at any point during ACIR
gen. This includes within the `GeneratedAcir` struct itself. We have a
few requirements on what we want to achieve:
- We do want to have to thread the ACIR gen `SharedContext` that is used
for generating normal Brillig function pointers to the `GeneratedAcir`.
Why would we want a reference to code generation inside of our Generated
ACIR structure (we don't)?
- We want to maintain one Brillig stdlib for an entire program. We do
not want to change the `BrilligCall` opcode so we need them to be a part
of the main list of `unconstrained_functions` in a program.
- Function IDs reference a flat list, so reserving some number of slots
would be wasteful if the program does not eventually use a Brillig
stdlib function in that slot.

So instead we maintain a map as part of the `GeneratedAcir` that notes
when we at which opcode location we inserted a call to a
`BrilligStdlibFunc`. The ID at this point will just be `0`. After
finishing ACIR generation for a function, only then do we resolve the
IDs for these `BrilligCall` opcodes.

## Additional Context



## Documentation\*

Check one:
- [X] No documentation needed.
- [ ] Documentation included in this PR.
- [ ] **[For Experimental Features]** Documentation to be submitted in a
separate PR.

# PR Checklist\*

- [X] I have tested the changes locally.
- [X] I have formatted the changes with [Prettier](https://prettier.io/)
and/or `cargo fmt` on default settings.

---------

Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
Co-authored-by: jfecher <jake@aztecprotocol.com>
Co-authored-by: TomAFrench <tom@tomfren.ch>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@vezenovm vezenovm

Labels
enhancement New feature or request
Projects
Noir
Archived in project
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat: Brillig pointer codegen and execution AztecProtocol/aztec-packages
4 participants
@TomAFrench @kevaundray @vezenovm @Savio-Sou