[InstCombine] 'Rem' formation from subtraction of rounded-down value (PR42673)

[lebedev.ri]

Summary

We can fold
x - ((x / y) * y)
to
x % y

https://rise4fun.com/Alive/8Rp

To be noted, we also prefer x - (x % y) to (x / y) * y,
and these tests show that we miss this transform
if division is not one-use. The caveat is that we could
still transform if we know that there already is (x % y);
but unlike back-end's SelectionDAG::getNodeIfExists(),
i'm not sure how to nicely check that in middle-end.

https://godbolt.org/z/rWjNl4
https://bugs.llvm.org/show_bug.cgi?id=42673

[lebedev.ri]

This is wrong solution.
Superseded by https://reviews.llvm.org/D65298

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
 
   // If we have p - gep(p, ...)  then we have to negate the result.
   if (Swapped)
     Result = Builder.CreateNeg(Result, "diff.neg");
 
   return Builder.CreateIntCast(Result, Ty, true);
 }
 
+/// If we have:
+///   x - ((x / y) * y)
+/// We can transform it into:
+///   x % y
+static Instruction *
+produceRemFromSubtractionOfRoundeddownValue(BinaryOperator &I) {
+  assert(I.getOpcode() == Instruction::Sub && "Must start from 'sub'.");
+
+  Value *X = I.getOperand(0);
+  Value *XroundedDownToMultipleOfY = I.getOperand(1);
+
+  Value *Y;
+  Instruction *Div;
+  // Look for  ((x / y) * y)
+  if (!match(XroundedDownToMultipleOfY,
+             m_c_Mul(m_CombineAnd(m_IDiv(m_Specific(X), m_Value(Y)),
+                                  m_Instruction(Div)),
+                     m_Deferred(Y))))
+    return nullptr;
+
+  return Div->getOpcode() == Instruction::SDiv
+             ? BinaryOperator::CreateSRem(X, Y, I.getName())
+             : BinaryOperator::CreateURem(X, Y, I.getName());
+}
+
 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
   if (Value *V = SimplifySubInst(I.getOperand(0), I.getOperand(1),
                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                                  SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
if (SelectPatternResult::isMinOrMax(SPF) &&
         if (NotA == Op0)
           return BinaryOperator::CreateSub(Not, A);
         else
           return BinaryOperator::CreateSub(A, Not);
       }
     }
   }
 
+  if (Instruction *Ext = produceRemFromSubtractionOfRoundeddownValue(I))
+    return Ext;
+
   // Optimize pointer differences into the same array into a size.  Consider:
   //  &A[10] - &A[0]: we should compile this to "10".
   Value *LHSOp, *RHSOp;
   if (match(Op0, m_PtrToInt(m_Value(LHSOp))) &&
       match(Op1, m_PtrToInt(m_Value(RHSOp))))
     if (Value *Res = OptimizePointerDifference(LHSOp, RHSOp, I.getType()))
       return replaceInstUsesWith(I, Res);
 

llvm/test/Transforms/InstCombine/srem-via-sdiv-mul-sub.ll

 
 declare void @use8(i8)
 declare void @use2xi8(<2 x i8>)
 
 define i8 @t0_basic(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t0_basic(
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[DIV]], [[Y]]
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %div = sdiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %div, %y
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem
 }
 
 define <2 x i8> @t1_vector(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t1_vector(
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i8> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use2xi8(<2 x i8> [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul <2 x i8> [[DIV]], [[Y]]
-; CHECK-NEXT:    [[REM:%.*]] = sub <2 x i8> [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = srem <2 x i8> [[X]], [[Y]]
 ; CHECK-NEXT:    ret <2 x i8> [[REM]]
 ;
   %div = sdiv <2 x i8> %x, %y
   call void @use2xi8(<2 x i8> %div)
   %roundXdownToMultipleOfY = mul <2 x i8> %div, %y
   %rem = sub <2 x i8> %x, %roundXdownToMultipleOfY
   ret <2 x i8> %rem
 }
 
 ; Extra use
 
 define i8 @t4_extrause(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t4_extrause(
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
 ; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[DIV]], [[Y]]
 ; CHECK-NEXT:    call void @use8(i8 [[ROUNDXDOWNTOMULTIPLEOFY]])
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %div = sdiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %div, %y
   call void @use8(i8 %roundXdownToMultipleOfY)
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem
 }
 
 ; Commutativity
 
 declare i8 @gen8()
 
 define i8 @t5_commutative(i8 %x) {
 ; CHECK-LABEL: @t5_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i8 [[X:%.*]], [[Y]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[Y]], [[DIV]]
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %y = call i8 @gen8()
   %div = sdiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %y, %div ; swapped
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem

llvm/test/Transforms/InstCombine/urem-via-udiv-mul-sub.ll

 
 declare void @use8(i8)
 declare void @use2xi8(<2 x i8>)
 
 define i8 @t0_basic(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t0_basic(
 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[DIV]], [[Y]]
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %div = udiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %div, %y
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem
 }
 
 define <2 x i8> @t1_vector(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @t1_vector(
 ; CHECK-NEXT:    [[DIV:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use2xi8(<2 x i8> [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul <2 x i8> [[DIV]], [[Y]]
-; CHECK-NEXT:    [[REM:%.*]] = sub <2 x i8> [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = urem <2 x i8> [[X]], [[Y]]
 ; CHECK-NEXT:    ret <2 x i8> [[REM]]
 ;
   %div = udiv <2 x i8> %x, %y
   call void @use2xi8(<2 x i8> %div)
   %roundXdownToMultipleOfY = mul <2 x i8> %div, %y
   %rem = sub <2 x i8> %x, %roundXdownToMultipleOfY
   ret <2 x i8> %rem
 }
 
 ; Extra use
 
 define i8 @t4_extrause(i8 %x, i8 %y) {
 ; CHECK-LABEL: @t4_extrause(
 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
 ; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[DIV]], [[Y]]
 ; CHECK-NEXT:    call void @use8(i8 [[ROUNDXDOWNTOMULTIPLEOFY]])
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %div = udiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %div, %y
   call void @use8(i8 %roundXdownToMultipleOfY)
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem
 }
 
 ; Commutativity
 
 declare i8 @gen8()
 
 define i8 @t5_commutative(i8 %x) {
 ; CHECK-LABEL: @t5_commutative(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @gen8()
 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[X:%.*]], [[Y]]
 ; CHECK-NEXT:    call void @use8(i8 [[DIV]])
-; CHECK-NEXT:    [[ROUNDXDOWNTOMULTIPLEOFY:%.*]] = mul i8 [[Y]], [[DIV]]
-; CHECK-NEXT:    [[REM:%.*]] = sub i8 [[X]], [[ROUNDXDOWNTOMULTIPLEOFY]]
+; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %y = call i8 @gen8()
   %div = udiv i8 %x, %y
   call void @use8(i8 %div)
   %roundXdownToMultipleOfY = mul i8 %y, %div ; swapped
   %rem = sub i8 %x, %roundXdownToMultipleOfY
   ret i8 %rem