[InstCombine] Fold (ctpop(X) == 1) | (X == 0) into ctpop(X) < 2

[hkmatsumoto]

Summary

https://alive2.llvm.org/ce/z/94yRMN

Fixes #54177

[xbolva00]

llvm/test/Transforms/InstCombine/icmp-or.ll

371

Please add a test with vector type.

llvm/test/Transforms/InstCombine/ispow2.ll

537–538

Now reduced.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2623

Should we also handle the opposite version ctpop(x) != 1 && x != 0?

llvm/test/Transforms/InstCombine/icmp-or.ll

399

Can you add a vector test as well?

[RKSimon]

llvm/test/Transforms/InstCombine/icmp-or.ll

382

What about if the ctpop has multi uses?

[craig.topper]

llvm/test/Transforms/InstCombine/icmp-or.ll

382

The ctpop isn't being changed. Does it matter if it has more uses?

What is interesting is if the (icmp eq (ctpop(x)), 1) has another user other than the or.

[hkmatsumoto]

Address code reviews

• Fold (icmp ne ctpop(X) 1) & (icmp ne X 0) into (icmp ugt ctpop(X) 1) as well

foldOrOfCtpop folds the aforementioned pattern into (icmp uge ctpop(X) 2)
and that is later transformed into (icmp ugt ctpop(X) 1). I think this is fine.

• Add tests for vector type

[hkmatsumoto]

llvm/test/Transforms/InstCombine/ispow2.ll

537–538

Since this is almost the first time contributing to LLVM, I'm not sure what I should do about this. Does it mean we should remove these reduced tests?

[xbolva00]

llvm/test/Transforms/InstCombine/ispow2.ll

537–538

just remove "(but this could reduce)" from the comment I think.

[hkmatsumoto]

Address code review, removing "but this could reduce" from comment

[hkmatsumoto]

llvm/test/Transforms/InstCombine/ispow2.ll

537–538

I get it, thanks!

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

921

Since the m_ICmp matches are the same for And/Or can we share those and possibly early out from the function if they don't match. Then only use IsAnd to check the predicates and control the what we emit?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

916

This name is too specific now that we are handling 'and'. It could be called "foldIsPowerOf2OrZero" to match the transform below?

llvm/test/Transforms/InstCombine/ispow2.ll

537–538

It seems better to rename this test and the next one now that we can optimize it - "is_pow2_or_zero" or similar.

[hkmatsumoto]

Reflect code reviews

• Factor out pattern matching code and exit early if it didn't match
• Rename foldOrOfCtpop to foldIsPowerOf2OrZero
• Rename 2 tests in ispow2.ll to is_pow2_or_zero(_logical) to inform that this patch optimizes them

[hkmatsumoto]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

921

You are definitely right! Changed accordingly.

[spatel]

A few changes for tests suggested inline.

There might be some generalization of ctpop analysis that we can make as a follow-up patch.
For example, I was looking at a "wrong predicate" combination and noticed that we miss possible optimizations like this:
https://alive2.llvm.org/ce/z/RRk_d9

llvm/test/Transforms/InstCombine/icmp-or.ll

382

This transform only replaces the logic op with a cmp, so I think we want to do it even if all of the intermediate values have other uses.
Either way, we should have at least one test where there are other uses of the icmps.

412

We can swap the operand order of the "or" for more coverage of the commuted pattern.

444

We are testing the 'and' pattern too now, so it doesn't match the name of the file. I think it would be better to add the new tests next to the changed tests in ispow2.ll.

478

Instead of checking the same wrong constant again, it would be better to change to a wrong predicate(s).

[hkmatsumoto]

Reflect code reviews

• Move all added tests to ispow2.ll from icmp-or.ll since now that they contain tests for "and" operand

• Add tests to confirm extra uses don't affect the optimization

• Add negative tests whose order of the op/and operand being swapped (named *_swap_cmp)

• Add negative tests for wrong predicates

• Test various wrong constants

[hkmatsumoto]

llvm/test/Transforms/InstCombine/ispow2.ll

540

Renamed to is_pow2or0_ctpop.

555

Renamed to is_pow2or0_ctpop_logical.

[hkmatsumoto]

In D122077#3405085, @spatel wrote:

A few changes for tests suggested inline.

There might be some generalization of ctpop analysis that we can make as a follow-up patch.
For example, I was looking at a "wrong predicate" combination and noticed that we miss possible optimizations like this:
https://alive2.llvm.org/ce/z/RRk_d9

Very interesting! I'll look into it and (try to) send a follow-up PR.

[spatel]

Thank you for the making the test changes. I pushed the baseline tests on your behalf here:
ebaa28e0750b

