[LVI] Infer local facts from unary expressions

[reames]

Summary

As pointed out by John Regehr over in http://reviews.llvm.org/D19485, LVI was being incredibly stupid about applying its transfer rules. Rather than gathering local facts from the expression itself, it was simply giving up entirely if one of the inputs was overdefined. This greatly impacts the precision of the overall analysis and makes it far more fragile as well.

This patch implements only the unary operation case. Once this is in, I'll implement the same for the binary operations.

[regehr]

LGTM

[mcrosier]

lib/Analysis/LazyValueInfo.cpp

1011 ↗

(On Diff #54889)

Please add a period.

When writing comments, write them as English prose, which means they should use proper capitalization, punctuation, etc.

test/Transforms/CorrelatedValuePropagation/basic.ll

420 ↗

(On Diff #54889)

Please add a period.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
   Result.mergeIn(FalseVal, DL);
   BBLV = Result;
   return true;
 }
 
 bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV,
                                              Instruction *BBI,
                                              BasicBlock *BB) {  
-  // Figure out the range of the LHS.  If that fails, bail.
-  if (!hasBlockValue(BBI->getOperand(0), BB)) {
+  // Figure out the range of the LHS.  If that fails, we still apply the
+  // transfer rule on the full set since we may be able to locally infer
+  // interesting facts.
+  if (!hasBlockValue(BBI->getOperand(0), BB))
     if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
+      // More work to do before applying this transfer rule.
       return false;
-    BBLV.markOverdefined();
-    return true;
-  }
 
+  const unsigned OperandBitWidth =
+    BBI->getOperand(0)->getType()->getPrimitiveSizeInBits();
+  
+  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
+  if (hasBlockValue(BBI->getOperand(0), BB)) {
     LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
     intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
-  if (!LHSVal.isConstantRange()) {
-    BBLV.markOverdefined();
-    return true;
+    if (LHSVal.isConstantRange())
+      LHSRange = LHSVal.getConstantRange();
   }
-  ConstantRange LHSRange = LHSVal.getConstantRange();
 
-  IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
+  const unsigned ResultBitWidth =
+    cast<IntegerType>(BBI->getType())->getBitWidth();
 
   // 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::Trunc:
-    Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
+    Result.markConstantRange(LHSRange.truncate(ResultBitWidth));
     break;
   case Instruction::SExt:
-    Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
+    Result.markConstantRange(LHSRange.signExtend(ResultBitWidth));
     break;
   case Instruction::ZExt:
-    Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
+    Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth));
     break;
   case Instruction::BitCast:
     Result.markConstantRange(LHSRange);
     break;
   // Unhandled instructions are overdefined.
   default:
     DEBUG(dbgs() << " compute BB '" << BB->getName()
                  << "' - overdefined (unknown cast).\n");
if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
 
       // If we're interested in the false dest, invert the condition.
       if (!isTrueDest) TrueValues = TrueValues.inverse();
 
       Result = LVILatticeVal::getRange(std::move(TrueValues));
       return true;
     }
   }
   
   return false;
 }
 
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                               BasicBlock *BBTo, LVILatticeVal &Result) {

llvm/trunk/test/Transforms/CorrelatedValuePropagation/basic.ll

a_guard:
   br label %next
 next:
 ; CHECK: next:
 ; CHECK: ret i1 false
   ret i1 %res
 out:
   ret i1 false
 }
+
+define i1 @zext_unknown(i8 %a) {
+; CHECK-LABEL: @zext_unknown
+; CHECK: ret i1 true
+entry:
+  %a32 = zext i8 %a to i32
+  %cmp = icmp sle i32 %a32, 256
+  br label %exit
+exit:
+  ret i1 %cmp
+}
+
+define i1 @trunc_unknown(i32 %a) {
+; CHECK-LABEL: @trunc_unknown
+; CHECK: ret i1 true
+entry:
+  %a8 = trunc i32 %a to i8
+  %a32 = sext i8 %a8 to i32
+  %cmp = icmp sle i32 %a32, 128
+  br label %exit
+exit:
+  ret i1 %cmp
+}
+
+; TODO: missed optimization
+; Make sure we exercise non-integer inputs to unary operators (i.e. crash 
+; check).
+define i1 @bitcast_unknown(float %a) {
+; CHECK-LABEL: @bitcast_unknown
+; CHECK: ret i1 %cmp
+entry:
+  %a32 = bitcast float %a to i32
+  %cmp = icmp sle i32 %a32, 128
+  br label %exit
+exit:
+  ret i1 %cmp
+}