[InstCombine] DCE instructions earlier

[nikic]

Summary

When InstCombine initially populates the worklist, it already performs constant folding and DCE. However, as the instructions are initially visited in program order, this DCE can pick up only the last instruction of a dead chain, the rest would only get picked up in the main InstCombine run.

To avoid this, we instead perform the DCE in separate pass over the collected instructions in reverse order, which will allow us to pick up full dead instruction chains. We already need to do this reverse iteration anyway to populate the worklist, so this shouldn't add extra cost.

This by itself only fixes a small part of the problem though: The same basic issue also applies during the main InstCombine loop. We generally always want DCE to occur as early as possible, because it will allow one-use folds to happen. Address this by also performing DCE while adding deferred instructions to the main worklist.

This drops the number of tests that perform more than 2 InstCombine iterations from ~80 to ~40. There's some spurious test changes due to operand order / icmp toggling.

[nikic]

Update a test case outside the InstCombine directory.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3418

Seems like we already have redundant lines between this and what is included within "eraseInstFromFunction()". Can we:

1. Remove the debug print.
2. Remove the set of MadeIRChange.

That could be a preliminary NFC cleanup for the existing call below this block too?

3678–3683

eraseInstFromFunction(*Inst) ?

[nikic]

Rebase and remove redundant code.

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3418

Done that in rG7da3b5e45c25 for the existing use, and here as well.

3678–3683

We can't use eraseInstFromFunction() here, because it will also push operands to the worklist. As this is the code doing the initial worklist population, these would interfere.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

727

I guess it's independent of this patch, but I'm confused about when it's appropriate to push() vs. add(). Will we eventually reach a state where push() is private to the worklist implementation, and all the user code should use add()?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

727

Generally yes, user code should use add() and things are slowly moving in that direction...

Normally the choice of add() (FIFO, what you usually want) vs push() (LIFO) is about order. In this case there is no clear order in which the operands should be processed, so either is fine. I'm only using add() because the extra DCE code added in this patch works by processing the deferred worklist.

I think in the future, we may want to have a separate worklist only for DCE (instead of reusing the deferred worklist), and separate out add() vs addForDCE(). I'm leaving that for later, as I'm not sure whether it's sufficient to only perform DCE (rather than a full revisit) if the use-count drops.

llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h

class InstCombineWorklist {
   SmallSetVector<Instruction *, 16> Deferred;
 
 public:
   InstCombineWorklist() = default;
 
   InstCombineWorklist(InstCombineWorklist &&) = default;
   InstCombineWorklist &operator=(InstCombineWorklist &&) = default;
 
-  bool isEmpty() const { return Worklist.empty(); }
+  bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
 
   /// Add instruction to the worklist.
   /// Instructions will be visited in the order they are added.
   /// You likely want to use this method.
   void add(Instruction *I) {
     if (Deferred.insert(I))
       LLVM_DEBUG(dbgs() << "IC: ADD DEFERRED: " << *I << '\n');
   }
void push(Instruction *I) {
     }
   }
 
   void pushValue(Value *V) {
     if (Instruction *I = dyn_cast<Instruction>(V))
       push(I);
   }
 
