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

keccakf1600 instructions aren't being deduplicated as expected #5756

Open
TomAFrench opened this issue Aug 19, 2024 · 1 comment · May be fixed by #6071 or #6496
Open

keccakf1600 instructions aren't being deduplicated as expected #5756

TomAFrench opened this issue Aug 19, 2024 · 1 comment · May be fixed by #6071 or #6496

Comments

@TomAFrench
Copy link
Member

Consider the program

fn main(x: Field, result: [u8; 32]) {
    // We use the `as` keyword here to denote the fact that we want to take just the first byte from the x Field
    // The padding is taken care of by the program
    let digest = std::hash::keccak256([x as u8], 1);
    assert(digest == result);

    //#1399: variable message size
    let message_size = 4;
    let hash_a = std::hash::keccak256([1, 2, 3, 4], message_size);
    let hash_b = std::hash::keccak256([1, 2, 3, 4, 0, 0, 0, 0], message_size);

    assert(hash_a == hash_b);

    let message_size_big = 8;
    let hash_c = std::hash::keccak256([1, 2, 3, 4, 0, 0, 0, 0], message_size_big);

    assert(hash_a != hash_c);

    // DO NOT MERGE: The code below is a pure duplication of what comes above. 
    // This is purely for testing the Brillig opcode report and should not be merged into master.

    // We use the `as` keyword here to denote the fact that we want to take just the first byte from the x Field
    // The padding is taken care of by the program
    let digest = std::hash::keccak256([x as u8], 1);
    assert(digest == result);

    //#1399: variable message size
    let message_size = 4;
    let hash_a = std::hash::keccak256([1, 2, 3, 4], message_size);
    let hash_b = std::hash::keccak256([1, 2, 3, 4, 0, 0, 0, 0], message_size);

    assert(hash_a == hash_b);

    let message_size_big = 8;
    let hash_c = std::hash::keccak256([1, 2, 3, 4, 0, 0, 0, 0], message_size_big);

    assert(hash_a != hash_c);
}

