[InstrSimplify] fold sdiv if two operands are negatived and non-overflow

[shchenz]

Summary

We add folding support for add instruction in D49216. Test cases are added at rL337179.

we should also fold for sdiv instruction if sdiv's two operands are negatived leverage new added interface isKnownNegation() in D49216. for example:

define i32 @negated_operand(i32 %x) {
  %negx = sub nsw i32 0, %x
  %div = sdiv i32 %negx, %x
  ret i32 %div
}

can be folded to

define i32 @negated_operand(i32 %x) {
  ret i32 -1
}

Note: we must ensure sdiv two operands are non-overflow. Otherwise, the optimization is not right.
Result from Alive:
testing transform:

%sub = sub i8 0, %x
%div = sdiv i8 %x, %sub

=>

%div = i8 -1

testing result:
ERROR: Mismatch in values of i8 %div
Example:
%x i8 = 0x80 (128, -128)
%sub i8 = 0x80 (128, -128)
Source value: 0x01 (1)
Target value: 0xFF (255, -1)

[spatel]

Should we generalize this, so we can include 'srem' (doesn't need 'nsw')?
https://rise4fun.com/Alive/tme

It's probably better to make that a separate patch in any case.

I'm going to take a break for a few days, so I may not be able to continue the review promptly. Adding Roman as a potential reviewer.

llvm/lib/Analysis/InstructionSimplify.cpp

1087 ↗

(On Diff #155693)

This is not the right place to add logic. It should go in here instead:
static Value *SimplifySDivInst()
...because that is called internally when the external user makes a call to llvm::SimplifyBinOp()

1092–1100 ↗

(On Diff #155693)

I don't think this behaves as you're expecting. Please add a test like this:

define i32 @irrelevant_sub(i32 %t) {
  %x = sub i32 %t, 5
  %negx = sub nsw i32 0, %x
  %div = sdiv i32 %x, %negx
  ret i32 %div
}

It would be better to match the patterns with m_Neg separately from the case with (x-y)/(y-x).

[shchenz]

fix Sanjay's comments

[shchenz]

@spatel Hi Sanjay, thanks for your comments. I have updated accordingly. For srem instruction, I will make another patch for it. Have a good break^-^

[lebedev.ri]

In general looks sane, but a few notes.

This fold does require nsw on sub, but i'm not seeing tests for that.

define i32 @negated_operand_bad(i32 %x) {
  %negx = sub i32 0, %x ; not nsw
  %div = sdiv i32 %negx, %x
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub nsw i32 %x, %y
  %yx = sub i32 %y, %x ; not nsw
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub i32 %x, %y ; not nsw
  %yx = sub nsw i32 %y, %x
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}
define i32 @knownnegation_bad(i32 %x, i32 %y) {
  %xy = sub i32 %x, %y ; not nsw
  %yx = sub i32 %y, %x ; not nsw
  %div = sdiv i32 %xy, %yx
  ret i32 %div
}

llvm/test/Transforms/InstSimplify/sdiv.ll

40 ↗

(On Diff #155822)

Same as with D49423, i'd like to see a bit more tests:

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

[shchenz]

@lebedev.ri Hi Roman, thanks very much for your comments. I wrongly assumed we only need the cases which are truly transformed by code patch. I will add the cases you point out.

[shchenz]

fix Roman's comments.

[lebedev.ri]

Hmm, if this has issues, then i'm not seeing them.
Please commit tests now, wait 24h just in case anyone else wants to comment, and then feel free to land this.

llvm/include/llvm/Analysis/ValueTracking.h

105 ↗

(On Diff #156433)

s/checkNSW/NeedNSW/

105 ↗

(On Diff #156433)

Also maybe add a comment showing two examples that are handled?

llvm/lib/Analysis/InstructionSimplify.cpp

1085 ↗

(On Diff #156433)

This is also valid with NUW https://rise4fun.com/Alive/zb6
But we do not care because that is 0 https://godbolt.org/g/G55Np1

[shchenz]

@lebedev.ri Hi Roman, thanks for your comments. Testcases are committed. And waiting for other reviewer's comment.

[lebedev.ri]

In D49382#1169656, @shchenz wrote:

@lebedev.ri Hi Roman, thanks for your comments. Testcases are committed.

(You most likely want to rebase this to signify that)

[shchenz]

Fix Roman's comments

[shchenz]

new testcases are added at rL337549

llvm/trunk/include/llvm/Analysis/ValueTracking.h

class Value;
   /// pointer couldn't possibly be null at the specified instruction.
   /// Supports values with integer or pointer type and vectors of integers.
   bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
                       const DominatorTree *DT = nullptr);
 
   /// Return true if the two given values are negation.
-  bool isKnownNegation(const Value *X, const Value *Y);
+  /// Currently can recoginze Value pair:
+  /// 1: <X, Y> if X = sub (0, Y) or Y = sub (0, X)
+  /// 2: <X, Y> if X = sub (A, B) and Y = sub (B, A)
+  bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false);
 
   /// Returns true if the give value is known to be non-negative.
   bool isKnownNonNegative(const Value *V, const DataLayout &DL,
                           unsigned Depth = 0,
                           AssumptionCache *AC = nullptr,
                           const Instruction *CxtI = nullptr,
                           const DominatorTree *DT = nullptr);
 

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 
   return nullptr;
 }
 
 /// Given operands for an SDiv, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
                                unsigned MaxRecurse) {
+  // If two operands are negated and no signed overflow, return -1.
+  if (isKnownNegation(Op0, Op1, /*NeedNSW=*/true))
+    return Constant::getAllOnesValue(Op0->getType());
+
   return simplifyDiv(Instruction::SDiv, Op0, Op1, Q, MaxRecurse);
 }
 
 Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifySDivInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Given operands for a UDiv, see if we can fold the result.
static Value *SimplifySRemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   // 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);
 }
 

llvm/trunk/lib/Analysis/ValueTracking.cpp

static SelectPatternResult matchMinMax(CmpInst::Predicate Pred,
   // (X <s C) ? ~C : ~X ==> (~X >s ~C) ? ~C : ~X ==> SMIN(~C, ~X)
   if (match(FalseVal, m_Not(m_Specific(CmpLHS))) &&
       match(TrueVal, m_APInt(C2)) && ~(*C1) == *C2)
     return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false};
 
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
-bool llvm::isKnownNegation(const Value *X, const Value *Y) {
+bool llvm::isKnownNegation(const Value *X, const Value *Y, bool NeedNSW) {
   assert(X && Y && "Invalid operand");
 
-  // X = sub (0, Y)
-  if (match(X, m_Neg(m_Specific(Y))))
+  // X = sub (0, Y) || X = sub nsw (0, Y)
+  if ((!NeedNSW && match(X, m_Sub(m_ZeroInt(), m_Specific(Y)))) ||
+      (NeedNSW && match(X, m_NSWSub(m_ZeroInt(), m_Specific(Y)))))
     return true;
 
-  // Y = sub (0, X)
-  if (match(Y, m_Neg(m_Specific(X))))
+  // Y = sub (0, X) || Y = sub nsw (0, X)
+  if ((!NeedNSW && match(Y, m_Sub(m_ZeroInt(), m_Specific(X)))) ||
+      (NeedNSW && match(Y, m_NSWSub(m_ZeroInt(), m_Specific(X)))))
     return true;
 
-  // X = sub (A, B), Y = sub (B, A)
+  // X = sub (A, B), Y = sub (B, A) || X = sub nsw (A, B), Y = sub nsw (B, A)
   Value *A, *B;
-  return match(X, m_Sub(m_Value(A), m_Value(B))) &&
-         match(Y, m_Sub(m_Specific(B), m_Specific(A)));
+  return (!NeedNSW && (match(X, m_Sub(m_Value(A), m_Value(B))) &&
+                        match(Y, m_Sub(m_Specific(B), m_Specific(A))))) ||
+         (NeedNSW && (match(X, m_NSWSub(m_Value(A), m_Value(B))) &&
+                       match(Y, m_NSWSub(m_Specific(B), m_Specific(A)))));
 }
 
 static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
                                               FastMathFlags FMF,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
                                               Value *&LHS, Value *&RHS,
                                               unsigned Depth) {

llvm/trunk/test/Transforms/InstSimplify/sdiv.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 nsw i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[NEGX]], [[X]]
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %negx = sub nsw i32 0, %x
   %div = sdiv i32 %negx, %x
   ret i32 %div
 }
 
 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:    [[DIV:%.*]] = sdiv <2 x i32> [[NEGX]], [[X]]
-; CHECK-NEXT:    ret <2 x i32> [[DIV]]
+; CHECK-NEXT:    ret <2 x i32> <i32 -1, i32 -1>
 ;
   %negx = sub nsw <2 x i32> zeroinitializer, %x
   %div = sdiv <2 x i32> %negx, %x
   ret <2 x i32> %div
 }
 
 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:    [[DIV:%.*]] = sdiv i32 [[XY]], [[YX]]
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %xy = sub nsw i32 %x, %y
   %yx = sub nsw i32 %y, %x
   %div = sdiv i32 %xy, %yx
   ret i32 %div
 }
 
 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:    [[DIV:%.*]] = sdiv <2 x i32> [[XY]], [[YX]]
