Tighten known bits for ctpop based on zero input bits
authorPhilip Reames <listmail@philipreames.com>
Wed, 14 Oct 2015 22:42:12 +0000 (22:42 +0000)
committerPhilip Reames <listmail@philipreames.com>
Wed, 14 Oct 2015 22:42:12 +0000 (22:42 +0000)
commitc52d6d530c80207b6cc33633b901d3e332ab34b6
tree09c1f9595de2488aef76c8b735287b5aa90f405a
parentdf03dfef7d34a30659c10dd218a51e689fdf8c63
Tighten known bits for ctpop based on zero input bits

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.

Differential Revision: http://reviews.llvm.org/D13253

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@250338 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Analysis/ValueTracking.cpp
test/Transforms/InstCombine/ctpop.ll [new file with mode: 0644]