[InstCombine] Add range metadata to cttz/ctlz/ctpop intrinsic calls based on known bits

[craig.topper]

Summary

I noticed that passing known bits across these intrinsics isn't great at capturing the information we really know. Turning known bits of the input into known bits of a count output isn't able to convey a lot of what we really know.

This patch adds range metadata to these intrinsics based on the known bits.

Currently the patch punts if we already have range metadata present. Should we analyze the existing metadata and refine it to remove things that aren't possible based on known bits? I think its also possible that later visits of this instruction can get more known bit information if instructions are removed and we are able to look further back the input chain. I didn't see any existing code anywhere that rewrites range metadata like we would need to do here.

[hfinkel]

What analysis benefits from this range data? Should we teach that analysis to use known-bits information directly instead of using metadata as an analysis cache?

[craig.topper]

I believe there is code in our compare handling that looks at range metadata. Compares also look at known bits.

The problem is that when converting the known bits from the input into known bits for the output it's very difficult to set any known one bits.

Let's say for cttz all we know from known bits that there is at least one trailing zero, but there could be all trailing zeros. So we can't set any known one bits because the binary encodings for every value in range of possible values for the count have no bits in common,

[sanjoy]

Fwiw, I'm okay with the overall direction.

[RKSimon]

test/Transforms/InstCombine/intrinsics.ll

406 ↗

(On Diff #96865)

This doesn't look relevant to the patch - pre-commit to tidyup?

[craig.topper]

Add tests and support for ctpop

[RKSimon]

Add the new tests to trunk now to show the diff?

[craig.topper]

Tests have been committed to trunk now. Update to show only the delta for the new output.

[RKSimon]

I don't suppose this works for vectors?

[craig.topper]

I lifted the scalar restriction on the existing code over the weekend.

I'm having trouble getting range metadata to work with vectors. One piece of code said "Range types must match instruction type!", but computeKnownBitsFromRangeMetadata assumes metadata is scalar. I haven't found any examples of vector range metadata so I don't know what the right answer is.

[RKSimon]

In D32582#772572, @craig.topper wrote:

I lifted the scalar restriction on the existing code over the weekend.

I'm having trouble getting range metadata to work with vectors. One piece of code said "Range types must match instruction type!", but computeKnownBitsFromRangeMetadata assumes metadata is scalar. I haven't found any examples of vector range metadata so I don't know what the right answer is.

For this patch, I'd be happy with just adding vector tests to show how they are currently affected.

Ideally metadata for vectors would be per-element, but its more likely that it'd match knownbits and just be 'common' bits (although often knownbits only works for splatted vectors).

[craig.topper]

Rebase due to changes that improved vector handling for the existing code. Now we have to explicitly block vectors in the new metadata code.

Also fixed a bug where we created bad metadata for cttz/ctlz if the input bits were unknown and the type was i1. In that case the output value could be 0 or 1 which would be a full set for the metadata which we can't encode.

[craig.topper]

Fix the i1 issue for ctpop as well.

[craig.topper]

Ping

[RKSimon]

LGTM, with the addition of some ctpop vector tests, even if they don't currently combine.

test/Transforms/InstCombine/ctpop.ll

8 ↗

(On Diff #101420)

Please add some ctpop vector tests as well, with the relevant TODO comments.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (!Known.One.isNullValue() ||
       isKnownNonZero(Op0, IC.getDataLayout(), 0, &IC.getAssumptionCache(), &II,
                      &IC.getDominatorTree())) {
     if (!match(II.getArgOperand(1), m_One())) {
       II.setOperand(1, IC.Builder->getTrue());
       return ⅈ
     }
   }
 
+  // Add range metadata since known bits can't completely reflect what we know.
+  // TODO: Handle splat vectors.
+  auto *IT = dyn_cast<IntegerType>(Op0->getType());
+  if (IT && IT->getBitWidth() != 1 && !II.getMetadata(LLVMContext::MD_range)) {
+    Metadata *LowAndHigh[] = {
+        ConstantAsMetadata::get(ConstantInt::get(IT, DefiniteZeros)),
+        ConstantAsMetadata::get(ConstantInt::get(IT, PossibleZeros + 1))};
+    II.setMetadata(LLVMContext::MD_range,
+                   MDNode::get(II.getContext(), LowAndHigh));
+    return &II;
+  }
+
+  return nullptr;
+}
+
+static Instruction *foldCtpop(IntrinsicInst &II, InstCombiner &IC) {
+  assert(II.getIntrinsicID() == Intrinsic::ctpop &&
+         "Expected ctpop intrinsic");
+  Value *Op0 = II.getArgOperand(0);
+  // FIXME: Try to simplify vectors of integers.
+  auto *IT = dyn_cast<IntegerType>(Op0->getType());
+  if (!IT)
+    return nullptr;
+
+  unsigned BitWidth = IT->getBitWidth();
+  KnownBits Known(BitWidth);
+  IC.computeKnownBits(Op0, Known, 0, &II);
+
+  unsigned MinCount = Known.countMinPopulation();
+  unsigned MaxCount = Known.countMaxPopulation();
+
+  // Add range metadata since known bits can't completely reflect what we know.
+  if (IT->getBitWidth() != 1 && !II.getMetadata(LLVMContext::MD_range)) {
+    Metadata *LowAndHigh[] = {
+        ConstantAsMetadata::get(ConstantInt::get(IT, MinCount)),
+        ConstantAsMetadata::get(ConstantInt::get(IT, MaxCount + 1))};
+    II.setMetadata(LLVMContext::MD_range,
+                   MDNode::get(II.getContext(), LowAndHigh));
+    return &II;
+  }
+
   return nullptr;
 }
 
 // TODO: If the x86 backend knew how to convert a bool vector mask back to an
 // XMM register mask efficiently, we could transform all x86 masked intrinsics
 // to LLVM masked intrinsics and remove the x86 masked intrinsic defs.
 static Instruction *simplifyX86MaskedLoad(IntrinsicInst &II, InstCombiner &IC) {
   Value *Ptr = II.getOperand(0);
case Intrinsic::powi:
     break;
 
   case Intrinsic::cttz:
   case Intrinsic::ctlz:
     if (auto *I = foldCttzCtlz(*II, *this))
       return I;
     break;
 
+  case Intrinsic::ctpop:
+    if (auto *I = foldCtpop(*II, *this))
+      return I;
+    break;
+
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (isa<Constant>(II->getArgOperand(0)) &&
         !isa<Constant>(II->getArgOperand(1))) {
       // Canonicalize constants into the RHS.
       Value *LHS = II->getArgOperand(0);

llvm/trunk/test/Transforms/InstCombine/ctpop.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -instcombine | FileCheck %s
 
 declare i32 @llvm.ctpop.i32(i32)
 declare i8 @llvm.ctpop.i8(i8)
+declare i1 @llvm.ctpop.i1(i1)
+declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>)
 declare void @llvm.assume(i1)
 
 define i1 @test1(i32 %arg) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    ret i1 false
 ;
   %and = and i32 %arg, 15
   %cnt = call i32 @llvm.ctpop.i32(i32 %and)
;
   %cnt = call i32 @llvm.ctpop.i32(i32 %arg)
   %res = icmp eq i32 %cnt, 2
   ret i1 %res
 }
 
 ; Negative test for when we know nothing
 define i1 @test4(i8 %arg) {
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctpop.i8(i8 [[ARG:%.*]])
+; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctpop.i8(i8 [[ARG:%.*]]), !range ![[RANGE:[0-9]+]]
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[CNT]], 2
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %cnt = call i8 @llvm.ctpop.i8(i8 %arg)
   %res = icmp eq i8 %cnt, 2
   ret i1 %res
 }
 
 ; Test when the number of possible known bits isn't one less than a power of 2
 ; and the compare value is greater but less than the next power of 2.
