[X86] 8bit divrem: Improve codegen for AH register extraction.

[ab]

Summary

For 8-bit divrems where the remainder is used, we used to generate:

divb  %sil
shrw  $8, %ax
movzbl  %al, %eax

That was to avoid an H-reg access, which is problematic mainly because
it isn't possible in REX-prefixed instructions.

This patch optimizes that to:

divb  %sil
movzbl  %ah, %eax

To do that, we explicitly extend AH, and extract the L-subreg in the
resulting register. The extension is done using the NOREX variants of
MOVZX. To support signed operations, MOVSX_NOREX is also added.
Further, this introduces a new SDNode type, [us]divrem_ext_hreg, which is
then lowered to a sequence containing a single zext (rather than 2).

The new node isn't ideal, but I'm not aware of any alternatives to avoid redundant extensions.

[ab]

Remove support for 64-bit sexts: those are impossible from h-regs.

I had previously added a subreg_to_reg to also support i64 extensions for free. But I just had a flash where I remembered that we still need to explicitly movsx to a 64-bit register.

While there, remove useless ops vectors.

[qcolombet]

Hi Ahmed,

I am wondering if you did not miss to include some files in the diff. I may be wrong but I would have expected to see some definitions of DAG nodes for SDIVREM8_SEXT_HREG and UDIVREM8_ZEXT_HREG.

Other comments inlined.

Thanks,
-Quentin

lib/Target/X86/X86ISelDAGToDAG.cpp

2545

You slightly change the condition here by removing Subtarget->is64Bit().
I believe this is correct, but you need to add a test case for that.

2574

Now that you are done, does this debug line still make sense?

test/CodeGen/X86/divrem8_ext.ll

1

Do a x86_64 run and a i386 to test the change in the condition of the lowering of U/SREM.

[ab]

Also test i386 codegen.

[ab]

Remove .td node definition.

[ab]

Hi Quentin,

I added 32-bit checks.
However, for the node definitions, are you talking about TableGen? If so, I didn't add those because I don't expect the added node types to be ever referenced in TableGen. I can still add them for consistency though, if you'd like.

Thanks for the review!

-Ahmed

lib/Target/X86/X86ISelDAGToDAG.cpp

2545

Right, I didn't explicitly check 32-bit. Added in the test file.

2574

This is modeled after the debug outputs in the other parts of the code (for instance line 2582).

[qcolombet]

I added 32-bit checks.

Thanks.

However, for the node definitions, are you talking about TableGen?

Yes, I was talking about that.

If so, I didn't add those because I don't expect the added node types to be ever referenced in TableGen. I can still add them for consistency though, if you'd like.

Fair enough, that is fine :).

LGTM then.

Thanks,
-Quentin

[ab]

Closed by commit rL221176 (authored by @ab).

lib/Target/X86/X86ISelDAGToDAG.cpp

if (!SDValue(Node, 1).use_empty()) {
       ReplaceUses(SDValue(Node, 1), ResHi);
       DEBUG(dbgs() << "=> "; ResHi.getNode()->dump(CurDAG); dbgs() << '\n');
     }
 
     return nullptr;
   }
 
   case ISD::SDIVREM:
