Kernel fails to compile for CPU target seemingly due to use of OpBitReverse in SPIR-V

[pdurbano]

Describe the bug
I've found a scenario where a particular simple function used by my SYCL kernel fails with either JIT or AOT SPIR-V compilation for a CPU target (although not a GPU target). Looking at SPIR-V disassembly suggests that the failure only happens when the compiler was able to recognize the function can be reduced to the OpBitReverse operation. Breaking up the function so that the compiler doesn't recognize the OpBitReverse optimization allows the kernel to compile for the CPU target without a problem.

To Reproduce
Call this function from a SYCL kernel (e.g. just add the call to any simple SYCL tutorial's kernel):

uint8_t reverse_byte(uint8_t a)
{
    a = ((0x55 & a) << 1) | (0x55 & (a >> 1));
    a = ((0x33 & a) << 2) | (0x33 & (a >> 2));
    return (a << 4) | (a >> 4);
}

Compile with vanilla options:

icpx -fsycl <whatever>.cpp -o <whatever>

Runtime fails for a CPU target:

The program was built for 1 devices
Build program log for 'Intel(R) Xeon(R) W-10885M CPU @ 2.40GHz':
Compilation started
Unsupported SPIR-V module
SPIRV module requires unsupported capability 0
Compilation failed
 -11 (CL_BUILD_PROGRAM_FAILURE)

NOTE: I only see this problem with a CPU target. When I target a GPU it has no problem.
Now replace that function definition with these without changing anything at the reverse_byte call site in the kernel:

uint8_t parital_reverse_byte(uint8_t a)
{
    a = ((0x55 & a) << 1) | (0x55 & (a >> 1));
    return ((0x33 & a) << 2) | (0x33 & (a >> 2));
}
uint8_t reverse_byte(uint8_t a)
{
    a = parital_reverse_byte(a);
    return (a << 4) | (a >> 4);
}

Recompile and run. Now there are no issues at runtime.
SPIR-V disassembly (via -fsycl-device-only -fsycl-device-obj=spirv and https://github.com/KhronosGroup/SPIRV-Tools) shows that only in the first case does it optimize the reverse_byte function down to the OpBitReverse operation. So my suspicion is that there is no backing implementation for OpBitReverse for CPU targets (or at least my CPU, see above). But I don't know how to decipher "SPIRV module requires unsupported capability 0" any further to know for sure that that's the issue.

Environment:

• OS: Linux (Ubuntu 20.04.1)
• Target device and vendor: Intel(R) Xeon(R) W-10885M CPU @ 2.40GHz
• DPC++ version: Intel(R) oneAPI DPC++/C++ Compiler 2022.2.1 (2022.2.1.20221020)
• Dependencies version: n/a

Additional context
None.

[AlexeySachkov]

Hi @pdurbano, thanks for the report

OpBitReverse declares either Shader or BitInstructions capability and I'm sure that Shader is not supported by our OCL CPU Experimental runtime. Tagging @MrSidims here for awareness: we probably want to update the translator to support SPV_KHR_bit_instructions to emit OptBitReverse with BitInstructions instead of Shader.

However, the error says it doesn't support capability 0, which is Matrix and I honestly have no idea why is it generated in this case: I've tried my own minimalistic example with almost empty kernel, which simply calls reverse_byte and it still emits Matrix capability.

Interesting thing: Matrix capability is used in a default constructor of SPIRVCapability class. It may be possible that the translator mistakenly default-constructs SPIRVCapability somewhere and that leads to Matrix being emitted.

llvm/llvm-spirv/lib/SPIRV/libSPIRV/SPIRVEntry.h

Lines 819 to 823 in d37ea6e

	class SPIRVCapability : public SPIRVEntryNoId<OpCapability> {
	public:
	SPIRVCapability(SPIRVModule *M, SPIRVCapabilityKind K);
	SPIRVCapability() : Kind(CapabilityMatrix) {}
	_SPIRV_DCL_ENCDEC

@MrSidims, could you please take a look at this from the translator side? I think it makes sense to outline those two issues into the translator repo once they are confirmed.

[MrSidims]

Sure, I'll take a look

[MrSidims]

However, the error says it doesn't support capability 0, which is Matrix and I honestly have no idea why is it generated in this case: I've tried my own minimalistic example with almost empty kernel, which simply calls reverse_byte and it still emits Matrix capability.

Shader capability implicitly declares Matrix capability and I was a bit surprised to see, that the translator can actually check such implicit declarations and add the appropriate capabilities from the list, see SPIRVMap<SPIRVCapabilityKind, SPIRVCapVec> from SPIRV/libSPIRV/SPIRVEnum.h (currently starting from line 149). Though, I agree, that default initialization for the translator should probably be either disabled or set to CapabilityKernel.

we probably want to update the translator to support SPV_KHR_bit_instructions

It supports the extension, it has a check if the extension is enabled by driver - then use it, otherwise fallback to Shader capability. I believe we need to do the following:

• Check if our devices support SPV_KHR_bit_instructions extension and if they do - enable it in frontend driver;
• If the extension is not supported, then create appropriate requests for devices' drivers teams and, probably, instead of adding Shader capability - lower @llvm.bitreverse.i8 intrinsic in the semantically equivalent IR block aka reverse frontend optimization. But the later will require an approval from the community.

[MrSidims]

It does look like that cl_khr_extended_bit_ops OpenCL extension (which has SPIR-V counterpart SPV_KHR_bit_instructions) is not supported at least on CPU. And I don't see much of a value to support it, as SYCL 2020 doesn't have appropriate bit operations, @AlexeySachkov please correct me if I'm wrong. Hence it seems lowering of llvm.bitreverse.iN in the translator is the way to go. (meanwhile bit_reverse() OpenCL builtin should remain untouched as well as other OpenCL builtins added by the extension).

[AlexeySachkov]

It does look like that cl_khr_extended_bit_ops OpenCL extension (which has SPIR-V counterpart SPV_KHR_bit_instructions) is not supported at least on CPU. And I don't see much of a value to support it, as SYCL 2020 doesn't have appropriate bit operations, @AlexeySachkov please correct me if I'm wrong. Hence it seems lowering of llvm.bitreverse.iN in the translator is the way to go. (meanwhile bit_reverse() OpenCL builtin should remain untouched as well as other OpenCL builtins added by the extension).

Personally, I don't like solutions like emitting a whole function in LLVM IR or SPIR-V at the translator level and someone might even see this as a regression (those who support Shader capability), so I would vote for supporting the extension in OCL CPU RT.

But yeah, I don't see a direct counterpart for OpBitReverse in SYCL spec.

[Rbiessy]

I have run into this same issue on CPU. I am also seeing error: undefined reference to `__builtin_spirv_OpBitReverse_i2' on an integrated GPU.
What's annoying is that bitreverse seems to be generated by the compiler from some indices computation and I don't see how I can avoid this issue. Does a workaround exist?