From 9e6356994a0e0d82ad08e8665008991d69721fe1 Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Thu, 12 Sep 2019 20:03:32 +0000 Subject: [PATCH] [SCEV] Support SCEVUMinExpr in getRangeRef. This patch adds support for SCEVUMinExpr to getRangeRef, similar to the support for SCEVUMaxExpr. Reviewers: sanjoy.google, efriedma, reames, nikic Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D67177 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@371768 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/ScalarEvolution.cpp | 8 +++++++ .../ScalarEvolution/max-expr-cache.ll | 2 +- test/Analysis/ScalarEvolution/trip-count15.ll | 24 +++++++++---------- 3 files changed, 21 insertions(+), 13 deletions(-) diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 04d4105cb2e..3817b1142d3 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -5596,6 +5596,14 @@ ScalarEvolution::getRangeRef(const SCEV *S, ConservativeResult.intersectWith(X, RangeType)); } + if (const SCEVUMinExpr *UMin = dyn_cast(S)) { + ConstantRange X = getRangeRef(UMin->getOperand(0), SignHint); + for (unsigned i = 1, e = UMin->getNumOperands(); i != e; ++i) + X = X.umin(getRangeRef(UMin->getOperand(i), SignHint)); + return setRange(UMin, SignHint, + ConservativeResult.intersectWith(X, RangeType)); + } + if (const SCEVUDivExpr *UDiv = dyn_cast(S)) { ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint); ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint); diff --git a/test/Analysis/ScalarEvolution/max-expr-cache.ll b/test/Analysis/ScalarEvolution/max-expr-cache.ll index e30345eb984..52552bef399 100644 --- a/test/Analysis/ScalarEvolution/max-expr-cache.ll +++ b/test/Analysis/ScalarEvolution/max-expr-cache.ll @@ -130,7 +130,7 @@ bb4: %tmp45 = icmp ult i32 %tmp43, 256 %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256 ; CHECK: %tmp46 = select i1 %tmp45, i32 %tmp43, i32 256 -; CHECK-NEXT: --> (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>) +; CHECK-NEXT: --> (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin (1 + (256 umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>)) umin {%tmp3,+,-256}<%bb4>) U: [0,257) S: [0,257) Exits: <> LoopDispositions: { %bb4: Computable, %bb53: Invariant } %tmp47 = icmp ugt i32 %tmp44, %tmp46 %tmp48 = select i1 %tmp47, i32 %tmp44, i32 %tmp46 %tmp49 = ashr i32 %tmp48, 3 diff --git a/test/Analysis/ScalarEvolution/trip-count15.ll b/test/Analysis/ScalarEvolution/trip-count15.ll index a15e3c66bf4..4469439b046 100644 --- a/test/Analysis/ScalarEvolution/trip-count15.ll +++ b/test/Analysis/ScalarEvolution/trip-count15.ll @@ -5,15 +5,15 @@ define void @umin_unsigned_check(i64 %n) { ; CHECK-LABEL: 'umin_unsigned_check' ; CHECK-NEXT: Classifying expressions for: @umin_unsigned_check ; CHECK-NEXT: %min.n = select i1 %min.cmp, i64 4096, i64 %n -; CHECK-NEXT: --> (4096 umin %n) U: full-set S: full-set +; CHECK-NEXT: --> (4096 umin %n) U: [0,4097) S: [0,4097) ; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,4098) S: [0,4098) Exits: (1 + (4096 umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add i64 %iv, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4099) S: [1,4099) Exits: (2 + (4096 umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @umin_unsigned_check -; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. -; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. -; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; CHECK-NEXT: Loop %loop: backedge-taken count is (1 + (4096 umin %n)) +; CHECK-NEXT: Loop %loop: max backedge-taken count is 4097 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (1 + (4096 umin %n)) ; entry: %min.cmp = icmp ult i64 4096, %n @@ -33,15 +33,15 @@ define void @umin_signed_check(i64 %n) { ; CHECK-LABEL: 'umin_signed_check' ; CHECK-NEXT: Classifying expressions for: @umin_signed_check ; CHECK-NEXT: %min.n = select i1 %min.cmp, i64 4096, i64 %n -; CHECK-NEXT: --> (4096 umin %n) U: full-set S: full-set +; CHECK-NEXT: --> (4096 umin %n) U: [0,4097) S: [0,4097) ; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,4098) S: [0,4098) Exits: (1 + (4096 umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add i64 %iv, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,4099) S: [1,4099) Exits: (2 + (4096 umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @umin_signed_check -; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. -; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. -; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; CHECK-NEXT: Loop %loop: backedge-taken count is (1 + (4096 umin %n)) +; CHECK-NEXT: Loop %loop: max backedge-taken count is 4097 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (1 + (4096 umin %n)) ; entry: %min.cmp = icmp ult i64 4096, %n -- 2.40.0