Attempt SSA optimizations on zero-argument functions first

[michaeljklein]

Problem

Currently in Brillig, we inline functions but don’t do loop unrolling, so we are really constrained in terms of constant folding.

It seems likely that there are plenty of functions that could be constant-folded if we separated out a category that can be easily worked with, viz. zero-argument functions (with no foreign calls).

• These zero-argument functions are often used to build arrays, so O(n) savings for even a few arrays could be significant

When we optimize_into_acir, we run all of the passes over all of the functions in one go.

Happy Case

1. Validate how many cases of this there are using the flamegraph tool on Brillig

• Are there a lot of zero-arg functions?
• When you do array operations in Brillig functions without args, do they currently get fuzed/unrolled?
• Confirm that this optimization seems useful

3. Running all passes over:
   a. functions without arguments
   b. functions reachable from (a)
   c. the remaining functions

• Validate whether that allows us to take advantage of the zero-arg functions being smaller, meaning they will get inlined as smaller versions

NOTE:

• Most passes appear to be relatively idempotent, with the notable exception of inlining
• The first line of most SSA passes is ~for function in self.functions {
  • These passes can be easily converted to per-function passes

Workaround

Yes

Workaround Description

Optimize by hand

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[michaeljklein]

@TomAFrench After running the noir-profiler on all test_programs (with dumping the folded_lines from flamegraph.rs)

• The successful runs were collected
• I used ad-hoc regex to parse out the zero-arg functions
• I tallied the number of occurrences, which may be found below:

{
"equal()"=>10,                          
 "less()"=>3,                            
 "inner_1()"=>3,                         
 "inner_2()"=>3,                         
 "inner_3()"=>6,                         
 "new()"=>72,                            
 "none()"=>84,                           
 "foo()"=>1,                             
 "regression_2903()"=>3,                 
 "regression_2906()"=>5,                 
 "regression_4967()"=>5,                 
 "test_iterators()"=>2744,               
 "test_mut_iterators()"=>4302,           
 "doc_tests()"=>7882,                    
 "x5_5_config()"=>3390,
 "regression_2255()"=>1,
 "zero()"=>24,
 "regression_4506()"=>17,
 "one()"=>11,
 "ALLOCATE_HASHMAP()"=>185,
 "test_retain()"=>1143,
 "zeroed()"=>21
}

Out of 240 programs where noir-profiler succeeded.

Notes:

• I used a couple ad-hoc ruby one-liners which can be modified if we want other stats.
• Some interesting functions:
  • test_mut_iterators(), >4k occurrences, used for hashmaps (HashMap and UHashMap cases conflated)
  • doc_tests() is also used by both hashmaps
• What is x5_5_config?

[TomAFrench]

what is x5_5_config?

https://github.com/noir-lang/noir/blob/master/noir_stdlib/src/hash/poseidon/bn254/consts.nr

We can make this whole file comptime tbh so we don't need to worry about it.

[TomAFrench]

It would be interesting to run this on aztec-packages as it's more representative of real world usage.

[michaeljklein]

Running the same script at the root of aztec-packages after a successful bootstrap.sh full gives:

{
  "get_instance()"=>176576,
  "t_main()"=>1,
  "tx_overhead()"=>12,
  "empty()"=>12,
  "new()"=>416
}

[michaeljklein]

Notes from manually reviewing SSA emitted from compiling the blob crate in aztec-packages:

• There are a lot of functions that just jump somewhere else:

b37185():
  jmp b37186()

• Moreover, there are chains of A(): jmp B(); B(): jmp C(); ..
  • I would expect some of these to go away by completing this issue
• Many large constants are repeated, e.g. strings and arrays
• Inlining might be over-eager in some cases:
  • E.g. the 23-instr methods b37163 and b37167 from the blob crate appear to be inlined versions of the same function

[michaeljklein]

There were no changes to Brillig sized from result of running SSA passes on individual functions, so dropping the 0-arg SSA pass and keeping the impl Function { fn do_pass() } refactor