Use LVI to eliminate instructions during VP

[sehirst]

Summary

LVI gives us a ConstantRange which we can use to determine if the
results of div and shr instructions will always be zero. Similarly, we
can determine if one side of max/min instructions will always be
returned.

[sehirst]

Rebased and resolved conflict

[nikic]

See https://llvm.org/docs/TestingGuide.html#precommit-workflow-for-tests and the following section for testing requirements.

TBH the entire patch makes very little sense to me.

llvm/include/llvm/IR/ConstantRange.h

283

I think you re-invented the icmp() method here. CR1.icmp(ICmpInst::ICMP_UGT, CR2) etc is how you're supposed to write these.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

578

How does your code differ from the existing getPredicateAt() check above?

The tests you added already fold without your change.

[sehirst]

TBH the entire patch makes very little sense to me.

Thanks for the review. I think the main problem is that I was unaware of some key ConstantRange and LVI functionality, namely icmp() and getPredicateAt(), as you pointed out. Additionally, when I ported this patch from LLVM 15 to main I missed that some of the opportunities to remove instructions I was catching in this patch had already been caught. However, I ran my tests in this patch on main and found missed opportunities to remove sdiv, ashr, and lshr instructions.

I am re-working the patch to remove the duplication and follow the existing methods (e.g. the code to eliminate udiv's in expandUDivOrURem() using ConstantRange::icmp()).

I'll update this revision in a day or 2, including a fix for the build failure.

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

1098

LVI should be able to determine that this value is constant by itself -- does using LVI->getConstant(SDI, SDI) give the desired result?

llvm/include/llvm/IR/ConstantRange.h

public:
   bool isSingleElement() const { return getSingleElement() != nullptr; }
 
   /// Compare set size of this range with the range CR.
   bool isSizeStrictlySmallerThan(const ConstantRange &CR) const;
 
   /// Compare set size of this range with Value.
   bool isSizeLargerThan(uint64_t MaxSize) const;
 
+  /// Return true if all signed values in this range are less than all signed
+  /// values in Other.
+  bool isSignedStrictlyLowerThan(const ConstantRange &Other) const;
+
+  /// Return true if all unsigned values in this range are less than all
+  /// unsigned values in Other.
+  bool isUnsignedStrictlyLowerThan(const ConstantRange &Other) const;
+
+  /// Return true if all signed values in this range are greater than all signed
+  /// values in Other.
+  bool isSignedStrictlyHigherThan(const ConstantRange &Other) const;
+
+  /// Return true if all unsigned values in this range are greater than all
+  /// unsigned values in Other.
+  bool isUnsignedStrictlyHigherThan(const ConstantRange &Other) const;
+
   /// Return true if all values in this range are negative.
   bool isAllNegative() const;
 
   /// Return true if all values in this range are non-negative.
   bool isAllNonNegative() const;
 
   /// Return the largest unsigned value contained in the ConstantRange.
   APInt getUnsignedMax() const;

llvm/lib/IR/ConstantRange.cpp

ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
   // If this a full set, we need special handling to avoid needing an extra bit
   // to represent the size.
   if (isFullSet())
     return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
 
   return (Upper - Lower).ugt(MaxSize);
 }
 