Taken from #5747. We should be able to optimize out the second half of the function body as it's the same as the first but the final SSA we get shows that this isn't happening.

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0(v0: Field, v1: [u8; 32]):
    v3961 = truncate v0 to 8 bits, max_bit_size: 254
    v3986 = add v3961, Field 2⁸
    v3987 = truncate v3986 to 64 bits, max_bit_size: 254
    v3988 = cast v3987 as u64
    v4023 = call keccakf1600([v3988, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 2⁶³, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0])
    v4025 = array_get v4023, index u32 0
    v4026 = cast v4025 as Field
    v4027, v4028 = call to_le_radix(v4026, u32 2⁸, u32 8)
    v4029 = lt u32 0, v4027
    constrain v4029 == u1 1 '"Index out of bounds"'
    v4030 = array_get v4028, index u32 0
    v4031 = lt u32 1, v4027
    constrain v4031 == u1 1 '"Index out of bounds"'
    v4032 = array_get v4028, index u32 1
    v4033 = lt u32 2, v4027
    constrain v4033 == u1 1 '"Index out of bounds"'
    v4034 = array_get v4028, index u32 2
    v4035 = lt u32 3, v4027
    constrain v4035 == u1 1 '"Index out of bounds"'
    v4036 = array_get v4028, index u32 3
    v4037 = lt u32 4, v4027
    constrain v4037 == u1 1 '"Index out of bounds"'
    v4038 = array_get v4028, index u32 4
    v4039 = lt u32 5, v4027
    constrain v4039 == u1 1 '"Index out of bounds"'
    v4040 = array_get v4028, index u32 5
    v4041 = lt u32 6, v4027
    constrain v4041 == u1 1 '"Index out of bounds"'
    v4042 = array_get v4028, index u32 6
    v4043 = lt u32 7, v4027
    constrain v4043 == u1 1 '"Index out of bounds"'
    v4044 = array_get v4028, index u32 7
    v4045 = array_get v4023, index u32 1
    v4046 = cast v4045 as Field
    v4047, v4048 = call to_le_radix(v4046, u32 2⁸, u32 8)
    v4049 = lt u32 0, v4047
    constrain v4049 == u1 1 '"Index out of bounds"'
    v4050 = array_get v4048, index u32 0
    v4051 = lt u32 1, v4047
    constrain v4051 == u1 1 '"Index out of bounds"'
    v4052 = array_get v4048, index u32 1
    v4053 = lt u32 2, v4047
    constrain v4053 == u1 1 '"Index out of bounds"'
    v4054 = array_get v4048, index u32 2
    v4055 = lt u32 3, v4047
    constrain v4055 == u1 1 '"Index out of bounds"'
    v4056 = array_get v4048, index u32 3
    v4057 = lt u32 4, v4047
    constrain v4057 == u1 1 '"Index out of bounds"'
    v4058 = array_get v4048, index u32 4
    v4059 = lt u32 5, v4047
    constrain v4059 == u1 1 '"Index out of bounds"'
    v4060 = array_get v4048, index u32 5
    v4061 = lt u32 6, v4047
    constrain v4061 == u1 1 '"Index out of bounds"'
    v4062 = array_get v4048, index u32 6
    v4063 = lt u32 7, v4047
    constrain v4063 == u1 1 '"Index out of bounds"'
    v4064 = array_get v4048, index u32 7
    v4065 = array_get v4023, index u32 2
    v4066 = cast v4065 as Field
    v4067, v4068 = call to_le_radix(v4066, u32 2⁸, u32 8)
    v4069 = lt u32 0, v4067
    constrain v4069 == u1 1 '"Index out of bounds"'
    v4070 = array_get v4068, index u32 0
    v4071 = lt u32 1, v4067
    constrain v4071 == u1 1 '"Index out of bounds"'
    v4072 = array_get v4068, index u32 1
    v4073 = lt u32 2, v4067
    constrain v4073 == u1 1 '"Index out of bounds"'
    v4074 = array_get v4068, index u32 2
    v4075 = lt u32 3, v4067
    constrain v4075 == u1 1 '"Index out of bounds"'
    v4076 = array_get v4068, index u32 3
    v4077 = lt u32 4, v4067
    constrain v4077 == u1 1 '"Index out of bounds"'
    v4078 = array_get v4068, index u32 4
    v4079 = lt u32 5, v4067
    constrain v4079 == u1 1 '"Index out of bounds"'
    v4080 = array_get v4068, index u32 5
    v4081 = lt u32 6, v4067
    constrain v4081 == u1 1 '"Index out of bounds"'
    v4082 = array_get v4068, index u32 6
    v4083 = lt u32 7, v4067
    constrain v4083 == u1 1 '"Index out of bounds"'
    v4084 = array_get v4068, index u32 7
    v4085 = array_get v4023, index u32 3
    v4086 = cast v4085 as Field
    v4087, v4088 = call to_le_radix(v4086, u32 2⁸, u32 8)
    v4089 = lt u32 0, v4087
    constrain v4089 == u1 1 '"Index out of bounds"'
    v4090 = array_get v4088, index u32 0
    v4091 = lt u32 1, v4087
    constrain v4091 == u1 1 '"Index out of bounds"'
    v4092 = array_get v4088, index u32 1
    v4093 = lt u32 2, v4087
    constrain v4093 == u1 1 '"Index out of bounds"'
    v4094 = array_get v4088, index u32 2
    v4095 = lt u32 3, v4087
    constrain v4095 == u1 1 '"Index out of bounds"'
    v4096 = array_get v4088, index u32 3
    v4097 = lt u32 4, v4087
    constrain v4097 == u1 1 '"Index out of bounds"'
    v4098 = array_get v4088, index u32 4
    v4099 = lt u32 5, v4087
    constrain v4099 == u1 1 '"Index out of bounds"'
    v4100 = array_get v4088, index u32 5
    v4101 = lt u32 6, v4087
    constrain v4101 == u1 1 '"Index out of bounds"'
    v4102 = array_get v4088, index u32 6
    v4103 = lt u32 7, v4087
    constrain v4103 == u1 1 '"Index out of bounds"'
    v4104 = array_get v4088, index u32 7
    v4106 = array_get v1, index u32 0
    v4108 = array_get v1, index u32 1
    v4111 = array_get v1, index u32 2
    v4114 = array_get v1, index u32 3
    v4117 = array_get v1, index u32 4
    v4120 = array_get v1, index u32 5
    v4123 = array_get v1, index u32 6
    v4126 = array_get v1, index u32 7
    v4129 = array_get v1, index u32 8
    v4132 = array_get v1, index u32 9
    v4135 = array_get v1, index u32 10
    v4138 = array_get v1, index u32 11
    v4141 = array_get v1, index u32 12
    v4144 = array_get v1, index u32 13
    v4147 = array_get v1, index u32 14
    v4150 = array_get v1, index u32 15
    v4153 = array_get v1, index u32 2⁴
    v4156 = array_get v1, index u32 17
    v4159 = array_get v1, index u32 18
    v4162 = array_get v1, index u32 19
    v4165 = array_get v1, index u32 20
    v4168 = array_get v1, index u32 21
    v4171 = array_get v1, index u32 22
    v4174 = array_get v1, index u32 23
    v4177 = array_get v1, index u32 24
    v4180 = array_get v1, index u32 25
    v4183 = array_get v1, index u32 26
    v4186 = array_get v1, index u32 27
    v4189 = array_get v1, index u32 28
    v4192 = array_get v1, index u32 29
    v4195 = array_get v1, index u32 30
    v4198 = array_get v1, index u32 31
    constrain v4030 == v4106
    constrain v4032 == v4108
    constrain v4034 == v4111
    constrain v4036 == v4114
    constrain v4038 == v4117
    constrain v4040 == v4120
    constrain v4042 == v4123
    constrain v4044 == v4126
    constrain v4050 == v4129
    constrain v4052 == v4132
    constrain v4054 == v4135
    constrain v4056 == v4138
    constrain v4058 == v4141
    constrain v4060 == v4144
    constrain v4062 == v4147
    constrain v4064 == v4150
    constrain v4070 == v4153
    constrain v4072 == v4156
    constrain v4074 == v4159
    constrain v4076 == v4162
    constrain v4078 == v4165
    constrain v4080 == v4168
    constrain v4082 == v4171
    constrain v4084 == v4174
    constrain v4090 == v4177
    constrain v4092 == v4180
    constrain v4094 == v4183
    constrain v4096 == v4186
    constrain v4098 == v4189
    constrain v4100 == v4192
    constrain v4102 == v4195
    constrain v4104 == v4198
    v4434 = call keccakf1600([v3988, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 2⁶³, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0, u64 0])
    v4436 = array_get v4434, index u32 0
    v4437 = cast v4436 as Field
    v4438, v4439 = call to_le_radix(v4437, u32 2⁸, u32 8)
    v4440 = lt u32 0, v4438
    constrain v4440 == u1 1 '"Index out of bounds"'
    v4441 = array_get v4439, index u32 0
    v4442 = lt u32 1, v4438
    constrain v4442 == u1 1 '"Index out of bounds"'
    v4443 = array_get v4439, index u32 1
    v4444 = lt u32 2, v4438
    constrain v4444 == u1 1 '"Index out of bounds"'
    v4445 = array_get v4439, index u32 2
    v4446 = lt u32 3, v4438
    constrain v4446 == u1 1 '"Index out of bounds"'
    v4447 = array_get v4439, index u32 3
    v4448 = lt u32 4, v4438
    constrain v4448 == u1 1 '"Index out of bounds"'
    v4449 = array_get v4439, index u32 4
    v4450 = lt u32 5, v4438
    constrain v4450 == u1 1 '"Index out of bounds"'
    v4451 = array_get v4439, index u32 5
    v4452 = lt u32 6, v4438
    constrain v4452 == u1 1 '"Index out of bounds"'
    v4453 = array_get v4439, index u32 6
    v4454 = lt u32 7, v4438
    constrain v4454 == u1 1 '"Index out of bounds"'
    v4455 = array_get v4439, index u32 7
    v4456 = array_get v4434, index u32 1
    v4457 = cast v4456 as Field
    v4458, v4459 = call to_le_radix(v4457, u32 2⁸, u32 8)
    v4460 = lt u32 0, v4458
    constrain v4460 == u1 1 '"Index out of bounds"'
    v4461 = array_get v4459, index u32 0
    v4462 = lt u32 1, v4458
    constrain v4462 == u1 1 '"Index out of bounds"'
    v4463 = array_get v4459, index u32 1
    v4464 = lt u32 2, v4458
    constrain v4464 == u1 1 '"Index out of bounds"'
    v4465 = array_get v4459, index u32 2
    v4466 = lt u32 3, v4458
    constrain v4466 == u1 1 '"Index out of bounds"'
    v4467 = array_get v4459, index u32 3
    v4468 = lt u32 4, v4458
    constrain v4468 == u1 1 '"Index out of bounds"'
    v4469 = array_get v4459, index u32 4
    v4470 = lt u32 5, v4458
    constrain v4470 == u1 1 '"Index out of bounds"'
    v4471 = array_get v4459, index u32 5
    v4472 = lt u32 6, v4458
    constrain v4472 == u1 1 '"Index out of bounds"'
    v4473 = array_get v4459, index u32 6
    v4474 = lt u32 7, v4458
    constrain v4474 == u1 1 '"Index out of bounds"'
    v4475 = array_get v4459, index u32 7
    v4476 = array_get v4434, index u32 2
    v4477 = cast v4476 as Field
    v4478, v4479 = call to_le_radix(v4477, u32 2⁸, u32 8)
    v4480 = lt u32 0, v4478
    constrain v4480 == u1 1 '"Index out of bounds"'
    v4481 = array_get v4479, index u32 0
    v4482 = lt u32 1, v4478
    constrain v4482 == u1 1 '"Index out of bounds"'
    v4483 = array_get v4479, index u32 1
    v4484 = lt u32 2, v4478
    constrain v4484 == u1 1 '"Index out of bounds"'
    v4485 = array_get v4479, index u32 2
    v4486 = lt u32 3, v4478
    constrain v4486 == u1 1 '"Index out of bounds"'
    v4487 = array_get v4479, index u32 3
    v4488 = lt u32 4, v4478
    constrain v4488 == u1 1 '"Index out of bounds"'
    v4489 = array_get v4479, index u32 4
    v4490 = lt u32 5, v4478
    constrain v4490 == u1 1 '"Index out of bounds"'
    v4491 = array_get v4479, index u32 5
    v4492 = lt u32 6, v4478
    constrain v4492 == u1 1 '"Index out of bounds"'
    v4493 = array_get v4479, index u32 6
    v4494 = lt u32 7, v4478
    constrain v4494 == u1 1 '"Index out of bounds"'
    v4495 = array_get v4479, index u32 7
    v4496 = array_get v4434, index u32 3
    v4497 = cast v4496 as Field
    v4498, v4499 = call to_le_radix(v4497, u32 2⁸, u32 8)
    v4500 = lt u32 0, v4498
    constrain v4500 == u1 1 '"Index out of bounds"'
    v4501 = array_get v4499, index u32 0
    v4502 = lt u32 1, v4498
    constrain v4502 == u1 1 '"Index out of bounds"'
    v4503 = array_get v4499, index u32 1
    v4504 = lt u32 2, v4498
    constrain v4504 == u1 1 '"Index out of bounds"'
    v4505 = array_get v4499, index u32 2
    v4506 = lt u32 3, v4498
    constrain v4506 == u1 1 '"Index out of bounds"'
    v4507 = array_get v4499, index u32 3
    v4508 = lt u32 4, v4498
    constrain v4508 == u1 1 '"Index out of bounds"'
    v4509 = array_get v4499, index u32 4
    v4510 = lt u32 5, v4498
    constrain v4510 == u1 1 '"Index out of bounds"'
    v4511 = array_get v4499, index u32 5
    v4512 = lt u32 6, v4498
    constrain v4512 == u1 1 '"Index out of bounds"'
    v4513 = array_get v4499, index u32 6
    v4514 = lt u32 7, v4498
    constrain v4514 == u1 1 '"Index out of bounds"'
    v4515 = array_get v4499, index u32 7
    constrain v4441 == v4106
    constrain v4443 == v4108
    constrain v4445 == v4111
    constrain v4447 == v4114
    constrain v4449 == v4117
    constrain v4451 == v4120
    constrain v4453 == v4123
    constrain v4455 == v4126
    constrain v4461 == v4129
    constrain v4463 == v4132
    constrain v4465 == v4135
    constrain v4467 == v4138
    constrain v4469 == v4141
    constrain v4471 == v4144
    constrain v4473 == v4147
    constrain v4475 == v4150
    constrain v4481 == v4153
    constrain v4483 == v4156
    constrain v4485 == v4159
    constrain v4487 == v4162
    constrain v4489 == v4165
    constrain v4491 == v4168
    constrain v4493 == v4171
    constrain v4495 == v4174
    constrain v4501 == v4177
    constrain v4503 == v4180
    constrain v4505 == v4183
    constrain v4507 == v4186
    constrain v4509 == v4189
    constrain v4511 == v4192
    constrain v4513 == v4195
    constrain v4515 == v4198
    return 
}

