Consider adding a no-op instruction to SSA

[jfecher]

Problem

Certain passes like resolve_is_unconstrained go through the ssa to handle only a few instructions (in this case only vN = call is_unconstrained()) but don't have a good way to remove these instructions without re-inserting every instruction into the block as they go (and choosing not to re-insert these handled instructions) or iterating through the block again afterward and retaining only the non-handled instructions.

Happy Case

We can consider adding an Instruction::Nop { result_types } instruction which conceptually "returns" value(s) of any type but in practice will always be removed from the program or skipped over in acir-gen.

This Nop instruction can be used to replace instructions like call is_unconstrained() with so that they will later automatically be removed by calling Instruction::Nop { ... }.simplify() which will always return SimplifyResult::Remove.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

None

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[aakoshh]

Certain passes ... don't have a good way to remove these instructions without re-inserting every instruction ... or ... retaining only the non-handled instructions.

Just looked at resolve_is_unconstrainted at it's doing neither re-insertion of all instructions nor retaining them per-se, rather, it disconnects the results of the call from their original return value and assumes the DIE pass will remove the now-unused call. Does that imply that in this case there is a way, but it's not a good way?

To make sure I understand correctly, what you're suggesting is not only to replace the original result with a constant, but to replace the call instruction itself with a different Nop instruction in-place, to avoid having to shift the instruction vector in the block, and then, similar to how resolve_is_unconstrained relies on DIE removing unused instructions, that there will be some other pass that will actually re-insert all instructions, while calling simplify.

IIUC the DIE pass would not eliminate Nop because it still has return values, unless those are similarly disconnected from the originals. If I just return None from simplify, wouldn't that leave the original result IDs unassigned and somehow invalid?

[TomAFrench]

The general idea is this no-op instruction is a way that we can tell compiler that we don't care about the results. The compiler can then whenever it starts reinserting instructions ignore this instruction and so we automatically filter them out without needing a whole pass devoted to that.

The current situation where the instructions persist until die is a method but not ideal as we have to keep these instructions through all the other SSA passes

[TomAFrench]

What you say in your comment is correct. We would want the diepass to assert that any noop instructions are used however - it would be a compiler bug if this instruction had its results used by other instructions.

[aakoshh]

... assert that any noop instructions are used however - it would be a compiler bug if this instruction had its results used ...

You mean assert that they are not used?

[TomAFrench]

Ah yeah, typo there. "are not used" is correct.

[jfecher]

Tom is right, but I thought I'd add my own clarifications:

Just looked at resolve_is_unconstrainted at it's doing neither re-insertion of all instructions nor retaining them per-se, rather, it disconnects the results of the call from their original return value and assumes the DIE pass will remove the now-unused call. Does that imply that in this case there is a way, but it's not a good way?

I originally made this issue while working on the remove value ids PR in which I had to rewrite the resolve_is_unconstrained pass so that it didn't need to call this replace results method which was no longer possible in this PR. I'd still like to remove replace results because I don't think it should be needed if we're already calling set_value_from_id on the results, and I think adding a Nop instruction could be one way to do it.

I mentioned a Nop instruction returning possibly any dummy values but maybe what we'd want instead is for the instruction to always return nothing, since if you insert a Nop you should always be relying on the return values being mapped away already. This'd provide us a bit greater guarantee that these return values which should be removed aren't sticking around I think. resolve_is_unconstrained also isn't the only PR which has this "touch only a few things, then call .retain() on the instructions vec afterward" pattern. IIRC at least mem2reg does it as well with removing unneeded stores.

These Nop instructions would be expected to be removed automatically in a few cases:

• Calling .simplify() on them will always remove them. So any pass which re-inserts instructions like unrolling, constant folding, etc would remove them.
• They have no return values and aren't side-effectful so DIE will always remove them
• Failing all the above (e.g. if they're inserted by the last SSA pass that is run), acir-gen and brillig can simply ignore them since they have no results.