X86: More efficient codegen for 64-bit compares on 32-bit target

[hans]

Summary

This patch changes the lowering of 64-bit integer compares on 32-bit x86 to be more efficient.

Example:

define i32 @test_slt(i64 %a, i64 %b) {
entry:
  %cmp = icmp slt i64 %a, %b
  br i1 %cmp, label %bb1, label %bb2
bb1:
  ret i32 1
bb2:
  ret i32 2
}

Before this patch:

test_slt:
        movl    4(%esp), %eax
        movl    8(%esp), %ecx
        cmpl    12(%esp), %eax
        setae   %al
        cmpl    16(%esp), %ecx
        setge   %cl
        je      .LBB2_2
        movb    %cl, %al
.LBB2_2:
        testb   %al, %al
        jne     .LBB2_4
        movl    $1, %eax
        retl
.LBB2_4:
        movl    $2, %eax
        retl

After this patch:

test_slt:
        movl    4(%esp), %eax
        movl    8(%esp), %ecx
        cmpl    12(%esp), %eax
        sbbl    16(%esp), %ecx
        jge     .LBB1_2
        movl    $1, %eax
        retl
.LBB1_2:
        movl    $2, %eax
        retl

On a 32-bit Clang bootstrap, this results in 19 KB binary size reduction.

[mkuper]

Hi Hans,

For the eq version, I find it a bit surprising that the new code is faster, but if benchmarksing says it is, who am I to argue. Adding Dave to the review for another opinion.

For the lt version, the new code definitely looks better than what we had before. It looks like there's another option though, which is more similar in spirit to the old code than to the new, but looks much nicer. This is what ICC produces:

test(long long, long long):
        movl      4(%esp), %eax 
        subl      12(%esp), %eax
        movl      8(%esp), %edx 
        sbbl      16(%esp), %edx
        jge       ..B1.3        
        movl      $1, %eax      
        ret                     
..B1.3:                         
        movl      $2, %eax      
        ret

Do you think it may be worth lowering the new pseudo to that, instead of the proposed sequence?

Michael

lib/Target/X86/X86ISelLowering.cpp

15235

I'm not a huge fan of this, but producing the pseudo in a target-specific pre-legalization DAG combine sounds like it may cause too many problems due to making the comparison opaque to other early combines.

21275

Why is this guaranteed?

[hans]

Thanks for the quick reply!

In D14496#285017, @mkuper wrote:

test(long long, long long):
        movl      4(%esp), %eax 
        subl      12(%esp), %eax
        movl      8(%esp), %edx 
        sbbl      16(%esp), %edx
        jge       ..B1.3        
        movl      $1, %eax      
        ret                     
..B1.3:                         
        movl      $2, %eax      
        ret

Do you think it may be worth lowering the new pseudo to that, instead of the proposed sequence?

Ooh, that looks very nice indeed. Thinking about cmp as a subtraction, this wide subtraction seems like a natural way to do it. I wonder why MSVC doesn't do it this way..

By the way, is there a reason ICC is using %edx instead of %eax for the second move and sbb? It seems to me that the register pressure here should be the same as for my proposed sequence, i.e. only one register needed.

Maybe we could also use this for the equality comparisons?

I'm mainly coming at this from a binary size perspective. Your suggestion is 4 bytes shorter than my test_slt. It's also 2 bytes shorter than my test_eq, so I like it :-)

[mkuper]

ICC doesn't do this for equality comparisons.
In fact, it produces code that's very close to what we currently have in clang (before your patch).

As to eax/edx - I can't see a good reason for that. Doesn't necessarily mean there isn't one, of course, just that I can't see one...

[DavidKreitzer]

(1) The subl/sbbl sequence cannot distinguish between greater-than and equal-to, so it doesn't work for ==/!= without an additional instruction at which point, it's no better than the current sequence. This also means you have to be careful about how you order the operands depending on the condition. For (a < b), you'd generate what Michael showed:

test(long long, long long):
        movl      4(%esp), %eax 
        subl      12(%esp), %eax
        movl      8(%esp), %edx 
        sbbl      16(%esp), %edx
        jge       ..B1.3        
        movl      $1, %eax      
        ret                     
..B1.3:                         
        movl      $2, %eax      
        ret

For (a >= b), you can simply replace the "jge" with "jl". For (a > b), you have to reverse the sense of the subtraction like this:

test(long long, long long):
        movl     12(%esp), %eax 
        subl      4(%esp), %eax
        movl      16(%esp), %edx 
        sbbl      8(%esp), %edx
        jge       ..B1.3        
        movl      $1, %eax      
        ret                     
..B1.3:                         
        movl      $2, %eax      
        ret

(a <= b) would have the same operand order but with "jl" instead of "jge".

(2) I think there is no clear winner between the current 1-branch implementation of ==/!= and the proposed 2-branch implementation. The branch prediction effect will be data dependent, and the context will determine whether the extra branch or the longer dependence chain of the current implementation is more harmful. For example, one situation where the 1-branch implementation will shine is when the compare operands almost always compare unequal, but the lower bits often compare equal.

(3) ICC uses both eax and edx to give the post-RA scheduler more flexibility, which is sometimes useful, sometimes not. (In Michael's code snippet, it clearly didn't accomplish anything.)

[hans]

David, Michael: thank you very much for your input. Not only is the code you suggest better, but it should be easier to generate too since it doesn't change the cfg.