Please rebase and update the patch here in Phabricator - it should only show changes in the CHECK lines after the update.

[RKSimon]

rebase?

[joerg]

Why is this fold preferable to (X & (X-1)) == 0? At least on all architectures without native population count, the binary-and based test is preferable and it might even be better with it.

[xbolva00]

In D122077#3413550, @joerg wrote:

Why is this fold preferable to (X & (X-1)) == 0? At least on all architectures without native population count, the binary-and based test is preferable and it might even be better with it.

Less IR instructions. I think SDAG already expands some ctpop patterns to logic (backends should decide about optimal form)

[hkmatsumoto]

Sync with main branch

[spatel]

In D122077#3413565, @xbolva00 wrote:

In D122077#3413550, @joerg wrote:

Why is this fold preferable to (X & (X-1)) == 0? At least on all architectures without native population count, the binary-and based test is preferable and it might even be better with it.

Less IR instructions. I think SDAG already expands some ctpop patterns to logic (backends should decide about optimal form)

Correct - we try to convert the setcc(ctpop) pattern here:
https://github.com/llvm/llvm-project/blob/f1d8e46258c6a08ca1a375dc9670dd5581d6cf65/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp#L3772

That doesn't check whether the target has a popcount instruction for scalar types, so it is potentially too aggressive. For x86, we have a bonus optimization after that, so it should not show up there:
https://godbolt.org/z/oc16Kdhcf

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

915

Why create ">= 2" instead of "> 1" directly?

I don't think it makes the transform or code any clearer with ">= 2", and we will always canonicalize to the other form, so I would prefer to go directly to the final result for efficiency.

[hkmatsumoto]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

915

You're right. I thought it is fine to let another pass do further transformation but in retrospect, folding >= 2 to > 1 is so trivial that we should do it here.

[hkmatsumoto]

Create ctpop(X) > 1 instead of ctpop(X) >= 2

[spatel]

LGTM

[hkmatsumoto]

@spatel Since I don't have commit access, can you land this patch?
Please use "Hirochika Matsumoto <[e-mail]>" as my identity.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Value *foldSignedTruncationCheck(ICmpInst *ICmp0, ICmpInst *ICmp1,
   }
   // Else, if it does not, then all is ok as-is.
 
   // %r = icmp ult %X, SignBit
   return Builder.CreateICmpULT(X, ConstantInt::get(X->getType(), HighestBit),
                                CxtI.getName() + ".simplified");
 }
 
+/// Fold (icmp eq ctpop(X) 1) | (icmp eq X 0) into (icmp ult ctpop(X) 2) and
+/// fold (icmp ne ctpop(X) 1) & (icmp ne X 0) into (icmp uge ctpop(X) 2).
+static Value *foldIsPowerOf2OrZero(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd,
+                                   InstCombiner::BuilderTy &Builder) {
+  CmpInst::Predicate Pred0, Pred1;
+  Value *X;
+  if (!match(Cmp0, m_ICmp(Pred0, m_Intrinsic<Intrinsic::ctpop>(m_Value(X)),
+                          m_SpecificInt(1))) ||
+      !match(Cmp1, m_ICmp(Pred1, m_Specific(X), m_ZeroInt())))
+    return nullptr;
+
+  Value *CtPop = Cmp0->getOperand(0);
+  if (IsAnd && Pred0 == ICmpInst::ICMP_NE && Pred1 == ICmpInst::ICMP_NE)
+    return Builder.CreateICmpUGE(CtPop, ConstantInt::get(CtPop->getType(), 2));
+  if (!IsAnd && Pred0 == ICmpInst::ICMP_EQ && Pred1 == ICmpInst::ICMP_EQ)
+    return Builder.CreateICmpULT(CtPop, ConstantInt::get(CtPop->getType(), 2));
+
+  return nullptr;
+}
+
 /// Reduce a pair of compares that check if a value has exactly 1 bit set.
 static Value *foldIsPowerOf2(ICmpInst *Cmp0, ICmpInst *Cmp1, bool JoinedByAnd,
                              InstCombiner::BuilderTy &Builder) {
   // Handle 'and' / 'or' commutation: make the equality check the first operand.
   if (JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_NE)
     std::swap(Cmp0, Cmp1);
   else if (!JoinedByAnd && Cmp1->getPredicate() == ICmpInst::ICMP_EQ)
     std::swap(Cmp0, Cmp1);
Value *InstCombinerImpl::foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS,
   if (Value *V = foldLogOpOfMaskedICmps(LHS, RHS, true, Builder))
     return V;
 
   if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, And, Builder, Q))
     return V;
   if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, And, Builder, Q))
     return V;
 