+bool ConstantRange::isSignedStrictlyLowerThan(
+    const ConstantRange &Other) const {
+  assert(getBitWidth() == Other.getBitWidth());
+  if (isFullSet())
+    return false;
+  if (Other.isFullSet())
+    return false;
+  return getSignedMax().slt(Other.getSignedMin());
+}
+
+bool ConstantRange::isUnsignedStrictlyLowerThan(
+    const ConstantRange &Other) const {
+  assert(getBitWidth() == Other.getBitWidth());
+  if (isFullSet())
+    return false;
+  if (Other.isFullSet())
+    return false;
+  return getUnsignedMax().ult(Other.getUnsignedMin());
+}
+
+bool ConstantRange::isSignedStrictlyHigherThan(
+    const ConstantRange &Other) const {
+  assert(getBitWidth() == Other.getBitWidth());
+  if (isFullSet())
+    return false;
+  if (Other.isFullSet())
+    return false;
+  return getSignedMin().sgt(Other.getSignedMax());
+}
+
+bool ConstantRange::isUnsignedStrictlyHigherThan(
+    const ConstantRange &Other) const {
+  assert(getBitWidth() == Other.getBitWidth());
+  if (isFullSet())
+    return false;
+  if (Other.isFullSet())
+    return false;
+  return getUnsignedMin().ugt(Other.getUnsignedMax());
+}
+
 bool ConstantRange::isAllNegative() const {
   // Empty set is all negative, full set is not.
   if (isEmptySet())
     return true;
   if (isFullSet())
     return false;
 
   return !isUpperSignWrapped() && !Upper.isStrictlyPositive();

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 
 STATISTIC(NumPhis,      "Number of phis propagated");
 STATISTIC(NumPhiCommon, "Number of phis deleted via common incoming value");
 STATISTIC(NumSelects,   "Number of selects propagated");
 STATISTIC(NumMemAccess, "Number of memory access targets propagated");
 STATISTIC(NumCmps,      "Number of comparisons propagated");
 STATISTIC(NumReturns,   "Number of return values propagated");
 STATISTIC(NumDeadCases, "Number of switch cases removed");
+STATISTIC(NumDivEliminated, "Number of sdivs/udivs replaced with zero");
 STATISTIC(NumSDivSRemsNarrowed,
           "Number of sdivs/srems whose width was decreased");
 STATISTIC(NumSDivs,     "Number of sdiv converted to udiv");
 STATISTIC(NumUDivURemsNarrowed,
           "Number of udivs/urems whose width was decreased");
 STATISTIC(NumAShrsConverted, "Number of ashr converted to lshr");
 STATISTIC(NumAShrsRemoved, "Number of ashr removed");
+STATISTIC(NumLShrsRemoved, "Number of lshr removed");
 STATISTIC(NumSRems,     "Number of srem converted to urem");
 STATISTIC(NumSExt,      "Number of sext converted to zext");
 STATISTIC(NumSICmps,    "Number of signed icmp preds simplified to unsigned");
 STATISTIC(NumAnd,       "Number of ands removed");
 STATISTIC(NumNW,        "Number of no-wrap deductions");
 STATISTIC(NumNSW,       "Number of no-signed-wrap deductions");
 STATISTIC(NumNUW,       "Number of no-unsigned-wrap deductions");
 STATISTIC(NumAddNW,     "Number of no-wrap deductions for add");
static bool processAbsIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI) {
   return true;
 }
 
 // See if this min/max intrinsic always picks it's one specific operand.
 static bool processMinMaxIntrinsic(MinMaxIntrinsic *MM, LazyValueInfo *LVI) {
   CmpInst::Predicate Pred = CmpInst::getNonStrictPredicate(MM->getPredicate());
   LazyValueInfo::Tristate Result = LVI->getPredicateAt(
       Pred, MM->getLHS(), MM->getRHS(), MM, /*UseBlockValue=*/true);
-  if (Result == LazyValueInfo::Unknown)
-    return false;
-
+  if (Result != LazyValueInfo::Unknown) {
     ++NumMinMax;
     MM->replaceAllUsesWith(MM->getOperand(!Result));
     MM->eraseFromParent();
     return true;
   }
 
+  Value *LHS = MM->getArgOperand(0);
+  Value *RHS = MM->getArgOperand(1);
+  Value *AlwaysThisSide = nullptr;
+
+  if (MM->getType()->isVectorTy())
+    return false;
+
+  ConstantRange CRLHS = LVI->getConstantRange(LHS, MM);
+  // No need to calculate CRRHS if CRLHS one isFullSet
+  if (CRLHS.isFullSet())
+    return false;
+  ConstantRange CRRHS = LVI->getConstantRange(RHS, MM);
+
+  // Use constant range to see if the max/min always picks one operand.
+  switch (MM->getIntrinsicID()) {
+  case Intrinsic::smax:
+    if (CRLHS.isSignedStrictlyHigherThan(CRRHS))
+      AlwaysThisSide = LHS;
+    else if (CRRHS.isSignedStrictlyHigherThan(CRLHS))
+      AlwaysThisSide = RHS;
+    break;
+  case Intrinsic::umax:
+    if (CRLHS.isUnsignedStrictlyHigherThan(CRRHS))
+      AlwaysThisSide = LHS;
+    else if (CRRHS.isUnsignedStrictlyHigherThan(CRLHS))
+      AlwaysThisSide = RHS;
+    break;
+  case Intrinsic::smin:
+    if (CRLHS.isSignedStrictlyLowerThan(CRRHS))
+      AlwaysThisSide = LHS;
+    else if (CRRHS.isSignedStrictlyLowerThan(CRLHS))
+      AlwaysThisSide = RHS;
+    break;
+  case Intrinsic::umin:
+    if (CRLHS.isUnsignedStrictlyLowerThan(CRRHS))
+      AlwaysThisSide = LHS;
+    else if (CRRHS.isUnsignedStrictlyLowerThan(CRLHS))
+      AlwaysThisSide = RHS;
+    break;
+  default:
+    llvm_unreachable("Invalid Intrinsic");
+  }
+  if (AlwaysThisSide) {
+    ++NumMinMax;
+    MM->replaceAllUsesWith(AlwaysThisSide);
+    MM->eraseFromParent();
+    return true;
+  }
+  return false;
+}
+
 // Rewrite this with.overflow intrinsic as non-overflowing.
 static bool processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) {
   IRBuilder<> B(WO);
   Instruction::BinaryOps Opcode = WO->getBinaryOp();
   bool NSW = WO->isSigned();
   bool NUW = !WO->isSigned();
 
   Value *NewOp =
if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
     if (BinOp->getOpcode() == Instruction::UDiv)
       BinOp->setIsExact(Instr->isExact());
 
   Instr->replaceAllUsesWith(Zext);
   Instr->eraseFromParent();
   return true;
 }
 
