Implement WGSL uniformity analysis

[jimblandy]

Naga should implement the uniformity analysis introduced in gpuweb/gpuweb@0561a0ee.

I think this would replace the uniformity analysis we have now. It could still be enabled by ValidationFlags::CONTROL_FLOW_UNIFORMITY.

The algorithm given in the spec looks, at first glance, like it should be straightforward to implement on Naga's IR, even though we don't have handles/indices for statements, only expressions.

There are also some more ideas on how to update our analysis in https://github.com/gfx-rs/wgpu/issues/4320.

Items to check:

• [ ] DISABLE_UNIFORMITY_REQ_FOR_FRAGMENT_STAGE should be removed.
• [ ] Uniformity should be required for workgroupUniformLoad.
• [ ] Non-uniformity in unreachable code (e.g. additional statements after return / break / discard / continue) should be permitted.

[ErichDonGubler]

Firefox downstream tracking issue: https://bugzilla.mozilla.org/show_bug.cgi?id=1850044

[afd]

My research group is doing some work on WGSL uniformity analysis and we have a way to test support for uniformity analysis in WGSL implementations.

@jimblandy would there be interest in us bringing this to bear on uniformity analysis in Naga, or would it still be too early?

From a quick play with Naga it seems that:

• Uniformity analysis for fragment shaders is disabled by default:

const DISABLE_UNIFORMITY_REQ_FOR_FRAGMENT_STAGE: bool = false;

in naga/src/valid/analyzer.rs

• If I change this to true I get some meaningful error messages for fragment shaders that use derivatives in a non-uniform way.

• Uniformity analysis doesn't seem to do anything for compute shaders with barriers at present - e.g. Naga accepts this shader, which has a non-uniform barrier:

@compute
@workgroup_size(16, 1, 1)
fn main(@builtin(local_invocation_index) lid: u32) {
  if (lid > 5u) {
    return;
  }
  workgroupBarrier();
}

Our approach focuses on compute shaders but would be easy to re-target for fragment shaders if the support there is more complete (and if there's an appetite for this kind of testing, or course).