feat: Separate runtimes of SSA functions before inlining

[sirasistant]

Description

Problem*

Resolves #5043

Opcode count of Aztec public functions before => after this change in the inlining strategy

_approve_bridge_and_exit_input_asset_to_L1 on contract Uniswap with size 3788 => 3166
_assert_token_is_same on contract TokenBridge with size 916 => 640
_assert_token_is_same on contract Uniswap with size 1845 => 1546
_borrow on contract Lending with size 10988 => 10152
_call_mint_on_token on contract TokenBridge with size 1427 => 1125
_check_deadline on contract Crowdfunding with size 1015 => 752
_deposit on contract Lending with size 1699 => 1220
_increase_public_balance on contract GasToken with size 1325 => 1103
_increase_public_balance on contract Token with size 1577 => 1201
_increase_public_balance on contract TokenBlacklist with size 1577 => 1201
_reduce_total_supply on contract Token with size 945 => 626
_reduce_total_supply on contract TokenBlacklist with size 945 => 626
_repay on contract Lending with size 6775 => 6284
_withdraw on contract Lending with size 10715 => 9850
add_args_return on contract AvmNestedCallsTest with size 15 => 15
add_args_return on contract AvmTest with size 15 => 15
add_storage_map on contract AvmTest with size 797 => 664
add_to_tally_public on contract EasyPrivateVoting with size 1496 => 1112
add_u128 on contract AvmTest with size 187 => 187
admin on contract Token with size 495 => 348
approve_public_authwit on contract EcdsaAccount with size 977 => 718
approve_public_authwit on contract SchnorrAccount with size 743 => 621
approve_public_authwit on contract SchnorrHardcodedAccount with size 742 => 620
approve_public_authwit on contract SchnorrSingleKeyAccount with size 742 => 620
assert_block_number on contract AppSubscription with size 920 => 669
assert_minter_and_mint on contract Token with size 1434 => 1035
assert_not_expired on contract AppSubscription with size 910 => 658
assert_nullifier_exists on contract AvmTest with size 242 => 156
assert_public_global_vars on contract Test with size 1054 => 679
assert_same on contract AvmNestedCallsTest with size 138 => 138
assert_unsiloed_nullifier_acvm on contract AvmAcvmInteropTest with size 102 => 16
assertion_failure on contract AvmTest with size 166 => 166
avm_to_acvm_call on contract AvmAcvmInteropTest with size 287 => 169
balance_of_public on contract GasToken with size 651 => 612
balance_of_public on contract Token with size 880 => 710
balance_of_public on contract TokenBlacklist with size 880 => 710
borrow_public on contract Lending with size 1193 => 939
broadcast on contract Benchmarking with size 419 => 337
burn_public on contract Token with size 2426 => 1962
burn_public on contract TokenBlacklist with size 3148 => 2468
call_acvm_from_avm on contract AvmAcvmInteropTest with size 574 => 503
call_avm_from_acvm on contract AvmAcvmInteropTest with size 578 => 507
check_balance on contract GasToken with size 856 => 768
check_selector on contract AvmTest with size 463 => 463
claim_public on contract GasToken with size 3963 => 3416
claim_public on contract TokenBridge with size 4176 => 3457
constant_field_acvm on contract AvmAcvmInteropTest with size 13 => 13
constant_field_avm on contract AvmAcvmInteropTest with size 13 => 13
constructor on contract AppSubscription with size 3376 => 1983
constructor on contract Auth with size 1414 => 994
constructor on contract AvmInitializerTest with size 1290 => 908
constructor on contract Claim with size 1700 => 1123
constructor on contract EasyPrivateVoting with size 1454 => 941
constructor on contract FPC with size 1700 => 1123
constructor on contract InclusionProofs with size 1021 => 704
constructor on contract Token with size 2737 => 1961
constructor on contract TokenBlacklist with size 1925 => 1285
constructor on contract TokenBridge with size 1400 => 924
constructor on contract Uniswap with size 1326 => 909
consume_message_from_arbitrary_sender_public on contract Test with size 2203 => 1893
consume_mint_public_message on contract Test with size 2910 => 2600
create_different_nullifier_in_nested_call on contract AvmNestedCallsTest with size 743 => 639
create_l2_to_l1_message_arbitrary_recipient_public on contract Test with size 56 => 12
create_l2_to_l1_message_public on contract Test with size 73 => 29
create_same_nullifier_in_nested_call on contract AvmNestedCallsTest with size 741 => 637
debug_logging on contract AvmTest with size 725 => 402
deposit_public on contract Lending with size 2286 => 1846
dummy_public_call on contract Test with size 354 => 284
emit_nullifier_and_check on contract AvmTest with size 436 => 314
emit_nullifier_public on contract Test with size 47 => 11
emit_unencrypted on contract Test with size 54 => 16
emit_unencrypted_log on contract AvmTest with size 757 => 685
end_vote on contract EasyPrivateVoting with size 514 => 279
exit_to_l1_public on contract TokenBridge with size 2154 => 1773
get_address on contract AvmTest with size 45 => 13
get_args_hash on contract AvmTest with size 18 => 18
get_asset on contract Lending with size 888 => 718
get_assets on contract Lending with size 587 => 411
get_authorized on contract Auth with size 597 => 443
get_authorized_delay on contract Auth with size 702 => 517
get_block_number on contract AvmTest with size 45 => 13
get_chain_id on contract AvmTest with size 45 => 13
get_fee_per_da_gas on contract AvmTest with size 45 => 13
get_fee_per_l2_gas on contract AvmTest with size 45 => 13
get_portal_address_public on contract TokenBridge with size 297 => 145
get_position on contract Lending with size 3908 => 3623
get_price on contract PriceFeed with size 617 => 579
get_public_value on contract StatefulTest with size 636 => 598
get_roles on contract TokenBlacklist with size 989 => 749
get_scheduled_authorized on contract Auth with size 595 => 443
get_sender on contract AvmTest with size 45 => 13
get_shared_immutable_constrained_public on contract DocsExample with size 438 => 406
get_shared_immutable_constrained_public_indirect on contract DocsExample with size 701 => 607
get_shared_immutable_constrained_public_multiple on contract DocsExample with size 136 => 98
get_storage_address on contract AvmTest with size 45 => 13
get_timestamp on contract AvmTest with size 45 => 13
get_token on contract TokenBridge with size 513 => 366
get_transaction_fee on contract AvmTest with size 45 => 13
get_version on contract AvmTest with size 45 => 13
increment_balance on contract Benchmarking with size 1472 => 1264
increment_public_value on contract StatefulTest with size 695 => 449
increment_public_value_no_init_check on contract StatefulTest with size 447 => 351
init on contract Crowdfunding with size 2100 => 1341
init on contract Lending with size 958 => 598
initialize_public_immutable on contract DocsExample with size 433 => 252
initialize_shared_immutable on contract DocsExample with size 433 => 252
is_minter on contract Token with size 838 => 668
is_time_equal on contract Test with size 56 => 18
keccak_hash on contract AvmTest with size 49 => 49
l1_to_l2_msg_exists on contract AvmTest with size 65 => 17
mint_private on contract Token with size 1247 => 790
mint_private on contract TokenBlacklist with size 1495 => 906
mint_public on contract GasToken with size 946 => 813
mint_public on contract Token with size 2048 => 1520
mint_public on contract TokenBlacklist with size 2821 => 2137
modulo2 on contract AvmTest with size 16 => 16
nested_call_to_add on contract AvmNestedCallsTest with size 862 => 756
nested_call_to_add_with_gas on contract AvmNestedCallsTest with size 929 => 799
nested_static_call_to_add on contract AvmNestedCallsTest with size 890 => 784
nested_static_call_to_set_storage on contract AvmNestedCallsTest with size 759 => 665
new_note_hash on contract AvmTest with size 47 => 11
new_nullifier on contract AvmAcvmInteropTest with size 47 => 11
new_nullifier on contract AvmNestedCallsTest with size 47 => 11
new_nullifier on contract AvmTest with size 47 => 11
new_nullifier_acvm on contract AvmAcvmInteropTest with size 47 => 11
note_hash_exists on contract AvmTest with size 65 => 17
nullifier_collision on contract AvmTest with size 82 => 12
nullifier_exists on contract AvmTest with size 103 => 17
on_card_played on contract CardGame with size 2386 => 2151
on_cards_claimed on contract CardGame with size 2176 => 1927
on_game_joined on contract CardGame with size 1972 => 1733
pay_refund on contract FPC with size 2052 => 1685
pay_refund_with_shielded_rebate on contract FPC with size 2138 => 1771
pedersen_hash on contract AvmTest with size 19 => 19
pedersen_hash_with_index on contract AvmTest with size 19 => 19
poseidon2_hash on contract AvmTest with size 1370 => 1370
prepare_fee on contract FPC with size 1643 => 1280
pub_call_public_fn on contract ImportTest with size 710 => 636
pub_entry_point on contract Parent with size 263 => 189
pub_entry_point_twice on contract Parent with size 497 => 339
pub_get_value on contract Child with size 174 => 22
pub_get_value on contract StaticChild with size 409 => 281
pub_illegal_inc_value on contract StaticChild with size 448 => 336
pub_inc_value on contract Child with size 175 => 45
pub_inc_value on contract StaticChild with size 175 => 45
pub_inc_value_internal on contract Child with size 552 => 340
pub_set_value on contract Child with size 108 => 30
pub_set_value on contract StaticChild with size 108 => 30
public_call on contract StaticParent with size 263 => 189
public_constructor on contract StatefulTest with size 1808 => 1399
public_delegate_set_value on contract Delegator with size 724 => 724
public_get_decimals on contract Token with size 557 => 411
public_get_name on contract Token with size 538 => 392
public_get_symbol on contract Token with size 546 => 400
public_get_value_from_child on contract StaticParent with size 759 => 685
public_nested_static_call on contract Parent with size 674 => 561
public_nested_static_call on contract StaticParent with size 1012 => 894
public_set_value on contract DelegatedOn with size 68 => 28
public_static_call on contract Parent with size 328 => 236
public_static_call on contract StaticParent with size 328 => 236
push_nullifier_public on contract InclusionProofs with size 285 => 117
read_storage_immutable on contract AvmInitializerTest with size 286 => 133
read_storage_list on contract AvmTest with size 101 => 62
read_storage_map on contract AvmTest with size 385 => 341
read_storage_single on contract AvmTest with size 66 => 27
register on contract KeyRegistry with size 6385 => 5041
repay_public on contract Lending with size 2141 => 1747
rotate_npk_m on contract KeyRegistry with size 2592 => 1843
send_l2_to_l1_msg on contract AvmTest with size 56 => 12
set_admin on contract Token with size 528 => 257
set_authorized on contract Auth with size 925 => 474
set_authorized_delay on contract Auth with size 679 => 400
set_minter on contract Token with size 865 => 559
set_opcode_big_field on contract AvmTest with size 19 => 19
set_opcode_small_field on contract AvmTest with size 13 => 13
set_opcode_u32 on contract AvmTest with size 13 => 13
set_opcode_u64 on contract AvmTest with size 13 => 13
set_opcode_u8 on contract AvmTest with size 13 => 13
set_portal on contract GasToken with size 434 => 272
set_price on contract PriceFeed with size 401 => 349
set_read_storage_single on contract AvmTest with size 122 => 42
set_storage_list on contract AvmTest with size 76 => 30
set_storage_map on contract AvmTest with size 409 => 355
set_storage_single on contract AvmNestedCallsTest with size 65 => 25
set_storage_single on contract AvmTest with size 65 => 25
set_value_twice_with_nested_first on contract Child with size 803 => 654
set_value_twice_with_nested_last on contract Child with size 791 => 654
set_value_with_two_nested_calls on contract Child with size 1308 => 1063
sha256_hash on contract AvmTest with size 47 => 47
shield on contract Token with size 2368 => 1809
shield on contract TokenBlacklist with size 3102 => 2315
spend_public_authwit on contract DocsExample with size 14 => 14
spend_public_authwit on contract EcdsaAccount with size 1008 => 637
spend_public_authwit on contract SchnorrAccount with size 770 => 541
spend_public_authwit on contract SchnorrHardcodedAccount with size 770 => 540
spend_public_authwit on contract SchnorrSingleKeyAccount with size 770 => 540
spend_public_authwit on contract Uniswap with size 749 => 486
start_game on contract CardGame with size 2518 => 2175
swap_public on contract Uniswap with size 7983 => 6584
test_authwit_send_money on contract AvmAcvmInteropTest with size 803 => 709
test_get_contract_instance on contract AvmTest with size 522 => 410
test_get_contract_instance_raw on contract AvmTest with size 159 => 83
test_nullifier_inclusion_from_public on contract InclusionProofs with size 332 => 121
to_radix_le on contract AvmTest with size 187 => 187
total_supply on contract Token with size 536 => 390
total_supply on contract TokenBlacklist with size 536 => 390
transfer_public on contract Token with size 3071 => 2512
transfer_public on contract TokenBlacklist with size 4491 => 3533
u128_addition_overflow on contract AvmTest with size 772 => 668
u128_from_integer_overflow on contract AvmTest with size 357 => 357
update_accumulator on contract Lending with size 8695 => 8358
update_leader on contract DocsExample with size 430 => 290
update_roles on contract TokenBlacklist with size 2058 => 1252
withdraw_public on contract Lending with size 1190 => 93