+/// If the largest absolute value in the constant range of a dividend is less
+/// than the constant divisor, the quotient must be zero.
+static bool isDivResultZero(BinaryOperator *Div, ConstantInt *Divisor,
+                            LazyValueInfo *LVI) {
+  assert(Div->getOpcode() == Instruction::UDiv ||
+         Div->getOpcode() == Instruction::SDiv);
+
+  ConstantRange CR = LVI->getConstantRange(Div->getOperand(0), Div);
+  APInt upperBound, Quotient;
+  switch (Div->getOpcode()) {
+  case Instruction::UDiv:
+    upperBound = CR.getUnsignedMax();
+    Quotient = upperBound.udiv(Divisor->getValue());
+    break;
+  case Instruction::SDiv: {
+    APInt SignedMax = CR.getSignedMax();
+    APInt SignedMin = CR.getSignedMin();
+    upperBound = SignedMax.abs().ugt(SignedMin.abs()) ? SignedMax : SignedMin;
+    Quotient = upperBound.sdiv(Divisor->getValue());
+  } break;
+  default:
+    llvm_unreachable("Invalid Div Opcode");
+  }
+  if (Quotient == APInt::getZero(Divisor->getBitWidth())) {
+    return true;
+  }
+  return false;
+}
+
+/// Try to replace udiv with zero, otherwise try to shrink udiv/urem's width
+/// down to the smallest power of two that's sufficient to contain its operands.
 static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
   assert(Instr->getOpcode() == Instruction::UDiv ||
          Instr->getOpcode() == Instruction::URem);
   if (Instr->getType()->isVectorTy())
     return false;
 
