[InstCombine][CGP] Move swapMayExposeCSEOpportunities() fold

[nikic]

Summary

InstCombine tries to swap compare operands to match sub instructions in order to expose "CSE opportunities". However, it doesn't really make sense to perform this transform in the middle-end, as we cannot actually CSE the instructions there.

The backend already performs this fold in https://github.com/llvm/llvm-project/blob/18f5446a45da5a61dbfb1b7667d27fb441ac62db/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp#L4236 on the SDAG level, however this only works within a single basic block.

To handle cross-BB cases, we do need to handle this on the IR layer. This patch moves the fold from InstCombine to CGP in the backend, while keeping the same, somewhat dubious, heuristic.

[RKSimon]

Looks like this landed all the way back at rG5ab555532b5a - are the cse tests in icmp.ll still relevant?

[nikic]

In D152541#4409284, @RKSimon wrote:

Looks like this landed all the way back at rG5ab555532b5a - are the cse tests in icmp.ll still relevant?

Okay, based on the commit description this is targeted at cross-BB cases, which SDAG doesn't handle. And indeed, something like this survives all the way through the backend: https://llvm.godbolt.org/z/TzT3rEehe I think in that case we can't drop this entirely and should move it from InstCombine into CGP instead.

[nikic]

Move the fold to CGP instead of removing it entirely. cmp_sub_different_order shows the desired outcome for cross-BB cmp/sub reuse. All other test changes are noise.

[RKSimon]

LGTM - cheers

llvm/lib/CodeGen/CodeGenPrepare.cpp

1851

I feel like this limiter has a story behind it - but I'm not sure whether we need to do anything about it......

[nikic]

llvm/lib/CodeGen/CodeGenPrepare.cpp

1851

It does: At one point the InstCombine fold tried to inspect the users of a constant like i32 0, with millions of entries. When I fixed that I both added the guard against constants and a limit on the walk, to be doubly sure it doesn't get out of hand...

[uabelho]

Hi,

The following starts hanging in CGP with this patch:

llc -march=x86-64 -mcpu=corei7 -o /dev/null stress-11366.ll

The input was generated with

bin/llvm-stress -size 300 -seed 11366

stress-11366.ll19 KBDownload

[nikic]

@uabelho Thanks for the report! Should be fixed by https://github.com/llvm/llvm-project/commit/b7bd3a734c7c08e1a703a4f23e3e854ba94a1bf2.

Guess this didn't happen in InstCombine because this would get folded to a constant.

[uabelho]

In D152541#4428134, @nikic wrote:

@uabelho Thanks for the report! Should be fixed by https://github.com/llvm/llvm-project/commit/b7bd3a734c7c08e1a703a4f23e3e854ba94a1bf2.

Guess this didn't happen in InstCombine because this would get folded to a constant.

Yep, thanks!

llvm/lib/CodeGen/CodeGenPrepare.cpp

if (auto *SI = dyn_cast<SelectInst>(U)) {
       continue;
     }
     llvm_unreachable("Must be a branch or a select");
   }
   Cmp->setPredicate(CmpInst::getSwappedPredicate(DomPred));
   return true;
 }
 
