CodeGenPrepare: Avoid and/or i1 in select conditions.

[MatzeB]

Summary

Thanks for the comments chandler.

I extracted the visitAND/visitOR refactoring to http://reviews.llvm.org/D8026. This new version only deals with the select DAG combines:

This is based on the following equivalences:
select(C0 & C1, X, Y) <=> select(C0, select(C1, X, Y), Y)
select(C0 | C1, X, Y) <=> select(C0, X, select(C1, X, Y))

Many target cannot perform and/or on the CPU flags and therefore the
right side should be choosen to avoid materializign the i1 flags in an
integer register. If the target can perform this operation efficiently
we normalize to the left form.

[ab]

I should note that this would have been useful as a DAGCombine as
well, because for instance on X86, (select (fcmp oeq/une)) is lowered
into the pattern matched here.

Matthias tells me doing it as a DAGCombine was frowned upon (why?), so
I'm doing pretty much the same thing on X86ISD::CMOV nodes, and will
submit shortly.
-Ahmed

[hfinkel]

In D7622#123459, @ab wrote:

I should note that this would have been useful as a DAGCombine as
well, because for instance on X86, (select (fcmp oeq/une)) is lowered
into the pattern matched here.

Matthias tells me doing it as a DAGCombine was frowned upon (why?),

I also don't understand why this would not be done in DAGCombine. It is basic-block local, and concerns itself with type legality, it seems appropriate for DAGCombine. One complication with DAGCombine is, if SELECT is not legal, then matching this might be hard.

so
I'm doing pretty much the same thing on X86ISD::CMOV nodes, and will
submit shortly.
-Ahmed

[MatzeB]

We discussed this in IRC, and I think chandler (and you?) told me that DAGCombine is supposed to normalize in a target independent way, as this normalization should or should not be done depending on the target I was told to do it in CodeGenPrepare...

Legality should not be a problem here as there is already a select instruction in use, I don't see why duplicating this select with a different condition (but same true/false input) could not be legal.

• Matthias

[MatzeB]

New version performing the transformation as a DAGCombine operation instead of CodeGenPrepare.

[MatzeB]

The commit message for this:

DAGCombine: Canonicalize select(and/or,x,y) depending on target.

This is based on the following equivalences:
select(C0 & C1, X, Y) <=> select(C0, select(C1, X, Y), Y)
select(C0 | C1, X, Y) <=> select(C0, X, select(C1, X, Y))

Many target cannot perform and/or on the CPU flags and therefore the
right side should be choosen to avoid materializign the i1 flags in an
integer register. If the target can perform this operation efficiently
we normalize to the left form.

Canonicalizing to nested selects has the problem that the and/or in the
conditions is only implcit afterwards, so this patch factors our bigger
parts of the and/or DAGCombiners so they can be applied to nested
selects as well.

[chandlerc]

There is no context in the diff, and there appears to be a bunch of unrelated code motion mixed in with the change. Fixing those issues would make it much easier to review.

If the code motion doesn't change any behavior but makes it easier to fit this into the DAG combine, just submit the no-op code motion change first and base this patch off that?

[hfinkel]

include/llvm/Target/TargetLowering.h

1095

I think it makes more sense to make this default to:

!hasMultipleConditionRegisters()

because if a target has multiple condition registers, then it probably has operations on those registers.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4714

Range-based for?

lib/Target/PowerPC/PPCISelLowering.h

624

This needs to default to !Subtarget.useCRBits() (so you might need to move the implementation into the PPCISelLowering.cpp).

Better yet, if you use hasMultipleConditionRegisters() for the default implementation (which I think you should), then you don't need this at all.

[MatzeB]

Thanks for the review Hal, the new version uses hasMultipleConditionRegisters() as default.

