Flatten CFG pass hangs

[joss-aztec]

Aim

To be able to compile the following example:

fn foo(x: Field, toggle: bool) -> Field {
    if x == 2 {
        2
    } else {
        if toggle {
            x + 1
        } else {
            x - 1
        }
    }
}

fn main(x: Field) -> pub Field {
    let mut agg: Field = x;
    let mut toggle = true;
    for _i in 0..3 {
        agg += foo(agg, toggle);
        toggle = !toggle;
    }
    agg
}

Expected Behavior

It compiles

Bug

Compilation appears to hang on the CFG flattening pass. Here is the log up until it hangs:

Initial SSA:
fn main f0 {
  b0(v0: Field):
    v2 = alloc 1 fields
    store v0 at v2
    v4 = alloc 1 fields
    store u1 1 at v4
    jmp b1(unit 0)
  b1(v5: Field):
    v7 = lt v5, Field 3
    jmpif v7 then: b2, else: b3
  b2():
    v8 = load v2
    v10 = load v2
    v11 = load v4
    v12 = call f1(v10, v11)
    v13 = add v8, v12
    store v13 at v2
    v14 = load v4
    v15 = not v14
    store v15 at v4
    v16 = add v5, u1 1
    jmp b1(v16)
  b3():
    v17 = load v2
    return v17
}
fn foo f1 {
  b0(v0: Field, v1: u1):
    v4 = eq v0, Field 2
    jmpif v4 then: b1, else: b2
  b1():
    jmp b3(Field 2)
  b3(v9: Field):
    return v9
  b2():
    jmpif v1 then: b4, else: b5
  b4():
    v6 = add v0, Field 1
    jmp b6(v6)
  b6(v8: Field):
    jmp b3(v8)
  b5():
    v7 = sub v0, Field 1
    jmp b6(v7)
}

After Inlining:
fn main f2 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    v2 = alloc 1 fields
    store u1 1 at v2
    jmp b1(unit 0)
  b1(v4: Field):
    v7 = lt v4, Field 3
    jmpif v7 then: b2, else: b3
  b2():
    v9 = load v1
    v10 = load v1
    v11 = load v2
    v14 = eq v10, Field 2
    jmpif v14 then: b4, else: b5
  b4():
    jmp b9(Field 2)
  b9(v17: Field):
    v19 = add v9, v17
    store v19 at v1
    v20 = load v2
    v21 = not v20
    store v21 at v2
    v22 = add v4, u1 1
    jmp b1(v22)
  b5():
    jmpif v11 then: b6, else: b7
  b6():
    v18 = add v10, u1 1
    jmp b8(v18)
  b8(v16: Field):
    jmp b9(v16)
  b7():
    v15 = sub v10, u1 1
    jmp b8(v15)
  b3():
    v8 = load v1
    return v8
}

After Unrolling:
fn main f2 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    v2 = alloc 1 fields
    store u1 1 at v2
    v23 = load v1
    v24 = load v1
    v25 = load v2
    v26 = eq v24, Field 2
    jmpif v26 then: b12, else: b13
  b12():
    jmp b17(Field 2)
  b17(v29: Field):
    v30 = add v23, v29
    store v30 at v1
    v31 = load v2
    v32 = not v31
    store v32 at v2
    v35 = load v1
    v36 = load v1
    v37 = load v2
    v38 = eq v36, Field 2
    jmpif v38 then: b21, else: b22
  b21():
    jmp b26(Field 2)
  b26(v41: Field):
    v42 = add v35, v41
    store v42 at v1
    v43 = load v2
    v44 = not v43
    store v44 at v2
    v47 = load v1
    v48 = load v1
    v49 = load v2
    v50 = eq v48, Field 2
    jmpif v50 then: b30, else: b31
  b30():
    jmp b35(Field 2)
  b35(v53: Field):
    v54 = add v47, v53
    store v54 at v1
    v55 = load v2
    v56 = not v55
    store v56 at v2
    jmp b3()
  b3():
    v8 = load v1
    return v8
  b31():
    jmpif v49 then: b32, else: b33
  b32():
    v58 = add v48, u1 1
    jmp b34(v58)
  b34(v52: Field):
    jmp b35(v52)
  b33():
    v51 = sub v48, u1 1
    jmp b34(v51)
  b22():
    jmpif v37 then: b23, else: b24
  b23():
    v46 = add v36, u1 1
    jmp b25(v46)
  b25(v40: Field):
    jmp b26(v40)
  b24():
    v39 = sub v36, u1 1
    jmp b25(v39)
  b13():
    jmpif v25 then: b14, else: b15
  b14():
    v34 = add v24, u1 1
    jmp b16(v34)
  b16(v28: Field):
    jmp b17(v28)
  b15():
    v27 = sub v24, u1 1
    jmp b16(v27)
}

