Add SSA pass to remove duplicate instructions with no side-effects

[TomAFrench]

Problem

Consider the program below

fn main(x : Field)  {
    assert(x as u32 == x as u32);
}

This program is satisfied for all values of x so we expect zero constraints to be generated. However, this currently compiles to the SSA

acir fn main f1 {
  b0(v0: Field):
    v5 = cast v0 as u32
    v6 = cast v0 as u32
    v7 = eq v5, v6
    constrain v7
    return 
}

v5 and v6 are obviously equal but the compiler doesn't take this into account to simplify the rest of the circuit.

Happy Case

We should have an SSA pass which for each block, checks that for each instruction:

• The instruction has no side-effects.
• The instruction is a duplicate of an instruction earlier in the block.

If both of these are true then we can drop the instruction and just replace its results with the results of the earlier instruction.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

Yes

Support Needs

No response

[TomAFrench]

@jfecher I've got a branch which addresses this by adding an instruction cache to the constant_folding pass. I think that fits quite well into this pass, but would you prefer this to be performed as a separate pass?

[jfecher]

@TomAFrench Ah, I forgot to respond to this issue earlier but I was actually going to suggest the same thing. Feel free to make a PR