Example of an unexpectedly-huge contract artifact.

[iAmMichaelConnor]

AztecProtocol/aztec-packages#10546

In particular, create_note and create_note_no_init_check

https://github.com/AztecProtocol/aztec-packages/blob/6f209fb69fcce868c6e0fe9b79b5ac3f3a1e5c48/noir-projects/noir-contracts/contracts/stateful_test_contract/src/main.nr#L45

[iAmMichaelConnor]

https://aztecprotocol.slack.com/archives/C02M7VC7TN0/p1733953786902059

[TomAFrench]

@aakoshh Do you have bandwidth to take a look at this?

[aakoshh]

The first jump I found in the size was AztecProtocol/aztec-packages@3304046 where the create_note_no_init_check goes from 164,516 bytes in the previous commit up all the way to 13,815,792, or if we consider the entire stateful_test_contract-StatefulTest.json then it goes from 3.3M to 42M. This is not the final size, but it's something worth intestigating.

Commands to check:

PROGRAM_DIR=$PWD/noir-projects/noir-contracts 
git checkout 3304046704e257902e32b86baf1aafc8b23bcaf6
cd noir/noir-repo
cargo run --release -p nargo_cli -- --program-dir $PROGRAM_DIR compile --package stateful_test_contract
jq '.functions | sort_by(.name) | .[] | {name: .name, size: .bytecode | length }' $PROGRAM_DIR/target/stateful_test_contract-StatefulTest.json

[aakoshh]

Within the syncing PR AztecProtocol/aztec-packages#10307 that backs the above squashed commit, the two commits where there are significant bytecode size increases for create_note_no_init_check are:

• AztecProtocol/aztec-packages@369ea54 the size goes from 213,180 to 4,802,664 compared to 0577c1a
• AztecProtocol/aztec-packages@70cf870f the size goes from 4,331,388 to 15,129,080 compared to feef655

[aakoshh]

The following is the printout of the number of lines in the SSA in AztecProtocol/aztec-packages@369ea54

COMPILING CONTRACT FUNCTION create_note_no_init_check
Initial SSA:: 7661
After Defunctionalization:: 7693
After Removing Paired rc_inc & rc_decs:: 7693
After Runtime Separation:: 8136
After Resolving IsUnconstrained:: 8136
After Inlining (1st):: 12098
After Mem2Reg (1st):: 8727
After Simplifying (1st):: 7953
After `as_slice` optimization: 7953
After `static_assert` and `assert_constant`:: 7953
After Loop Invariant Code Motion:: 7953
After Unrolling:: 40728
After Simplifying (2nd):: 38161
After Flattening:: 58927
After Removing Bit Shifts:: 58927
After Mem2Reg (2nd):: 33335
After Inlining (2nd):: 33813
After Remove IfElse:: 1287564
After Constant Folding:: 967623
After EnableSideEffectsIf removal:: 965798
After Constraint Folding:: 963258
After Dead Instruction Elimination:: 958799
After Simplifying:: 958797
After Array Set Optimizations:: 958797
After Constant Folding with Brillig:: 958478
After Dead Instruction Elimination:: 958458

We can see that there is a dramatic increase in the Remove IfElse step, going from 33,813 to 1,287,564

Compare it with the same in its parent commit AztecProtocol/aztec-packages@0577c1a

COMPILING CONTRACT FUNCTION create_note_no_init_check
Initial SSA:: 8009
After Defunctionalization:: 8041
After Removing Paired rc_inc & rc_decs:: 7861
After Runtime Separation:: 8342
After Resolving IsUnconstrained:: 8342
After Inlining (1st):: 13330
After Mem2Reg (1st):: 11720
After Simplifying (1st):: 10834
After `as_slice` optimization: 10834
After `static_assert` and `assert_constant`:: 10834
After Loop Invariant Code Motion:: 10834
After Unrolling:: 44343
After Simplifying (2nd):: 41738
After Flattening:: 71721
After Removing Bit Shifts:: 71721
After Mem2Reg (2nd):: 35739
After Inlining (2nd):: 35277
After Remove IfElse:: 39020
After Constant Folding:: 31940
After EnableSideEffectsIf removal:: 30111
After Constraint Folding:: 27518
After Dead Instruction Elimination:: 19253
After Simplifying:: 19251
After Array Set Optimizations:: 19251
After Constant Folding with Brillig:: 18969
After Dead Instruction Elimination:: 18944

