[InstCombine] Fix store merge worklist management

[nikic]

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=46680.

Just like insertions through IRBuilder, InsertNewInstBefore() should be using the deferred worklist mechanism, so that processing of newly added instructions is prioritized.

There's one side-effect of the worklist order change which could be classified as a regression. An add op gets pushed through a select that at the time is not a umax. We could add a reverse transform that tries to push adds in the reverse direction to restore a min/max, but that seems like a sure way of getting infinite loops :) Seems like something that should best wait on min/max intrinsics.

[lebedev.ri]

llvm/test/Transforms/InstCombine/pr46680.ll

2

Please precommit with larger threshold and change it here in the patch.

[nikic]

Rebase over test.

[lebedev.ri]

There's one side-effect of the worklist order change which could be classified as a regression. An add op gets pushed through a select that at the time is not a umax. We could add a reverse transform that tries to push adds in the reverse direction to restore a min/max, but that seems like a sure way of getting infinite loops :) Seems like something that should best wait on min/max intrinsics.

Yeah, i think we can/should easily undo that, but indeed, until intrinsics are here, it can't not cause infinite loops.

So LGTM.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   ///
   /// Also adds the new instruction to the worklist and returns \p New so that
   /// it is suitable for use as the return from the visitation patterns.
   Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
     assert(New && !New->getParent() &&
            "New instruction already inserted into a basic block!");
     BasicBlock *BB = Old.getParent();
     BB->getInstList().insert(Old.getIterator(), New); // Insert inst
-    Worklist.push(New);
+    Worklist.add(New);
     return New;
   }
 
   /// Same as InsertNewInstBefore, but also sets the debug loc.
   Instruction *InsertNewInstWith(Instruction *New, Instruction &Old) {
     New->setDebugLoc(Old.getDebugLoc());
     return InsertNewInstBefore(New, Old);
   }

llvm/test/Transforms/InstCombine/minmax-fold.ll

;
   %a = add nuw i32 %x, 15
   %c = icmp ult i32 %a, 42
   %r = select i1 %c, i32 %a, i32 42
   ret i32 %r
 }
 
 define i32 @add_umin_constant_limit(i32 %x) {
 ; CHECK-LABEL: @add_umin_constant_limit(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i32 41, i32 42
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[DOTNOT]], i32 41, i32 42
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add nuw i32 %x, 41
   %c = icmp ult i32 %a, 42
   %r = select i1 %c, i32 %a, i32 42
   ret i32 %r
 }
 
;
   %a = add nuw <2 x i33> %x, <i33 5, i33 5>
   %c = icmp ugt <2 x i33> %a, <i33 240, i33 240>
   %r = select <2 x i1> %c, <2 x i33> %a, <2 x i33> <i33 240, i33 240>
   ret <2 x i33> %r
 }
 
 define i8 @PR14613_umin(i8 %x) {
 ; CHECK-LABEL: @PR14613_umin(
-; CHECK-NEXT:    [[U7:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[X:%.*]], i8 15)
-; CHECK-NEXT:    ret i8 [[U7]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[X:%.*]], i8 15)
+; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %u4 = zext i8 %x to i32
   %u5 = add nuw nsw i32 %u4, 15
   %u6 = icmp ult i32 %u5, 255
   %u7 = select i1 %u6, i32 %u5, i32 255
   %r = trunc i32 %u7 to i8
   ret i8 %r
 }
 
 define i8 @PR14613_umax(i8 %x) {
 ; CHECK-LABEL: @PR14613_umax(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], -16
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 -16
-; CHECK-NEXT:    [[U7:%.*]] = add nsw i8 [[TMP2]], 15
+; CHECK-NEXT:    [[X_OP:%.*]] = add i8 [[X]], 15
+; CHECK-NEXT:    [[U7:%.*]] = select i1 [[TMP1]], i8 [[X_OP]], i8 -1
 ; CHECK-NEXT:    ret i8 [[U7]]
 ;
   %u4 = zext i8 %x to i32
   %u5 = add nuw nsw i32 %u4, 15
   %u6 = icmp ugt i32 %u5, 255
   %u7 = select i1 %u6, i32 %u5, i32 255
   %r = trunc i32 %u7 to i8
   ret i8 %r
;
   %c = icmp sgt <2 x i33> %a, <i33 240, i33 240>
   %r = select <2 x i1> %c, <2 x i33> %a, <2 x i33> <i33 240, i33 240>
   ret <2 x i33> %r
 }
 
 define i8 @PR14613_smin(i8 %x) {
 ; CHECK-LABEL: @PR14613_smin(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[X:%.*]], 40
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 40
-; CHECK-NEXT:    [[U7:%.*]] = add nsw i8 [[TMP2]], 15
+; CHECK-NEXT:    [[X_OP:%.*]] = add i8 [[X]], 15
+; CHECK-NEXT:    [[U7:%.*]] = select i1 [[TMP1]], i8 [[X_OP]], i8 55
 ; CHECK-NEXT:    ret i8 [[U7]]
 ;
   %u4 = sext i8 %x to i32
   %u5 = add nuw nsw i32 %u4, 15
   %u6 = icmp slt i32 %u5, 55
   %u7 = select i1 %u6, i32 %u5, i32 55
   %r = trunc i32 %u7 to i8
   ret i8 %r
 }
 
 define i8 @PR14613_smax(i8 %x) {
 ; CHECK-LABEL: @PR14613_smax(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i8 [[X:%.*]], 40
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 40
-; CHECK-NEXT:    [[U7:%.*]] = add nuw i8 [[TMP2]], 15
+; CHECK-NEXT:    [[X_OP:%.*]] = add i8 [[X]], 15
+; CHECK-NEXT:    [[U7:%.*]] = select i1 [[TMP1]], i8 [[X_OP]], i8 55
 ; CHECK-NEXT:    ret i8 [[U7]]
 ;
   %u4 = sext i8 %x to i32
   %u5 = add nuw nsw i32 %u4, 15
   %u6 = icmp sgt i32 %u5, 55
   %u7 = select i1 %u6, i32 %u5, i32 55
   %r = trunc i32 %u7 to i8
   ret i8 %r

llvm/test/Transforms/InstCombine/pr46680.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
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-linux-gnu"
 
 @a = dso_local local_unnamed_addr global i64 0, align 8
 @d = dso_local local_unnamed_addr global i64 0, align 8
 @c = external dso_local local_unnamed_addr global i8, align 1