uniformity analysis + basic tail-branching

(examples in GLSL, forgive me)

float CalcValue(float v) {
    // piecewise linear function with points 0.2, 0.5, 1.4
    if (v <= 0.5)
        return mix(0.2, 0.5, v * 2.0);
    else
        return mix(0.5, 1.4, (v - 0.5) * 2.0);
}

in vec2 vTexCoord;
in vec4 vColor;

void main() {
    float mult = CalcValue(vColor.a);
    vec4 texColor = texture(uSampler, vTexCoord.xy) * mult;
    gl_FragColor = texColor;
}

This fails analysis, because return inside CalcValue() causes divergence -- the return doesn't force the branch to fully reconverge. This can be fixed like so:

float CalcValue(float v) {
    // piecewise linear function with points 0.2, 0.5, 1.4
    float ret;
    if (v <= 0.5)
        ret = mix(0.2, 0.5, v * 2.0);
    else
        ret = mix(0.5, 1.4, (v - 0.5) * 2.0);
    return ret;
}

but it feels clunky. The other hack is to wrap the call in an if (true) to force reconvergence:

    float mult;
    if (true) mult = CalcValue(vColor.a);

These both work, but they feel clunky, and it's hard for someone to understand the behavior. I have no suggestions for how the language design should be changed to handle this.

@jrprice

@jrprice fyi

I agree this is annoying.
It turns out that underlying platforms don't force reconvergence upon function return.
We see that behaviour in the wild.

So the analysis surfaces that non-reconvergence.

I found a small example of reconvergence not occurring at function call boundary: #954 (comment)

Are we convinced that the if (true) {} will reconverge, is the thing? I don't see why that necessarily would be true.

Are we convinced that the if (true) {} will reconverge, is the thing? I don't see why that necessarily would be true.

I had exactly the same question about a decade ago working on OpenCL. So this is a bit of deja vu for me.

When there are specs that get specific on this issue (like GLSL and SPIR-V), the answer is "yes".

When you ask IHVs for what they promise, the answer is "yes". As an example, Intel GPUs have "branch diverging", "branch converging", and "break" instructions, explicitly to support structured control flow. At some point you have to trust their toolchains work. At least you know where the bug is, if there is one.

For other APIs and flows, a lot is left unsaid.

Testing is best effort but can't be exhaustive.

The Metal API contract is that reconvergence happens at the } character, and a call that doesn't discard doesn't affect the uniformity around it.

Yesterday during the call, the group started going in the direction of saying the first example in the OP is legal (which may require polyfilling on some backend APIs/languages), but Google wanted an additional week to think about it before we resolved.

WGSL meeting minutes 2022-06-14

DN: Computers don’t work the way you think they do. If you believe the world is inlined always, then this simplifies down, but I’m not sure we can rely on it.
DN: If you introduce subgroups into this, I’ve demonstrated that you don’t get subgroup reconvergence at end of function. We know it’s annoying, but it’s the rule.
DN: We have spec’d what we can.
MM: When we discussed whether returns reconverge, we said “no”, and said we’d file an issue. It’s likely that programmers’ expectations don’t reflect what we do today. We should try to match programmer expectations, unless that’s too hard.
DN: I agree that there’s a mismatch.
DS: What do we do now? While we can rewrite e.g. with local variables, I worry that we might cause a performance issue in doing that rewrite.
Options:
- 1. We do what we have now. All burden is on users to adapt their shader.
- 1. Add annotation like @reconverge to ask the compiler to rewrite it to ensure a single return.
  - 2b. Inverse: annotate the “please don’t restructure this, at risk of triggering uniformity error”.
