SSA Refactor: Calling Brillig in ACIR with black box funcs will panic

[vezenovm]

Aim

Trying to call a Brillig function inside of merkle_insert will cause a panic inside SSA.

Expected Behavior

I should be able to call Brillig functions as expected when stdlib black box funcs are being used.

Bug

use dep::std;

fn main(
    old_root: Field,
    old_leaf: Field,
    old_hash_path: [Field; 3],
    new_root: pub Field,
    leaf: Field,
    index: Field,
    mimc_input: [Field; 4],
) {
    assert(loop(4) == 6);

    assert(old_root == std::merkle::compute_merkle_root(old_leaf, index, old_hash_path));

    let calculated_root = std::merkle::compute_merkle_root(leaf, index, old_hash_path);
    assert(new_root == calculated_root);

    let h = std::hash::mimc_bn254([0, 1, 2, 4]);
    // Regression test for PR #891
    // NOTE: This println will cause a panic as well 
    // std::println(h);
    assert(h == 18226366069841799622585958305961373004333097209608110160936134895615261821931);
}

unconstrained fn loop(x: u32) -> u32 {
    let mut sum = 0;
    for i in 0..x {
        sum = sum + i;
    }
    sum
}

will return this:

Message:  internal error: entered unreachable code: return encountered before a join point was found. This can only happen if early-return was added to the language without implementing it by jmping to a join block first
Location: crates/noirc_evaluator/src/ssa_refactor/opt/flatten_cfg/branch_analysis.rs:107

To Reproduce

1. Run the program in the issue with nargo execute --experimental-ssa

Installation Method

Compiled from source

Nargo Version

master

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[sirasistant]

There are two issues here:

1. The inlining step, if a call cannot be inlined (such as a call to brillig) retains all original functions along the new main, instead of doing simple reachability analysis (which was non-trivial before defunctionalization, but now can be trivially done and it's done for another separate feature)
2. These original functions retained seem to be breaking the branch analysis

[sirasistant]

Regarding 2, the branch analysis seems to have a bad time handling this function when is left in the SSA by the inlining step:

acir fn compute_merkle_root f2 {
  b0(v0: Field, v1: Field, v2: [Field]):
    v4 = call array_len(v2)
    v6 = cast v4 as u32
    v7 = call to_le_bits(v1, v6)
    v8 = allocate
    store v0 at v8
    jmp b1(Field 0)
  b1(v9: Field):
    v11 = lt v9, v4
    jmpif v11 then: b2, else: b3
  b2():
    v13 = array_get v7, index v9
    jmpif v13 then: b4, else: b5
  b4():
    v14 = array_get v2, index v9
    v15 = load v8
    jmp b6(v14, v15)
  b6(v18: Field, v19: Field):
    v22 = call f6([v18, v19])
    v23 = array_get v22, index Field 0
    store v23 at v8
    v24 = add v9, Field 1
    jmp b1(v24)
  b5():
    v16 = array_get v2, index v9
    v17 = load v8
    jmp b6(v17, v16)
  b3():
    v25 = load v8
    return v25
}

Probably because it's not unrolled since it's no longer called by main

[sirasistant]

Fixing just the issue 1 won't fix this for all cases because a function might be reachable from both ACIR and brillig. In that case the inliner step will leave the compute_merkle_root in the SSA because even if it detects it's no longer reachable from main, it's still reachable from the brillig functions called from main.
The fix for 2 would either be:

• Make flatten_cfg only act on main (since all the other functions should no longer be relevant since they are executed as brillig)
• Make flatten_cfg not to panic if it cannot transform a function, just leave it untouched