Comment at: lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4714
@@ +4713,3 @@
+ const SDNode *Node = Value.getNode();
+ for (auto I = Node->use_begin(), E = Node->use_end(); I != E; ++I) {

+ const SDUse &Use = I.getUse();

Range-based for?

A range based for prohibits me from doing I.getUse() above as I can't access the iterator anymore.

[hfinkel]

In D7622#134397, @MatzeB wrote:

Thanks for the review Hal, the new version uses hasMultipleConditionRegisters() as default.

Comment at: lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4714
@@ +4713,3 @@
+ const SDNode *Node = Value.getNode();
+ for (auto I = Node->use_begin(), E = Node->use_end(); I != E; ++I) {

+ const SDUse &Use = I.getUse();

Range-based for?

A range based for prohibits me from doing I.getUse() above as I can't access the iterator anymore.

Ah, alright.

include/llvm/Target/TargetLowering.h

1094

You should update the comment also. I'd say:

// If a target has multiple condition registers, then it likely has logical operations on those registers.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4716

Don't you want to check that it is used as the condition operand of the select?

[MatzeB]

Thanks Hal,

good points. Addressed in this update.

Thanks,
Matthias

[hfinkel]

LGTM.

[MatzeB]

Thanks again for the review. I can't commit this yet though as it depends on http://reviews.llvm.org/D8026

[MatzeB]

After looking at some more examples I tweaked the code some more:

• I'm not checking for hasOnlySelectAsUser() anymore. The fact that we have only select users means that we could get rid of the extra register and the SETCC but we produce an extra select instruction for each of the users, this is not necessarily better so I changed to the conservative hasOneUser().
• Tweak the callback to not cover types that need multiple registers as those will typically be broken down into multiple select-like instructions.

[hfinkel]

include/llvm/Target/TargetLowering.h

1100

Tweak the callback to not cover types that need multiple registers as those will typically be broken down into multiple select-like instructions.

Normally, to check this condition, we'd just use:

isTypeLegal(VT)

[MatzeB]

include/llvm/Target/TargetLowering.h

1100

But that will report false for types like i8 and i16 on many target even though we will end up with a single select like instruction. What about?

LegalizeTypeAction Action = getTypeAction(Context, VT);
return Action != TypeExpandInteger && Action != TYpeExpandFloat &&
  Action != TypeSplitVector

[hfinkel]

include/llvm/Target/TargetLowering.h

1100

Sure; seems reasonable to me. Go ahead whenever you're ready.

[michele.scandale]

Hi all,

working on compiler-rt for an out-of-tree target I found an issue related to this commit. I was able to reproduce it using the Mips backend. Please have a look to the inline comments.

Thanks in advance.

-Michele

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4853–4854 ↗

(On Diff #21383)

fixunsxfdi.ll1 KBDownload

Running "llc -O3" on the attached example I reach the following assertion

llc: /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:3204: llvm::SDValue llvm::SelectionDAG::getNode(unsigned int, llvm::SDLoc, llvm::EVT, llvm::SDValue, llvm::SDValue, bool, bool, bool): Assertion `N1.getValueType() == N2.getValueType() && N1.getValueType() == VT && "Binary operator types must match!"' failed.
#0 0x1997d75 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:425:0
#1 0x19980f1 PrintStackTraceSignalHandler(void*) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:483:0
#2 0x1996cc9 SignalHandler(int) /home/scandale/devel/pure-llvm/llvm/lib/Support/Unix/Signals.inc:199:0
#3 0x7f677b48e740 __restore_rt (/usr/lib/libpthread.so.0+0x10740)
#4 0x7f677a6ce4b7 __GI_raise (/usr/lib/libc.so.6+0x334b7)
#5 0x7f677a6cf88a __GI_abort (/usr/lib/libc.so.6+0x3488a)
#6 0x7f677a6c741d __assert_fail_base (/usr/lib/libc.so.6+0x2c41d)
#7 0x7f677a6c74d2 (/usr/lib/libc.so.6+0x2c4d2)
#8 0x181f0cb llvm::SelectionDAG::getNode(unsigned int, llvm::SDLoc, llvm::EVT, llvm::SDValue, llvm::SDValue, bool, bool, bool) /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:3203:0
#9 0x17781ae (anonymous namespace)::DAGCombiner::visitSELECT(llvm::SDNode*) /home/scandale/devel/pure-llvm/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:4888:0

This is because the condition values of the two select nodes have different types, thus we cannot create an AND between them.

A quick workaround is to check also that the types of the two conditions are the same. An alternative could be to extend one of the condition to have homogeneous types.

4872–4873 ↗

(On Diff #21383)

Same issue of lines 4853-4854...

[MatzeB]

I would be fine with either skipping the transformation if the types don't match up or extending the types. I personally would lean towards skipping the transformation as the extension is an extra instruction which makes the transformation less beneficial. As none of the targets I know are affected, what would the preference for your target?

• Matthias

[michele.scandale]

In D7622#154957, @MatzeB wrote:

I would be fine with either skipping the transformation if the types don't match up or extending the types. I personally would lean towards skipping the transformation as the extension is an extra instruction which makes the transformation less beneficial. As none of the targets I know are affected, what would the preference for your target?

• Matthias

The previous example was showing the issue using the in-tree Mips backend.
Btw, the behavior of the target I am working on is quite close to Mips. On the proposed example it is better to skip the transformation when the two condition are not homogeneous.

-Michele

[MatzeB]

I fixed this in r234763.

include/llvm/Target/TargetLowering.h

public:
   /// http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf
   /// This method tries doing that transformation, returning the atomic load if
   /// it succeeds, and nullptr otherwise.
   /// If shouldExpandAtomicLoadInIR returns true on that load, it will undergo
   /// another round of expansion.
   virtual LoadInst *lowerIdempotentRMWIntoFencedLoad(AtomicRMWInst *RMWI) const {
     return nullptr;
   }
+
+  /// Returns true if we should normalize
+  /// select(N0&N1, X, Y) => select(N0, select(N1, X, Y), Y) and
+  /// select(N0|N1, X, Y) => select(N0, select(N1, X, Y, Y)) if it is likely
+  /// that it saves us from materializing N0 and N1 in an integer register.
+  /// Targets that are able to perform and/or on flags should return false here.
+  virtual bool shouldNormalizeToSelectSequence() const {
+    // If SELECTs are expensive then we should not do this.
+    return !isSelectExpensive();
+  }
+
   //===--------------------------------------------------------------------===//
   // TargetLowering Configuration Methods - These methods should be invoked by
   // the derived class constructor to configure this object for the target.
   //
 protected:
   /// Specify how the target extends the result of integer and floating point
   /// boolean values from i1 to a wider type.  See getBooleanContents.
   void setBooleanContents(BooleanContent Ty) {
     BooleanContents = Ty;
     BooleanFloatContents = Ty;
   }

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (TLI.isOperationLegal(Opcode, VT))
       return DAG.getNode(Opcode, DL, VT, LHS, RHS);
     return SDValue();
   }
   default:
     return SDValue();
   }
 }
 
+/// Returns true if all users of @p Value are SELECT nodes.
+static bool hasOnlySelectAsUser(const SDValue &Value) {
+  const SDNode *Node = Value.getNode();
+  for (auto I = Node->use_begin(), E = Node->use_end(); I != E; ++I) {
+    const SDUse &Use = I.getUse();
+    if (Use != Value)
+      continue;
+    if (I->getOpcode() != ISD::SELECT)
+      return false;
+  }
+  return true;
+}
+
 SDValue DAGCombiner::visitSELECT(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue N2 = N->getOperand(2);
   EVT VT = N->getValueType(0);
   EVT VT0 = N0.getValueType();
 
   // fold (select C, X, X) -> X
if ((!LegalOperations &&
          TLI.isOperationLegalOrCustom(ISD::SELECT_CC, VT)) ||
         TLI.isOperationLegal(ISD::SELECT_CC, VT))
       return DAG.getNode(ISD::SELECT_CC, SDLoc(N), VT,
                          N0.getOperand(0), N0.getOperand(1),
                          N1, N2, N0.getOperand(2));
     return SimplifySelect(SDLoc(N), N0, N1, N2);
   }
 
+  if (VT0 == MVT::i1) {
+    if (TLI.shouldNormalizeToSelectSequence()) {
+      // select (and Cond0, Cond1), X, Y
+      //   -> select Cond0, (select Cond1, X, Y), Y
+      if (N0->getOpcode() == ISD::AND && hasOnlySelectAsUser(N0)) {
+        SDValue Cond0 = N0->getOperand(0);
+        SDValue Cond1 = N0->getOperand(1);
+        SDValue InnerSelect = DAG.getNode(ISD::SELECT, SDLoc(N),
+                                          N1.getValueType(), Cond1, N1, N2);
+        return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), Cond0,
+                           InnerSelect, N2);
+      }
+      // select (or Cond0, Cond1), X, Y -> select Cond0, X, (select Cond1, X, Y)
+      if (N0->getOpcode() == ISD::OR && hasOnlySelectAsUser(N0)) {
+        SDValue Cond0 = N0->getOperand(0);
+        SDValue Cond1 = N0->getOperand(1);
+        SDValue InnerSelect = DAG.getNode(ISD::SELECT, SDLoc(N),
+                                          N1.getValueType(), Cond1, N1, N2);
+        return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), Cond0, N1,
+                           InnerSelect);
+      }
+    }
+
+    // select Cond0, (select Cond1, X, Y), Y -> select (and Cond0, Cond1), X, Y
+    if (N1->getOpcode() == ISD::SELECT) {
+      SDValue N1_0 = N1->getOperand(0);
+      SDValue N1_1 = N1->getOperand(1);
+      SDValue N1_2 = N1->getOperand(2);
+      if (N1_2 == N2) {
+        // Create the actual and node if we can generate good code for it.
+        if (!TLI.shouldNormalizeToSelectSequence()) {
+          SDValue And = DAG.getNode(ISD::AND, SDLoc(N), N0.getValueType(),
+                                    N0, N1_0);
+          return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), And,
+                             N1_1, N2);
+        }
+        // Otherwise see if we can optimize the "and" to a better pattern.
+        if (SDValue Combined = visitANDLike(N0, N1_0, N))
+          return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), Combined,
+                             N1_1, N2);
+      }
+    }
+    // select Cond0, X, (select Cond1, X, Y) -> select (or Cond0, Cond1), X, Y
+    if (N2->getOpcode() == ISD::SELECT) {
+      SDValue N2_0 = N2->getOperand(0);
+      SDValue N2_1 = N2->getOperand(1);
+      SDValue N2_2 = N2->getOperand(2);
+      if (N2_1 == N1) {
+        // Create the actual or node if we can generate good code for it.
+        if (!TLI.shouldNormalizeToSelectSequence()) {
+          SDValue Or = DAG.getNode(ISD::OR, SDLoc(N), N0.getValueType(),
+                                   N0, N2_0);
+          return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), Or,
+                             N1, N2_2);
+        }
+        // Otherwise see if we can optimize to a better pattern.
+        if (SDValue Combined = visitORLike(N0, N2_0, N))
+          return DAG.getNode(ISD::SELECT, SDLoc(N), N1.getValueType(), Combined,
+                             N1, N2_2);
+      }
+    }
+  }
+
   return SDValue();
 }
 
 static
 std::pair<SDValue, SDValue> SplitVSETCC(const SDNode *N, SelectionDAG &DAG) {
   SDLoc DL(N);
   EVT LoVT, HiVT;
   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));

lib/Target/PowerPC/PPCISelLowering.h

bool functionArgumentNeedsConsecutiveRegisters(
       // whether the argument should go in GPRs, FPRs, or VRs if available.
       //
       // Note that clang uses this capability both to implement the ELFv2
       // homogeneous float/vector aggregate ABI, and to avoid having to use
       // "byval" when passing aggregates that might fully fit in registers.
       return Ty->isArrayTy();
     }
 
+    /// No gain in select sequences as we can natively perform and/or on flag
+    /// registers.
+    bool shouldNormalizeToSelectSequence() const override {
+      return false;
+    }
+
   private:
 
     struct ReuseLoadInfo {
       SDValue Ptr;
       SDValue Chain;
       SDValue ResChain;
       MachinePointerInfo MPI;
       bool IsInvariant;

test/CodeGen/ARM/movcc-double.ll

+; RUN: llc -o - %s | FileCheck %s
+target triple = "arm-unknown-unknown"
+
+; select with and i1/or i1 condition should be implemented as a series of 2
+; cmovs, not by producing two conditions and using and on them.
+
+define i32 @select_and(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK-NOT: tst
+; CHECK-NOT: movne
+; CHECK: mov{{lo|hs}}
+; CHECK: mov{{lo|hs}}
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a2, %a3
+  %and = and i1 %cmp0, %cmp1
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_or(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4, i32 %a5) {
+; select with and i1 condition should be implemented as a series of 2 cmovs, not
+; by producing two conditions and using and on them.
+; CHECK-LABEL: select_or
+; CHECK-NOT: orss
+; CHECK-NOT: tst
+; CHECK: mov{{lo|hs}}
+; CHECK: mov{{lo|hs}}
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a2, %a3
+  %and = or i1 %cmp0, %cmp1
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+; If one of the conditions is materialized as a 0/1 value anyway, then the
+; sequence of 2 cmovs should not be used.
+
+@var32 = global i32 0
+define i32 @select_noopt(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_noopt
+; CHECK: orrs
+; CHECK: movne
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}

test/CodeGen/R600/or.ll

define void @trunc_i64_or_to_i32(i32 addrspace(1)* %out, i64 %a, i64 %b) {
   store i32 %trunc, i32 addrspace(1)* %out, align 8
   ret void
 }
 
 ; FUNC-LABEL: {{^}}or_i1:
 ; EG: OR_INT {{\** *}}T{{[0-9]+\.[XYZW], PV\.[XYZW], PS}}
 
 ; SI: s_or_b64 s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}], s[{{[0-9]+:[0-9]+}}]
-define void @or_i1(float addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
+define void @or_i1(i32 addrspace(1)* %out, float addrspace(1)* %in0, float addrspace(1)* %in1) {
   %a = load float, float addrspace(1)* %in0
   %b = load float, float addrspace(1)* %in1
   %acmp = fcmp oge float %a, 0.000000e+00
   %bcmp = fcmp oge float %b, 0.000000e+00
   %or = or i1 %acmp, %bcmp
-  %result = select i1 %or, float %a, float %b
-  store float %result, float addrspace(1)* %out
+  %result = zext i1 %or to i32
+  store i32 %result, i32 addrspace(1)* %out
   ret void
 }
 
 ; FUNC-LABEL: {{^}}s_or_i1:
 ; SI: s_or_b64 s[{{[0-9]+:[0-9]+}}], vcc, s[{{[0-9]+:[0-9]+}}]
 define void @s_or_i1(i1 addrspace(1)* %out, i32 %a, i32 %b, i32 %c, i32 %d) {
   %cmp0 = icmp eq i32 %a, %b
   %cmp1 = icmp eq i32 %c, %d
   %or = or i1 %cmp0, %cmp1
   store i1 %or, i1 addrspace(1)* %out
   ret void
 }

test/CodeGen/X86/cmov-double.ll

+; RUN: llc -o - %s | FileCheck %s
+target triple = "x86_64-unknown-unknown"
+
+; select with and i1/or i1 condition should be implemented as a series of 2
+; cmovs, not by producing two conditions and using and on them.
+
+define i32 @select_and(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; CHECK-LABEL: select_and
+; CHECK-NOT: set
+; CHECK-NOT: and[lb]
+; CHECK-NOT: test
+; CHECK: cmov
+; CHECK: cmov
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp olt float %a2, %a3
+  %and = and i1 %cmp0, %cmp1
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+define i32 @select_or(i32 %a0, i32 %a1, float %a2, float %a3, i32 %a4, i32 %a5) {
+; select with and i1 condition should be implemented as a series of 2 cmovs, not
+; by producing two conditions and using and on them.
+; CHECK-LABEL: select_or
+; CHECK-NOT: set
+; CHECK-NOT: or[lb]
+; CHECK-NOT: test
+; CHECK: cmov
+; CHECK: cmov
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = fcmp olt float %a2, %a3
+  %and = or i1 %cmp0, %cmp1
+  %res = select i1 %and, i32 %a4, i32 %a5
+  ret i32 %res
+}
+
+; If one of the conditions is materialized as a 0/1 value anyway, then the
+; sequence of 2 cmovs should not be used.
+
+@var32 = global i32 0
+define i32 @select_noopt(i32 %a0, i32 %a1, i32 %a2, i32 %a3, i32 %a4) {
+; CHECK-LABEL: select_noopt
+; CHECK: cmov
+; CHECK-NOT: cmov
+  %cmp0 = icmp ult i32 %a0, %a1
+  %cmp1 = icmp ult i32 %a1, %a2
+  %or = or i1 %cmp0, %cmp1
+  %zero_one = zext i1 %or to i32
+  store volatile i32 %zero_one, i32* @var32
+  %res = select i1 %or, i32 %a3, i32 %a4
+  ret i32 %res
+}

test/CodeGen/X86/jump_sign.ll

; CHECK: cmovs
   %add = add nsw i32 %b, %a
   %cmp = icmp sgt i32 %add, 0
   %add. = select i1 %cmp, i32 %add, i32 0
   ret i32 %add.
 }
 ; PR13475
 ; If we have sub a, b and cmp b, a and the result of cmp is used
 ; by sbb, we should not optimize cmp away.
-define i32 @func_q(i32 %j.4, i32 %w, i32 %el) {
+define i32 @func_q(i32 %a0, i32 %a1, i32 %a2) {
 ; CHECK-LABEL: func_q:
 ; CHECK: cmp
 ; CHECK-NEXT: sbb
-  %tmp532 = add i32 %j.4, %w
-  %tmp533 = icmp ugt i32 %tmp532, %el
-  %tmp534 = icmp ult i32 %w, %el
-  %or.cond = and i1 %tmp533, %tmp534
-  %tmp535 = sub i32 %el, %w
-  %j.5 = select i1 %or.cond, i32 %tmp535, i32 %j.4
-  ret i32 %j.5
+  %1 = icmp ult i32 %a0, %a1
+  %2 = sub i32 %a1, %a0
+  %3 = select i1 %1, i32 -1, i32 0
+  %4 = xor i32 %2, %3
+  ret i32 %4
 }
 ; rdar://11873276
 define i8* @func_r(i8* %base, i32* nocapture %offset, i32 %size) nounwind {
 entry:
 ; CHECK-LABEL: func_r:
 ; CHECK: sub
 ; CHECK-NOT: cmp
 ; CHECK: j

test/CodeGen/X86/zext-sext.ll

entry:
   %outSign = select i1 %tmp7, i32 1, i32 -1
   %tmp8 = icmp slt i32 %tmp4, 0
   %tmp9 = icmp eq i32 %outSign, 1
   %tmp10 = and i1 %tmp8, %tmp9
   %tmp11 = sext i32 %tmp4 to i64
   %tmp12 = add i64 %tmp11, 5089792279245435153
 
 ; CHECK:      addl  $2138875574, %e[[REGISTER_zext:[a-z0-9]+]]
-; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK:      cmpl  $-8608074, %e[[REGISTER_zext]]
+; CHECK:      movslq  %e[[REGISTER_zext]], [[REGISTER_sext:%r[a-z0-9]+]]
 ; CHECK-NOT:  [[REGISTER_zext]]
-; CHECK-DAG:  testl     %e[[REGISTER_zext]]
-; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext]]
+; CHECK-DAG:  cmpl  $2138875573, %e[[REGISTER_zext]]
+; CHECK:      movq  [[REGISTER_sext]], [[REGISTER_sext2:%[a-z0-9]+]]
+; CHECK:      subq  %r[[REGISTER_zext]], [[REGISTER_sext2]]
 
   %tmp13 = sub i64 %tmp12, 2138875574
   %tmp14 = zext i32 %tmp4 to i64
   %tmp15 = sub i64 %tmp11, %tmp14
   %tmp16 = select i1 %tmp10, i64 %tmp15, i64 0
   %tmp17 = sub i64 %tmp13, %tmp16
   %tmp18 = mul i64 %tmp17, 4540133155013554595
   %tmp19 = sub i64 %tmp18, 5386586244038704851