I've been trying to make this work today, but am not sure exactly where to put it. The approach of pattern-matching for "(setcc (or (xor hi1 hi2) (xor lo1 lo2)) 0 {eq,ne})" is brittle because some nodes can get "simplified" e.g .(setcc a 0 ugt) will become (setcc a 0 ne). We could of course try to unsimplify it but I wonder if there's a better way.

Michael mentioned maybe we could do a target-specific DAG-combine. But that would need to be done before legalization, so the types would be illegal. Is it OK to legalize them in a combine? I don't think the combine has access to the logic for expanding integers etc?

Can I make this a target-specific legalization somehow? Where would I do that?

Or, could we make this a generic thing? We have SUBE and SUBC that would let us do subtract with borrow, but I don't think we can pick up the flags from that. Is there some way we could represent this in the generic selection dag?

I'll keep working on this tomorrow, just wanted to put down my notes in case you have any comments. The backend is still new territory for me.

[hans]

Here is a new version of the patch, using the SUB-SBB method.

I'm trying a new approach, adding a custom SETCC_PARTS node. This avoids the trouble of pattern-matching, allows this to fire in more situations (e.g. not just branches, but all setcc's), and would makes it easier to do the same thing for other targets.

I did try to come up with a way to make this more generic, using ISD::SUBC and SUBE, but couldn't figure out how to detect the outcome based on the result from SUBE. For unsigned comparisons we can just compare it against zero (a comparison that will get folded away nicely), but what to do for unsigned?

I've removed the change to equality comparisons. It might still be worth looking at some more since it lowers the register pressure (maybe use when optimizing for size?).

[DavidKreitzer]

include/llvm/CodeGen/ISDOpcodes.h

375 ↗

