Do Subgroup Shuffle Intrinsics require a preceeding `OpControlBarrier` with scope at least Subgroup to avoid UB?

[devshgraphicsprogramming]

We've ran into some really weird behaviour on Nvidia GPUs, it looked as-if Subgroup Shuffles were exchanging values where one or more invocation was at a different place in the SPIR-V code.

Its too long to write up in a GitHub issue, but its described in our blog post
https://graphics-programming.org/blog/subgroup-shuffle-execution-dependency-on-nvidia

Btw slight errata on the blogpost, broadcasts and relative shuffles with constant deltas can be implemented as register snooping, while shuffles with non-constant indices or relative deltas can't and the data exchange needs to happen through some bit of compiler allocated shared/on-chip memory.

Its possible that the compiler messed up the sync on on that bit of memory we don't even know exists or expect since the shuffles are pure SSA without taking any pointers.

[devshgraphicsprogramming]

Repro on our Instance of DXC godbolt (with our includes / STL library)
Short link is live https://godbolt.devsh.eu/z/1qY33Y

               OpCapability GroupNonUniformBallot
               OpCapability Shader
               OpCapability GroupNonUniform
               OpCapability Int64
               OpCapability Int16
               OpCapability PhysicalStorageBufferAddresses
               OpCapability GroupNonUniformShuffleRelative
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel PhysicalStorageBuffer64 GLSL450
               OpEntryPoint GLCompute %main "main" %pc %gl_WorkGroupID %SubgroupId %SubgroupSize %SubgroupLocalInvocationId %scratch
               OpExecutionMode %main LocalSize 1024 1 1
               OpDecorate %gl_WorkGroupID BuiltIn WorkgroupId
               OpDecorate %SubgroupSize BuiltIn SubgroupSize
               OpDecorate %SubgroupId BuiltIn SubgroupId
               OpDecorate %SubgroupLocalInvocationId BuiltIn SubgroupLocalInvocationId
               OpMemberDecorate %type_PushConstant_PushConstantData 0 Offset 0
               OpMemberDecorate %type_PushConstant_PushConstantData 1 Offset 8
               OpDecorate %type_PushConstant_PushConstantData Block
        %int = OpTypeInt 32 1
      %int_0 = OpConstant %int 0
      %int_1 = OpConstant %int 1
       %uint = OpTypeInt 32 0
     %uint_1 = OpConstant %uint 1
    %uint_16 = OpConstant %uint 16
       %bool = OpTypeBool
       %true = OpConstantTrue %bool
     %uint_2 = OpConstant %uint 2
     %uint_3 = OpConstant %uint 3
     %uint_4 = OpConstant %uint 4
      %ulong = OpTypeInt 64 0
     %uint_0 = OpConstant %uint 0
     %uint_8 = OpConstant %uint 8
    %uint_32 = OpConstant %uint 32
     %ushort = OpTypeInt 16 0
   %ushort_0 = OpConstant %ushort 0
   %ushort_1 = OpConstant %ushort 1
  %ushort_32 = OpConstant %ushort 32
   %ushort_5 = OpConstant %ushort 5
  %ushort_15 = OpConstant %ushort 15
  %ushort_10 = OpConstant %ushort 10
%ushort_1024 = OpConstant %ushort 1024
   %uint_264 = OpConstant %uint 264
   %ulong_16 = OpConstant %ulong 16
%_ptr_Input_uint = OpTypePointer Input %uint
     %v3uint = OpTypeVector %uint 3
%_ptr_Input_v3uint = OpTypePointer Input %v3uint
     %v4uint = OpTypeVector %uint 4
%_arr_uint_uint_32 = OpTypeArray %uint %uint_32
%_ptr_Workgroup__arr_uint_uint_32 = OpTypePointer Workgroup %_arr_uint_uint_32
%type_PushConstant_PushConstantData = OpTypeStruct %ulong %ulong
%_ptr_PushConstant_type_PushConstant_PushConstantData = OpTypePointer PushConstant %type_PushConstant_PushConstantData
       %void = OpTypeVoid
         %44 = OpTypeFunction %void
