From 5ceb070bbbe3a58870dce811bf8f9e9ec1438d72 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Tue, 11 Jan 2022 18:23:02 +0300 Subject: [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. --- llvm/lib/Analysis/ScalarEvolution.cpp | 41 ++++++++++++++++++---- .../ScalarEvolution/exit-count-select-safe.ll | 40 ++++++++++----------- 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 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(Ops[Idx])) { + SmallVector 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: <> 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: <> 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: <> 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: <> 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: <> 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 ; -- cgit v1.2.1