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

Push array_gets through array_sets if they act on different constant indices. #5767

Closed
TomAFrench opened this issue Aug 20, 2024 · 0 comments · Fixed by #5772
Closed

Push array_gets through array_sets if they act on different constant indices. #5767

TomAFrench opened this issue Aug 20, 2024 · 0 comments · Fixed by #5772
Labels
enhancement New feature or request optimization

Comments

@TomAFrench
Copy link
Member

Looking at the conditional_1 program failure on #5762 I noticed that we're generating SSA with snippets of the form.

 v11060 = array_set mut [v8829, v8910, v8988, v9062, v9142, v9220, v9300, v9376, v9456, v9530, v9610, v9686, v9766, v9842, v9920, v10000, v10076, v10158, v10236, v10310, v10390, v10466, v10544, v10622, v10700, v10778, v10860, v10934, v11014, v11009, v11006, v11003], index u32 2⁵, value v11000
v11061 = array_get v11060, index u32 0
v11063 = array_get v11060, index u32 1
v11065 = array_get v11060, index u32 2
v11067 = array_get v11060, index u32 3
v11093 = array_get v11060, index u32 2⁵
v11099 = array_get v11060, index u32 29
v11104 = array_get v11060, index u32 30
v11109 = array_get v11060, index u32 31

It's clear that v11061 == v8829, etc. as the array_set only affects the index 32. We could then optimize out all of these array_gets using this knowledge.
@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Aug 20, 2024
@TomAFrench TomAFrench changed the title Push array_gets through array_sets if they act one different constant indices. Push array_gets through array_sets if they act on different constant indices. Aug 20, 2024
@TomAFrench TomAFrench added enhancement New feature or request optimization labels Aug 20, 2024
@jfecher jfecher mentioned this issue Aug 20, 2024
Merged
5 tasks
github-merge-queue bot pushed a commit that referenced this issue Aug 20, 2024
@jfecher @TomAFrench
feat(optimization): Follow past array_sets when optimizing `array_g…
090501d 
…et`s (#5772)

# Description

## Problem\*

Resolves #5767

## Summary\*

Instead of checking if an array_get is from a constant array, we can
follow array_sets to find a previous constant array. If the index was
ever unknown we fail to optimize. If the index is known but changed by
an array set we fail as well instead of optimizing to the set value.
This is in case the side effect variables are different for the get &
set.

## Additional Context

I set an arbitrary maximum of 5 array_sets to check before giving up and
failing to find a constant array.

## 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>
@github-project-automation github-project-automation bot moved this from 📋 Backlog to ✅ Done in Noir Aug 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request optimization
Projects
Noir
Status: ✅ Done
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat(optimization): Follow past array_sets when optimizing array_gets noir-lang/noir
1 participant
@TomAFrench