-; TODO: The icmp is unnecessary given the known bits of the input.
 define i1 @test5(i32 %arg) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARG:%.*]], 3
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.ctpop.i32(i32 [[AND]])
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[CNT]], 3
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
   %and = and i32 %arg, 3
   %cnt = call i32 @llvm.ctpop.i32(i32 %and)
   %res = icmp eq i32 %cnt, 3
   ret i1 %res
 }
+
+; Test when the number of possible known bits isn't one less than a power of 2
+; and the compare value is greater but less than the next power of 2.
+; TODO: The icmp is unnecessary given the known bits of the input, but range
+; metadata doesn't support vectors
+define <2 x i1> @test5vec(<2 x i32> %arg) {
+; CHECK-LABEL: @test5vec(
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[ARG:%.*]], <i32 3, i32 3>
+; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[AND]])
+; CHECK-NEXT:    [[RES:%.*]] = icmp eq <2 x i32> [[CNT]], <i32 3, i32 3>
+; CHECK-NEXT:    ret <2 x i1> [[RES]]
+;
+  %and = and <2 x i32> %arg, <i32 3, i32 3>
+  %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %and)
+  %res = icmp eq <2 x i32> %cnt, <i32 3, i32 3>
+  ret <2 x i1> %res
+}
+
+; Make sure we don't add range metadata to i1 ctpop.
+define i1 @test6(i1 %arg) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:    [[CNT:%.*]] = call i1 @llvm.ctpop.i1(i1 [[ARG:%.*]])
+; CHECK-NEXT:    ret i1 [[CNT]]
+;
+  %cnt = call i1 @llvm.ctpop.i1(i1 %arg)
+  ret i1 %cnt
+}
+
+; CHECK: ![[RANGE]] = !{i8 0, i8 9}