After Simplifying:
fn main f2 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    v2 = alloc 1 fields
    store u1 1 at v2
    v23 = load v1
    v24 = load v1
    v25 = load v2
    v26 = eq v24, Field 2
    jmpif v26 then: b12, else: b13
  b12():
    jmp b17(Field 2)
  b17(v29: Field):
    v30 = add v23, v29
    store v30 at v1
    v31 = load v2
    v32 = not v31
    store v32 at v2
    v35 = load v1
    v36 = load v1
    v37 = load v2
    v38 = eq v36, Field 2
    jmpif v38 then: b21, else: b22
  b21():
    jmp b26(Field 2)
  b26(v41: Field):
    v42 = add v35, v41
    store v42 at v1
    v43 = load v2
    v44 = not v43
    store v44 at v2
    v47 = load v1
    v48 = load v1
    v49 = load v2
    v50 = eq v48, Field 2
    jmpif v50 then: b30, else: b31
  b30():
    jmp b35(Field 2)
  b35(v53: Field):
    v54 = add v47, v53
    store v54 at v1
    v55 = load v2
    v56 = not v55
    store v56 at v2
    jmp b3()
  b3():
    v8 = load v1
    return v8
  b31():
    jmpif v49 then: b32, else: b33
  b32():
    v58 = add v48, u1 1
    jmp b34(v58)
  b34(v52: Field):
    jmp b35(v52)
  b33():
    v51 = sub v48, u1 1
    jmp b34(v51)
  b22():
    jmpif v37 then: b23, else: b24
  b23():
    v46 = add v36, u1 1
    jmp b25(v46)
  b25(v40: Field):
    jmp b26(v40)
  b24():
    v39 = sub v36, u1 1
    jmp b25(v39)
  b13():
    jmpif v25 then: b14, else: b15
  b14():
    v34 = add v24, u1 1
    jmp b16(v34)
  b16(v28: Field):
    jmp b17(v28)
  b15():
    v27 = sub v24, u1 1
    jmp b16(v27)
}

To Reproduce

Installation Method

Compiled from source

Nargo Version

nargo 0.6.0 (git version hash: fb6da48, is dirty: true)

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[joss-aztec]

In fact this program is enough to break it.

fn main(x: Field) -> pub Field {
    let mut agg: Field = x;
    for _i in 0..3 {
        agg += 1;
    }
    agg
}

Initial SSA:
fn main f0 {
  b0(v0: Field):
    v2 = alloc 1 fields
    store v0 at v2
    jmp b1(unit 0)
  b1(v3: Field):
    v5 = lt v3, Field 3
    jmpif v5 then: b2, else: b3
  b2():
    v6 = load v2
    v8 = add v6, Field 1
    store v8 at v2
    v9 = add v3, Field 1
    jmp b1(v9)
  b3():
    v10 = load v2
    return v10
}

After Inlining:
fn main f1 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    jmp b1(unit 0)
  b1(v2: Field):
    v5 = lt v2, Field 3
    jmpif v5 then: b2, else: b3
  b2():
    v7 = load v1
    v9 = add v7, Field 1
    store v9 at v1
    v10 = add v2, Field 1
    jmp b1(v10)
  b3():
    v6 = load v1
    return v6
}

After Unrolling:
fn main f1 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    v11 = load v1
    v12 = add v11, Field 1
    store v12 at v1
    v14 = load v1
    v15 = add v14, Field 1
    store v15 at v1
    v18 = load v1
    v19 = add v18, Field 1
    store v19 at v1
    jmp b3()
  b3():
    v6 = load v1
    return v6
}

After Simplifying:
fn main f1 {
  b0(v0: Field):
    v1 = alloc 1 fields
    store v0 at v1
    v11 = load v1
    v12 = add v11, Field 1
    store v12 at v1
    v14 = load v1
    v15 = add v14, Field 1
    store v15 at v1
    v18 = load v1
    v19 = add v18, Field 1
    store v19 at v1
    jmp b3()
  b3():
    v6 = load v1
    return v6
}

[joss-aztec]

The CFG was at fault. It contained unreachable blocks dangling from previous passes, which then caused the predecessors.len() > 1 check in analyze_function to give a false positive.