-  void addDeferredInstructions() {
-    for (Instruction *I : reverse(Deferred))
-      push(I);
-    Deferred.clear();
+  Instruction *popDeferred() {
+    if (Deferred.empty())
+      return nullptr;
+    return Deferred.pop_back_val();
   }
 
-  /// AddInitialGroup - Add the specified batch of stuff in reverse order.
-  /// which should only be done when the worklist is empty and when the group
-  /// has no duplicates.
-  void addInitialGroup(ArrayRef<Instruction *> List) {
-    assert(Worklist.empty() && "Worklist must be empty to add initial group");
-    Worklist.reserve(List.size()+16);
-    WorklistMap.reserve(List.size());
-    LLVM_DEBUG(dbgs() << "IC: ADDING: " << List.size()
-                      << " instrs to worklist\n");
-    unsigned Idx = 0;
-    for (Instruction *I : reverse(List)) {
-      WorklistMap.insert(std::make_pair(I, Idx++));
-      Worklist.push_back(I);
-    }
+  void reserve(size_t Size) {
+    Worklist.reserve(Size + 16);
+    WorklistMap.reserve(Size);
   }
 
   /// Remove I from the worklist if it exists.
   void remove(Instruction *I) {
     DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I);
     if (It != WorklistMap.end()) {
       // Don't bother moving everything down, just null out the slot.
       Worklist[It->second] = nullptr;
       WorklistMap.erase(It);
     }
 
     Deferred.remove(I);
   }
 
   Instruction *removeOne() {
+    if (Worklist.empty())
+      return nullptr;
     Instruction *I = Worklist.pop_back_val();
     WorklistMap.erase(I);
     return I;
   }
 
   /// When an instruction is simplified, add all users of the instruction
   /// to the work lists because they might get more simplified now.
   void pushUsersToWorkList(Instruction &I) {

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

Instruction *eraseInstFromFunction(Instruction &I) {
     assert(I.use_empty() && "Cannot erase instruction that is used!");
     salvageDebugInfoOrMarkUndef(I);
 
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
     if (I.getNumOperands() < 8) {
       for (Use &Operand : I.operands())
         if (auto *Inst = dyn_cast<Instruction>(Operand))
-          Worklist.push(Inst);
+          Worklist.add(Inst);
     }
     Worklist.remove(&I);
     I.eraseFromParent();
     MadeIRChange = true;
     return nullptr; // Don't do anything with FI
   }
 
   void computeKnownBits(const Value *V, KnownBits &Known,

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (DII->getParent() == SrcBlock) {
       }
     }
   }
   return true;
 }
 
 bool InstCombiner::run() {
   while (!Worklist.isEmpty()) {
+    // Walk deferred instructions in reverse order, and push them to the
+    // worklist, which means they'll end up popped from the worklist in-order.
+    while (Instruction *I = Worklist.popDeferred()) {
+      // Check to see if we can DCE the instruction. We do this already here to
+      // reduce the number of uses and thus allow other folds to trigger.
+      // Note that eraseInstFromFunction() may push additional instructions on
+      // the deferred worklist, so this will DCE whole instruction chains.
+      if (isInstructionTriviallyDead(I, &TLI)) {
+        eraseInstFromFunction(*I);
+        ++NumDeadInst;
+        continue;
+      }
+
+      Worklist.push(I);
+    }
+
     Instruction *I = Worklist.removeOne();
     if (I == nullptr) continue;  // skip null values.
 
     // Check to see if we can DCE the instruction.
     if (isInstructionTriviallyDead(I, &TLI)) {
       eraseInstFromFunction(*I);
       ++NumDeadInst;
       continue;
if (Instruction *Result = visit(*I)) {
           eraseInstFromFunction(*I);
         } else {
           Worklist.pushUsersToWorkList(*I);
           Worklist.push(I);
         }
       }
       MadeIRChange = true;
     }
-    Worklist.addDeferredInstructions();
   }
 
   Worklist.zap();
   return MadeIRChange;
 }
 
 /// Walk the function in depth-first order, adding all reachable code to the
 /// worklist.