%_arr_v4uint_uint_1 = OpTypeArray %v4uint %uint_1
%_ptr_PushConstant_ulong = OpTypePointer PushConstant %ulong
%_ptr_Function__arr_v4uint_uint_1 = OpTypePointer Function %_arr_v4uint_uint_1
%_ptr_Function_v4uint = OpTypePointer Function %v4uint
%_ptr_Function_uint = OpTypePointer Function %uint
%_ptr_PhysicalStorageBuffer_v4uint = OpTypePointer PhysicalStorageBuffer %v4uint
%_ptr_Workgroup_uint = OpTypePointer Workgroup %uint
%gl_WorkGroupID = OpVariable %_ptr_Input_v3uint Input
%SubgroupSize = OpVariable %_ptr_Input_uint Input
 %SubgroupId = OpVariable %_ptr_Input_uint Input
%SubgroupLocalInvocationId = OpVariable %_ptr_Input_uint Input
    %scratch = OpVariable %_ptr_Workgroup__arr_uint_uint_32 Workgroup
         %pc = OpVariable %_ptr_PushConstant_type_PushConstant_PushConstantData PushConstant
         %52 = OpUndef %v4uint
         %53 = OpUndef %uint
    %uint_31 = OpConstant %uint 31
 %uint_16384 = OpConstant %uint 16384
       %main = OpFunction %void None %44
