The last_use optimization is unsound #4685
Labels
bug
Something isn't working
Comments
5 tasks
github-merge-queue bot
pushed a commit
that referenced
this issue
Apr 2, 2024
# Description ## Problem\* Resolves #4685 ## Summary\* Fixes some issues with the last_use analysis and makes it into a dedicated SSA pass (after all other passes, only on 1 block acir functions). ## Additional Context One case I noticed where we don't make array sets mutable currently is in parallel if branches: ```rs if array[0] == 1 { array[1] = 10; } else { array[1] = 20; } ``` Will produce the IR: ```rs v137 = array_get v0, index u64 0 v138 = eq v137, Field 1 enable_side_effects v138 v139 = array_set v0, index u64 1, value Field 10 v140 = not v138 enable_side_effects v140 v141 = array_set mut v0, index u64 1, value Field 20 enable_side_effects u1 1 ``` Note that with this change we can see the second array_set is mutable and not the first. Fixing this isn't in the scope of this PR but this could be a good future optimization. ## 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.
TomAFrench
pushed a commit
that referenced
this issue
Apr 3, 2024
# Description ## Problem\* Resolves #4685 ## Summary\* Fixes some issues with the last_use analysis and makes it into a dedicated SSA pass (after all other passes, only on 1 block acir functions). ## Additional Context One case I noticed where we don't make array sets mutable currently is in parallel if branches: ```rs if array[0] == 1 { array[1] = 10; } else { array[1] = 20; } ``` Will produce the IR: ```rs v137 = array_get v0, index u64 0 v138 = eq v137, Field 1 enable_side_effects v138 v139 = array_set v0, index u64 1, value Field 10 v140 = not v138 enable_side_effects v140 v141 = array_set mut v0, index u64 1, value Field 20 enable_side_effects u1 1 ``` Note that with this change we can see the second array_set is mutable and not the first. Fixing this isn't in the scope of this PR but this could be a good future optimization. ## 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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Aim
The last_use optimization to make array_sets mutable is unsound since it iterates through all functions, accumulating into the same map even though ValueIds and InstructionIds are not unique across functions. This can potentially make some arrays mutable which were not intended to be if they share the same ValueId of an array intended to be made mutable in another function.
Additionally, this should be an SSA pass rather than a separate analysis so it can be debugged more easily.
Expected Behavior
(given above)
Bug
(given above)
To Reproduce
Project Impact
None
Impact Context
No response
Workaround
None
Workaround Description
No response
Additional Context
No response
Installation Method
None
Nargo Version
No response
NoirJS Version
No response
Would you like to submit a PR for this Issue?
None
Support Needs
No response
The text was updated successfully, but these errors were encountered: