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

fix: Respect order in bubble up for redundant asserts #4109

Merged
merged 11 commits into from
Jan 22, 2024
Merged

fix: Respect order in bubble up for redundant asserts #4109

merged 11 commits into from
Jan 22, 2024

Conversation

sirasistant
Copy link
Contributor

Description

Problem*

Bubble up was reordering redundant assertions for the same data. This PR makes it respect the order for those.

Summary*

Additional Context

Documentation*

Check one:

  • No documentation needed.
  • Documentation included in this PR.
  • [Exceptional Case] 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.

@sirasistant sirasistant mentioned this pull request Jan 22, 2024
Merged
@TomAFrench
Copy link
Member

Seems like this is an imperfect solution to this problem. Instruction implements Hash so we could make the hashmap take the actual Instruction as a key which should solve the order dependence of this solution.

@sirasistant
Copy link
Contributor Author

Oh true, it'd invalidate indexes. I'm going to use proper identifiers!

@github-actions GitHub Actions
Copy link
Contributor

github-actions bot commented Jan 22, 2024 •
edited
Loading

Changes to circuit sizes

Generated at commit: 659a9edf47e7f3398e4b168d2c99e3c5726de1b5, compared to commit: 199d129bd7ae02c4336399455ecda69905dfa1bd

🧾 Summary (10% most significant diffs)

Program ACIR opcodes (+/-) % Circuit size (+/-) %
struct_inputs -1 ✅ -3.57% -1 ✅ -0.04%
u128 -2 ✅ -0.25% -17 ✅ -0.37%
Full diff report 👇
Program ACIR opcodes (+/-) % Circuit size (+/-) %
struct_inputs 27 (-1) -3.57% 2,841 (-1) -0.04%
u128 787 (-2) -0.25% 4,588 (-17) -0.37%

TomAFrench
TomAFrench approved these changes Jan 22, 2024
View reviewed changes
Copy link
Member

@TomAFrench TomAFrench left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm good to merge this now as it seems to be robust.

Having a Rust test with a more complex case would be nice but happy for this to go in so we can sync into aztec-packages.

@TomAFrench
Copy link
Member

TomAFrench commented Jan 22, 2024 •
edited
Loading

Actually, I'd like to check the changes in ACIR output for those two tests first. Seems strange this would affect that.

Ah, it's changing

constrain v7 == v4
constrain v4 == Field 1

to

constrain v4 == Field 1
constrain v7 == v4

which is unlocking more ACIRgen optimisations.

@sirasistant
Copy link
Contributor Author

Yes because it also respects user-defined order for assertions that don't refer to any instruction results, which is the case for those I think. It just happens that the writer of that test did it in a way that unlocked some optimizations

@TomAFrench TomAFrench added this pull request to the merge queue Jan 22, 2024
@sirasistant sirasistant removed this pull request from the merge queue due to a manual request Jan 22, 2024
@sirasistant
Copy link
Contributor Author

Added a rust test @TomAFrench If it looks good for you we can readd to the merge queue

@sirasistant @TomAFrench
Update compiler/noirc_evaluator/src/ssa/opt/bubble_up_constrains.rs
c9c5d39 
Co-authored-by: Tom French <15848336+TomAFrench@users.noreply.github.com>
@sirasistant sirasistant enabled auto-merge January 22, 2024 14:36
@sirasistant sirasistant disabled auto-merge January 22, 2024 14:39
@sirasistant sirasistant enabled auto-merge January 22, 2024 14:40
@TomAFrench TomAFrench disabled auto-merge January 22, 2024 14:44
@TomAFrench
Copy link
Member

Removing this from the merge queue as we're putting out a release and I need to make manual changes to the release please PR

