Incorrect branching surrounding WaveReadLaneAt when shader model cs_6_6

[noahwhygodwhy]

Description

Branching around WaveReadLaneAt has incorrect behavior when compiled with cs_6_6

Steps to Reproduce

cs_6_5 version: https://godbolt.org/z/sbK7hPGbj
cs_6_6 version: https://godbolt.org/z/66nPod54s

(same code, just shader model changed)

So, this code is not as simple as I want, but is as simple as I could get it. The idea is, we have groups of 16 threads that are all one one task, but we don't want them doing duplicate memory loads, so we keep track of the groups, and lane0 does the load, and then shares it with waveReadLaneAt().

Actual Behavior

I'm not perfect at reading dxil, but as far as I can tell, what's happening:

For the cs_6_5 version:

• Lane 0 of each group of 16 threads does a load from a location
• Each thread does a waveReadLaneAt to read their groups lane0 val
• Lane 0 of each group then stores its 0 at it's original location (this isn't important, but we need another "if(laneIndex == 0)" statement that can't be optimized out)
• Each lane stores the value given to it by the waveReadLaneAt, which comes from each laneGroup's lane0

Howeva ☝️

For the cs_6_6 version:

• It BRANCHES based on laneIndex == 0?
• every thread that isn't lane index 0 in the group reads lane 0's value...that hasn't been loaded yet?
• lane 0 threads then do the load. And then do the waveReadAtLane, which just reads their own value, but it's at least loaded this time
• Each lane stores it's "val" but everything but the lane0's in the lane groups have the wrong value (uninitialized?)

Environment

• DXC version - dxc Trunk on godbolt
• Host Operating System - godbolt

[simondeschenes]

I am not sure this is actually a bug.

From the point of view of the compiler, only lanes that are doing the load needs to wait for the load to be completed before moving to the next instruction. The other lanes can't just call WaveReadLaneAt immediately.

The compiler doesn't actually know that WaveReadLaneAt accesses data from other lanes. In fact, DXC compiles assuming that that there is a single thread alone. For the compiler, WaveReadLaneAt is just an extern function call. There isn't any concept of some other lanes or thread to the optimizer. The optimization seems valid from the optimizer's point of view. It doesn't know there is more than one lane and it doesn't care. The language is designed like you are writing for a single thread and it is compiled the same way.

You have to explicitly tell the compiler to stop if there is any data shared between lanes or threads. For operations that reads "shared" data between lanes or threads, there are barriers. There is one for groupshared accesses, one for "device memory" accesses and one that does both. A buffer Load is a device memory access.

The only way prevent the compiler from doing this optimization is to add a barrier in the code yourself. With a DeviceMemoryBarrier() call, it will tell the compiler to wait on all device memory operations (such as Load) before moving to the next instruction.

Adding the barrier leads to the expected behavior. I don't think you need WithGroupSync because you are not synchronizing over the whole thread group, only with the lanes of the current wave that are progressing in lockstep.

RWByteAddressBuffer buff : register(u0);
RWByteAddressBuffer buff2 : register(u1);

[numthreads(64, 1, 1)]
void main()
{
    const uint laneGroupSize = 16;
    const uint laneIndex = WaveGetLaneIndex() % laneGroupSize;
    const uint groupIndex = WaveGetLaneIndex() / laneGroupSize;
    
    uint val;
    if(laneIndex == 0)
    {
        val = buff.Load(groupIndex*sizeof(uint));
    }

    DeviceMemoryBarrier();

    val = WaveReadLaneAt(val, groupIndex * laneGroupSize);
    if(laneIndex == 0)
    {
        buff.Store(groupIndex*sizeof(uint), 0);
    }
    buff2.Store(WaveGetLaneIndex()*sizeof(uint), val);
}

Why is it different between shader model <= 6.5 and >= 6.6?
I don't know.

I may be wrong, but that is how I understand how DXC works.

[noahwhygodwhy]

