fix(ssa): Do not replace previously constrained values

[vezenovm]

Description

Problem*

Resolves #2645

Summary*

This PR simply checks whether we have an enable_side_effects instruction before caching an instruction in constant_folding. This makes sure that we only replace previously constrained values that we know do not have possible side effects.

This PR removes the optimization in this PR (#2483). As per the issue, doing this optimization during SSA can cause constant constraints failures before a dynamic constraint check has been executed.

In order to avoid this there are a few options:

1. Do not fail on compile time constraint checks. I lean towards that this is not good as we should be able to tell a user at compile time whether a circuit they wrote is unprovable without them having to execute the program.
2. We can track a replaced constrain statement to see which instruction it was simplified from. If it was modified because of a simplification we don't issue an error during ACIR gen and we wait until execution. This is essentially a more selective version of option 1, and would most likely not be a simple solution for marginal gains.
3. We can remove the constrain cache entirely.

This PR went with option 3 as the optimization looks to have minimal use-cases (if any) that are not handled by simplifications during ACIR gen and ACVM. For the use-case linked in PR #2483, the backend circuit size remains the same with or without the optimization. If I add the following to the linked program above:

    assert(sender_bytes.len() == 32);
    assert(chainId_bytes.len() == 32);
    assert(recipient_bytes.len() == 32);
    assert(version_bytes.len() == 32);
    assert(content_bytes.len() == 32);
    assert(secret_hash_bytes.len() == 32);
    assert(deadline_bytes.len() == 32);
    assert(fee_bytes.len() == 32);

With the constrain cache the number of ACIR opcodes reduces from 3724 to 1036. However, the backend circuit size remains the same in both cases. Having the PR check for enable_side_effects and disabling the constrain cache when it is true was the original workaround. However, other than the linked use-case, any program that has on side effects will most likely disable this constrain cache. The fact that the final circuit size remains the same makes me lean towards removing the cache straight up.

Using the program linked in the issue:
SSA currently:

After Mem2Reg:
acir fn main f0 {
  b0(v0: Field, v1: Field):
    v104 = allocate
    v105 = allocate
    v107 = eq v0, v1
    v108 = not v107
    enable_side_effects v108
    enable_side_effects v107
    enable_side_effects u1 1
    v118 = cast v108 as Field
    v119 = cast v107 as Field
    v120 = mul v118, Field 4
    v121 = mul v119, Field 3
    v122 = add v120, v121
    v123 = cast v108 as Field
    v124 = cast v107 as Field
    v125 = cast v108 as Field
    v126 = cast v107 as Field
    v127 = cast v108 as Field
    v128 = cast v107 as Field
    v129 = mul v127, v1
    v130 = mul v128, v0
    v131 = add v129, v130
    v132 = cast v108 as Field
    v133 = cast v107 as Field
    v134 = mul v132, v0
    constrain v122 == Field 3
    v138 = cast v122 as u64
    v139 = lt Field 3, v138
    constrain v139 == u1 1
    constrain v134 == Field 5
    return 
}

After Constant Folding:
acir fn main f0 {
  b0(v0: Field, v1: Field):
    v141 = allocate
    v142 = allocate
    v143 = eq v0, v1
    v144 = not v143
    enable_side_effects u1 1
    v145 = cast v144 as Field
    v146 = cast v143 as Field
    v147 = mul v145, Field 4
    v148 = mul v146, Field 3
    v149 = add v147, v148
    v150 = mul v145, v1
    v151 = mul v146, v0
    v152 = add v150, v151
    v153 = mul v145, v0
    constrain v149 == Field 3
    constrain u1 0 == u1 1
    constrain v153 == Field 5
    return 
}

You can see that the lines

    v138 = cast v122 as u64
    v139 = lt Field 3, v138

are getting optimized out when they should not be. Because these two lines are replaced with constrain u1 0 == u1 1 we end up with a constant constraint failure that occurs before we can check that constrain v149 == Field 3 is invalid.

SSA after this PR:

After Mem2Reg:
acir fn main f0 {
  b0(v0: Field, v1: Field):
    v104 = allocate
    v105 = allocate
    v107 = eq v0, v1
    v108 = not v107
    enable_side_effects v108
    enable_side_effects v107
    enable_side_effects u1 1
    v118 = cast v108 as Field
    v119 = cast v107 as Field
    v120 = mul v118, Field 4
    v121 = mul v119, Field 3
    v122 = add v120, v121
    v123 = cast v108 as Field
    v124 = cast v107 as Field
    v125 = cast v108 as Field
    v126 = cast v107 as Field
    v127 = cast v108 as Field
    v128 = cast v107 as Field
    v129 = mul v127, v1
    v130 = mul v128, v0
    v131 = add v129, v130
    v132 = cast v108 as Field
    v133 = cast v107 as Field
    v134 = mul v132, v0
    constrain v122 == Field 3
    v138 = cast v122 as u64
    v139 = lt Field 3, v138
    constrain v139 == u1 1
    constrain v134 == Field 5
    return 
}

After Constant Folding:
acir fn main f0 {
  b0(v0: Field, v1: Field):
    v141 = allocate
    v142 = allocate
    v143 = eq v0, v1
    v144 = not v143
    enable_side_effects u1 1
    v145 = cast v144 as Field
    v146 = cast v143 as Field
    v147 = mul v145, Field 4
    v148 = mul v146, Field 3
    v149 = add v147, v148
    v150 = mul v145, v1
    v151 = mul v146, v0
    v152 = add v150, v151
    v153 = mul v145, v0
    constrain v149 == Field 3
    v154 = cast v149 as u64
    v155 = lt Field 3, v154
    constrain v155 == u1 1
    constrain v153 == Field 5
    return 
}

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.

[kevaundray]

Could you resolve the merge conflicts por favor?

[vezenovm]

Conflicts resolved this is ready for review again

[jfecher]

I think this PR is too pessimistic. Since the default value of enable side effects is true, this can effectively disable constant folding for an entire program (after the first if when enable_side_effects is first inserted). I think a better solution would be finding the side-effectful instructions that may differ depending on the status of enable_side_effects and selectively disabling those.

[vezenovm]

Since the default value of enable side effects is true, this can effectively disable constant folding for an entire program

I will take a look at how I can select specific instructions. Although, this PR wouldn't disable constant folding for an entire program, it would just disable usage of the constrain statement cache and replacing those values.

[vezenovm]

I think a better solution would be finding the side-effectful instructions that may differ depending on the status of enable_side_effects and selectively disabling those.

Actually I think because this only disables the constrain cache this PR does do what this says by only disabling folding the dynamic part of a constrain instruction.

[vezenovm]

I have updated this PR to remove the constrain cache inside of constant folding. Reasoning for this can be found in the PR description.