[LLVM] New carry-less multiplication instruction llvm.experimental.clmul

[shawnl]

Summary

This is mostly glue code, with only a few instructions in ARM wired up
(PMUL but not PMULL), and no fallback code.

[craig.topper]

llvm/docs/LangRef.rst

8417

Glois - > Galois?

equivilent -> equivalent

[shawnl]

updated docs

[kparzysz]

llvm/docs/LangRef.rst

8471

I would reword this to define what this operation does, then add a remark about how it's different from integer multiplication. Something like:

"In the scalar version with operands of type iN, both operands are assumed to be polynomials with binary coefficients, where the most significant bit corresponds to the coefficient at x^(N-1). The operation calculates the result of polynomial multiplication of the operands, modulo x^N.
The vector version treats each element of the input vector as a separate polynomial.

Note that this is different from integer multiplication ..."

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/docs/LangRef.rst

::
       <result> = frem [fast-math flags]* <ty> <op1>, <op2>   ; yields ty:result
 
 Overview:
 """""""""
 
 The '``frem``' instruction returns the remainder from the division of
 its two operands.
 
 Arguments:
 """"""""""
 
 The two arguments to the '``frem``' instruction must be
 :ref:`floating-point <t_floating>` or :ref:`vector <t_vector>` of
 floating-point values. Both arguments must have identical types.
 
 Semantics:
 """"""""""

 
 Example:
 """"""""
 
 .. code-block:: text
 
       <result> = frem float 4.0, %var          ; yields float:result = 4.0 % %var
 
+'``llvm.experimental.clmul``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      define <16 x i8> @llvm.experimental.clmul.v16i8(<16 x i8> <in0>, <16 x i8> <in1>)
+
+Overview:
+"""""""""
+
+This is an overloaded intrinsic. You can use '``llvm.experimental.clmul.*``' on
+any integer bit width and for different address spaces. Not all targets support
+all bit widths however.
+
+Arguments:
+""""""""""
+
+The two arguments to the '``llvm.experimental.clmul.*``' intrinsic must be
+:ref:`integer <t_integer>` or :ref:`vector <t_vector>` of integer values. Both
+arguments must have identical types.
+
+Semantics:
+""""""""""
+
+This is not the same as multiplication. It is as if multiplication was done,
+but with no carrying of overflow values. If the operands are polynomials in a
+Galois field of 2 elements, then this is equivalent to multiplication. Thus,
+this operation is also known as polynomial multiplication.
+
+There is no guarantee that execution will happen in constant time. In particular,
+if there is no hardware carryless-multiplication, and multiplication is not
+constant time, then the lowering to multiplication will not be constant time.
+
 .. _bitwiseops:
 
 Bitwise Binary Operations
 -------------------------
 
 Bitwise binary operators are used to do various forms of bit-twiddling
 in a program. They are generally very efficient instructions and can
 commonly be strength reduced from other instructions. They require two

llvm/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
 
   /// Byte Swap and Counting operators.
   BSWAP,
   CTTZ,
   CTLZ,
   CTPOP,
   BITREVERSE,
 
+  // Carry-less multiplication.
+  CLMUL,
+
   /// Bit counting operators with an undefined result for zero inputs.
   CTTZ_ZERO_UNDEF,
   CTLZ_ZERO_UNDEF,
 
   /// Select(COND, TRUEVAL, FALSEVAL).  If the type of the boolean COND is not
   /// i1 then the high bits must conform to getBooleanContents.
   SELECT,
 

llvm/include/llvm/IR/Intrinsics.td

 }
 
 let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn,
                       ImmArg<ArgIndex<1>>] in {
   def int_ctlz : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>, llvm_i1_ty]>;
   def int_cttz : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>, llvm_i1_ty]>;
 }
 
