[GlobalISel] Add G_BFI (bitfield insertion opcode)

[kschwarz]

Summary

Similar to G_[SU]BFX, many targets support similar bitfield insertion operations.

The most generic form extracts a number of bits (width) from a register (val), starting at bit 0.
Those bits are shifted by a certain shift amount (pos), and inserted into another register (src).
The resulting value is written into the output register:

%x = G_BFI %src, %val, %pos, %width

There are several patterns that can be combined to a generic bitfield insertion operation.

[foad]

llvm/include/llvm/Target/GenericOpcodes.td

1422

Can you add a comment like for sbfx and ubfx, and explain the limits on pos and witdth?

llvm/lib/CodeGen/MachineVerifier.cpp

1617

Any reason why it's not supported?

[kschwarz]

Add comment about range of operands

[kschwarz]

Thanks for the quick review @foad!

llvm/lib/CodeGen/MachineVerifier.cpp

1617

Not really. I wanted to focus on scalars first, and basically took this from the bitfield extracts above.

[foad]

Looks OK to me technically. I don't have an opinion on the big question of whether it's a good idea to introduce this opcode.

[paquette]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

Maybe add a FIXME or TODO here noting that it may make sense to extend this to vectors in the future? (I can't think of any use-cases, but maybe it makes sense on some target...)

llvm/test/MachineVerifier/test_g_bfi.mir

13

Some tests that would be good to add:

Test that the verifier complains when...

• Type index 0 != type index 1
• Type index 1 != type index 2
• Type index 3 != type index 4

e.g.

%x:_(s32) = G_BFI %y:_(s64), ...

should complain

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

Supporting on vectors is good for consistency and also can help with combine ordering problems

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

I don't think this should disallow vectors. Having the legalizer scalarize is trivial

I think it's a better question if the second/third operands can be vectors or not

[kschwarz]

I'm fine with allowing vectors, but shouldn't we then also allow vectors for the G_*BFX? What was the reason for disallowing them there?

[arsenm]

In D112435#3086994, @kschwarz wrote:

I'm fine with allowing vectors, but shouldn't we then also allow vectors for the G_*BFX? What was the reason for disallowing them there?

Yes. I don't think any opcode should be arbitrarily restricted from vectors

[paquette]

Yeah I think we can drop the vector restriction on G_*BFX. I don't think there's any reason to disallow vectors now that I think about it.

[foad]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

I think it's a better question if the second/third operands can be vectors or not

What are the rules for basic shifts like G_SHL ? I don't see any special handling for them in MachineVerifier. Do we really allow any combination of scalars and vectors for the first and second inputs?

[arsenm]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

For basic shifts it's all operands vector or all scalar

[foad]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

OK: D115868

[kschwarz]

llvm/lib/CodeGen/MachineVerifier.cpp

1616

Having the width and pos operands support vectors too allows different values per lane, which is probably the most generic form.
Are you aware of any ISA that has such instructions?

llvm/docs/GlobalISel/GenericOpcode.rst

.. code-block:: none
   ; the result.
   ;
   ; Example:
   ; %x = 1...11111[100]11 ---> %b = 0...00000[100]
   %lsb_two = G_CONSTANT i32 2
   %width_three = G_CONSTANT i32 3
   %b:_(s32) = G_UBFX %x, %lsb_two, %width_three
 
+G_BFI
+^^^^^
+Insert a range of bits into a register.
+
+The source operands are registers as follows:
+
+- Source: existing value
+- Value: the actual bits that will be inserted
+- Position: the starting bit position where the value will be inserted
+- Width: the bit-width of the value to be inserted
+
+The position (pos) and width operands are in the range:
+
+::
+
+      0 <= pos < pos + width <= source bitwidth, where all values are unsigned
+
+.. code-block:: none
+
+  ; Insert the value 0x5, with bit-width 8, starting at bit position 1
+  ;
+  ; Example:
+  ; %src = 0..0111..001000011 ------> %a = 0..0111..000001011
+  %val = G_CONSTANT i32 5
+  %pos_one = G_CONSTANT i32 1
+  %width_eight = G_CONSTANT i32 8
+  %a:_(s32) = G_BFI %src, %val, %pos_one, %width_eight
+
 Integer Operations
 -------------------
 
 G_ADD, G_SUB, G_MUL, G_AND, G_OR, G_XOR, G_SDIV, G_UDIV, G_SREM, G_UREM
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 These each perform their respective integer arithmetic on a scalar.
 

llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h

   }
 
   /// Build and insert \p Dst = G_UBFX \p Src, \p LSB, \p Width.
   MachineInstrBuilder buildUbfx(const DstOp &Dst, const SrcOp &Src,
                                 const SrcOp &LSB, const SrcOp &Width) {
     return buildInstr(TargetOpcode::G_UBFX, {Dst}, {Src, LSB, Width});
   }
 