- 1. Compiler detects Is a clean break from WebGL really necessary? #2 but does the rewrite automatically. Potentially risk performance pit because you use extra variables and control flow.
MM: So the rewriting would rewrite return V into storing V into a return function local var, and break back out?
DS: Yes
MM: Does any compiler do this?
DS: Tint no
KG: Naga no
TR: DXC has this
DN: Why?
TR: It was useful to someone in some cases. It’s called “structurize return”
(trying to find it) dxc -T ps_6_0 -opt-enable structurize-returns
Other links:
- https://github.com/microsoft/DirectXShaderCompiler/blob/main/lib/Transforms/Scalar/StructurizeCFG.cpp
- https://github.com/KhronosGroup/SPIRV-Tools/blob/master/source/opt/merge_return_pass.h
- https://github.com/microsoft/DirectXShaderCompiler/blob/main/tools/clang/test/HLSLFileCheck/hlsl/control_flow/loops/structurize_multiexit_crash_do.hlsl
KG: Do we need this in v1? People have a workaround.
MM: I think programmers will get caught by this a lot, so we should probably do this in v1.
DN: I want another week, I want AB to weigh in.
MM: Is this a whole-program problem?
DN: Yes.
TR: So you’re saying the control flow uniformity is leaking? So e.g. the instruction pointer might desync.
int foo() { if (tid % 2 == 0) { return 4; } else { return 5; } int bar() { foo(); barrier(); }
- The barrier() is legal in HLSL
TR: HLSL does reconvergence; as if predicated execution across the entire wave.
DS: So it’s just SPIR-V that doesn’t reconverge coming out of functions?
DN: Yes
DN: So on the table is that we give the programmer this tool, and UAs will polyfill this as needed.
??: We also need to decide implicit or explicit
Come back next week

WGSL meeting minutes 2022-06-21

DN: last week, stated MSL and HLSL have wave reconvergence at end of structured block including function call. Doesn’t fit intuition on how drivers are structured. Working on example to show what’s happening. Based on VK subgroup reconvergence test and ported to DX12. We think drivers like Nvidia and others have same backends on compiler stack and think Vulkan behaviour would appear on DX12. Haven’t seen docs to explain that. In MSL close brace was started to do the same thing. Don’t recall filing an issue, but there was an issue with metal team filed?
TR: Wanted to try to clarify about reconvergence at end of function, trying to say logically all the threads that were active before should be active after function call. Doesn't’ mean converged but visibly a wave operation after function call they have to be converged. In other words, implementations are free to diverge until an operation that would expose that divergence is performed.
AB: So wave ops are like barriers? SPIRVs don't’
TR: The model is the wave runs in lock step. When wave op happens if the behaviour is different then if running in lock step then not according to spec
KG: If that’s true, isn’t that what barriers are for?
TR: Barriers synchronize the waves in a group
KG, a group of waves
TR We don’t have a wave barrier, as it’s assumed the wave is in lock step.
DN: Point of comparison, subgroups in opencl had a subgroup barrier added to ensure all the threads got to that spot. Saying, in HLSL model acts as if any time you could sense the divergence there is a barrier. Any thread still active at all would have to come back and participate in that group op.
TR: That’s right. If you have a wave op you have to insert the logical wave barrier (you said thread group)
MM: For comparison, metal requirements are weaker. Different policy for ops like barriers and derivatives then wave ops. For wave ops it’s insert and if some divergence can be observed via wave ops that can’t be observed from barriers or derivatives.
DN: Can metal force the reconverge like HLSL?
MM: Not sure. Haven’t spent time thinking about wave ops.
DN: Concerned we’ll have an execution model that does not map to hardware. Dangerous territory. Question for Apple, how do you compile HLSL to metal in a portable way.
MM: We don’t compile hlsl
TR: If you have a loop and a wave op in a loop could you have threads in the loop in different iterations doing the wave op. That’s not allowed in HLSL. In HLSL if the thread is active then it has to be in that wave op. Does metal allow divergence of threads in that subgroup to the point of threads being in different iterations?
MM: Would have to see example to answer.
TR: Another example, the convergence case of wave op after function or block diverging will that wave op happen many times on different subgroups of threads because they reach it at different times?
MM: For that case, if I understand, a function call that inside has divergence and there are [???] in the divergence and then after you do a wave op?
TR: Could be an if that has expensive divergent code. Could thread that skip do wave op while other threads in the if?
MM: In spirv those are different constructs. Metal doesn’t have an opjoin. Talking about a return in SPIRV that skips the op join.
KG: Given others don’t skip it, should we just not skip it? Said there maybe overhead, right?Have to assign to function local thing and then return at the end of the function. That’s the transform?
MM: The argument mentioned last time, which I think is the strongest is don’t think programmers mental model for GPU software involves different policies for returns
DN: Trying to expose what hardware is doing, not invent new stuff. Don’t lie to the programmer
KG: That’s the fiction we’re in. Proposal is what if we can help the programmer do the thing they want at low enough cost. It sounds like this is just how other systems work, there is no way to not join. Seems like good indication that if there is something to gain it isn’t sufficient to make folks care. Only question, how bad is this to implement as a transform assuming it’s likely it’s a spirv-only transform.
MM: Implementation of transform exists in spirv. Not an implementation cost and integration cost.
KG: Yes, but spirit of concern is complexity of having our code do what we want, not how we go about doing that.
MM: Ok.
KG: If one answer is ship spirv-cross, that’s not useful.
MM: Suggesting lifting a piece, not all.
KG: How do we feel about this,do we want to volunteer to do this work? Do we think the tradeoff is worth it to match what devs are expecting even though in spirv there is a case where it’s less optimal?
JB: Lifting in spirv-cross, or pieces of spirv-cross is not feasible due to different IRs and converting back and forth. Would have to re-implement ourselves. What do spirv users do when they want to write a function where they can use interlane operations after the function returns? Do they normally re-write their functions to have a single op return instruction?
KG: Two options, do an get correct behaviour or don’t and sometimes get correct behaviour
DN: And they don’t notice.
KG: Unfortunately a lot of the uniformity protections protect against it might go wrong vs it will go wrong
JB And the transform is to take the early returns and take the tails and make them conditional instead of opreturns
KG: And hoist the return
JB: Yea, store in a local
BC: JP wrote a transform for tint which we think is sufficient and is very well tested
- https://dawn-review.googlesource.com/c/dawn/+/93660/5/src/tint/transform/merge_return_test.cc
JB: We do similar gymnastics. Think it’s implementatable. If all the implementations take same approach of rewriting spirv then i think this is something that FF can take on. Already doing various things like this.
AB: How often do we need to be right about reconvergence for the guarantees in the spec for that work to be valuable? Know that not everything works but it tends to happen in cornercases you don’t come across most of the time. What we release in 1.0 might be difficult to observe if we release subgroups/wave ops it becomes easier ot observes. At what level of going wrong is it a spec issue?
KG: Interesting question
MM: Barrier after function call and barrier could deadlock, seems like a bad time
KG: But, how likely is it to deadlock. Would be sad to ship something where it works by luck even if we don’t have to be that lucky. It’s sad when looking at a system with older drivers and there is no formal protections we can use to get the thing we want and would like to avoid scenario where we don’t have sufficient protection there. That said, folks do have a workaround if they try it and it doesn’t work. But, if we’re all on board to do the transform, can just do that knowing there is a gap we’re filling. Good point we don’t need to be perfect
TR: Don’t really know what the difference between doing the transform and doing an OpJoin is?
MM: Can’t just say OpJoin wherever you want.
JB: Really just imposed a tree structure that fits into block graph but it’s really a tree. You can recover the tree from the graph of blocks.
MM: Another way to say is in order to stick OpJoin where needed all of the leaves of the tree would have to re-converge to hit it according to spir-v rules and you’ve just built the transform we’re talking about
TR: So, if around function call the implicit join may not join what diverged in the function call just what diverged for the if? Is that right?
AB: Theoretically, everything that entered the merge instruction that leaves through the merge block will reconverge at the merge block. If warp in if true not confidence the driver will just remove that and fake reconvergence
MM: Doesn’t describe the function issue
AB: Not what he’s asking if
JB: Wrap all functions in an if
TR: Not sure of limitations here, and if there are problems with an if in code and a function call and the function has divergent returns how is that dealt with today?
MM: Would be an alternative implementation where one would have all the control flow reconverge in the function, the other would be wrap all function calls with if(true). Implementations could pick what they want to do.
KG: Can we sign up to have reconvergence happen and we will promise we will make in spirv or if we can’t make work it will work enough so folks won’t be mad where it doesn’t work. We’ll claim we will do it, especially as it relates to uniformity, so they can do if’s in uniformity and not have to hoist themselves. Feel like we should do that as we think we can do it. Going to say we’re going to do taht.
JB: If just spirv we can handle that.
AB: Just want known reservation that don’t know how well this has been tested. When we looked in spirv it didnt’ work. Doesn’t give tonne of confidence in other backends as it’s usually the same folks working on other drivers. We’re perpetuating an illusion around errors that we introduction to make folks lives easier. Almost circular in that we want to get rid of uniformity analysis errors by working around errors.
KG: Important distinction, sounds like you don’t agree with what proposed. Not that we paper over but that we do the transform to give maximila hope they will reconverge. Driver might make it impossible but we’ll try our hardest, saying in WGSL we’ll try hardest to give reconvergence here and also update our uniformity analysis to reflect that. Not promising anything new, we’re going to do the transform the use would have to do anyway when uniformity rejects. They have to hoist the return and we’re just going to do it and if that doesn’t give reconvergence in the driver then there is no hope but we’ve done our best for the driver.
MM: What AB said it doesn't’ work, what is ‘it’?
AB: We looked at reconvergence on various drivers and it didn’t work for what was promised now. If i add a CTS case I know will have driver bug, is that driver a non-conformat and need to be denylisted?
MM: Those tests are test that the spirv guarantees were not followed by hardware?
AB: Yes.
MM: For later case, talked in WebGPU case about driver bugs in CTS. A lot of arguing but resolution I believe.
KG: Think we can give assurances, I view it as we should surface the guarnentees underlying implementations have and make them eaiser to use and if drivers break guarantees we should respond on a case by case basis. If we find drivers have no guarantees we can come back to drawing board but that’s a bad sign for the spirv requirements. Don’t know how to operate if all the tools are broken. Don’t have a strong answer for how we should design then.
MM: Question is, are the tools are so broken should we behave as if they don’t exist? Think the answer is now
KG: Should surface guarantee in API and respond to make it so.
DN: Ask MM to repeat Metal guarantee, on wave reconvergence group operations do not force reconverge but derivative do. If only targeting d3d and not metal would we only care about derivative requirements?
MM: Not sure about not care part?
DN: Would we have to spe canything with uniformity and derivatives?
MM: Derivative after function where function has divergent returns the derivative after is legal.
KG: And do that by reflecting that in the uniformity analysis and have it pass
TR: So, derivative ops force reconvergence if we have to do this transform to get reconvergence?
DN: If metal doesn’t need transform and HLSL doesn’t and because discard is demote then if only targeting D3D and Metal then we would not need uniformity at all for derivates
TR: I see
AB: That’s impossible
MM: Need to know derivative in non-uniformity control flow
AB: Can violate condition of if to force reconvergence down branch
TR: derivative only needs quad convergence not wave convergence
KG: Talked about one level uniformity but technically 2-3
MM: Now unobservable identical but may not be in the future.
KG: Continue next week.

We discussed this again internally.

The proposal on the table is that:

SPIR-V backends: Merge the returns inside a function, to avoid this uniformity issue.
HLSL and MSL are not supposed to need a merge-return transform.

We can accept this solution until testing proves otherwise. We think it's probably hard to exercise a failure with the current language features. We think we'll need to revisit this when we consider subgroup operations post-v1.

My understanding of how different backend languages guarantee reconvergence at the end of a structured if/ structured loop:

Language	wave reconvergence sensed at subgroup operation	implicit derivative
MSL	N	Y
HLSL	Y	Y
SPIR-V / Vulkan	N	N

WGSL meeting minutes 2022-06-28

DN: Google agrees to implement merge-return in SPIR-V backends. Trust the experts in MSL and HLSL that things are supposed to work as promised. Accept this solution until testing proves otherwise.
DN: Talked off line and willing to go with what others were asking to do. For SPIR-V do merge return transform so problem goes away. So we change uniformity analysis to match. MSL and HLSL it should just work. We’re willing to go with this and defer to see if we can break it but not blocking for now.
AB: Think we should invest some effort in getting good testing for uniformity code.
KG: Alright. Other thoughts? … That’s consensus then

Make function returns reconverge

Make function returns reconverge (#3254)

Make function returns reconverge (gpuweb#3254)

Navigation Menu

Repository navigation

uniformity analysis + basic tail-branching #3007

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

uniformity analysis + basic tail-branching #3007

Description

Activity

dj2 commented on Jun 2, 2022

dneto0 commented on Jun 3, 2022

dneto0 commented on Jun 3, 2022

magcius commented on Jun 3, 2022

dneto0 commented on Jun 6, 2022

litherum commented on Jun 15, 2022

litherum commented on Jun 15, 2022

kdashg commented on Jun 19, 2022

kdashg commented on Jun 23, 2022

dneto0 commented on Jun 28, 2022

dneto0 commented on Jun 28, 2022

kdashg commented on Jun 29, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions