[InstSimplify] Simplify UREM and SREM left shifted operands

[MattDevereau]

Summary

If both operands of a rem instruction are left shifts of the same value, this can be simplified to 0 or the first operand

[MattDevereau]

Here are some alive tests which support the transforms:
https://alive2.llvm.org/ce/z/9KpSpV
https://alive2.llvm.org/ce/z/JFsIPK

negative transformations:
https://alive2.llvm.org/ce/z/9HD6L_
https://alive2.llvm.org/ce/z/PDymNH

[david-arm]

Nice improvement @MattDevereau! I just had a few minor comments ...

llvm/lib/Analysis/InstructionSimplify.cpp

1006

Perhaps you can create a temp variable here to reuse the logic, i.e.

bool NoWrap = (IsSigned && Q.IIQ.hasNoSignedWrap(Shift)) ||
  (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Shift));
if (S1 >= S2 && NoWrap)
  return Constant::getNullValue(Shift->getType());

if (NoWrap)
  return Op0;

llvm/test/Transforms/InstSimplify/rem.ll

502

Could you leave comments on the negative tests explaining why they fail? If it makes it easier you could put all the negative tests together?

539

Is it worth having a negative test for srem with nuw shifts as well? We shouldn't do any simplification in that case either.

[MattDevereau]

llvm/lib/Analysis/InstructionSimplify.cpp

1006

I'm not sure this suggestion is correct, they key thing here being Shift = cast<OverflowingBinaryOperator>(Op1); on line 1010 which changes Shift to be a cast of Op1 instead of Op0 on which the nsw/nuw flags are checked, which is because the larger shift value needs its flags checking. If we went ahead with this, in this example (https://alive2.llvm.org/ce/z/YiFELt) NoWrap would evaluate to true while the transform is not viable.

llvm/test/Transforms/InstSimplify/rem.ll

502

Sure thing, should be simple enough

539

I personally think the current tests are ok since we have one test for nsw which is testing the presence of nsw, and one which tests for it's absence and other flags aren't particularly relevant. These tests are quite compact though so I suppose there's no harm in adding extra cases.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

995

Instead of a new helper maybe this should be in simplifyRem which already appears to have:

// (X << Y) % X -> 0
if (Q.IIQ.UseInstrInfo &&
    ((Opcode == Instruction::SRem &&
      match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
     (Opcode == Instruction::URem &&
      match(Op0, m_NUWShl(m_Specific(Op1), m_Value())))))
  return Constant::getNullValue(Op0->getType());

This is really just a superset of that case, so maybe expanding the existing logic would be simpler?

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

997

Maybe add a TODO for the more generalized case of (rem (mul nsw/nuw X, C1), (mul nsw/nuw X, C2) if C1 % C2 == 0 -> 0 We seem to be missing it: https://godbolt.org/z/fzxb4sxb5

[david-arm]

llvm/test/Transforms/InstSimplify/rem.ll

539

Sure, I was just thinking that specifically we don't want to perform the simplification for any of nsw or nuw. They both mark the instruction as not wrapping, but only the signed version applies here. It's just because your logic accepts both nsw and nuw flags as valid, but *only if* the signedness matches the instruction. I was hoping to defend against someone accidentally rewriting your code in future and losing the signedness checks.

[MattDevereau]

Inlined unnecessary helper function
Added comments to negative tests
Added more incorrect flag tests

[MattDevereau]

llvm/lib/Analysis/InstructionSimplify.cpp

995

I've inlined it into simplifyRem which I think looks a lot neater now. Thank you for the feedback.

llvm/test/Transforms/InstSimplify/rem.ll

539

I've added negative tests for urem with nsw and srem with nuw now.

[MattDevereau]

Note that this patch will likely be dropped in favour of https://reviews.llvm.org/D143014

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyMulInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
   return nullptr;
 }
 
 Value *llvm::simplifyMulInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
                              const SimplifyQuery &Q) {
   return ::simplifyMulInst(Op0, Op1, IsNSW, IsNUW, Q, RecursionLimit);
 }
 
 /// Check for common or similar folds of integer division or integer remainder.
 /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
 static Value *simplifyDivRem(Instruction::BinaryOps Opcode, Value *Op0,
                              Value *Op1, const SimplifyQuery &Q,
                              unsigned MaxRecurse) {
   bool IsDiv = (Opcode == Instruction::SDiv || Opcode == Instruction::UDiv);
   bool IsSigned = (Opcode == Instruction::SDiv || Opcode == Instruction::SRem);
 
   Type *Ty = Op0->getType();
 
   // X / undef -> poison
   // X % undef -> poison
   if (Q.isUndefValue(Op1) || isa<PoisonValue>(Op1))
     return PoisonValue::get(Ty);
 
   // X / 0 -> poison
   // X % 0 -> poison
   // We don't need to preserve faults!
   if (match(Op1, m_Zero()))
     return PoisonValue::get(Ty);
static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
   // (X << Y) % X -> 0
   if (Q.IIQ.UseInstrInfo &&
       ((Opcode == Instruction::SRem &&
         match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
        (Opcode == Instruction::URem &&
         match(Op0, m_NUWShl(m_Specific(Op1), m_Value())))))
     return Constant::getNullValue(Op0->getType());
 
+  // (X << S1) % (X << S2)
+  // (S1 >= S2) ? -> 0 : -> (X << S1)
+  Value *ShiftX;
+  ConstantInt *S1, *S2;
+  if (match(Op0, m_Shl(m_Value(ShiftX), m_ConstantInt(S1))) &&
+      match(Op1, m_Shl(m_Deferred(ShiftX), m_ConstantInt(S2)))) {
+    auto Shl0 = cast<OverflowingBinaryOperator>(Op0);
+    if (S1 >= S2 &&
+        ((Opcode == Instruction::SRem && Q.IIQ.hasNoSignedWrap(Shl0)) ||
+         (Opcode == Instruction::URem && Q.IIQ.hasNoUnsignedWrap(Shl0))))
+      return Constant::getNullValue(Shl0->getType());
+
+    auto Shl1 = cast<OverflowingBinaryOperator>(Op1);
+    if ((Opcode == Instruction::SRem && Q.IIQ.hasNoSignedWrap(Shl1)) ||
+        (Opcode == Instruction::URem && Q.IIQ.hasNoUnsignedWrap(Shl1)))
+      return Op0;
+  }
+
   // If the operation is with the result of a select instruction, check whether
   // operating on either branch of the select always yields the same value.
   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     if (Value *V = threadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
       return V;
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.

llvm/test/Transforms/InstSimplify/rem.ll

 ; CHECK-NEXT:    [[MOD:%.*]] = urem i8 [[MUL]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[MOD]]
 ;
   %d = sdiv i8 %x, %y
   %mul = mul i8 %y, %d
   %mod = urem i8 %mul, %y
   ret i8 %mod
 }
+
+define i8 @urem_shl(i8 %x){
+; CHECK-LABEL: @urem_shl(
+; CHECK-NEXT:    ret i8 0
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nuw i8 %x, 2
+  %1 = urem i8 %x2, %x1
+  ret i8 %1
+}
+
+define i8 @urem_shl_2(i8 %x){
+; CHECK-LABEL: @urem_shl_2(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i8 [[X1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nuw i8 %x, 2
+  %1 = urem i8 %x1, %x2
+  ret i8 %1
+}
+
+define i8 @srem_shl(i8 %x){
+; CHECK-LABEL: @srem_shl(
+; CHECK-NEXT:    ret i8 0
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nsw i8 %x, 2
+  %1 = srem i8 %x2, %x1
+  ret i8 %1
+}
+
+define i8 @srem_shl_2(i8 %x){
+; CHECK-LABEL: @srem_shl_2(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i8 [[X1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nsw i8 %x, 2
+  %1 = srem i8 %x1, %x2
+  ret i8 %1
+}
+
+; Cannot simplify to ret 0 when larger shift is missing nuw with urem
+define i8 @neg_urem_shl_no_nuw(i8 %x){
+; CHECK-LABEL: @neg_urem_shl_no_nuw(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = urem i8 [[X2]], [[X1]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl i8 %x, 2
+  %1 = urem i8 %x2, %x1
+  ret i8 %1
+}
+
+; Cannot simplify to ret %x1 when larger shift is missing nuw with urem
+define i8 @neg_urem_shl_no_nuw_2(i8 %x){
+; CHECK-LABEL: @neg_urem_shl_no_nuw_2(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = urem i8 [[X1]], [[X2]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl i8 %x, 2
+  %1 = urem i8 %x1, %x2
+  ret i8 %1
+}
+
+; Cannot simplify to ret 0 when larger shift is missing nuw with urem; ignore nsw
+define i8 @neg_urem_shl_no_nuw_3(i8 %x){
+; CHECK-LABEL: @neg_urem_shl_no_nuw_3(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl nsw i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = urem i8 [[X2]], [[X1]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nsw i8 %x, 2
+  %1 = urem i8 %x2, %x1
+  ret i8 %1
+}
+
+; Cannot simplify to ret 0 when larger shift is missing nsw with srem
+define i8 @neg_srem_shl_no_nsw(i8 %x){
+; CHECK-LABEL: @neg_srem_shl_no_nsw(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i8 [[X2]], [[X1]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl i8 %x, 2
+  %1 = srem i8 %x2, %x1
+  ret i8 %1
+}
+
+; Cannot simplify to ret %x1 when larger shift is missing nsw with srem
+define i8 @neg_srem_shl_no_nsw_2(i8 %x){
+; CHECK-LABEL: @neg_srem_shl_no_nsw_2(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i8 [[X1]], [[X2]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl i8 %x, 2
+  %1 = srem i8 %x1, %x2
+  ret i8 %1
+}
+
+; Cannot simplify to ret 0 when larger shift is missing nsw with srem; ignore nuw
+define i8 @neg_srem_shl_no_nsw_3(i8 %x){
+; CHECK-LABEL: @neg_srem_shl_no_nsw_3(
+; CHECK-NEXT:    [[X1:%.*]] = shl i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[X2:%.*]] = shl nuw i8 [[X]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = srem i8 [[X2]], [[X1]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %x1 = shl i8 %x, 1
+  %x2 = shl nuw i8 %x, 2
+  %1 = srem i8 %x2, %x1
+  ret i8 %1
+}