%ternary_rhs = OpLabel
         %56 = OpVariable %_ptr_Function__arr_v4uint_uint_1 Function
         %57 = OpVariable %_ptr_Function_v4uint Function
         %58 = OpVariable %_ptr_Function_v4uint Function
         %59 = OpVariable %_ptr_Function_v4uint Function
         %60 = OpVariable %_ptr_Function_v4uint Function
         %61 = OpBitwiseAnd %ushort %ushort_0 %ushort_15
         %62 = OpShiftLeftLogical %ushort %ushort_1 %61
         %63 = OpBitwiseAnd %ushort %ushort_10 %ushort_15
         %64 = OpShiftLeftLogical %ushort %ushort_1 %63
         %65 = OpBitwiseAnd %ushort %ushort_5 %ushort_15
         %66 = OpShiftLeftLogical %ushort %ushort_1 %65
         %67 = OpUDiv %ushort %ushort_1024 %64
         %68 = OpAccessChain %_ptr_PushConstant_ulong %pc %int_0
         %69 = OpLoad %ulong %68
         %70 = OpAccessChain %_ptr_PushConstant_ulong %pc %int_1
         %71 = OpLoad %ulong %70
         %72 = OpLoad %v3uint %gl_WorkGroupID
         %73 = OpCompositeExtract %uint %72 0
         %74 = OpIMul %uint %73 %uint_16384
         %75 = OpUConvert %ulong %74
         %76 = OpIAdd %ulong %69 %75
         %77 = OpIAdd %ulong %71 %75
         %78 = OpCompositeConstruct %_arr_v4uint_uint_1 %52
               OpStore %56 %78
         %79 = OpLoad %uint %SubgroupId
         %80 = OpUConvert %ushort %79
         %81 = OpLoad %uint %SubgroupSize
         %82 = OpExtInst %uint %1 FindUMsb %81
         %83 = OpUConvert %ushort %82
         %84 = OpBitwiseAnd %ushort %83 %ushort_15
         %85 = OpShiftLeftLogical %ushort %80 %84
         %86 = OpLoad %uint %SubgroupLocalInvocationId
         %87 = OpUConvert %ushort %86
         %88 = OpIAdd %ushort %85 %87
               OpBranch %89
         %89 = OpLabel
         %90 = OpPhi %ushort %ushort_0 %ternary_rhs %91 %92
         %93 = OpULessThan %bool %90 %67
               OpLoopMerge %94 %92 Unroll
               OpBranchConditional %93 %92 %94
         %92 = OpLabel
         %95 = OpIMul %ushort %90 %64
         %96 = OpIAdd %ushort %95 %88
         %97 = OpAccessChain %_ptr_Function_v4uint %56 %90
         %98 = OpUConvert %ulong %96
         %99 = OpIMul %ulong %98 %ulong_16
        %100 = OpIAdd %ulong %76 %99
        %101 = OpBitcast %_ptr_PhysicalStorageBuffer_v4uint %100
        %102 = OpLoad %v4uint %101 Aligned 4
               OpStore %97 %102
         %91 = OpIAdd %ushort %90 %ushort_1
               OpBranch %89
         %94 = OpLabel
               OpBranch %103
        %103 = OpLabel
        %104 = OpPhi %ushort %ushort_0 %94 %105 %106
        %107 = OpUDiv %ushort %64 %64
        %108 = OpULessThan %bool %104 %107
               OpLoopMerge %109 %106 Unroll
               OpBranchConditional %108 %110 %109
        %110 = OpLabel
        %111 = OpIMul %ushort %104 %64
        %112 = OpIAdd %ushort %111 %88
        %113 = OpShiftRightLogical %ushort %112 %63
        %114 = OpAccessChain %_ptr_Function_v4uint %56 %113
        %115 = OpLoad %v4uint %114
               OpStore %58 %115
               OpStore %59 %115
        %116 = OpAccessChain %_ptr_Function_uint %59 %uint_0
        %117 = OpLoad %uint %116
        %118 = OpAccessChain %_ptr_Function_uint %57 %uint_0
               OpStore %118 %117
        %119 = OpLoad %uint %118
        %120 = OpAccessChain %_ptr_Function_uint %59 %uint_1
        %121 = OpLoad %uint %120
        %122 = OpIAdd %uint %119 %121
        %123 = OpAccessChain %_ptr_Function_uint %57 %uint_1
               OpStore %123 %122
        %124 = OpLoad %uint %123
        %125 = OpAccessChain %_ptr_Function_uint %59 %uint_2
        %126 = OpLoad %uint %125
        %127 = OpIAdd %uint %124 %126
        %128 = OpAccessChain %_ptr_Function_uint %57 %uint_2
               OpStore %128 %127
        %129 = OpLoad %uint %128
        %130 = OpAccessChain %_ptr_Function_uint %59 %uint_3
        %131 = OpLoad %uint %130
        %132 = OpIAdd %uint %129 %131
        %133 = OpAccessChain %_ptr_Function_uint %57 %uint_3
               OpStore %133 %132
        %134 = OpLoad %uint %133
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %135 = OpGroupNonUniformShuffleUp %uint %uint_3 %134 %uint_1
        %136 = OpINotEqual %bool %86 %uint_0
        %137 = OpSelect %uint %136 %135 %uint_0
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %138 = OpGroupNonUniformShuffleUp %uint %uint_3 %137 %uint_1
        %139 = OpULessThan %bool %86 %uint_1
        %140 = OpSelect %uint %139 %uint_0 %138
        %141 = OpIAdd %uint %137 %140
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %142 = OpGroupNonUniformShuffleUp %uint %uint_3 %141 %uint_2
        %143 = OpULessThan %bool %86 %uint_2
        %144 = OpSelect %uint %143 %uint_0 %142
        %145 = OpIAdd %uint %141 %144
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %146 = OpGroupNonUniformShuffleUp %uint %uint_3 %145 %uint_4
        %147 = OpULessThan %bool %86 %uint_4
        %148 = OpSelect %uint %147 %uint_0 %146
        %149 = OpIAdd %uint %145 %148
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %150 = OpGroupNonUniformShuffleUp %uint %uint_3 %149 %uint_8
        %151 = OpULessThan %bool %86 %uint_8
        %152 = OpSelect %uint %151 %uint_0 %150
        %153 = OpIAdd %uint %149 %152
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %154 = OpGroupNonUniformShuffleUp %uint %uint_3 %153 %uint_16
        %155 = OpULessThan %bool %86 %uint_16
        %156 = OpSelect %uint %155 %uint_0 %154
        %157 = OpIAdd %uint %153 %156
        %158 = OpLoad %uint %118
        %159 = OpIAdd %uint %158 %157
               OpStore %118 %159
        %160 = OpLoad %uint %123
        %161 = OpIAdd %uint %160 %157
               OpStore %123 %161
        %162 = OpLoad %uint %128
        %163 = OpIAdd %uint %162 %157
               OpStore %128 %163
        %164 = OpLoad %uint %133
        %165 = OpIAdd %uint %164 %157
               OpStore %133 %165
        %166 = OpLoad %v4uint %57
               OpStore %58 %166
               OpStore %114 %166
        %167 = OpIEqual %bool %86 %uint_31
               OpSelectionMerge %168 None
               OpBranchConditional %167 %169 %168
        %169 = OpLabel
        %170 = OpShiftRightLogical %ushort %64 %65
        %171 = OpIMul %ushort %104 %170
        %172 = OpIAdd %ushort %171 %80
        %173 = OpBitwiseAnd %ushort %172 %ushort_0
        %174 = OpIMul %ushort %173 %ushort_32
        %175 = OpIAdd %ushort %174 %172
        %176 = OpIMul %ushort %66 %62
        %177 = OpUDiv %ushort %172 %176
        %178 = OpIAdd %ushort %175 %177
        %179 = OpUConvert %uint %178
        %180 = OpAccessChain %_ptr_Function_uint %58 %uint_3
        %181 = OpLoad %uint %180
        %182 = OpAccessChain %_ptr_Workgroup_uint %scratch %179
               OpStore %182 %181
               OpBranch %168
        %168 = OpLabel
               OpBranch %106
        %106 = OpLabel
        %105 = OpIAdd %ushort %104 %ushort_1
               OpBranch %103
        %109 = OpLabel
               OpControlBarrier %uint_2 %uint_2 %uint_264
        %183 = OpIEqual %bool %79 %uint_0
               OpSelectionMerge %184 None
               OpBranchConditional %183 %185 %184
        %185 = OpLabel
               OpBranch %186
        %186 = OpLabel
        %187 = OpPhi %uint %53 %185 %188 %189
        %190 = OpPhi %ushort %ushort_0 %185 %191 %189
        %192 = OpULessThan %bool %190 %62
               OpLoopMerge %193 %189 Unroll
               OpBranchConditional %192 %189 %193
        %189 = OpLabel
        %194 = OpIMul %ushort %190 %ushort_32
        %195 = OpIAdd %ushort %194 %88
        %196 = OpUDiv %ushort %88 %66
        %197 = OpIAdd %ushort %195 %196
        %198 = OpUConvert %uint %197
        %199 = OpAccessChain %_ptr_Workgroup_uint %scratch %198
        %188 = OpLoad %uint %199
        %191 = OpIAdd %ushort %190 %ushort_1
               OpBranch %186
        %193 = OpLabel
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %200 = OpGroupNonUniformShuffleUp %uint %uint_3 %187 %uint_1
        %201 = OpULessThan %bool %86 %uint_1
        %202 = OpSelect %uint %201 %uint_0 %200
        %203 = OpIAdd %uint %187 %202
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %204 = OpGroupNonUniformShuffleUp %uint %uint_3 %203 %uint_2
        %205 = OpULessThan %bool %86 %uint_2
        %206 = OpSelect %uint %205 %uint_0 %204
        %207 = OpIAdd %uint %203 %206
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %208 = OpGroupNonUniformShuffleUp %uint %uint_3 %207 %uint_4
        %209 = OpULessThan %bool %86 %uint_4
        %210 = OpSelect %uint %209 %uint_0 %208
        %211 = OpIAdd %uint %207 %210
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %212 = OpGroupNonUniformShuffleUp %uint %uint_3 %211 %uint_8
        %213 = OpULessThan %bool %86 %uint_8
        %214 = OpSelect %uint %213 %uint_0 %212
        %215 = OpIAdd %uint %211 %214
               OpControlBarrier %uint_3 %uint_3 %uint_0
        %216 = OpGroupNonUniformShuffleUp %uint %uint_3 %215 %uint_16
        %217 = OpULessThan %bool %86 %uint_16
        %218 = OpSelect %uint %217 %uint_0 %216
        %219 = OpIAdd %uint %215 %218
               OpBranch %220
        %220 = OpLabel
        %221 = OpPhi %ushort %ushort_0 %193 %222 %223
        %224 = OpULessThan %bool %221 %62
               OpLoopMerge %225 %223 Unroll
               OpBranchConditional %224 %223 %225
        %223 = OpLabel
        %226 = OpIMul %ushort %221 %ushort_32
        %227 = OpIAdd %ushort %226 %88
        %228 = OpUDiv %ushort %88 %66
        %229 = OpIAdd %ushort %227 %228
        %230 = OpUConvert %uint %229
        %231 = OpAccessChain %_ptr_Workgroup_uint %scratch %230
               OpStore %231 %219
        %222 = OpIAdd %ushort %221 %ushort_1
               OpBranch %220
        %225 = OpLabel
               OpBranch %184
        %184 = OpLabel
               OpControlBarrier %uint_2 %uint_2 %uint_264
               OpBranch %232
        %232 = OpLabel
        %233 = OpPhi %ushort %ushort_0 %184 %234 %235
        %236 = OpULessThan %bool %233 %107
               OpLoopMerge %237 %235 Unroll
               OpBranchConditional %236 %238 %237
        %238 = OpLabel
        %239 = OpIMul %ushort %233 %64
        %240 = OpIAdd %ushort %239 %88
        %241 = OpShiftRightLogical %ushort %240 %63
        %242 = OpAccessChain %_ptr_Function_v4uint %56 %241
        %243 = OpLoad %v4uint %242
               OpStore %60 %243
        %244 = OpISub %uint %79 %uint_1
        %245 = OpUConvert %ushort %244
        %246 = OpShiftRightLogical %ushort %64 %65
        %247 = OpIMul %ushort %233 %246
        %248 = OpIAdd %ushort %247 %245
        %249 = OpBitwiseAnd %ushort %248 %ushort_0
        %250 = OpIMul %ushort %249 %ushort_32
        %251 = OpIAdd %ushort %250 %248
        %252 = OpIMul %ushort %66 %62
        %253 = OpUDiv %ushort %248 %252
        %254 = OpIAdd %ushort %251 %253
        %255 = OpUConvert %uint %233
        %256 = OpINotEqual %bool %255 %uint_0
        %257 = OpLogicalNot %bool %256
               OpSelectionMerge %258 None
               OpBranchConditional %257 %259 %258
        %259 = OpLabel
        %260 = OpINotEqual %bool %79 %uint_0
               OpBranch %258
        %258 = OpLabel
        %261 = OpPhi %bool %true %238 %260 %259
               OpSelectionMerge %262 None
               OpBranchConditional %261 %263 %262
        %263 = OpLabel
        %264 = OpUConvert %uint %254
        %265 = OpAccessChain %_ptr_Workgroup_uint %scratch %264
        %266 = OpLoad %uint %265
               OpBranch %262
        %262 = OpLabel
        %267 = OpPhi %uint %uint_0 %258 %266 %263
        %268 = OpAccessChain %_ptr_Function_uint %60 %uint_0
        %269 = OpLoad %uint %268
        %270 = OpIAdd %uint %267 %269
               OpStore %268 %270
        %271 = OpAccessChain %_ptr_Function_uint %60 %uint_1
        %272 = OpLoad %uint %271
        %273 = OpIAdd %uint %267 %272
               OpStore %271 %273
        %274 = OpAccessChain %_ptr_Function_uint %60 %uint_2
        %275 = OpLoad %uint %274
        %276 = OpIAdd %uint %267 %275
               OpStore %274 %276
        %277 = OpAccessChain %_ptr_Function_uint %60 %uint_3
        %278 = OpLoad %uint %277
        %279 = OpIAdd %uint %267 %278
               OpStore %277 %279
        %280 = OpLoad %v4uint %60
               OpStore %242 %280
               OpBranch %235
        %235 = OpLabel
        %234 = OpIAdd %ushort %233 %ushort_1
               OpBranch %232
        %237 = OpLabel
               OpControlBarrier %uint_2 %uint_2 %uint_264
               OpBranch %281
        %281 = OpLabel
        %282 = OpPhi %ushort %ushort_0 %237 %283 %284
        %285 = OpULessThan %bool %282 %67
               OpLoopMerge %286 %284 Unroll
               OpBranchConditional %285 %284 %286
        %284 = OpLabel
        %287 = OpIMul %ushort %282 %64
        %288 = OpIAdd %ushort %287 %88
        %289 = OpAccessChain %_ptr_Function_v4uint %56 %282
        %290 = OpLoad %v4uint %289
        %291 = OpUConvert %ulong %288
        %292 = OpIMul %ulong %291 %ulong_16
        %293 = OpIAdd %ulong %77 %292
        %294 = OpBitcast %_ptr_PhysicalStorageBuffer_v4uint %293
               OpStore %294 %290 Aligned 4
        %283 = OpIAdd %ushort %282 %ushort_1
               OpBranch %281
        %286 = OpLabel
               OpReturn
               OpFunctionEnd

