LVI was neglecting to call the transfer functions for instructions where either operand was the full constant range. This dropped a bunch of precision on the floor for operations such as "and x, 1" or "zext x" or "lshr x, 3" where we learn something from the operation even when x is the full range. This patch fixes the precision bug by forcing LVI to unconditionally run the transfer functions.

This patch also fixes a minor precision bug where LVI was only considering binary instructions of the form "op x, C" where C is a constant. This loses precision by neglecting the "op x, y" case where y is not a constant but we still know something about it.

We can measure the precision of LVI by looking at how much entropy it eliminates from a program. If LVI takes a 32-bit variable and constrains its range to [0..256) we can say that we gain 24 bits of information. By totaling up the number of bits we gain across an entire compilation, we can get an idea about how well LVI is working.

Before this patch, here's the information gained while compiling SPEC CINT 2006:

LVI bits 380433 (2.2%)

Known bits 2226534 (12.9%)

Total bits 17237799

After this patch:

LVI bits 2784947 (16.1%)

Known bits 2232534 (12.9%)

Total bits 17253797

So now LVI has become a stronger analysis than the known bits analysis, which is generally a pretty decent analysis, so this is good. There's plenty more gain to be squeezed out of LVI but this was the lowest hanging fruit.

LLVM with this patch passes tests and also compiles a working SPEC CINT 2006. More testing would be good.

Bug was reported here: https://llvm.org/bugs/show_bug.cgi?id=27434