+/// Many architectures use the same instruction for both subtract and cmp. Try
+/// to swap cmp operands to match subtract operations to allow for CSE.
+static bool swapICmpOperandsToExposeCSEOpportunities(CmpInst *Cmp) {
+  Value *Op0 = Cmp->getOperand(0);
+  Value *Op1 = Cmp->getOperand(1);
+  if (!Op0->getType()->isIntegerTy() || isa<Constant>(Op0) ||
+      isa<Constant>(Op1))
+    return false;
+
+  // If a subtract already has the same operands as a compare, swapping would be
+  // bad. If a subtract has the same operands as a compare but in reverse order,
+  // then swapping is good.
+  int GoodToSwap = 0;
+  unsigned NumInspected = 0;
+  for (const User *U : Op0->users()) {
+    // Avoid walking many users.
+    if (++NumInspected > 128)
+      return false;
+    if (match(U, m_Sub(m_Specific(Op1), m_Specific(Op0))))
+      GoodToSwap++;
+    else if (match(U, m_Sub(m_Specific(Op0), m_Specific(Op1))))
+      GoodToSwap--;
+  }
+
+  if (GoodToSwap > 0) {
+    Cmp->swapOperands();
+    return true;
+  }
+  return false;
+}
+
 bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT) {
   if (sinkCmpExpression(Cmp, *TLI))
     return true;
 
   if (combineToUAddWithOverflow(Cmp, ModifiedDT))
     return true;
 
   if (combineToUSubWithOverflow(Cmp, ModifiedDT))
     return true;
 
   if (foldICmpWithDominatingICmp(Cmp, *TLI))
     return true;
 
+  if (swapICmpOperandsToExposeCSEOpportunities(Cmp))
+    return true;
+
   return false;
 }
 
 /// Duplicate and sink the given 'and' instruction into user blocks where it is
 /// used in a compare to allow isel to generate better code for targets where
 /// this operation can be combined.
 ///
 /// Return true if any changes are made.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static APInt getDemandedBitsLHSMask(ICmpInst &I, unsigned BitWidth) {
   case ICmpInst::ICMP_ULT:
     return APInt::getBitsSetFrom(BitWidth, RHS->countr_zero());
 
   default:
     return APInt::getAllOnes(BitWidth);
   }
 }
 