(On Diff #40020)

wit --> with

378 ↗

(On Diff #40020)

I think the operand ordering ought to be [LHSLo, LHSHi, RHSLo, RHSHi] to be consistent with SHL_PARTS, et al.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2685 ↗

(On Diff #40020)

Should probably delete the extra blank line.

2749 ↗

(On Diff #40020)

This looks reasonable to me.

I am just wondering whether it would be better to refactor this such that we always generate SETCC_PARTS here regardless of whether the target has a custom lowering and then implement a default lowering that does most of what this routine is currently doing.

lib/Target/X86/X86ISelLowering.cpp

14545

Your operand ordering for SETCC_PARTS doesn't match your comment in ISDOpcodes.h. The two should at least be in sync, and I already gave my opinion on what the operand order ought to be. :-)

14575

The code sequences you are generating here look great!

test/CodeGen/X86/wide-integer-cmp.ll

39

I think you meant LHSHi here.

61

Again, this looks odd. Did you mean RHSHi here and at line 62?

80

Also RHSHi here and at line 81.

[hans]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2749 ↗

(On Diff #40020)

Can you provide an example of how always generating SETCC_PARTS and having a default lowering would help? One problem I see is that we'd need to legalize it too.

For example a 128-bit SETCC could be legalized to 64-bit SETCC_PARTS, and on a 32-bit target we'd need to legalize that too. With the current patch, we only legalize SETCC to SETCC_PARTS for types the target has said it can efficiently lower.

lib/Target/X86/X86ISelLowering.cpp

14545

Oops. Thanks for catching this. So much for trying to document things :-) I've updated the code to use the order you suggested.

14575

Thanks to you and Michael for suggesting it :-)

test/CodeGen/X86/wide-integer-cmp.ll

80

Thanks! Not sure how I managed to get them so backwards.

[hans]

Addressing David's comments.

[DavidKreitzer]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2749 ↗

(On Diff #40020)

I didn't have any particular example in mind. I was just thinking about alternative design choices. The current SETCC_PARTS design seems like it is putting a little too much target-specific knowledge in this target-independent piece of type legalization.

Another option you might like that is in line with your earlier thinking, i.e.

I did try to come up with a way to make this more generic, using ISD::SUBC and SUBE

is to define a new SETCCE opcode that behaves just like SETCC except that it has an additional borrow operand. So the sequence you'd generate during type legalization is

SUBC LHSLo, RHSLo
SETCCE LHSHi, RHSHi, <SUBC borrow>, <cond>

And then the SETCCE would be implemented using SBB+SETcc rather than CMP+SETcc as SETCC is currently implemented.

It is probably easier and/or more natural to extend SETCCE to other targets than SETCC_PARTS.

What do you think?

[DavidKreitzer]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2748 ↗

(On Diff #40115)

Another advantage of the SETCCE approach is that it can be used to implement arbitrary precision integer compares. For example, an __int128 compare on x86 could be legalized to

SUBC
SUBE
SUBE
SETCCE

[hans]

Apologies for the delay.

Here is a version using the proposed SETCCE approach. I think this turned out really well, and of course the code for e.g. 128-bit compares is now very nice.

The only downside I can think of is that this gives targets less flexibility in lowering. For example, with SETCC_PARTS a target could choose to lower with a three-way branch on the high part if it wanted too. On the other hand, this flexibility meant more work; the SETCCE node should be very straight-forward for targets to handle, and it handles the cases with more than two halves nicely so I think it's the better option.

Please take a look and let me know what you think.

[DavidKreitzer]

I really like the way this turned out! Thanks so much for doing the rework. I just had a couple minor additional suggestions.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

2772 ↗

(On Diff #40453)

I would expect every target to be able to support this (at which point, much of the code in this routine can be removed). Maybe it would be a good idea to add a FIXME comment to that effect.

lib/Target/X86/X86ISelLowering.cpp

14548

I would recommend against this restriction. The SETCCE operation itself makes perfect sense for other conditions. (For example, SETCCE "eq" computes op0 - op1 - carry == 0.) For the purposes of large integer compare lowering, it happens to only be useful for < and >=, but we might find other good uses for it. (I'm imagining some fancy DAG combine optimizations ...)

test/CodeGen/X86/wide-integer-cmp.ll

87

Nice! This is SO much better than the current code!

[hans]

lib/Target/X86/X86ISelLowering.cpp

14548

Sounds good to me.

[hans]

Addressing review comments.

I also ran into a problem when the carry value gets folded to CARRY_FALSE. Added code to handle that and a test.

Please take a look.

[DavidKreitzer]

lib/Target/X86/X86ISelLowering.cpp

14547

I like the idea of leveraging TranslateX86CC, but I believe these two optimizations at the beginning of TranslateX86CC are invalid for SETCCE and somehow need to be avoided for it:

// X > -1   -> X == 0, jump !sign.
// X < 0   -> X == 0, jump on sign.

They are invalid in the one special case where X is 0x80000000 and the carry is true. FWIW, this optimization *is* valid:

// X < 1   -> X <= 0

[hans]

lib/Target/X86/X86ISelLowering.cpp

14547

Thanks for catching that!

[hans]

Breaking out the actual operation translation part from TranslateX86CC and use that instead.

[DavidKreitzer]

I like it! Everything looks good to me now.

include/llvm/CodeGen/MachineBasicBlock.h

public:
   instr_iterator                instr_begin()       { return Insts.begin();  }
   const_instr_iterator          instr_begin() const { return Insts.begin();  }
   instr_iterator                  instr_end()       { return Insts.end();    }
   const_instr_iterator            instr_end() const { return Insts.end();    }
   reverse_instr_iterator       instr_rbegin()       { return Insts.rbegin(); }
   const_reverse_instr_iterator instr_rbegin() const { return Insts.rbegin(); }
   reverse_instr_iterator       instr_rend  ()       { return Insts.rend();   }
   const_reverse_instr_iterator instr_rend  () const { return Insts.rend();   }
+  iterator_range<instr_iterator> instrs() {
+    return iterator_range<instr_iterator>(Insts.begin(), Insts.end());
+  }
+  iterator_range<const_instr_iterator> instrs() const  {
+    return iterator_range<const_instr_iterator>(Insts.begin(), Insts.end());
+  }
 
   iterator                begin()       { return instr_begin();  }
   const_iterator          begin() const { return instr_begin();  }
   iterator                end  ()       { return instr_end();    }
   const_iterator          end  () const { return instr_end();    }
   reverse_iterator       rbegin()       { return instr_rbegin(); }
   const_reverse_iterator rbegin() const { return instr_rbegin(); }
   reverse_iterator       rend  ()       { return instr_rend();   }

lib/Target/X86/X86ISelLowering.h

enum NodeType : unsigned {
       CMOV,
 
       /// X86 conditional branches. Operand 0 is the chain operand, operand 1
       /// is the block to branch if condition is true, operand 2 is the
       /// condition code, and operand 3 is the flag operand produced by a CMP
       /// or TEST instruction.
       BRCOND,
 
+      /// Wide comparison and branch. E.g. "branch if hi1:lo1 < hi2:lo2".
+      WIDECMPBR,
+
       /// Return with a flag operand. Operand 0 is the chain operand, operand
       /// 1 is the number of bytes of stack to pop.
       RET_FLAG,
 
       /// Repeat fill, corresponds to X86::REP_STOSx.
       REP_STOS,
 
       /// Repeat move, corresponds to X86::REP_MOVSx.
private:
     /// Utility function to emit the xmm reg save portion of va_start.
     MachineBasicBlock *EmitVAStartSaveXMMRegsWithCustomInserter(
                                                    MachineInstr *BInstr,
                                                    MachineBasicBlock *BB) const;
 
     MachineBasicBlock *EmitLoweredSelect(MachineInstr *I,
                                          MachineBasicBlock *BB) const;
 
+    MachineBasicBlock *EmitWideCmpBr(MachineInstr *I,
+                                     MachineBasicBlock *BB) const;
+
     MachineBasicBlock *EmitLoweredAtomicFP(MachineInstr *I,
                                            MachineBasicBlock *BB) const;
 
     MachineBasicBlock *EmitLoweredWinAlloca(MachineInstr *MI,
                                               MachineBasicBlock *BB) const;
 
     MachineBasicBlock *EmitLoweredSegAlloca(MachineInstr *MI,
                                             MachineBasicBlock *BB) const;

lib/Target/X86/X86ISelLowering.cpp

 }
 
 // isX86LogicalCmp - Return true if opcode is a X86 logical comparison.
 static bool isX86LogicalCmp(SDValue Op) {
   unsigned Opc = Op.getNode()->getOpcode();
   if (Opc == X86ISD::CMP || Opc == X86ISD::COMI || Opc == X86ISD::UCOMI ||
       Opc == X86ISD::SAHF)
     return true;
   if (Op.getResNo() == 1 &&
       (Opc == X86ISD::ADD ||
        Opc == X86ISD::SUB ||
        Opc == X86ISD::ADC ||
        Opc == X86ISD::SBB ||
        Opc == X86ISD::SMUL ||
        Opc == X86ISD::UMUL ||
        Opc == X86ISD::INC ||
        Opc == X86ISD::DEC ||
        Opc == X86ISD::OR ||
        Opc == X86ISD::XOR ||
        Opc == X86ISD::AND))
if (V.getOpcode() != ISD::TRUNCATE)
     return false;
 
   SDValue VOp0 = V.getOperand(0);
   unsigned InBits = VOp0.getValueSizeInBits();
   unsigned Bits = V.getValueSizeInBits();
   return DAG.MaskedValueIsZero(VOp0, APInt::getHighBitsSet(InBits,InBits-Bits));
 }
 
 SDValue X86TargetLowering::LowerSELECT(SDValue Op, SelectionDAG &DAG) const {
   bool addTest = true;
   SDValue Cond  = Op.getOperand(0);
   SDValue Op1 = Op.getOperand(1);
   SDValue Op2 = Op.getOperand(2);
   SDLoc DL(Op);
   MVT VT = Op1.getSimpleValueType();
   SDValue CC;
 
static bool isXor1OfSetCC(SDValue Op) {
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Op.getOperand(1));
   if (N1C && N1C->getAPIntValue() == 1) {
     return Op.getOperand(0).getOpcode() == X86ISD::SETCC &&
       Op.getOperand(0).hasOneUse();
   }
   return false;
 }
 
+// isWideCmp - Return true if Node is a doing a "wide" comparison of Hi1:Lo1
+// and Hi2:Lo2.
+static bool isWideCmp(SDValue Node, SDValue &Hi1, SDValue &Hi2, SDValue &Lo1,
+                      SDValue &Lo2, unsigned &CC) {
+  // This function is pattern matching for the output of
+  // DAGTypeLegalizer::IntegerExpandSetCCOperands.
+
+  // Check for: (setcc (or (xor hi1 hi2) (xor lo1 lo2)) 0 {eq,ne}).
+  if (Node.getOpcode() == ISD::SETCC && Node.hasOneUse() &&
+      Node.getOperand(0)->getOpcode() == ISD::OR) {
+    SDValue Or = Node.getOperand(0);
+    ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Node.getOperand(1));
+    if (!Or.hasOneUse() || !Const || !Const->isNullValue())
+      return false;
+    if (Or.getOperand(0).getOpcode() != ISD::XOR ||
+        !Or.getOperand(0).hasOneUse() ||
+        Or.getOperand(1).getOpcode() != ISD::XOR ||
+        !Or.getOperand(1).hasOneUse())
+      return false;
+    Hi1 = Or.getOperand(0).getOperand(0);
+    Hi2 = Or.getOperand(0).getOperand(1);
+    Lo1 = Or.getOperand(1).getOperand(0);
+    Lo2 = Or.getOperand(1).getOperand(1);
+
+    switch (cast<CondCodeSDNode>(Node.getOperand(2))->get()) {
+      case ISD::SETEQ: CC = X86::COND_E; break;
+      case ISD::SETNE: CC = X86::COND_NE; break;
+      default: return false;
+    }
+    // Wide compares use 32-bit integers only.
+    if (Hi1.getValueType() != MVT::i32 || Lo1.getValueType() != MVT::i32)
+      return false;
+
+    return true;
+  }
+
+  // Check for: (select (setcc hi1 hi2 eq) (setcc lo1 lo2 <) (setcc hi1 hi2 <)).
+  if (Node.getOpcode() != ISD::SELECT || !Node.hasOneUse() ||
+      Node.getOperand(0)->getOpcode() != ISD::SETCC ||
+      Node.getOperand(1)->getOpcode() != ISD::SETCC ||
+      Node.getOperand(2)->getOpcode() != ISD::SETCC)
+    return false;
+
+  // The select condition is checking equality of the high bits.
+  SDValue SelectCond = Node.getOperand(0);
+  if (cast<CondCodeSDNode>(SelectCond->getOperand(2))->get() != ISD::SETEQ)
+    return false;
+  if (!SelectCond.hasOneUse())
+    return false;
+  Hi1 = SelectCond->getOperand(0);
+  Hi2 = SelectCond->getOperand(1);
+
+  // The select false node is comparing the high bits.
+  SDValue SelectFalse = Node.getOperand(2);
+  if (!SelectFalse.hasOneUse())
+    return false;
+  if (SelectFalse->getOperand(0) != Hi1 || SelectFalse->getOperand(1) != Hi2)
+    return false;
+  unsigned HighCC = cast<CondCodeSDNode>(SelectFalse->getOperand(2))->get();
+
+  // The select true is comparing the low bits.
+  SDValue SelectTrue = Node.getOperand(1);
+  if (!SelectTrue.hasOneUse())
+    return false;
+  Lo1 = SelectTrue->getOperand(0);
+  Lo2 = SelectTrue->getOperand(1);
+  unsigned LowCC = cast<CondCodeSDNode>(SelectTrue->getOperand(2))->get();
+
+  // Wide compares only work with 32-bit integers.
+  if (Hi1.getValueType() != MVT::i32 || Lo1.getValueType() != MVT::i32)
+    return false;
+
+  // Determine the condition code. The low bits use unsigned cmp.
+  switch (HighCC) {
+  case ISD::SETLT:
+    if (LowCC != ISD::SETULT) { return false; } CC = X86::COND_L; break;
+  case ISD::SETULT:
+    if (LowCC != ISD::SETULT) { return false; } CC = X86::COND_B; break;
+  case ISD::SETGT:
+    if (LowCC != ISD::SETUGT) { return false; } CC = X86::COND_G; break;
+  case ISD::SETUGT:
+    if (LowCC != ISD::SETUGT) { return false; } CC = X86::COND_A; break;
+  case ISD::SETLE:
+    if (LowCC != ISD::SETULE) { return false; } CC = X86::COND_LE; break;
+  case ISD::SETULE:
+    if (LowCC != ISD::SETULE) { return false; } CC = X86::COND_BE; break;
+  case ISD::SETGE:
+    if (LowCC != ISD::SETUGE) { return false; } CC = X86::COND_GE; break;
+  case ISD::SETUGE:
+    if (LowCC != ISD::SETUGE) { return false; } CC = X86::COND_AE; break;
+  default:
+    return false;
+  }
+
+  return true;
+}
+
 SDValue X86TargetLowering::LowerBRCOND(SDValue Op, SelectionDAG &DAG) const {
   bool addTest = true;
   SDValue Chain = Op.getOperand(0);
   SDValue Cond  = Op.getOperand(1);
   SDValue Dest  = Op.getOperand(2);
   SDLoc dl(Op);
   SDValue CC;
   bool Inverted = false;
 
+  {
+    // Check for wide integer compare.
+    SDValue Hi1, Hi2, Lo1, Lo2;
+    unsigned CC;
+    if (isWideCmp(Cond, Hi1, Hi2, Lo1, Lo2, CC)) {
+      SDValue Ops[] = {
+          Chain, Dest, Hi1, Hi2, Lo1, Lo2, DAG.getConstant(CC, dl, MVT::i8)};
+      return DAG.getNode(X86ISD::WIDECMPBR, dl, Op.getValueType(), makeArrayRef(Ops));
+    }
+  }
+
   if (Cond.getOpcode() == ISD::SETCC) {
     // Check for setcc([su]{add,sub,mul}o == 0).
     if (cast<CondCodeSDNode>(Cond.getOperand(2))->get() == ISD::SETEQ &&
         isa<ConstantSDNode>(Cond.getOperand(1)) &&
         cast<ConstantSDNode>(Cond.getOperand(1))->isNullValue() &&
         Cond.getOperand(0).getResNo() == 1 &&
         (Cond.getOperand(0).getOpcode() == ISD::SADDO ||
          Cond.getOperand(0).getOpcode() == ISD::UADDO ||
const char *X86TargetLowering::getTargetNodeName(unsigned Opcode) const {
   case X86ISD::CMPMU:              return "X86ISD::CMPMU";
   case X86ISD::CMPM_RND:           return "X86ISD::CMPM_RND";
   case X86ISD::SETCC:              return "X86ISD::SETCC";
   case X86ISD::SETCC_CARRY:        return "X86ISD::SETCC_CARRY";
   case X86ISD::FSETCC:             return "X86ISD::FSETCC";
   case X86ISD::FGETSIGNx86:        return "X86ISD::FGETSIGNx86";
   case X86ISD::CMOV:               return "X86ISD::CMOV";
   case X86ISD::BRCOND:             return "X86ISD::BRCOND";
+  case X86ISD::WIDECMPBR:          return "X86ISD::WIDECMPBR";
   case X86ISD::RET_FLAG:           return "X86ISD::RET_FLAG";
   case X86ISD::REP_STOS:           return "X86ISD::REP_STOS";
   case X86ISD::REP_MOVS:           return "X86ISD::REP_MOVS";
   case X86ISD::GlobalBaseReg:      return "X86ISD::GlobalBaseReg";
   case X86ISD::Wrapper:            return "X86ISD::Wrapper";
   case X86ISD::WrapperRIP:         return "X86ISD::WrapperRIP";
   case X86ISD::MOVDQ2Q:            return "X86ISD::MOVDQ2Q";
   case X86ISD::MMX_MOVD2W:         return "X86ISD::MMX_MOVD2W";
X86TargetLowering::EmitLoweredSelect(MachineInstr *MI,
   // Now remove the CMOV(s).
   for (MachineBasicBlock::iterator MIIt = MIItBegin; MIIt != MIItEnd; )
     (MIIt++)->eraseFromParent();
 
   return sinkMBB;
 }
 
 MachineBasicBlock *
+X86TargetLowering::EmitWideCmpBr(MachineInstr *MI,
+                                 MachineBasicBlock *BB) const {
+  DebugLoc DL = MI->getDebugLoc();
+  const X86InstrInfo *TII = Subtarget->getInstrInfo();
+  const BasicBlock *LLVM_BB = BB->getBasicBlock();
+  MachineFunction *MF = BB->getParent();
+
+  // The next instruction should be a jump to the "false" destination.
+  MachineInstr *FalseJmp = ++MachineBasicBlock::iterator(MI);
+  assert(FalseJmp->getOpcode() == X86::JMP_1);
+
+  MachineBasicBlock *FalseMBB = FalseJmp->getOperand(0).getMBB();
+  MachineBasicBlock *TrueMBB = MI->getOperand(0).getMBB();
+
+  // JCC is a jump matching the overall relation we're checking (e.g. JL)
+  // DisproveJCC is a comparison on the high bits disproving the relation (e.g.
+  // JG), and UnsignedJCC is the unsigned variant of JCC (e.g. JB). Except for
+  // ==, normalize the condition so it may be proved by comparing the high bits.
+  // E.g for >= we check < instead and reverse the destinations.
+  unsigned JCC, DisproveJCC, UnsignedJCC;
+  switch (MI->getOperand(5).getImm()) {
+  case X86::COND_NE:
+    std::swap(FalseMBB, TrueMBB);
+  case X86::COND_E:
+    JCC = X86::JE_1; DisproveJCC = X86::JNE_1; UnsignedJCC = X86::JE_1; break;
+
+  case X86::COND_GE:
+    std::swap(FalseMBB, TrueMBB);
+  case X86::COND_L:
+    JCC = X86::JL_1; DisproveJCC = X86::JG_1; UnsignedJCC = X86::JB_1; break;
+
+  case X86::COND_AE:
+    std::swap(FalseMBB, TrueMBB);
+  case X86::COND_B:
+    JCC = X86::JB_1; DisproveJCC = X86::JA_1; UnsignedJCC = X86::JB_1; break;
+
+  case X86::COND_LE:
+    std::swap(FalseMBB, TrueMBB);
+  case X86::COND_G:
+    JCC = X86::JG_1; DisproveJCC = X86::JL_1; UnsignedJCC = X86::JA_1; break;
+
+  case X86::COND_BE:
+    std::swap(FalseMBB, TrueMBB);
+  case X86::COND_A:
+    JCC = X86::JA_1; DisproveJCC = X86::JB_1; UnsignedJCC = X86::JA_1; break;
+
+  default: llvm_unreachable("Unexpected condition code!");
+  }
+
+
+  // Compare the high bits.
+  BuildMI(*BB, MI, DL, TII->get(X86::CMP32rr))
+           .addOperand(/*Hi1=*/MI->getOperand(1))
+           .addOperand(/*Hi2=*/MI->getOperand(2));
+  if (JCC != X86::JE_1) // High bits not enough to prove equality.
+    BuildMI(*BB, MI, DL, TII->get(JCC)).addMBB(TrueMBB);
+  BuildMI(*BB, MI, DL, TII->get(DisproveJCC)).addMBB(FalseMBB);
+
+  // Fall through to a new block.
+  MachineBasicBlock *CmpLowMBB = MF->CreateMachineBasicBlock(LLVM_BB);
+  MF->insert(++BB->getIterator(), CmpLowMBB);
+  FalseJmp->getOperand(0).setMBB(CmpLowMBB);
+  BB->addSuccessor(CmpLowMBB);
+
+  // The new block does an unsigned comparison of the low bits.
+  BuildMI(CmpLowMBB, DL, TII->get(X86::CMP32rr))
+           .addOperand(/*Lo1=*/MI->getOperand(3))
+           .addOperand(/*Lo2=*/MI->getOperand(4));
+  BuildMI(CmpLowMBB, DL, TII->get(UnsignedJCC)).addMBB(TrueMBB);
+  BuildMI(CmpLowMBB, DL, TII->get(X86::JMP_1)).addMBB(FalseMBB);
+
+  // Add NewPred as a predecessor to Succ, updating PHIs to get the same value
+  // as from OldPred. If RemoveOld is true, OldPred is no longer a predecessor.
+  auto updateSuccessor = [MF](MachineBasicBlock *Succ,
+                              MachineBasicBlock *OldPred,
+                              MachineBasicBlock *NewPred, bool RemoveOld) {
+    NewPred->addSuccessor(Succ);
+    if (RemoveOld)
+      OldPred->removeSuccessor(Succ);
+    for (auto &I : Succ->instrs()) {
+      if (!I.isPHI()) break;
+      for (unsigned i = 1, e = I.getNumOperands() - 1; i != e; i += 2) {
+        unsigned Value = I.getOperand(i).getReg();
+        MachineBasicBlock *MBB = I.getOperand(i + 1).getMBB();
+        if (MBB == OldPred) {
+          if (RemoveOld)
+            I.getOperand(i + 1).setMBB(NewPred);
+          else
+            MachineInstrBuilder(*MF, &I).addReg(Value).addMBB(NewPred);
+          break;
+        }
+      }
+    }
+  };
+
+  // If comparing for equality, BB no longer branches directly to TrueMBB.
+  updateSuccessor(TrueMBB, BB, CmpLowMBB, JCC == X86::JE_1);
+  updateSuccessor(FalseMBB, BB, CmpLowMBB, false);
+
+  MI->eraseFromParent();
+  return BB;
+}
+
+MachineBasicBlock *
 X86TargetLowering::EmitLoweredAtomicFP(MachineInstr *MI,
                                        MachineBasicBlock *BB) const {
   // Combine the following atomic floating-point modification pattern:
   //   a.store(reg OP a.load(acquire), release)
   // Transform them into:
   //   OPss (%gpr), %xmm
   //   movss %xmm, (%gpr)
   // Or sd equivalent for 64-bit operations.
X86TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
   case X86::CMOV_V8F64:
   case X86::CMOV_V8I64:
   case X86::CMOV_V8I1:
   case X86::CMOV_V16I1:
   case X86::CMOV_V32I1:
   case X86::CMOV_V64I1:
     return EmitLoweredSelect(MI, BB);
 
+  case X86::WIDECMPBR:
+    return EmitWideCmpBr(MI, BB);
+
   case X86::RELEASE_FADD32mr:
   case X86::RELEASE_FADD64mr:
     return EmitLoweredAtomicFP(MI, BB);
 
   case X86::FP32_TO_INT16_IN_MEM:
   case X86::FP32_TO_INT32_IN_MEM:
   case X86::FP32_TO_INT64_IN_MEM:
   case X86::FP64_TO_INT16_IN_MEM:

lib/Target/X86/X86InstrCompiler.td

 let Defs = [RAX, RSP, EFLAGS], Uses = [RSP] in
 def SEG_ALLOCA_64 : I<0, Pseudo, (outs GR64:$dst), (ins GR64:$size),
                       "# variable sized alloca for segmented stacks",
                       [(set GR64:$dst,
                          (X86SegAlloca GR64:$size))]>,
                     Requires<[In64BitMode]>;
 }
 
+let usesCustomInserter = 1, Defs = [EFLAGS], isBranch = 1, isTerminator = 1, hasCtrlDep = 1 in {
+def WIDECMPBR : I<0, Pseudo, (outs), (ins brtarget32:$dst, GR32:$hi1, GR32:$hi2, GR32:$lo1, GR32:$lo2, i8imm:$cc),
+                  " #WIDECMPBR PSEUDO! $dst, $hi1, $hi2, $lo1, $lo2 $cc",
+                  [(X86widecmpbr bb:$dst, GR32:$hi1, GR32:$hi2, GR32:$lo1, GR32:$lo2, imm:$cc),
+                   (implicit EFLAGS)]>;
+}
+
 //===----------------------------------------------------------------------===//
 // EH Pseudo Instructions
 //
 let SchedRW = [WriteSystem] in {
 let isTerminator = 1, isReturn = 1, isBarrier = 1,
     hasCtrlDep = 1, isCodeGenOnly = 1 in {
 def EH_RETURN   : I<0xC3, RawFrm, (outs), (ins GR32:$addr),
                     "ret\t#eh_return, addr: $addr",

lib/Target/X86/X86InstrInfo.td

def SDT2ResultBinaryArithWithFlags : SDTypeProfile<3, 2,
                                             [SDTCisSameAs<0, 1>,
                                              SDTCisSameAs<0, 2>,
                                              SDTCisSameAs<0, 3>,
                                              SDTCisInt<0>, SDTCisVT<1, i32>]>;
 def SDTX86BrCond  : SDTypeProfile<0, 3,
                                   [SDTCisVT<0, OtherVT>,
                                    SDTCisVT<1, i8>, SDTCisVT<2, i32>]>;
 
+def SDTX86WideCmpBr : SDTypeProfile<0, 6,
+                                    [SDTCisVT<0, OtherVT>,
+                                     SDTCisVT<1, i32>,
+                                     SDTCisVT<2, i32>,
+                                     SDTCisVT<3, i32>,
+                                     SDTCisVT<4, i32>,
+                                     SDTCisVT<5, i8>]>;
+
 def SDTX86SetCC   : SDTypeProfile<1, 2,
                                   [SDTCisVT<0, i8>,
                                    SDTCisVT<1, i8>, SDTCisVT<2, i32>]>;
 def SDTX86SetCC_C : SDTypeProfile<1, 2,
                                   [SDTCisInt<0>,
                                    SDTCisVT<1, i8>, SDTCisVT<2, i32>]>;
 
 def SDTX86sahf : SDTypeProfile<1, 1, [SDTCisVT<0, i32>, SDTCisVT<1, i8>]>;

 def X86shrd    : SDNode<"X86ISD::SHRD",     SDTIntShiftDOp>;
 
 def X86cmp     : SDNode<"X86ISD::CMP" ,     SDTX86CmpTest>;
 def X86bt      : SDNode<"X86ISD::BT",       SDTX86CmpTest>;
 
 def X86cmov    : SDNode<"X86ISD::CMOV",     SDTX86Cmov>;
 def X86brcond  : SDNode<"X86ISD::BRCOND",   SDTX86BrCond,
                         [SDNPHasChain]>;
+def X86widecmpbr : SDNode<"X86ISD::WIDECMPBR", SDTX86WideCmpBr, [SDNPHasChain]>;
 def X86setcc   : SDNode<"X86ISD::SETCC",    SDTX86SetCC>;
 def X86setcc_c : SDNode<"X86ISD::SETCC_CARRY", SDTX86SetCC_C>;
 
 def X86sahf    : SDNode<"X86ISD::SAHF",     SDTX86sahf>;
 
 def X86rdrand  : SDNode<"X86ISD::RDRAND",   SDTX86rdrand,
                         [SDNPHasChain, SDNPSideEffect]>;
 

test/CodeGen/X86/avx512-cmp.ll

 A:
  ret i32 6
 B:
  ret i32 7
 }
 
 ; AVX512-32-LABEL: test10
 ; AVX512-32: movl    4(%esp), %ecx
-; AVX512-32: cmpl    $9, (%ecx)
-; AVX512-32: seta    %al
+; AVX512-32: cmpl    $10, (%ecx)
+; AVX512-32: setb    %al
 ; AVX512-32: cmpl    $0, 4(%ecx)
-; AVX512-32: setg    %cl
+; AVX512-32: sets    %cl
 ; AVX512-32: je
 ; AVX512-32: movb    %cl, %al
-; AVX512-32: testb   $1, %al
-
-define void @test10(i64* %i.addr)  {
+; AVX512-32: retl
 
+define i1 @test10(i64* %i.addr)  {
   %x = load i64, i64* %i.addr, align 8
-  %cmp = icmp slt i64 %x, 10
-  br i1 %cmp, label %true, label %false
-
-true:
-  ret void
-
-false:
-  ret void
+  %res = icmp slt i64 %x, 10
+  ret i1 %res
 }
-

test/CodeGen/X86/wide-integer-cmp.ll

+; RUN: llc -mtriple=i686-linux-gnu %s -o - | FileCheck %s
+
+
+define i32 @test_eq(i64 %a, i64 %b) {
+entry:
+  %cmp = icmp eq i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  ret i32 1
+bb2:
+  ret i32 2
+
+; CHECK-LABEL: test_eq:
+; CHECK: cmp
+; CHECK: jne [[FALSE:.LBB[0-9_]+]]
+; CHECK: cmp
+; CHECK: jne [[FALSE]]
+; CHECK: movl $1, %eax
+; CHECK: retl
+; CHECK: [[FALSE]]:
+; CHECK: movl $2, %eax
+; CHECK: retl
+}
+
+define i32 @test_ne(i64 %a, i64 %b) {
+entry:
+  %cmp = icmp ne i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  ret i32 1
+bb2:
+  ret i32 2
+
+; CHECK-LABEL: test_ne:
+; CHECK: cmp
+; CHECK: jne [[TRUE:.LBB[0-9_]+]]
+; CHECK: cmp
+; CHECK: jne [[TRUE]]
+; CHECK: movl $2, %eax
+; CHECK: retl
+; CHECK: [[TRUE]]:
+; CHECK: movl $1, %eax
+; CHECK: retl
+}
+
+define i32 @test_slt(i64 %a, i64 %b) {
+entry:
+  %cmp = icmp slt i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  ret i32 1
+bb2:
+  ret i32 2
+
+; CHECK-LABEL: test_slt:
+; CHECK: cmp
+; CHECK: jl [[TRUE:.LBB[0-9_]+]]
+; CHECK: jg [[FALSE:.LBB[0-9_]+]]
+; CHECK: cmp
+; CHECK: jae [[FALSE]]
+; CHECK: [[TRUE]]:
+; CHECK: movl $1, %eax
+; CHECK: retl
+; CHECK: [[FALSE]]:
+; CHECK: movl $2, %eax
+; CHECK: retl
+}
+
+define i32 @test_uge(i64 %a, i64 %b) {
+entry:
+  %cmp = icmp uge i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  ret i32 1
+bb2:
+  ret i32 2
+
+; CHECK-LABEL: test_uge:
+; CHECK: cmp
+; CHECK: jb [[FALSE:.LBB[0-9_]+]]
+; CHECK: ja [[TRUE:.LBB[0-9_]+]]
+; CHECK: cmp
+; CHECK: jae [[TRUE]]
+; CHECK: [[FALSE]]:
+; CHECK: movl $2, %eax
+; CHECK: retl
+; CHECK: [[TRUE]]:
+; CHECK: movl $1, %eax
+; CHECK: retl
+}
+
+define i32 @test_lt_phi_updates(i64 %a, i64 %b, i1 %foo) {
+entry:
+ br i1 %foo, label %bb0, label %bb1
+bb0:
+  %cmp = icmp slt i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  %phi1 = phi i32 [ 42, %entry ], [ 1, %bb0 ]
+  br label %bb2
+bb2:
+  %phi2 = phi i32 [ 2, %bb0 ], [ %phi1, %bb1 ]
+  ret i32 %phi2
+
+; CHECK-LABEL: test_lt_phi_updates:
+; CHECK: movl $42, [[PHI1:%[a-z]+]]
+; CHECK: test
+; CHECK: je [[BB1:.LBB[0-9_]+]]
+; CHECK: movl $2, [[PHI2:%[a-z]+]]
+; CHECK: movl $1, [[PHI1]]
+; CHECK: cmp
+; CHECK: jl [[BB1]]
+; CHECK: jg [[BB2:.LBB[0-9_]+]]
+; CHECK: cmp
+; CHECK: jae [[BB2]]
+; CHECK: [[BB1]]
+; CHECK: movl [[PHI1]], [[PHI2]]
+; CHECK: [[BB2]]
+; CHECK retl
+}
+
+define i32 @test_eq_phi_updates(i64 %a, i64 %b, i1 %foo) {
+entry:
+ br i1 %foo, label %bb0, label %bb1
+bb0:
+  %cmp = icmp eq i64 %a, %b
+  br i1 %cmp, label %bb1, label %bb2
+bb1:
+  %phi1 = phi i32 [ 42, %entry ], [ 1, %bb0 ]
+  br label %bb2
+bb2:
+  %phi2 = phi i32 [ 2, %bb0 ], [ %phi1, %bb1 ]
+  ret i32 %phi2
+
+; CHECK-LABEL: test_eq_phi_updates:
+; CHECK: movl $42, [[PHI1:%[a-z]+]]
+; CHECK: test
+; CHECK: je [[BB1:.LBB[0-9_]+]]
+; CHECK: movl $2, [[PHI2:%[a-z]+]]
+; CHECK: cmp
+; CHECK: jne [[BB2:.LBB[0-9_]+]]
+; CHECK: movl $1, [[PHI1]]
+; CHECK: cmp
+; CHECK: jne [[BB2]]
+; CHECK: [[BB1]]
+; CHECK: movl [[PHI1]], [[PHI2]]
+; CHECK: [[BB2]]
+; CHECK retl
+}