fix major imprecision in LazyValueInfo

[regehr]

Summary

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

[reames]

The data and motivation for this patch is obvious, but code wise, it's a ways off. Let's start with the basics:

1. Always running the transfer rules is straight-forward and unlikely to be expensive compile time wise. Forking the analysis at binary operator is not as clearly safe. I would *strongly* prefer to see this patch split so that we can get the first part in and evaluate the second part separately.

This should be rebased on the refactoring change I just made in revision 267438. This will make the handling for unary vs binary far more obvious. I'd suggest writing the unary case by itself with test cases, and post that for review.

For the unary case, we can simply promote the input to a full range if we can't find a constant range input. For the binary case, we can do the same (provided the RHS is a constant). Once we introduce non-constant RHS, the cost model becomes a bit tricker.

[regehr]

Hi Philip, since this is a relatively straightforward change (or should be) and you're knee deep in the code anyway, I would certainly not be offended if you pushed whatever parts of this into the code base yourself in whatever order makes the most sense.

[reames]

See [LVI] Infer local facts from unary expressions, http://reviews.llvm.org/D19492. That's the first part.

[regehr]

Mostly subsumed by changes implemented by Philip; I'll introduce the remaining changes (taking advantage of LVI information on both sides of a binop) in a different revision.

lib/Analysis/LazyValueInfo.cpp

class LazyValueInfoCache {
     // be revisited after going through the new items.
     bool solveBlockValue(Value *Val, BasicBlock *BB);
     bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
                                  Value *Val, BasicBlock *BB);
     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
                                 PHINode *PN, BasicBlock *BB);
     bool solveBlockValueSelect(LVILatticeVal &BBLV,
                                SelectInst *S, BasicBlock *BB);
+    bool getCachedConstantRange(Value *V, Instruction *BBI, BasicBlock *BB,
+                                ConstantRange &CR);
     bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
                                       Instruction *BBI, BasicBlock *BB);
     void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
                                             Instruction *BBI);
 
     void solve();
 
     ValueCacheEntryTy &lookup(Value *V) {
bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   // If this value is a nonnull pointer, record it's range and bailout.
   PointerType *PT = dyn_cast<PointerType>(BBI->getType());
   if (PT && isKnownNonNull(BBI)) {
     Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
     insertResult(Val, BB, Res);
     return true;
   }
 
-  if (isa<CastInst>(BBI) && BBI->getType()->isIntegerTy()) {
+  CastInst *CI = dyn_cast<CastInst>(BBI);
+  if (CI && CI->isIntegerCast()) {
     if (!solveBlockValueConstantRange(Res, BBI, BB))
       return false;
     insertResult(Val, BB, Res);
     return true;
   }
 
-  BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
-  if (BO && isa<ConstantInt>(BO->getOperand(1))) { 
+  // No point looking for a ConstantRange in a non-integer BinOp like fadd
+  if (isa<BinaryOperator>(BBI) && BBI->getType()->isIntegerTy()) {
     if (!solveBlockValueConstantRange(Res, BBI, BB))
       return false;
     insertResult(Val, BB, Res);
     return true;
   }
 
   DEBUG(dbgs() << " compute BB '" << BB->getName()
                  << "' - unknown inst def found.\n");
bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
   
   LVILatticeVal Result;  // Start Undefined.
   Result.mergeIn(TrueVal, DL);
   Result.mergeIn(FalseVal, DL);
   BBLV = Result;
   return true;
 }
 
+/// If there is a cached ConstantRange for V at instruction BBI, set CR and
+/// return true, otherwise return false
+bool LazyValueInfoCache::getCachedConstantRange(Value *V,
+                                                Instruction *BBI,
+                                                BasicBlock *BB,
+                                                ConstantRange &CR) {
+  if (hasBlockValue(V, BB)) {
+    LVILatticeVal LVal = getBlockValue(V, BB);
+    intersectAssumeBlockValueConstantRange(V, LVal, BBI);
+    if (LVal.isConstantRange())
+      CR = LVal.getConstantRange();
+    else
+      CR = ConstantRange(V->getType()->getIntegerBitWidth());
+    return true;
+  } else {
+    return false;
+  }
+}
+
 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
                                                       Instruction *BBI,
-                                                      BasicBlock *BB) {  
-  // Figure out the range of the LHS.  If that fails, bail.
-  if (!hasBlockValue(BBI->getOperand(0), BB)) {
-    if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
+                                                      BasicBlock *BB) {
+  ConstantRange LHSRange(1);
+  if (!getCachedConstantRange(BBI->getOperand(0), BBI, BB, LHSRange)) {
+    if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) {
       return false;
+    } else {
       BBLV.markOverdefined();
       return true;
     }
-
-  LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
-  intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
-  if (!LHSVal.isConstantRange()) {
-    BBLV.markOverdefined();
-    return true;
   }
-
-  ConstantRange LHSRange = LHSVal.getConstantRange();
   ConstantRange RHSRange(1);
-  IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
   if (isa<BinaryOperator>(BBI)) {
-    if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
-      RHSRange = ConstantRange(RHS->getValue());
+    if (!getCachedConstantRange(BBI->getOperand(1), BBI, BB, RHSRange)) {
+      if (pushBlockValue(std::make_pair(BB, BBI->getOperand(1)))) {
+        return false;
       } else {
         BBLV.markOverdefined();
         return true;
       }
     }
+  }
+
+  IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
   // can evaluate symbolically.  Enhancing that set will allows us to analyze
   // more definitions.
   LVILatticeVal Result;
   switch (BBI->getOpcode()) {
   case Instruction::Add:
     Result.markConstantRange(LHSRange.add(RHSRange));