CFG flattening pass's reordering of store instructions breaks mem2reg

[sirasistant]

Aim

To be able to combine mutable variables with calls to unconstrained functions.

Expected Behavior

This should compile:

fn main(mut x: u32)  {
    assert(identity(x) == 7);
}

unconstrained fn identity(x: u32) -> u32 {
    x
}

Bug

fn identity f1 {
  b0(v0: u32):
    return v0
}
fn main f2 {
  b0(v0: u32):
    v7 = allocate
    store v0 at v7
    v8 = call f1(v0)
    v9 = eq v8, u32 7
    constrain v9
    return 
}


The application panicked (crashed).
Message:  internal error: entered unreachable code: Expected all allocate instructions to be removed before acir_gen
Location: crates/noirc_evaluator/src/ssa_refactor/acir_gen/mod.rs:252

To Reproduce

Installation Method

Compiled from source

Nargo Version

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[kevaundray]

Noting that if mut is removed from the function parameter then this now works

[sirasistant]

This fails in the same manner without brillig calls:

struct Context {
    read_requests: Field,
}

impl Context {
    fn new() -> Context {
        Context { read_requests: 0 }
    }

    fn push_read_request(mut self: Self, request: Field) -> Context {
        self.read_requests += request;
        self
    }
}

struct Note {
    is_real: bool,
}


fn compute_note_hash(note: Note) -> Field {
    dep::std::hash::pedersen([
        note.is_real as Field,
    ])[0]
}

fn read_2_notes(storage_slot: Field) -> (Note, Note) {
    let randomness = dep::std::hash::pedersen([storage_slot])[0];
    let note0_is_real =  ((randomness as u32) % 2) as bool;
    let note0 = Note {
        is_real: note0_is_real,
    };

    let note1 = Note {
        is_real: !note0_is_real,
    };

    (note0, note1)
}

fn is_real(note: Note) -> bool {
    note.is_real
}

struct Set {
    storage_slot: Field,
}

impl Set {
    fn new(storage_slot: Field) -> Set {
        Set { storage_slot }
    }

    fn get_2(self, mut context: Context) -> (Context, (Note, Note)) {
        let storage_slot = self.storage_slot;
      
        let notes = read_2_notes(storage_slot);

        let note0_hash = compute_note_hash(notes.0);
        let note1_hash = compute_note_hash(notes.1);

        if is_real(notes.0) {
           context = context.push_read_request(note0_hash);
        };

        if is_real(notes.1) {
            context = context.push_read_request(note1_hash);
        };

        (context, notes)
    }

}

#[test]
fn test_set() {
    let set = Set::new(0);

    let mut context = Context::new();

    let result = set.get_2(context);
    context = result.0;
    let (note0, note1) = result.1;

    assert(note0.is_real == false);
    assert(note1.is_real == false);
}


fn main(x : Field, y : pub Field) {
    assert(x != y);
}

The application panicked (crashed).
Message:  internal error: entered unreachable code: Expected all allocate instructions to be removed before acir_gen

[joss-aztec]

Noting that #1761 fixes the first example but not the second

[joss-aztec]

This appears to be a problem with the flattening pass. The store that immediately following an allocate is being lost:

After Flattening:
fn test_set f9 {
  b0():
    //...
    v53 = allocate
    v54 = load v53

[joss-aztec]

Minimal reproduction of above issue:

fn foo() -> Field {
    let mut x = 0;
    x
}

fn main(cond:bool) {
    if cond {
        foo();
    };
}

[joss-aztec]

After flattening, the store instruction still exists but it has been reordered after its counterpart load, which breaks mem2reg

After Flattening:
fn main f2 {
  b0(v0: u1):
    enable_side_effects v0
    v6 = allocate
    v7 = load v6
    store Field 0 at v6
    v8 = load v6
    v9 = not v0
    enable_side_effects u1 1
    v11 = mul v9, v7
    store v11 at v6
    return 
}

[joss-aztec]

Reopening this issue as tracking the latter issue. (Was automatically closed by PR)

[jfecher]

Looks like this is a result of the flattening pass trying to track stores that were used across branches. It is breaking here when it tries to load the previous value of the store for reference but there was no previous value since the allocation also occurred in the branch.