[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

1068

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

 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the interface for lazy computation of value constraint
 // information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/ValueLattice.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
namespace {
   bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
                            BasicBlock *BB);
   bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
                                BasicBlock *BB);
   bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
                               BasicBlock *BB);
   bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
                              BasicBlock *BB);
+  Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I,
+                                             BasicBlock *BB);
   bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
                                BasicBlock *BB);
   bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
                            BasicBlock *BB);
   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                      ValueLatticeElement &BBLV,
                                                      Instruction *BBI);
 
bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
   if (PT && isKnownNonZero(BBI, DL)) {
     Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
     return true;
   }
   if (BBI->getType()->isIntegerTy()) {
     if (auto *CI = dyn_cast<CastInst>(BBI))
       return solveBlockValueCast(Res, CI, BB);
 
-    BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
-    if (BO && isa<ConstantInt>(BO->getOperand(1)))
+    if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
       return solveBlockValueBinaryOp(Res, BO, BB);
   }
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - unknown inst def found.\n");
   Res = getFromRangeMetadata(BBI);
   return true;
 }
bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
 
   ValueLatticeElement Result;  // Start Undefined.
   Result.mergeIn(TrueVal, DL);
   Result.mergeIn(FalseVal, DL);
   BBLV = Result;
   return true;
 }
 
+Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
+                                                              Instruction *I,
+                                                              BasicBlock *BB) {
+  if (!hasBlockValue(I->getOperand(Op), BB))
+    if (pushBlockValue(std::make_pair(BB, I->getOperand(Op))))
+      return None;
+
+  const unsigned OperandBitWidth =
+    DL.getTypeSizeInBits(I->getOperand(Op)->getType());
+  ConstantRange Range = ConstantRange(OperandBitWidth);
+  if (hasBlockValue(I->getOperand(Op), BB)) {
+    ValueLatticeElement Val = getBlockValue(I->getOperand(Op), BB);
+    intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I);
+    if (Val.isConstantRange())
+      Range = Val.getConstantRange();
+  }
+  return Range;
+}
+
 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
                                             CastInst *CI,
                                             BasicBlock *BB) {
   if (!CI->getOperand(0)->getType()->isSized()) {
     // Without knowing how wide the input is, we can't analyze it in any useful
     // way.
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                       << "' - overdefined (unknown cast).\n");
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
   // 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(CI->getOperand(0), BB))
-    if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
-      // More work to do before applying this transfer rule.
-      return false;
-
-  const unsigned OperandBitWidth =
-    DL.getTypeSizeInBits(CI->getOperand(0)->getType());
-  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
-  if (hasBlockValue(CI->getOperand(0), BB)) {
-    ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
-    intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
-                                                  CI);
-    if (LHSVal.isConstantRange())
-      LHSRange = LHSVal.getConstantRange();
-  }
+  Optional<ConstantRange> LHSRes = getRangeForOperand(0, CI, BB);
+  if (!LHSRes.hasValue())
+  ConstantRange LHSRange = LHSRes.getValue();
 
   const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
 
   // 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.
   BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
                                                        ResultBitWidth));
bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
   default:
     // Unhandled instructions are overdefined.
     LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                       << "' - overdefined (unknown binary operator).\n");
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   };
 
-  // Figure out the range of the LHS.  If that fails, use a conservative range,
-  // but apply the transfer rule anyways.  This lets us pick up facts from
-  // expressions like "and i32 (call i32 @foo()), 32"
-  if (!hasBlockValue(BO->getOperand(0), BB))
-    if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
-      // More work to do before applying this transfer rule.
-      return false;
+  // Figure out the ranges of the operands.  If that fails, use a
+  // conservative range, but apply the transfer rule anyways.  This
+  // lets us pick up facts from expressions like "and i32 (call i32
+  // @foo()), 32"
+  Optional<ConstantRange> LHSRes = getRangeForOperand(0, BO, BB);
+  Optional<ConstantRange> RHSRes = getRangeForOperand(1, BO, BB);
+
+  if (!LHSRes.hasValue() || !RHSRes.hasValue())
 
-  const unsigned OperandBitWidth =
-    DL.getTypeSizeInBits(BO->getOperand(0)->getType());
-  ConstantRange LHSRange = ConstantRange(OperandBitWidth);
-  if (hasBlockValue(BO->getOperand(0), BB)) {
-    ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
-    intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
-                                                  BO);
-    if (LHSVal.isConstantRange())
-      LHSRange = LHSVal.getConstantRange();
-  }
-
-  ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
-  ConstantRange RHSRange = ConstantRange(RHS->getValue());
+  ConstantRange LHSRange = LHSRes.getValue();
+  ConstantRange RHSRange = RHSRes.getValue();
 
   // 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.
   Instruction::BinaryOps BinOp = BO->getOpcode();
   BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
   return true;
 }
 
 static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
                                                      bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);

test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 
 ; CHECK-NEXT:    ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%loop' is: overdefined
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%backedge' is: overdefined
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd1 = icmp sge i32 %iv, 0' in BB: '%exit' is: overdefined
 ; CHECK-NEXT:  %cnd1 = icmp sge i32 %iv, 0
   %cnd1 = icmp sge i32 %iv, 0
   %cnd2 = icmp sgt i32 %iv2, 0
 ; CHECK:       %cnd2 = icmp sgt i32 %iv2, 0
-; CHECK:         ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: overdefined
+; CHECK:         ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%loop' is: constantrange<-1, -1>
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%backedge' is: constantrange<-1, 0>
 ; CHECK-DAG:     ; LatticeVal for: '  %cnd = and i1 %cnd1, %cnd2' in BB: '%exit' is: overdefined
 ; CHECK-NEXT:  %cnd = and i1 %cnd1, %cnd2
   %cnd = and i1 %cnd1, %cnd2
   br i1 %cnd, label %backedge, label %exit
 
 ; CHECK-LABEL: backedge:
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %n' is: overdefined
 ; CHECK-NEXT:    ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, -2147483647>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
 backedge:
   %iv.next = add nsw i32 %iv, 1
   %iv2.next = sub nsw i32 %iv2, 1
 ; CHECK:         ; LatticeVal for: '  %cont1 = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
 ; CHECK-NEXT:  %cont1 = icmp slt i32 %iv.next, 400
   %cont1 = icmp slt i32 %iv.next, 400
 ; CHECK-NEXT:    ; LatticeVal for: '  %cont2 = icmp sgt i32 %iv2.next, 0' in BB: '%backedge' is: overdefined
 ; CHECK-NEXT:  %cont2 = icmp sgt i32 %iv2.next, 0
   %cont2 = icmp sgt i32 %iv2.next, 0
-; CHECK-NEXT:    ; LatticeVal for: '  %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:    ; LatticeVal for: '  %cont = and i1 %cont1, %cont2' in BB: '%backedge' is: constantrange<-1, -1>
 ; CHECK-NEXT:  %cont = and i1 %cont1, %cont2
   %cont = and i1 %cont1, %cont2
   br i1 %cont, label %loop, label %exit
 
 exit:
   ret i8 0
 }
 

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 }