+  ConstantInt *CInt;
+  if (Instr->getOpcode() == Instruction::UDiv &&
+      (CInt = dyn_cast<ConstantInt>(Instr->getOperand(1)))) {
+    if (isDivResultZero(Instr, CInt, LVI)) {
+      LLVM_DEBUG(dbgs() << *Instr
+                        << " will always be zero. Replacing uses with zero.\n");
+      Instr->replaceAllUsesWith(Constant::getNullValue(Instr->getType()));
+      Instr->eraseFromParent();
+      ++NumDivEliminated;
+      return true;
+    }
+  }
+
   ConstantRange XCR = LVI->getConstantRangeAtUse(Instr->getOperandUse(0));
   ConstantRange YCR = LVI->getConstantRangeAtUse(Instr->getOperandUse(1));
   if (expandUDivOrURem(Instr, XCR, YCR))
     return true;
 
   return narrowUDivOrURem(Instr, XCR, YCR);
 }
 
static bool processSRem(BinaryOperator *SDI, const ConstantRange &LCR,
   SDI->eraseFromParent();
 
   // Try to simplify our new urem.
   processUDivOrURem(URem, LVI);
 
   return true;
 }
 
-/// See if LazyValueInfo's ability to exploit edge conditions or range
-/// information is sufficient to prove the signs of both operands of this SDiv.
-/// If this is the case, replace the SDiv with a UDiv. Even for local
-/// conditions, this can sometimes prove conditions instcombine can't by
-/// exploiting range information.
+/// Try to eliminate SDiv, otherwise see if LazyValueInfo's ability to exploit
+/// edge conditions or range information is sufficient to prove the signs of
+/// both operands of this SDiv. If this is the case, replace the SDiv with a
+/// UDiv. Even for local conditions, this can sometimes prove conditions
+/// instcombine can't by exploiting range information.
 static bool processSDiv(BinaryOperator *SDI, const ConstantRange &LCR,
                         const ConstantRange &RCR, LazyValueInfo *LVI) {
   assert(SDI->getOpcode() == Instruction::SDiv);
   assert(!SDI->getType()->isVectorTy());
 
+  ConstantInt *CInt;
+  if ((CInt = dyn_cast<ConstantInt>(SDI->getOperand(1)))) {
+    if (isDivResultZero(SDI, CInt, LVI)) {
+      LLVM_DEBUG(dbgs() << *SDI
+                        << " will always be zero. Replacing uses with zero.\n");
+      SDI->replaceAllUsesWith(Constant::getNullValue(SDI->getType()));
+      SDI->eraseFromParent();
+      ++NumDivEliminated;
+      return true;
+    }
+  }
+
   struct Operand {
     Value *V;
     Domain D;
   };
   std::array<Operand, 2> Ops = {{{SDI->getOperand(0), getDomain(LCR)},
                                  {SDI->getOperand(1), getDomain(RCR)}}};
   if (Ops[0].D == Domain::Unknown || Ops[1].D == Domain::Unknown)
     return false;
static bool processSDivOrSRem(BinaryOperator *Instr, LazyValueInfo *LVI) {
   if (Instr->getOpcode() == Instruction::SRem) {
     if (processSRem(Instr, LCR, RCR, LVI))
       return true;
   }
 
   return narrowSDivOrSRem(Instr, LCR, RCR);
 }
 
+static bool processLShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
+  if (SDI->getType()->isVectorTy())
+    return false;
+
+  ConstantRange LRange = LVI->getConstantRange(SDI->getOperand(0), SDI);
+
+  if (auto *CInt = dyn_cast<ConstantInt>(SDI->getOperand(1))) {
+    APInt UpperBound = LRange.getUnsignedMax();
+    if (UpperBound.lshr(CInt->getValue()) ==
+        APInt::getZero(LRange.getBitWidth())) {
+      LLVM_DEBUG(dbgs() << *SDI
+                        << " will always be zero. Replace uses with zero.\n");
+      ++NumLShrsRemoved;
+      SDI->replaceAllUsesWith(Constant::getNullValue(SDI->getType()));
+      SDI->eraseFromParent();
+      return true;
+    }
+  }
+  return false;
+}
+
 static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
   if (SDI->getType()->isVectorTy())
     return false;
 
   ConstantRange LRange =
       LVI->getConstantRangeAtUse(SDI->getOperandUse(0), /*UndefAllowed*/ false);
   unsigned OrigWidth = SDI->getType()->getIntegerBitWidth();
   ConstantRange NegOneOrZero =
       ConstantRange(APInt(OrigWidth, (uint64_t)-1, true), APInt(OrigWidth, 1));
   if (NegOneOrZero.contains(LRange)) {
     // ashr of -1 or 0 never changes the value, so drop the whole instruction
     ++NumAShrsRemoved;
     SDI->replaceAllUsesWith(SDI->getOperand(0));
     SDI->eraseFromParent();
     return true;
   }
 
   if (!LRange.isAllNonNegative())
     return false;
 
