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

Flatten simple if-else statements in brillig to avoid unnecessary jump statements #6394

Open
TomAFrench opened this issue Oct 29, 2024 · 1 comment

Comments

@TomAFrench
Copy link
Member

Consider the program

unconstrained fn main(active: bool) -> pub Field {
    if active { 2 } else { 0 }
}

This compiles to the SSA

brillig(inline) fn main f0 {
  b0(v0: u1):
    jmpif v0 then: b2, else: b1
  b2():
    jmp b3(Field 2)
  b3(v1: Field):
    return v1
  b1():
    jmp b3(Field 0)
}

This is equivalent to the program

unconstrained fn main(active: bool) -> pub Field {
    2 * (active as Field)
}

which compiles down to the program

brillig(inline) fn main f0 {
  b0(v0: u1):
    v1 = cast v0 as Field
    v3 = mul Field 2, v1
    return v3
}

This is much smaller in terms of bytecode size and more amenable to further optimizations. We should then attempt to find simple if-else blocks similar to this in SSA and flatten them even in the case of brillig functions (we'll likely want to apply the changes made in #6073 as part of this).

This may seem a bit of a contrived example but we make heavy use of small if statements such as these in the sha256 implementation such that these jumpifs make a non-trivial portion of the overall program.

@github-project-automation github-project-automation bot moved this to 📋 Backlog in Noir Oct 29, 2024
@TomAFrench
Copy link
Member Author

Two key considerations here are that we need to make sure that:

  1. The arms of the if-else statement are small enough that executing both branches is preferable to the overhead of the jumpif.
  2. The instructions in each arm are infallible, e.g. we can't pull an array get which may fail out of an if-else to be performed unconditionally.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: 📋 Backlog
Development

No branches or pull requests

1 participant