[InstCombine] C - cttz(X) => ctlz(X) if C is bitwidth

[deadalnix]

Summary

Also do its counterpart C - ctlz(X) => cttz(X) if C is bitwidth .

[nikic]

This is missing alive2 proofs.

Are there any tests where C is not the bit width? I didn't spot them.

[RKSimon]

Won't this only work if only a single bit is set (pow2)?

[nikic]

In D140935#4025375, @RKSimon wrote:

Won't this only work if only a single bit is set (pow2)?

That, and it's off by one (the constant needs to be bitwidth-1, not bitwidth). The right transform would be this: https://alive2.llvm.org/ce/z/v588Fk

[deadalnix]

Lesson of the day, don't submit patches at 3am. It'll get this sorted out.

[deadalnix]

Ok, it turns out I'm an idiot and the correct transformation is already done. Sorry everybody.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitSub(BinaryOperator &I) {
   }
 
   // umin(X, Op1) - Op1 --> 0 - usub.sat(Op1, X)
   if (match(Op0, m_OneUse(m_c_UMin(m_Value(X), m_Specific(Op1))))) {
     Value *USub = Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Op1, X});
     return BinaryOperator::CreateNeg(USub);
   }
 
+  // C - X if C is bitwidth
+  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits()))) {
     // C - ctpop(X) => ctpop(~X) if C is bitwidth
-  if (match(Op0, m_SpecificInt(Ty->getScalarSizeInBits())) &&
-      match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
+    if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctpop>(m_Value(X)))))
       return replaceInstUsesWith(
           I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
                                      {Builder.CreateNot(X)}));
 
+    // C - cttz(X) => ctlz(X) if C is bitwidth
+    if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::cttz>(m_Value(X)))))
+      return replaceInstUsesWith(
+          I, Builder.CreateIntrinsic(
+                 Intrinsic::ctlz, {I.getType()},
+                 {X, cast<IntrinsicInst>(Op1)->getArgOperand(1)}));
+
+    // C - ctlz(X) => cttz(X) if C is bitwidth
+    if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::ctlz>(m_Value(X)))))
+      return replaceInstUsesWith(
+          I, Builder.CreateIntrinsic(
+                 Intrinsic::cttz, {I.getType()},
+                 {X, cast<IntrinsicInst>(Op1)->getArgOperand(1)}));
+  }
+
   return TryToNarrowDeduceFlags();
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) {
   // This is limited with one-use because fneg is assumed better for
   // reassociation and cheaper in codegen than fmul/fdiv.

llvm/test/Transforms/InstCombine/ctpop-cttz.ll

;
   %3 = or i32 %0, %2
   %4 = tail call i32 @llvm.ctpop.i32(i32 %3)
   %5 = sub i32 32, %4
   ret i32 %5
 }
 
 define <2 x i32> @ctpop1v(<2 x i32> %0) {
 ; CHECK-LABEL: @ctpop1v(
-; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> [[TMP0:%.*]], i1 false)
-; CHECK-NEXT:    [[TMP3:%.*]] = sub nuw nsw <2 x i32> <i32 32, i32 32>, [[TMP2]]
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.ctlz.v2i32(<2 x i32> [[TMP0:%.*]], i1 false)
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %2 = sub <2 x i32> zeroinitializer, %0
   %3 = or <2 x i32> %2, %0
   %4 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %3)
   ret <2 x i32> %4
 }
 
 define i32 @ctpop1_multiuse(i32 %0) {

llvm/test/Transforms/InstCombine/fls-i16.ll

 
 declare void @sink(i16)
 
 
 define void @fold_fls(i16 %x) {
 ; CHECK-LABEL: @fold_fls(
 ; CHECK-NEXT:    call void @sink(i16 0)
 ; CHECK-NEXT:    call void @sink(i16 1)
-; CHECK-NEXT:    [[CTLZ:%.*]] = call i16 @llvm.ctlz.i16(i16 [[X:%.*]], i1 false), !range [[RNG0:![0-9]+]]
-; CHECK-NEXT:    [[TMP1:%.*]] = sub nuw nsw i16 16, [[CTLZ]]
-; CHECK-NEXT:    call void @sink(i16 [[TMP1]])
+; CHECK-NEXT:    [[NX:%.*]] = call i16 @llvm.cttz.i16(i16 [[X:%.*]], i1 false), !range [[RNG0:![0-9]+]]
+; CHECK-NEXT:    call void @sink(i16 [[NX]])
 ; CHECK-NEXT:    ret void
 ;
   %n0 = call i16 @fls(i16 0)
   call void @sink(i16 %n0)
 
   %n1 = call i16 @fls(i16 1)
   call void @sink(i16 %n1)
 
   %nx = call i16 @fls(i16 %x)
   call void @sink(i16 %nx)
 
   ret void
 }

llvm/test/Transforms/InstCombine/fls.ll

;
   %whatever = call i32 @flsll(i64 42)
   ret i32 %whatever
 }
 
 ; Lower to llvm.ctlz() if the argument is not a constant
 
 define i32 @flsnotconst(i64 %z) {
 ; CHECK-LABEL: @flsnotconst(
-; CHECK-NEXT:    [[CTLZ:%.*]] = call i64 @llvm.ctlz.i64(i64 [[Z:%.*]], i1 false), !range [[RNG0:![0-9]+]]
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[CTLZ]] to i32
-; CHECK-NEXT:    [[GOO:%.*]] = sub nsw i32 64, [[TMP1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.cttz.i64(i64 [[Z:%.*]], i1 false), !range [[RNG0:![0-9]+]]
+; CHECK-NEXT:    [[GOO:%.*]] = trunc i64 [[TMP1]] to i32
 ; CHECK-NEXT:    ret i32 [[GOO]]
 ;
   %goo = call i32 @flsl(i64 %z)
   ret i32 %goo
 }
 
 ; Make sure we lower fls(0) to 0 and not to `undef`.