[LVI] run transfer function for binary operator even when the RHS isn't a constant

[regehr]

Summary

LVI was symbolically executing binary operators only when the RHS was constant, missing the case where we have a ConstantRange for the RHS, but not an actual constant. Fixing this increases the total number of bits known by LVI from 15.6% to 16.1%.

[reames]

Code wise, this looks fine, however, I think we need to assess the impact on compile time here. My strong suspicion is that this will be prohibitively expensive. Unless the increased precision implies code enough to discount the increased runtime, I'm really hesitant to commit this.

[regehr]

Do we have a standard benchmark for measuring effect on compile time? If I was going to be somewhat careful about it I'd do a single-threaded build of LLVM using itself, then repeat enough times to get statistical significance. Is that good enough? Overkill? Is there something other than LLVM that I should be building? I have SPEC 2006 handy but an not sure it's widely available.

[regehr]

Looks like this patch makes a -j1 build of LLVM + Clang about 4 seconds slower on a Haswell-E. The total build takes about 87 minutes. The effect is robust across repetitions. I can give more details if anyone wants.

[regehr]

A few more reps of the build completed, and it's more like a 6 second slowdown on an 1.5-hour non-parallel build.

I'd argue that requiring a constant on the RHS makes LVI quirky and unpredictable.

[reames]

Gah, thought I'd responded to this one months ago.

LGTM - I was convinced by the lack of observed compile time problem and the fact that LVI really should be able to catch this. If we can't, well, we should fix the algorithm so it can.

lib/Analysis/LazyValueInfo.cpp

1134

separating out a helper function getRangeForOperand would help here.

[regehr]

Refresh patch, and fix a test broken by increased LVI precision.

[regehr]

factor out the getRangeForOperand() code

[regehr]

eliminate tabs

[regehr]

refactor a bit-- getRangeForOperand() now returns an optional since it can fail

[regehr]

tweak spacing

lib/Analysis/LazyValueInfo.cpp

bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   }
   else if (BBI->getType()->isIntegerTy()) {
     if (isa<CastInst>(BBI)) {
       if (!solveBlockValueCast(Res, BBI, BB))
         return false;
       insertResult(Val, BB, Res);
       return true;
     }
-    BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
-    if (BO && isa<ConstantInt>(BO->getOperand(1))) { 
+    if (isa<BinaryOperator>(BBI)) { 
       if (!solveBlockValueBinaryOp(Res, BBI, BB))
         return false;
       insertResult(Val, BB, Res);
       return true;
     }
   }
 
   DEBUG(dbgs() << " compute BB '" << BB->getName()
bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
   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())
       LHSRange = LHSVal.getConstantRange();
   }
 
-  ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
-  ConstantRange RHSRange = ConstantRange(RHS->getValue());
+  // Same process for RHS.
+  if (!hasBlockValue(BBI->getOperand(1), BB))
+    if (pushBlockValue(std::make_pair(BB, BBI->getOperand(1))))
+      // More work to do before applying this transfer rule.
+      return false;
+
+  ConstantRange RHSRange = ConstantRange(OperandBitWidth);
+  if (hasBlockValue(BBI->getOperand(1), BB)) {
+    LVILatticeVal RHSVal = getBlockValue(BBI->getOperand(1), BB);
+    intersectAssumeBlockValueConstantRange(BBI->getOperand(1), RHSVal, BBI);
+    if (RHSVal.isConstantRange())
+      RHSRange = RHSVal.getConstantRange();
+  }
 
   // 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));

test/Transforms/CorrelatedValuePropagation/icmp.ll

merge:
   unreachable
 
 bb_false:
   %tmp48 = icmp sle i64 %tmp35, 0
   tail call void @check2(i1 %tmp48) #4
   unreachable
 }
 
+; Make sure binary operator transfer functions are run when RHS is non-constant
+; CHECK-LABEL: @test3
+define i1 @test3(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %add = add i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 25
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Same as previous but make sure nobody gets over-zealous
+; CHECK-LABEL: @test4
+define i1 @test4(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 10
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 10
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %add = add i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %add, 15
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
+; Make sure binary operator transfer functions are run when RHS is non-constant
+; CHECK-LABEL: @test5
+define i1 @test5(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 5
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 5
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %shifted = shl i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %shifted, 65536
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK: ret i1 true
+  ret i1 %ret
+}
+
+; Same as previous but make sure nobody gets over-zealous
+; CHECK-LABEL: @test6
+define i1 @test6(i32 %x, i32 %y) #0 {
+entry:
+  %cmp1 = icmp ult i32 %x, 5
+  br i1 %cmp1, label %cont1, label %out
+
+cont1:
+  %cmp2 = icmp ult i32 %y, 15
+  br i1 %cmp2, label %cont2, label %out
+
+cont2:
+  %shifted = shl i32 %x, %y
+  br label %cont3
+
+cont3:
+  %cmp3 = icmp ult i32 %shifted, 65536
+  br label %out
+
+out:
+  %ret = phi i1 [ true, %entry], [ true, %cont1 ], [ %cmp3, %cont3 ]
+; CHECK-NOT: ret i1 true
+  ret i1 %ret
+}
+
 attributes #4 = { noreturn }