+  /// Build and insert \p Dst = G_BFI \p Src, \p LSB, \p Width.
+  MachineInstrBuilder buildBfi(const DstOp &Dst, const SrcOp &Src,
+                               const SrcOp &Val, const SrcOp &Pos,
+                               const SrcOp &Width) {
+    return buildInstr(TargetOpcode::G_BFI, {Dst}, {Src, Val, Pos, Width});
+  }
+
   /// Build and insert \p Dst = G_ROTR \p Src, \p Amt
   MachineInstrBuilder buildRotateRight(const DstOp &Dst, const SrcOp &Src,
                                        const SrcOp &Amt) {
     return buildInstr(TargetOpcode::G_ROTR, {Dst}, {Src, Amt});
   }
 
   /// Build and insert \p Dst = G_ROTL \p Src, \p Amt
   MachineInstrBuilder buildRotateLeft(const DstOp &Dst, const SrcOp &Src,

llvm/include/llvm/Support/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_VECREDUCE_SMAX)
 HANDLE_TARGET_OPCODE(G_VECREDUCE_SMIN)
 HANDLE_TARGET_OPCODE(G_VECREDUCE_UMAX)
 HANDLE_TARGET_OPCODE(G_VECREDUCE_UMIN)
 
 HANDLE_TARGET_OPCODE(G_SBFX)
 HANDLE_TARGET_OPCODE(G_UBFX)
 
+HANDLE_TARGET_OPCODE(G_BFI)
+
 /// Marker for the end of the generic opcode.
 /// This is used to check if an opcode is in the range of the
 /// generic opcodes.
 HANDLE_TARGET_OPCODE_MARKER(PRE_ISEL_GENERIC_OPCODE_END, G_UBFX)
 
 /// BUILTIN_OP_END - This must be the last enum value in this list.
 /// The target-specific post-isel opcode values start here.
 HANDLE_TARGET_OPCODE_MARKER(GENERIC_OP_END, PRE_ISEL_GENERIC_OPCODE_END)

llvm/include/llvm/Target/GenericOpcodes.td

 // 0 <= lsb < lsb + width <= src bitwidth, where all values are unsigned.
 def G_UBFX : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src, type1:$lsb, type1:$width);
   let hasSideEffects = false;
 }
 
 //------------------------------------------------------------------------------
+// Bitfield insertion.
+//------------------------------------------------------------------------------
+
+// Generic bitfield insertion. The operands are in the range
+// 0 <= pos < pos + width <= src bitwidth, where all values are unsigned.
+def G_BFI : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src, type0:$val, type1:$pos, type1:$width);
+  let hasSideEffects = false;
+}
+
+//------------------------------------------------------------------------------
 // Optimization hints
 //------------------------------------------------------------------------------
 
 // Asserts that an operation has already been zero-extended from a specific
 // type.
 def G_ASSERT_ZEXT : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src, untyped_imm_0:$sz);

