From 18eaff1510525a2226e1fd0c31c6b176f07ae0a7 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Mon, 9 May 2022 15:01:27 +0200 Subject: [PATCH] [ScalarEvolution] Fold %x umin_seq %y if %x cannot be zero Fold %x umin_seq %y to %x umin %y if %x cannot be zero. They only differ in semantics for %x==0. More generally %x *_seq %y folds to %x * %y if %x cannot be the saturation fold (though currently we only have umin_seq). --- llvm/lib/Analysis/ScalarEvolution.cpp | 18 +++++++++++++++--- .../Analysis/ScalarEvolution/exit-count-select-safe.ll | 8 ++++---- 2 files changed, 19 insertions(+), 7 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index bbd4e0e..b43526d 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -4129,10 +4129,22 @@ ScalarEvolution::getSequentialMinMaxExpr(SCEVTypes Kind, return getSequentialMinMaxExpr(Kind, Ops); } - // In %x umin_seq %y, if %y being poison implies %x is also poison, we can - // use a non-sequential umin instead. + const SCEV *SaturationPoint; + switch (Kind) { + case scSequentialUMinExpr: + SaturationPoint = getZero(Ops[0]->getType()); + break; + default: + llvm_unreachable("Not a sequential min/max type."); + } + + // We can replace %x umin_seq %y with %x umin %y if either: + // * %y being poison implies %x is also poison. + // * %x cannot be the saturating value (e.g. zero for umin). for (unsigned i = 1, e = Ops.size(); i != e; ++i) { - if (::impliesPoison(Ops[i], Ops[i - 1])) { + if (::impliesPoison(Ops[i], Ops[i - 1]) || + isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_NE, Ops[i - 1], + SaturationPoint)) { SmallVector SeqOps = {Ops[i - 1], Ops[i]}; Ops[i - 1] = getMinMaxExpr( SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(Kind), diff --git a/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll b/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll index 9441c83..65ea5e0 100644 --- a/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll +++ b/llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll @@ -954,15 +954,15 @@ define i32 @logical_and_not_zero(i16 %n, i32 %m) { ; CHECK-NEXT: %n1 = add i32 %n.ext, 1 ; CHECK-NEXT: --> (1 + (zext i16 %n to i32)) U: [1,65537) S: [1,65537) ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,65537) S: [0,65537) Exits: ((1 + (zext i16 %n to i32)) umin_seq %m) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,65537) S: [0,65537) Exits: ((1 + (zext i16 %n to i32)) umin %m) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,65538) S: [1,65538) Exits: (1 + ((1 + (zext i16 %n to i32)) umin_seq %m)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,65538) S: [1,65538) Exits: (1 + ((1 + (zext i16 %n to i32)) umin %m)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_not_zero -; CHECK-NEXT: Loop %loop: backedge-taken count is ((1 + (zext i16 %n to i32)) umin_seq %m) +; CHECK-NEXT: Loop %loop: backedge-taken count is ((1 + (zext i16 %n to i32)) umin %m) ; CHECK-NEXT: Loop %loop: max backedge-taken count is 65536 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((1 + (zext i16 %n to i32)) umin_seq %m) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((1 + (zext i16 %n to i32)) umin %m) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; -- 2.7.4