[LVI][CVP] LazyValueInfoImpl::solveBlockValueBinaryOp(): use no-wrap flags from `add` op

[lebedev.ri]

Summary

This was suggested in https://reviews.llvm.org/D69277#1717210
In this form (this is what was suggested, right?), the results aren't staggering
(especially since given LVI cross-block focus)
this catch some things (as per test-suite), but not too much:

statistic	old	new	delta	% change
correlated-value-propagation.NumAddNSW	4981	4982	1	0.0201%
correlated-value-propagation.NumAddNW	12125	12126	1	0.0082%
correlated-value-propagation.NumCmps	1199	1202	3	0.2502%
correlated-value-propagation.NumDeadCases	112	111	-1	-0.8929%
correlated-value-propagation.NumMulNSW	275	278	3	1.0909%
correlated-value-propagation.NumMulNUW	1323	1326	3	0.2268%
correlated-value-propagation.NumMulNW	1598	1604	6	0.3755%
correlated-value-propagation.NumNSW	7158	7167	9	0.1257%
correlated-value-propagation.NumNUW	13304	13310	6	0.0451%
correlated-value-propagation.NumNW	20462	20477	15	0.0733%
correlated-value-propagation.NumOverflows	4	7	3	75.0000%
correlated-value-propagation.NumPhis	15366	15381	15	0.0976%
correlated-value-propagation.NumSExt	6273	6277	4	0.0638%
correlated-value-propagation.NumShlNSW	1172	1171	-1	-0.0853%
correlated-value-propagation.NumShlNUW	2793	2794	1	0.0358%
correlated-value-propagation.NumSubNSW	730	736	6	0.8219%
correlated-value-propagation.NumSubNUW	2044	2046	2	0.0978%
correlated-value-propagation.NumSubNW	2774	2782	8	0.2884%
instcount.NumAddInst	277586	277569	-17	-0.0061%
instcount.NumAndInst	66056	66054	-2	-0.0030%
instcount.NumBrInst	709147	709146	-1	-0.0001%
instcount.NumCallInst	528579	528576	-3	-0.0006%
instcount.NumExtractValueInst	18307	18301	-6	-0.0328%
instcount.NumOrInst	102660	102665	5	0.0049%
instcount.NumPHIInst	318008	318007	-1	-0.0003%
instcount.NumSelectInst	46373	46370	-3	-0.0065%
instcount.NumSExtInst	79496	79488	-8	-0.0101%
instcount.NumShlInst	40654	40657	3	0.0074%
instcount.NumTruncInst	62251	62249	-2	-0.0032%
instcount.NumZExtInst	68211	68221	10	0.0147%
instcount.TotalBlocks	843910	843909	-1	-0.0001%
instcount.TotalInsts	7387448	7387423	-25	-0.0003%

[nikic]

LGTM

Thanks for looking into this! I think we should definitely do this change as the functionality already exists, but based on the numbers, it probably doesn't make sense to invest in NoWrap implementations of other operators unless we also need them for something else (SCEV was the original motivation here).

llvm/include/llvm/IR/ConstantRange.h

330

nit: an left hand side -> a left hand side

335

I'd swap the last two arguments here to match the order of makeGuaranteedNoWrapRegion and addWithNoWrap, which both have NoWrapFlags after the range.

[lebedev.ri]

In D69321#1718474, @nikic wrote:

LGTM

Thanks for looking into this!

Thank you for the review.

I think we should definitely do this change as the functionality already exists, but based on the numbers,
it probably doesn't make sense to invest in NoWrap implementations of other operators
unless we also need them for something else (SCEV was the original motivation here).

It's indeed hard to say whether handling of other three OBO will be worth it,
without actually implementing everything and measuring..

llvm/include/llvm/IR/ConstantRange.h

