[InstCombine] fold X urem C -> X < C ? X : X - C when C is big (PR28672)

[spatel]

Summary

We already have the udiv variant of this transform, so I think this is ok for InstCombine too even though there is an increase in IR instructions. As the tests and TODO comments show, the transform can lead to follow-on combines.

https://llvm.org/bugs/show_bug.cgi?id=28672

[spatel]

Ping.

[efriedma]

Looks fine to me. It makes sense to prefer select as the canonical form.

[spatel]

Thanks, Eli!

llvm/trunk/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombiner::visitURem(BinaryOperator &I) {
 
   // 1 urem X -> zext(X != 1)
   if (match(Op0, m_One())) {
     Value *Cmp = Builder->CreateICmpNE(Op1, Op0);
     Value *Ext = Builder->CreateZExt(Cmp, I.getType());
     return replaceInstUsesWith(I, Ext);
   }
 
+  // X urem C -> X < C ? X : X - C, where C >= signbit.
+  const APInt *DivisorC;
+  if (match(Op1, m_APInt(DivisorC)) && DivisorC->isNegative()) {
+    Value *Cmp = Builder->CreateICmpULT(Op0, Op1);
+    Value *Sub = Builder->CreateSub(Op0, Op1);
+    return SelectInst::Create(Cmp, Op0, Sub);
+  }
+
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);

llvm/trunk/test/Transforms/InstCombine/urem.ll

;
   %r8 = sub i64 %x1, %r7
   ret i64 %r8
 }
 
 ; PR28672 - https://llvm.org/bugs/show_bug.cgi?id=28672
 
 define i8 @big_divisor(i8 %x) {
 ; CHECK-LABEL: @big_divisor(
-; CHECK-NEXT:    [[REM:%.*]] = urem i8 %x, -127
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i8 %x, -127
+; CHECK-NEXT:    [[TMP2:%.*]] = add i8 %x, 127
+; CHECK-NEXT:    [[REM:%.*]] = select i1 [[TMP1]], i8 %x, i8 [[TMP2]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %rem = urem i8 %x, 129
   ret i8 %rem
 }
 
+; TODO: Should this be zext+add instead of sext+sub?
 define i5 @biggest_divisor(i5 %x) {
 ; CHECK-LABEL: @biggest_divisor(
-; CHECK-NEXT:    [[REM:%.*]] = urem i5 %x, -1
+; CHECK-NEXT:    [[NOT_:%.*]] = icmp eq i5 %x, -1
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i1 [[NOT_]] to i5
+; CHECK-NEXT:    [[REM:%.*]] = sub i5 %x, [[TMP1]]
 ; CHECK-NEXT:    ret i5 [[REM]]
 ;
   %rem = urem i5 %x, -1
   ret i5 %rem
 }
 
+; TODO: Should vector subtract of constant be canonicalized to add?
 define <2 x i4> @big_divisor_vec(<2 x i4> %x) {
 ; CHECK-LABEL: @big_divisor_vec(
-; CHECK-NEXT:    [[REM:%.*]] = urem <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[TMP2:%.*]] = sub <2 x i4> %x, <i4 -3, i4 -3>
+; CHECK-NEXT:    [[REM:%.*]] = select <2 x i1> [[TMP1]], <2 x i4> %x, <2 x i4> [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i4> [[REM]]
 ;
   %rem = urem <2 x i4> %x, <i4 13, i4 13>
   ret <2 x i4> %rem
 }