[InstCombine] ctpop(rot(X)) -> ctpop(X)

[xbolva00]

Summary

Proof:
https://alive2.llvm.org/ce/z/ss2zyt - rotl
https://alive2.llvm.org/ce/z/ZM7Aue - rotr

[nikic]

LGTM

[lebedev.ri]

@nikic please don't blindly stamp @xbolva00 reviews.
The QC on those is the same as it ever was.

[xbolva00]

In D101235#2714818, @lebedev.ri wrote:

@nikic please don't blindly stamp @xbolva00 reviews.
The QC on those is the same as it ever was.

I fixed UB, sorry. Arent buildbots designed to find issues? Ok, fine. Fixed. I dont build llvm with msan. Great to know you never do mistakes :)

[lebedev.ri]

In D101235#2714835, @xbolva00 wrote:

In D101235#2714818, @lebedev.ri wrote:

@nikic please don't blindly stamp @xbolva00 reviews.
The QC on those is the same as it ever was.

I fixed UB, sorry. Fixed. I dont build llvm with msan. Great to know you never do mistakes :)

It's a sign of lack of most basic negative test.

I'm just really surprised to *still* see such basic teething problems
after so many years of patches to this area of codebase,
so i'm not really sure how to even suggest to please pay just a bit more attention. :/

[xbolva00]

Well, ctpop_add_no_common_bits contains ctpop( fshl(a, b, 16) ) so A != B path was triggered and still it was ok on my PC and some bots too.

[lebedev.ri]

In D101235#2714847, @xbolva00 wrote:

Well, ctpop_add_no_common_bits contains ctpop( fshl(a, b, 16) ) so A != B path was triggered and still it was ok on my PC and some bots too.

I can't comment on whether or not it reproduces on your machine.
Can you link the bot that run that did run that test and didn't fail?
I would suggest to analyze why that is and change things so that it does reproduce for you.

[xbolva00]

Thankfully @nikic improved documentation for m_Deferred to avoid misuse of m_Specific.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *foldCtpop(IntrinsicInst &II, InstCombinerImpl &IC) {
   Value *Op0 = II.getArgOperand(0);
   Value *X;
 
   // ctpop(bitreverse(x)) -> ctpop(x)
   // ctpop(bswap(x)) -> ctpop(x)
   if (match(Op0, m_BitReverse(m_Value(X))) || match(Op0, m_BSwap(m_Value(X))))
     return IC.replaceOperand(II, 0, X);
 
+  // ctpop(rot(x)) -> ctpop(x)
+  if (match(Op0, m_FShl(m_Value(X), m_Specific(X), m_Value())) ||
+      match(Op0, m_FShr(m_Value(X), m_Specific(X), m_Value())))
+    return IC.replaceOperand(II, 0, X);
+
   // ctpop(x | -x) -> bitwidth - cttz(x, false)
   if (Op0->hasOneUse() &&
       match(Op0, m_c_Or(m_Value(X), m_Neg(m_Deferred(X))))) {
     Function *F =
         Intrinsic::getDeclaration(II.getModule(), Intrinsic::cttz, Ty);
     auto *Cttz = IC.Builder.CreateCall(F, {X, IC.Builder.getFalse()});
     auto *Bw = ConstantInt::get(Ty, APInt(BitWidth, BitWidth));
     return IC.replaceInstUsesWith(II, IC.Builder.CreateSub(Bw, Cttz));

llvm/test/Transforms/InstCombine/ctpop.ll

;
   %and2 = and i32 %b, 2
   %ctpop2 = tail call i32 @llvm.ctpop.i32(i32 %and2)
   %res = add i32 %ctpop1, %ctpop2
   ret i32 %res
 }
 
 define i32 @ctpop_add_no_common_bits(i32 %a, i32 %b) {
 ; CHECK-LABEL: @ctpop_add_no_common_bits(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.fshl.i32(i32 [[B:%.*]], i32 [[B]], i32 16)
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.fshl.i32(i32 [[A:%.*]], i32 [[B:%.*]], i32 16)
 ; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP1]]), !range [[RNG1]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
-  %shl16 = shl i32 %b, 16
+  %shl16 = shl i32 %a, 16
   %ctpop1 = tail call i32 @llvm.ctpop.i32(i32 %shl16)
   %lshl16 = lshr i32 %b, 16
   %ctpop2 = tail call i32 @llvm.ctpop.i32(i32 %lshl16)
   %res = add i32 %ctpop1, %ctpop2
   ret i32 %res
 }
 
 define <2 x i32> @ctpop_add_no_common_bits_vec(<2 x i32> %a, <2 x i32> %b) {
;
   %shl16 = shl <2 x i32> %a, <i32 16, i32 16>
   %ctpop1 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %shl16)
   store <2 x i32> %ctpop1, <2 x i32>* %p
   %lshl16 = lshr <2 x i32> %b, <i32 16, i32 16>
   %ctpop2 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %lshl16)
   %res = add <2 x i32> %ctpop1, %ctpop2
   ret <2 x i32> %res
 }
+
+define i8 @ctpop_rotate_left(i8 %a, i8 %amt)  {
+; CHECK-LABEL: @ctpop_rotate_left(
+; CHECK-NEXT:    [[CTPOP:%.*]] = tail call i8 @llvm.ctpop.i8(i8 [[A:%.*]]), !range [[RNG0]]
+; CHECK-NEXT:    ret i8 [[CTPOP]]
+;
+  %rotl = tail call i8 @llvm.fshl.i8(i8 %a, i8 %a, i8 %amt)
+  %ctpop = tail call i8 @llvm.ctpop.i8(i8 %rotl)
+  ret i8 %ctpop
+}
+
+define i8 @ctpop_rotate_right(i8 %a, i8 %amt)  {
+; CHECK-LABEL: @ctpop_rotate_right(
+; CHECK-NEXT:    [[CTPOP:%.*]] = tail call i8 @llvm.ctpop.i8(i8 [[A:%.*]]), !range [[RNG0]]
+; CHECK-NEXT:    ret i8 [[CTPOP]]
+;
+  %rotr = tail call i8 @llvm.fshr.i8(i8 %a, i8 %a, i8 %amt)
+  %ctpop = tail call i8 @llvm.ctpop.i8(i8 %rotr)
+  ret i8 %ctpop
+}
+
+declare i8 @llvm.fshl.i8(i8, i8, i8)
+declare i8 @llvm.fshr.i8(i8, i8, i8)