Instruction::has_side_effects and Instrinsic::has_side_effects are not accurate.

[TomAFrench]

There's a number of Instructions and Intrinsics which use the side_effects_enabled_var variables in ACIR gen. This has a couple of knock-on-effects:

• We perform dead instruction elimination were we (maybe?) shouldn't.
  • e.g. We can perform array accesses past the end of the array as long as we don't use the read value.
• It makes it harder to implement SSA passes such as in feat: add remove_enable_side_effects SSA pass #4224
  • We can no longer easily determine whether a particular Instruction::EnableSideEffects any of the following instructions before we hit the next Instruction::EnableSideEffects.

The list that comes to mind of instructions/intrinsics which should

• ArrayGet/ArraySet

  • noir/compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs

    Lines 756 to 757 in 0ffc38b

    	let predicate_index =
    	self.acir_context.mul_var(index_var, self.current_side_effects_enabled_var)?;

• Anything that uses get_flattened_index
  • SliceInsert

    • noir/compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs

      Line 1849 in 0ffc38b

      self.get_flattened_index(&slice_typ, slice_contents, flat_insert_index, dfg)?;

  • SliceRemove

    • noir/compiler/noirc_evaluator/src/ssa/acir_gen/mod.rs

      Line 1989 in 0ffc38b

      self.get_flattened_index(&slice_typ, slice_contents, flat_remove_index, dfg)?;

[jfecher]

I'm still unsure why has_side_effects is inaccurate after reading the description here.

We perform dead instruction elimination were we (maybe?) shouldn't.

I can see the argument for keeping the error in this case but I'm also alright with enabling more optimizations by keeping the behavior as-is. Unlike e.g. printing, retrieving an element from an array is primarily done to get the actual element rather than doing so to perform the bounds check.

It makes it harder to implement SSA passes such as in #4224

I'm not sure what the motivation for a remove_enable_side_effects instruction would be since there's no motivation explained in the PR. From the name I would think it'd have the same behavior as enable_side_effects u1 0. Can you elaborate why we can't determine if an enable side effects instruction enables side effects in the following instructions or not? I could see not knowing because the argument is dependent on a program input, but it sounds like that's not what this was getting at.

[TomAFrench]

Can you elaborate why we can't determine if an enable side effects instruction enables side effects in the following instructions or not? I could see not knowing because the argument is dependent on a program input, but it sounds like that's not what this was getting at.

In this PR I'm attempting to maximise the number of instructions for which side effects are turned on for as this allows us to maximise the usage of constraint information in #4060. I'm then delaying any Instruction::EnableSideEffects instructions so that I insert them immediately before an instruction which uses side_effects_enabled_var. The trouble is that the instructions listed in this issue report that they don't make use of side_effects_enabled_var but then do. I'm then not inserting the Instruction::EnableSideEffects where I should and then we end up performing incorrect reads/writes.

I'm also alright with enabling more optimizations by keeping the behavior as-is. Unlike e.g. printing, retrieving an element from an array is primarily done to get the actual element rather than doing so to perform the bounds check.

Yeah, I get this point of view. It's only really an issue if you start messing about with Instruction::EnableSideEffects, if you leave them where they are then things are fine.

[TomAFrench]

I've done a little thinking on this and perhaps the issue is that we're overloading has_side_effects to mean two things where splitting it would make things clearer? has_side_effects currently implies both that we inject a predicate during acirgen as well as the instruction having side effects which mean it should be kept in the circuit even if the instruction results are unused (except in the cases where it isn't).

Might it be best to split this into requires_acirgen_predicate and can_eliminate_if_unused? We should then consider whether is_pure falls into some combination of these (seems like it's just !requires_acirgen_predicate?)

[jfecher]

@TomAFrench that sounds good to me. I'm all in favor of more specific names and splitting out different use cases from each other if needed.