From adee485adf84ae8af4105ab4e0b62753245f420d Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Wed, 23 Jun 2021 09:42:45 +0100 Subject: [PATCH] [SCEV] Support signed predicates in applyLoopGuards. This adds handling for signed predicates, similar to how unsigned predicates are already handled. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D104732 --- llvm/lib/Analysis/ScalarEvolution.cpp | 15 ++++++++++++++- llvm/test/Analysis/Delinearization/a.ll | 2 +- .../max-backedge-taken-count-guard-info.ll | 16 ++++++++-------- .../ScalarEvolution/max-trip-count-address-space.ll | 2 +- llvm/test/Analysis/ScalarEvolution/max-trip-count.ll | 2 +- llvm/test/Analysis/ScalarEvolution/sext-mul.ll | 4 ++-- 6 files changed, 27 insertions(+), 14 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 0b822c5..79925ed 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -13668,22 +13668,35 @@ const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) { auto I = RewriteMap.find(LHSUnknown->getValue()); const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHS; const SCEV *RewrittenRHS = nullptr; - // TODO: use information from more predicates. switch (Predicate) { case CmpInst::ICMP_ULT: RewrittenRHS = getUMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType()))); break; + case CmpInst::ICMP_SLT: + RewrittenRHS = + getSMinExpr(RewrittenLHS, getMinusSCEV(RHS, getOne(RHS->getType()))); + break; case CmpInst::ICMP_ULE: RewrittenRHS = getUMinExpr(RewrittenLHS, RHS); break; + case CmpInst::ICMP_SLE: + RewrittenRHS = getSMinExpr(RewrittenLHS, RHS); + break; case CmpInst::ICMP_UGT: RewrittenRHS = getUMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType()))); break; + case CmpInst::ICMP_SGT: + RewrittenRHS = + getSMaxExpr(RewrittenLHS, getAddExpr(RHS, getOne(RHS->getType()))); + break; case CmpInst::ICMP_UGE: RewrittenRHS = getUMaxExpr(RewrittenLHS, RHS); break; + case CmpInst::ICMP_SGE: + RewrittenRHS = getSMaxExpr(RewrittenLHS, RHS); + break; case CmpInst::ICMP_EQ: if (isa(RHS)) RewrittenRHS = RHS; diff --git a/llvm/test/Analysis/Delinearization/a.ll b/llvm/test/Analysis/Delinearization/a.ll index 8e0af8c..a03ee77 100644 --- a/llvm/test/Analysis/Delinearization/a.ll +++ b/llvm/test/Analysis/Delinearization/a.ll @@ -11,7 +11,7 @@ ; AddRec: {{{(28 + (4 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j>,+,20}<%for.k> ; CHECK: Base offset: %A ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 4 bytes. -; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<%for.j>][{7,+,5}<%for.k>] +; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<%for.j>][{7,+,5}<%for.k>] define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 { entry: diff --git a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll index bc72ad3..d22cb94 100644 --- a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll +++ b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll @@ -1113,14 +1113,14 @@ define void @test_guard_slt_sgt_1(i32* nocapture %a, i64 %N) { ; CHECK-NEXT: %and = and i1 %c.0, %c.1 ; CHECK-NEXT: --> %and U: full-set S: full-set ; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: (-1 + %N) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,11) S: [0,11) Exits: (-1 + %N) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, i32* %a, i64 %iv ; CHECK-NEXT: --> {%a,+,4}<%loop> U: full-set S: full-set Exits: (-4 + (4 * %N) + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-9223372036854775808) S: [1,-9223372036854775808) Exits: %N LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,12) S: [1,12) Exits: %N LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_slt_sgt_1 ; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %N) -; CHECK-NEXT: Loop %loop: max backedge-taken count is -2 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 10 ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-1 + %N) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 @@ -1156,7 +1156,7 @@ define void @test_guard_slt_sgt_2(i32* nocapture %a, i64 %i) { ; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_slt_sgt_2 ; CHECK-NEXT: Loop %loop: backedge-taken count is (17 + (-1 * %i)) -; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 12 ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (17 + (-1 * %i)) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 @@ -1185,14 +1185,14 @@ define void @test_guard_sle_sge_1(i32* nocapture %a, i64 %N) { ; CHECK-NEXT: %and = and i1 %c.0, %c.1 ; CHECK-NEXT: --> %and U: full-set S: full-set ; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: (-1 + %N) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,12) S: [0,12) Exits: (-1 + %N) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, i32* %a, i64 %iv ; CHECK-NEXT: --> {%a,+,4}<%loop> U: full-set S: full-set Exits: (-4 + (4 * %N) + %a) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw nsw i64 %iv, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-9223372036854775808) S: [1,-9223372036854775808) Exits: %N LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,13) S: [1,13) Exits: %N LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_sle_sge_1 ; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %N) -; CHECK-NEXT: Loop %loop: max backedge-taken count is -2 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 11 ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-1 + %N) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 @@ -1228,7 +1228,7 @@ define void @test_guard_sle_sge_2(i32* nocapture %a, i64 %i) { ; CHECK-NEXT: --> {(1 + %i),+,1}<%loop> U: full-set S: full-set Exits: 18 LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_sle_sge_2 ; CHECK-NEXT: Loop %loop: backedge-taken count is (17 + (-1 * %i)) -; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 13 ; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (17 + (-1 * %i)) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 diff --git a/llvm/test/Analysis/ScalarEvolution/max-trip-count-address-space.ll b/llvm/test/Analysis/ScalarEvolution/max-trip-count-address-space.ll index aaae7ac..7f379d3 100644 --- a/llvm/test/Analysis/ScalarEvolution/max-trip-count-address-space.ll +++ b/llvm/test/Analysis/ScalarEvolution/max-trip-count-address-space.ll @@ -66,4 +66,4 @@ for.end: ; preds = %for.cond.for.end_cr ; CHECK: Determining loop execution counts for: @test ; CHECK-NEXT: backedge-taken count is -; CHECK-NEXT: max backedge-taken count is 4294967294 +; CHECK-NEXT: max backedge-taken count is 2147483646 diff --git a/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll index c266d16..393cade 100644 --- a/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll +++ b/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll @@ -98,7 +98,7 @@ for.end: ; preds = %for.cond.for.end_cr ; CHECK: Determining loop execution counts for: @test ; CHECK-NEXT: backedge-taken count is -; CHECK-NEXT: max backedge-taken count is 4294967294 +; CHECK-NEXT: max backedge-taken count is 2147483646 ; PR19799: Indvars miscompile due to an incorrect max backedge taken count from SCEV. ; CHECK-LABEL: @pr19799 diff --git a/llvm/test/Analysis/ScalarEvolution/sext-mul.ll b/llvm/test/Analysis/ScalarEvolution/sext-mul.ll index b3a8dca..1d634e8 100644 --- a/llvm/test/Analysis/ScalarEvolution/sext-mul.ll +++ b/llvm/test/Analysis/ScalarEvolution/sext-mul.ll @@ -12,7 +12,7 @@ ; CHECK: %tmp15 = getelementptr inbounds i32, i32* %arg, i64 %tmp14 ; CHECK-NEXT: --> {{.*}} Exits: (4 + (4 * (sext i32 (-2 + (2 * %arg2)) to i64)) + %arg) ; CHECK:Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg2 to i64)) -; CHECK-NEXT:Loop %bb7: max backedge-taken count is 4294967294 +; CHECK-NEXT:Loop %bb7: max backedge-taken count is 2147483646 ; CHECK-NEXT:Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg2 to i64)) define void @foo(i32* nocapture %arg, i32 %arg1, i32 %arg2) { @@ -53,7 +53,7 @@ bb7: ; preds = %bb7, %bb3 ; CHECK: %t14 = or i128 %t10, 1 ; CHECK-NEXT: --> {{.*}} Exits: (1 + (sext i127 (-633825300114114700748351602688 + (633825300114114700748351602688 * (zext i32 %arg5 to i127))) to i128)) ; CHECK: Loop %bb7: backedge-taken count is (-1 + (zext i32 %arg5 to i128)) -; CHECK-NEXT: Loop %bb7: max backedge-taken count is 4294967294 +; CHECK-NEXT: Loop %bb7: max backedge-taken count is 2147483646 ; CHECK-NEXT: Loop %bb7: Predicated backedge-taken count is (-1 + (zext i32 %arg5 to i128)) define void @goo(i32* nocapture %arg3, i32 %arg4, i32 %arg5) { -- 2.7.4