+  if (Value *V = foldIsPowerOf2OrZero(LHS, RHS, /*IsAnd=*/true, Builder))
+    return V;
+  if (Value *V = foldIsPowerOf2OrZero(RHS, LHS, /*IsAnd=*/true, Builder))
+    return V;
+
   // E.g. (icmp sge x, 0) & (icmp slt x, n) --> icmp ult x, n
   if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/false))
     return V;
 
   // E.g. (icmp slt x, n) & (icmp sge x, 0) --> icmp ult x, n
   if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/false))
     return V;
 
if (A && B && B->getType()->isIntOrIntVectorTy())
           Builder.CreateAdd(B, Constant::getAllOnesValue(B->getType())), A);
   }
 
   if (Value *V = foldAndOrOfICmpsWithConstEq(LHS, RHS, Or, Builder, Q))
     return V;
   if (Value *V = foldAndOrOfICmpsWithConstEq(RHS, LHS, Or, Builder, Q))
     return V;
 
+  if (Value *V = foldIsPowerOf2OrZero(LHS, RHS, /*IsAnd=*/false, Builder))
+    return V;
+  if (Value *V = foldIsPowerOf2OrZero(RHS, LHS, /*IsAnd=*/false, Builder))
+    return V;
+
   // E.g. (icmp slt x, 0) | (icmp sgt x, n) --> icmp ugt x, n
   if (Value *V = simplifyRangeCheck(LHS, RHS, /*Inverted=*/true))
     return V;
 
   // E.g. (icmp sgt x, n) | (icmp slt x, 0) --> icmp ugt x, n
   if (Value *V = simplifyRangeCheck(RHS, LHS, /*Inverted=*/true))
     return V;
 

llvm/test/Transforms/InstCombine/icmp-or.ll

 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[OR]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %dec = add i8 %x, -2
   %or = or i8 %dec, %x
   %r = icmp sgt i8 %or, -1
   ret i1 %r
 }
+
+declare i32 @llvm.ctpop.i32(i32)
+
+; (icmp eq ctpop(X) 1) | (icmp eq X 0) --> icmp ult ctpop(X) 2
+
+define i1 @ctpop_or_eq_to_ctpop(i32 %0) {
+; CHECK-LABEL: @ctpop_or_eq_to_ctpop(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]]), !range [[RNG0:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 2
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  %2 = call i32 @llvm.ctpop.i32(i32 %0)
+  %3 = icmp eq i32 %2, 1
+  %4 = icmp eq i32 %0, 0
+  %5 = or i1 %4, %3
+  ret i1 %5
+}
+
+; negative test - wrong constants
+
+define i1 @not_ctpop_or_eq_to_ctpop(i32 %0) {
+; CHECK-LABEL: @not_ctpop_or_eq_to_ctpop(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]]), !range [[RNG0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP0]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = or i1 [[TMP4]], [[TMP3]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
+;
+  %2 = call i32 @llvm.ctpop.i32(i32 %0)
+  %3 = icmp eq i32 %2, 2
+  %4 = icmp eq i32 %0, 0
+  %5 = or i1 %4, %3
+  ret i1 %5
+}
+
+declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>)
+
+define <2 x i1> @ctpop_or_eq_to_ctpop_vec(<2 x i32> %0) {
+; CHECK-LABEL: @ctpop_or_eq_to_ctpop_vec(
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP0:%.*]])
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult <2 x i32> [[TMP2]], <i32 2, i32 2>
+; CHECK-NEXT:    ret <2 x i1> [[TMP3]]
+;
+  %2 = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %0)
+  %3 = icmp eq <2 x i32> %2, <i32 1, i32 1>
+  %4 = icmp eq <2 x i32> %0, <i32 0, i32 0>
+  %5 = or <2 x i1> %4, %3
+  ret <2 x i1> %5
+}
+
+; negative test - wrong constants
+
+define <2 x i1> @not_ctpop_or_eq_to_ctpop_vec(<2 x i32> %0) {
+; CHECK-LABEL: @not_ctpop_or_eq_to_ctpop_vec(
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP0:%.*]])
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq <2 x i32> [[TMP2]], <i32 2, i32 2>
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq <2 x i32> [[TMP0]], zeroinitializer
+; CHECK-NEXT:    [[TMP5:%.*]] = or <2 x i1> [[TMP4]], [[TMP3]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP5]]
+;
+  %2 = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %0)
+  %3 = icmp eq <2 x i32> %2, <i32 2, i32 2>
+  %4 = icmp eq <2 x i32> %0, <i32 0, i32 0>
+  %5 = or <2 x i1> %4, %3
+  ret <2 x i1> %5
+}
+
+; (icmp ne ctpop(X) 1) & (icmp ne X 0) --> icmp uge ctpop(X) 2
+
+define i1 @ctpop_and_ne_to_ctpop(i32 %0) {
+; CHECK-LABEL: @ctpop_and_ne_to_ctpop(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]]), !range [[RNG0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i32 [[TMP2]], 1
+; CHECK-NEXT:    ret i1 [[TMP3]]
+;
+  %2 = call i32 @llvm.ctpop.i32(i32 %0)
+  %3 = icmp ne i32 %2, 1
+  %4 = icmp ne i32 %0, 0
+  %5 = and i1 %4, %3
+  ret i1 %5
+}
+
+; negative test - wrong constants
+
+define i1 @not_ctpop_and_ne_to_ctpop(i32 %0) {
+; CHECK-LABEL: @not_ctpop_and_ne_to_ctpop(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]]), !range [[RNG0]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 2
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP0]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP4]], [[TMP3]]
+; CHECK-NEXT:    ret i1 [[TMP5]]
+;
+  %2 = call i32 @llvm.ctpop.i32(i32 %0)
+  %3 = icmp ne i32 %2, 2
+  %4 = icmp ne i32 %0, 0
+  %5 = and i1 %4, %3
+  ret i1 %5
+}
+
+define <2 x i1> @ctpop_and_ne_to_ctpop_vec(<2 x i32> %0) {
+; CHECK-LABEL: @ctpop_and_ne_to_ctpop_vec(
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP0:%.*]])
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt <2 x i32> [[TMP2]], <i32 1, i32 1>
+; CHECK-NEXT:    ret <2 x i1> [[TMP3]]
+;
+  %2 = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %0)
+  %3 = icmp ne <2 x i32> %2, <i32 1, i32 1>
+  %4 = icmp ne <2 x i32> %0, <i32 0, i32 0>
+  %5 = and <2 x i1> %4, %3
+  ret <2 x i1> %5
+}
+
+; negative test - wrong constants
+
+define <2 x i1> @not_ctpop_and_ne_to_ctpop_vec(<2 x i32> %0) {
+; CHECK-LABEL: @not_ctpop_and_ne_to_ctpop_vec(
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP0:%.*]])
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], <i32 2, i32 2>
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne <2 x i32> [[TMP0]], zeroinitializer
+; CHECK-NEXT:    [[TMP5:%.*]] = and <2 x i1> [[TMP4]], [[TMP3]]
+; CHECK-NEXT:    ret <2 x i1> [[TMP5]]
+;
+  %2 = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %0)
+  %3 = icmp ne <2 x i32> %2, <i32 2, i32 2>
+  %4 = icmp ne <2 x i32> %0, <i32 0, i32 0>
+  %5 = and <2 x i1> %4, %3
+  ret <2 x i1> %5
+}