Note the two keccakf1600 instructions are the same and so the second should be replaced with the results of the first but this isn't currently being done.
@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Aug 19, 2024
TomAFrench added a commit that referenced this issue Aug 20, 2024
@TomAFrench
chore: add regression test for #5756
03f0d6f
@TomAFrench TomAFrench mentioned this issue Aug 20, 2024
Merged
5 tasks
@TomAFrench
Copy link
Member Author

The root cause of this appears to be that when creating two copies of the same constant array, we don't check for any existing copies of it so it is assigned a new ValueId.

github-merge-queue bot pushed a commit that referenced this issue Oct 8, 2024
@TomAFrench
chore: add regression test for #5756 (#5770)
99332f6 
# Description

## Problem\*

Adds regression tests for #5756 

## Summary\*

This PR is some investigation for #5756 as I'm not sure on the
underlying cause as the keccakf1600 instructions _should_
be deduplicated. I'm getting different behaviour in the constant folding
pass test compared to `test_programs` which I'm a little confused by.

Posting this so other people can investigate as well.

## 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.
@TomAFrench TomAFrench linked a pull request Oct 9, 2024 that will close this issue
chore: Add Instruction::MakeArray to SSA #6071
Open
5 tasks
@asterite asterite linked a pull request Nov 11, 2024 that will close this issue
Draft
5 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
Noir
Status: 📋 Backlog
Milestone
No milestone
1 participant
@TomAFrench