[X86] Improve mul w/ overflow codegen, to MUL8+SETO.

[ab]

Summary

Currently, @llvm.smul.with.overflow.i8 expands to 9 instructions, where
3 are really needed.

This adds X86ISD::UMUL8/SMUL8 SD nodes, and custom lowers them to
MUL8/IMUL8 + SETO.

i8 is a special case because there is no two/three operand variants of
(I)MUL8, so the first operand and return value need to go in AL/AX.

Also, we can't write patterns for these instructions: TableGen refuses
patterns where output operands don't match SDNode results. In this case,
instructions where the output operand is an implicitly defined register.

A related special case (and FIXME) exists for MUL8 (X86InstrArith.td):

// FIXME: Used for 8-bit mul, ignore result upper 8 bits.
// This probably ought to be moved to a def : Pat<> if the
// syntax can be accepted.
[(set AL, (mul AL, GR8:$src)), (implicit EFLAGS)]

Ideally, these go away with UMUL8, but we still need to improve TableGen
support of implicit operands in patterns.

Before this change:

movsbl  %sil, %eax
movsbl  %dil, %ecx
imull   %eax, %ecx
movb    %cl, %al
sarb    $7, %al
movzbl  %al, %eax
movzbl  %ch, %esi
cmpl    %eax, %esi
setne   %al

After:

movb    %dil, %al
imulb   %sil
seto    %al

[ributzka]

Hi Ahmed,

this turned out to be a very nice and simple fix. I didn't know tblgen would give you such a hard time for this one.
Please check xaluo.ll for already existing tests for {u|s}mul.with.overflow and enable them for SelectionDAG.

Thanks and LGTM.

-Juergen

test/CodeGen/X86/i8-umulo.ll

26–48

There are already tests for this in xaluo.ll, but they are disabled for SelectionDAG.

[ab]

Closed by commit rL220516 (authored by @ab).

lib/Target/X86/X86ISelDAGToDAG.cpp

case ISD::XOR: {
     }
 
     // Emit the smaller op and the shift.
     SDValue NewCst = CurDAG->getTargetConstant(Val >> ShlVal, CstVT);
     SDNode *New = CurDAG->getMachineNode(Op, dl, NVT, N0->getOperand(0),NewCst);
     return CurDAG->SelectNodeTo(Node, ShlOp, NVT, SDValue(New, 0),
                                 getI8Imm(ShlVal));
   }
