[InstCombine] try to determine "exact" for sdiv

[spatel]

Summary

If the divisor is a power-of-2 or negative-power-of-2 and the dividend is known to have >= trailing zeros than the divisor, the division is exact:
https://alive2.llvm.org/ce/z/UGBksM (general proof)
https://alive2.llvm.org/ce/z/D4yPS- (examples based on regression tests)

This isn't the most direct optimization (we could create ashr in these examples instead of relying on existing folds for exact divides), but it's possible that there's a more general constraint than just a pow2 divisor, so this might be extended in the future.

This should solve issue #58348.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1351

Side note, as you are working on division transforms. This has an obvious generalization to any nonneg / neg (https://alive2.llvm.org/ce/z/bYVnFG), and similar for neg / nonneg and neg / neg. It does require adding two negations in the general case, but I believe we consider that worthwhile to relax sdiv to udiv -- or at least we do the same transform based on range information in CVP.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1351

Thanks for pointing that out. I didn't know CVP did that transform. Looks like it was:
8d487668d09fb0e

And the instcombine change/enhancement was implemented/mentioned here:
0fdcca07ad2c0bdc2

Scanning over x86 instruction timings at least, it's not clear if unsigned div (DIV) is any faster than signed div (IDIV). So that seems questionable as an IR transform since it's not reversible in general, but if the negates are deleted/noise in most cases, then it's ok.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombinerImpl::visitSDiv(BinaryOperator &I) {
   if (match(&I, m_c_BinOp(
                     m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())),
                     m_Deferred(X)))) {
     Value *Cond = Builder.CreateIsNotNeg(X);
     return SelectInst::Create(Cond, ConstantInt::get(Ty, 1),
                               ConstantInt::getAllOnesValue(Ty));
   }
 
-  if (isKnownNonNegative(Op0, DL, 0, &AC, &I, &DT)) {
+  KnownBits KnownDividend = computeKnownBits(Op0, 0, &I);
+  if (!I.isExact() &&
+      (match(Op1, m_Power2(Op1C)) || match(Op1, m_NegatedPower2(Op1C))) &&
+      KnownDividend.countMinTrailingZeros() >= Op1C->countTrailingZeros()) {
+    I.setIsExact();
+    return &I;
+  }
+
+  if (KnownDividend.isNonNegative()) {
     // If both operands are unsigned, turn this into a udiv.
     if (isKnownNonNegative(Op1, DL, 0, &AC, &I, &DT)) {
       auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
       BO->setIsExact(I.isExact());
       return BO;
     }
 
     if (match(Op1, m_NegatedPower2())) {
       // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
       //                    -> -(X udiv (1 << C)) -> -(X u>> C)
       Constant *CNegLog2 = ConstantExpr::getExactLogBase2(
           ConstantExpr::getNeg(cast<Constant>(Op1)));
       Value *Shr = Builder.CreateLShr(Op0, CNegLog2, I.getName(), I.isExact());
       return BinaryOperator::CreateNeg(Shr);
     }
 

llvm/test/Transforms/InstCombine/sdiv-exact-by-negative-power-of-two.ll

 ; CHECK-NEXT:    ret <2 x i8> poison
 ;
   %div = sdiv exact <2 x i8> %x, <i8 -32, i8 undef>
   ret <2 x i8> %div
 }
 
 define i8 @prove_exact_with_high_mask(i8 %x, i8 %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask(
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -32
-; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], -4
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[D_NEG:%.*]] = and i8 [[A]], -8
+; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 0, [[D_NEG]]
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %a = and i8 %x, -32
   %d = sdiv i8 %a, -4
   ret i8 %d
 }
 
 define i8 @prove_exact_with_high_mask_limit(i8 %x, i8 %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_limit(
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -32
-; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], -32
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 5
+; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 0, [[A]]
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %a = and i8 %x, -32
   %d = sdiv i8 %a, -32
   ret i8 %d
 }
 