+let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn, Commutative] in {
+  def int_experimental_clmul : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>, LLVMMatchType<0>]>;
+}
+
 //===------------------------ Debugger Intrinsics -------------------------===//
 //
 
 // None of these intrinsics accesses memory at all...but that doesn't
 // mean the optimizers can change them aggressively.  Special handling
 // needed in a few places. These synthetic intrinsics have no
 // side-effects and just mark information about their operands.
 let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn] in {

llvm/include/llvm/Support/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_CTPOP)
 
 /// Generic byte swap.
 HANDLE_TARGET_OPCODE(G_BSWAP)
 
 /// Generic bit reverse.
 HANDLE_TARGET_OPCODE(G_BITREVERSE)
 
+/// Carry-less multiplication.
+HANDLE_TARGET_OPCODE(G_CLMUL)
+
 /// Floating point ceil.
 HANDLE_TARGET_OPCODE(G_FCEIL)
 
 /// Floating point cosine.
 HANDLE_TARGET_OPCODE(G_FCOS)
 
 /// Floating point sine.
 HANDLE_TARGET_OPCODE(G_FSIN)

llvm/include/llvm/Target/GenericOpcodes.td

 }
 
 def G_CTPOP : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type1:$src);
   let hasSideEffects = 0;
 }
 
+def G_CLMUL : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src1, type0:$src2);
+  let hasSideEffects = 0;
+}
+
 def G_BSWAP : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src);
   let hasSideEffects = 0;
 }
 
 def G_BITREVERSE : GenericInstruction {
   let OutOperandList = (outs type0:$dst);

llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td

 def : GINodeEquiv<G_BITREVERSE, bitreverse>;
 def : GINodeEquiv<G_FSHL, fshl>;
 def : GINodeEquiv<G_FSHR, fshr>;
 def : GINodeEquiv<G_CTLZ, ctlz>;
 def : GINodeEquiv<G_CTTZ, cttz>;
 def : GINodeEquiv<G_CTLZ_ZERO_UNDEF, ctlz_zero_undef>;
 def : GINodeEquiv<G_CTTZ_ZERO_UNDEF, cttz_zero_undef>;
 def : GINodeEquiv<G_CTPOP, ctpop>;
+def : GINodeEquiv<G_CLMUL, clmul>;
 def : GINodeEquiv<G_EXTRACT_VECTOR_ELT, vector_extract>;
 def : GINodeEquiv<G_CONCAT_VECTORS, concat_vectors>;
 def : GINodeEquiv<G_BUILD_VECTOR, build_vector>;
 def : GINodeEquiv<G_FCEIL, fceil>;
 def : GINodeEquiv<G_FCOS, fcos>;
 def : GINodeEquiv<G_FSIN, fsin>;
 def : GINodeEquiv<G_FABS, fabs>;
 def : GINodeEquiv<G_FSQRT, fsqrt>;

llvm/include/llvm/Target/TargetSelectionDAG.td

 def abs        : SDNode<"ISD::ABS"        , SDTIntUnaryOp>;
 def bitreverse : SDNode<"ISD::BITREVERSE" , SDTIntUnaryOp>;
 def bswap      : SDNode<"ISD::BSWAP"      , SDTIntUnaryOp>;
 def ctlz       : SDNode<"ISD::CTLZ"       , SDTIntBitCountUnaryOp>;
 def cttz       : SDNode<"ISD::CTTZ"       , SDTIntBitCountUnaryOp>;
 def ctpop      : SDNode<"ISD::CTPOP"      , SDTIntBitCountUnaryOp>;
 def ctlz_zero_undef : SDNode<"ISD::CTLZ_ZERO_UNDEF", SDTIntBitCountUnaryOp>;
 def cttz_zero_undef : SDNode<"ISD::CTTZ_ZERO_UNDEF", SDTIntBitCountUnaryOp>;
+def clmul : SDNode<"ISD::CLMUL"      , SDTIntBinOp, [SDNPCommutative]>;
 def sext       : SDNode<"ISD::SIGN_EXTEND", SDTIntExtendOp>;
 def zext       : SDNode<"ISD::ZERO_EXTEND", SDTIntExtendOp>;
 def anyext     : SDNode<"ISD::ANY_EXTEND" , SDTIntExtendOp>;
 def trunc      : SDNode<"ISD::TRUNCATE"   , SDTIntTruncOp>;
 def bitconvert : SDNode<"ISD::BITCAST"    , SDTUnaryOp>;
 def addrspacecast : SDNode<"ISD::ADDRSPACECAST", SDTUnaryOp>;
 def extractelt : SDNode<"ISD::EXTRACT_VECTOR_ELT", SDTVecExtract>;
 def insertelt  : SDNode<"ISD::INSERT_VECTOR_ELT", SDTVecInsert>;

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

switch (ID) {
     case Intrinsic::fshr:
       return TargetOpcode::G_FSHR;
     case Intrinsic::ceil:
       return TargetOpcode::G_FCEIL;
     case Intrinsic::cos:
       return TargetOpcode::G_FCOS;
     case Intrinsic::ctpop:
       return TargetOpcode::G_CTPOP;
+    case Intrinsic::experimental_clmul:
+      return TargetOpcode::G_CLMUL;
     case Intrinsic::exp:
       return TargetOpcode::G_FEXP;
     case Intrinsic::exp2:
       return TargetOpcode::G_FEXP2;
     case Intrinsic::fabs:
       return TargetOpcode::G_FABS;
     case Intrinsic::copysign:
       return TargetOpcode::G_FCOPYSIGN;

llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

#endif
 
   case ISD::FLT_ROUNDS_: Res = PromoteIntRes_FLT_ROUNDS(N); break;
 
   case ISD::AND:
   case ISD::OR:
   case ISD::XOR:
   case ISD::ADD:
   case ISD::SUB:
+  case ISD::CLMUL:
   case ISD::MUL:         Res = PromoteIntRes_SimpleIntBinOp(N); break;
 
   case ISD::SDIV:
   case ISD::SREM:        Res = PromoteIntRes_SExtIntBinOp(N); break;
 
   case ISD::UDIV:
   case ISD::UREM:        Res = PromoteIntRes_ZExtIntBinOp(N); break;
 

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::ctlz: {
     return;
   }
   case Intrinsic::ctpop: {
     SDValue Arg = getValue(I.getArgOperand(0));
     EVT Ty = Arg.getValueType();
     setValue(&I, DAG.getNode(ISD::CTPOP, sdl, Ty, Arg));
     return;
   }
+  case Intrinsic::experimental_clmul: {
+    SDValue Arg0 = getValue(I.getArgOperand(0));
+    EVT Ty = Arg0.getValueType();
+    SDValue Arg1 = getValue(I.getArgOperand(1));
+    setValue(&I, DAG.getNode(ISD::CLMUL, sdl, Ty, {Arg0, Arg1}));
+    return;
+  }
   case Intrinsic::fshl:
   case Intrinsic::fshr: {
     bool IsFSHL = Intrinsic == Intrinsic::fshl;
     SDValue X = getValue(I.getArgOperand(0));
     SDValue Y = getValue(I.getArgOperand(1));
     SDValue Z = getValue(I.getArgOperand(2));
     EVT VT = X.getValueType();
     SDValue BitWidthC = DAG.getConstant(VT.getScalarSizeInBits(), sdl, VT);

llvm/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::BITREVERSE:                 return "bitreverse";
   case ISD::BSWAP:                      return "bswap";
   case ISD::CTPOP:                      return "ctpop";
   case ISD::CTTZ:                       return "cttz";
   case ISD::CTTZ_ZERO_UNDEF:            return "cttz_zero_undef";
   case ISD::CTLZ:                       return "ctlz";
   case ISD::CTLZ_ZERO_UNDEF:            return "ctlz_zero_undef";
 
+  case ISD::CLMUL:
+    return "clmul";
+
   // Trampolines
   case ISD::INIT_TRAMPOLINE:            return "init_trampoline";
   case ISD::ADJUST_TRAMPOLINE:          return "adjust_trampoline";
 
   case ISD::CONDCODE:
     switch (cast<CondCodeSDNode>(this)->get()) {
     default: llvm_unreachable("Unknown setcc condition!");
     case ISD::SETOEQ:                   return "setoeq";

llvm/lib/IR/AutoUpgrade.cpp

if (Name.startswith("aarch64.neon.addp")) {
         break; // Invalid IR.
       VectorType *Ty = dyn_cast<VectorType>(F->getReturnType());
       if (Ty && Ty->getElementType()->isFloatingPointTy()) {
         NewFn = Intrinsic::getDeclaration(F->getParent(),
                                           Intrinsic::aarch64_neon_faddp, Ty);
         return true;
       }
     }
+    // The last . here is important, as pmull is a differen't instruction
+    if (Name.startswith("aarch64.neon.pmul.")) {
+      if (F->arg_size() != 2)
+        break; // Invalid IR.
+      VectorType *Ty = dyn_cast<VectorType>(F->getReturnType());
+      if (Ty && Ty->getElementType()->isIntegerTy() &&
+          Ty->getElementType()->getIntegerBitWidth() == 8)
+        NewFn = Intrinsic::getDeclaration(
+            F->getParent(), Intrinsic::experimental_clmul, F->getReturnType());
+
+      return true;
+    }
     break;
   }
 
   case 'c': {
     if (Name.startswith("ctlz.") && F->arg_size() == 1) {
       rename(F);
       NewFn = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
                                         F->arg_begin()->getType());

   case Intrinsic::arm_neon_vst3lane:
   case Intrinsic::arm_neon_vst4lane: {
     SmallVector<Value *, 4> Args(CI->arg_operands().begin(),
                                  CI->arg_operands().end());
     NewCall = Builder.CreateCall(NewFn, Args);
     break;
   }
 
+  case Intrinsic::experimental_clmul: {
+    SmallVector<Value *, 4> Args(CI->arg_operands().begin(),
+                                 CI->arg_operands().end());
+    NewCall = Builder.CreateCall(NewFn, Args);
+    break;
+  }
+
   case Intrinsic::bitreverse:
     NewCall = Builder.CreateCall(NewFn, {CI->getArgOperand(0)});
     break;
 
   case Intrinsic::ctlz:
   case Intrinsic::cttz:
     assert(CI->getNumArgOperands() == 1 &&
            "Mismatch between function args and call args");

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

AArch64TargetLowering::AArch64TargetLowering(const TargetMachine &TM,
   }
   setOperationAction(ISD::SREM, MVT::i32, Expand);
   setOperationAction(ISD::SREM, MVT::i64, Expand);
   setOperationAction(ISD::UDIVREM, MVT::i32, Expand);
   setOperationAction(ISD::UDIVREM, MVT::i64, Expand);
   setOperationAction(ISD::UREM, MVT::i32, Expand);
   setOperationAction(ISD::UREM, MVT::i64, Expand);
 
+  if (Subtarget->hasNEON()) {
+    setOperationAction(ISD::CLMUL, MVT::v16i8, Legal);
+    setOperationAction(ISD::CLMUL, MVT::v8i8, Legal);
+  }
+
   // Custom lower Add/Sub/Mul with overflow.
   setOperationAction(ISD::SADDO, MVT::i32, Custom);
   setOperationAction(ISD::SADDO, MVT::i64, Custom);
   setOperationAction(ISD::UADDO, MVT::i32, Custom);
   setOperationAction(ISD::UADDO, MVT::i64, Custom);
   setOperationAction(ISD::SSUBO, MVT::i32, Custom);
   setOperationAction(ISD::SSUBO, MVT::i64, Custom);
   setOperationAction(ISD::USUBO, MVT::i32, Custom);

llvm/lib/Target/AArch64/AArch64InstrInfo.td

 defm FSUB     : SIMDThreeSameVectorFP<0,1,0b010,"fsub", fsub>;
 
 // MLA and MLS are generated in MachineCombine
 defm MLA      : SIMDThreeSameVectorBHSTied<0, 0b10010, "mla", null_frag>;
 defm MLS      : SIMDThreeSameVectorBHSTied<1, 0b10010, "mls", null_frag>;
 
 defm MUL      : SIMDThreeSameVectorBHS<0, 0b10011, "mul", mul>;
 defm PMUL     : SIMDThreeSameVectorB<1, 0b10011, "pmul", int_aarch64_neon_pmul>;
+def : Pat<(v16i8 (clmul V128:$Rn, V128:$Rm)),
+          (PMULv16i8 V128:$Rn, V128:$Rm)>;
+def : Pat<(v8i8 (clmul V64:$Rn, V64:$Rm)),
+          (PMULv8i8 V64:$Rn, V64:$Rm)>;
+
 defm SABA     : SIMDThreeSameVectorBHSTied<0, 0b01111, "saba",
       TriOpFrag<(add node:$LHS, (int_aarch64_neon_sabd node:$MHS, node:$RHS))> >;
 defm SABD     : SIMDThreeSameVectorBHS<0,0b01110,"sabd", int_aarch64_neon_sabd>;
 defm SHADD    : SIMDThreeSameVectorBHS<0,0b00000,"shadd", int_aarch64_neon_shadd>;
 defm SHSUB    : SIMDThreeSameVectorBHS<0,0b00100,"shsub", int_aarch64_neon_shsub>;
 defm SMAXP    : SIMDThreeSameVectorBHS<0,0b10100,"smaxp", int_aarch64_neon_smaxp>;
 defm SMAX     : SIMDThreeSameVectorBHS<0,0b01100,"smax", smax>;
 defm SMINP    : SIMDThreeSameVectorBHS<0,0b10101,"sminp", int_aarch64_neon_sminp>;

llvm/test/CodeGen/AArch64/GlobalISel/legalizer-info-validation.mir

 # DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: G_BSWAP (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. the first uncovered type index: 1, OK
 # DEBUG-NEXT: .. the first uncovered imm index: 0, OK
 # DEBUG-NEXT: G_BITREVERSE (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: G_CLMUL (opcode {{[0-9]+}}): 1 type index, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: G_FCEIL (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: G_FCOS (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. the first uncovered type index: 1, OK
 # DEBUG-NEXT: .. the first uncovered imm index: 0, OK
 # DEBUG-NEXT: G_FSIN (opcode {{[0-9]+}}): 1 type index, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}

llvm/test/CodeGen/AArch64/clmul.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -verify-machineinstrs -o - %s -mtriple=aarch64-linux-gnu | FileCheck %s
+
+declare <16 x i8> @llvm.experimental.clmul.v16i8(<16 x i8>, <16 x i8>)
+
+define <16 x i8> @clmul_v16i8(<16 x i8> %l, <16 x i8> %r) {
+; CHECK-LABEL: clmul_v16i8:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    pmul v0.16b, v0.16b, v1.16b
+; CHECK-NEXT:    ret
+  %ret = call <16 x i8> @llvm.experimental.clmul.v16i8(<16 x i8> %l, <16 x i8> %r)
+  ret <16 x i8> %ret
+}
+
+declare <8 x i8> @llvm.experimental.clmul.v8i8(<8 x i8>, <8 x i8>)
+
+define <8 x i8> @clmul_v8i8(<8 x i8> %l, <8 x i8> %r) {
+; CHECK-LABEL: clmul_v8i8:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    pmul v0.8b, v0.8b, v1.8b
+; CHECK-NEXT:    ret
+  %ret = call <8 x i8> @llvm.experimental.clmul.v8i8(<8 x i8> %l, <8 x i8> %r)
+  ret <8 x i8> %ret
+}