llvm/lib/CodeGen/MachineVerifier.cpp

void MachineVerifier::verifyPreISelGenericInstruction(const MachineInstr *MI) {
   case TargetOpcode::G_UBFX: {
     LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
     if (DstTy.isVector()) {
       report("Bitfield extraction is not supported on vectors", MI);
       break;
     }
     break;
   }
+  case TargetOpcode::G_BFI: {
+    LLT DstTy = MRI->getType(MI->getOperand(0).getReg());
+    if (DstTy.isVector()) {
+      report("Bitfield insertion is not supported on vectors", MI);
+      break;
+    }
+    break;
+  }
   case TargetOpcode::G_ROTR:
   case TargetOpcode::G_ROTL: {
     LLT Src1Ty = MRI->getType(MI->getOperand(1).getReg());
     LLT Src2Ty = MRI->getType(MI->getOperand(2).getReg());
     if (Src1Ty.isVector() != Src2Ty.isVector()) {
       report("Rotate requires operands to be either all scalars or all vectors",
              MI);
       break;

llvm/test/MachineVerifier/test_g_bfi.mir

+# RUN: not --crash llc -march=arm64 -verify-machineinstrs -run-pass none -o /dev/null %s 2>&1 | FileCheck %s
+# REQUIRES: aarch64-registered-target
+
+name:            test
+body: |
+  bb.0:
+    %v1:_(<2 x s64>) = G_IMPLICIT_DEF
+    %v2:_(<2 x s64>) = G_IMPLICIT_DEF
+    %v3:_(<2 x s64>) = G_IMPLICIT_DEF
+    %v4:_(<2 x s64>) = G_IMPLICIT_DEF
+
+    ; CHECK: *** Bad machine code: Bitfield insertion is not supported on vectors ***
+    %bfi_vector:_(<2 x s64>) = G_BFI %v1, %v2, %v3, %v4
+...

llvm/unittests/CodeGen/GlobalISel/MachineIRBuilderTest.cpp

TEST_F(AArch64GISelMITest, BuildBitfieldExtract) {
   ; CHECK: [[COPY1:%[0-9]+]]:_(s64) = COPY $x1
   ; CHECK: [[COPY2:%[0-9]+]]:_(s64) = COPY $x2
   ; CHECK: [[UBFX:%[0-9]+]]:_(s64) = G_UBFX [[COPY0]]:_, [[COPY1]]:_(s64), [[COPY2]]:_
   ; CHECK: [[SBFX:%[0-9]+]]:_(s64) = G_SBFX [[UBFX]]:_, [[COPY0]]:_(s64), [[COPY2]]:_
   )";
 
   EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
 }
+
+TEST_F(AArch64GISelMITest, BuildBitfieldInsert) {
+  StringRef MIRString = R"(
+    %3:_(s64) = COPY $x4
+  )";
+  setUp(MIRString.rtrim(' '));
+  if (!TM)
+    return;
+  LLT S64 = LLT::scalar(64);
+  SmallVector<Register, 4> Copies;
+  collectCopies(Copies, MF);
+
+  B.buildBfi(S64, Copies[0], Copies[1], Copies[2], Copies[3]);
+
+  const auto *CheckStr = R"(
+  ; CHECK: [[COPY0:%[0-9]+]]:_(s64) = COPY $x0
+  ; CHECK: [[COPY1:%[0-9]+]]:_(s64) = COPY $x1
+  ; CHECK: [[COPY2:%[0-9]+]]:_(s64) = COPY $x2
+  ; CHECK: [[COPY3:%[0-9]+]]:_(s64) = COPY $x4
+  ; CHECK: [[UBFX:%[0-9]+]]:_(s64) = G_BFI [[COPY0]]:_, [[COPY1]]:_, [[COPY2]]:_(s64), [[COPY3]]:_
+  )";
+
+  EXPECT_TRUE(CheckMachineFunction(*MF, CheckStr)) << *MF;
+}