+  ConstantInt *CInt;
+  if ((CInt = dyn_cast<ConstantInt>(SDI->getOperand(1))) &&
+      LRange.isAllNonNegative()) {
+    APInt UpperBound = LRange.getUnsignedMax();
+    if (UpperBound.ashr(CInt->getValue()) ==
+        APInt::getZero(LRange.getBitWidth())) {
+      LLVM_DEBUG(dbgs() << *SDI
+                        << " will always be zero. Replace uses with zero.\n");
+      ++NumAShrsRemoved;
+      SDI->replaceAllUsesWith(Constant::getNullValue(SDI->getType()));
+      SDI->eraseFromParent();
+      return true;
+    }
+  }
+
   ++NumAShrsConverted;
   auto *BO = BinaryOperator::CreateLShr(SDI->getOperand(0), SDI->getOperand(1),
                                         "", SDI);
   BO->takeName(SDI);
   BO->setDebugLoc(SDI->getDebugLoc());
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
   SDI->eraseFromParent();
for (Instruction &II : llvm::make_early_inc_range(*BB)) {
         break;
       case Instruction::UDiv:
       case Instruction::URem:
         BBChanged |= processUDivOrURem(cast<BinaryOperator>(&II), LVI);
         break;
       case Instruction::AShr:
         BBChanged |= processAShr(cast<BinaryOperator>(&II), LVI);
         break;
+      case Instruction::LShr:
+        BBChanged |= processLShr(cast<BinaryOperator>(&II), LVI);
+        break;
       case Instruction::SExt:
         BBChanged |= processSExt(cast<SExtInst>(&II), LVI);
         break;
       case Instruction::Add:
       case Instruction::Sub:
       case Instruction::Mul:
       case Instruction::Shl:
         BBChanged |= processBinOp(cast<BinaryOperator>(&II), LVI);

llvm/test/Transforms/CorrelatedValuePropagation/ashr.ll

 
 false:
   br label %exit
 
 exit:
   %p = phi i32 [ 2, %true.1 ], [ 4, %true.2], [ undef, %false ]
   %r = ashr i32 %p, 1
   ret i32 %r
+
+; check that an ashr of more bits than operand is optimized away
+; CHECK-LABEL: @test9
+define void @test9() {
+; CHECK-NOT: ashr
+  %shr = ashr i8 127, 7
+; CHECK: %add = add nuw nsw i8 0, 1
+  %add = add i8 %shr, 1
+  ret void
 }

llvm/test/Transforms/CorrelatedValuePropagation/lshr.ll

+; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s
+
+; Check that debug locations are preserved. For more info see:
+;   https://llvm.org/docs/SourceLevelDebugging.html#fixing-errors
+; RUN: opt < %s -enable-debugify -passes=correlated-propagation -S 2>&1 | \
+; RUN:   FileCheck %s -check-prefix=DEBUG
+; DEBUG: CheckModuleDebugify: PASS
+
+; check that an lshr of fewer bits than operand is not optimized away
+; CHECK-LABEL: @test1
+define void @test1() {
+  %shr = lshr i8 255, 7
+; CHECK: %shr = lshr i8 -1, 7
+  ret void
+}
+
+; check that an lshr of more bits than operand is optimized away
+; CHECK-LABEL: @test2
+define void @test2() {
+; CHECK-NOT: lshr
+  %shr = lshr i8 127, 7
+; CHECK: %add = add nuw nsw i8 0, 1
+  %add = add i8 %shr, 1
+  ret void
+}

llvm/test/Transforms/CorrelatedValuePropagation/min-max.ll

 ; CHECK-NEXT:    [[R:%.*]] = call i8 @llvm.smax.i8(i8 [[X]], i8 42)
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %lim = icmp sle i8 %x, 43
   call void @llvm.assume(i1 %lim)
   %r = call i8 @llvm.smax(i8 %x, i8 42)
   ret i8 %r
 }