Summary*

This PR:

• Creates a separate pass for "runtime separation" where we convert any Acir function called from brillig to a brillig function. After that pass, all functions have correct runtime, meaning they'll be converted to the runtime they hold.
• Updates the inliner to only consider entry points all brillig functions called from ACIR and all brillig recursive functions, instead of all brillig functions

With this change the inliner can correctly detect which brillig functions must not be inlined. This opens the door to allowing annotating brillig functions with inlining suggestions in the future.

Additional Context

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.

[jfecher]

Didn't have enough time to finish the review today so I'm blocking this to give me more time to think on the approach taken tomorrow. I'm wondering if we can avoid the extra pass at all and whether we can avoid the extra passes through the IR that are now within the inlining pass to look for recursive functions and functions that can be inlined.

For now, there's just a few nitpicks:

[sirasistant]

I'm wondering if we can avoid the extra pass at all and whether we can avoid the extra passes through the IR that are now within the inlining pass to look for recursive functions and functions that can be inlined.

I think it can be avoided, but then the inlining step becomes footgun land:

• In order to find brillig entry points, it has to explore recursively the SSA, instead of just searching for acir functions that call brillig
• Recursive functions in the SSA could marked as ACIR but called from brillig. This approach correctly handles this case, but without the runtime separation pass it'll try to unroll the recursive function even in a brillig context, so it'll need to clone the recursive function to brillig. Let me add an e2e test case for this.

