From ce8f42d4af2cf56c96f5a8cc4c4a02bf6b790ccc Mon Sep 17 00:00:00 2001 From: Martin Sebor Date: Tue, 26 Apr 2022 13:15:03 -0600 Subject: [PATCH] [InstCombine] Fold memrchr calls with a constant character. Reviewed By: nikic Differential Revision: //reviews.llvm.org/D123629 --- llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp | 25 ++++++ llvm/test/Transforms/InstCombine/memrchr-2.ll | 10 +-- llvm/test/Transforms/InstCombine/memrchr-3.ll | 119 ++++++++++++++++++++----- 3 files changed, 126 insertions(+), 28 deletions(-) diff --git a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp index 2ef33c6..312aebf 100644 --- a/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyLibCalls.cpp @@ -933,6 +933,31 @@ Value *LibCallSimplifier::optimizeMemRChr(CallInst *CI, IRBuilderBase &B) { return nullptr; } + if (ConstantInt *CharC = dyn_cast(CharVal)) { + // Fold memrchr(S, C, N) for a constant C. + size_t Pos = Str.rfind(CharC->getZExtValue(), EndOff); + if (Pos == StringRef::npos) + // When the character is not in the source array fold the result + // to null regardless of Size. + return NullPtr; + + if (LenC) + // Fold memrchr(s, c, N) --> s + Pos for constant N > Pos. + return B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos)); + + if (Str.find(CharC->getZExtValue(), Pos) == StringRef::npos) { + // When there is just a single occurrence of C in S, fold + // memrchr(s, c, N) --> N <= Pos ? null : s + Pos + // for nonconstant N. + Value *Cmp = B.CreateICmpULE(Size, ConstantInt::get(Size->getType(), + Pos), + "memrchr.cmp"); + Value *SrcPlus = B.CreateGEP(B.getInt8Ty(), SrcStr, B.getInt64(Pos), + "memrchr.ptr_plus"); + return B.CreateSelect(Cmp, NullPtr, SrcPlus, "memrchr.sel"); + } + } + return nullptr; } diff --git a/llvm/test/Transforms/InstCombine/memrchr-2.ll b/llvm/test/Transforms/InstCombine/memrchr-2.ll index e1f8e12..8426d1e 100644 --- a/llvm/test/Transforms/InstCombine/memrchr-2.ll +++ b/llvm/test/Transforms/InstCombine/memrchr-2.ll @@ -16,7 +16,7 @@ declare i8* @memrchr(i8*, i32, i64) define i8* @call_memrchr_a12345_c_ui32max_p1(i32 %C) { ; CHECK-LABEL: @call_memrchr_a12345_c_ui32max_p1( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967296) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967296) +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967296) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 4294967296) ; CHECK-NEXT: ret i8* [[RET]] ; @@ -30,7 +30,7 @@ define i8* @call_memrchr_a12345_c_ui32max_p1(i32 %C) { define i8* @call_memrchr_ax1_c_ui32max_p2(i32 %C) { ; CHECK-LABEL: @call_memrchr_ax1_c_ui32max_p2( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([1 x i8], [1 x i8]* @ax1, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967297) +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([1 x i8], [1 x i8]* @ax1, i64 0, i64 0), i32 [[C:%.*]], i64 4294967297) ; CHECK-NEXT: ret i8* [[RET]] ; @@ -44,7 +44,7 @@ define i8* @call_memrchr_ax1_c_ui32max_p2(i32 %C) { define i8* @call_memrchr_ax_c_ui32max_p2(i32 %C) { ; CHECK-LABEL: @call_memrchr_ax_c_ui32max_p2( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i32 [[TMP0:%.*]], i64 4294967297) +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4294967297) getelementptr inbounds ([0 x i8], [0 x i8]* @ax, i64 0, i64 0), i32 [[C:%.*]], i64 4294967297) ; CHECK-NEXT: ret i8* [[RET]] ; @@ -58,7 +58,7 @@ define i8* @call_memrchr_ax_c_ui32max_p2(i32 %C) { define i8* @call_memrchr_a12345_c_6(i32 %C) { ; CHECK-LABEL: @call_memrchr_a12345_c_6( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 6) +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 6) ; CHECK-NEXT: ret i8* [[RET]] ; @@ -72,7 +72,7 @@ define i8* @call_memrchr_a12345_c_6(i32 %C) { define i8* @call_memrchr_a12345_c_szmax(i32 %C) { ; CHECK-LABEL: @call_memrchr_a12345_c_szmax( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(18446744073709551615) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[TMP0:%.*]], i64 -1) +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(18446744073709551615) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 [[C:%.*]], i64 -1) ; CHECK-NEXT: ret i8* [[RET]] ; diff --git a/llvm/test/Transforms/InstCombine/memrchr-3.ll b/llvm/test/Transforms/InstCombine/memrchr-3.ll index f717b97..7ca5b362 100644 --- a/llvm/test/Transforms/InstCombine/memrchr-3.ll +++ b/llvm/test/Transforms/InstCombine/memrchr-3.ll @@ -105,8 +105,7 @@ define i8* @fold_memrchr_ax_c_1(i32 %C) { define i8* @fold_memrchr_a12345_5_5() { ; CHECK-LABEL: @fold_memrchr_a12345_5_5( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 5) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 4) ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 @@ -119,8 +118,7 @@ define i8* @fold_memrchr_a12345_5_5() { define i8* @fold_memrchr_a12345_5_4() { ; CHECK-LABEL: @fold_memrchr_a12345_5_4( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 4) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* null ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 @@ -133,8 +131,7 @@ define i8* @fold_memrchr_a12345_5_4() { define i8* @fold_memrchr_a12345_4_5() { ; CHECK-LABEL: @fold_memrchr_a12345_4_5( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 4, i64 5) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 3) ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 @@ -147,12 +144,24 @@ define i8* @fold_memrchr_a12345_4_5() { define i8* @fold_memrchr_a12345p1_1_4() { ; CHECK-LABEL: @fold_memrchr_a12345p1_1_4( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(4) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 1), i32 5, i64 4) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* null ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 1 - %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 4) + %ret = call i8* @memrchr(i8* %ptr, i32 1, i64 4) + ret i8* %ret +} + + +; Fold memrchr(a12345 + 1, 2, 4) to a12345 + 1. + +define i8* @fold_memrchr_a12345p1_2_4() { +; CHECK-LABEL: @fold_memrchr_a12345p1_2_4( +; CHECK-NEXT: ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 1) +; + + %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 1 + %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 4) ret i8* %ret } @@ -161,8 +170,7 @@ define i8* @fold_memrchr_a12345p1_1_4() { define i8* @fold_memrchr_a12345_2_5() { ; CHECK-LABEL: @fold_memrchr_a12345_2_5( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 2, i64 5) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 1) ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 @@ -175,8 +183,7 @@ define i8* @fold_memrchr_a12345_2_5() { define i8* @fold_memrchr_a12345_0_n(i64 %N) { ; CHECK-LABEL: @fold_memrchr_a12345_0_n( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 0, i64 [[N:%.*]]) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* null ; %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 @@ -185,12 +192,39 @@ define i8* @fold_memrchr_a12345_0_n(i64 %N) { } +; Fold memrchr(a12345, 3, n) to n < 3 ? null : s + 2. + +define i8* @fold_memrchr_a12345_3_n(i64 %n) { +; CHECK-LABEL: @fold_memrchr_a12345_3_n( +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 3, i64 [[N:%.*]]) +; CHECK-NEXT: ret i8* [[RET]] +; + + %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 + %ret = call i8* @memrchr(i8* %ptr, i32 3, i64 %n) + ret i8* %ret +} + + +; Fold memrchr(a12345, 5, n) to n < 5 ? null : s + 4. + +define i8* @fold_memrchr_a12345_5_n(i64 %n) { +; CHECK-LABEL: @fold_memrchr_a12345_5_n( +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @a12345, i64 0, i64 0), i32 5, i64 [[N:%.*]]) +; CHECK-NEXT: ret i8* [[RET]] +; + + %ptr = getelementptr [5 x i8], [5 x i8]* @a12345, i32 0, i32 0 + %ret = call i8* @memrchr(i8* %ptr, i32 5, i64 %n) + ret i8* %ret +} + + ; Fold memrchr(a123123, 3, 5) to a123123 + 2. define i8* @fold_memrchr_a123123_3_5() { ; CHECK-LABEL: @fold_memrchr_a123123_3_5( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(5) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, i64 5) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 2) ; %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 @@ -203,8 +237,7 @@ define i8* @fold_memrchr_a123123_3_5() { define i8* @fold_memrchr_a123123_3_6() { ; CHECK-LABEL: @fold_memrchr_a123123_3_6( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, i64 6) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 5) ; %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 @@ -216,8 +249,7 @@ define i8* @fold_memrchr_a123123_3_6() { define i8* @fold_memrchr_a123123_2_6() { ; CHECK-LABEL: @fold_memrchr_a123123_2_6( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 2, i64 6) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 4) ; %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 @@ -229,8 +261,7 @@ define i8* @fold_memrchr_a123123_2_6() { define i8* @fold_memrchr_a123123_1_6() { ; CHECK-LABEL: @fold_memrchr_a123123_1_6( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 1, i64 6) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 3) ; %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 @@ -243,11 +274,53 @@ define i8* @fold_memrchr_a123123_1_6() { define i8* @fold_memrchr_a123123_0_6() { ; CHECK-LABEL: @fold_memrchr_a123123_0_6( -; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* noundef nonnull dereferenceable(6) getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 0, i64 6) -; CHECK-NEXT: ret i8* [[RET]] +; CHECK-NEXT: ret i8* null ; %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 %ret = call i8* @memrchr(i8* %ptr, i32 0, i64 6) ret i8* %ret } + + +; Fold memrchr(a123123, 0, n) to null + +define i8* @fold_memrchr_a123123_0_n(i64 %n) { +; CHECK-LABEL: @fold_memrchr_a123123_0_n( +; CHECK-NEXT: ret i8* null +; + + %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 + %ret = call i8* @memrchr(i8* %ptr, i32 0, i64 %n) + ret i8* %ret +} + + +; Don't fold memrchr(a123123, 3, n) (although it's possible to fold the call +; for a small number of occurrences of the character greater than one, it's +; less and less profitable as the number grows). + +define i8* @call_memrchr_a123123_3_n(i64 %n) { +; CHECK-LABEL: @call_memrchr_a123123_3_n( +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 3, i64 [[N:%.*]]) +; CHECK-NEXT: ret i8* [[RET]] +; + + %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 + %ret = call i8* @memrchr(i8* %ptr, i32 3, i64 %n) + ret i8* %ret +} + + +; Same as above but for 2. + +define i8* @call_memrchr_a123123_2_n(i64 %n) { +; CHECK-LABEL: @call_memrchr_a123123_2_n( +; CHECK-NEXT: [[RET:%.*]] = call i8* @memrchr(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @a123123, i64 0, i64 0), i32 2, i64 [[N:%.*]]) +; CHECK-NEXT: ret i8* [[RET]] +; + + %ptr = getelementptr [6 x i8], [6 x i8]* @a123123, i32 0, i32 0 + %ret = call i8* @memrchr(i8* %ptr, i32 2, i64 %n) + ret i8* %ret +} -- 2.7.4