feat: RC optimization pass

[jfecher]

Description

Problem*

inc_rc and dec_rc instructions can bloat unconstrained code with unneeded rc changes on otherwise immutable arrays.

Summary*

Adds an optimization pass to remove inc_rc vN .. dec_rc vN pairs as long as there are not array_set instructions in the same function which may mutate an array of the same type.

Additional Context

I thought of tracking all inc and dec instructions in the function originally but eventually limited it to finding just those in the function's entry block and exit block respectively. The later is the only place we currently issue dec_rc instructions anyway. This restriction greatly simplifies the code since we do not have to merge intermediate results across several blocks, nor do we have to handle inc/dec in loops.

This pass applies to both acir and brillig functions since acir functions can still be called in an unconstrained context.

Documentation*

Check one:

• [x] No documentation needed.
• [ ] Documentation included in this PR.
• [ ] [Exceptional Case] 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 and/or cargo fmt on default settings.

[jfecher]

This PR is ready to review, only some docs links are failing

[sirasistant]

Shouldn't possibly mutated also look for arrays sent as parameter to call functions? The nested call might return it aliased even though it's a reference to the same array? :thinking: Then the function might mutate the alias and the pass wouldn't notice it

[jfecher]

@sirasistant In that case, I think the called function will inc and dec the reference count of that array internally still. I'll add a test case for it though.

Edit: Since you mentioned returning it aliased, the returned aliased array will still be of the same type, so mutating that array will mark all arrays of the same type as potentially mutated

[sirasistant]

Ahh true, i missed the part where it did it by type and not by id! Will do a full review now :)

[jfecher]

Looks like the debugger crashes when running the new test. I think I'll have to remove it and file an issue:

The application panicked (crashed).
Message:  expected type with sub-fields, found terminal type: MutableReference { typ: Array { length: Some(3), typ: Field } }
Location: compiler/noirc_frontend/src/monomorphization/debug.rs:199