Naga front ends do not properly short-circuit `&&` and `||`

[jimblandy]

NOTE: description edited 2024-4-16, so much of the following discussion may look irrelevant

The WGSL specification says that a && b only evaluates b if a is true, but Naga generally will always evaluate both.

The following input:

fn h() -> bool {
  return f() || g();
}

produces the following output WGSL:

fn h() -> bool {
    let _e0 = f();
    let _e1 = g();
    return (_e0 || _e1);
}

The call to g is hoisted out to a statement and made unconditional, which is incorrect.

This means that even though most backends turn Naga IR's BinaryOperator::LogicalAnd and BinaryOperator::LogicalOr into short-circuiting operations in the target language, it doesn't help because the front end has already hoisted the right-hand side, which ought to be conditional, out into its own unconditional statement.

[JCapucho]

I can confirm glsl short circuits

[expenses]

According to https://devblogs.microsoft.com/directx/announcing-hlsl-2021/#logical-operator-short-circuiting, hlsl only short-circuits in the 2021 version.

We could store this information in Naga IR's BinaryOperator ala:

// naga/src/lib.rs

pub enum BinaryOperator {
    // ...
    LogicalAnd { short_circuits: bool },
    LogicalOr { short_circuits: bool },
}

For reference, here's the relevant code in the SPIR-V backend:
https://github.com/gfx-rs/naga/blob/cc985396dadc95039a0f3d5cfc818a6b4d5eba6b/src/back/spv/block.rs#L615-L616

[adeline-sparks]

I started looking in to this as it seemed like an interesting issue for learning Naga. After doing some reading, I'm starting to think the issue lies with the front ends. When parsing a && b in both wgsl and glsl, b is emitted unconditionally, which I think is the actual origin of the incorrect short circuiting behavior:

// master WGSL output for `let x = foo() && bar();`
let _e0 = foo();
let _e1 = bar();
let x = (_e0 && _e1);

I'm working on a PR to introduce an IR branch and emit b conditionally:

// new WGSL output for `let x = foo() && bar();`
var local: bool;
let _e0 = foo();
if _e0 {
    let _e1 = bar();
    local = _e1;
} else {
    local = false;
}
let x = local;

I think this logic needs to be present in the wgsl and glsl frontends, and only in the hlsl frontend when parsing the 2021 edition.

Does this seem like the right approach? Are there performance issues with introducing an if statement and local variable for each operator?

[jimblandy]

Yes, I think this does need to be handled in the front end.

In Naga IR, function calls are not expressions, they're statements. This is explained in the top-level comments in lib.rs, but roughly speaking, expressions are never supposed to have side effects, and function calls can have side effects, so they get lifted out into independent statements. So the translation of WGSL foo() + bar() (ordinary operator +) into Naga IR would be something like:

let foo_result = foo(); // Statement::Call
let bar_result = bar(); // Statement::Call
etc = foo_result + bar_result // two Expression::LocalVariables and one Expression::Binary

This means that there's no reasonable way for back ends to apply the short circuiting when they see BinaryOperator::LogicalAnd: if the right operand includes any side effects, they've already taken place.

So your conclusion - that the front end needs to turn a && expression into statements - seems correct.

How would you translate longer chains like a() && b() && c(), or (a() && b()) || (c() && d())?

Makes sense. I hadn't taken a good look at the IR yet by the time I made my suggestion; my bad. I agree with this approach.

[JCapucho]

@jimblandy I thought the IR was supposed to follow wgsl semantics and the backends would do the necessary transformations.

If that's the case then this should be handled in the backends because wgsl defines short circuiting for the operators, also both glsl and msl define short circuiting in it's semantics, so only 2/5 backends need this transform and I think it doesn't make sense to add a possible performance penalty to the other ones.

[adeline-sparks]

I'm not sure what "follows wgsl semantics" means exactly, but this is how short-circuiting operators get lowered into any IR that lacks expression side effects. All frontends of languages with side effects in their expressions will need this transform, although we could consider omitting the branch in specific cases if there are no possible side effects on the RHS. My thought is that GPU compilers probably do the same transform in their IRs anyway and then optimize out the branch later, but I'm not sure of this and if the compilers do care about if statements vs short-circuiting operators, it wouldn't be too hard to make this slightly smarter. It could also be worthwhile to improve compilation time.

[JCapucho]

I'm not sure what "follows wgsl semantics" means exactly

The IR is supposed to mirror wgsl, including the semantics of it's operations as defined in the wgsl specification.

but this is how short-circuiting operators get lowered into any IR that lacks expression side effects

We don't know the internal IR of the graphics device so we must design around the interfaces provided to us, and in this case only 2 of the supported backends don't support short-circuiting, so I think it's better to make the transformations on those and let the others properly encode the operation.

All frontends of languages with side effects in their expressions will need this transform

We can do it in the backends :)

although we could consider omitting the branch in specific cases if there are no possible side effects on the RHS.

naga doesn't optimize

My thought is that GPU compilers probably do the same transform in their IRs anyway and then optimize out the branch later, but I'm not sure of this and if the compilers do care about if statements vs short-circuiting operators

It's not our job to guess what the compiler does, that in itself would be impossible because there are many and they target many different architectures, we should just encode the program as closely as possible to souce.

it wouldn't be too hard to make this slightly smarter. It could also be worthwhile to improve compilation time.

I doubt any compiler spends a significant amount on this transform, and even if some does another could not have the transform and optimizing the branches to a short-circuit take more time.

This is all speculation, so that's why we should just encode as closely to source as possible and let compilers do their job.

[adeline-sparks]

How can you do this in the backend without changing the semantics of the shader? None of the current backends "support short circuiting" because our IR itself does not support short circuiting.

[JCapucho]

The IR implicitly assumes short circuiting, uniformity analysis might not be correct but that's another issue, and both glsl, MSL, and wgsl have short circuiting