feat: Avoid incrementing reference counts in some cases

[jfecher]

Description

Problem*

Fixes #6565

Summary*

Avoids incrementing array reference counts in some cases:

• If the parameter is an immutable array (we used to rely on the remove paired rc pass for this case)
• No longer increment rcs when dereferencing lvalues

Additional Context

Since immutable arrays no longer issue rc instructions, the "remove paired rcs" pass is less needed. Now it only really applies when a user passes a mutable array but never mutates it (although it does still apply if that array is only passed to other mutating functions which is useful).

Documentation*

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[github-actions]

Changes to number of Brillig opcodes executed

Generated at commit: 0a4594d9e9db1089dd0ff6d16c84b975032ccd25, compared to commit: 68c32b4ffd9b069fe4b119327dbf4018c17ab9d4

🧾 Summary (10% most significant diffs)

Program	Brillig opcodes (+/-)	%
bench_2_to_17	-226,990 ✅	-26.88%
fold_2_to_17	-431,740 ✅	-27.35%
fold_complex_outputs	-376 ✅	-32.19%
regression_struct_array_conditional	-972 ✅	-37.95%
sha2_byte	-41,325 ✅	-44.18%
array_dynamic_blackbox_input	-29,579 ✅	-59.67%
sha256_brillig_performance_regression	-411,727 ✅	-93.64%

---

Full diff report 👇

Program	Brillig opcodes (+/-)	%
regression_4449	228,505 (+8,680)	+3.95%
conditional_regression_short_circuit	7,684 (+248)	+3.34%
6	7,606 (+245)	+3.33%
reference_only_used_as_alias	200 (+6)	+3.09%
sha256	14,745 (+369)	+2.57%
array_dynamic_nested_blackbox_input	4,753 (+118)	+2.55%
ecdsa_secp256k1	7,202 (+124)	+1.75%
sha256_var_witness_const_regression	7,161 (+121)	+1.72%
slice_loop	974 (+12)	+1.25%
sha256_var_size_regression	17,732 (+121)	+0.69%
sha256_regression	125,986 (+236)	+0.19%
hashmap	57,519 (+96)	+0.17%
slices	3,286 (+3)	+0.09%
ram_blowup_regression	877,404 (-3)	-0.00%
sha256_var_padding_regression	234,827 (-18)	-0.01%
nested_array_dynamic	3,116 (-3)	-0.10%
array_to_slice	1,872 (-3)	-0.16%
strings	1,750 (-3)	-0.17%
regression_capacity_tracker	912 (-3)	-0.33%
conditional_1	6,018 (-26)	-0.43%
brillig_cow	1,147 (-6)	-0.52%
brillig_pedersen	983 (-6)	-0.61%
pedersen_check	983 (-6)	-0.61%
references	305 (-3)	-0.97%
array_dynamic_main_output	296 (-3)	-1.00%
array_if_cond_simple	538 (-6)	-1.10%
databus_two_calldata	449 (-6)	-1.32%
uhashmap	149,814 (-2,203)	-1.45%
eddsa	749,067 (-11,140)	-1.47%
conditional_2	119 (-3)	-2.46%
poseidon_bn254_hash	177,082 (-5,511)	-3.02%
poseidon_bn254_hash_width_3	177,082 (-5,511)	-3.02%
regression_mem_op_predicate	96 (-3)	-3.03%
poseidonsponge_x5_254	196,091 (-6,471)	-3.19%
regression_5252	979,153 (-34,098)	-3.37%
nested_dyn_array_regression_5782	163 (-6)	-3.55%
brillig_cow_regression	583,782 (-21,720)	-3.59%
u128	25,438 (-1,040)	-3.93%
brillig_arrays	139 (-6)	-4.14%
import	54 (-3)	-5.26%
brillig_constant_reference_regression	99 (-6)	-5.71%
higher_order_functions	1,305 (-109)	-7.71%
regression	2,851 (-266)	-8.53%
keccak256	36,255 (-3,508)	-8.82%
7_function	2,587 (-262)	-9.20%
array_dynamic	498 (-59)	-10.59%
slice_dynamic_index	4,681 (-786)	-14.38%
brillig_rc_regression_6123	300 (-58)	-16.20%
poseidon2	731 (-142)	-16.27%
fold_numeric_generic_poseidon	5,364 (-1,300)	-19.51%
no_predicates_numeric_generic_poseidon	5,364 (-1,300)	-19.51%
array_sort	586 (-156)	-21.02%
bench_2_to_17	617,618 (-226,990)	-26.88%
fold_2_to_17	1,146,735 (-431,740)	-27.35%
fold_complex_outputs	792 (-376)	-32.19%
regression_struct_array_conditional	1,589 (-972)	-37.95%
sha2_byte	52,211 (-41,325)	-44.18%
array_dynamic_blackbox_input	19,990 (-29,579)	-59.67%
sha256_brillig_performance_regression	27,956 (-411,727)	-93.64%

[github-actions]

Changes to Brillig bytecode sizes

Generated at commit: 0a4594d9e9db1089dd0ff6d16c84b975032ccd25, compared to commit: 68c32b4ffd9b069fe4b119327dbf4018c17ab9d4

