Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Flattening pass does not handle branches where the merge block is in the then branch. #6620

Closed
TomAFrench opened this issue Nov 25, 2024 · 2 comments · Fixed by #6621
Closed

Comments

@TomAFrench
Copy link
Member

TomAFrench commented Nov 25, 2024

Consider the programs

        acir(inline) fn main f0 {
          b0(v0: u1):
            v1 = allocate -> &mut Field
            store Field 0 at v1
            jmpif v0 then: b2, else: b1
          b2():
            jmp b3()
          b1():
            store Field 2 at v1
            jmp b3()
          b3():
            v5 = load v1 -> Field
            constrain v5 == Field 2
            return
        }

and

acir(inline) fn main f0 {
          b0(v0: u1):
            v1 = allocate -> &mut Field
            store Field 0 at v1
            jmpif v0 then: b2, else: b1
          b2():
            v5 = load v1 -> Field
            constrain v5 == Field 2
            return
          b1():
            store Field 2 at v1
            jmp b2()           
        }

These are entirely equivalent as the only difference is in the second we have inlined b3 into b2. However when we flatten these programs we end up with the results

acir(inline) fn main f0 {
  b0(v0: u1):
    v1 = allocate -> &mut Field
    store Field 0 at v1
    enable_side_effects v0
    v3 = load v1 -> Field
    v4 = cast v0 as Field
    v6 = sub Field 2, v3
    v7 = mul v4, v6
    v8 = add v3, v7
    store v8 at v1
    v9 = not v0
    enable_side_effects u1 1
    v11 = load v1 -> Field
    constrain v11 == Field 2
    return
}
acir(inline) fn main f0 {
  b0(v0: u1):
    v1 = allocate -> &mut Field
    store Field 0 at v1
    enable_side_effects v0
    v5 = not v0
    enable_side_effects v5
    v6 = load v1 -> Field
    v7 = cast v5 as Field // We're now using `not v0` instead of `v0`!
    v8 = sub Field 2, v6
    v9 = mul v7, v8
    v10 = add v6, v9
    store v10 at v1
    enable_side_effects u1 1
    v12 = load v1 -> Field
    constrain v12 == Field 2
    return
}

We must be doing something incorrectly caused by how we're looking for the point at which these two branches merge again. One thing to note is that b2 is the then branch for this if-else branch so we end up in a situation where we're inlining the merge block before we've inlined both of the branching blocks:

vec![self.branch_ends[if_entry], *else_destination, *then_destination]

@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Nov 25, 2024
TomAFrench added a commit that referenced this issue Nov 25, 2024
@TomAFrench TomAFrench changed the title Flattening pass does not handle branches where the merge block is in one of the branches. Flattening pass does not handle branches where the merge block is in the then branch. Nov 26, 2024
@TomAFrench
Copy link
Member Author

TomAFrench commented Nov 26, 2024

The real problem with the above is that because the merge block is the same as the then block, we try and add the new blocks [b2, b1, b2] to the work queue, however due to deduplication we instead get [b2, b1]. This means that when we take then next block off of the work queue we pick up the else block and treat it as if it were the then block. We apply the incorrect condition within this block which causes the store to be predicated incorrectly.

@TomAFrench
Copy link
Member Author

Marking this as closed by #6621 as it prevents us from outputting invalid code. If we want to allow branches merging in the then branch then we can do this as part of #6624

@TomAFrench TomAFrench linked a pull request Nov 26, 2024 that will close this issue
5 tasks
@github-project-automation github-project-automation bot moved this from 📋 Backlog to ✅ Done in Noir Nov 26, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: ✅ Done
Development

Successfully merging a pull request may close this issue.

1 participant