do {
 
     // We have now visited this block!  If we've already been here, ignore it.
     if (!Visited.insert(BB).second)
       continue;
 
     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
       Instruction *Inst = &*BBI++;
 
-      // DCE instruction if trivially dead.
-      if (isInstructionTriviallyDead(Inst, TLI)) {
-        ++NumDeadInst;
-        LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
-        salvageDebugInfoOrMarkUndef(*Inst);
-        Inst->eraseFromParent();
-        MadeIRChange = true;
-        continue;
-      }
-
       // ConstantProp instruction if trivially constant.
       if (!Inst->use_empty() &&
           (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
         if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
           LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *Inst
                             << '\n');
           Inst->replaceAllUsesWith(C);
           ++NumConstProp;
for (BasicBlock *SuccBB : successors(TI))
       Worklist.push_back(SuccBB);
   } while (!Worklist.empty());
 
   // Once we've found all of the instructions to add to instcombine's worklist,
   // add them in reverse order.  This way instcombine will visit from the top
   // of the function down.  This jives well with the way that it adds all uses
   // of instructions to the worklist after doing a transformation, thus avoiding
   // some N^2 behavior in pathological cases.
-  ICWorklist.addInitialGroup(InstrsForInstCombineWorklist);
+  ICWorklist.reserve(InstrsForInstCombineWorklist.size());
+  for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {
+    // DCE instruction if trivially dead. As we iterate in reverse program
+    // order here, we will clean up whole chains of dead instructions.
+    if (isInstructionTriviallyDead(Inst, TLI)) {
+      ++NumDeadInst;
+      LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
+      salvageDebugInfoOrMarkUndef(*Inst);
+      Inst->eraseFromParent();
+      MadeIRChange = true;
+      continue;
+    }
+
+    ICWorklist.push(Inst);
+  }
 
   return MadeIRChange;
 }
 
 /// Populate the IC worklist from a function, and prune any dead basic
 /// blocks discovered in the process.
 ///
 /// This also does basic constant propagation and other forward fixing to make

llvm/test/Transforms/InstCombine/2010-11-01-lshr-mask.ll

-; RUN: opt -instcombine -instcombine-infinite-loop-threshold=3 -S < %s | FileCheck %s
+; RUN: opt -instcombine -instcombine-infinite-loop-threshold=2 -S < %s | FileCheck %s
 
 ; <rdar://problem/8606771>
 define i32 @main(i32 %argc) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:    [[TMP3151:%.*]] = trunc i32 %argc to i8
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[TMP3151]], 5
 ; CHECK-NEXT:    [[TMP4126:%.*]] = and i8 [[TMP1]], 64
 ; CHECK-NEXT:    [[TMP4127:%.*]] = xor i8 [[TMP4126]], 64