🧾 Summary (10% most significant diffs)

Program	Brillig opcodes (+/-)	%
keccak256	+1,547 ❌	+70.16%
higher_order_functions	+46 ❌	+6.71%
7_function	-30 ✅	-4.80%
brillig_arrays	-6 ✅	-5.00%
regression_mem_op_predicate	-6 ✅	-5.22%
brillig_constant_reference_regression	-6 ✅	-5.71%
fold_complex_outputs	-36 ✅	-6.64%

---

Full diff report 👇

Program	Brillig opcodes (+/-)	%
keccak256	3,752 (+1,547)	+70.16%
higher_order_functions	732 (+46)	+6.71%
reference_only_used_as_alias	179 (+6)	+3.47%
slice_loop	285 (+6)	+2.15%
bigint	1,996 (+3)	+0.15%
slices	2,037 (+3)	+0.15%
u128	2,796 (-3)	-0.11%
nested_array_dynamic	1,992 (-3)	-0.15%
sha256_regression	6,820 (-18)	-0.26%
ecdsa_secp256k1	979 (-3)	-0.31%
ram_blowup_regression	960 (-3)	-0.31%
strings	897 (-3)	-0.33%
sha256_var_size_regression	1,791 (-6)	-0.33%
regression_4449	820 (-3)	-0.36%
sha256_var_padding_regression	4,909 (-18)	-0.37%
array_to_slice	818 (-3)	-0.37%
conditional_regression_short_circuit	1,355 (-6)	-0.44%
sha256_var_witness_const_regression	1,319 (-6)	-0.45%
sha256	2,467 (-12)	-0.48%
6	1,282 (-9)	-0.70%
array_dynamic_blackbox_input	1,027 (-9)	-0.87%
brillig_cow_regression	2,249 (-21)	-0.93%
array_dynamic_nested_blackbox_input	950 (-9)	-0.94%
eddsa	10,687 (-108)	-1.00%
pedersen_check	578 (-6)	-1.03%
brillig_pedersen	578 (-6)	-1.03%
sha256_brillig_performance_regression	3,329 (-36)	-1.07%
poseidon_bn254_hash	5,448 (-66)	-1.20%
poseidon_bn254_hash_width_3	5,448 (-66)	-1.20%
uhashmap	13,532 (-165)	-1.20%
hashmap	20,529 (-276)	-1.33%
references	203 (-3)	-1.46%
brillig_cow	380 (-6)	-1.55%
poseidonsponge_x5_254	4,269 (-69)	-1.59%
regression	732 (-12)	-1.61%
brillig_rc_regression_6123	179 (-3)	-1.65%
regression_5252	4,657 (-81)	-1.71%
conditional_1	1,271 (-24)	-1.85%
array_sort	304 (-6)	-1.94%
sha2_byte	2,890 (-60)	-2.03%
regression_struct_array_conditional	535 (-12)	-2.19%
regression_capacity_tracker	238 (-6)	-2.46%
conditional_2	116 (-3)	-2.52%
databus_two_calldata	217 (-6)	-2.69%
array_dynamic_main_output	91 (-3)	-3.19%
nested_dyn_array_regression_5782	167 (-6)	-3.47%
array_dynamic	319 (-12)	-3.63%
fold_numeric_generic_poseidon	794 (-31)	-3.76%
no_predicates_numeric_generic_poseidon	794 (-31)	-3.76%
poseidon2	363 (-15)	-3.97%
bench_2_to_17	356 (-15)	-4.04%
array_if_cond_simple	132 (-6)	-4.35%
fold_2_to_17	617 (-30)	-4.64%
slice_dynamic_index	2,640 (-132)	-4.76%
import	60 (-3)	-4.76%
7_function	595 (-30)	-4.80%
brillig_arrays	114 (-6)	-5.00%
regression_mem_op_predicate	109 (-6)	-5.22%
brillig_constant_reference_regression	99 (-6)	-5.71%
fold_complex_outputs	506 (-36)	-6.64%

[jfecher]

keccak256 +1,547 ❌ +70.16%

Hmm, not sure what's going on with this test. I haven't added any new instructions, just removed some existing inc_rcs

[jfecher]

sha256_brillig_performance_regression -411,727 ✅ -93.64%

Looks like this fixes #6565

[michaeljklein]

Now it only really applies when a user passes an immutable array but never mutates it.

You mean when a user passes a mutable array, but never mutates it?

[asterite]

Is there a small SSA test that can show what this change does?

[jfecher]

@asterite No, this is just a small ssa-gen change to not issue ref count instructions for immutable array parameters like foo: [Field; 3] (but still for mut foo: [Field; 3] and foo: &mut [Field; 3]), and also avoid issuing them within lvalues.
I don't think it's major enough to require a test for it (aside ensuring it works for our existing test_programs), but if we wanted a test we can't use the existing SSA test infrastructure since it's a ssa-gen change which needs to go from monomorphized ast -> SSA instead of SSA -> SSA.

[vezenovm]

Just noting this PR also reduces the number of opcodes executed from array copies in the blob binary. Went from ~171 million samples to ~71 million samples from array copies after this PR (the total samples when compiled with the current master is ~760 million).