Description

Problem*

Resolves #7306.

The description in this PR repeats a lot of the comments and tests from the new SSA pass, but I have copied things here for visibility.

Take this program:

global ONE: Field = 1;
global TWO: Field = 2;
global THREE: Field = 3;
fn main(x: Field, y: pub Field) {
    /// Safety: testing context
    unsafe {
        entry_point_one(x, y);
        entry_point_two(x, y);
    }
}
unconstrained fn entry_point_one(x: Field, y: Field) {
    let z = ONE + x + y;
    assert(z == 2);
    inner_func(x, y);
}
unconstrained fn entry_point_two(x: Field, y: Field) {
    let z = TWO + x + y;
    assert(z == 3);
    inner_func(x, y);
}
unconstrained fn inner_func(x: Field, y: Field) {
    let z = THREE + x + y;
    assert(z == 4);
}

We have this SSA before Brillig gen:

g0 = Field 1
g1 = Field 2
g2 = Field 3

acir(inline) predicate_pure fn main f0 {
  b0(v3: Field, v4: Field):
    call f1(v3, v4)
    call f2(v3, v4)
    return
}
brillig(inline) predicate_pure fn entry_point_one f1 {
  b0(v3: Field, v4: Field):
    v5 = add Field 1, v3
    v6 = add v5, v4
    constrain v6 == Field 2
    call f3(v3, v4)
    return
}
brillig(inline) predicate_pure fn entry_point_two f2 {
  b0(v3: Field, v4: Field):
    v5 = add Field 2, v3
    v6 = add v5, v4
    constrain v6 == Field 3
    call f3(v3, v4)
    return
}
brillig(inline) predicate_pure fn inner_func f3 {
  b0(v3: Field, v4: Field):
    v5 = add Field 3, v3
    v6 = add v5, v4
    constrain v6 == Field 4
    return
}

For each entry point we will generate the follows artifacts for globals initialization:

GlobalInit(Id(1)):
  CONST M32835 = 1
  CONST M32836 = 2
  CONST M32837 = 3
  RETURN
GlobalInit(Id(2)):
  CONST M32835 = 2
  CONST M32836 = 3
  RETURN

It is then not clear to inner_func which map of SSA value id -> Brillig global initialization we should use.
Without the hack from #7306 we get the following bytecode for f3:

Function(Id(3), Some(Id(0))):
  S3 = M32836 + S1
  S1 = S3 + S2
  CONST S2 = 4
  S3 = S1 == S2
  JUMP_IF S3 TO Function(Id(3), Some(Id(0))) - 1
  CONST S4 = 0
  TRAP FreeMem[0..S4]
  RETURN

This works when f3 is called from the f2 entry point. But it will break when called from the f1 entry point. We need to specialize f3 to account for the potentially conflicting global allocation maps.

Summary*

We now specialize functions per entry point.

A few things were done in this PR:

1. A new pass the specializes functions per entry point
2. I run the new pass following DIE as to reduce the amount of code we may have to duplicate. However, this also required re-running DIE following this pass as the used_globals map is set during DIE. Perhaps we do not have to re-run this though as the global value IDs should not change across SSA passes. I could foresee the CFG simplification after DIE leading to some terminators that use globals being removed and needing to recompute the used globals map. Perhaps we could recompute this during CFG simplification. I feel this can be done in a followup PR though.
3. I have been testing against aztec-packages directly and added a few simplified regression tests to our integration tests as well as some unit tests for the new SSA pass.

Additional Context

This works further re-iterates the need for a debug/release mode as laid out in #2128. This duplication can lead to code bloat. During debug mode we could potentially not perform any entry point analysis and just have the same globals across all functions if this work is shown to seriously degrade compilation. Then during release mode we can perform the full entry point analysis to optimize for runtime.

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.