public:
 
   /// Return a new range representing the possible values resulting
   /// from an application of the specified binary operator to an left hand side
   /// of this range and a right hand side of \p Other.
   ConstantRange binaryOp(Instruction::BinaryOps BinOp,
                          const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
+  /// from an application of the specified overflowing binary operator to a
+  /// left hand side of this range and a right hand side of \p Other given
+  /// the provided knowledge about lack of wrapping \p NoWrapKind.
+  ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp,
+                                    const ConstantRange &Other,
+                                    unsigned NoWrapKind) const;
+
+  /// Return a new range representing the possible values resulting
   /// from an addition of a value in this range and a value in \p Other.
   ConstantRange add(const ConstantRange &Other) const;
 
   /// Return a new range representing the possible values resulting
   /// from an addition with wrap type \p NoWrapKind of a value in this
   /// range and a value in \p Other.
   /// If the result range is disjoint, the preferred range is determined by the
   /// \p PreferredRangeType.

llvm/lib/Analysis/LazyValueInfo.cpp

bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
   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;
   }
 
-  return solveBlockValueBinaryOpImpl(BBLV, BO, BB,
-      [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
+  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) {
+    unsigned NoWrapKind = 0;
+    if (OBO->hasNoUnsignedWrap())
+      NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
+    if (OBO->hasNoSignedWrap())
+      NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap;
+
+    return solveBlockValueBinaryOpImpl(
+        BBLV, BO, BB,
+        [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
+          return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
+        });
+  }
+
+  return solveBlockValueBinaryOpImpl(
+      BBLV, BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.binaryOp(BO->getOpcode(), CR2);
       });
 }
 
 bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(
     ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB) {
   return solveBlockValueBinaryOpImpl(BBLV, WO, BB,
       [WO](const ConstantRange &CR1, const ConstantRange &CR2) {

llvm/lib/IR/ConstantRange.cpp

ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
   case Instruction::FMul:
     return multiply(Other);
   default:
     // Conservatively return getFull set.
     return getFull();
   }
 }
 
+ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,
+                                                 const ConstantRange &Other,
+                                                 unsigned NoWrapKind) const {
+  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
+
+  switch (BinOp) {
+  case Instruction::Add:
+    return addWithNoWrap(Other, NoWrapKind);
+  default:
+    // Don't know about this Overflowing Binary Operation.
+    // Conservatively fallback to plain binop handling.
+    return binaryOp(BinOp, Other);
+  }
+}
+
 ConstantRange
 ConstantRange::add(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
   if (isFullSet() || Other.isFullSet())
     return getFull();
 
   APInt NewLower = getLower() + Other.getLower();

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[A:%.*]], 0
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[B:%.*]], 0
 ; CHECK-NEXT:    [[BR:%.*]] = and i1 [[CMP0]], [[CMP1]]
 ; CHECK-NEXT:    br i1 [[BR]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[A]], [[B]]
 ; CHECK-NEXT:    br label [[CONT:%.*]]
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = icmp sge i32 [[ADD]], 0
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[IV:%.*]] = phi i1 [ true, [[BEGIN:%.*]] ], [ [[RES]], [[CONT]] ]
-; CHECK-NEXT:    ret i1 [[IV]]
+; CHECK-NEXT:    ret i1 true
 ;
 begin:
   %cmp0 = icmp sge i32 %a, 0
   %cmp1 = icmp sge i32 %b, 0
   %br = and i1 %cmp0, %cmp1
   br i1 %br, label %bb, label %exit
 
 bb:

 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:  begin:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[A:%.*]], -256
 ; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    br label [[CONT:%.*]]
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES:%.*]] = icmp uge i32 [[ADD]], -256
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[IV:%.*]] = phi i1 [ true, [[BEGIN:%.*]] ], [ [[RES]], [[CONT]] ]
-; CHECK-NEXT:    ret i1 [[IV]]
+; CHECK-NEXT:    ret i1 true
 ;
 begin:
   %cmp = icmp uge i32 %a, 4294967040
   br i1 %cmp, label %bb, label %exit
 
 bb:
   %add = add nuw i32 %a, %b
   br label %cont