Simpler example. What about things like WaveActiveSum()? I would expect every single active thread in the wave (that hasn't explicitly returned ) to participate. Like the following, where every thread contributes 1 to the sum: https://godbolt.org/z/rdMenW9EG

And you can see somewhat consistent behavior in cs6_5, where every thread contributes it's "val" to the sum: https://godbolt.org/z/Kz3715nxc
But the same branching happens with cs6_6, where the threads that take one branch all sum, and the first threads in the lanegroup have their own sum, while the WaveActiveSum() call is in global scope within the shader. https://godbolt.org/z/n1Yn581f3

Afaik, the point of wave intrinsics is to do things within a wave between threads without having to have barriers or synchronization. Per the "Wave Intrinsics" glossary page from this repo. . This is the reason that we have to have branching in the first place

[noahwhygodwhy]

I feel, and I'm struggling to find anything in the spec one way or another, that

The compiler doesn't actually know that WaveReadLaneAt accesses data from other lanes

Is explicitly wrong. It has "WaveReadLaneAt" in the name. The implication is that it is reading from other lanes?

[simondeschenes]

Well, the compiler has no idea what a lane is and that there are other lanes or threads.
It is just extern function calls as you can see here:

%7 = call i32 @dx.op.waveReadLaneAt.i32(i32 117, i32 undef, i32 %6), !dbg !120

I will replace WaveReadLaneAt with ExternFunc to make that more obvious.

This code:

   template<typename T>
   T ExternFunc(T a, uint b);

...

    uint val;
    if(laneIndex == 0)
    {
        val = buff.Load(groupIndex*sizeof(uint));
    }
    val = ExternFunc(val, groupIndex * laneGroupSize);

Is functionally the same as:

   template<typename T>
   T ExternFunc(T a, uint b);

...

    uint val;
    if(laneIndex == 0)
    {
        val = buff.Load(groupIndex);
        val = ExternFunc(val, groupIndex * laneGroupSize);
    }
    else
    {
        val = ExternFunc(val, groupIndex * laneGroupSize);
    }

This is also why the standard waterfall loop code just plain doesn't work.
See: #6721

There is a hack inside of the compiler that recognize the pattern in DXC and adds a condition to the break by comparing a constant with something from a fake internal constant buffer. See dx.break.cond.

It prevents the compiler from removing the loop completely. It only applies to pixel and compute shaders though.
For vertex shaders and mesh shaders, that is still completely broken:

for (;;) {
      int uniformIndex = WaveReadLaneFirst(varyingIndex);
      if (uniformIndex == varyingIndex) {
          //...
          break;
        }
    }

This is correct code that works knowing that the compiler doesn't have any idea that there are multiple threads or lanes:

    bool active = !IsHelperLane();
    [loop] while (WaveActiveAnyTrue(active)) {
        [branch] if (active) {
            const uint uniformIndex = WaveReadLaneFirst(varyingIndex);
            bool process = (varyingIndex == uniformIndex);
            [branch] if (process) {
                //...
            }
            active &= !process;
        }
    }

Now that you know the compiler works like this, it will make your debugging much easier.

I have stepped in completely broken edge cases using wave intrinsics for years (since 2019) and considered they were bug until I finally understood that the compiler was compiling just like a standard C++ compiler, for a single thread running a single program with single data.

Ever since I understood that, I have had no issue with using wave intrinsics.
The wave intrinsics were tacked on, as extern functions and there is no internal support for any of that, just keep that in your mind.
I am pretty sure that is by design, but maybe Microsoft employees can chime in.

[noahwhygodwhy]

The classic case is

...
uint val;
if(WaveIsFirstLane())
{
    // Extremely likely that the driver will use the other inactive threads as helper threads to load data into sgprs
    val = <Do a bunch of expensive loads on this single thread>
}
// Order of instructions is preserved
val = ReadLaneAt(0);
...

But you're saying that's equivalent to this?

...
uint val;
if(WaveisFirstLane() == false)
{
    val = ReadAtLane(0); // uninitialized data
}
else
{
    val = <Do a bunch of expensive loads on this single thread>
    val = ReadAtLane(0); // uninitialized data
}
...

(this case shown at https://github.com/microsoft/directxshadercompiler/wiki/wave-intrinsics#example)

[simondeschenes]

The example in the link works because it is and atomic add / InterlockedAdd.
In that case, the atomic semantics guarantee that this works correctly.

If it was anything but an atomic operation like this:

if ( WaveIsFirstLane () )
{
    // this way, we only issue one atomic for the entire wave, which reduces contention
    // and keeps the output data for each lane in this wave together in the output buffer
    appendOffset = atomicAdd(bufferSize, appendCount);
}

Then yes, the compiler would assume it could reorder like that.

[simondeschenes]

At the time DXC was made, there was no such thing as convergence and uniformity analysis in clang.
That was introduced much later and isn't present in DXC.

Now, it does:
https://llvm.org/docs/ConvergenceAndUniformity.html

That was added to LLVM following work from AMD on that exact problem.
Presentation from end of 2020 here:
https://llvm.org/devmtg/2020-09/slides/Hahnle-Evolving_convergent_Lessons_from_Control_Flow_in_AMDGPU.pdf

It is one of the many reason DXC is getting dropped and HLSL is currently directly being added in clang/llvm right now.
But DXC won't ever have that and will always have those quirks until clang replaces DXC.

Edit: Your problem is on slide 17 in the PDF. Without reconvergence you get exactly the current behavior. And DXC can't do better.

[noahwhygodwhy]

Then shouldn't the "Load" shown in the example also prevent a reordering? Per https://github.com/microsoft/DirectXShaderCompiler/blob/main/docs/Atomics.rst#optimization-outside-atomic

But, if we take into account the compiler does know that we're in a concurrent environment, which this doc suggests, and that the compiler knows that other threads can access other thread's values with the intrinsics (because in reality it isn't just a generic "externFunc") then these rules of ordering should apply to this scenario?

[simondeschenes]

I know it is extremely frustrating, I have felt anger, despair, sadness, and all kinds of emotions over the years where I complained and where I have been told probably hundreds of time that this won't change until we move to clang. There are many issues just like yours that have been closed as "Won't fix" and others are forever in the backlog.

It may look like the compiler does know that it is in a concurrent environment. And, up to a certain point, it does, because it knows what an atomic operation is. But it doesn't understand it more than when it compiles C++. If you want to share things between threads outside of using atomics, you need locks and barriers. There is an advantage where all the lanes of a wave executes the same instructions in lockstep, however that doesn't guarantee anything from the point of view of the compiler.

Everyone had the same problem. Khronos even released an extension to request maximal reconvergence from drivers. Because even if DXC would be doing the right thing, the NVIDIA driver (notoriously) would do the same (wrong) optimization later when it compiles to native from the bytecode:
https://www.khronos.org/blog/khronos-releases-maximal-reconvergence-and-quad-control-extensions-for-vulkan-and-spir-v

In D3D12, there is currently nothing to request maximal reconvergence and you have to use workaround for the next few years at least. I have been doing workarounds since 2019 (and we shipped games), and I really can't wait until that changes.

Edit: The trick is that wherever you use data from other lanes using wave intrinsics, that data must have been fetched through uniform control flow. If the control flow was divergent, then you need to either make the flow uniform or use barriers. Don't ever put barriers inside the divergent control flow though, that is UB. Like above, put the barrier before the wave operation which happens inside a uniform control flow.

Edit 2: Even AMD and NVIDIA engineers asked us why our code with wave intrinsics was so strange. I rewrote the code right in front of them to show them that wave intrinsics absolutely don't work the way it is documented and not doing it the way we do just doesn't work. It "may work" if you are lucky and the compiler is nice, but just moving a single line may mean that you'll hit a case where the compiler breaks your code. I fixed at least 20 cases where wave intrinsics were used but it wasn't "working the intended way" in my last game. I was told that it was a bug from Microsoft, then Microsoft told me it was a bug from AMD, then AMD found a workaround, but that breaks NVIDIA, ... Just accept that it is like this and nobody is going to fix it anytime soon. I came to that realization in 2023 after 4 years of back and forth.

[noahwhygodwhy]

I know it is extremely frustrating, I have felt anger, despair, sadness, and all kinds of emotions over the years where I complained and where I have been told probably hundreds of time that this won't change until we move to clang. There are many issues just like yours that have been closed as "Won't fix" and others are forever in the backlog.

Ooook

how about this. Atomics, but it gets reordered. https://godbolt.org/z/KnKv6znse

[simondeschenes]

Yeah, with atomics, that is not normal.