llvm/test/Transforms/InstCombine/ispow2.ll

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = tail call i32 @llvm.ctpop.i32(i32 %x)
   %cmp = icmp ugt i32 %t0, 1
   %iszero = icmp eq i32 %x, 1
   %r = select i1 %iszero, i1 true, i1 %cmp
   ret i1 %r
 }
 
-; Negative test - wrong predicate (but this could reduce).
-
-define i1 @isnot_pow2_ctpop_wrong_pred1(i32 %x) {
-; CHECK-LABEL: @isnot_pow2_ctpop_wrong_pred1(
+define i1 @is_pow2_or_zero(i32 %x) {
+; CHECK-LABEL: @is_pow2_or_zero(
 ; CHECK-NEXT:    [[T0:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range [[RNG0]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[T0]], 1
-; CHECK-NEXT:    [[ISZERO:%.*]] = icmp eq i32 [[X]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[ISZERO]], [[CMP]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[T0]], 2
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t0 = tail call i32 @llvm.ctpop.i32(i32 %x)
   %cmp = icmp eq i32 %t0, 1
   %iszero = icmp eq i32 %x, 0
   %r = or i1 %iszero, %cmp
   ret i1 %r
 }
 
-define i1 @isnot_pow2_ctpop_wrong_pred1_logical(i32 %x) {
-; CHECK-LABEL: @isnot_pow2_ctpop_wrong_pred1_logical(
+define i1 @is_pow2_or_zero_logical(i32 %x) {
+; CHECK-LABEL: @is_pow2_or_zero_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range [[RNG0]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[T0]], 1
-; CHECK-NEXT:    [[ISZERO:%.*]] = icmp eq i32 [[X]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[ISZERO]], [[CMP]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[T0]], 2
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %t0 = tail call i32 @llvm.ctpop.i32(i32 %x)
   %cmp = icmp eq i32 %t0, 1
   %iszero = icmp eq i32 %x, 0
   %r = select i1 %iszero, i1 true, i1 %cmp
   ret i1 %r
 }