+; negative test - not enough low zeros in dividend
+
 define i8 @not_prove_exact_with_high_mask(i8 %x, i8 %y) {
 ; CHECK-LABEL: @not_prove_exact_with_high_mask(
 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -32
 ; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], -64
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %a = and i8 %x, -32
   %d = sdiv i8 %a, -64
   ret i8 %d
 }
 
 define <2 x i8> @prove_exact_with_high_mask_splat_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_splat_vec(
 ; CHECK-NEXT:    [[A:%.*]] = shl <2 x i8> [[X:%.*]], <i8 5, i8 5>
-; CHECK-NEXT:    [[D:%.*]] = sdiv <2 x i8> [[A]], <i8 -16, i8 -16>
+; CHECK-NEXT:    [[D_NEG:%.*]] = ashr exact <2 x i8> [[A]], <i8 4, i8 4>
+; CHECK-NEXT:    [[D:%.*]] = sub nsw <2 x i8> zeroinitializer, [[D_NEG]]
 ; CHECK-NEXT:    ret <2 x i8> [[D]]
 ;
   %a = shl <2 x i8> %x, <i8 5, i8 5>
   %d = sdiv <2 x i8> %a, <i8 -16, i8 -16>
   ret <2 x i8> %d
 }
 
+; TODO: Needs knownbits to handle arbitrary vector constants.
+
 define <2 x i8> @prove_exact_with_high_mask_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_vec(
 ; CHECK-NEXT:    [[A:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 2>
 ; CHECK-NEXT:    [[D:%.*]] = sdiv <2 x i8> [[A]], <i8 -8, i8 -4>
 ; CHECK-NEXT:    ret <2 x i8> [[D]]
 ;
   %a = shl <2 x i8> %x, <i8 3, i8 2>
   %d = sdiv <2 x i8> %a, <i8 -8, i8 -4>
   ret <2 x i8> %d
 }

llvm/test/Transforms/InstCombine/sdiv-exact-by-power-of-two.ll

 ;
   %shl = shl nsw i8 1, %y
   %div = sdiv i8 %x, %shl
   ret i8 %div
 }
 
 define i8 @prove_exact_with_high_mask(i8 %x, i8 %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask(
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -8
-; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], 4
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 2
+; CHECK-NEXT:    [[D:%.*]] = and i8 [[A]], -2
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %a = and i8 %x, -8
   %d = sdiv i8 %a, 4
   ret i8 %d
 }
 
 define i8 @prove_exact_with_high_mask_limit(i8 %x, i8 %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_limit(
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -8
-; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], 8
-; CHECK-NEXT:    ret i8 [[D]]
+; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 3
+; CHECK-NEXT:    ret i8 [[A]]
 ;
   %a = and i8 %x, -8
   %d = sdiv i8 %a, 8
   ret i8 %d
 }
 
+; negative test - not enough low zeros in dividend
+
 define i8 @not_prove_exact_with_high_mask(i8 %x, i8 %y) {
 ; CHECK-LABEL: @not_prove_exact_with_high_mask(
 ; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], -8
 ; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[A]], 16
 ; CHECK-NEXT:    ret i8 [[D]]
 ;
   %a = and i8 %x, -8
   %d = sdiv i8 %a, 16
   ret i8 %d
 }
 
 define <2 x i8> @prove_exact_with_high_mask_splat_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_splat_vec(
 ; CHECK-NEXT:    [[A:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 3>
-; CHECK-NEXT:    [[D:%.*]] = sdiv <2 x i8> [[A]], <i8 8, i8 8>
+; CHECK-NEXT:    [[D:%.*]] = ashr exact <2 x i8> [[A]], <i8 3, i8 3>
 ; CHECK-NEXT:    ret <2 x i8> [[D]]
 ;
   %a = shl <2 x i8> %x, <i8 3, i8 3>
   %d = sdiv <2 x i8> %a, <i8 8, i8 8>
   ret <2 x i8> %d
 }
 
+; TODO: Needs knownbits to handle arbitrary vector constants.
+
 define <2 x i8> @prove_exact_with_high_mask_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @prove_exact_with_high_mask_vec(
 ; CHECK-NEXT:    [[A:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 2>
 ; CHECK-NEXT:    [[D:%.*]] = sdiv <2 x i8> [[A]], <i8 8, i8 4>
 ; CHECK-NEXT:    ret <2 x i8> [[D]]
 ;
   %a = shl <2 x i8> %x, <i8 3, i8 2>
   %d = sdiv <2 x i8> %a, <i8 8, i8 4>
   ret <2 x i8> %d
 }