[InstCombine] canonicalize "extract lowest set bit" away from cttz intrinsic

[spatel]

Summary

1 << (cttz X) --> -X & X
https://alive2.llvm.org/ce/z/qv3E9e

This creates an extra use of the input value, so that's generally not preferred, but there are advantages to this direction:

1. 'negate' and 'and' allow for better analysis than 'cttz'.
2. This is more likely to induce follow-on transforms (in the example from issue #60801, we'll get the decrement pattern).
3. The more basic ALU ops are more likely to result in better codegen across a variety of targets.

This won't solve the motivating bugs (see issue #60799) because we do not recognize the redundant icmp+sel, and the x86 backend may not have the pattern-matching to produce the optimal BMI instructions.

[nikic]

LGTM. I think this is a reasonable canonical form, especially as @goldstein.w.n added KnownBits support for these patterns recently.

Worth noting that for pow2 detection we canonicalize in the reverse direction (towards ctpop and icmp), and I don't quite remember why we ended up going with that somewhat unusual choice.

[kazu]

LGTM. Thanks!

[spatel]

In D144329#4136980, @nikic wrote:

Worth noting that for pow2 detection we canonicalize in the reverse direction (towards ctpop and icmp), and I don't quite remember why we ended up going with that somewhat unusual choice.

For this pattern:
(-A & A) != A --> ctpop(A) > 1
It was a combination of less instructions, less uses, and being the more obvious spelling for, "Is more than one bit set?"

We can make the same argument about cttz with the low-set-bit in this pattern, but it's the same number of instructions and has the other noted benefits. Both ways have advantages, so we just have to make a choice.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) {
   }
 
   if (match(Op0, m_One())) {
     // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
     if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
       return BinaryOperator::CreateLShr(
           ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);
 
+    // Canonicalize "extract lowest set bit" using cttz to and-with-negate:
+    // 1 << (cttz X) --> -X & X
+    if (match(Op1,
+              m_OneUse(m_Intrinsic<Intrinsic::cttz>(m_Value(X), m_Value())))) {
+      Value *NegX = Builder.CreateNeg(X, "neg");
+      return BinaryOperator::CreateAnd(NegX, X);
+    }
+
     // The only way to shift out the 1 is with an over-shift, so that would
     // be poison with or without "nuw". Undef is excluded because (undef << X)
     // is not undef (it is zero).
     Constant *ConstantOne = cast<Constant>(Op0);
     if (!I.hasNoUnsignedWrap() && !ConstantOne->containsUndefElement()) {
       I.setHasNoUnsignedWrap();
       return &I;
     }

llvm/test/Transforms/InstCombine/shift.ll

;
   %d = sdiv i32 %x, 42
   call void @use_i32(i32 %d)
   %r = ashr i32 %d, 31
   ret i32 %r
 }
 
 define i32 @shl1_cttz(i32 %x) {
 ; CHECK-LABEL: @shl1_cttz(
-; CHECK-NEXT:    [[TZ:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true), !range [[RNG0:![0-9]+]]
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 1, [[TZ]]
+; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[X:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = and i32 [[NEG]], [[X]]
 ; CHECK-NEXT:    ret i32 [[SHL]]
 ;
   %tz = call i32 @llvm.cttz.i32(i32 %x, i1 true)
   %shl = shl i32 1, %tz
   ret i32 %shl
 }
 
 define <2 x i8> @shl1_cttz_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @shl1_cttz_vec(
-; CHECK-NEXT:    [[TZ:%.*]] = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> [[X:%.*]], i1 false)
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <2 x i8> <i8 1, i8 1>, [[TZ]]
+; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = and <2 x i8> [[NEG]], [[X]]
 ; CHECK-NEXT:    ret <2 x i8> [[SHL]]
 ;
   %tz = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> %x, i1 false)
   %shl = shl <2 x i8> <i8 1, i8 1>, %tz
   ret <2 x i8> %shl
 }
 
 define <2 x i8> @shl1_cttz_vec_poison(<2 x i8> %x) {
 ; CHECK-LABEL: @shl1_cttz_vec_poison(
-; CHECK-NEXT:    [[TZ:%.*]] = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> [[X:%.*]], i1 false)
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <2 x i8> <i8 1, i8 poison>, [[TZ]]
+; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[X:%.*]]
+; CHECK-NEXT:    [[SHL:%.*]] = and <2 x i8> [[NEG]], [[X]]
 ; CHECK-NEXT:    ret <2 x i8> [[SHL]]
 ;
   %tz = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> %x, i1 false)
   %shl = shl <2 x i8> <i8 1, i8 poison>, %tz
   ret <2 x i8> %shl
 }
 
+; negative test - extra use
+
 define i32 @shl1_cttz_extra_use(i32 %x) {
 ; CHECK-LABEL: @shl1_cttz_extra_use(
-; CHECK-NEXT:    [[TZ:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 false), !range [[RNG0]]
+; CHECK-NEXT:    [[TZ:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 false), !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[TZ]])
 ; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 1, [[TZ]]
 ; CHECK-NEXT:    ret i32 [[SHL]]
 ;
   %tz = call i32 @llvm.cttz.i32(i32 %x, i1 false)
   call void @use_i32(i32 %tz)
   %shl = shl i32 1, %tz
   ret i32 %shl
 }
 
+; negative test - must be shift-left of 1
+
 define i32 @shl2_cttz(i32 %x) {
 ; CHECK-LABEL: @shl2_cttz(
 ; CHECK-NEXT:    [[TZ:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true), !range [[RNG0]]
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TZ]]
 ; CHECK-NEXT:    ret i32 [[SHL]]
 ;
   %tz = call i32 @llvm.cttz.i32(i32 %x, i1 true)
   %shl = shl i32 2, %tz
   ret i32 %shl
 }