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

feat(ssa): Merge slices in if statements with witness conditions #2347

Merged
merged 73 commits into from
Aug 18, 2023

Conversation

vezenovm
Copy link
Contributor

Description

Problem*

Resolves #1889

Summary*

This PR enables merging of slice values in if statements where the condition is a witness. This change was preceded by #2243 as merging of slices occurs in the flattening pass and requires simplification of the slice intrinsics. However, this simplification requires the mem2reg pass, thus mem2reg had to be enabled to work over multiple blocks.

In order to merge slices during flattening, the smaller slice to be merged is filled with placeholder data. This leads to a new challenge though. For example in this snippet:

let slice = [0; 2];
let slice = if x != y {
    slice.push_back(y)
} else {
    slice
};
assert(slice[2] == 0);

We need to prevent the assert from passing in the else case. To prevent accessing elements past the dynamic size of the slice, we now codegen an array length check before every slice ArrayGet. This also required having to codegen the slice size. The structure of slices in SSA has been changed to a tuple (slice length, slice contents), which the length is a field and the contents are an Array in SSA.

This new slice size codegen may also be useful for codegen of dynamic slices as the size of a slice is directly stored and updated during execution of the program.

Documentation

  • This PR requires documentation updates when merged.

    • I will submit a noir-lang/docs PR.
    • I will request for and support Dev Rel's help in documenting this PR.

Additional Context

PR Checklist*

  • I have tested the changes locally.
  • I have formatted the changes with Prettier and/or cargo fmt on default settings.

@vezenovm
Copy link
Contributor Author

This is ready for review again

Copy link
Contributor

@jfecher jfecher left a comment

Choose a reason for hiding this comment

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

LGTM 👍

@vezenovm vezenovm added this pull request to the merge queue Aug 18, 2023
Merged via the queue into master with commit 76f7e43 Aug 18, 2023
16 checks passed
@vezenovm vezenovm deleted the mv/merge-slices-2 branch August 18, 2023 17:35
TomAFrench added a commit that referenced this pull request Aug 19, 2023
* master:
  feat(ssa): Merge slices in if statements with witness conditions (#2347)
  chore: Separate frontend `Visibility` and `Distinctness` from the ABI (#2369)
  feat: add syntax for specifying function type environments (#2357)
  chore: Remove unused `Directive::Log` (#2366)
  chore: clippy fixes (#2365)
  chore: Extract bytecode from artifact files for backend integration test inputs (#2356)
  feat: Add trait definition representation in DefCollector and HIR (#2338)
  chore: Remove unused `Intrinsic::Println` (#2358)
  fix: Remove duplicte `T` in `expected T, found T` error on tuple assignment (#2360)
  chore(brillig): Fix brillig radix instruction return vector size (#2350)
  fix: Show types in error message in same order as in source code (#2353)
TomAFrench added a commit that referenced this pull request Aug 22, 2023
* master: (46 commits)
  chore: Remove `serde` from `noirc_frontend` (#2390)
  chore: allow parenthesizing in two type locations  (#2388)
  chore(ci): automatically delete cache entries associated with closed PRs (#2342)
  feat: Perform more checks for compile-time arithmetic (#2380)
  chore: Remove `noirc_abi::FunctionSignature` and define in terms of HIR (#2372)
  feat: Update to `acvm` 0.22.0 (#2363)
  chore: Update committed ACIR artifacts (#2376)
  feat(ssa): Merge slices in if statements with witness conditions (#2347)
  chore: Separate frontend `Visibility` and `Distinctness` from the ABI (#2369)
  feat: add syntax for specifying function type environments (#2357)
  chore: Remove unused `Directive::Log` (#2366)
  chore: clippy fixes (#2365)
  chore: Extract bytecode from artifact files for backend integration test inputs (#2356)
  feat: Add trait definition representation in DefCollector and HIR (#2338)
  chore: Remove unused `Intrinsic::Println` (#2358)
  fix: Remove duplicte `T` in `expected T, found T` error on tuple assignment (#2360)
  chore(brillig): Fix brillig radix instruction return vector size (#2350)
  fix: Show types in error message in same order as in source code (#2353)
  chore: update noir-source-resolver from `1.1.2` to `^1.1.3` (#2349)
  chore(ci): Avoid writing to cache in workflows triggered by the merge queue (#2341)
  ...
TomAFrench added a commit that referenced this pull request Aug 23, 2023
* master: (34 commits)
  chore: Decouple `noirc_abi` from frontend by introducing `PrintableType` (#2373)
  feat(brillig): Added locations for brillig artifacts (#2415)
  feat: Report compilation warnings before errors (#2398)
  chore: Rework `CrateGraph` to only have one root crate (#2391)
  chore: clippy fix (#2408)
  chore(deps): bump rustls-webpki from 0.101.1 to 0.101.4 (#2404)
  fix(acir): Attach locations to MemoryOps in ACIR (#2389)
  feat: Use equivalence information from equality assertions to simplify circuit (#2378)
  chore: fix body expr span (#2402)
  feat(attributes): enable custom attributes (#2395)
  chore: Remove `serde` from `noirc_frontend` (#2390)
  chore: allow parenthesizing in two type locations  (#2388)
  chore(ci): automatically delete cache entries associated with closed PRs (#2342)
  feat: Perform more checks for compile-time arithmetic (#2380)
  chore: Remove `noirc_abi::FunctionSignature` and define in terms of HIR (#2372)
  feat: Update to `acvm` 0.22.0 (#2363)
  chore: Update committed ACIR artifacts (#2376)
  feat(ssa): Merge slices in if statements with witness conditions (#2347)
  chore: Separate frontend `Visibility` and `Distinctness` from the ABI (#2369)
  feat: add syntax for specifying function type environments (#2357)
  ...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

SSA Refactor: Handle merging slice values
3 participants