[LVI][CVP] Add support for urem, srem and sdiv

[nikic]

Summary

The underlying ConstantRange functionality has been added in D60952, D61207 and D61238, this just exposes it for LVI.

I'm switching the code from using a whitelist to a blacklist, as we're down to one unsupported operation here (xor) and writing it this way seems more obvious :)

[reames]

llvm/lib/IR/ConstantRange.cpp

792 ↗

(On Diff #202783)

If I understand the context of the patch, xor is the only case not handled right? If so, then I'd strongly prefer to see a case handled for xor (even if that's simply return full). The contract of "supports all binops but xor" is not a great API for this function.

[nikic]

Remove ConstantRange::binaryOp() assertion.

[nikic]

llvm/lib/IR/ConstantRange.cpp

792 ↗

(On Diff #202783)

Xor is the only unsupported integer binop. There are more unsupported float binops which aren't relevant to LVI though.

I've restored the code to returning a conservative result now.

[reames]

LGTM

llvm/lib/Analysis/LazyValueInfo.cpp

 }
 
 bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
                                                 BinaryOperator *BO,
                                                 BasicBlock *BB) {
 
   assert(BO->getOperand(0)->getType()->isSized() &&
          "all operands to binary operators are sized");
+  if (BO->getOpcode() == Instruction::Xor) {
+    // Xor is the only operation not supported by ConstantRange::binaryOp().
+    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
+                      << "' - overdefined (unknown binary operator).\n");
+    BBLV = ValueLatticeElement::getOverdefined();
+    return true;
+  }
 
-  // Filter out operators we don't know how to reason about before attempting to
-  // recurse on our operand(s).  This can cut a long search short if we know
-  // we're not going to be able to get any useful information anyways.
-  switch (BO->getOpcode()) {
-  case Instruction::Add:
-  case Instruction::Sub:
-  case Instruction::Mul:
-  case Instruction::UDiv:
-  case Instruction::Shl:
-  case Instruction::LShr:
-  case Instruction::AShr:
-  case Instruction::And:
-  case Instruction::Or:
-    return solveBlockValueBinaryOpImpl(BBLV, BO, BB,
-        [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
-          return CR1.binaryOp(BO->getOpcode(), CR2);
-        });
-  default:
-    // Unhandled instructions are overdefined.
-    LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
-                      << "' - overdefined (unknown binary operator).\n");
-    BBLV = ValueLatticeElement::getOverdefined();
-    return true;
-  };
 }
 
 bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(
     ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB) {
   return solveBlockValueBinaryOpImpl(BBLV, WO, BB,
       [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.binaryOp(WO->getBinaryOp(), CR2);
       });

llvm/test/Transforms/CorrelatedValuePropagation/basic.ll

 
 define i1 @urem_unknown(i32 %a) {
 ; CHECK-LABEL: @urem_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[UREM:%.*]] = urem i32 [[A:%.*]], 30
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[UREM]], 30
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %urem = urem i32 %a, 30
   %cmp = icmp ult i32 %urem, 30
   br label %exit
 exit:
   ret i1 %cmp
 }
 
 define i1 @srem_unknown(i32 %a) {
 ; CHECK-LABEL: @srem_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SREM:%.*]] = srem i32 [[A:%.*]], 30
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[SREM]], 30
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[SREM]], -30
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
-; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %srem = srem i32 %a, 30
   %cmp1 = icmp slt i32 %srem, 30
   %cmp2 = icmp sgt i32 %srem, -30
   br i1 undef, label %exit1, label %exit2
 exit1:
   ret i1 %cmp1
 exit2:
   ret i1 %cmp2
 }
 
 define i1 @sdiv_unknown(i32 %a) {
 ; CHECK-LABEL: @sdiv_unknown(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[SREM:%.*]] = sdiv i32 [[A:%.*]], 123
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[SREM]], 17459217
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[SREM]], -17459217
 ; CHECK-NEXT:    br i1 undef, label [[EXIT1:%.*]], label [[EXIT2:%.*]]
 ; CHECK:       exit1:
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       exit2:
-; CHECK-NEXT:    ret i1 [[CMP2]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %srem = sdiv i32 %a, 123
   %cmp1 = icmp slt i32 %srem, 17459217
   %cmp2 = icmp sgt i32 %srem, -17459217
   br i1 undef, label %exit1, label %exit2
 exit1:
   ret i1 %cmp1