[SPIRV] Add support for SPV_KHR_bit_instructions

[pmatos]

Summary

Draft version of patch to add support for SPV_KHR_bit_instructions.

Created revision so we can discuss how to proceed here.
SPV_KHR_bit_instructions (http://htmlpreview.github.io/?https://github.com/KhronosGroup/SPIRV-Registry/blob/main/extensions/KHR/SPV_KHR_bit_instructions.html),
adds support for instructions that we already support through
the Shader capability but without requiring the shader cap.

However we currently have no way to disable the shader cap afaiu.
On the other hand, SPV_KHR_bit_instructions was one of the
extensions @mpaszkowski listed that we need to implement.

So what does it mean at the moment the need to implement this?
Is it just the ability to issue the extension and capabilities
instructions without issuing the Shader capability? If so,
then I will need to add here a way to disable the Shader
capability. What do you think?

[iliya-diyachkov]

For such cases, we can use SPIRV translator as a reference tool. You can build it (https://github.com/KhronosGroup/SPIRV-LLVM-Translator) and run to see what output it generates. It also has a set of tests that we partly adopted for our backend, so you can use its test base to search for tests of some functionality and reuse them.

For example, they have test/transcoding/cl_khr_extended_bit_ops.cl for SPV_KHR_bit_instructions extension. Here is the beginning of SPIRV, which the translator outputs:

...
               OpCapability Addresses
               OpCapability Linkage
               OpCapability Kernel
               OpCapability Vector16
               OpCapability Int64
               OpCapability Int16
               OpCapability Int8
               OpCapability BitInstructions
               OpExtension "SPV_KHR_bit_instructions"
          %1 = OpExtInstImport "OpenCL.std"
...

There is no Shader capability but we have BitInstructions capability and SPV_KHR_bit_instructions extension (as you suggested).

[pmatos]

In D156661#4548049, @iliya-diyachkov wrote:

For such cases, we can use SPIRV translator as a reference tool. You can build it (https://github.com/KhronosGroup/SPIRV-LLVM-Translator) and run to see what output it generates. It also has a set of tests that we partly adopted for our backend, so you can use its test base to search for tests of some functionality and reuse them.

For example, they have test/transcoding/cl_khr_extended_bit_ops.cl for SPV_KHR_bit_instructions extension. Here is the beginning of SPIRV, which the translator outputs:

...
               OpCapability Addresses
               OpCapability Linkage
               OpCapability Kernel
               OpCapability Vector16
               OpCapability Int64
               OpCapability Int16
               OpCapability Int8
               OpCapability BitInstructions
               OpExtension "SPV_KHR_bit_instructions"
          %1 = OpExtInstImport "OpenCL.std"
...

There is no Shader capability but we have BitInstructions capability and SPV_KHR_bit_instructions extension (as you suggested).

OK - thanks. I think you confirmed what I wanted to know.
When using these instructions, we can use BitInstructions, instead of Shader cap. This means that the current hardcoded (afaiu) Shader cap will need to be optionally enabled only when required.

[pmatos]

Implement support for dropping the shader capability if BitInstructions is all that's needed.

Still need to add some tests ensuring this works and that we never use both Shader and BitInstructions capability since that's redundant.

[pmatos]

Modify test OpBitReverse* to use BitInstructions.
Add bit instructions as available cap.

[iliya-diyachkov]

In D156661#4584861, @pmatos wrote:

Still need to add some tests ensuring this works and that we never use both Shader and BitInstructions capability since that's redundant.

Are you going to add these tests in this patch or later?

[pmatos]

In D156661#4614836, @iliya-diyachkov wrote:

In D156661#4584861, @pmatos wrote:

Still need to add some tests ensuring this works and that we never use both Shader and BitInstructions capability since that's redundant.

Are you going to add these tests in this patch or later?

In this patch. Moving to GitHub PR: https://github.com/llvm/llvm-project/pull/66215

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.h

public:
   void checkSatisfiable(const SPIRVSubtarget &ST) const;
   void initAvailableCapabilities(const SPIRVSubtarget &ST);
   // Add the given capabilities to available and all their implicitly defined
   // capabilities too.
   void addAvailableCaps(const CapabilityList &ToAdd);
   bool isCapabilityAvailable(Capability::Capability Cap) const {
     return AvailableCaps.contains(Cap);
   }
+
+  // Remove capability ToRemove, but only if IfPresent is present.
+  void removeCapabilityIf(const Capability::Capability ToRemove,
+                          const Capability::Capability IfPresent);
 };
 
 using InstrList = SmallVector<MachineInstr *>;
 // Maps a local register to the corresponding global alias.
 using LocalToGlobalRegTable = std::map<Register, Register>;
 using RegisterAliasMapTy =
     std::map<const MachineFunction *, LocalToGlobalRegTable>;
 

llvm/lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

 // and performs the global register numbering.
 //
 // The results of this analysis are used in AsmPrinter to rename registers
 // globally and to output required instructions at the module level.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SPIRVModuleAnalysis.h"
+#include "MCTargetDesc/SPIRVBaseInfo.h"
+#include "MCTargetDesc/SPIRVMCTargetDesc.h"
 #include "SPIRV.h"
 #include "SPIRVSubtarget.h"
 #include "SPIRVTargetMachine.h"
 #include "SPIRVUtils.h"
 #include "TargetInfo/SPIRVTargetInfo.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"

 // Add the given capabilities and all their implicitly defined capabilities too.
 void SPIRV::RequirementHandler::addAvailableCaps(const CapabilityList &ToAdd) {
   for (const auto Cap : ToAdd)
     if (AvailableCaps.insert(Cap).second)
       addAvailableCaps(getSymbolicOperandCapabilities(
           SPIRV::OperandCategory::CapabilityOperand, Cap));
 }
 
+void SPIRV::RequirementHandler::removeCapabilityIf(const Capability::Capability ToRemove, 
+                                                   const Capability::Capability IfPresent) {
+  if (AvailableCaps.contains(IfPresent))
+    AvailableCaps.erase(ToRemove);
+}
+
 namespace llvm {
 namespace SPIRV {
 void RequirementHandler::initAvailableCapabilities(const SPIRVSubtarget &ST) {
   // TODO: Implemented for other targets other then OpenCL.
   if (!ST.isOpenCLEnv())
     return;
   // Add the min requirements for different OpenCL and SPIR-V versions.
   addAvailableCaps({Capability::Addresses, Capability::Float16Buffer,
addAvailableCaps({Capability::DenormPreserve, Capability::DenormFlushToZero,
                       Capability::SignedZeroInfNanPreserve,
                       Capability::RoundingModeRTE,
                       Capability::RoundingModeRTZ});
   // TODO: verify if this needs some checks.
   addAvailableCaps({Capability::Float16, Capability::Float64});
 
   // Add cap for SPV_INTEL_optnone.
   // FIXME: this should be added only if the target has the extension.
-  addAvailableCaps({Capability::OptNoneINTEL});
-
+  addAvailableCaps({Capability::OptNoneINTEL, 
+                   Capability::BitInstructions});
   // TODO: add OpenCL extensions.
 }
 } // namespace SPIRV
 } // namespace llvm
 
 // Add the required capabilities from a decoration instruction (including
 // BuiltIns).
 static void addOpDecorateReqs(const MachineInstr &MI, unsigned DecIndex,
case SPIRV::OpTypePointer: {
     const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
     SPIRVType *TypeDef = MRI.getVRegDef(MI.getOperand(2).getReg());
     if (TypeDef->getOpcode() == SPIRV::OpTypeFloat &&
         TypeDef->getOperand(1).getImm() == 16)
       Reqs.addCapability(SPIRV::Capability::Float16Buffer);
     break;
   }
   case SPIRV::OpBitReverse:
+  case SPIRV::OpBitFieldInsert:
+  case SPIRV::OpBitFieldSExtract:
+  case SPIRV::OpBitFieldUExtract:
+    Reqs.addExtension(SPIRV::Extension::SPV_KHR_bit_instructions);
+    Reqs.addCapability(SPIRV::Capability::BitInstructions);
+    break;
   case SPIRV::OpTypeRuntimeArray:
     Reqs.addCapability(SPIRV::Capability::Shader);
     break;
   case SPIRV::OpTypeOpaque:
   case SPIRV::OpTypeEvent:
     Reqs.addCapability(SPIRV::Capability::Kernel);
     break;
   case SPIRV::OpTypePipe:
void addInstrRequirements(const MachineInstr &MI,
   case SPIRV::OpGroupNonUniformBallotBitCount:
   case SPIRV::OpGroupNonUniformBallotFindLSB:
   case SPIRV::OpGroupNonUniformBallotFindMSB:
     Reqs.addCapability(SPIRV::Capability::GroupNonUniformBallot);
     break;
   default:
     break;
   }
+
+  // If we require capability Shader, then we can remove the requirement for
+  // the BitInstructions capability, since Shader is a superset capability
+  // of BitInstructions.
+  Reqs.removeCapabilityIf(SPIRV::Capability::Shader,
+                          SPIRV::Capability::BitInstructions);
 }
 
 static void collectReqs(const Module &M, SPIRV::ModuleAnalysisInfo &MAI,
                         MachineModuleInfo *MMI, const SPIRVSubtarget &ST) {
   // Collect requirements for existing instructions.
   for (auto F = M.begin(), E = M.end(); F != E; ++F) {
     MachineFunction *MF = MMI->getMachineFunction(*F);
     if (!MF)

llvm/lib/Target/SPIRV/SPIRVSubtarget.cpp

 //===-- SPIRVSubtarget.cpp - SPIR-V Subtarget Information ------*- C++ -*--===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SPIR-V specific subclass of TargetSubtargetInfo.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SPIRVSubtarget.h"
+#include "MCTargetDesc/SPIRVBaseInfo.h"
 #include "SPIRV.h"
 #include "SPIRVGlobalRegistry.h"
 #include "SPIRVLegalizerInfo.h"
 #include "SPIRVRegisterBankInfo.h"
 #include "SPIRVTargetMachine.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/TargetParser/Host.h"
 
void SPIRVSubtarget::initAvailableExtensions() {
   if (!isOpenCLEnv())
     return;
   // A default extension for testing.
   // FIXME: This should be changed when we can select extensions through a
   // command line flag.
   AvailableExtensions.insert(
       SPIRV::Extension::SPV_KHR_no_integer_wrap_decoration);
   AvailableExtensions.insert(SPIRV::Extension::SPV_INTEL_optnone);
+  AvailableExtensions.insert(SPIRV::Extension::SPV_KHR_bit_instructions);
 }
 
 // TODO: use command line args for this rather than just defaults.
 // Must have called initAvailableExtensions first.
 void SPIRVSubtarget::initAvailableExtInstSets() {
   AvailableExtInstSets.clear();
   if (!isOpenCLEnv())
     AvailableExtInstSets.insert(SPIRV::InstructionSet::GLSL_std_450);

llvm/lib/Target/SPIRV/SPIRVSymbolicOperands.td

 defm SPV_INTEL_fpga_loop_controls : ExtensionOperand<51>;
 defm SPV_EXT_fragment_shader_interlock : ExtensionOperand<52>;
 defm SPV_NV_shader_sm_builtins : ExtensionOperand<53>;
 defm SPV_KHR_shader_clock : ExtensionOperand<54>;
 defm SPV_INTEL_unstructured_loop_controls : ExtensionOperand<55>;
 defm SPV_EXT_demote_to_helper_invocation : ExtensionOperand<56>;
 defm SPV_INTEL_fpga_reg : ExtensionOperand<57>;
 defm SPV_INTEL_optnone : ExtensionOperand<58>;
+defm SPV_KHR_bit_instructions : ExtensionOperand<59>;
 
 //===----------------------------------------------------------------------===//
 // Multiclass used to define Capabilities enum values and at the same time
 // SymbolicOperand entries with string mnemonics, versioning, extensions, and
 // capabilities.
 //===----------------------------------------------------------------------===//
 
 def Capability : GenericEnum, Operand<i32> {

 defm ImageFootprintNV : CapabilityOperand<5282, 0, 0, [], []>;
 defm FragmentBarycentricNV : CapabilityOperand<5284, 0, 0, [], []>;
 defm ComputeDerivativeGroupQuadsNV : CapabilityOperand<5288, 0, 0, [], []>;
 defm ComputeDerivativeGroupLinearNV : CapabilityOperand<5350, 0, 0, [], []>;
 defm FragmentDensityEXT : CapabilityOperand<5291, 0, 0, [], [Shader]>;
 defm PhysicalStorageBufferAddressesEXT : CapabilityOperand<5347, 0, 0, [], [Shader]>;
 defm CooperativeMatrixNV : CapabilityOperand<5357, 0, 0, [], [Shader]>;
 defm OptNoneINTEL : CapabilityOperand<6094, 0, 0, [SPV_INTEL_optnone], []>;
+defm BitInstructions : CapabilityOperand<6025, 0, 0, [SPV_KHR_bit_instructions], []>;
 
 //===----------------------------------------------------------------------===//
 // Multiclass used to define SourceLanguage enum values and at the same time
 // SymbolicOperand entries.
 //===----------------------------------------------------------------------===//
 
 def SourceLanguage : GenericEnum, Operand<i32> {
   let FilterClass = "SourceLanguage";

llvm/test/CodeGen/SPIRV/transcoding/OpBitReverse_i32.ll

 ; RUN: llc -O0 -mtriple=spirv32-unknown-unknown %s -o - | FileCheck %s --check-prefix=CHECK-SPIRV
 
+; CHECK-SPIRV:      OpCapability BitInstructions
+; CHECK-SPIRV-NEXT: OpExtension "SPV_KHR_bit_instructions"
+
 ; CHECK-SPIRV: %[[#int:]] = OpTypeInt 32
 ; CHECK-SPIRV: OpBitReverse %[[#int]]
 
 define spir_kernel void @testBitRev(i32 %a, i32 %b, i32 %c, i32 addrspace(1)* nocapture %res) local_unnamed_addr {
 entry:
   %call = tail call i32 @llvm.bitreverse.i32(i32 %b)
   store i32 %call, i32 addrspace(1)* %res, align 4
   ret void
 }
 
 declare i32 @llvm.bitreverse.i32(i32)