[SCEV] `getSequentialMinMaxExpr()`: look into `umin` when deduplicating operands

We could just merge all umin into umin_seq, but that is likely
a pessimization, so don't do that, but pretend that we did
for the purpose of deduplication.

2 files changed, 54 insertions, 27 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 02972c75ca48..556472f54426 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -3897,17 +3897,44 @@ ScalarEvolution::getSequentialMinMaxExpr(SCEVTypes Kind,
   {
     SmallPtrSet<const SCEV *, 16> SeenOps;
     unsigned Idx = 0;
-    bool DeletedAny = false;
+    bool Changed = false;
     while (Idx < Ops.size()) {
-      if (SeenOps.insert(Ops[Idx]).second) {
-        ++Idx;
-        continue;
+      // Has the whole operand been seen already?
+      if (!SeenOps.insert(Ops[Idx]).second) {
+        Ops.erase(Ops.begin() + Idx);
+        Changed = true;
+        continue; // Look at operand under this index again.
       }
-      Ops.erase(Ops.begin() + Idx);
-      DeletedAny = true;
+
+      // Look into non-sequential same-typed min/max expressions,
+      // drop any of it's operands that we have already seen.
+      // FIXME: once there are other sequential min/max types, generalize.
+      if (const auto *CommUMinExpr = dyn_cast<SCEVUMinExpr>(Ops[Idx])) {
+        SmallVector<const SCEV *> InnerOps;
+        InnerOps.reserve(CommUMinExpr->getNumOperands());
+        for (const SCEV *InnerOp : CommUMinExpr->operands()) {
+          if (SeenOps.insert(InnerOp).second) // Operand not seen before?
+            InnerOps.emplace_back(InnerOp);   // Keep this inner operand.
+        }
+        // Were any operands of this 'umin' themselves redundant?
+        if (InnerOps.size() != CommUMinExpr->getNumOperands()) {
+          Changed = true;
+          // Was the whole operand effectively redundant? Note that it can
+          // happen even when the operand itself wasn't redundant as a whole.
+          if (InnerOps.empty()) {
+            Ops.erase(Ops.begin() + Idx);
+            continue; // Look at operand under this index again.
+          }
+          // Recreate our operand.
+          Ops[Idx] = getMinMaxExpr(Ops[Idx]->getSCEVType(), InnerOps);
+        }
+      }
+
+      // Ok, can't do anything else about this operand, move onto the next one.
+      ++Idx;
     }
 
-    if (DeletedAny)
+    if (Changed)
       return getSequentialMinMaxExpr(Kind, Ops);
   }
 
diff --git a/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll b/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll
index e8bf108d8624..a1236db3dad6 100644
--- a/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll
+++ b/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll
@@ -166,9 +166,9 @@ define i32 @logical_or_3ops_redundant_uminseq_operand(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: 'logical_or_3ops_redundant_uminseq_operand'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_3ops_redundant_uminseq_operand
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %n umin_seq %k) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %k) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %n umin_seq %k)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %k)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %n, i32 %m)
 ; CHECK-NEXT:    --> (%n umin %m) U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %cond_p3 = select i1 %cond_p0, i1 true, i1 %cond_p1
@@ -176,9 +176,9 @@ define i32 @logical_or_3ops_redundant_uminseq_operand(i32 %n, i32 %m, i32 %k) {
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_3ops_redundant_uminseq_operand
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %n umin_seq %k)
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %k)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %n umin_seq %k)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %k)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
@@ -202,9 +202,9 @@ define i32 @logical_or_3ops_redundant_umin_operand(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: 'logical_or_3ops_redundant_umin_operand'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_3ops_redundant_umin_operand
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %k umin_seq (%n umin %m)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %k umin_seq %m) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %k umin_seq (%n umin %m))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %k umin_seq %m)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %n, i32 %m)
 ; CHECK-NEXT:    --> (%n umin %m) U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %cond_p3 = select i1 %cond_p0, i1 true, i1 %cond_p1
@@ -212,9 +212,9 @@ define i32 @logical_or_3ops_redundant_umin_operand(i32 %n, i32 %m, i32 %k) {
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_3ops_redundant_umin_operand
-; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %k umin_seq (%n umin %m))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq %k umin_seq %m)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %k umin_seq (%n umin %m))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq %k umin_seq %m)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
@@ -238,9 +238,9 @@ define i32 @logical_or_4ops_redundant_operand_across_umins(i32 %n, i32 %m, i32 %
 ; CHECK-LABEL: 'logical_or_4ops_redundant_operand_across_umins'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_4ops_redundant_operand_across_umins
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %k umin_seq (%n umin %q)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %k umin_seq %q) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %k umin_seq (%n umin %q))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %k umin_seq %q)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %n, i32 %m)
 ; CHECK-NEXT:    --> (%n umin %m) U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %umin2 = call i32 @llvm.umin.i32(i32 %n, i32 %q)
@@ -250,9 +250,9 @@ define i32 @logical_or_4ops_redundant_operand_across_umins(i32 %n, i32 %m, i32 %
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_4ops_redundant_operand_across_umins
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %k umin_seq (%n umin %q))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %k umin_seq %q)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %k umin_seq (%n umin %q))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %k umin_seq %q)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
@@ -277,9 +277,9 @@ define i32 @logical_or_3ops_operand_wise_redundant_umin(i32 %n, i32 %m, i32 %k)
 ; CHECK-LABEL: 'logical_or_3ops_operand_wise_redundant_umin'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_3ops_operand_wise_redundant_umin
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %k umin_seq (%n umin %k)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n umin %m) umin_seq %k) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %k umin_seq (%n umin %k))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n umin %m) umin_seq %k)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %n, i32 %m)
 ; CHECK-NEXT:    --> (%n umin %m) U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %umin2 = call i32 @llvm.umin.i32(i32 %n, i32 %k)
@@ -289,9 +289,9 @@ define i32 @logical_or_3ops_operand_wise_redundant_umin(i32 %n, i32 %m, i32 %k)
 ; CHECK-NEXT:    %cond = select i1 %cond_p3, i1 true, i1 %cond_p2
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_3ops_operand_wise_redundant_umin
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %k umin_seq (%n umin %k))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((%n umin %m) umin_seq %k)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %k umin_seq (%n umin %k))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((%n umin %m) umin_seq %k)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
@@ -316,9 +316,9 @@ define i32 @logical_or_3ops_partially_redundant_umin(i32 %n, i32 %m, i32 %k) {
 ; CHECK-LABEL: 'logical_or_3ops_partially_redundant_umin'
 ; CHECK-NEXT:  Classifying expressions for: @logical_or_3ops_partially_redundant_umin
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq (%n umin %m umin %k)) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq (%m umin %k)) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %i.next = add i32 %i, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq (%n umin %m umin %k))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq (%m umin %k))) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %n, i32 %m)
 ; CHECK-NEXT:    --> (%n umin %m) U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %umin2 = call i32 @llvm.umin.i32(i32 %umin, i32 %k)
@@ -326,9 +326,9 @@ define i32 @logical_or_3ops_partially_redundant_umin(i32 %n, i32 %m, i32 %k) {
 ; CHECK-NEXT:    %cond = select i1 %cond_p0, i1 true, i1 %cond_p1
 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 ; CHECK-NEXT:  Determining loop execution counts for: @logical_or_3ops_partially_redundant_umin
-; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq (%n umin %m umin %k))
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (%n umin_seq (%m umin %k))
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq (%n umin %m umin %k))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%n umin_seq (%m umin %k))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;