-  case ISD::UDIVREM: {
+  case ISD::UDIVREM:
+  case X86ISD::SDIVREM8_SEXT_HREG:
+  case X86ISD::UDIVREM8_ZEXT_HREG: {
     SDValue N0 = Node->getOperand(0);
     SDValue N1 = Node->getOperand(1);
 
-    bool isSigned = Opcode == ISD::SDIVREM;
+    bool isSigned = (Opcode == ISD::SDIVREM ||
+                     Opcode == X86ISD::SDIVREM8_SEXT_HREG);
     if (!isSigned) {
       switch (NVT.SimpleTy) {
       default: llvm_unreachable("Unsupported VT!");
       case MVT::i8:  Opc = X86::DIV8r;  MOpc = X86::DIV8m;  break;
       case MVT::i16: Opc = X86::DIV16r; MOpc = X86::DIV16m; break;
       case MVT::i32: Opc = X86::DIV32r; MOpc = X86::DIV32m; break;
       case MVT::i64: Opc = X86::DIV64r; MOpc = X86::DIV64m; break;
       }
if (foldedLoad) {
       InFlag = SDValue(CNode, 1);
       // Update the chain.
       ReplaceUses(N1.getValue(1), SDValue(CNode, 0));
     } else {
       InFlag =
         SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, N1, InFlag), 0);
     }
 
-    // Prevent use of AH in a REX instruction by referencing AX instead.
-    // Shift it down 8 bits.
+    // Prevent use of AH in a REX instruction by explicitly copying it to
+    // an ABCD_L register.
     //
     // The current assumption of the register allocator is that isel
-    // won't generate explicit references to the GPR8_NOREX registers. If
+    // won't generate explicit references to the GR8_ABCD_H registers. If
     // the allocator and/or the backend get enhanced to be more robust in
     // that regard, this can be, and should be, removed.
-    if (HiReg == X86::AH && Subtarget->is64Bit() &&
-        !SDValue(Node, 1).use_empty()) {
-      SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
-                                              X86::AX, MVT::i16, InFlag);
-      InFlag = Result.getValue(2);
-
-      // If we also need AL (the quotient), get it by extracting a subreg from
-      // Result. The fast register allocator does not like multiple CopyFromReg
-      // nodes using aliasing registers.
-      if (!SDValue(Node, 0).use_empty())
-        ReplaceUses(SDValue(Node, 0),
-          CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result));
-
-      // Shift AX right by 8 bits instead of using AH.
-      Result = SDValue(CurDAG->getMachineNode(X86::SHR16ri, dl, MVT::i16,
-                                         Result,
-                                         CurDAG->getTargetConstant(8, MVT::i8)),
-                       0);
-      ReplaceUses(SDValue(Node, 1),
-        CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result));
+    if (HiReg == X86::AH && !SDValue(Node, 1).use_empty()) {
+      SDValue AHCopy = CurDAG->getRegister(X86::AH, MVT::i8);
+      unsigned AHExtOpcode =
+          isSigned ? X86::MOVSX32_NOREXrr8 : X86::MOVZX32_NOREXrr8;
+
+      SDNode *RNode = CurDAG->getMachineNode(AHExtOpcode, dl, MVT::i32,
+                                             MVT::Glue, AHCopy, InFlag);
+      SDValue Result(RNode, 0);
+      InFlag = SDValue(RNode, 1);
+
+      if (Opcode == X86ISD::UDIVREM8_ZEXT_HREG ||
+          Opcode == X86ISD::SDIVREM8_SEXT_HREG) {
+        if (Node->getValueType(1) == MVT::i64) {
+          // It's not possible to directly movsx AH to a 64bit register, because
+          // the latter needs the REX prefix, but the former can't have it.
+          assert(Opcode != X86ISD::SDIVREM8_SEXT_HREG &&
+                 "Unexpected i64 sext of h-register");
+          Result =
+              SDValue(CurDAG->getMachineNode(
+                          TargetOpcode::SUBREG_TO_REG, dl, MVT::i64,
+                          CurDAG->getTargetConstant(0, MVT::i64), Result,
+                          CurDAG->getTargetConstant(X86::sub_32bit, MVT::i32)),
+        }
+      } else {
+        Result =
+            CurDAG->getTargetExtractSubreg(X86::sub_8bit, dl, MVT::i8, Result);
+      }
+      ReplaceUses(SDValue(Node, 1), Result);
+      DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');
     }
     // Copy the division (low) result, if it is needed.
     if (!SDValue(Node, 0).use_empty()) {
       SDValue Result = CurDAG->getCopyFromReg(CurDAG->getEntryNode(), dl,
                                                 LoReg, NVT, InFlag);
       InFlag = Result.getValue(2);
       ReplaceUses(SDValue(Node, 0), Result);
       DEBUG(dbgs() << "=> "; Result.getNode()->dump(CurDAG); dbgs() << '\n');

lib/Target/X86/X86ISelLowering.h

enum NodeType {
 
       BEXTR,  // BEXTR - Bit field extract
 
       UMUL, // LOW, HI, FLAGS = umul LHS, RHS
 
       // 8-bit SMUL/UMUL - AX, FLAGS = smul8/umul8 AL, RHS
       SMUL8, UMUL8,
 
+      // 8-bit divrem that zero-extend the high result (AH).
+      UDIVREM8_ZEXT_HREG,
+      SDIVREM8_SEXT_HREG,
+
       // 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

const char *X86TargetLowering::getTargetNodeName(unsigned Opcode) const {
   case X86ISD::PCMPEQM:            return "X86ISD::PCMPEQM";
   case X86ISD::PCMPGTM:            return "X86ISD::PCMPGTM";
   case X86ISD::ADD:                return "X86ISD::ADD";
   case X86ISD::SUB:                return "X86ISD::SUB";
   case X86ISD::ADC:                return "X86ISD::ADC";
   case X86ISD::SBB:                return "X86ISD::SBB";
   case X86ISD::SMUL:               return "X86ISD::SMUL";
   case X86ISD::UMUL:               return "X86ISD::UMUL";
+  case X86ISD::SDIVREM8_SEXT_HREG: return "X86ISD::SDIVREM8_SEXT_HREG";
+  case X86ISD::UDIVREM8_ZEXT_HREG: return "X86ISD::UDIVREM8_ZEXT_HREG";
   case X86ISD::INC:                return "X86ISD::INC";
   case X86ISD::DEC:                return "X86ISD::DEC";
   case X86ISD::OR:                 return "X86ISD::OR";
   case X86ISD::XOR:                return "X86ISD::XOR";
   case X86ISD::AND:                return "X86ISD::AND";
   case X86ISD::BEXTR:              return "X86ISD::BEXTR";
   case X86ISD::MUL_IMM:            return "X86ISD::MUL_IMM";
   case X86ISD::PTEST:              return "X86ISD::PTEST";
if (VT == MVT::v4i64 && (N0.getOpcode() == ISD::ANY_EXTEND ||
     }
   }
   return SDValue();
 }
 
 static SDValue PerformSExtCombine(SDNode *N, SelectionDAG &DAG,
                                   TargetLowering::DAGCombinerInfo &DCI,
                                   const X86Subtarget *Subtarget) {
+  SDValue N0 = N->getOperand(0);
+  EVT VT = N->getValueType(0);
+
+  // (i8,i32 sext (sdivrem (i8 x, i8 y)) ->
+  // (i8,i32 (sdivrem_sext_hreg (i8 x, i8 y)
+  // This exposes the sext to the sdivrem lowering, so that it directly extends
+  // from AH (which we otherwise need to do contortions to access).
+  if (N0.getOpcode() == ISD::SDIVREM && N0.getResNo() == 1 &&
+      N0.getValueType() == MVT::i8 && VT == MVT::i32) {
+    SDLoc dl(N);
+    SDVTList NodeTys = DAG.getVTList(MVT::i8, VT);
+    SDValue R = DAG.getNode(X86ISD::SDIVREM8_SEXT_HREG, dl, NodeTys,
+                            N0.getOperand(0), N0.getOperand(1));
+    DAG.ReplaceAllUsesOfValueWith(N0.getValue(0), R.getValue(0));
+    return R.getValue(1);
+  }
+
   if (!DCI.isBeforeLegalizeOps())
     return SDValue();
 
   if (!Subtarget->hasFp256())
     return SDValue();
 
-  EVT VT = N->getValueType(0);
   if (VT.isVector() && VT.getSizeInBits() == 256) {
     SDValue R = WidenMaskArithmetic(N, DAG, DCI, Subtarget);
     if (R.getNode())
       return R;
   }
 
   return SDValue();
 }
if (N0.getOpcode() == ISD::TRUNCATE &&
     }
   }
   if (VT.is256BitVector()) {
     SDValue R = WidenMaskArithmetic(N, DAG, DCI, Subtarget);
     if (R.getNode())
       return R;
   }
 
+  // (i8,i32 zext (udivrem (i8 x, i8 y)) ->
+  // (i8,i32 (udivrem_zext_hreg (i8 x, i8 y)
+  // This exposes the zext to the udivrem lowering, so that it directly extends
+  // from AH (which we otherwise need to do contortions to access).
+  if (N0.getOpcode() == ISD::UDIVREM &&
+      N0.getResNo() == 1 && N0.getValueType() == MVT::i8 &&
+      (VT == MVT::i32 || VT == MVT::i64)) {
+    SDVTList NodeTys = DAG.getVTList(MVT::i8, VT);
+    SDValue R = DAG.getNode(X86ISD::UDIVREM8_ZEXT_HREG, dl, NodeTys,
+                            N0.getOperand(0), N0.getOperand(1));
+    DAG.ReplaceAllUsesOfValueWith(N0.getValue(0), R.getValue(0));
+    return R.getValue(1);
+  }
+
   return SDValue();
 }
 
 // Optimize x == -y --> x+y == 0
 //          x != -y --> x+y != 0
 static SDValue PerformISDSETCCCombine(SDNode *N, SelectionDAG &DAG,
                                       const X86Subtarget* Subtarget) {
   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();

lib/Target/X86/X86InstrExtension.td

def MOVZX32rm16: I<0xB7, MRMSrcMem, (outs GR32:$dst), (ins i16mem:$src),
                    TB, OpSize32, Sched<[WriteALULd]>;
 
 // These are the same as the regular MOVZX32rr8 and MOVZX32rm8
 // except that they use GR32_NOREX for the output operand register class
 // instead of GR32. This allows them to operate on h registers on x86-64.
 let neverHasSideEffects = 1, isCodeGenOnly = 1 in {
 def MOVZX32_NOREXrr8 : I<0xB6, MRMSrcReg,
                          (outs GR32_NOREX:$dst), (ins GR8_NOREX:$src),
-                         "movz{bl|x}\t{$src, $dst|$dst, $src}",
+                         "movz{bl|x}\t{$src, $dst|$dst, $src}  # NOREX",
                          [], IIC_MOVZX>, TB, Sched<[WriteALU]>;
 let mayLoad = 1 in
 def MOVZX32_NOREXrm8 : I<0xB6, MRMSrcMem,
                          (outs GR32_NOREX:$dst), (ins i8mem_NOREX:$src),
-                         "movz{bl|x}\t{$src, $dst|$dst, $src}",
+                         "movz{bl|x}\t{$src, $dst|$dst, $src}  # NOREX",
                          [], IIC_MOVZX>, TB, Sched<[WriteALULd]>;
+
+def MOVSX32_NOREXrr8 : I<0xBE, MRMSrcReg,
+                         (outs GR32_NOREX:$dst), (ins GR8_NOREX:$src),
+                         "movs{bl|x}\t{$src, $dst|$dst, $src}  # NOREX",
+                         [], IIC_MOVSX>, TB, Sched<[WriteALU]>;
+let mayLoad = 1 in
+def MOVSX32_NOREXrm8 : I<0xBE, MRMSrcMem,
+                         (outs GR32_NOREX:$dst), (ins i8mem_NOREX:$src),
+                         "movs{bl|x}\t{$src, $dst|$dst, $src}  # NOREX",
+                         [], IIC_MOVSX>, TB, Sched<[WriteALULd]>;
 }
 
 // MOVSX64rr8 always has a REX prefix and it has an 8-bit register
 // operand, which makes it a rare instruction with an 8-bit register
 // operand that can never access an h register. If support for h registers
 // were generalized, this would require a special register class.
 def MOVSX64rr8 : RI<0xBE, MRMSrcReg, (outs GR64:$dst), (ins GR8 :$src),
                     "movs{bq|x}\t{$src, $dst|$dst, $src}",

test/CodeGen/X86/divrem8_ext.ll

+; RUN: llc < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+define zeroext i8 @test_udivrem_zext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_udivrem_zext_ah
+; CHECK:   movq   _z@GOTPCREL(%rip), [[REG_ZPTR:%[a-z0-9]+]]
+; CHECK:   movzbl %dil, %eax
+; CHECK:   divb   %sil
+; CHECK:   movzbl %ah, [[REG_REM:%[a-z0-9]+]]
+; CHECK:   movb   %al, ([[REG_ZPTR]])
+; CHECK:   movl   [[REG_REM]], %eax
+; CHECK:   retq
+  %div = udiv i8 %x, %y
+  store i8 %div, i8* @z
+  %1 = urem i8 %x, %y
+  ret i8 %1
+}
+
+define zeroext i8 @test_urem_zext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_urem_zext_ah
+; CHECK:   movzbl %dil, %eax
+; CHECK:   divb   %sil
+; CHECK:   movzbl %ah, %eax
+; CHECK:   retq
+  %1 = urem i8 %x, %y
+  ret i8 %1
+}
+
+define i8 @test_urem_noext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_urem_noext_ah
+; CHECK:   movzbl %dil, %eax
+; CHECK:   divb   %sil
+; CHECK:   movzbl %ah, %eax
+; CHECK:   addb   %sil, %al
+; CHECK:   retq
+  %1 = urem i8 %x, %y
+  %2 = add i8 %1, %y
+  ret i8 %2
+}
+
+define i64 @test_urem_zext64_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_urem_zext64_ah
+; CHECK:   movzbl %dil, %eax
+; CHECK:   divb   %sil
+; CHECK:   movzbl %ah, %eax
+; CHECK:   retq
+  %1 = urem i8 %x, %y
+  %2 = zext i8 %1 to i64
+  ret i64 %2
+}
+
+define signext i8 @test_sdivrem_sext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_sdivrem_sext_ah
+; CHECK:   movq   _z@GOTPCREL(%rip), [[REG_ZPTR:%[a-z0-9]+]]
+; CHECK:   movb   %dil, %al
+; CHECK:   cbtw
+; CHECK:   idivb  %sil
+; CHECK:   movsbl %ah, [[REG_REM:%[a-z0-9]+]]
+; CHECK:   movb   %al, ([[REG_ZPTR]])
+; CHECK:   movl   [[REG_REM]], %eax
+; CHECK:   retq
+  %div = sdiv i8 %x, %y
+  store i8 %div, i8* @z
+  %1 = srem i8 %x, %y
+  ret i8 %1
+}
+
+define signext i8 @test_srem_sext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_srem_sext_ah
+; CHECK:   movb   %dil, %al
+; CHECK:   cbtw
+; CHECK:   idivb  %sil
+; CHECK:   movsbl %ah, %eax
+; CHECK:   retq
+  %1 = srem i8 %x, %y
+  ret i8 %1
+}
+
+define i8 @test_srem_noext_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_srem_noext_ah
+; CHECK:   movb   %dil, %al
+; CHECK:   cbtw
+; CHECK:   idivb  %sil
+; CHECK:   movsbl %ah, %eax
+; CHECK:   addb   %sil, %al
+; CHECK:   retq
+  %1 = srem i8 %x, %y
+  %2 = add i8 %1, %y
+  ret i8 %2
+}
+
+define i64 @test_srem_sext64_ah(i8 %x, i8 %y) {
+; CHECK-LABEL: test_srem_sext64_ah
+; CHECK:   movb   %dil, %al
+; CHECK:   cbtw
+; CHECK:   idivb  %sil
+; CHECK:   movsbl %ah, %eax
+; CHECK:   movsbq %al, %rax
+; CHECK:   retq
+  %1 = srem i8 %x, %y
+  %2 = sext i8 %1 to i64
+  ret i64 %2
+}
+
+@z = external global i8