In this version RemoveIfElse adds less than 4,000 lines.

Further digging revealed that remove_if_else.rs calls value_merger.rs on arrays, which merges the then and else values being assigned to arrays by merging their values index by index, and creating new arrays of the merged values, without the if-then-else. This introduces 4096 new opcodes for each merge in this example, doing it hundreds of times. None of these two modules had changed, so some preceding SSA pass must have put a lot more arrays in the code than existed before.

Printing the number of arrays reveals where they get introduced.

This is in 0577c1a

After Simplifying (2nd):: 41738
f0: if-then-else arrays: 0
f44: if-then-else arrays: 0
f103: if-then-else arrays: 0
f110: if-then-else arrays: 0
f117: if-then-else arrays: 0
f159: if-then-else arrays: 0
f170: if-then-else arrays: 0
f175: if-then-else arrays: 0
After Flattening:: 71721
f0: if-then-else arrays: 77
f44: if-then-else arrays: 10
f103: if-then-else arrays: 78
f110: if-then-else arrays: 38
f117: if-then-else arrays: 1
f159: if-then-else arrays: 22
f170: if-then-else arrays: 102
f175: if-then-else arrays: 60
...
After Mem2Reg (2nd):: 35739
f0: if-then-else arrays: 17
f44: if-then-else arrays: 0
f103: if-then-else arrays: 30
f110: if-then-else arrays: 0
f117: if-then-else arrays: 0
f159: if-then-else arrays: 0
f170: if-then-else arrays: 0
f175: if-then-else arrays: 22
After Inlining (2nd):: 35277
f0: if-then-else arrays: 17
After Remove IfElse:: 39020
f0: if-then-else arrays: 0

And this is in 369ea54:

After Flattening:: 58927
f0 if-then-else arrays: 352
f44 if-then-else arrays: 10
f103 if-then-else arrays: 46
f110 if-then-else arrays: 46
f117 if-then-else arrays: 1
f159 if-then-else arrays: 26
f170 if-then-else arrays: 126
f175 if-then-else arrays: 36
...
After Mem2Reg (2nd):: 33335
f0 if-then-else arrays: 283
f44 if-then-else arrays: 0
f103 if-then-else arrays: 22
f110 if-then-else arrays: 0
f117 if-then-else arrays: 0
f159 if-then-else arrays: 0
f170 if-then-else arrays: 0
f175 if-then-else arrays: 16
After Inlining (2nd):: 33813
f0 if-then-else arrays: 283
After Remove IfElse:: 1287564
f0 if-then-else arrays: 0

The numbers show the count of of arrays that would be merged in the entry block of the functions, the only block remove_if_else looks at, I assume because Inlining should have eliminated all other blocks by then (at least all other functions disappeared). 283*4096 is explains most of the growth in the instruction count.

IfElse counter

    let mut count = 0;
    let block = function.entry_block();
    for instruction in function.dfg[block].instructions() {
        if let Instruction::IfElse { then_condition: _, then_value, else_value: _ } =
            function.dfg[*instruction]
        {
            let then_value = function.dfg.resolve(then_value);
            if let Type::Array(..) = function.dfg.type_of_value(then_value) {
                count += 1;
            }
        }
    }

So the question is why has flatten_cfg introduced so many more if-then-else arrays then before; and this is a module that has changed in this commit, with the crux being these lines: where previously it was a Store, now it can be an IfElse, which in case of an array gets removed later by merging values.

One further thing to look at would be whether there were more stores to arrays in this commit then before.
Adding this extra count shows that before the change there were more stores to arrays, but they got eliminated by mem2reg:

After Flattening:: 71721
f0 if-then-else arrays: 77, store arrays: 516
After Mem2Reg (2nd):: 35739
f0 if-then-else arrays: 17, store arrays: 0
After Remove IfElse:: 39020
f0 if-then-else arrays: 0, store arrays: 0

whereas after there are more if-then-else and less stores, but the if-then-else's don't get eliminated, which then plays a magnified role during remove_if_then:

After Flattening:: 58927
f0 if-then-else arrays: 352, store arrays: 374
After Mem2Reg (2nd):: 33335
f0 if-then-else arrays: 283, store arrays: 0
After Remove IfElse:: 1287564
f0 if-then-else arrays: 0, store arrays: 0

[aakoshh]

Looking at what is causing the following:

AztecProtocol/aztec-packages@70cf870f the size goes from 4,331,388 to 15,129,080 compared to feef655