-; CHECK-NEXT:    ret <2 x i32> [[DIV]]
+; CHECK-NEXT:    ret <2 x i32> <i32 -1, i32 -1>
 ;
   %xy = sub nsw <2 x i32> %x, %y
   %yx = sub nsw <2 x i32> %y, %x
   %div = sdiv <2 x i32> %xy, %yx
   ret <2 x i32> %div
 }
 
 define i32 @negated_operand_2(i32 %t) {
 ; CHECK-LABEL: @negated_operand_2(
-; CHECK-NEXT:    [[X:%.*]] = sub i32 [[T:%.*]], 5
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[NEGX]], [[X]]
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %x = sub i32 %t, 5 
   %negx = sub nsw i32 0, %x
   %div = sdiv i32 %negx, %x
   ret i32 %div
 }
 
 define i32 @negated_operand_commute(i32 %x) {
 ; CHECK-LABEL: @negated_operand_commute(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[X]], [[NEGX]]
-; CHECK-NEXT:    ret i32 [[DIV]]
+; CHECK-NEXT:    ret i32 -1
 ;
   %negx = sub nsw i32 0, %x
   %div = sdiv i32 %x, %negx
   ret i32 %div
 }
 
 define i32 @negated_operand_bad(i32 %x) {
 ; CHECK-LABEL: @negated_operand_bad(
;
   %xy = sub <2 x i32> %x, %y ; not nsw
   %yx = sub <2 x i32> %y, %x ; not nsw
   %div = sdiv <2 x i32> %xy, %yx
   ret <2 x i32> %div
 }
 
 define <3 x i32> @negated_operand_vec_undef(<3 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_vec_undef(
-; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw <3 x i32> <i32 0, i32 undef, i32 0>, [[X:%.*]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv <3 x i32> [[NEGX]], [[X]]
-; CHECK-NEXT:    ret <3 x i32> [[DIV]]
+; CHECK-NEXT:    ret <3 x i32> <i32 -1, i32 -1, i32 -1>
 ;
   %negx = sub nsw <3 x i32> <i32 0, i32 undef, i32 0>, %x
   %div = sdiv <3 x i32> %negx, %x
   ret <3 x i32> %div
 }
 
 define <2 x i32> @negated_operand_vec_nonsplat(<2 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_vec_nonsplat(
 ; CHECK-NEXT:    [[NEGX:%.*]] = sub nsw <2 x i32> <i32 0, i32 1>, [[X:%.*]]
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i32> [[NEGX]], [[X]]
 ; CHECK-NEXT:    ret <2 x i32> [[DIV]]
 ;
   %negx = sub nsw <2 x i32> <i32 0, i32 1>, %x ; not 0, don't fold
   %div = sdiv <2 x i32> %negx, %x
   ret <2 x i32> %div
 }