-/// Check if the order of \p Op0 and \p Op1 as operands in an ICmpInst
-/// should be swapped.
-/// The decision is based on how many times these two operands are reused
-/// as subtract operands and their positions in those instructions.
-/// The rationale is that several architectures use the same instruction for
-/// both subtract and cmp. Thus, it is better if the order of those operands
-/// match.
-/// TODO: Shouldn't this be part of CGP instead?
-/// \return true if Op0 and Op1 should be swapped.
-static bool swapMayExposeCSEOpportunities(const Value *Op0, const Value *Op1) {
-  // Filter out pointer values as those cannot appear directly in subtract.
-  // FIXME: we may want to go through inttoptrs or bitcasts.
-  if (Op0->getType()->isPointerTy() || isa<Constant>(Op0))
-    return false;
-  // If a subtract already has the same operands as a compare, swapping would be
-  // bad. If a subtract has the same operands as a compare but in reverse order,
-  // then swapping is good.
-  int GoodToSwap = 0;
-  unsigned NumInspected = 0;
-  for (const User *U : Op0->users()) {
-    // Avoid walking many users.
-    if (++NumInspected > 128)
-      return false;
-    if (match(U, m_Sub(m_Specific(Op1), m_Specific(Op0))))
-      GoodToSwap++;
-    else if (match(U, m_Sub(m_Specific(Op0), m_Specific(Op1))))
-      GoodToSwap--;
-  }
-  return GoodToSwap > 0;
-}
-
 /// Check that one use is in the same block as the definition and all
 /// other uses are in blocks dominated by a given block.
 ///
 /// \param DI Definition
 /// \param UI Use
 /// \param DB Block that must dominate all uses of \p DI outside
 ///           the parent block
 /// \return true when \p UI is the only use of \p DI in the parent block
Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   const SimplifyQuery Q = SQ.getWithInstruction(&I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   unsigned Op0Cplxity = getComplexity(Op0);
   unsigned Op1Cplxity = getComplexity(Op1);
 
   /// Orders the operands of the compare so that they are listed from most
   /// complex to least complex.  This puts constants before unary operators,
   /// before binary operators.
-  if (Op0Cplxity < Op1Cplxity ||
-      (Op0Cplxity == Op1Cplxity && swapMayExposeCSEOpportunities(Op0, Op1))) {
+  if (Op0Cplxity < Op1Cplxity) {
     I.swapOperands();
     std::swap(Op0, Op1);
     Changed = true;
   }
 
   if (Value *V = simplifyICmpInst(I.getPredicate(), Op0, Op1, Q))
     return replaceInstUsesWith(I, V);
 

llvm/test/CodeGen/Lanai/sub-cmp-peephole.ll

 }
 
 ; If SR is live-out, we can't remove cmp if there exists a swapped sub.
 define i32 @j(i32 inreg %a, i32 inreg %b) nounwind {
 ; CHECK-LABEL: j:
 ; CHECK:       ! %bb.0: ! %entry
 ; CHECK-NEXT:    st %fp, [--%sp]
 ; CHECK-NEXT:    add %sp, 0x8, %fp
-; CHECK-NEXT:    sub.f %r6, %r7, %rv
-; CHECK-NEXT:    bne .LBB4_2
 ; CHECK-NEXT:    sub %sp, 0x8, %sp
+; CHECK-NEXT:    sub.f %r6, %r7, %r0
+; CHECK-NEXT:    bne .LBB4_2
+; CHECK-NEXT:    sub %r6, %r7, %rv
 ; CHECK-NEXT:  .LBB4_1: ! %if.then
-; CHECK-NEXT:    sub.f %r7, %r6, %r0
-; CHECK-NEXT:    sel.gt %rv, %r6, %rv
+; CHECK-NEXT:    sel.lt %rv, %r6, %rv
 ; CHECK-NEXT:  .LBB4_2: ! %if.else
 ; CHECK-NEXT:    ld -4[%fp], %pc ! return
 ; CHECK-NEXT:    add %fp, 0x0, %sp
 ; CHECK-NEXT:    ld -8[%fp], %fp
 entry:
   %cmp = icmp eq i32 %b, %a
   %sub = sub nsw i32 %a, %b
   br i1 %cmp, label %if.then, label %if.else

llvm/test/CodeGen/RISCV/aext-to-sext.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=riscv64 -verify-machineinstrs < %s \
 ; RUN:   | FileCheck %s -check-prefix=RV64I
 
 ; Make sure we don't generate an addi in the loop in
 ; addition to the addiw. Previously we type legalize the
 ; setcc use using signext and the phi use using anyext.
 ; We now detect when it would be beneficial to replace
 ; anyext with signext.
 
 define void @quux(i32 signext %arg, i32 signext %arg1) nounwind {
 ; RV64I-LABEL: quux:
 ; RV64I:       # %bb.0: # %bb
-; RV64I-NEXT:    beq a0, a1, .LBB0_4
+; RV64I-NEXT:    beq a1, a0, .LBB0_4
 ; RV64I-NEXT:  # %bb.1: # %bb2.preheader
 ; RV64I-NEXT:    addi sp, sp, -16
 ; RV64I-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
 ; RV64I-NEXT:    sd s0, 0(sp) # 8-byte Folded Spill
 ; RV64I-NEXT:    subw s0, a1, a0
 ; RV64I-NEXT:  .LBB0_2: # %bb2
 ; RV64I-NEXT:    # =>This Inner Loop Header: Depth=1
 ; RV64I-NEXT:    call hoge@plt

llvm/test/CodeGen/Thumb2/LowOverheadLoops/varying-outer-2d-reduction.ll

 ; ENABLED-NEXT:    strh.w r0, [r1, r8, lsl #1]
 ; ENABLED-NEXT:    add.w r8, r8, #1
 ; ENABLED-NEXT:    add.w r10, r10, #2
 ; ENABLED-NEXT:    cmp r8, r3
 ; ENABLED-NEXT:    beq .LBB0_8
 ; ENABLED-NEXT:  .LBB0_4: @ %for.body
 ; ENABLED-NEXT:    @ =>This Loop Header: Depth=1
 ; ENABLED-NEXT:    @ Child Loop BB0_6 Depth 2
-; ENABLED-NEXT:    cmp r8, r2
-; ENABLED-NEXT:    bge .LBB0_2
+; ENABLED-NEXT:    cmp r2, r8
+; ENABLED-NEXT:    ble .LBB0_2
 ; ENABLED-NEXT:  @ %bb.5: @ %vector.ph
 ; ENABLED-NEXT:    @ in Loop: Header=BB0_4 Depth=1
 ; ENABLED-NEXT:    bic r0, r9, #3
 ; ENABLED-NEXT:    movs r7, #1
 ; ENABLED-NEXT:    subs r0, #4
 ; ENABLED-NEXT:    sub.w r4, r2, r8
 ; ENABLED-NEXT:    vmov.i32 q1, #0x0
 ; ENABLED-NEXT:    add.w r6, r7, r0, lsr #2

 ; NOREDUCTIONS-NEXT:    strh.w r0, [r1, r8, lsl #1]
 ; NOREDUCTIONS-NEXT:    add.w r8, r8, #1
 ; NOREDUCTIONS-NEXT:    add.w r10, r10, #2
 ; NOREDUCTIONS-NEXT:    cmp r8, r3
 ; NOREDUCTIONS-NEXT:    beq .LBB0_8
 ; NOREDUCTIONS-NEXT:  .LBB0_4: @ %for.body
 ; NOREDUCTIONS-NEXT:    @ =>This Loop Header: Depth=1
 ; NOREDUCTIONS-NEXT:    @ Child Loop BB0_6 Depth 2
-; NOREDUCTIONS-NEXT:    cmp r8, r2
-; NOREDUCTIONS-NEXT:    bge .LBB0_2
+; NOREDUCTIONS-NEXT:    cmp r2, r8
+; NOREDUCTIONS-NEXT:    ble .LBB0_2
 ; NOREDUCTIONS-NEXT:  @ %bb.5: @ %vector.ph
 ; NOREDUCTIONS-NEXT:    @ in Loop: Header=BB0_4 Depth=1
 ; NOREDUCTIONS-NEXT:    bic r0, r9, #3
 ; NOREDUCTIONS-NEXT:    movs r7, #1
 ; NOREDUCTIONS-NEXT:    subs r0, #4
 ; NOREDUCTIONS-NEXT:    sub.w r4, r2, r8
 ; NOREDUCTIONS-NEXT:    vmov.i32 q1, #0x0
 ; NOREDUCTIONS-NEXT:    add.w r6, r7, r0, lsr #2

llvm/test/CodeGen/Thumb2/mve-postinc-lsr.ll

 ; CHECK-NEXT:    beq .LBB5_8
 ; CHECK-NEXT:  .LBB5_5: @ %for.body
 ; CHECK-NEXT:    @ =>This Loop Header: Depth=1
 ; CHECK-NEXT:    @ Child Loop BB5_7 Depth 2
 ; CHECK-NEXT:    ldr r0, [sp, #96]
 ; CHECK-NEXT:    cmp r1, r1
 ; CHECK-NEXT:    str r1, [sp, #24] @ 4-byte Spill
 ; CHECK-NEXT:    ldr.w r12, [r0, r11, lsl #2]
-; CHECK-NEXT:    bge .LBB5_3
+; CHECK-NEXT:    ble .LBB5_3
 ; CHECK-NEXT:  @ %bb.6: @ %for.body24.preheader
 ; CHECK-NEXT:    @ in Loop: Header=BB5_5 Depth=1
 ; CHECK-NEXT:    ldr.w lr, [sp, #92]
 ; CHECK-NEXT:    ldr r0, [sp, #12] @ 4-byte Reload
 ; CHECK-NEXT:    mov r6, r12
 ; CHECK-NEXT:    ldr r1, [sp, #16] @ 4-byte Reload
 ; CHECK-NEXT:    mov r8, r12
 ; CHECK-NEXT:    mla r3, r11, lr, r0

 ; CHECK-NEXT:    lsrs r1, r0, #3
 ; CHECK-NEXT:  .LBB6_3: @ %for.body
 ; CHECK-NEXT:    @ =>This Loop Header: Depth=1
 ; CHECK-NEXT:    @ Child Loop BB6_5 Depth 2
 ; CHECK-NEXT:    ldr r0, [sp, #96]
 ; CHECK-NEXT:    cmp r1, r1
 ; CHECK-NEXT:    str r1, [sp, #24] @ 4-byte Spill
 ; CHECK-NEXT:    ldr.w r12, [r0, r11, lsl #2]
-; CHECK-NEXT:    bge .LBB6_6
+; CHECK-NEXT:    ble .LBB6_6
 ; CHECK-NEXT:  @ %bb.4: @ %for.body24.preheader
 ; CHECK-NEXT:    @ in Loop: Header=BB6_3 Depth=1
 ; CHECK-NEXT:    ldr.w lr, [sp, #92]
 ; CHECK-NEXT:    ldr r0, [sp, #12] @ 4-byte Reload
 ; CHECK-NEXT:    mov r6, r12
 ; CHECK-NEXT:    ldr r1, [sp, #16] @ 4-byte Reload
 ; CHECK-NEXT:    mov r8, r12
 ; CHECK-NEXT:    mla r3, r11, lr, r0

llvm/test/CodeGen/X86/cmp-merge.ll

 cond.end:
   ret void
 }
 
 define void @cmp_sub_different_order(i32 %x, i32 %y, ptr %p) {
 ; X86-LABEL: cmp_sub_different_order:
 ; X86:       # %bb.0: # %entry
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    cmpl %ecx, %eax
-; X86-NEXT:    jle .LBB3_2
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    jge .LBB3_2
 ; X86-NEXT:  # %bb.1: # %cond.true
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    subl %eax, %ecx
-; X86-NEXT:    movl %ecx, (%edx)
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %eax, (%ecx)
 ; X86-NEXT:  .LBB3_2: # %cond.end
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: cmp_sub_different_order:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    cmpl %edi, %esi
-; X64-NEXT:    jle .LBB3_2
-; X64-NEXT:  # %bb.1: # %cond.true
 ; X64-NEXT:    subl %esi, %edi
+; X64-NEXT:    jge .LBB3_2
+; X64-NEXT:  # %bb.1: # %cond.true
 ; X64-NEXT:    movl %edi, (%rdx)
 ; X64-NEXT:  .LBB3_2: # %cond.end
 ; X64-NEXT:    retq
 entry:
   %cmp = icmp sgt i32 %y, %x
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:

llvm/test/CodeGen/X86/jump_sign.ll

; CHECK-NEXT:    retl
   ret i32 %cond
 }
 
 ; (This used to test that an unsafe removal of cmp in bb.0 is not happening,
 ;  but now we can do so safely).
 define i32 @func_l2(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: func_l2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; CHECK-NEXT:    movl %eax, %ecx
-; CHECK-NEXT:    subl %edx, %ecx
+; CHECK-NEXT:    subl {{[0-9]+}}(%esp), %ecx
 ; CHECK-NEXT:    jne .LBB8_2
 ; CHECK-NEXT:  # %bb.1: # %if.then
 ; CHECK-NEXT:    cmovll %ecx, %eax
 ; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB8_2: # %if.else
 ; CHECK-NEXT:    movl %ecx, %eax
 ; CHECK-NEXT:    retl
   %cmp = icmp eq i32 %b, %a

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

 cond.end:
   %r = phi i32 [ %0, %cond.true ], [ 0, %entry ]
   ret i32 %r
 }
 
 define i32 @sub_abs_lt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_lt(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
 ; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;

 cond.end:
   %r = phi i32 [ %0, %cond.true ], [ 0, %entry ]
   ret i32 %r
 }
 
 define i32 @sub_abs_lt_min_not_poison(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_lt_min_not_poison(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
 ; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;

llvm/test/Transforms/InstCombine/icmp.ll

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xor = xor i8 %x, 63
   store i8 %xor, ptr %p
   %r = icmp ugt i8 %xor, 63
   ret i1 %r
 }
 
-define i1 @icmp_swap_operands_for_cse(i32 %X, i32 %Y) {
-; CHECK-LABEL: @icmp_swap_operands_for_cse(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[TRUE:%.*]], label [[FALSE:%.*]]
-; CHECK:       true:
-; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[SUB]], 1
-; CHECK-NEXT:    br label [[END:%.*]]
-; CHECK:       false:
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SUB]], 16
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[RES_IN:%.*]] = phi i32 [ [[TMP0]], [[TRUE]] ], [ [[TMP1]], [[FALSE]] ]
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[RES_IN]], 0
-; CHECK-NEXT:    ret i1 [[RES]]
-;
-entry:
-  %sub = sub i32 %X, %Y
-  %cmp = icmp ugt i32 %Y, %X
-  br i1 %cmp, label %true, label %false
-true:
-  %restrue = trunc i32 %sub to i1
-  br label %end
-false:
-  %shift = lshr i32 %sub, 4
-  %resfalse = trunc i32 %shift to i1
-  br label %end
-end:
-  %res = phi i1 [%restrue, %true], [%resfalse, %false]
-  ret i1 %res
-}
-
-define i1 @icmp_swap_operands_for_cse2(i32 %X, i32 %Y) {
-; CHECK-LABEL: @icmp_swap_operands_for_cse2(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[TRUE:%.*]], label [[FALSE:%.*]]
-; CHECK:       true:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SUB1:%.*]] = sub i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SUB]], [[SUB1]]
-; CHECK-NEXT:    br label [[END:%.*]]
-; CHECK:       false:
-; CHECK-NEXT:    [[SUB2:%.*]] = sub i32 [[Y]], [[X]]
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[RES_IN_IN:%.*]] = phi i32 [ [[ADD]], [[TRUE]] ], [ [[SUB2]], [[FALSE]] ]
-; CHECK-NEXT:    [[RES_IN:%.*]] = and i32 [[RES_IN_IN]], 1
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[RES_IN]], 0
-; CHECK-NEXT:    ret i1 [[RES]]
-;
-entry:
-  %cmp = icmp ugt i32 %Y, %X
-  br i1 %cmp, label %true, label %false
-true:
-  %sub = sub i32 %X, %Y
-  %sub1 = sub i32 %X, %Y
-  %add = add i32 %sub, %sub1
-  %restrue = trunc i32 %add to i1
-  br label %end
-false:
-  %sub2 = sub i32 %Y, %X
-  %resfalse = trunc i32 %sub2 to i1
-  br label %end
-end:
-  %res = phi i1 [%restrue, %true], [%resfalse, %false]
-  ret i1 %res
-}
-
-define i1 @icmp_do_not_swap_operands_for_cse(i32 %X, i32 %Y) {
-; CHECK-LABEL: @icmp_do_not_swap_operands_for_cse(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[TRUE:%.*]], label [[FALSE:%.*]]
-; CHECK:       true:
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[X]], [[Y]]
-; CHECK-NEXT:    br label [[END:%.*]]
-; CHECK:       false:
-; CHECK-NEXT:    [[SUB2:%.*]] = sub i32 [[Y]], [[X]]
-; CHECK-NEXT:    br label [[END]]
-; CHECK:       end:
-; CHECK-NEXT:    [[RES_IN_IN:%.*]] = phi i32 [ [[SUB]], [[TRUE]] ], [ [[SUB2]], [[FALSE]] ]
-; CHECK-NEXT:    [[RES_IN:%.*]] = and i32 [[RES_IN_IN]], 1
-; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[RES_IN]], 0
-; CHECK-NEXT:    ret i1 [[RES]]
-;
-entry:
-  %cmp = icmp ugt i32 %Y, %X
-  br i1 %cmp, label %true, label %false
-true:
-  %sub = sub i32 %X, %Y
-  %restrue = trunc i32 %sub to i1
-  br label %end
-false:
-  %sub2 = sub i32 %Y, %X
-  %resfalse = trunc i32 %sub2 to i1
-  br label %end
-end:
-  %res = phi i1 [%restrue, %true], [%resfalse, %false]
-  ret i1 %res
-}
-
 define i1 @icmp_lshr_lshr_eq(i32 %a, i32 %b) {
 ; CHECK-LABEL: @icmp_lshr_lshr_eq(
 ; CHECK-NEXT:    [[Z_UNSHIFTED:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp ult i32 [[Z_UNSHIFTED]], 1073741824
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %x = lshr i32 %a, 30
   %y = lshr i32 %b, 30

llvm/test/Transforms/InstCombine/result-of-usub-is-non-zero-and-no-overflow.ll

 declare void @llvm.assume(i1)
 
 ; There is a number of base patterns..
 
 define i1 @t0_noncanonical_ignoreme(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t0_noncanonical_ignoreme(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %adjusted, %base
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t0_noncanonical_ignoreme_logical(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t0_noncanonical_ignoreme_logical(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %adjusted, %base
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)

 }
 
 ; Commutativity
 
 define i1 @t3_commutability0(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t3_commutability0(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %offset, %base ; swapped
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %not_null, %no_underflow
   ret i1 %r
 }
 
 define i1 @t3_commutability0_logical(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t3_commutability0_logical(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %offset, %base ; swapped
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
;
   call void @use1(i1 %not_null)
   %r = select i1 %no_underflow, i1 %not_null, i1 false ; swapped
   ret i1 %r
 }
 define i1 @t5_commutability2(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t5_commutability2(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %no_underflow = icmp ule i8 %offset, %base ; swapped
   call void @use1(i1 %no_underflow)
   %not_null = icmp ne i8 %adjusted, 0
   call void @use1(i1 %not_null)
   %r = and i1 %no_underflow, %not_null ; swapped
   ret i1 %r
 }
 
 define i1 @t5_commutability2_logical(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t5_commutability2_logical(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[NO_UNDERFLOW:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[NO_UNDERFLOW]])
 ; CHECK-NEXT:    [[NOT_NULL:%.*]] = icmp ne i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NOT_NULL]])
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)

 }
 
 ; And these patterns also have commutative variants
 
 define i1 @t9_commutative(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t9_commutative(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ugt i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[UNDERFLOW]])
 ; CHECK-NEXT:    [[NULL:%.*]] = icmp eq i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %underflow = icmp ult i8 %base, %adjusted ; swapped
   call void @use1(i1 %underflow)
   %null = icmp eq i8 %adjusted, 0
   call void @use1(i1 %null)
   %r = or i1 %null, %underflow
   ret i1 %r
 }
 
 define i1 @t9_commutative_logical(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t9_commutative_logical(
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[UNDERFLOW:%.*]] = icmp ugt i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    call void @use1(i1 [[UNDERFLOW]])
 ; CHECK-NEXT:    [[NULL:%.*]] = icmp eq i8 [[BASE]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use1(i1 [[NULL]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %underflow = icmp ult i8 %base, %adjusted ; swapped
   call void @use1(i1 %underflow)
   %null = icmp eq i8 %adjusted, 0
   call void @use1(i1 %null)

llvm/test/Transforms/InstCombine/strict-sub-underflow-check-to-comparison-of-sub-operands.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @llvm.assume(i1)
 declare i8 @gen8()
 declare void @use8(i8)
 
 define i1 @t0(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t0(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[OFFSET:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[RES:%.*]] = icmp uge i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[RES:%.*]] = icmp ule i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %cmp = icmp slt i8 %offset, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %res = icmp ult i8 %adjusted, %base
   ret i1 %res
 }
 define i1 @t1(i8 %base, i8 %offset) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[OFFSET:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
 ; CHECK-NEXT:    [[ADJUSTED:%.*]] = sub i8 [[BASE:%.*]], [[OFFSET]]
 ; CHECK-NEXT:    call void @use8(i8 [[ADJUSTED]])
-; CHECK-NEXT:    [[RES:%.*]] = icmp ult i8 [[BASE]], [[OFFSET]]
+; CHECK-NEXT:    [[RES:%.*]] = icmp ugt i8 [[OFFSET]], [[BASE]]
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %cmp = icmp slt i8 %offset, 0
   call void @llvm.assume(i1 %cmp)
 
   %adjusted = sub i8 %base, %offset
   call void @use8(i8 %adjusted)
   %res = icmp uge i8 %adjusted, %base

llvm/test/Transforms/InstCombine/sub-ashr-or-to-icmp-select.ll

 }
 
 ; Extra uses
 
 define i32 @sub_ashr_or_i32_extra_use_sub(i32 %x, i32 %y, ptr %p) {
 ; CHECK-LABEL: @sub_ashr_or_i32_extra_use_sub(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    store i32 [[SUB]], ptr [[P:%.*]], align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i32 -1, i32 [[X]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %sub = sub nsw i32 %y, %x
   store i32 %sub, ptr %p
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   ret i32 %or

llvm/test/Transforms/InstCombine/unsigned-sub-lack-of-overflow-check.ll

 ; Extra-use tests
 
 declare void @use8(i8)
 
 define i1 @t3_extrause0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t3_extrause0(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[X]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = sub i8 %x, %y
   call void @use8(i8 %t0)
   %r = icmp ule i8 %t0, %x
   ret i1 %r
 }
 

llvm/test/Transforms/InstCombine/unsigned-sub-overflow-check.ll

 ; Extra-use tests
 
 declare void @use8(i8)
 
 define i1 @t3_extrause0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t3_extrause0(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[T0]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[X]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = sub i8 %x, %y
   call void @use8(i8 %t0)
   %r = icmp ugt i8 %t0, %x
   ret i1 %r
 }