Tighten known bits for ctpop based on zero input bits

[reames]

Summary

This is a cleaned up patch from the one written by John Regehr based on the findings of the Souper superoptimizer.

The basic idea here is that input bits that are known zero reduce the maximum count that the intrinsic could return. We know that the number of bits required to represent a particular count is at most log2(N)+1.

[sanjoy]

lib/Analysis/ValueTracking.cpp

1374 ↗

(On Diff #35996)

I think you can also do (with better variable naming :) ):

X = CLZ(BitsPossiblySet);
KnownZero |= APInt::getHighBitsSet(BitWidth, X);
KnownOne &= ~KnownZero;

to avoid the branch, since this would work for BitsPossiblySet == 0 as well.

[reames]

Address Sanjoy's review comments.

[reames]

ping. Sanjoy?

[sanjoy]

LGTM.

lib/Analysis/ValueTracking.cpp

1379 ↗

(On Diff #36654)

Nit: capitalize We.

Actually, I'd just change this to say // Bits known to be zero ....

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         unsigned LowBits = Log2_32(BitWidth)+1;
         // If this call is undefined for 0, the result will be less than 2^n.
         if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
           LowBits -= 1;
         KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
         break;
       }
       case Intrinsic::ctpop: {
-        unsigned LowBits = Log2_32(BitWidth)+1;
-        KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
+        computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL,
+                         Depth + 1, Q);
+        // We can bound the space the count needs.  Also, bits known to be zero
+        // can't contribute to the population.
+        unsigned BitsPossiblySet = BitWidth - KnownZero2.countPopulation();
+        unsigned LeadingZeros =
+          APInt(BitWidth, BitsPossiblySet).countLeadingZeros();
+        assert(LeadingZeros >= 0 && LeadingZeros <= BitWidth);
+        KnownZero |= APInt::getHighBitsSet(BitWidth, LeadingZeros);
+        KnownOne &= ~KnownZero;
+        // TODO: we could bound KnownOne using the lower bound on the number
+        // of bits which might be set provided by popcnt KnownOne2.
         break;
       }
       case Intrinsic::fabs: {
         Type *Ty = II->getType();
         APInt SignBit = APInt::getSignBit(Ty->getScalarSizeInBits());
         KnownZero |= APInt::getSplat(Ty->getPrimitiveSizeInBits(), SignBit);
         break;
       }

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

+; RUN: opt < %s -S -instcombine | FileCheck %s
+
+declare i32 @llvm.ctpop.i32(i32)
+declare i8 @llvm.ctpop.i8(i8)
+declare void @llvm.assume(i1)
+
+define i1 @test1(i32 %arg) {
+; CHECK: @test1
+; CHECK: ret i1 false
+  %and = and i32 %arg, 15
+  %cnt = call i32 @llvm.ctpop.i32(i32 %and)
+  %res = icmp eq i32 %cnt, 9
+  ret i1 %res
+}
+
+define i1 @test2(i32 %arg) {
+; CHECK: @test2
+; CHECK: ret i1 false
+  %and = and i32 %arg, 1
+  %cnt = call i32 @llvm.ctpop.i32(i32 %and)
+  %res = icmp eq i32 %cnt, 2
+  ret i1 %res
+}
+
+define i1 @test3(i32 %arg) {
+; CHECK: @test3
+; CHECK: ret i1 false
+  ;; Use an assume to make all the bits known without triggering constant 
+  ;; folding.  This is trying to hit a corner case where we have to avoid
+  ;; taking the log of 0.
+  %assume = icmp eq i32 %arg, 0
+  call void @llvm.assume(i1 %assume)
+  %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: @test4
+; CHECK: ret i1 %res
+  %cnt = call i8 @llvm.ctpop.i8(i8 %arg)
+  %res = icmp eq i8 %cnt, 2
+  ret i1 %res
+}