SPIR-V optimiser and removal of duplicate instructions across branches

[McDaMastR]

The SPIR-V optimiser spirv-opt is able to optimise a SPIR-V module containing simple and identical duplicate branches. With the use of the --if-conversion, --eliminate-dead-code-aggressive, and --merge-blocks options, the duplicate branches will be removed.

If instead the branches were not completely identical but rather only shared some number of identical instructions, then the module could be similarly optimised by removing the duplicate instructions and inserting them before the branching occurs. However, spirv-opt appears to be unable to do this.

The following is the assembly of a SPIR-V module containing a compute shading stage entry point function.

               OpCapability Shader
               OpMemoryModel Logical GLSL450
               OpEntryPoint GLCompute %main "main" %GlobalInvocationId %buffer

               OpDecorate %GlobalInvocationId BuiltIn GlobalInvocationId
               OpMemberDecorate %struct 0 Offset 0
               OpDecorate %struct Block

       %void = OpTypeVoid
       %bool = OpTypeBool
       %uint = OpTypeInt 32 0
     %v3uint = OpTypeVector %uint 3
     %struct = OpTypeStruct %uint
       %func = OpTypeFunction %void

     %uint_0 = OpConstant %uint 0
     %uint_1 = OpConstant %uint 1

%ptr_Input_uint   = OpTypePointer Input %uint
%ptr_Input_v3uint = OpTypePointer Input %v3uint
%ptr_StorageBuffer_uint   = OpTypePointer StorageBuffer %uint
%ptr_StorageBuffer_struct = OpTypePointer StorageBuffer %struct
%GlobalInvocationId = OpVariable %ptr_Input_v3uint Input
     %buffer        = OpVariable %ptr_StorageBuffer_struct StorageBuffer

       %main = OpFunction %void None %func
      %start = OpLabel
          %1 =   OpAccessChain %ptr_Input_uint %GlobalInvocationId %uint_0
          %2 =   OpLoad %uint %1
          %3 =   OpBitwiseAnd %uint %2 %uint_1
          %4 =   OpIEqual %bool %3 %uint_0
                 OpSelectionMerge %end None
                 OpBranchConditional %4 %branch1 %branch2

    %branch1 =     OpLabel
          %5 =       OpIAdd %uint %2 %uint_1
          %6 =       OpShiftLeftLogical %uint %5 %uint_1
                     OpBranch %end

    %branch2 =     OpLabel
          %7 =       OpIAdd %uint %2 %uint_1
          %8 =       OpShiftRightLogical %uint %7 %uint_1
                     OpBranch %end

        %end = OpLabel
          %9 =   OpPhi %uint %6 %branch1 %8 %branch2
         %10 =   OpAccessChain %ptr_StorageBuffer_uint %buffer %uint_0
                 OpStore %10 %9
                 OpReturn
               OpFunctionEnd

The module's entry point functionally does the following (pseudocode).

UINT x = global invocation ID
IF x is even
    x = x + 1
    x = x << 1
ELSE
    x = x + 1
    x = x >> 1
ENDIF
STORE x

Both branches begin with OpIAdd %uint %2 %uint_1 (x = x + 1), meaning it will be executed in all possible structured control-flow paths, making it a duplicate instruction. The module can therefore be optimised by merging these duplicate instructions before the branch and merge instructions. However, no option provided by spirv-opt seems to be able to achieve this optimisation. Numerous potentially relevant options were tested, including -O, -Os, --local-redundancy-elimination, --loop-invariant-code-motion, --strength-reduction, etc.

As such, it will likely be beneficial either to add this optimisation to an existing option, such as --redundancy-elimination, or to add a new option for this optimisation, such as --branch-redundancy-elimination.

All utilised SPIR-V tools used SPIR-V 1.6, and gave the following --version.

SPIRV-Tools v2024.4 v2024.4.rc1-0-g6dcc7e35