+  case X86ISD::UMUL8:
+  case X86ISD::SMUL8: {
+    SDValue N0 = Node->getOperand(0);
+    SDValue N1 = Node->getOperand(1);
+
+    Opc = (Opcode == X86ISD::SMUL8 ? X86::IMUL8r : X86::MUL8r);
+
+    SDValue InFlag = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, X86::AL,
+                                          N0, SDValue()).getValue(1);
+
+    SDVTList VTs = CurDAG->getVTList(NVT, MVT::i32);
+    SDValue Ops[] = {N1, InFlag};
+    SDNode *CNode = CurDAG->getMachineNode(Opc, dl, VTs, Ops);
+
+    ReplaceUses(SDValue(Node, 0), SDValue(CNode, 0));
+    ReplaceUses(SDValue(Node, 1), SDValue(CNode, 1));
+    return nullptr;
+  }
   case X86ISD::UMUL: {
     SDValue N0 = Node->getOperand(0);
     SDValue N1 = Node->getOperand(1);
 
     unsigned LoReg;
     switch (NVT.SimpleTy) {
     default: llvm_unreachable("Unsupported VT!");
     case MVT::i8:  LoReg = X86::AL;  Opc = X86::MUL8r; break;

lib/Target/X86/X86ISelLowering.h

enum NodeType {
       // ADD, SUB, SMUL, etc. - Arithmetic operations with FLAGS results.
       ADD, SUB, ADC, SBB, SMUL,
       INC, DEC, OR, XOR, AND,
 
       BEXTR,  // BEXTR - Bit field extract
 
       UMUL, // LOW, HI, FLAGS = umul LHS, RHS
 
+      // 8-bit SMUL/UMUL - AX, FLAGS = smul8/umul8 AL, RHS
+      SMUL8, UMUL8,
+
       // MUL_IMM - X86 specific multiply by immediate.
       MUL_IMM,
 
       // PTEST - Vector bitwise comparisons.
       PTEST,
 
       // TESTP - Vector packed fp sign bitwise comparisons.
       TESTP,

lib/Target/X86/X86ISelLowering.cpp

for (unsigned i = 0, e = 3+Subtarget->is64Bit(); i != e; ++i) {
     setOperationAction(ISD::SADDO, VT, Custom);
     setOperationAction(ISD::UADDO, VT, Custom);
     setOperationAction(ISD::SSUBO, VT, Custom);
     setOperationAction(ISD::USUBO, VT, Custom);
     setOperationAction(ISD::SMULO, VT, Custom);
     setOperationAction(ISD::UMULO, VT, Custom);
   }
 
-  // There are no 8-bit 3-address imul/mul instructions
-  setOperationAction(ISD::SMULO, MVT::i8, Expand);
-  setOperationAction(ISD::UMULO, MVT::i8, Expand);
 
   if (!Subtarget->is64Bit()) {
     // These libcalls are not available in 32-bit.
     setLibcallName(RTLIB::SHL_I128, nullptr);
     setLibcallName(RTLIB::SRL_I128, nullptr);
     setLibcallName(RTLIB::SRA_I128, nullptr);
   }
 
case ISD::SSUBO:
     BaseOp = X86ISD::SUB;
     Cond = X86::COND_O;
     break;
   case ISD::USUBO:
     BaseOp = X86ISD::SUB;
     Cond = X86::COND_B;
     break;
   case ISD::SMULO:
-    BaseOp = X86ISD::SMUL;
+    BaseOp = N->getValueType(0) == MVT::i8 ? X86ISD::SMUL8 : X86ISD::SMUL;
     Cond = X86::COND_O;
     break;
   case ISD::UMULO: { // i64, i8 = umulo lhs, rhs --> i64, i64, i32 umul lhs,rhs
+    if (N->getValueType(0) == MVT::i8) {
+      BaseOp = X86ISD::UMUL8;
+      Cond = X86::COND_O;
+      break;
+    }
     SDVTList VTs = DAG.getVTList(N->getValueType(0), N->getValueType(0),
                                  MVT::i32);
     SDValue Sum = DAG.getNode(X86ISD::UMUL, DL, VTs, LHS, RHS);
 
     SDValue SetCC =
       DAG.getNode(X86ISD::SETCC, DL, MVT::i8,
                   DAG.getConstant(X86::COND_O, MVT::i32),
                   SDValue(Sum.getNode(), 2));

test/CodeGen/X86/i8-umulo.ll

 ; RUN: llc -mcpu=generic -march=x86 < %s | FileCheck %s
 ; PR19858
 
 declare {i8, i1} @llvm.umul.with.overflow.i8(i8 %a, i8 %b)
 define i8 @testumulo(i32 %argc) {
-; CHECK: imull
-; CHECK: testb %{{.+}}, %{{.+}}
-; CHECK: je [[NOOVERFLOWLABEL:.+]]
+; CHECK-LABEL: testumulo
+; CHECK: movb $25, %al
+; CHECK: mulb [[RESULTREG:.+]]
+; CHECK: jno [[NOOVERFLOWLABEL:.+]]
+; CHECK: movb [[RESULTREG]], %al
 ; CHECK: {{.*}}[[NOOVERFLOWLABEL]]:
-; CHECK-NEXT: movb
-; CHECK-NEXT: retl
+; CHECK: retl
 top:
   %RHS = trunc i32 %argc to i8
   %umul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 25, i8 %RHS)
   %ex = extractvalue { i8, i1 } %umul, 1
   br i1 %ex, label %overflow, label %nooverlow
 
 overflow:
   ret i8 %RHS
 
 nooverlow:
   %umul.value = extractvalue { i8, i1 } %umul, 0
   ret i8 %umul.value
 }
+
+declare {i8, i1} @llvm.smul.with.overflow.i8(i8 %a, i8 %b)
+define i8 @testsmulo(i32 %argc) {
+; CHECK-LABEL: testsmulo
+; CHECK: movb $25, %al
+; CHECK: imulb [[RESULTREG:.+]]
+; CHECK: jno [[NOOVERFLOWLABEL:.+]]
+; CHECK: movb [[RESULTREG]], %al
+; CHECK: {{.*}}[[NOOVERFLOWLABEL]]:
+; CHECK: retl
+top:
+  %RHS = trunc i32 %argc to i8
+  %smul = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 25, i8 %RHS)
+  %ex = extractvalue { i8, i1 } %smul, 1
+  br i1 %ex, label %overflow, label %nooverlow
+
+overflow:
+  ret i8 %RHS
+
+nooverlow:
+  %smul.value = extractvalue { i8, i1 } %smul, 0
+  ret i8 %smul.value
+}