+
+; CHECK-LABEL: @test20
+define void @test20() {
+; CHECK-NOT: smax
+  %max = call i8 @llvm.smax(i8 1, i8 255)
+; CHECK: %add = add nuw nsw i8 1, 3
+  %add = add i8 %max, 3
+  ret void
+}
+
+; CHECK-LABEL: @test21
+define void @test21() {
+; CHECK-NOT: smin
+  %min = call i8 @llvm.smin(i8 1, i8 255)
+; CHECK: %add = add nsw i8 -1, 3
+  %add = add i8 %min, 3
+  ret void
+}
+
+; CHECK-LABEL: @test22
+define void @test22() {
+; CHECK-NOT: umax
+  %max = call i8 @llvm.umax(i8 1, i8 255)
+; CHECK: %add = add nsw i8 -1, 3
+  %add = add i8 %max, 3
+  ret void
+}
+
+; CHECK-LABEL: @test23
+define void @test23() {
+; CHECK-NOT: umin
+  %min = call i8 @llvm.umin(i8 1, i8 255)
+; CHECK: %add = add nuw nsw i8 1, 3
+  %add = add i8 %min, 3
+  ret void
+}

llvm/test/Transforms/CorrelatedValuePropagation/sdiv.ll

entry:
   %c2 = icmp sle i64 %y, 32767
   call void @llvm.assume(i1 %c2)
   %c3 = icmp sge i64 %y, -32768
   call void @llvm.assume(i1 %c3)
 
   %div = sdiv exact i64 %x, %y
   ret i64 %div
 }
+
+; CHECK-LABEL: @test23
+define void @test23() {
+; CHECK-NOT: sdiv
+  %div = sdiv i64 -1, 2
+; CHECK: %add = add nuw nsw i64 0, 1
+  %add = add i64 %div, 1
+  ret void
+}

llvm/test/Transforms/CorrelatedValuePropagation/udiv.ll

 bb:
 ; CHECK: udiv i8
   %div = sdiv i32 %n, 100
   br label %exit
 
 exit:
   ret void
 }
+
+; CHECK-LABEL: @test7
+define void @test7() {
+if.cond:
+  %cmp = icmp slt i64 1, 2
+  br i1 %cmp, label %if, label %else
+
+if:
+  %x = add i64 0, 1
+  br label %if.end
+
+else:
+  %y = add i64 1, 1
+  br label %if.end
+
+if.end:
+  %phi = phi i64 [ %x, %if ], [ %y, %else ]
+; CHECK-NOT: udiv
+  %div = udiv i64 %phi, 3
+; CHECK: %add = add nuw nsw i64 0, 1
+  %add = add nuw nsw i64 %div, 1
+  ret void
+}