llvm/trunk/test/Transforms/InstCombine/intrinsics.ll

 declare %ov.result.32 @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
 declare %ov.result.32 @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
 declare %ov.result.32 @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
 declare %ov.result.32 @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone
 declare %ov.result.32 @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone
 declare double @llvm.powi.f64(double, i32) nounwind readonly
 declare i32 @llvm.cttz.i32(i32, i1) nounwind readnone
 declare i32 @llvm.ctlz.i32(i32, i1) nounwind readnone
+declare i1 @llvm.cttz.i1(i1, i1) nounwind readnone
+declare i1 @llvm.ctlz.i1(i1, i1) nounwind readnone
 declare i32 @llvm.ctpop.i32(i32) nounwind readnone
 declare <2 x i32> @llvm.cttz.v2i32(<2 x i32>, i1) nounwind readnone
 declare <2 x i32> @llvm.ctlz.v2i32(<2 x i32>, i1) nounwind readnone
 declare <2 x i32> @llvm.ctpop.v2i32(<2 x i32>) nounwind readnone
 declare i8 @llvm.ctlz.i8(i8, i1) nounwind readnone
 declare <2 x i8> @llvm.ctlz.v2i8(<2 x i8>, i1) nounwind readnone
 declare double @llvm.cos.f64(double %Val) nounwind readonly
 declare double @llvm.sin.f64(double %Val) nounwind readonly

 ; CHECK-NEXT:    ret <2 x i32> <i32 3, i32 3>
 ;
   %or = or <2 x i32> %a, <i32 8, i32 8>
   %and = and <2 x i32> %or, <i32 -8, i32 -8>
   %count = tail call <2 x i32> @llvm.cttz.v2i32(<2 x i32> %and, i1 true) nounwind readnone
   ret <2 x i32> %count
 }
 
+; Make sure we don't add range metadata to i1 cttz.
+define i1 @cttz_i1(i1 %arg) {
+; CHECK-LABEL: @cttz_i1(
+; CHECK-NEXT:    [[CNT:%.*]] = call i1 @llvm.cttz.i1(i1 [[ARG:%.*]], i1 false) #2
+; CHECK-NEXT:    ret i1 [[CNT]]
+;
+  %cnt = call i1 @llvm.cttz.i1(i1 %arg, i1 false) nounwind readnone
+  ret i1 %cnt
+}
+
 define i1 @cttz_knownbits(i32 %arg) {
 ; CHECK-LABEL: @cttz_knownbits(
 ; CHECK-NEXT:    ret i1 false
 ;
   %or = or i32 %arg, 4
   %cnt = call i32 @llvm.cttz.i32(i32 %or, i1 true) nounwind readnone
   %res = icmp eq i32 %cnt, 4
   ret i1 %res
 }
 
 define <2 x i1> @cttz_knownbits_vec(<2 x i32> %arg) {
 ; CHECK-LABEL: @cttz_knownbits_vec(
 ; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = or <2 x i32> %arg, <i32 4, i32 4>
   %cnt = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> %or, i1 true) nounwind readnone
   %res = icmp eq <2 x i32> %cnt, <i32 4, i32 4>
   ret <2 x i1> %res
 }
 
 define i1 @cttz_knownbits2(i32 %arg) {
 ; CHECK-LABEL: @cttz_knownbits2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[ARG:%.*]], 4
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.cttz.i32(i32 [[OR]], i1 true)
+; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.cttz.i32(i32 [[OR]], i1 true) #2, !range ![[CTTZ_RANGE:[0-9]+]]
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[CNT]], 2
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %or = or i32 %arg, 4
   %cnt = call i32 @llvm.cttz.i32(i32 %or, i1 true) nounwind readnone
   %res = icmp eq i32 %cnt, 2
   ret i1 %res
 }
 
 define <2 x i1> @cttz_knownbits2_vec(<2 x i32> %arg) {
 ; CHECK-LABEL: @cttz_knownbits2_vec(
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i32> [[ARG:%.*]], <i32 4, i32 4>
 ; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> [[OR]], i1 true)
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq <2 x i32> [[CNT]], <i32 2, i32 2>
 ; CHECK-NEXT:    ret <2 x i1> [[RES]]
 ;
   %or = or <2 x i32> %arg, <i32 4, i32 4>
   %cnt = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> %or, i1 true) nounwind readnone
   %res = icmp eq <2 x i32> %cnt, <i32 2, i32 2>
   ret <2 x i1> %res
 }
 