@TomAFrench TomAFrench enabled auto-merge January 22, 2024 15:28
@TomAFrench TomAFrench added this pull request to the merge queue Jan 22, 2024
Merged via the queue into master with commit 189aa48 Jan 22, 2024
31 checks passed
@TomAFrench TomAFrench deleted the arv/bubble_up_respect_order branch January 22, 2024 16:07
@kevaundray kevaundray mentioned this pull request Jan 22, 2024
Merged
github-merge-queue bot pushed a commit that referenced this pull request Feb 12, 2024
@kevaundray
chore: Release Noir(0.24.0) (#4113)
df04ce9 
🤖 I have created a release *beep* *boop*
---


<details><summary>0.24.0</summary>

## [0.24.0](v0.23.0...v0.24.0)
(2024-02-12)


### ⚠ BREAKING CHANGES

* rename bigint_neg into bigint_sub
(AztecProtocol/aztec-packages#4420)
* Add expression width into acir
(AztecProtocol/aztec-packages#4014)
* init storage macro
(AztecProtocol/aztec-packages#4200)
* **acir:** Move `is_recursive` flag to be part of the circuit
definition (AztecProtocol/aztec-packages#4221)
* Sync commits from `aztec-packages`
([#4144](#4144))

### Features

* Add bit size to const opcode
(AztecProtocol/aztec-packages#4385)
([158c8ce](158c8ce))
* Add brillig array index check
([#4127](#4127))
([c29f85f](c29f85f))
* Add definitions for From and Into traits to Noir prelude
([#4169](#4169))
([4421ce4](4421ce4))
* Add expression width into acir
(AztecProtocol/aztec-packages#4014)
([158c8ce](158c8ce))
* Add instrumentation for tracking variables in debugging
([#4122](#4122))
([c58d691](c58d691))
* Add option to print monomorphized program
([#4119](#4119))
([80f7e29](80f7e29))
* Add support for overriding expression width
([#4117](#4117))
([c8026d5](c8026d5))
* Add warnings for usage of restricted bit sizes
([#4234](#4234))
([0ffc38b](0ffc38b))
* Allow bitshifts to be represented in SSA for brillig
([#4301](#4301))
([d86ff1a](d86ff1a))
* Allow brillig to read arrays directly from memory
(AztecProtocol/aztec-packages#4460)
([158c8ce](158c8ce))
* Allow globals to refer to any expression
([#4293](#4293))
([479330e](479330e))
* Allow nested arrays and vectors in Brillig foreign calls
(AztecProtocol/aztec-packages#4478)
([158c8ce](158c8ce))
* Allow variables and stack trace inspection in the debugger
([#4184](#4184))
([bf263fc](bf263fc))
* **avm:** Back in avm context with macro - refactor context
(AztecProtocol/aztec-packages#4438)
([158c8ce](158c8ce))
* **aztec-nr:** Initial work for aztec public vm macro
(AztecProtocol/aztec-packages#4400)
([158c8ce](158c8ce))
* Deallocate stack items at the instruction level
([#4339](#4339))
([8f024a8](8f024a8))
* Disable constraint bubbling pass
([#4131](#4131))
([9ba2de6](9ba2de6))
* Disable unused variable checks on low-level and oracle functions
([#4179](#4179))
([8f70e57](8f70e57))
* Evaluation of dynamic assert messages
([#4101](#4101))
([c284e01](c284e01))
* Improve Error Handling for Cargo in Bootstrap Script
([#4211](#4211))
([3a90849](3a90849))
* Init storage macro
(AztecProtocol/aztec-packages#4200)
([158c8ce](158c8ce))
* **lsp:** Goto type reference for Struct
([#4091](#4091))
([d56cac2](d56cac2))
* Move bounded_vec into the noir stdlib
([#4197](#4197))
([c50621f](c50621f))
* Multiply first to allow more ACIR gen optimizations
([#4201](#4201))
([882639d](882639d))
* Option expect method
([#4219](#4219))
([8e042f2](8e042f2))
* Perform constraints on uncasted values if they are the same type
([#4303](#4303))
([816fa85](816fa85))
* Remove predicate from `sort` intrinsic function
([#4228](#4228))
([d646243](d646243))
* Remove replacement of boolean range opcodes with `AssertZero` opcodes
([#4107](#4107))
([dac0e87](dac0e87))
* Replace bitwise ANDs used for truncation with `Instruction::Truncate`
([#4327](#4327))
([eb67ff6](eb67ff6))
* Replace modulo operations with truncations where possible
([#4329](#4329))
([70f2435](70f2435))
* Separate compilation and expression narrowing in `nargo` interface
([#4100](#4100))
([62a4e37](62a4e37))
* Simplify all unsigned constant NOT instructions
([#4230](#4230))
([fab4a6e](fab4a6e))
* Sync commits from `aztec-packages`
([#4144](#4144))
([0205d3b](0205d3b))
* Use constraint information to perform constant folding
([#4060](#4060))
([9a4bf16](9a4bf16))


### Bug Fixes

* Accurate tracking of slice capacities across blocks
([#4240](#4240))
([7420dbb](7420dbb))
* Allow function calls in global definitions
([#4320](#4320))
([0dc205c](0dc205c))
* Allow performing bitwise NOT on unsigned integers
([#4229](#4229))
([b3ddf10](b3ddf10))
* Apply generic arguments from trait constraints before instantiating
identifiers ([#4121](#4121))
([eb6fc0f](eb6fc0f))
* Apply range constraints to return values from unconstrained functions
([#4217](#4217))
([3af2a89](3af2a89))
* Apply trait constraints from method calls
([#4152](#4152))
([68c5486](68c5486))
* Better errors for missing `fn` keyword
([#4154](#4154))
([057c208](057c208))
* Check for tests in all packages before failing due to an unsatisfied
test filter ([#4114](#4114))
([1107373](1107373))
* Clean error when attemping to return a slice from Brillig to ACIR
([#4280](#4280))
([bcad4ec](bcad4ec))
* Correct result when assigning shared arrays in unconstrained code
([#4210](#4210))
([bdd8a96](bdd8a96))
* **docs:** Codegen docs before cutting a new version
([#4183](#4183))
([2914310](2914310))
* Ensure that destination register is allocated when moving between
registers in brillig gen
([#4316](#4316))
([ca0a56e](ca0a56e))
* Ensure that unconstrained entrypoint functions don't generate
constraints ([#4292](#4292))
([fae4ead](fae4ead))
* From field with constant values
([#4226](#4226))
([593916b](593916b))
* **lsp:** Crash when file not in workspace
([#4146](#4146))
([cf7130f](cf7130f))
* **lsp:** Replace panics with errors
([#4209](#4209))
([26e9618](26e9618))
* Maintain correct type when simplifying `x ^ x`
([#4082](#4082))
([9d83c2b](9d83c2b))
* Message formatting for assert statement
([#4323](#4323))
([3972ead](3972ead))
* Prevent debugger crashing on circuits with no opcodes
([#4283](#4283))
([2e32845](2e32845))
* Prevent declarations of blackbox functions outside of the stdlib
([#4177](#4177))
([9fb6b09](9fb6b09))
* Remove panic from `init_log_level` in `acvm_js`
([#4195](#4195))
([2e26530](2e26530))
* Respect order in bubble up for redundant asserts
([#4109](#4109))
([189aa48](189aa48))
* Revert "correct result when assigning shared arrays" and added
regression test ([#4333](#4333))
([05e78b3](05e78b3))
* Save the data bus to the current function before generating others
([#4047](#4047))
([0a5bd4f](0a5bd4f))
* Simplify constant assert messages into `ConstrainError::Static`
([#4287](#4287))
([fd15052](fd15052))
* Ssa typing for array & slice indexes
([#4278](#4278))
([4074bab](4074bab))
* Ssa typing for assign_lvalue_index
([#4289](#4289))
([37f149c](37f149c))
* SSA typing for right shifts
([#4302](#4302))
([41ee1aa](41ee1aa))
* Ssa typing of make_offset
([#4277](#4277))
([e4378ee](e4378ee))
* Track graphs of item dependencies to find dependency cycles
([#4266](#4266))
([61eabf1](61eabf1))
* Type check ACIR mutable reference passed to brillig
([#4281](#4281))
([7e139de](7e139de))
* Update array method type signatures in the docs
([#4178](#4178))
([7c0a955](7c0a955))
* Zero out input to `to_radix` calls if inactive
([#4116](#4116))
([3f5bad3](3f5bad3))


### Miscellaneous Chores

* **acir:** Move `is_recursive` flag to be part of the circuit
definition (AztecProtocol/aztec-packages#4221)
([158c8ce](158c8ce))
* Rename bigint_neg into bigint_sub
(AztecProtocol/aztec-packages#4420)
([158c8ce](158c8ce))
</details>

<details><summary>0.40.0</summary>

## [0.40.0](v0.39.0...v0.40.0)
(2024-02-12)


### ⚠ BREAKING CHANGES

* rename bigint_neg into bigint_sub
(AztecProtocol/aztec-packages#4420)
* Add expression width into acir
(AztecProtocol/aztec-packages#4014)
* init storage macro
(AztecProtocol/aztec-packages#4200)
* **acir:** Move `is_recursive` flag to be part of the circuit
definition (AztecProtocol/aztec-packages#4221)
* Sync commits from `aztec-packages`
([#4144](#4144))
* Breaking changes from aztec-packages
([#3955](#3955))
* Rename Arithmetic opcode to AssertZero
([#3840](#3840))
* Remove unused methods on ACIR opcodes
([#3841](#3841))
* Remove partial backend feature
([#3805](#3805))

### Features

* Add bit size to const opcode
(AztecProtocol/aztec-packages#4385)
([158c8ce](158c8ce))
* Add expression width into acir
(AztecProtocol/aztec-packages#4014)
([158c8ce](158c8ce))
* Add instrumentation for tracking variables in debugging
([#4122](#4122))
([c58d691](c58d691))
* Add support for overriding expression width
([#4117](#4117))
([c8026d5](c8026d5))
* Allow brillig to read arrays directly from memory
(AztecProtocol/aztec-packages#4460)
([158c8ce](158c8ce))
* Allow nested arrays and vectors in Brillig foreign calls
(AztecProtocol/aztec-packages#4478)
([158c8ce](158c8ce))
* Allow variables and stack trace inspection in the debugger
([#4184](#4184))
([bf263fc](bf263fc))
* **avm:** Back in avm context with macro - refactor context
(AztecProtocol/aztec-packages#4438)
([158c8ce](158c8ce))
* **aztec-nr:** Initial work for aztec public vm macro
(AztecProtocol/aztec-packages#4400)
([158c8ce](158c8ce))
* Aztec-packages
([#3754](#3754))
([c043265](c043265))
* Breaking changes from aztec-packages
([#3955](#3955))
([5be049e](5be049e))
* Evaluation of dynamic assert messages
([#4101](#4101))
([c284e01](c284e01))
* Init storage macro
(AztecProtocol/aztec-packages#4200)
([158c8ce](158c8ce))
* Remove range constraints from witnesses which are constrained to be
constants ([#3928](#3928))
([afe9c7a](afe9c7a))
* Remove replacement of boolean range opcodes with `AssertZero` opcodes
([#4107](#4107))
([dac0e87](dac0e87))
* Speed up transformation of debug messages
([#3815](#3815))
([2a8af1e](2a8af1e))
* Sync `aztec-packages`
([#4011](#4011))
([fee2452](fee2452))
* Sync commits from `aztec-packages`
([#4068](#4068))
([7a8f3a3](7a8f3a3))
* Sync commits from `aztec-packages`
([#4144](#4144))
([0205d3b](0205d3b))


### Bug Fixes

* Deserialize odd length hex literals
([#3747](#3747))
([4000fb2](4000fb2))
* Remove panic from `init_log_level` in `acvm_js`
([#4195](#4195))
([2e26530](2e26530))
* Return error rather instead of panicking on invalid circuit
([#3976](#3976))
([67201bf](67201bf))


### Miscellaneous Chores

* **acir:** Move `is_recursive` flag to be part of the circuit
definition (AztecProtocol/aztec-packages#4221)
([158c8ce](158c8ce))
* Remove partial backend feature
([#3805](#3805))
([0383100](0383100))
* Remove unused methods on ACIR opcodes
([#3841](#3841))
([9e5d0e8](9e5d0e8))
* Rename Arithmetic opcode to AssertZero
([#3840](#3840))
([836f171](836f171))
* Rename bigint_neg into bigint_sub
(AztecProtocol/aztec-packages#4420)
([158c8ce](158c8ce))
</details>

---
This PR was generated with [Release
Please](https://github.com/googleapis/release-please). See
[documentation](https://github.com/googleapis/release-please#release-please).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@TomAFrench TomAFrench TomAFrench approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@sirasistant @TomAFrench