Bug shows up if OpControlBarrier %uint_3 %uint_3 %uint_0 is removed before the shuffles in the resulting SPIR-V.

[jeffbolznv]

The short answer to the subject is "no, you've probably just hit a compiler bug", the longer answer is "this is actually a really subtle question that the memory model TSG is currently working on, but you've still probably just hit a compiler bug."

Please share instructions for how to reproduce this to vulkan-support @ nvidia.com and we'll take a look.

[devshgraphicsprogramming]

The short answer to the subject is "no, you've probably just hit a compiler bug", the longer answer is "this is actually a really subtle question that the memory model TSG is currently working on, but you've still probably just hit a compiler bug."

Please share instructions for how to reproduce this to vulkan-support @ nvidia.com and we'll take a look.

Awesome, thanks for the prompt reply, I'll get @keptsecret to make Release and Debug self contained executables with the Subgroup Barriers on and off.

Hmm, I wonder what has the Memory Model got to do with it? Shuffles don't deal with any pointers, so its just a matter of execution dependency.

P.S. The other thing to take a look at is why our Shuffle-based Stone-Kogge prefix sum is 2x faster than Nvidia's native subgroup arithmetic implementation.

[jeffbolznv]

P.S. The other thing to take a look at is why our Shuffle-based Stone-Kogge prefix sum is 2x faster than Nvidia's native subgroup arithmetic implementation.

We don't get many (any?) real apps using these scans in a way that affects performance, so it's not something we've optimized in real code. We do have to handle inactive invocations as you mention, so maybe we just need a fast path for when it's fully active. We have such a fast path for reduce, but I don't think we do for scans.

[jeffbolznv]

Hmm, I wonder what has the Memory Model got to do with it? Shuffles don't deal with any pointers, so its just a matter of execution dependency.

It's really the Memory and Execution Model TSG, and yeah it's an execution model thing.

[devshgraphicsprogramming]

P.S. The other thing to take a look at is why our Shuffle-based Stone-Kogge prefix sum is 2x faster than Nvidia's native subgroup arithmetic implementation.

We don't get many (any?) real apps using these scans in a way that affects performance, so it's not something we've optimized in real code. We do have to handle inactive invocations as you mention, so maybe we just need a fast path for when it's fully active. We have such a fast path for reduce, but I don't think we do for scans.

yeah our reductions are slightly slower, only scans are affected.