diff options
author | Yingwei Zheng <dtcxzyw2333@gmail.com> | 2024-06-04 23:50:17 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-06-04 23:50:17 +0800 |
commit | 0a39c88e81dadca9f6ceef8e0b0be0ed692fe4fe (patch) | |
tree | 4e728335582409859c98c004b139157faa868528 /llvm | |
parent | 6cd86d0fae8cbb752a713860f131b9b759b2cbb8 (diff) | |
download | llvm-0a39c88e81dadca9f6ceef8e0b0be0ed692fe4fe.zip llvm-0a39c88e81dadca9f6ceef8e0b0be0ed692fe4fe.tar.gz llvm-0a39c88e81dadca9f6ceef8e0b0be0ed692fe4fe.tar.bz2 |
[InstCombine] Fold `select Cond, not X, X` into `Cond ^ X` (#93591)
See the following example:
```
define i1 @src(i64 %x, i1 %y) {
%1526 = icmp ne i64 %x, 0
%1527 = icmp eq i64 %x, 0
%sel = select i1 %y, i1 %1526, i1 %1527
ret i1 %sel
}
define i1 @tgt(i64 %x, i1 %y) {
%1527 = icmp eq i64 %x, 0
%sel = xor i1 %y, %1527
ret i1 %sel
}
```
I find that this pattern is common in C/C++/Rust code base.
This patch folds `select Cond, Y, X` into `Cond ^ X` iff:
1. X has the same type as Cond
2. X is poison -> Y is poison
3. X == !Y
Alive2: https://alive2.llvm.org/ce/z/hSmkHS
Diffstat (limited to 'llvm')
-rw-r--r-- | llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp | 31 | ||||
-rw-r--r-- | llvm/test/Transforms/InstCombine/select-cmp.ll | 135 |
2 files changed, 166 insertions, 0 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp index a9aba55..313beb7 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp @@ -3505,6 +3505,33 @@ static bool matchFMulByZeroIfResultEqZero(InstCombinerImpl &IC, Value *Cmp0, return false; } +/// Return true iff: +/// 1. X is poison implies Y is poison. +/// 2. X is true implies Y is false. +/// 3. X is false implies Y is true. +/// Otherwise, return false. +static bool isKnownInversion(Value *X, Value *Y) { + // Handle X = icmp pred A, B, Y = icmp pred A, C. + Value *A, *B, *C; + ICmpInst::Predicate Pred1, Pred2; + if (!match(X, m_ICmp(Pred1, m_Value(A), m_Value(B))) || + !match(Y, m_c_ICmp(Pred2, m_Specific(A), m_Value(C)))) + return false; + + if (B == C) + return Pred1 == ICmpInst::getInversePredicate(Pred2); + + // Try to infer the relationship from constant ranges. + const APInt *RHSC1, *RHSC2; + if (!match(B, m_APInt(RHSC1)) || !match(C, m_APInt(RHSC2))) + return false; + + const auto CR1 = ConstantRange::makeExactICmpRegion(Pred1, *RHSC1); + const auto CR2 = ConstantRange::makeExactICmpRegion(Pred2, *RHSC2); + + return CR1.inverse() == CR2; +} + Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) { Value *CondVal = SI.getCondition(); Value *TrueVal = SI.getTrueValue(); @@ -3999,5 +4026,9 @@ Instruction *InstCombinerImpl::visitSelectInst(SelectInst &SI) { } } + // select Cond, !X, X -> xor Cond, X + if (CondVal->getType() == SI.getType() && isKnownInversion(FalseVal, TrueVal)) + return BinaryOperator::CreateXor(CondVal, FalseVal); + return nullptr; } diff --git a/llvm/test/Transforms/InstCombine/select-cmp.ll b/llvm/test/Transforms/InstCombine/select-cmp.ll index 711fac5..4f75745 100644 --- a/llvm/test/Transforms/InstCombine/select-cmp.ll +++ b/llvm/test/Transforms/InstCombine/select-cmp.ll @@ -345,4 +345,139 @@ define i1 @icmp_no_common(i1 %c, i8 %x, i8 %y, i8 %z) { ret i1 %r } +define i1 @test_select_inverse_eq(i64 %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_eq( +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i64 [[X:%.*]], 0 +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[Y:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ne i64 %x, 0 + %cmp2 = icmp eq i64 %x, 0 + %sel = select i1 %y, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_signed(i64 %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_signed( +; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i64 [[X:%.*]], 0 +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[Y:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp sgt i64 %x, -1 + %cmp2 = icmp slt i64 %x, 0 + %sel = select i1 %y, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_unsigned(i64 %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_unsigned( +; CHECK-NEXT: [[CMP2:%.*]] = icmp ugt i64 [[X:%.*]], 10 +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[Y:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ult i64 %x, 11 + %cmp2 = icmp ugt i64 %x, 10 + %sel = select i1 %y, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_eq_ptr(ptr %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_eq_ptr( +; CHECK-NEXT: [[CMP2:%.*]] = icmp ne ptr [[X:%.*]], null +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[Y:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp eq ptr %x, null + %cmp2 = icmp ne ptr %x, null + %sel = select i1 %y, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_fail(i64 %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_fail( +; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i64 [[X:%.*]], 0 +; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i64 [[X]], 0 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[Y:%.*]], i1 [[CMP1]], i1 [[CMP2]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp sgt i64 %x, 0 + %cmp2 = icmp slt i64 %x, 0 + %sel = select i1 %y, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define <2 x i1> @test_select_inverse_vec(<2 x i64> %x, <2 x i1> %y) { +; CHECK-LABEL: @test_select_inverse_vec( +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq <2 x i64> [[X:%.*]], zeroinitializer +; CHECK-NEXT: [[SEL:%.*]] = xor <2 x i1> [[CMP2]], [[Y:%.*]] +; CHECK-NEXT: ret <2 x i1> [[SEL]] +; + %cmp1 = icmp ne <2 x i64> %x, zeroinitializer + %cmp2 = icmp eq <2 x i64> %x, zeroinitializer + %sel = select <2 x i1> %y, <2 x i1> %cmp1, <2 x i1> %cmp2 + ret <2 x i1> %sel +} + +define <2 x i1> @test_select_inverse_vec_fail(<2 x i64> %x, i1 %y) { +; CHECK-LABEL: @test_select_inverse_vec_fail( +; CHECK-NEXT: [[CMP1:%.*]] = icmp ne <2 x i64> [[X:%.*]], zeroinitializer +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq <2 x i64> [[X]], zeroinitializer +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[Y:%.*]], <2 x i1> [[CMP1]], <2 x i1> [[CMP2]] +; CHECK-NEXT: ret <2 x i1> [[SEL]] +; + %cmp1 = icmp ne <2 x i64> %x, zeroinitializer + %cmp2 = icmp eq <2 x i64> %x, zeroinitializer + %sel = select i1 %y, <2 x i1> %cmp1, <2 x i1> %cmp2 + ret <2 x i1> %sel +} + +define i1 @test_select_inverse_nonconst1(i64 %x, i64 %y, i1 %cond) { +; CHECK-LABEL: @test_select_inverse_nonconst1( +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i64 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[COND:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ne i64 %x, %y + %cmp2 = icmp eq i64 %x, %y + %sel = select i1 %cond, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_nonconst2(i64 %x, i64 %y, i1 %cond) { +; CHECK-LABEL: @test_select_inverse_nonconst2( +; CHECK-NEXT: [[CMP2:%.*]] = icmp eq i64 [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[COND:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ne i64 %x, %y + %cmp2 = icmp eq i64 %y, %x + %sel = select i1 %cond, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_nonconst3(i64 %x, i64 %y, i1 %cond) { +; CHECK-LABEL: @test_select_inverse_nonconst3( +; CHECK-NEXT: [[CMP2:%.*]] = icmp uge i64 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[SEL:%.*]] = xor i1 [[CMP2]], [[COND:%.*]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ult i64 %x, %y + %cmp2 = icmp uge i64 %x, %y + %sel = select i1 %cond, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + +define i1 @test_select_inverse_nonconst4(i64 %x, i64 %y, i64 %z, i1 %cond) { +; CHECK-LABEL: @test_select_inverse_nonconst4( +; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i64 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[CMP2:%.*]] = icmp uge i64 [[Z:%.*]], [[Y]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMP1]], i1 [[CMP2]] +; CHECK-NEXT: ret i1 [[SEL]] +; + %cmp1 = icmp ult i64 %x, %y + %cmp2 = icmp uge i64 %z, %y + %sel = select i1 %cond, i1 %cmp1, i1 %cmp2 + ret i1 %sel +} + declare void @use(i1) |