Printing SSA sizes does not reveal any smoking gun, the numbers are similar to above.
Actually in this case, commit feef655 looks bigger on paper than what follows:

Dead Instruction Elimination (2nd): 874,549 lines, 36,977,266 chars
f0: 874,081 instructions
ACIR OPCODES BEFORE TRANS: 298,782
ACIR OPCODES AFTER TRANS: 299,471

Whereas in 70cf870f we have a smaller SSA, but the final ACIR opcode count is 5x larger:

Dead Instruction Elimination (2nd): 641,474 lines, 28,936,683 chars
f0: 640,942 instructions
OPCODES BEFORE TRANS: 1,580,140
OPCODES AFTER TRANS: 1,580,497

The following are the statistics of how many ACIR opcodes were generated from how many encountered Instructions:

In feef655:

f0: 874081 instructions
IncrementRc: instructions=73, opcodes=0, avg=0
Call: instructions=143, opcodes=1562, avg=10
Not: instructions=756, opcodes=0, avg=0
Binary: instructions=437052, opcodes=7918, avg=0
ArrayGet: instructions=145101, opcodes=288850, avg=1
Truncate: instructions=8, opcodes=86, avg=10
EnableSideEffectsIf: instructions=1598, opcodes=0, avg=0
RangeCheck: instructions=168, opcodes=304, avg=1
MakeArray: instructions=302, opcodes=0, avg=0
Cast: instructions=287870, opcodes=0, avg=0
Constrain: instructions=1010, opcodes=522, avg=0
ACIR OPCODES=298782

In 70cf870f:

f0: 640942 instructions
IncrementRc: instructions=30, opcodes=0, avg=0
Call: instructions=172, opcodes=1822, avg=10
Not: instructions=1167, opcodes=0, avg=0
Binary: instructions=476607, opcodes=1262996, avg=2
ArrayGet: instructions=158692, opcodes=314999, avg=1
Truncate: instructions=9, opcodes=93, avg=10
EnableSideEffectsIf: instructions=1686, opcodes=0, avg=0
RangeCheck: instructions=168, opcodes=304, avg=1
MakeArray: instructions=303, opcodes=0, avg=0
Cast: instructions=906, opcodes=0, avg=0
Constrain: instructions=1202, opcodes=682, avg=0
ACIR OPCODES=1581401

The biggest visible change is in the ratio of opcodes generated from Binary instructions: we have roughly the same number of instructions, but instead of 7,918 opcodes end u with 1,262,996 them.

Just looking at binary instructions originally:

Binary add: instructions=144620, opcodes=732, avg=0.005061540589130134
Binary eq: instructions=424, opcodes=1669, avg=3.936320754716981
Binary lt: instructions=828, opcodes=2436, avg=2.9420289855072466
Binary mul: instructions=147400, opcodes=3078, avg=0.020881953867028492
Binary or: instructions=18, opcodes=3, avg=0.16666666666666666
Binary sub: instructions=143762, opcodes=0, avg=0

and then after the new commit:

Binary add: instructions=157852, opcodes=315542, avg=1.9989737222208144
Binary eq: instructions=424, opcodes=1669, avg=3.936320754716981
Binary lt: instructions=860, opcodes=2436, avg=2.832558139534884
Binary mul: instructions=317308, opcodes=943346, avg=2.9729663292447714
Binary or: instructions=18, opcodes=3, avg=0.16666666666666666
Binary sub: instructions=145, opcodes=0, avg=0

Further digging revealed that the difference in the number of instructions generated comes from check_unsigned_overflow: previously we only generated 434 constraints, but with the new commit the number is 471,411.

The following show the number of times convert_ssa_binary was called with Signed vs Unsigned values before the commit, and the number of different potential overflows for which range constraints were added:

signed: 433712
unsigned: 3340

attempt to add with overflow: 358
attempt to multiply with overflow: 70
attempt to subtract with overflow: 6

And in the new commit:

signed: 1662
unsigned: 474945
attempt to add with overflow: 157612
attempt to multiply with overflow: 313792
attempt to subtract with overflow: 7

It shows that we switched from doing mostly signed to mostly unsigned binary operations, which is what induced the creation of the new range constraints.

The cause of this change is how the rules in the ValueMerger have changed from using Field to using the actual type of the if-then-else, notably the casts to and from Field to the type of the actual result have been removed. The following code would restore the number of opcodes:

ValueMerger::merge_numeric_values

pub(crate) fn merge_numeric_values(
        dfg: &mut DataFlowGraph,
        block: BasicBlockId,
        then_condition: ValueId,
        else_condition: ValueId,
        then_value: ValueId,
        else_value: ValueId,
    ) -> ValueId {
        let then_type = dfg.type_of_value(then_value);
        let else_type = dfg.type_of_value(else_value);
        assert_eq!(
            then_type, else_type,
            "Expected values merged to be of the same type but found {then_type} and {else_type}"
        );

        if then_value == else_value {
            return then_value;
        }

        let then_call_stack = dfg.get_value_call_stack(then_value);
        let else_call_stack = dfg.get_value_call_stack(else_value);

        let call_stack = if then_call_stack.is_empty() { else_call_stack } else { then_call_stack };

        let then_field = Instruction::Cast(then_value, Type::field());
        let then_field_value =
            dfg.insert_instruction_and_results(then_field, block, None, call_stack.clone()).first();

        let else_field = Instruction::Cast(else_value, Type::field());
        let else_field_value =
            dfg.insert_instruction_and_results(else_field, block, None, call_stack.clone()).first();

        // We must cast the bool conditions to the actual numeric type used by each value.
        let then_condition = dfg
            .insert_instruction_and_results(
                Instruction::Cast(then_condition, Type::field()),
                block,
                None,
                call_stack.clone(),
            )
            .first();

        let else_condition = dfg
            .insert_instruction_and_results(
                Instruction::Cast(else_condition, Type::field()),
                block,
                None,
                call_stack.clone(),
            )
            .first();

        let mul = Instruction::binary(BinaryOp::Mul, then_condition, then_field_value);
        let then_value =
            dfg.insert_instruction_and_results(mul, block, None, call_stack.clone()).first();

        let mul = Instruction::binary(BinaryOp::Mul, else_condition, else_field_value);
        let else_value =
            dfg.insert_instruction_and_results(mul, block, None, call_stack.clone()).first();

        let add = Instruction::binary(BinaryOp::Add, then_value, else_value);
        let add_field_value =
            dfg.insert_instruction_and_results(add, block, None, call_stack.clone()).first();

        let merged = Instruction::Cast(add_field_value, then_type);
        dfg.insert_instruction_and_results(merged, block, None, call_stack).first()
    }

With this modification, the results would be:

f0: 955828 instructions
Binary add: instructions=157828, opcodes=1598, avg=0.010124946143903489
Binary mul: instructions=317284, opcodes=4333, avg=0.01365653483944983
...
attempt to add with overflow: 791
attempt to multiply with overflow: 503
attempt to subtract with overflow: 7
signed: 472260
unsigned: 4299
...
ACIR OPCODES = 328992

The problem, of course, is that this would be potentially unsafe as it would not detect overflows, which is probably why it was reverted. OTOH we're only using it in combination with a boolean conditional variable, so it should be c*a + !c*b, which shouldn't cause an overflow because it's either a or b, never a+b.

Most probably the effect of this range check is exacerbated by the previous change, which causes merge_numeric_values to be applied on all members of an array during the remove_if_else pass - if these arrays include unsigned numbers that can balloon the range constraints, along with the already inflated instruction count.

Note that even with the change above to use Field again, the size of the JSON is still 14MB and the bytecode of create_note_no_init_check is 4,220,040. We need to fix both to bring the artefact size back to near its original value.

[aakoshh]

The next larger change to the overall size shown by ls -lh ./target/stateful_test_contract-StatefulTest.json is AztecProtocol/aztec-packages@3166529 which is the squashed commit of AztecProtocol/aztec-packages#10483

(I'll keep updating the comment if I find anything).

Within the PR it is the transition from AztecProtocol/aztec-packages@7a66f06 to AztecProtocol/aztec-packages@9c79a87 that sees the size go from 42MB to 64MB

Unfortunately this 9c79a87 is a merge from master of 64 commits, with over 800 files changed: AztecProtocol/aztec-packages@7a66f06...9c79a87

None of these files are under the noir/noir-repo path (that's what the sync PR is trying to add), but there are many changes under noir-projects, for example noir-projects/aztec-nr which the contract we're investigating uses.

[benesjan]

@aakoshh I don't know if you've seen my comment but there the cause of blowup is pretty clear. Might make sense to investigate that first as the cause of the blowup of the stateful contract seems hard to point down (might be the same issue).