llvm/test/Transforms/InstCombine/demorgan-sink-not-into-xor.ll

 
 ; If the operand is easily-invertible, fold into it.
 declare i1 @gen1()
 
 define i1 @positive_easyinvert(i16 %x, i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i16 [[X:%.*]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = icmp slt i16 %x, 0
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp2, %tmp1
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }
 
 define i1 @positive_easyinvert0(i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert0(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp2, %tmp1
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }
 
 define i1 @positive_easyinvert1(i8 %y) {
 ; CHECK-LABEL: @positive_easyinvert1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @gen1()
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %tmp1 = call i1 @gen1()
   %tmp2 = icmp slt i8 %y, 0
   %tmp3 = xor i1 %tmp1, %tmp2
   %tmp4 = xor i1 %tmp3, true
   ret i1 %tmp4
 }

llvm/test/Transforms/InstCombine/logical-select.ll

;
   %add = add <4 x i32> %or, %mask_flip1
   ret <4 x i32> %add
 }
 
 ; The 'ashr' guarantees that we have a bitmask, so this is select with truncated condition.
 
 define i32 @allSignBits(i32 %cond, i32 %tval, i32 %fval) {
 ; CHECK-LABEL: @allSignBits(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[COND:%.*]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[TVAL:%.*]], i32 [[FVAL:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[COND:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[FVAL:%.*]], i32 [[TVAL:%.*]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %bitmask = ashr i32 %cond, 31
   %not_bitmask = xor i32 %bitmask, -1
   %a1 = and i32 %tval, %bitmask
   %a2 = and i32 %not_bitmask, %fval
   %sel = or i32 %a1, %a2
   ret i32 %sel
 }
 
 define <4 x i8> @allSignBits_vec(<4 x i8> %cond, <4 x i8> %tval, <4 x i8> %fval) {
 ; CHECK-LABEL: @allSignBits_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i8> [[COND:%.*]], zeroinitializer
-; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i8> [[TVAL:%.*]], <4 x i8> [[FVAL:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i8> [[COND:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i8> [[FVAL:%.*]], <4 x i8> [[TVAL:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[TMP2]]
 ;
   %bitmask = ashr <4 x i8> %cond, <i8 7, i8 7, i8 7, i8 7>
   %not_bitmask = xor <4 x i8> %bitmask, <i8 -1, i8 -1, i8 -1, i8 -1>
   %a1 = and <4 x i8> %tval, %bitmask
   %a2 = and <4 x i8> %fval, %not_bitmask
   %sel = or <4 x i8> %a2, %a1
   ret <4 x i8> %sel

llvm/test/Transforms/InstCombine/pr44245.ll

 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[COND_TRUE133:%.*]], label [[COND_FALSE138:%.*]]
 ; CHECK:       cond.true133:
 ; CHECK-NEXT:    br label [[COND_END144:%.*]]
 ; CHECK:       cond.false138:
+; CHECK-NEXT:    store %type_2* undef, %type_2** null, align 536870912
 ; CHECK-NEXT:    br label [[COND_END144]]
 ; CHECK:       cond.end144:
-; CHECK-NEXT:    store %type_3* undef, %type_3** null, align 536870912
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ;
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %cond.end144, %entry
   %link.0 = phi %type_2* [ undef, %entry ], [ %cond145, %cond.end144 ]
   %os115 = bitcast %type_2* %link.0 to %type_3*

llvm/test/Transforms/InstCombine/select-imm-canon.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=3 -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s
 
 define i8 @single(i32 %A) {
 ; CHECK-LABEL: @single(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[A:%.*]], -128
 ; CHECK-NEXT:    [[L2:%.*]] = select i1 [[TMP0]], i32 [[A]], i32 -128
 ; CHECK-NEXT:    [[CONV7:%.*]] = trunc i32 [[L2]] to i8
 ; CHECK-NEXT:    ret i8 [[CONV7]]

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine %s -S -o - | FileCheck %s
 
 ; Clamp negative to zero:
 ; E.g., clamp0 implemented in a shifty way, could be optimized as v > 0 ? v : 0, where sub hasNoSignedWrap.
 ; int32 clamp0(int32 v) {
 ;   return ((-(v) >> 31) & (v));
 ; }
 ;
 
 ; Scalar Types
 
 define i8 @sub_ashr_and_i8(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 0
 ; CHECK-NEXT:    ret i8 [[AND]]
 ;
   %sub = sub nsw i8 %y, %x
   %shr = ashr i8 %sub, 7
   %and = and i8 %shr, %x
   ret i8 %and
 }
 
 define i16 @sub_ashr_and_i16(i16 %x, i16 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i16 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i16 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i16 [[X]], i16 0
 ; CHECK-NEXT:    ret i16 [[AND]]
 ;
 
   %sub = sub nsw i16 %y, %x
   %shr = ashr i16 %sub, 15
   %and = and i16 %shr, %x
   ret i16 %and
 }
 
 define i32 @sub_ashr_and_i32(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %sub = sub nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %and = and i32 %shr, %x
   ret i32 %and
 }
 
 define i64 @sub_ashr_and_i64(i64 %x, i64 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i64 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i64 [[X]], i64 0
 ; CHECK-NEXT:    ret i64 [[AND]]
 ;
   %sub = sub nsw i64 %y, %x
   %shr = ashr i64 %sub, 63
   %and = and i64 %shr, %x
   ret i64 %and
 }
 
 ; nuw nsw
 
 define i32 @sub_ashr_and_i32_nuw_nsw(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32_nuw_nsw(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %sub = sub nuw nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %and = and i32 %shr, %x
   ret i32 %and
 }
 
 ; Commute
 
 define i32 @sub_ashr_and_i32_commute(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32_commute(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %sub = sub nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %and = and i32 %x, %shr  ; commute %x and %shr
   ret i32 %and
 }
 
 ; Vector Types
 
 define <4 x i32> @sub_ashr_and_i32_vec(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[X]], <4 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <4 x i32> [[AND]]
 ;
   %sub = sub nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %and = and <4 x i32> %shr, %x
   ret <4 x i32> %and
 }
 
 define <4 x i32> @sub_ashr_and_i32_vec_nuw_nsw(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32_vec_nuw_nsw(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[X]], <4 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <4 x i32> [[AND]]
 ;
   %sub = sub nuw nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %and = and <4 x i32> %shr, %x
   ret <4 x i32> %and
 }
 
 define <4 x i32> @sub_ashr_and_i32_vec_commute(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_and_i32_vec_commute(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[X]], <4 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <4 x i32> [[AND]]
 ;
   %sub = sub nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %and = and <4 x i32> %x, %shr  ; commute %x and %shr
   ret <4 x i32> %and
 }
;
   store i32 %sub, i32* %p
   %shr = ashr i32 %sub, 31
   %and = and i32 %shr, %x
   ret i32 %and
 }
 
 define i32 @sub_ashr_and_i32_extra_use_and(i32 %x, i32 %y, i32* %p) {
 ; CHECK-LABEL: @sub_ashr_and_i32_extra_use_and(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 0
 ; CHECK-NEXT:    store i32 [[AND]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %sub = sub nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %and = and i32 %shr, %x
   store i32 %and, i32* %p

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

;
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   %and = and i32 %or, 255
   ret i32 %and
 }
 
 define i8 @sub_ashr_or_i8(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i8 -1, i8 [[X]]
 ; CHECK-NEXT:    ret i8 [[OR]]
 ;
   %sub = sub nsw i8 %y, %x
   %shr = ashr i8 %sub, 7
   %or = or i8 %shr, %x
   ret i8 %or
 }
 
 define i16 @sub_ashr_or_i16(i16 %x, i16 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i16(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i16 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i16 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i16 -1, i16 [[X]]
 ; CHECK-NEXT:    ret i16 [[OR]]
 ;
   %sub = sub nsw i16 %y, %x
   %shr = ashr i16 %sub, 15
   %or = or i16 %shr, %x
   ret i16 %or
 }
 
 define i32 @sub_ashr_or_i32(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32(
-; 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
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   ret i32 %or
 }
 
 define i64 @sub_ashr_or_i64(i64 %x, i64 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i64(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i64 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i64 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select i1 [[TMP1]], i64 -1, i64 [[X]]
 ; CHECK-NEXT:    ret i64 [[OR]]
 ;
   %sub = sub nsw i64 %y, %x
   %shr = ashr i64 %sub, 63
   %or = or i64 %shr, %x
   ret i64 %or
 }
 
 ; nuw nsw
 
 define i32 @sub_ashr_or_i32_nuw_nsw(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32_nuw_nsw(
-; 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 nuw nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   ret i32 %or
 }
 
 ; Commute
 
 define i32 @sub_ashr_or_i32_commute(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32_commute(
-; 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
   %shr = ashr i32 %sub, 31
   %or = or i32 %x, %shr  ; commute %shr and %x
   ret i32 %or
 }
 
 ; Vector Types
 
 define <4 x i32> @sub_ashr_or_i32_vec(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, <4 x i32> [[X]]
 ; CHECK-NEXT:    ret <4 x i32> [[OR]]
 ;
   %sub = sub nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %or = or <4 x i32> %shr, %x
   ret <4 x i32> %or
 }
 
 define <4 x i32> @sub_ashr_or_i32_vec_nuw_nsw(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32_vec_nuw_nsw(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, <4 x i32> [[X]]
 ; CHECK-NEXT:    ret <4 x i32> [[OR]]
 ;
   %sub = sub nuw nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %or = or <4 x i32> %shr, %x
   ret <4 x i32> %or
 }
 
 define <4 x i32> @sub_ashr_or_i32_vec_commute(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @sub_ashr_or_i32_vec_commute(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[OR:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, <4 x i32> [[X]]
 ; CHECK-NEXT:    ret <4 x i32> [[OR]]
 ;
   %sub = sub nsw <4 x i32> %y, %x
   %shr = ashr <4 x i32> %sub, <i32 31, i32 31, i32 31, i32 31>
   %or = or <4 x i32> %x, %shr
   ret <4 x i32> %or
 }
;
   store i32 %sub, i32* %p
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   ret i32 %or
 }
 
 define i32 @sub_ashr_or_i32_extra_use_or(i32 %x, i32 %y, i32* %p) {
 ; CHECK-LABEL: @sub_ashr_or_i32_extra_use_or(
-; 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:    store i32 [[OR]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %sub = sub nsw i32 %y, %x
   %shr = ashr i32 %sub, 31
   %or = or i32 %shr, %x
   store i32 %or, i32* %p

llvm/test/Transforms/InstCombine/vec_sext.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define <4 x i32> @vec_select(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: @vec_select(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <4 x i32> zeroinitializer, [[A:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[B:%.*]], zeroinitializer
-; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[SUB]], <4 x i32> [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[B:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[A]], <4 x i32> [[SUB]]
 ; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %cmp = icmp slt <4 x i32> %b, zeroinitializer
   %sext = sext <4 x i1> %cmp to <4 x i32>
   %sub = sub nsw <4 x i32> zeroinitializer, %a
   %t0 = icmp slt <4 x i32> %sext, zeroinitializer
   %sext3 = sext <4 x i1> %t0 to <4 x i32>
   %t1 = xor <4 x i32> %sext3, <i32 -1, i32 -1, i32 -1, i32 -1>
   %t2 = and <4 x i32> %a, %t1
   %t3 = and <4 x i32> %sext3, %sub
   %cond = or <4 x i32> %t2, %t3
   ret <4 x i32> %cond
 }
 
 define <4 x i32> @vec_select_alternate_sign_bit_test(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: @vec_select_alternate_sign_bit_test(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <4 x i32> zeroinitializer, [[A:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <4 x i32> [[B:%.*]], zeroinitializer
-; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[A]], <4 x i32> [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <4 x i32> [[B:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[SUB]], <4 x i32> [[A]]
 ; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %cmp = icmp sgt <4 x i32> %b, <i32 -1, i32 -1, i32 -1, i32 -1>
   %sext = sext <4 x i1> %cmp to <4 x i32>
   %sub = sub nsw <4 x i32> zeroinitializer, %a
   %t0 = icmp slt <4 x i32> %sext, zeroinitializer
   %sext3 = sext <4 x i1> %t0 to <4 x i32>
   %t1 = xor <4 x i32> %sext3, <i32 -1, i32 -1, i32 -1, i32 -1>

llvm/test/Transforms/SimplifyCFG/merge-cond-stores.ll

 end:
   ret void
 }
 
 ; This test should entirely fold away, leaving one large basic block.
 define void @test_recursive(i32* %p, i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @test_recursive(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[X4:%.*]] = icmp eq i32 [[D:%.*]], 0
-; CHECK-NEXT:    [[TMP0:%.*]] = or i32 [[C:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP0]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[TMP0]], [[C:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[X4]], true
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i1 [[TMP2]], [[TMP3]]
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[TMP5:%.*]], label [[TMP6:%.*]]
 ; CHECK:       5:
 ; CHECK-NEXT:    [[X3:%.*]] = icmp eq i32 [[C]], 0
 ; CHECK-NEXT:    [[X2:%.*]] = icmp ne i32 [[B]], 0
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = zext i1 [[X2]] to i32