[InstSimplify] fold srem instruction if its two operands are negatived.

[shchenz]

Summary

This is from code review comment from D49382. We already finish related optimization for add instruction in D49216 and sdiv instruction in D49382.

This patch is for srem instruction. for example:

define i32 @negated_operand(i32 %x) {
  %negx = sub i32 0, %x
  %rem = srem i32 %negx, %x
  ret i32 %rem 
}

can be folded to:

define i32 @negated_operand(i32 %x) {
  ret i32 0
}

Alive verification:
https://rise4fun.com/Alive/q20
https://rise4fun.com/Alive/h4o

[lebedev.ri]

I general looks good, i think.

Why do the testcases contain nsw attributes?
We transform anyway, and they aren't required, and don't affect the results.
I'd recommend dropping them. Unless there is a purpose?

llvm/test/Transforms/InstSimplify/srem.ll

1 ↗

(On Diff #155866)

The first line is missing, it should say it was produced with the tool.

20 ↗

(On Diff #155866)

I'd like to see more tests:

define <3 x i32> @negated_operand_vec_undef(<3 x i32> %x) {
  %negx = sub <3 x i32> <i32 0, i32 undef, i32 0>, %x
  %rem = srem <3 x i32> %negx, %x
  ret <3 x i32> %rem
}
define <2 x i32> @negated_operand_vec_nonsplat(<2 x i32> %x) {
  %negx = sub <2 x i32> <i32 0, 1>, %x ; not 0, don't fold
  %rem = srem <2 x i32> %negx, %x
  ret <2 x i32> %rem
}

[shchenz]

fix Roman's comments

[lebedev.ri]

OK, this looks good to me.
Please commit tests first, so the code change only changes the tests, not adds a new ones.

llvm/lib/Analysis/InstructionSimplify.cpp

1112 ↗

(On Diff #156435)

s/negatived/negated/? Not sure which is more correct in english.

llvm/test/Transforms/InstSimplify/srem.ll

11 ↗

(On Diff #156435)

One more test i didn't think of yet:
https://rise4fun.com/Alive/DplN
isKnownNegation() doesn't care about which operand came from which side.
In this case, it is ok, but in general srem/sdiv is not commutative.
It should be kept in mind, and at least one test should verify that we still fold this case properly.

[shchenz]

more testcases are added at rL337543

llvm/lib/Analysis/InstructionSimplify.cpp

1112 ↗

(On Diff #156435)

should be negated.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

 static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
                                unsigned MaxRecurse) {
   // If the divisor is 0, the result is undefined, so assume the divisor is -1.
   // srem Op0, (sext i1 X) --> srem Op0, -1 --> 0
   Value *X;
   if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
     return ConstantInt::getNullValue(Op0->getType());
 
+  // If the two operands are negated, return 0.
+  if (isKnownNegation(Op0, Op1))
+   return ConstantInt::getNullValue(Op0->getType());
+
   return simplifyRem(Instruction::SRem, Op0, Op1, Q, MaxRecurse);
 }
 
 Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifySRemInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Given operands for a URem, see if we can fold the result.

llvm/trunk/test/Transforms/InstSimplify/srem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i32 @negated_operand(i32 %x) {
 ; CHECK-LABEL: @negated_operand(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[NEGX]], [[X]]
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 0
 ;
   %negx = sub i32 0, %x
   %rem = srem i32 %negx, %x
   ret i32 %rem
 }
 
 define <2 x i32> @negated_operand_commute_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_commute_vec(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[REM:%.*]] = srem <2 x i32> [[NEGX]], [[X]]
-; CHECK-NEXT:    ret <2 x i32> [[REM]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
-  %negx = sub nsw <2 x i32> zeroinitializer, %x
+  %negx = sub <2 x i32> zeroinitializer, %x
   %rem = srem <2 x i32> %negx, %x
   ret <2 x i32> %rem
 }
 
 define i32 @knownnegation(i32 %x, i32 %y) {
 ; CHECK-LABEL: @knownnegation(
-; CHECK-NEXT:    [[XY:%.*]] = sub nsw i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[YX:%.*]] = sub nsw i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[XY]], [[YX]]
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 0
 ;
-  %xy = sub nsw i32 %x, %y
-  %yx = sub nsw i32 %y, %x
+  %xy = sub i32 %x, %y
+  %yx = sub i32 %y, %x
   %rem = srem i32 %xy, %yx
   ret i32 %rem
 }
 
 define <2 x i32> @knownnegation_commute_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @knownnegation_commute_vec(
-; CHECK-NEXT:    [[XY:%.*]] = sub nsw <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[YX:%.*]] = sub nsw <2 x i32> [[Y]], [[X]]
-; CHECK-NEXT:    [[REM:%.*]] = srem <2 x i32> [[XY]], [[YX]]
-; CHECK-NEXT:    ret <2 x i32> [[REM]]
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
-  %xy = sub nsw <2 x i32> %x, %y
-  %yx = sub nsw <2 x i32> %y, %x
+  %xy = sub <2 x i32> %x, %y
+  %yx = sub <2 x i32> %y, %x
   %rem = srem <2 x i32> %xy, %yx
   ret <2 x i32> %rem
 }
 
 define <3 x i32> @negated_operand_vec_undef(<3 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_vec_undef(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub <3 x i32> <i32 0, i32 undef, i32 0>, [[X:%.*]]
-; CHECK-NEXT:    [[REM:%.*]] = srem <3 x i32> [[NEGX]], [[X]]
-; CHECK-NEXT:    ret <3 x i32> [[REM]]
+; CHECK-NEXT:    ret <3 x i32> zeroinitializer
 ;
   %negx = sub <3 x i32> <i32 0, i32 undef, i32 0>, %x
   %rem = srem <3 x i32> %negx, %x
   ret <3 x i32> %rem
 }
 
 define <2 x i32> @negated_operand_vec_nonsplat(<2 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_vec_nonsplat(
 ; CHECK-NEXT:    [[NEGX:%.*]] = sub <2 x i32> <i32 0, i32 1>, [[X:%.*]]
 ; CHECK-NEXT:    [[REM:%.*]] = srem <2 x i32> [[NEGX]], [[X]]
 ; CHECK-NEXT:    ret <2 x i32> [[REM]]
 ;
   %negx = sub <2 x i32> <i32 0, i32 1>, %x ; not 0, don't fold
   %rem = srem <2 x i32> %negx, %x
   ret <2 x i32> %rem
 }
 
 define i32 @negated_operand_commute(i32 %x) {
 ; CHECK-LABEL: @negated_operand_commute(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X]], [[NEGX]]
-; CHECK-NEXT:    ret i32 [[REM]]
+; CHECK-NEXT:    ret i32 0
 ;
   %negx = sub i32 0, %x
   %rem = srem i32 %x, %negx
   ret i32 %rem
 }