In general I think it's saner to have a pass that makes the function.runtime express what the function will actually be converted to and reduce the inliner responsibility to just inline functions instead of dealing with context-dependant runtimes. And even if we don't have the pass the inliner will have to do most of the pass work so I think it's cleaner to have it in a separate pass with clear responsibilities.

[sirasistant]

Recursive functions in the SSA could marked as ACIR but called from brillig. This approach correctly handles this case, but without the runtime separation pass it'll try to unroll the recursive function even in a brillig context, so it'll need to clone the recursive function to brillig. Let me add an e2e test case for this.

Added the e2e test case that fails on nightly and is fixed by this process.

[TomAFrench]

I'm in favour of having this as a separate pass for simplicity and ease of testing. If necessary those two passes can be merged in future.

[jfecher]

The main reason I bring this up is just the general trend of adding increasingly more SSA passes which slows down compilation speed. The biggest offender is probably also the oldest - running mem2reg so many times.

[sirasistant]

Possibly the passes that run after unrolling are the ones that have more impact, since unrolling (logically) tends to increase a lot instruction counts

[sirasistant]

I thought about making this pass more lightweight via collecting called functions using func.values_iter(), but I think it makes it way more brittle, since we could have unused function values there ):

[sirasistant]

If performance of this pass is a concern I can possibly explore the SSA only once and build a cache of functionId => calledFunctionIds to be reused across the pass. But I'm not sure it'll make much of a difference. What do you think @jfecher ?

[sirasistant]

Nah, it won't be much of a difference because we do need to reexplore to trim unreachable functions anyway

[jfecher]

Yeah, I didn't see the cache making much of a difference either.
Anyway - the main reason I blocked this yesterday was to give me more time to review today not that I didn't think this should be merged. I'll finish the review now

[jfecher]

LGTM. Just some final nitpicks

[sirasistant]

Still no permission to add to merge queue ): @TomAFrench