-; TODO: The icmp is unnecessary given the known bits of the input.
 define i1 @cttz_knownbits3(i32 %arg) {
 ; CHECK-LABEL: @cttz_knownbits3(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[ARG:%.*]], 4
-; CHECK-NEXT:    [[CNT:%.*]] = call i32 @llvm.cttz.i32(i32 [[OR]], i1 true) #2
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[CNT]], 3
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = or i32 %arg, 4
   %cnt = call i32 @llvm.cttz.i32(i32 %or, i1 true) nounwind readnone
   %res = icmp eq i32 %cnt, 3
   ret i1 %res
 }
 
 ; TODO: The icmp is unnecessary given the known bits of the input.

 ; CHECK-NEXT:    ret <2 x i8> <i8 2, i8 2>
 ;
   %or = or <2 x i8> %a, <i8 32, i8 32>
   %and = and <2 x i8> %or, <i8 63, i8 63>
   %count = tail call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %and, i1 true) nounwind readnone
   ret <2 x i8> %count
 }
 
+; Make sure we don't add range metadata to i1 ctlz.
+define i1 @ctlz_i1(i1 %arg) {
+; CHECK-LABEL: @ctlz_i1(
+; CHECK-NEXT:    [[CNT:%.*]] = call i1 @llvm.ctlz.i1(i1 [[ARG:%.*]], i1 false) #2
+; CHECK-NEXT:    ret i1 [[CNT]]
+;
+  %cnt = call i1 @llvm.ctlz.i1(i1 %arg, i1 false) nounwind readnone
+  ret i1 %cnt
+}
+
 define i1 @ctlz_knownbits(i8 %arg) {
 ; CHECK-LABEL: @ctlz_knownbits(
 ; CHECK-NEXT:    ret i1 false
 ;
   %or = or i8 %arg, 32
   %cnt = call i8 @llvm.ctlz.i8(i8 %or, i1 true) nounwind readnone
   %res = icmp eq i8 %cnt, 4
   ret i1 %res
 }
 
 define <2 x i1> @ctlz_knownbits_vec(<2 x i8> %arg) {
 ; CHECK-LABEL: @ctlz_knownbits_vec(
 ; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = or <2 x i8> %arg, <i8 32, i8 32>
   %cnt = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %or, i1 true) nounwind readnone
   %res = icmp eq <2 x i8> %cnt, <i8 4, i8 4>
   ret <2 x i1> %res
 }
 
 define i1 @ctlz_knownbits2(i8 %arg) {
 ; CHECK-LABEL: @ctlz_knownbits2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i8 [[ARG:%.*]], 32
-; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctlz.i8(i8 [[OR]], i1 true)
+; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctlz.i8(i8 [[OR]], i1 true) #2, !range ![[CTLZ_RANGE:[0-9]+]]
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[CNT]], 2
 ; CHECK-NEXT:    ret i1 [[RES]]
 ;
   %or = or i8 %arg, 32
   %cnt = call i8 @llvm.ctlz.i8(i8 %or, i1 true) nounwind readnone
   %res = icmp eq i8 %cnt, 2
   ret i1 %res
 }
 
 define <2 x i1> @ctlz_knownbits2_vec(<2 x i8> %arg) {
 ; CHECK-LABEL: @ctlz_knownbits2_vec(
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i8> [[ARG:%.*]], <i8 32, i8 32>
 ; CHECK-NEXT:    [[CNT:%.*]] = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> [[OR]], i1 true)
 ; CHECK-NEXT:    [[RES:%.*]] = icmp eq <2 x i8> [[CNT]], <i8 2, i8 2>
 ; CHECK-NEXT:    ret <2 x i1> [[RES]]
 ;
   %or = or <2 x i8> %arg, <i8 32, i8 32>
   %cnt = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %or, i1 true) nounwind readnone
   %res = icmp eq <2 x i8> %cnt, <i8 2, i8 2>
   ret <2 x i1> %res
 }
 
-; TODO: The icmp is unnecessary given the known bits of the input.
 define i1 @ctlz_knownbits3(i8 %arg) {
 ; CHECK-LABEL: @ctlz_knownbits3(
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[ARG:%.*]], 32
-; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctlz.i8(i8 [[OR]], i1 true) #2
-; CHECK-NEXT:    [[RES:%.*]] = icmp eq i8 [[CNT]], 3
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = or i8 %arg, 32
   %cnt = call i8 @llvm.ctlz.i8(i8 %or, i1 true) nounwind readnone
   %res = icmp eq i8 %cnt, 3
   ret i1 %res
 }
 
 ; TODO: The icmp is unnecessary given the known bits of the input.

 ; CHECK-NEXT:    ret void
 ;
   %B = tail call double @llvm.nearbyint.f64(double 1.5) nounwind
   store volatile double %B, double* %P
   %C = tail call double @llvm.nearbyint.f64(double -1.5) nounwind
   store volatile double %C, double* %P
   ret void
 }
+
+; CHECK: [[CTTZ_RANGE]] = !{i32 0, i32 3}
+; CHECK: [[CTLZ_RANGE]] = !{i8 0, i8 3}