feat: Handle no_predicates attribute

[vezenovm]

Description

Problem*

Resolves #4911 and #4688

Summary*

We recently included the #[inline(never)] attribute to enable developers to optimize codegen. This has now been switched to the name no_predicates. The main use-case in mind is for circuits in issue #4688 where inlining a function with heavy array operations when dependent upon witnesses is not always ideal. Specifically when the function being inlined does not need to rely on the predicate for correctness.

Originally I had in mind to delay inlining all the way to after ACIR gen and inline the ACIR artifacts. However, this feels overly complex now as we have all the infrastructure to inline functions as we wish during SSA, we could just need to delay the inlining of certain functions to happen after flattening. This PR does exactly what was just mentioned.

For example, the new test no_predicates_numeric_generic_poseidon gave these results when poseidon_hash was not marked with #[no_predicates]:

While when poseidon_hash was marked with #[no_predicates]:

Additional Context

Documentation*

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[vezenovm]

Look to be getting some panics still so can hold off on a review

[vezenovm]

I was thinking to perhaps change the name of the attribute to something more specific to the Noir codegen. Like #[inline(post_if_flatten)] or #[inline(post_flatten)]. It is a bit more verbose but it gets across better what is actually happening and how it provides an optimization when writing circuits. Documentation should also help with any knowledge gap (which will come in a follow-up).

[jfecher]

Is this PR ready for review now?

#[inline(post_if_flatten)] or #[inline(post_flatten)]. It is a bit more verbose but it gets across better what is actually happening and how it provides an optimization when writing circuits.

I definitely think that we shouldn't call it #[inline(never)] if it does actually get inlined eventually.

Also, can you elaborate more on why inlining after flattening fixes #4688? It seems somewhat odd to me - like we're missing a more direct optimization or fix instead.

[vezenovm]

Is this PR ready for review now?

Yeah it is

[vezenovm]

I definitely think that we shouldn't call it #[inline(never)] if it does actually get inlined eventually.

We can discuss further during scrum and I can change it as part of this PR or a follow-up. I was leaning towards the more verbose post_if_flatten.

Also, can you elaborate more on why inlining after flattening fixes #4688?

We are getting a big blow-up for poseidon due to how predicates need to be handled when working with large arrays and complex logic. Each call to poseidon is inlined before flattening thus causing everything inside of poseidon also needing to be flattened. In some cases (such as finding a hash) we don't need to worry about handling a predicate appropriately in the failure case and just want the result from the passing case.

Our black box functions like pedersen_hash do not have a blow-up like this as they lay down a single "Call" instruction and do not inlined anything. We then only flatten the result of the hash if it is used outside of the if statement.

For this program using pedersen_hash:

pub fn pedersen_hash<N>(inputs: [Field; N], hash_index: u32) -> Field {
    dep::std::hash::pedersen_hash_with_separator(inputs, hash_index)
}
fn main(
    to_hash: [[Field; HASH_LENGTH]; NUM_HASHES],
    enable: [bool; NUM_HASHES]
) -> pub [Field; NUM_HASHES + 1] {
    let mut result = [0; NUM_HASHES + 1];
    for i in 0..NUM_HASHES {
        let enable = enable[i];
        let to_hash = to_hash[i];
        if enable {
            result[i] = pedersen_hash(to_hash, 0);
            // result[i] = poseidon_hash(to_hash);
        }
    }
    result
}

We have the following SSA:

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0(v0: [[Field; 10]; 2], v1: [u1; 2]):
    v55 = array_get v1, index u64 0
    v56 = array_get v0, index u64 0
    v57 = call pedersen_hash(v56, u32 0)
    enable_side_effects u1 1
    v59 = cast v55 as Field
    v61 = mul v59, v57
    v62 = array_get v1, index u64 1
    v63 = array_get v0, index u64 1
    v64 = call pedersen_hash(v63, u32 0)
    v65 = not v62
    enable_side_effects u1 1
    v66 = cast v62 as Field
    v67 = cast v65 as Field
    v68 = mul v66, v61
    v69 = mul v67, v61
    v70 = add v68, v69
    v71 = mul v66, v64
    return [v70, v71, Field 0]
}

Replacing pedersen with poseidon_hash without an inline attribute leads to a massive SSA (where I will not post it as it is up to 12k values). Enabling the developer to inline post flattening allows them to write their own black box function call in a way, and escape some of the compiler's codegen.

It seems somewhat odd to me - like we're missing a more direct optimization or fix instead.

I definitely think it would still be good to optimize array merges either way. However, this felt like it could be its own issue and I'm not sure if it would still provide as meaningful optimization that this inlining attribute provides. It actually felt kind of natural to me that Noir would start to adopt codegen attributes that can provide optimizations to the user.

[jfecher]

Enabling the developer to inline post flattening allows them to write their own black box function call in a way, and escape some of the compiler's codegen.

The tradeoff of this would be if there are failing constraints or similar inside the function call then they'd still fail even if the call was wrapped by an if false { ... } though, right? I think we should discuss this more if so because that sounds very confusing to me if that is the case.

I definitely think it would still be good to optimize array merges either way. However, this felt like it could be its own issue and I'm not sure if it would still provide as meaningful optimization that this inlining attribute provides. It actually felt kind of natural to me that Noir would start to adopt codegen attributes that can provide optimizations to the user.

Right, that comment wasn't in reference to array merges which barely affected the original issue constraint count wise. I also don't disagree with adding more compilation/optimization annotations. I was just thinking that this particular solution seemed indirect and I was wondering if there was a more direct way to optimize out predicates we're missing in general. Assuming my if false { ... } question above is wrong, one issue with this approach would be that it requires users to know about this somewhat niche problem and apply an annotation fix manually. That isn't the end of the world but it did make me wonder if there was an alternative.

[jfecher]

The tradeoff of this would be if there are failing constraints or similar inside the function call then they'd still fail even if the call was wrapped by an if false { ... } though, right? I think we should discuss this more if so because that sounds very confusing to me if that is the case.

I wonder if we can have an optimization or change semantics in a way that we can only apply predicates to results in general instead of every intermediate step. Maybe we'd need to check for side-effect boundaries and delay it until then? Or group up side effects to perform all at once later somehow? Not sure.

[jfecher]

Looks like:

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

#[inline(never)]
fn foo() {
    assert(false);
}

with x = false fails

[jfecher]

Discussed in standup:

• Name change: I think no_predicates or similar would be good since it is more direct in the reason someone may apply the annotation instead of just referencing how we implement that behavior via inlining later on.
• it seems the if x { foo() } example may only be failing because of a bug in the remove enable side effects pass. We can fix that separately.
• I was hesitant at first but I suppose it's fine in general to add opt-in optimization annotations that can potentially break programs if used incorrectly. The opt-in and (eventually) documentation around them will be key here.

[vezenovm]

• Name change: I think no_predicates or similar would be good since it is more direct in the reason someone may apply the annotation instead of just referencing how we implement that behavior via inlining later on.

I ended up going with no_predicates. It most clearly conveys what is happening to the user and the unsafe nature of using the attribute.

[jfecher]

no_predicates_is_entry_point is a bit of an awkward name but I've no better suggestions at this point and it's not worth blocking over

👍

[vezenovm]

no_predicates_is_entry_point is a bit of an awkward name

Yeah I thought the same but was unsure about a better one and didn't feel the need to make some context struct for one flag.